Theoretical Understanding of Some Conditional and Joint Biases in RC4 Stream Cipher

Sonu JHA  Subhadeep BANIK  Takanori ISOBE  Toshihiro OHIGASHI  Santanu SARKAR  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A   No.11   pp.1869-1879
Publication Date: 2018/11/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E101.A.1869
Type of Manuscript: PAPER
Category: Cryptography and Information Security
RC4,  triple-byte biases,  conditional biases,  distinguishing attacks,  3-predictive-3-states,  

Full Text: PDF(1.3MB)
>>Buy this Article

In this paper we present proofs for the new biases in RC4 which were experimentally found and listed out (without theoretical justifications and proofs) in a paper by Vanhoef et al. in USENIX 2015. Their purpose was to exploit the vulnerabilities of RC4 in TLS using the set of new biases found by them. We also show (and prove) new results on couple of very strong biases residing in the joint distribution of three consecutive output bytes of the RC4 stream cipher. These biases provides completely new distinguisher for RC4 taking roughly O(224) samples to distinguish streams of RC4 from a uniformly random stream. We also provide a list of new results with proofs relating to some conditional biases in the keystreams of the RC4 stream cipher.