An Improved Internal-state Reconstruction Method of a Stream Cipher RC4

Y. Shiraishi, T. Ohigashi, and M. Morii (Japan)


Security Analysis Methodology, Stream Cipher, RC4,InternalState Reconstruction


Knudsen et al. proposed a method based on a tree search algorithm with a recursive process for reconstructing inter nal state of an RC4 stream cipher. However, the attack be comes infeasible for word size n > 5 because its time com plexity is too large to reconstruct an internal state. We as sessed efficiency of Knudsen et al.'s method for n = 8 and calculation time within 220 to reconstruct an internal state. The experimental result indicated that at least 112 entries in the internal state must be known for successful recon struction. This paper presents a more efficient method than Knudsen et al.'s method. We found some recovered cases using only 73 pre-known entries of 256 in initial-state table under the above condition.

Important Links:

Go Back