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,
Search WWH ::




Custom Search