Cryptography Reference
In-Depth Information
depending on whether
j
τ
> τ mod N or j
τ
≤ τ mod N
respectively. If we know the values of j
G
at multiple stages of the PRGA
(it may be possible to read some values of j
G
through side-channel attacks),
then the biases propagate further down the keystream. The following example
illustrates how the biases propagate down the keystream output bytes when
single as well as multiple j
G
values are known.
Example 5.6.7. Suppose we know the value of j
5
as 18. With probability
η
5
, S
4
[5] would have remained f
5
which would move to index 18 due to the
swap in round 5, i.e., S
5
[18] = f
5
. With approximately
18−5−1
−
1
N
N −1
N
1
N
η
5
+
probability, f
5
would remain in index 18 till the end of the round 18-1 = 17.
Thus, we immediately get a bias of z
18
with 18−f
5
.
Further, in round 18, f
5
would move from index 18 to j
18
. If the value
of j
18
is also known, say j
18
= 3, then we have S
18
[3] = f
5
. We can apply
the same line of arguments for round 256 + 3 = 259 to get a bias of z
259
with
259−f
5
. Experiments with 1 billion random keys demonstrate that in this case
the bias of z
18
toward 18−f
5
is 0.0052 and the bias of z
259
toward 259−f
5
is
0.0044. These conform to the theoretical values and show that the knowledge
of j
G
during the PRGA helps in finding non-random association (away from
1
256
= 0.0039) between the keystream bytes and the secret key.
5.7 Exhaustive Enumeration of All Biases
Recently, experimental results of an exhaustive search for biases in all
possible linear combinations of the state variables and the keystream bytes of
RC4 were published in [158]. In this work, the linear equations are modeled
as
a
0
i
r
+ a
1
j
r
+ a
2
S
r
[i
r
] + a
3
S
r
[j
r
] + a
4
z
r
= b,
(5.1)
where the a
i
's and b belong to Z
N
and the additions are modulo N. This
gives 2
48
linear equations corresponding to each round r of RC4 PRGA. Now,
b−a
0
i
r
can be regarded as a single variable C, reducing Equation (5.1) to
c
0
j
r
+ c
1
S
r
[i
r
] + c
2
S
r
[j
r
] + c
3
z
r
= C.
(5.2)
The number of equations 5.2 are further reduced as follows. The equations
are grouped into 256 classes, each corresponding to a specific value of C ∈
Z
N
.
