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