Cryptography Reference
In-Depth Information
6.3 Distinguishers Based on Any Stage of PRGA
So far, we have discussed distinguishing attacks based on biases in the
initial keystream bytes. If the initial keystream output of RC4 (say, the first
1024 bytes) are thrown away, which is the standard practice for real-life ap-
plications, the above attack fails. However, there are a few biased events that
hold at any stage during the PRGA. This section is devoted to these special
distinguishers.
6.3.1 Digraph Repetition Bias
The work in [109] discovered the first distinguisher for RC4 when any
amount of initial keystream bytes are thrown away. This distinguisher is
based on the digraph distribution of RC4. The term digraph means a pair
of consecutive keystream words. In [109, Section 3], it has been shown that
getting strings of the pattern ABTAB, where A,B are bytes and T is a string
of bytes of small length ∆ (typically ∆ ≤ 16) are more probable in RC4
keystream than in random stream. This is called the digraph repetition bias.
In order to prove this bias, the following two lemma are required.
Lemma 6.3.1. Let R be a set of m permutation locations. Suppose that RC4
is in a state where the index i
G
in the next t rounds does not visit R. Then
the probability of the permutation t rounds later to have the same values in R
is approximately e
−
m
N
.
Proof: The index i
G
does not reach any of the indices in R. The index j
G
does not touch a particular position in each of the t rounds with probability
1 −
N
. The set R is untouched, if j
G
does not touch any of the m positions
in any of the t rounds. The probability of this event is (1−
N
)
mt
≈e
−
m
N
.
Lemma 6.3.2. Suppose that S
r−1
[i
r
] = 1 and let g = j
r−1
−i
r−1
. If j
r+g−1
=
i
r−1
, then the probability of the digraph that is outputted in rounds [r + g −
1,r + g] to be identical to the digraph outputted in rounds [r−1,r] is at least
e
8−8
N
.
Proof: By Lemma 6.3.1, the four locations i
r−1
, i
r
, i
r+g−1
and i
r+g
remain unchanged during the g − 2 intermediate rounds with probability
e
−
4(g−2
N
.
The locations of the initial digraph are
= S
r−1
[i
r−1
] + S
r−1
[i
r+g−1
]
t
r−1
= S
r
[i
r
] + S
r
[i
r+g
].
and t
r
Again by Lemma 6.3.1, the two locations t
r−1
and t
r
remain unchanged for
