Statistical weaknesses in the alleged RC4 keystream generator.
Марина Александровна Пудовкина · IACR Cryptology ePrint Archive · 2002
A large number of stream cipher were proposed and implemented over the last twenty years. In 1987 Rivest designed the RC4 stream cipher, which was based on a different and more software friendly paradigm. It was integrated into Microsoft Windows, Lotus Notes, Apple AOCE, Oracle Secure SQL, and many other applications, and has thus become the most widely used a software-based stream cipher. In this paper we describe some properties of an output sequence of RC4. It is proved that the distribution of first, second output values of RC4 and digraphs are not uniform, which makes RC4 trivial to distinguish between short outputs of RC4 and random strings by analyzing their first, or second output values of RC4 or digraphs. 1. Introduction A large number of stream cipher were proposed and implemented over the last twenty years. Most of these cipher were based on various combinations of linear feedback shift registers, which were easy to implement in hardware, but relatively slow in software. In 1987 R. Rivest designed the RC4 stream cipher, which was based on a different and more software friendly paradigm. Its design was kept a trade secret until 1994. An anonymous source claimed to have reverseengineered this algorithm, and published an alleged specification of it in 1994 [1]. It was integrated into Microsoft Windows, Lotus Notes, Apple AOCE, Oracle Secure SQL, and many other applications, and has thus become the most widely used a software-based stream cipher. The alleged RC4 keystream generator is an algorithm for generating an arbitrarily long pseudorandom sequences based on a variable length key. The pseudorandom sequence is conjectured to be cryptographically secure for using in a stream cipher. RC4 is in fact a family of algorithms indexed by parameter m, which is a positive integer. The value of m=256 is of greatest interest, as this is value used by all known RC4 applications. In this paper we describe some properties of an output sequence of RC4. It is proved that the distribution of first, second output values of RC4 and digraphs are not uniform. Also we obtain generalizations results of Fluhrer S.R., McGrew D [2] and Mantin I., Shamir A. [3] for different initial values of i0 and j0. The following standard notation will be used throughout: 1. N ={1,2, .}, 2. Zm={0,1, ,m1}, 3. Sm the set of all possible permutations of Zm. 2. Description of the RC4 cipher The RC4 stream cipher is modeled a finite automata Ag= (F, f , Zm×Zm×Sm, Zm), where F: Zm×Zm×Sm→Zm×Zm×Sm is a next-state function, f: Zm×Zm×Sm→Zm is an output function. The RC4 stream cipher depends on m=2, n∈N . The state of the RC4 cipher at time t is (it, jt, st)∈Zm×Zm×Sm and the initial state is (0, 0, s0,). Consider the RC4 cipher at time t (t=1,2 .). The next-state function F 2 1. it= it1+1 (mod m ); 2. jt = jt1+ st1[it] (mod m ); 3. st[it]= st1[jt], st[jt]= st1[it]; 4. st[r]= st1[r], r= 1 , 0 − m \{it, jt}. The output function f Output: zt= st[( st[jt]+ st[it] )(mod m)]. Encryption xt: ct=xt⊕ zt. Decryption ct: xt=ct⊕ zt. 3. Description of the used probabilistic model We will use the following probabilistic model. Assume that the permutation s0∈Sm is randomly chosen from Sm, i.e. P{s=s0}=1/m!. Consider a probabilistic model without replacement. Then P{s0[r]=a}=1/m, r= 1 , 0 − m , P{s0[rk]=ak |s0[rk1]=ak1, ,s0[r1]=a1}= k m − 1 , where {a1, ,ak}⊆{0, ,m1}, {r1, ,rk}⊆{0, ,m1}, |{a1, , ak}|=|{r1, ,rk}|=k. Let us suppose that P{s=s1}=1/m! и P{s1[r]=a}=1/m, r= 1 , 0 − m , P{ s1[rk]=ak | s1[rk-1]=ak-1, , s1[r1]=a1}= k m − 1 and s1 does not depend on j. Note that j1= j0+s0[i1]= j0+s1[j1]= j0+s0[j0+s1[j1]] и γ1= ( s0[i1]+ s0[j1]) (mod m)= ( s1[i1]+ s1[j1]) (mod m)= ( s1[i1]+ s1[j0+s1[j1]]) (mod m). Proposition 1. Assume that the permutation s0∈Sm is randomly chosen from Sm and γ= (s0[i1]+ s0[j1]) (mod m). 1. If m=1 (mod 2), then a) P{γ=k}= m 1 – ) 1 ( 1 − m m for k ≠2(i1-j0), b) P{γ=2(i1-j0)}= m 2 . 2. If m=0 (mod 2), then a) P{γ=k}= m 1 – ) 1 ( 2 − m m for k=0 (mod 2), k≠2(i1-j0), b) P{γ=k}= m 1 for k=1 (mod 2), c) P{γ=2(i1–j0)}= m 2 . Proof. Using γ=(s0[i1]+s0[j1]) (mod m)=(s1[i1]+ s1[j1])(mod m)=(s1[i1]+s1[j0+s1[j1]])(mod m), we get P{γ=k}=∑ −