Cryptography Reference
In-Depth Information
swapped out and we have S 1 [i 2 ] = S 1 [2] = 0. Hence, j 2 = S 0 [i 1 ] =
j 1 and
z 2 = S 2 [S 2 [i 2 ] + S 2 [j 2 ]]
= S 2 [S 1 [j 2 ] + S 1 [i 2 ]]
(reverting the swap in round 2)
= S 2 [S 1 [j 2 ]]
(since S 1 [i 2 ] = 0)
= S 2 [S 1 [j 1 ]]
(since j 2
= j 1 )
= S 2 [S 0 [i 1 ]]
(reverting the swap in round 1)
= S 2 [j 2 ]
(since j 2 = S 0 [i 1 ])
= S 1 [i 2 ]
(reverting the swap in round 2)
= 0.
Thus,P(z 2 = 0 | S 0 [2] = 0)
= P(j 1
= 2 | S 0 [2] = 0)
= P(S 0 [1] = 2 | S 0 [2] = 0)
N −2
N −1 ,
=
assuming j 1 to be uniformly random over the set Z N
\{0} of its possible
values. Note that since the permutation S 0 has the entry 0 at index 2,
it cannot have the entry 0 at index 1.
Case II: Suppose that S 0 [2] = 0. Assuming z 2 is uniformly random in this
case, we have P(z 2 = 0 | S 0 [2] = 0) =
1
N .
Combining these two cases, we get
= P(S 0 [2] = 0)P(z 2 = 0 | S 0 [2] = 0)
+P(S 0 [2] = 0)P(z 2 = 0 | S 0 [2] = 0)
P(z 2 = 0)
1
N
N − 2
N − 1
N −1
N
1
N
=
+
2
N
1
N 2
1
N(N −1)
2
=
N .
Hence the result.
According to Theorem 3.2.3, the underlying assumption of [107] regarding
the randomness of the permutation is violated in practice. However, it does
not affect the final result of Theorem 6.2.3 much.
Theorem 6.2.3 gives a distinguisher which is currently the best known
distinguisher for RC4. Let X and Y be the distributions corresponding to
random stream and RC4 keystream respectively and define A as the event
“z 2 = 0.” The bias
N can be written as p 0 (1 + ǫ), where p 0 = 1 N and ǫ = 1.
According to Theorem 6.1.1, the number of samples required to distinguish
2
Search WWH ::




Custom Search