Comprehensive Analysis of Initial Keystream Biases of RC4

Takanori ISOBE  Toshihiro OHIGASHI  Yuhei WATANABE  Masakatu MORII  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E97-A   No.1   pp.139-151
Publication Date: 2014/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E97.A.139
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Symmetric Key Based Cryptography
Keyword: 
RC4,  stream cipher,  keystream biases,  plaintext recovery attack,  multiple key distinguisher,  key recovery attack,  broadcast setting,  

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




Summary: 
After the disclosure of the RC4 algorithm in 1994, a number of keystream biases of RC4 were reported, e.g., Mantin and Shamir showed that the second byte of the keystream is biased to 0, Sepehrdad et al. found that the l-th byte of the keystream is biased to -l, and Maitra et al. showed that 3rd to 255th bytes of the keystream are also biased to 0, where l is the keylength in byte. However, it is unknown that which bias is strongest in each byte of initial bytes. This paper comprehensively analyzes initial keystream biases of RC4. In particular, we introduce several new biases in the initial (1st to 257th) bytes of the RC4 keystream, which are substantially stronger than known biases. Combining the new biases with the known ones, a complete list of strongest single-byte biases in the first 257bytes of the RC4 keystream is constructed for the first time. Then, we show that our set of these biases are applicable to plaintext recovery attacks, key recovery attacks and distinguishing attacks.