Cryptography Reference
In-Depth Information
next g rounds (t
r−1
unchanged in rounds r,...,r + g − 1 and t
r
unchanged
in rounds r + 1,...,r + g) with probability e
−
2
N
, given that the index i
G
in
these g rounds does not touch them. But each of t
r−1
and t
r
does not fall in
the i
G
-affected area with probability 1 −
N
and hence the probability of the
values at t
r−1
and t
r
to remain in place is
1−
g
N
2
e
−
2
N
≈e
−
4
N
(for small g).
Thus the overall probability of all indices to be in place is at least
e
−
4(g−2)
e
−
4
N
= e
8−8
N
.
N
Now, using the above two results, we are going to prove the main result
on the digraph repetition bias.
Theorem 6.3.3. For small values of ∆, the probability of the pattern ABTAB
in RC4 keystream, where T is a ∆-word string is
N
2
(1 +
e
−8−8∆
1
N
N
).
−i
r−1
as defined in Lemma 6.3.2, the real gap between
the digraphs is ∆ = g−2. The digraph repetition can occur in two ways.
Proof: If g = j
r−1
1. When the conditions of Lemma 6.3.2 are satisfied, the digraph repeti-
tion occurs with probability e
8−8g
= e
−8−8∆
. The probability of the
N
N
conditions being satisfied is
P(S
r−1
[i
r
] = 1)P(j
r−1
= i
r+∆+1
)P(j
r+∆+1
= i
r−1
) =
1
N
3
.
Thus, the contribution of this part is
e
−8−8∆
N
N
3
.
2. When the conditions of Lemma 6.3.2 are not satisfied (the probability of
which is 1−
N
3
), it may be assumed that the digraph repetition occurs
due to random association (the probability of which is
1
N
2
). Hence the
contribution of this part is
1−
N
3
N
2
.
Adding the above two components, we get the total probability to be approx-
imately
N
2
(1 +
e
−8−8∆
1
N
N
).
Note that in uniformly random stream, the probability of digraph repeti-
tion is
1
N
2
, irrespective of the length ∆ of T. Whereas in RC4, the probability
of such an event is more than
1
1
1
N
3
.
Using information theoretic arguments [21], it is claimed in [109] that the
number of samples required to distinguish RC4 from uniform random stream
are 2
29
,2
28
,2
26
for success probabilities 0.9,0.8 and
3
respectively.
N
2
and little less than
N
2
+
