Miyaji Laboratory

RC4 is a one of the most popular stream cipher proposed by Ron Rivest in 1987, which is widely used in a large number of applications because of its simplicity and security. Many cryptanalysis against RC4 have been proposed so far, however, it is said to be secure under proper uses. RC4 consists two algorithms, KSA (key scheduling algorithm) and PRGA (pseudo random number generation algorithm). KSA is given a secret key $K$ with length $l$ bytes and generates the initial permutation $S_0$, which is passed to PRGA. Updating its internal states, PRGA generates a pseudo-random sequence as a keystream. The existence of the near-equivalent key pair, which generates almost same initial permutation $S_0$ has been shown in 2009. In other words, there are the key pairs for which the condition $K \ne K'$ and that the difference between $S_0 = KSA\left( K \right)$ and $S'_0 = KSA\left( K' \right)$ is exactly 2 bytes holds. Such differences in the initial round are called initial difference, and we denote these difference $\text{Diff}_0 = \left\{ \text{df}_0\left[ 1 \right], \text{df}_0\left[ 2 \right] \right\}$. In the analysis proposed previously, attacker can observe the output stream of RC4 PRGA and he guesses the internal states with using these sequence. Some specific internal states are defined as $\text{Event}$, which is related the index $i$ and initial differences, and as $\Delta\text{State}$, which is related the index $j$ and the positions of the differences. By computing the probability of the output difference from the special states, one can estimate a part of the internal states with output. In this previous study, only the position of first difference $\text{df}_0\left[ 1 \right]$ of initial differences, so, we extend this results to analyze in more detail. We conclude that by using two permutations $S$ and $S'$ with the initial differences $\text{Diff}_0$, the previous results can be extended to the case of $\text{df}_0\left[ 1 \right] < r < \text{df}_0\left[ 2 \right]$, assuming the $\text{Event}\left[ 3 \right]$ has occurred in round $r = \text{df}_0\left[ 1 \right]$. In addition, we shown that the internal states will be transit to some states according to the value of $j_r$ at round $r = \text{df}_0\left[ 2 \right]$, and exploiting it, we can guess the value of $j_r$.