Some New Weaknesses in the RC4 Stream Cipher

摘要

In FSE 2011, Maitra and Paul observed that there exists negative bias in the first byte of the RC4 keystream towards 0. In this paper, we give our theoretical proof of this bias. This bias immediately provide distinguisher for RC4, and ciphertext only attack on broadcast RC4. Additionally, we discover some new weaknesses of the keystream bytes even after the first N rounds of the PRGA, where N is the size of the RC4 permutation, generally, N = 256. The weaknesses in turn provide us with certain state information from the keystream bytes no matter how many initial bytes are thrown away.