Santanu Sarkar

RC4 has attracted many cryptologists due to its simple structure. In [9], Paterson, Poettering and Schuldt reported the results of a large scale computation of RC4 biases. Among the biases reported by them, we try to theoretically analyze a few which show very interesting visual patterns. We first study the bias which relates the key stream byte, where k is the first byte of the secret key. We then present a generalization of the Roos bias. In 1995, Roos observed the bias of initial bytes S of the permutation after KSA towards f. Here we study the probability of S. Our generalization provides a complete correlation between z i. We also analyze the key-keystream relation z i = f i - 1 which was studied by Maitra and Paul [6] in FSE 2008. We provide more accurate formulas for the probability of both z i = i - f i {z-{i}=i-f-{i}} and z i = f i - 1 {z-{i}=f-{i-1}} for different i's than the existing works.

In this paper, using a matrix, at first we revisit the work of Mantin on finding the probability distribution of the RC4 permutation after the completion of the KSA. After that, we extend the same idea to analyse the probabilities during any iteration of the Pseudo Random Generation Algorithm. Next, we study the bias of Zr = r (where Zr is the r-th output keystream byte), which is one of the significant biases observed in the 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 Zr = r is still a mystery. Though several attempts have been made to prove this bias, none of those provides an accurate justification. Here, using the results found with the help of the probability transition matrix we justify this bias of Zr = r accurately and settle this issue. The bias obtained from our proof matches the experimental observations perfectly.

RC4 is one of the most popular stream cipher with wide industrial applications, it has received serious attention in cryptology literature in the last 2 decades. In 1995, Roos pointed out that the elements SN[ y] of the permutation SN after the key scheduling algorithm for the first few values of y are biased to certain combinations of secret key bytes. These correlations were theoretically studied by Paul and Maitra (SAC, 2007). The formula for the correlation probabilities provided by them gives a wrong impression that the probabilities decrease as the value of y becomes larger, which is not true. In this paper, we point out some gaps in their analysis and present a detailed analysis of Roos bias. We provide a more accurate formula for the correlation probabilities. We further study nested Roos type biases and present comparison results. These types of biases are used to reconstruct key from the permutation SN for better success probability.

In this paper we present proofs for the new biases in RC4 which were experimentally found and listed out (without theoretical justifications and proofs) in a paper by Vanhoef et al. in USENIX 2015. Their purpose was to exploit the vulnerabilities of RC4 in TLS using the set of new biases found by them. We also show (and prove) new results on couple of very strong biases residing in the joint distribution of three consecutive output bytes of the RC4 stream cipher. These biases provides completely new distinguisher for RC4 taking roughly O(224) samples to distinguish streams of RC4 from a uniformly random stream. We also provide a list of newresults with proofs relating to some conditional biases in the keystreams of the RC4 stream cipher.