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

9.4 RC4 +
In all the variants we discussed so far, the design is modified to a great
extent relative to RC4. In [101], a new variant called RC4 + is presented
that keeps the RC4 structure as it is and adds a few more operations to
strengthen the cipher. This design attempts to exploit the good points of
RC4 and then provide some additional features for a better security margin.
The existing literature on RC4 reveals that in spite of having a very simple
description, the cipher possesses nice combinatorial structures in the shu e-
exchange paradigm. The design of [101] retains this elegant property of RC4
and at the same time removes the existing weaknesses of RC4.
Section 9.4.1 focuses on the design of the new key scheduling. After a
summary of the existing weaknesses of the RC4 KSA, the description of the
modified KSA is presented. It is also argued that the new algorithm KSA +
circumvents the weaknesses of the standard RC4 KSA. Section 9.4.2 explains
the modification of the RC4 PRGA, called PRGA + . Logical arguments as
well as empirical evidence are provided to support the security conjectures
of the new design. Finally, Section 9.4.3 presents a study on the software
performance of both the KSA + and PRGA + .

9.4.1 KSA + : Modifications to RC4 KSA
First, let us review the important weaknesses of RC4 KSA, that the new
design attempts to get rid of.

1. Roos' biases, i.e., biases of S N [y] toward f y for initial values of y
are described in detail in Section 3.1.1. In summary, the probability
P(S N [y] = f y ) decreases from 0.37 for y = 0 to 0.006 for y = 48 and
then settles down to 0.0039 (≈ 256 ).
2. In addition to S N [y], the nested entries S N [S N [y]], S N [S N [S N [y]]],
and so on, are also biased to f y . In particular, they proved that
P(S N [S N [y]] = f y ) decreases from 0.137 for y = 0 to 0.018 for y = 31
and then slowly settles down to 0.0039 (beyond y = 48). We discuss
these results in Section 3.1.3.

3. Recall from Section 4.5.1 that the the inverse permutation entries S −1
N

[y],

S −1
N

[S −1
N

[y]], and so on are biased to j y+1 , and in turn, to f y .

4. The above biases and related results can be used to recover the secret key
from the final permutation S N after the KSA, as discussed in Chapter 4
in detail.

5. In RC4 KSA, the update rule is given by j = (j + S[i] + K[i]). In
Section 3.1.2, it has been demonstrated that for a certain class of update