Novel strategies for searching RC4 key collisions

The property that the stream cipher RC4 can generate the same keystream outputs under two different secret keys has been discovered recently. The principle of how the two different keys can achieve a collision has been studied in the previous researches by investigating the key scheduling algorithm of RC4. However, how to find those colliding key pairs is a different story, which has largely remained unexploited. Previous researches have demonstrated that finding colliding key pairs becomes more difficult as the key size decreases, and also finding key collisions can be related to key recovery attacks and hash collisions. In this paper, we propose novel searching techniques which can be used to find short colliding key pairs that belong to two different kind of colliding key patterns efficiently. The colliding key pairs we find in both patterns are by far the shortest ones ever found.