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 21700), 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},
      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.