Cryptography Reference
In-Depth Information
Adding the above two contributions, we get the result.
In the next chapter (in Section 6.3.2), a corollary of this theorem would
be used to construct a new distinguisher.
The analysis performed in this section presents some weaknesses in RC4
design. On the positive side, the elegant structure of RC4 allows such an
analysis possible by pen and paper and shows that there does not exist any
hidden trapdoor in the design. Most of the recent software stream ciphers
(e.g. the eSTREAM candidates) are significantly more complicated than RC4.
However, the complicated nature of these ciphers may not allow a detailed
theoretical analysis of even a single step during the keystream generation.
5.5 Some Biases in First Keystream Byte toward Secret
Key
A bias of the first keystream byte z
1
toward K[2] + 3, given that the sum
of the first two key bytes is zero, was first observed by Roos [146]. This result
was subsequently proved in [131], which reported some additional biases in
z
1
. We present all these biases in this section.
The expression
N
N −1
N
1−
1
N
−
1
N
2
1
N
2
+
will be used a number of times in this section. So we denote it by the symbol
φ
N
.
Here we are interested in z
1
that is generated in the first round of PRGA. So
let us analyze the first round in detail and introduce some additional notations.
Before the PRGA begins, we have
i
0
= j
0
= 0.
Let
S
0
[1] = u and S
0
[u] = v.
In the first round, i
1
= 1 and
j
1
= 0 + S
0
[1]
= u.
The contents u and v of locations 1 and u respectively are interchanged. Thus,
after the first round, we have
S
1
[1] = v and S
1
[u] = u.
