Paper 2017/1072

Settling the mystery of $Z_r=r$ in RC4

Sabyasachi Dey and Santanu Sarkar

Abstract

In this paper, using probability transition matrix, at first we revisit the work of Mantin on finding the probability distribution of RC4 permutation after the completion of KSA. After that, we extend the same idea to analyse the probabilities during any iteration of Pseudo Random Generation Algorithm. Next, we study the bias $Z_r=r$ (where $Z_r$ is the $r$-th output keystream bit), which is one of the significant biases observed in RC4 output keystream. This bias has played an important role in the plaintext recovery attack proposed by Isobe et al. in FSE 2013. However, the accurate theoretical explanation of the bias of $Z_r=r$ is still a mystery. Though several attempts have been made to prove this bias, none of those provides accurate justification. Here, using the results found with the help of probability transition matrix we justify this bias of $Z_r=r$ accurately and settle this issue. The bias obtained from our proof matches perfectly with the experimental observations.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
CryptanalysisKSAPRGARC4BiasStream Cipher
Contact author(s)
sarkar santanu bir @ gmail com
sabya ndp @ gmail com
History
2017-11-10: received
Short URL
https://ia.cr/2017/1072
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1072,
      author = {Sabyasachi Dey and Santanu Sarkar},
      title = {Settling the mystery of $Z_r=r$ in RC4},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1072},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1072}},
      url = {https://eprint.iacr.org/2017/1072}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.