On the Entropy of Arcfour Keys

Arcfour is a stream cipher that produces a byte keystream B = {b(i)}**infinity (i=0), where a key K is used to select the initial state S(0), and the b(i) are produced by the state transition delta(S(i)) = S(i+1). Let the byte length of K be |K|, and let S(0)(K) be the initial state produced by K. Two keys K(1), K(2) are considered equivalent if S(0)(K(1))=S(0)(K(2)), and further K(2) is weak if |K(1)| < |K(2)|. We show that there is a class of weak keys based on the notion of string periodicity which contains 256 weak 40-bit keys and 2**64 weak 128-bit keys. We
exhibit 128-bit keys whose entropy is no more than a byte.

We also present an algorithm for constructing the initial contents of the Arcfour state machine based on observing B(256) = {b(i)}(i=0)**255. The method is significantly faster than exhaustive search for initial the state S(0), and shows that no additional security against brute-force attacks is expected to be achieved by selecting keys K for which |K| >/= 57. Also it shows that if Arcfour is scaled down to operate on 4-bit values with 64-bit keys, say suitable for smart card environments, the state contents can be recovered in approximately 10**7 operations.