Cryptography Reference
In-Depth Information
3. If z
r
is equal to the value v previously assigned to index u of S
G
, then
t
r
= S
r
[i
r
] + S
r
[j
r
] becomes equal to u. This either uniquely deter-
mines S
r
[j
r
] or leads to a contradiction.
The above algorithm can be e
ciently implemented using recursion on the
time step r. The recursion steps backward if a contradiction is reached, due
to the previously wrong guesses. If M (out of N) many permutation entries
are a priori known, the complexity can be reduced further. For N = 256, the
complete attack complexity turns out to be around 2
779
. The time complexity
of the attack for various values of N and M are enumerated in Tables D.1
and D.2 of [110, Appendix D.4].
In [123], the cycle structures in RC4 are investigated in detail and a “track-
ing” attack is proposed. This strategy recovers the RC4 state, if a significant
fraction of the full cycle of keystream bits is available. For example, the state
of a 5-bit RC4-like cipher can be derived from a portion of the keystream
using 2
42
steps, while the nominal key-space of the system is 2
160
.
The work [165] showed that Knudsen's attack [87] requires 2
220
search com-
plexity if 112 entries of the permutation are known a priori. It also presents
an improvement whereby state recovery with the same complexity can be
achieved with prior knowledge of only 73 permutation entries in certain cases.
In [181], an improvement over [87] is proposed using a tree representation
of RC4. At time-step r, the nodes are distributed at r + 1 levels. Nodes at
level h, 0 < h ≤ r, correspond to the set of all possible positions in S
r−h
where z
r
can be found. The nodes are linked by the branches which represent
the conditions to pass from one node to another. In order to find the internal
state, such a tree of general conditions is searched by a hill-climbing strategy.
This approach reduces the time complexity of the full RC4 state recovery from
2
779
to 2
731
.
5.8.3 Maximov et al.'s Attack
The best known result for state recovery has been reported in [116]. It
shows that the permutation can be reconstructed from the keystream in
around 2
241
complexity. This renders RC4 insecure when the key length is
more than 30 bytes (240 bits).
The basic idea of cryptanalysis in [116] is as follows. Corresponding to a
window of w + 1 keystream output bytes from some round r, it is assumed
that all the j
G
's are known, i.e., j
r
,j
r+1
,...,j
r+w
are known. Thus w many
state variable values S
r+1
[i
r+1
],...,S
r+w
[i
r+w
] can immediately be computed
as
S
t+1
[i
t+1
] = j
t+1
−j
t
,
t = r,r + 1,...,r + w−1.
Then w many equations of type
(S
t
)
−1
[z
t
] = S
t
[i
t
] + S
t
[j
t
],
t = r,r + 1,...,r + w.
(5.9)
