共查询到20条相似文献,搜索用时 15 毫秒
1.
A New Attack on the Filter Generator 总被引:1,自引:0,他引:1
Ronjom S. Helleseth T. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2007,53(5):1752-1758
The filter generator is an important building block in many stream ciphers. The generator consists of a linear feedback shift register of length n that generates an m-sequence of period 2n-1 filtered through a Boolean function of degree d that combines bits from the shift register and creates an output bit zt at any time t. The previous best attacks aimed at reconstructing the initial state from an observed keystream, have essentially reduced the problem to solving a nonlinear system of D=Sigmai=1 d(n/i) equations in n unknowns using techniques based on linear algebra. This attack needs about D bits of keystream and the system can be solved in complexity O(Domega), where omega can be taken to be Strassen's reduction exponent omega=log2(7)ap2.807. This paper describes a new algorithm that recovers the initial state of most filter generators after observing O(D) keystream bits with complexity O((D-n)/2)apO(D), after a pre-computation with complexity O(D(log2D)3) 相似文献
2.
A collision property analysis of the GMR-2 cipher used in the satellite phone was presented.By using the F-component as a bridge,the link between the difference of the key byte and the collision of the output ofFas well as the link between the collision of the output of F and the collision of keystream byte were analyzed,which finally revealed the relationship between the difference of the original key byte and the keystream collision.The theoretical analysis showed that for a random frame number,a special chosen key pair could lead to a keystream collision with a high probability,when the key pair has only one byte difference in which the most significant 4 bit of the difference was equal to the last significant 4 bit.The experimental result shows that the keystream collision probability is 2?8.248,which is far higher than the ideal collision probability 2?120.This proves once again,that there exists serious potential security hazards in the GMR-2 cipher. 相似文献
3.
Sourav Sen Gupta Subhamoy Maitra Goutam Paul Santanu Sarkar 《Journal of Cryptology》2014,27(1):67-108
RC4 has been the most popular stream cipher in the history of symmetric key cryptography. Its internal state contains a permutation over all possible bytes from 0 to 255, and it attempts to generate a pseudo-random sequence of bytes (called keystream) by extracting elements of this permutation. Over the last twenty years, numerous cryptanalytic results on RC4 stream cipher have been published, many of which are based on non-random (biased) events involving the secret key, the state variables, and the keystream of the cipher. Though biases based on the secret key are common in RC4 literature, none of the existing ones depends on the length of the secret key. In the first part of this paper, we investigate the effect of RC4 keylength on its keystream, and report significant biases involving the length of the secret key. In the process, we prove the two known empirical biases that were experimentally reported and used in recent attacks against WEP and WPA by Sepehrdad, Vaudenay and Vuagnoux in EUROCRYPT 2011. After our current work, there remains no bias in the literature of WEP and WPA attacks without a proof. In the second part of the paper, we present theoretical proofs of some significant initial-round empirical biases observed by Sepehrdad, Vaudenay and Vuagnoux in SAC 2010. In the third part, we present the derivation of the complete probability distribution of the first byte of RC4 keystream, a problem left open for a decade since the observation by Mironov in CRYPTO 2002. Further, the existence of positive biases towards zero for all the initial bytes 3 to 255 is proved and exploited towards a generalized broadcast attack on RC4. We also investigate for long-term non-randomness in the keystream, and prove a new long-term bias of RC4. 相似文献
4.
5.
Maximov A. Johansson T. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2007,53(9):3127-3144
A linear distinguishing attack on the stream cipher Scream is proposed. When the keystream is of length 298 words, the distinguisher has a detectable advantage. When the keystream length is around 2120 the advantage is very close to 1. This shows certain weaknesses of Scream. In the process, the paper introduces new general ideas on how to improve the performance of linear distinguishing attacks on stream ciphers. 相似文献
6.
7.
8.
The author examines the application of linear cryptanalysis to the RC5 private-key cipher and shows that there are expected to be weak keys for which the attack is applicable to many rounds. It is demonstrated that, for the 12-round nominal RC5 version with a 64 bit block size and a 128 bit key, there are 228 weak keys for which only ~217 known plaintexts are required to break the cipher. There are 268 keys for which the cipher is theoretically breakable, requiring ~257 known plaintexts. The analysis highlights the sensitivity of RC5 security to its key scheduling algorithm 相似文献
9.
In this paper, we study an E0-like combiner with memory as the keystream generator. First, we formulate a systematic and simple
method to compute correlations of the FSM output sequences (up to certain bits). An upper bound of the correlations is given,
which is useful to the designer. Second, we show how to build either a uni-bias-based or multi-bias-based distinguisher to
distinguish the keystream produced by the combiner from a truly random sequence, once correlations are found. The data complexity
of both distinguishers is carefully analyzed for performance comparison. We show that the multi-bias-based distinguisher outperforms
the uni-bias-based distinguisher only when the patterns of the largest biases are linearly dependent. The keystream distinguisher
is then upgraded for use in the key-recovery attack. The latter actually reduces to the well-known Maximum Likelihood Decoding
(MLD) problem given the keystream long enough. We devise an algorithm based on Fast Walsh Transform (FWT) to solve the MLD
problem for any linear code with dimension L and length n within time O(n+L⋅2
L
). Meanwhile, we summarize a design criterion for our E0-like combiner with memory to resist the proposed attacks. 相似文献
10.
Etzion T. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1999,45(2):693-698
The linear complexity of a de Bruijn sequence is the degree of the shortest linear recursion which generates the sequence. It is well known that the complexity of a binary de Bruijn sequence of length 2n is bounded below by 2n-1+n and above by 2n-1 for n⩾3. We briefly survey the known knowledge in this area. Some new results are also presented, in particular, it is shown that for each interval of length 2[log n]+1 in the above range, there exist binary de Bruijn sequences of length 2n with linear complexity in the interval 相似文献
11.
Harald Niederreiter 《Journal of Cryptology》1990,2(2):105-112
The linear-complexity profile measures the extent to which the initial segments of a keystream sequence can be simulated by linear feedback shift-register sequences. To provide a benchmark for the assessment of keystream sequences, a probabilistic theory of the linear-complexity profile of random sequences is needed. For sequences of elements of a finite field we show probabilistic results that can be derived by a combinatorial method. 相似文献
12.
13.
Frequency-hopping code sequence designs having large linear span 总被引:3,自引:0,他引:3
Kumar P.V. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1988,34(1):146-151
In frequency-hopping spread-spectrum multiple-access communication systems, it is desirable to use sets of hopping patterns that, in addition to having good Hamming correlation properties and large period, are also derived from sequences having large linear span. Here, two such frequency hopping code sequence designs that are based on generalized bent functions and generalized bent sequences are presented. The Hamming correlation properties of the designs are optimal in the first case and close to optimal in the second. In terms of the alphabet size p (required to be prime in both cases), the period and family size of the two designs are given by (p 2, p ) and (p n, p n/2+1) (n an even integer), respectively. The finite field sequences underlying the patterns in the first design have linear span exceeding p , whereas still larger linear spans (when compared to the sequence period) can be obtained using the second design method 相似文献
14.
Hao Chen 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2005,51(5):1854-1856
We prove a result which reduces the computation of the linear complexity of a sequence over GF(pm) (p is an odd prime) with period 2n (n is a positive integer such that there exists an element bisinGF(pm), bn=-1) to the computation of the linear complexities of two sequences with period n. By combining with some known algorithms such as the Berlekamp-Massey algorithm and the Games-Chan algorithm we can determine the linear complexity of any sequence over GF(pm) with period 2tn (such that 2 t|pm-1 and gcd(n,pm-1)=1) more efficiently 相似文献
15.
Golic J.D. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2001,47(3):1032-1041
A theoretical framework for correlation attacks based on edit distances and edit probabilities on binary keystream generators consisting of clock-controlled shift registers combined by a function with memory is introduced. Recursive algorithms for efficient computation of the proposed many-to-one string edit distances and statistically optimal edit probabilities are derived for both constrained and unconstrained irregular clocking. The distances and probabilities are based on mutually correlated linear transforms of input and output sequences in the corresponding regularly clocked combiner with memory. Linear transforms can also incorporate linear models of clock-controlled shift registers. The complexity of the recursive algorithms is exponential in the memory size of the input linear transform which can be considerably smaller than the memory size of combining function. This is demonstrated for a special type of combiners with memory based on a time-varying memoryless function. In addition, a decimation method for reducing the memory size of the input linear transform is proposed. The design criteria with respect to the introduced correlation attacks are also discussed 相似文献
16.
Bent-function sequences 总被引:12,自引:0,他引:12
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1982,28(6):858-864
In this paper we construct a new family of nonlinear binary signal sets which achieve Welch's lower bound on simultaneous cross correlation and autocorrelation magnitudes. Given a parametern withn=0 pmod{4} , the period of the sequences is2^{n}-1 , the number of sequences in the set is2^{n/2} , and the cross/auto correlation function has three values with magnitudesleq 2^{n/2}+1 . The equivalent linear span of the codes is bound above bysum_{i=1}^{n/4}left(stackrel{n}{i} right) . These new signal sets have the same size and correlation properties as the small set of Kasami codes, but they have important advantages for use in spread spectrum multiple access communications systems. First, the sequences are "balances," which represents only a slight advantage. Second, the sequence generators are easy to randomly initialize into any assigned code and hence can be rapidly "hopped" from sequence to sequence for code division multiple access operation. Most importantly, the codes are nonlinear in that the order of the linear difference equation satisfied by the sequence can be orders of magnitude larger than the number of memory elements in the generator that produced it. This high equivalent linear span assures that the code sequence cannot be readily analyzed by a sophisticated enemy and then used to neutralize the advantages of the spread spectrum processing. 相似文献
17.
线性复杂度和k- 错线性复杂度是度量密钥流序列密码强度的重要指标。为了更好地研究序列的随机性,该文通过将序列的k-错线性复杂度的计算转化为求Hamming重量最小的错误序列的方法,讨论了序列不同k-错线性复杂度条件下对应的k-错误序列的分布情况。基于Games-Chan算法,该文给出了线性复杂度为2n的2n-周期二元序列的3错误序列的计数公式,计算机编程验证了该文方法的正确性。 相似文献
18.
Canteaut A. Charpin P. Dobbertin H. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2000,46(1):4-8
We prove the long-standing conjecture of Welch stating that for odd n=2m+1, the power function xd with d=2m+3 is maximally nonlinear on GF(2n) or, in other terms, that the crosscorrelation function between a binary maximum-length linear shift register sequence of degree n and a decimation of that sequence by 2m+3 takes on precisely the three values -1, -1±2m+1 相似文献
19.
Generalized Kasami Sequences: The Large Set 总被引:2,自引:0,他引:2
Xiangyong Zeng Liu J.Q. Lei Hu 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2007,53(7):2587-2598
In this correspondence, new binary sequence families Fk of period 2n-1 are constructed for even n and any k with gcd(k,n)=2 if n/2 is odd or gcd(k,n)=1 if n/2 is even. The distribution of their correlation values is completely determined. These families have maximum correlation 2n/2+1 and family size 23n/2 + 2n/2 for odd n/2 or 23n/2+2n/2-1 for even n/2. The proposed families include the large set of Kasami sequences, where the k is taken as k=n/2+1. 相似文献
20.
当前,由于还没有一个适于一般目的的流密码国际加密标准,流密码的设计与分析引起了广泛关注。在以前的流密码的设计中多采用线性反馈移位寄存器(LFSR)作为基本的部件。然而由于LFSR本身的线性性,基于LFSR的流密码备受攻击,进而相继出现了一些替换部件,例如T函数,带进位的反馈移位寄存器(FCSR)等等。文中给出了一个新的基于FCSR的密钥流生成器。理论分析表明该密钥流生成器具有高度的安全性。NIST统计测试表明该密钥流生成器的伪随机特性是理想的。 相似文献