Paper 2007/305

On Non-Randomness of the Permutation after RC4 Key Scheduling

Goutam Paul, Subhamoy Maitra, and Rohit Srivastava

Abstract

Here we study a weakness of the RC4 Key Scheduling Algorithm (KSA) that has already been noted by Mantin and Mironov. Consider the RC4 permutation $S$ of $N$ (usually 256) bytes and denote it by $S_N$ after the KSA. Under reasonable assumptions we present a simple proof that each permutation byte after the KSA is significantly biased (either positive or negative) towards many values in the range $0, \ldots, N-1$. These biases are independent of the secret key and thus present an evidence that the permutation after the KSA can be distinguished from random permutation without any assumption on the secret key. We also present a detailed empirical study over Mantin's work when the theoretical formulae vary significantly from experimental results due to repetition of short keys in RC4. Further, it is explained how these results can be used to identify new distinguishers for RC4 keystream.

Note: Substantial revision. The earlier title "Key Independent Bias in the Permutation after RC4 Key Scheduling" has been modified.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Accepted for presentation in AAECC 17
Keywords
BiasCryptographyCryptanalysisKey Scheduling AlgorithmRC4Stream Cipher.
Contact author(s)
subho @ isical ac in
History
2007-09-27: revised
2007-08-07: received
See all versions
Short URL
https://ia.cr/2007/305
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/305,
      author = {Goutam Paul and Subhamoy Maitra and Rohit Srivastava},
      title = {On Non-Randomness of the Permutation after RC4 Key Scheduling},
      howpublished = {Cryptology ePrint Archive, Paper 2007/305},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/305}},
      url = {https://eprint.iacr.org/2007/305}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.