[Resource Topic] 2017/1072: Settling the mystery of $Z_r=r$ in RC4

Welcome to the resource topic for 2017/1072

Settling the mystery of Z_r=r in RC4

Authors: Sabyasachi Dey, Santanu Sarkar


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.

ePrint: https://eprint.iacr.org/2017/1072

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .