Cryptography Reference
In-Depth Information
Chapter 4
Key Recovery from State Information
In the previous chapter, we presented a detailed analysis of the RC4 KSA and
demonstrated different types of biases present in the permutation bytes. Here
we discuss different algorithms for recovering the secret key of RC4 from the
state information.
In a shu
e-exchange kind of stream cipher, for proper cryptographic se-
curity, one may expect that after the key scheduling algorithm one should
not be able to get any information on the secret key bytes from the random
looking permutation in time complexity less than the exhaustive key search.
The KSA of RC4 is weak in this aspect.
There are three primary motivations for studying the possibility of key
recovery from a known RC4 state.
1. An important class of attacks on RC4 is the class of state recovery
attacks [87, 116, 181]. Key recovery from the internal state is useful to
turn a state recovery attack into a key recovery attack. If the complexity
of recovering the secret key from the permutation is less than that of
recovering RC4 permutation from the keystream, then by cascading the
techniques of the latter with those of the former, recovering the secret
key from the keystream is possible at the same complexity as the latter.
2. In many practical applications, a secret key is combined with a known IV
to form a session key. Generally, recovering the permutation is enough
for cryptanalysis of a single session only. However, there are many ap-
plications (such as WEP [92]), where the key and the IV are combined
to form the session key in such a way that the secret key can be easily
extracted from the session key. For such an application, if the session
key can be recovered from the permutation, then the secret key is im-
mediately broken. Moreover, for subsequent sessions, where the same
secret key would be used with different known IVs, the RC4 encryption
would be rendered completely insecure.
3. Apart from cryptanalytic significance, the different methods of key re-
trieval from state information provide guidelines in designing improved
versions or modes of operations of RC4 with better security.
The first section of this chapter shows that the steps of RC4 PRGA are
reversible and hence explains why the final permutation after the KSA should
be the starting point of key recovery from state information.
