Paper 2007/261

New Form of Permutation Bias and Secret Key Leakage in Keystream Bytes of RC4

Subhamoy Maitra and Goutam Paul

Abstract

Consider the permutation $S$ in RC4. Roos pointed out in 1995 that after the Key Scheduling Algorithm (KSA) of RC4, each of the initial bytes of the permutation, i.e., $S[y]$ for small values of $y$, is biased towards some linear combination of the secret key bytes. In this paper, for the first time we show that the bias can be observed in $S[S[y]]$ too. Based on this new form of permutation bias after the KSA and other related results, a complete framework is presented to show that many keystream output bytes of RC4 are significantly biased towards several linear combinations of the secret key bytes. The results do not assume any condition on the secret key. We find new biases in the initial as well as in the 256-th and 257-th keystream output bytes. For the first time biases at such later stages are discovered without any knowledge of the secret key bytes. We also identify that these biases propagate further, once the information for the index $j$ is revealed.

Note: Theorem 6 is included as a new result and minor revisions have been made in the formula of Theorem 7.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. FSE 2008
Keywords
BiasCryptanalysisKeystreamRC4Stream Cipher.
Contact author(s)
subho @ isical ac in
History
2009-01-09: last of 3 revisions
2007-07-03: received
See all versions
Short URL
https://ia.cr/2007/261
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/261,
      author = {Subhamoy Maitra and Goutam Paul},
      title = {New Form of Permutation Bias and Secret Key Leakage in Keystream Bytes of RC4},
      howpublished = {Cryptology ePrint Archive, Paper 2007/261},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/261}},
      url = {https://eprint.iacr.org/2007/261}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.