Cryptology ePrint Archive: Report 2020/512

Glimpses are Forever in RC4 amidst the Spectre of Biases

Chandratop Chakraborty and 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.

Category / Keywords: secret-key cryptography / Biases, Cryptanalysis, Glimpses, Non-randomness, RC4, Stream Cipher.

Date: received 1 May 2020, last revised 10 May 2020

Contact author: subho at isical ac in

Available format(s): PDF | BibTeX Citation

Note: Minor technical and editorial revisions

Version: 20200510:201205 (All versions of this report)

Short URL: ia.cr/2020/512


[ Cryptology ePrint archive ]