ABSTRACT
In this chapter, we present theoretical analysis of the Key Scheduling Algorithm (KSA) of RC4. We start with an exposition on several biases of permutation bytes toward secret key bytes in Section 3.1. In 1995, Roos [146] observed that the initial permutation bytes, obtained just after the KSA, are biased to some combinations of the secret key bytes. After presenting an explicit formula for the probabilities with which the permutation bytes at any stage of the KSA are biased to the secret key, we analyze a generalization of the RC4 KSA corresponding to a certain class of update functions. This reveals an inherent weakness of the shuffle-exchange kind of key scheduling. Interestingly, the nested permutation entries, such as S[S[y]], S[S[S[y]]], and so on, are also biased to the secret key for the initial values of y. We end the first section with a discussion on this issue.
