Glimpses are Forever in RC4 amidst the Spectre of Biases

Chandratop Chakraborty; Pranab Chakraborty; Subhamoy Maitra

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: Biases Cryptanalysis Glimpses Non-randomness RC4 Stream 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: 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},
      url = {https://eprint.iacr.org/2020/512}
}