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

Jenkins' Correlation or Glimpse Theorem [78,108] discussed in Section 5.2. It
states that during any PRGA round, P(S G [j G ] = i G −z) = P(S G [i G ] = j G −
z) ≈ N . As we saw in the proof of Theorem 5.2.1, given i G = S[i G ] + S[j G ],
the event S G [j G ] = i G −z holds with probability 1. To obtain Glimpse-like
such biases in PRGA + , one needs to have more assumptions of the above
form. Thus, Glimpse-like biases of PRGA + , if they at all exist, would be
much weaker.

Resisting distinguishing attacks

2
N

In [107], it was proved that P(z 2 = 0) = instead of the uniformly ran-

1

dom case of

N . We discuss this distinguishing attack in detail in Section 6.2.2.
As we saw in the proof of Theorem 6.2.3, the bias originates from the fact that
when S N [2] = 0 and S N [1] = 2 after the KSA, the second keystream output
byte z 2 takes the value 0 with probability 1. Based on this, a ciphertext-only
attack can be mounted in broadcast mode. This kind of situation does not
arise in the new design. When 100 million secret keys of length 16 bytes are
generated and 1024 rounds of PRGA + are executed for each such key, the em-
pirical evidence indicates that P(z r = v) =

1

N , 1 ≤ r ≤ 1024,0 ≤v ≤N −1.
In the work [139], it was reported that P(z 1 = z 2 ) = − N 2 , which leads

to a distinguishing attack. Even after extensive experimentation, such bias in
the keystream output bytes of PRGA + is not observed. The same experiment
described above also supports that P(z r = z r+1 ) is uniformly distributed for
1 ≤r ≤ 1023.
In [109], it has been shown that getting strings of pattern ABTAB (A,B
are bytes and T is a string of bytes of small length ∆, say ∆ ≤ 16) are more
frequent in RC4 keystream than in random stream. In a uniformly random
keystream, the probability of getting such pattern irrespective of the length of
T is

1
N

N 2 (1+ e −4−8∆

1
N 2 , whereas for RC4, the probability of such an event is

1

N
N

) >

1
N 2 . We have already presented this distinguishing attack in Section 6.3.1.
This result is based on the fact that the permutation entries in locations that
affect the swaps and the selection of keystream output bytes in both pairs of
rounds that are ∆-round apart, remain unchanged during the intermediate
rounds with high probability. The permutation in PRGA + evolves in the
same way as RC4 PRGA, but the keystream output generation in PRGA +
is different. This does not allow the pattern AB to propagate down the
keystream with significant probability even for smaller interval lengths (∆).
Thus, the source of RC4's ABTAB bias is present in the permutation of RC4 +
also, but it is not revealed in the keystream. The simulation on PRGA + also
confirms that the keystream is free from such biases.

9.4.3 Performance Evaluation
The performance of the new design has been tested using the eSTREAM
testing framework [26]. The C-implementation of the testing framework was