Key Recovery from State Information - RC4: Stream Cipher and Its Variants - page 66

i τ = τ mod N. All subtractions except r = r−1 in Algorithm PRGAreverse
are performed modulo N.
Input:
1. Number of rounds τ.
2. The permutation S τ .
Output: Few candidates for S N , the final permutation after the
KSA.
i τ = τ mod N;
for j τ = 0 to N −1 do
i = i τ ; j = j τ ; S = S τ ; r = τ;
repeat
Swap(S[i], S[j]);
j = j −S[i]; i = i−1; r = r−1;
until r = 0 ;
if j = 0 then
Report S as a candidate for S N ;
end
end
Algorithm 4.1.1: PRGAreverse
Once S N is derived from the current state information, the next step of
the attacker would be to invert S N to get back the secret key. The technique
for recovering the secret key from the permutation after the KSA or at any
stage during the KSA is the main theme of the following sections.
4.2 Recovery through Solving Simultaneous Equations
This was the first strategy developed for secret key recovery of RC4 from
the permutation after the KSA [133]. The complexity is of the order of square
root of exhaustive search complexity, i.e., for a secret key of size 8l bits (40 ≤
8l ≤ 128), the key can be recovered in O(2 8 2 ) effort with a constant probability
of success.
To illustrate the idea, let us start with an example.
Example 4.2.1. Consider a 5-byte secret key K[0...4] with K[0] =
106,K[1] = 59,K[2] = 220,K[3] = 65, and K[4] = 34. If one runs the KSA
with this key, then the first 16 bytes of the final permutation are as follows.