Analysis of Key Scheduling - RC4: Stream Cipher and Its Variants - page 58

3 3

2.8 2.8

2.6 2.6

2.4 2.4

2.2 2.2

2 2

1.8 1.8

1.6 1.6

1.4 1.4

0 50 100 150 200 250 300 0 50 100 150 200 250 300

v −> v −>

FIGURE 3.6: Experimental and theoretical E v versus v, 0 ≤ v ≤ 255.

In [5, 134], it is shown that the probabilities P(j y+1 = S − N [y]) increase
with increasing y. This is related to the above decreasing pattern in the
expectations. In the first half of the KSA, i.e., when y is small, the values
v = S[y] are thrown more to the right of S with high probability by the index
j y+1 due to the swaps and hence are touched again either by the deterministic
index i or by the pseudo-random index j in the subsequent rounds. On the
other hand, in the second half of the KSA, i.e., when y ≥ 128, the values
v = S[y] are thrown more to the left of S by the index j y+1 due to the
swap and hence are never touched by i in the subsequent rounds, and may be
touched by j with a small probability.
An important requirement in designing a key scheduling algorithm in
shu e-exchange paradigm is that each value in the permutation should be
touched (and therefore moved with probability almost one) su cient number
of times. This would make it harder to guess the values of j for which a
permutation byte is swapped. However, in RC4 KSA, there are many permu-
tation bytes which are swapped only once with a high probability, leading to
information leakage from S N regarding the secret key bytes.

3.4 Key Collisions
Suppose S (1) and S (2) are the internal states and j (1) and j (2) are the j
index when the RC4 KSA is executed with two different secret keys K 1 and
K 2 respectively. The keys K 1 and K 2 are called colliding keys, if they yield
the same internal state after the KSA (i.e., if S (1)
N

= S (2)
N

) and hence produce

the same keystream sequence during the PRGA.
Construction of a colliding key pair of RC4 was first attempted in [14, Sec-