Miyaji Laboratory

RC4 is the stream cipher proposed by Rivest in 1987, which is widely used in a number of commercial products because of its simpleness together with substantial security. RC4 exploits shuffle-exchange paradigm, which uses a permutation $S = (S[0], \cdots, S[N])$. Many attacks have been reported so far. Few researches, however, has focused on correlations in PRGA between outputs of two permutations with some differences nevertheless such a correlation is related with an inherent weakness of shuffle-exchange-type Pseudo-Random Generation (PRGA).
In this paper, we investigate how the structure mixes the permutation $S$ by observing correlation between two permutations $S$ and $S'$ with some differences in the initial round. We show that correlations between two permutations $S$ and $S'$ remains until $i$ reaches the first index of nonzero bit differences and that $i$ can even skip over the nonzero bit differences with non negligible probability. In the case of $N=256$, there exist two permutations that output the same keystream from the 1st to the 255-th round with the probability of 0.9984436 and that $i$ can even skip over all nonzero bit differences until the $255$-th round with probability of 0.6399549. This means that the same correlations between permutations will be observed after the $255$-th round. This reveals an inherent weakness of shuffle-exchange kind of Pseudo-Random Generation (PRGA).