New Results on Generalization of Roos-Type Biases and Related Keystreams of RC4

The first known result on RC4 cryptanalysis (presented by Roos in 1995) points out that the most likely value of the

y

-th element of the permutation after the key scheduling algorithm (KSA) for the first few values of

y

is given by

S

N

[

y

] = 

f

y

, some linear combinations of the secret keys. While it should have been quite natural to study the association

S

N

[

y

] = 

f

y

±

t

for small positive integers

t

(e.g.,

t

 ≤ 4), surprisingly that had never been tried before. In this paper, we study that problem for the first time and show that though the event

S

N

[

y

] = 

f

y

 + 

t

occurs with random association, there is a significantly high probability for the event

S

N

[

y

] = 

f

y

 − 

t

. We also present several related non-randomness behaviour for the event

S

N

[

S

N

[

y

]] = 

f

y

 − 

t

of RC4 KSA in this direction. Further, we investigate near-colliding keys that lead to related states after the KSA and related keystream bytes. Our investigation reveals that near-colliding states do not necessarily lead to near-colliding keystreams. From this motivation, we present a heuristic to find a related key pair with differences in two bytes, that lead to significant matches in the initial keystream. In the process, we discover a class of related key distinguishers for RC4. The best one of these shows that given a random key and a related one to that (the last two bytes increased and decreased by 1 respectively), the first pair of bytes corresponding to the related keys are same with very high probability (e.g., approximately 0.011 for 16-byte keys to 0.044 for 30-byte keys).