Cryptography Reference
In-Depth Information
tion 5.1]. Consider secret keys of size 32 bytes. From a given 32-byte key K 1 ,
a second 32-byte key K 2 was formed as follows.
8
<
: K 1 [i] for i = 0,...,29;
K 1 [i] + 1 for i = 30;
K 1 [i]−1 for i = 31.
With these two keys, for the first 30 rounds of the KSA, S 1 and S 2 would
remain the same. In round 31 (when i = 30), if j (1)
31
K 2 [i] =
= 30, then j (2)
31 = 31.
Due to this, no swap happens in S (1) and a swap happens in S (2) between the
indices 30 and 31. In the next round (i.e., in round 31), i becomes 31. Now if
j (1)
32 = 31, then j (2)
32 = 30. Again no swap happens in S (1) and a swap happens
in S (2) between the indices 30 and 31. Thus, after the first 32 rounds of the
KSA,
P(S (1)
32
= S (2)
= P(j (1)
31
= 30)P(j (1)
32
32 )
= 31)
2 −16 .
=
Since the 32-byte secret key is repeated 8 times before the KSA is complete,
we have
P(S (1)
N
= S (2)
N
) = (2 −16 ) 8 = 2 −128 .
(3.3)
This collision finding method is based on the natural expectation that the
differences in two byte positions would compensate each other. However, as
Equation (3.3) points out, it is practically infeasible to generate a colliding
key pair using this method for 32-byte key length. In general, since a key
of length l bytes is repeated at least ⌊ N l
⌋ times, the probability of finding a
colliding key pair using the above approach is less than or equal to (2 −16 ) l ,
which decreases when l decreases. This implies that it is more di cult to find
collision for shorter keys than for longer keys.
Later, for the first time, a practical method of constructing colliding key
pairs of RC4 was presented in [111]. However counter-intuitive it may appear,
in [111], no attempt was made to compensate one difference with another.
Rather, the keys were selected so that they differ in a single byte position
only, and the initial differences in the permutation are automatically balanced
at the end of the KSA.
The distance of a key pair at step r may be defined as the number of
distinct bytes between S (1 r and S (2 r . If the distance between a key pair is 0
at r = N, then they are a colliding key pair. A collision search algorithm is
designed in [111], where the key pairs are constructed in such a way that the
distance of a key pair is at most 2 in any step r (1 ≤ r ≤ N). Let us briefly
discuss this search strategy.
For a given key K and two indices y and δ in [0,N −1], define a modified
Search WWH ::




Custom Search