Paper 2013/502

Proving TLS-attack related open biases of RC4

Santanu Sarkar, Sourav Sen Gupta, Goutam Paul, and Subhamoy Maitra

Abstract

After a series of works on RC4 cryptanalysis in last few years (published in flagship cryptology conferences and journals), the most significant (and also very recent) attack on the cipher has been the discovery of vulnerabilities in the SSL/TLS protocol, by AlFardan, Bernstein, Paterson, Poettering and Schuldt. They ran extensive computations to identify significant short-term single-byte keystream biases of RC4, and utilized that knowledge in the attack. The biases identified by AlFardan et al. consist of earlier known biases of RC4, as well as some newly discovered ones. In this paper, we attempt at proving the new, unproved or partially proved biases amongst the above-mentioned ones. The theoretical proofs of these biases not only assert a scientific justification, but also discover intricate patterns and operations of the cipher associated with these biases. For example, while attempting the proof of a bias of the first output byte towards 129, we observe that this bias occurs prominently only for certain lengths of the secret key of RC4. In addition, our findings reveal that this bias may be related to the old and unsolved problem of ``anomalies'' in the distribution of the state array after the Key Scheduling Algorithm. In this connection, we prove the anomaly in $S_0[128] = 127$, a problem open for more than a decade. Other than proving the new biases, we also complete the proof for the extended keylength dependent biases in RC4, a problem attempted and partially solved by Isobe, Ohigashi, Watanabe and Morii in FSE 2013. Our new proofs and observations in this paper, along with the connection to the older results, provide a comprehensive view on the state-of-the-art literature in RC4 cryptanalysis.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Stream cipherRC4BiasesShort-termKeylength dependentAnomaly
Contact author(s)
sg sourav @ gmail com
History
2013-08-15: received
Short URL
https://ia.cr/2013/502
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/502,
      author = {Santanu Sarkar and Sourav Sen Gupta and Goutam Paul and Subhamoy Maitra},
      title = {Proving TLS-attack related open biases of RC4},
      howpublished = {Cryptology ePrint Archive, Paper 2013/502},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/502}},
      url = {https://eprint.iacr.org/2013/502}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.