Cryptography Reference
In-Depth Information
Chapter 3
Analysis of Key Scheduling
In this chapter, we present theoretical analysis of the Key Scheduling Al-
gorithm (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 ex-
plicit 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 shu
e-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.
In Section 3.2, we shift focus on non-randomness of permutation S. Under
reasonable assumptions, each permutation byte after the KSA is significantly
biased toward many values in the range Z
N
. This weakness was first noted
by Mantin [107] and later revisited in [122,135]. We present a proof of these
biases and demonstrate that permutation after the KSA can be distinguished
from random permutation without any assumption on the secret key. The
last part of Section 3.2 is devoted to the anomaly pairs, i.e., the (index,value)
pairs where the theoretical computations and the empirical data regarding the
biases differ significantly.
In RC4, an interesting phenomenon is that there exists a non-uniformity
in the expected number of times each value of the permutation is touched by
the indices i,j. The theoretical analysis of this fact first appeared in [101].
We present this in Section 3.3 of this chapter.
This chapter ends with a discussion on key collisions of RC4 [111].
3.1 Bias of Permutation toward Secret Key
In this section we analyze the KSA to prove different types of biases of the
permutation bytes toward combinations of secret key bytes. We begin with the
