Cryptography Reference
In-Depth Information
Mantin mentioned in [52, Appendix D] as well as in [110, Appendix A.2]
how to recover the first A bytes of the secret key from an “Early Permutation
State” after round A. Apart from this, key recovery from RC4 permuta-
tion has earlier been considered in various forms [86,180,184] (see Chapter 7
for details). However, the first algorithm to recover the complete key from
the final permutation after the KSA, without any assumption on the key
or IV, appeared in [133, Section 3]. This work is described in Section 4.2.
Subsequently, Biham and Carmeli [15] refined the idea of [133] to devise an
improved algorithm. We summarize this improvement in Section 4.3. The
following section, i.e., Section 4.4, outlines further improvement in the sequel
made by Akgun et al. [5]. Around the same time as [5], two other independent
techniques for the secret key recovery were developed. One takes a byte-by-
byte approach [134, Sections 2.3, 3.4] and the other a bit-by-bit approach [83].
These two works are described in Sections 4.5 and 4.6 respectively. Finally,
Section 4.7 concludes this chapter by describing the recently developed bidi-
rectional key recovery algorithm [10] based on certain sequences of the index
j.
4.1 Reversibility of RC4 PRGA
The RC4 state information consists of
• the entire permutation S,
• the number of keystream output bytes generated (which is related to
the index i) and
• the value of the index j.
If this state information at any instant during the PRGA is available, then it
is possible to run the PRGA backwards to get back to the permutation after
the KSA. Once the final permutation after the KSA is retrieved, the secret
key can be reconstructed using any one of the techniques described in the
subsequent sections.
Suppose we know the RC4 internal state after τ rounds of PRGA. We can
get back the permutation S
N
after the KSA using the PRGAreverse algorithm
described below. Even when the value j
τ
of the index j is not known, one
can make an exhaustive search over Z
N
and for each value perform the state-
reversing loop in PRGAreverse. If, for a value of j
τ
, the final value of j after
the completion of the loop equals zero, the resulting final permutation is a
candidate for S
N
. On average, one expects to get one such candidate.
Note that we do not need the keystream bytes themselves. The algorithm
requires the value of τ only. From τ, we can get the current value of i as
