International Association
for Cryptologic Research

It is shown that an improved version of a previously proposed iterative probabilistic algorithm, based on forward and backward probability recursions along a short keystream segment, is capable of reconstructing the RC4 internal states from a relatively small number of known initial permutation entries. Given a modulus $N$, it is argued that about $N/3$ and $N/10$ known entries are sufficient for success, for consecutive and specially generated entries, respectively. The complexities of the corresponding guess-and-determine attacks are analyzed and, e.g., for $N=256$, the data and time complexities are (conservatively) estimated to be around $D \approx 2^{41}$, $C \approx 2^{689}$ and $D \approx 2^{211}$, $C \approx 2^{262}$, for the two types of guessed entries considered, respectively.

A new, vectorial approach to fast correlation attacks on binary memoryless combiners is proposed. Instead of individual input sequences or their linear combinations, the new attack is targeting subsets of input sequences as a whole, thus exploiting the full correlation between the chosen subset and the output sequence. In particular, all the input sequences can be targeted simultaneously. The attack is based on a novel iterative probabilistic algorithm which is also applicable to general memoryless combiners over finite fields or finite rings. Experimental results obtained for randomly chosen binary combiners with balanced combining functions show that the vectorial approach yields a considerable improvement in comparison with the classical, scalar approach.