Paper 2020/512

Glimpses are Forever in RC4 amidst the Spectre of Biases

Chandratop Chakraborty, Pranab Chakraborty, and Subhamoy Maitra

Abstract

In this paper we exploit elementary combinatorial techniques to settle different cryptanalytic observations on RC4 that remained unproved for more than two decades. At the same time, we present new observations with theoretical proofs. We first prove the biases (non-randomness) presented by Fluhrer and McGrew (FSE 2000) two decades ago. It is surprising that though the biases have been published long back, and there are many applications of them in cryptanalysis till recent days as well, the proofs have never been presented. In this paper, we complete that task and also show that any such bias immediately provides a glimpse of hidden variables in RC4. Further, we take up the biases of two non-consecutive key-stream bytes skipping one byte in between. We show the incompleteness of such a result presented by SenGupta et al (JoC, 2013) and provide new observations and proofs in this direction relating the key-stream bytes and glimpses. Similarly, we streamline certain missed observation in the famous Glimpse theorem presented by Jenkins in 1996. Our results point out how biases of RC4 key-stream and the Glimpses of the RC4 hidden variables are related. It is evident from our results that the biases and glimpses are everywhere in RC4 and it needs further investigation as we provide very high magnitude of glimpses that were not known earlier. The new glimpses and biases that we identify in this paper may be exploited in improving practical attacks against the protocols that use RC4.

Note: Minor technical and editorial revisions

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
BiasesCryptanalysisGlimpsesNon-randomnessRC4Stream Cipher.
Contact author(s)
subho @ isical ac in
History
2020-05-10: revised
2020-05-05: received
See all versions
Short URL
https://ia.cr/2020/512
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/512,
      author = {Chandratop Chakraborty and Pranab Chakraborty and Subhamoy Maitra},
      title = {Glimpses are Forever in RC4 amidst the Spectre of Biases},
      howpublished = {Cryptology ePrint Archive, Paper 2020/512},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/512}},
      url = {https://eprint.iacr.org/2020/512}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.