Cryptography Reference
In-Depth Information
Z N is propagated to
z r , the final bias at z r is quite small and di cult to observe experimentally.
Rather, if we start with the bias of S N [r] toward many values in some suitably
chosen set B ⊂
When the bias of S N [r] toward a single value v ∈
Z N , then according to Theorem 6.2.15, a sum of b = |B| many
probabilities is propagated to z r , making the bias of z r empirically observable
too. For instance, given 1 ≤ r ≤ 127, consider the set B = {r+1,...,r+128},
i.e., b = |B| = 128. The formulae of Theorem 3.2.11 gives
P(S N [r] ∈B) > 0.5,
and in turn we get
∈C) > 0.5,
which is clearly observable at the r-th keystream output byte of RC4. It is im-
portant to note that the non-uniform distribution can be observed even at the
256-th output byte z 256 , since the deterministic index i at round 256 becomes
0 and S N [0] has a non-uniform distribution according to Theorem 3.2.11. For
random association, P(z r
P(z r
b
N , which is not the case here, and
thus all these results provide several distinguishers for RC4.
In Section 3.2.3, it has already been pointed out that for short key lengths,
there exist many anomaly pairs. One may exploit these to construct some
additional distinguishers by including in the set B those values which are far
away from being random. We illustrate this in the following two examples.
For 5-byte secret keys, the experimentally observed value of P(S N [9] ∈ B)
is 0.137564, calculated from 100 million runs, where B is the set of all even
integers greater than or equal to 128 and less than 256, i.e., b = |B| = 64
and
∈ C) should be
b
N = 0.25. The value 0.137564 is much less than the theoretical value
0.214785. Applying Theorem 6.2.15 we get
P(z 9
∈C) = 0.249530 < 0.25,
where
C = {c | c = 9−b where b ∈ B}.
Again, for 8-byte secret keys, we experimentally find that P(S N [15] ∈ B) =
0.160751, which is much less than the theoretical value 0.216581, where B is
the set of all odd integers greater than or equal to 129 and less than 256, i.e.,
b = |B| = 64 once again. Theorem 6.2.15 gives
P(z 15 ∈C) = 0.249340 < 0.25,
where
C = {c | c = 15−b where b ∈ B}.
Direct experimental data on the keystream also confirm these biases of z 9
and z 15 . Further, given the values of δ approximately −0.1 in the above two
examples, one can form new linear distinguishers for RC4 with 5-byte and
8-byte keys.
It is interesting to note that since the anomaly pairs are different for differ-
ent key lengths, one can also distinguish among RC4 of different key lengths,
by suitably choosing the anomaly pairs in the set B.
Search WWH ::




Custom Search