Analysis of Non-fortuitous Predictive States of the RC4 Keystream Generator

摘要

The RC4 stream cipher is the most widely used software based stream cipher. It is based on a secret internal state of N = 256 bytes and two pointers. This paper proposes an efficient algorithm to compute a special set of RC4 states named non-fortuitous predictive states. These special states increase the probability to guess part of the internal state in a known plaintext attack and present a cryptanalytic weakness of RC4. The problem of designing a practical algorithm to compute them has been open since it was posed by Mantin and Shamir in 2001. We also formally prove a slightly corrected version of the conjecture by Mantin and Shamir of 2001 that only a known elements along with the two pointers at any RC4 round cannot predict more than a outputs in the next N rounds.