Paper 2016/1001

Revisiting RC4 Key Collision: Faster Search Algorithm and New 22-byte Colliding Key Pairs

Amit Jana and Goutam Paul


If two different secret keys of a stream cipher yield the same internal state after the key scheduling algorithm (KSA) and hence generates the same sequence of keystream bits, they are called a colliding key pair. The number of possible internal states of RC4 stream cipher is very large (approximately $2^{1700}$), which makes finding key collision hard for practical key length (i.e., less than 30 bytes). Matsui [FSE 2009] for the first time reported a 24-byte colliding key pair and one 20-byte near-colliding key pair (i.e., for which the state arrays after the KSA differ in at most two positions) for RC4. Subsequently, Chen and Miyaji [ISC 2011] claimed to design a more efficient search algorithm using Matsui's collision pattern and reported a 22-byte colliding key pair which remains the only shortest known colliding key pair so far. In this paper, we show some limitations of both the above approaches and propose a faster collision search algorithm that overcomes these limitations. Using our algorithm, we are able to find three additional 22-byte colliding key pairs that are different from the one reported by Chen and Miyaji [ISC 2011]. We additionally give 12 new 20-byte near-colliding key pairs different from Matsui's [FSE 2009]. These results are significant, considering the argument by the experts [Biham and Dunkelman, 2007] that for shorter keys there might be no instances of collision at all.

Note: This work is an extension of the Master's thesis of the first author under the supervision of the second author.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Cryptography and Communications (2017)
Colliding PairKey CollisionNear Colliding PairRC4Related Key CryptanalysisStream Cipher.
Contact author(s)
goutam k paul @ gmail com
2017-08-18: last of 2 revisions
2016-10-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Amit Jana and Goutam Paul},
      title = {Revisiting RC4 Key Collision: Faster Search Algorithm and New 22-byte Colliding Key Pairs},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1001},
      year = {2016},
      doi = {10.1007/s12095-017-0231-z},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.