Cryptography Reference
In-Depth Information
present an evidence that the permutation after the KSA can be distinguished
from random permutation without any assumption on the secret key.
Due to the small keys (say 5 to 32 bytes) generally used in RC4, some of
the assumptions differ from practice and hence the theoretical formulae do
not match with the experimental results for some values of u and v. We also
discuss this issue later.
Lemma 3.2.4. P(S
2
[0] = 1) =
2(N−1)
.
N
2
Proof: In the first round, we have i = 0, and
j
1
= 0 + S[0] + K[0]
= K[0].
In the second round, i = 1 and
j
2
= j
1
+ S
1
[1] + K[1].
Consider two mutually exclusive and exhaustive cases, namely, K[0] = 1 and
K[0] = 1.
Case I: Take K[0] = 1. So, after the first swap, S
1
[0] = 1 and S
1
[1] = 0.
Now,
j
2
= K[0] + 0 + K[1]
= K[0] + K[1].
After the second swap, S
2
[0] will remain 1, if K[0] + K[1] = 0. Hence
the contribution of this case to the event (S
2
[0] = 1) is
1
N
N −1
N
P(K[0] = 1)P(K[0] + K[1] = 0)
=
N −1
N
2
=
.
Case II: Now consider K[0] = 1. After the first swap, S
1
[1] remains 1. Now,
j
2
= K[0] + 1 + K[1]
= K[0] + K[1] + 1.
Thus, after the second swap, S
2
[0] will obtain the value 1, if K[0]+K[1]+
1 = 0. Hence the contribution of this case to the event (S
2
[0] = 1) is
N −1
N
1
N
P(K[0] = 1)P(K[0] + K[1] + 1 = 0)
=
N −1
N
2
=
.