Cryptanalysis of Stream Ciphers from a New Aspect: How to Apply Key Collisions to Key Recovery Attack

In this paper, we propose two new attacks against stream cipher RC4 which can recover the secret key in different length with practical computational amount. However, we have to point out that the proposed attacks are performed under relatively strong related key models. The same as the usual related key models, the adversary can specify the key differentials without knowing the target key information. However, in our attacks, only the relation between two keystream outputs or the two final internal states are required for the attacker. In addition, we discover a statistical bias of RC4 which is the key point to one of the attacks. Besides the inappropriate usage during the WEP environment, RC4 is still considered to be secure with the proper setting, and we believe the result of this paper will add to the understanding of RC4 and how to use it correctly and safely.