Variants of RC4 - RC4: Stream Cipher and Its Variants - page 230

• Incorporating the bytes S[t ′ ],S[t ′′ ], in addition to the existing S[t] in
RC4, makes the running time of PRGA + little more than that of RC4
PRGA (see Section 9.4.3 for details). The evolution of the permutation
S in PRGA + stays exactly the same as in RC4 PRGA.

• A constant value 0xAA (equivalent to 10101010 in binary) is used in t ′ .
Without this, if j G becomes 0 in rounds 256, 512, ... (i.e., when i G = 0),
then t and t ′ in such a round become equal with probability 1, giving
an internal bias.

Input: Key-dependent scrambled permutation array S[0...N −1].
Output: Pseudo-random keystream bytes z.
Initialization:
i = j = 0;
Output Keystream Generation Loop:
i = i + 1;
j = j + S[i];
Swap(S[i], S[j]);
t = S[i] + S[j];
t ′ = (S[i 3 R ⊕j L ] + S[i L ⊕j R ])⊕ 0xAA;

t ′′ = j + S[j];
Output z = (S[t] + S[t ′ ])⊕S[t ′′ ];
Algorithm 9.4.2: PRGA + of RC4 +

Resisting state recovery attacks

We already explained in Chapter 5.8 the basic idea of cryptanalysis in [116],
the best known state recovery attack on RC4. Corresponding to a window of
w + 1 keystream output bytes, one may assume that all the j G 's are known,
i.e., j r ,j r+1 ,...,j r+w are known. Thus w many permutation entries S r [i r ]
would be available from j r+1 − j r . Then w many equations of the form

S G −1

r [z r ] = S r [i r ] +S r [j r ] can be formed where each equation contains only
two unknowns.
PRGA + does not allow the strategy of [116] to work, since S G [S G [i G ] +
S G [j G ]] is not exposed directly; rather it is masked by several other quan-
tities. To form the equations as given in [116], one first needs to guess
S G [t],S G [t ′ ],S G [t ′′ ]. However, looking at the value of z, there is no other op-
tion than to go for all the possible choices. The same permutation structure of
S in RC4 + could be similarly exploited to get the good patterns [116, Section
3], but introducing the additional output indices t ′ ,t ′′ , the non-detectability
of such a pattern in the keystream is ensured and thus the idea of [116, Section
4] would not work.
Information on permutation entries is also leaked in the keystream via the