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

3.1.3 Biases of Nested Permutation Entries to Secret Key
We have, so far, explained the biases of the elements S[y] toward the se-
cret key. The next natural question to ask is whether there exists any bias
if we consider accessing the elements of S by more than one level of index-
ing. The work [103] established that the entries S[S[y]] are indeed corre-
lated to the secret key for different values of y. As the KSA proceeds, the
probabilities P(S[y] = f y ) decrease monotonically, whereas the probabilities
P(S[S[y]] = f y ) first increases monotonically until the middle of the KSA and
then decreases monotonically until the end of the KSA.
Let us first discuss how P(S r [S r [1]] = f 1 ) varies with round r,1 ≤r ≤ N,
during the KSA of RC4. Refer to Figure 3.1 that demonstrates the nature of
the curve with an experimentation using 10 million randomly chosen secret
keys. The probability P(S r [S r [1]] = f 1 ) increases till around r =

N

2 where
it gets the maximum value around 0.185 and then it decreases to 0.136 at
r = N. On the other hand, as we saw in Theorem 3.1.5, P(S r [1] = f 1 )
decreases continuously as r increases during the KSA.

0.2

0.18

0.16

0.14

0.12

0.1

0.08

0.06

0.04

0.02

0

0 50 100 150 200 250 300

i −−−−>

FIGURE 3.1: P(S i+1 [S i+1 [1]] = f 1 ) versus i (r = i + 1) during RC4 KSA.

We first present theoretical analysis for the base case for r = 2, i.e., after
round 2 of the RC4 KSA.
Lemma 3.1.12. P(S 2 [S 2 [1]] = K[0] + K[1] + 1) =

3
N

− N 2 +

2

N 3 .

Further, P(S 2 [S 2 [1]] = K[0] + K[1] + 1∧S 2 [1] ≤ 1) ≈ N .
Proof: The proof is based on three cases.