Paper 2016/1001

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

Amit Jana and Goutam Paul

Abstract

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Cryptography and Communications (2017)
DOI
10.1007/s12095-017-0231-z
Keywords
Colliding PairKey CollisionNear Colliding PairRC4Related Key CryptanalysisStream Cipher.
Contact author(s)
goutam k paul @ gmail com
History
2017-08-18: last of 2 revisions
2016-10-20: received
See all versions
Short URL
https://ia.cr/2016/1001
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1001,
      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{https://eprint.iacr.org/2016/1001}},
      url = {https://eprint.iacr.org/2016/1001}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.