Cryptography Reference
In-Depth Information
for γ = 0.
Thus, for r ≥ 0,
1
N
2
N
2
P(z
r+2
= z
r+1
| 2z
r+1
= i
r+1
) =
1 +
.
In other words, for r ≥ 1,
1
N
2
N
2
| 2z
r
= i
r
) =
P(z
r+1
= z
r
1 +
.
The result of Theorem 6.3.4 provides a new distinguisher for RC4. Using
the formulation of distinguishing attacks from Section 6.1, let p
0
=
1
N
and
N
2
. Given N = 2
8
, we require 2
32
,2
38
,2
40
and 2
42
keystream bytes
with success probabilities 0.5249, 0.6915, 0.8413 and 0.9772 respectively to
distinguish RC4 keystream from a uniformly random stream by observing the
event
2
ǫ =
(z
r+1
= z
r
) given 2z
r
= i
r
.
The event 2z
r
= i
r
mod N is expected to occur once in a sequence of N
consecutive keystream output bytes. Thus the number of keystream bytes
needed to mount the distinguisher would be multiplied by N. Hence the
distinguisher actually requires 2
40
,2
46
,2
48
and 2
50
keystream bytes to get
success probabilities 0.5249, 0.6915, 0.8413 and 0.9772 respectively.
Following Item 1 of Corollary 5.4.2 and Theorem 5.4.8, one may note that
| i
r
even)
is positively biased. However, this bias is weaker than that presented in The-
orem 6.3.4.
P(z
r+1
= z
r
6.3.3 Extension of “z
2
= 0” Bias: Best Long-Term Bias in
Keystream
Since the work of Mantin [109] in 2005, it has been an open question
whether there is any other significant long-term bias of RC4 in the keystream.
The bias described in Section 6.3.2 is much weaker than that of [109]. Recently,
the best long-term bias in RC4 keystream has been discovered [157]. Below
we present this result.
RC4 PRGA rounds are typically seen in multiples of N = 256:
{1,2,...,255}
{256,258,...,511}
,
where the first period was 1 short of 256 rounds. The analysis in this section
views the PRGA rounds in the following structure
{1,2,...,255}
{256}
{257,258,...,511}
{512}
,
where each long period is exactly 255 rounds. Thus,