Analysis of Keystream Generation - RC4: Stream Cipher and Its Variants - page 109

5.1 Finney Cycles
Shortly after the RC4 algorithm was known publicly, Finney [50] discov-
ered an interesting set of states linked by a set of short cycles.

Theorem 5.1.1. Suppose j r = i r + 1 and S r [j r ] = 1 hold in some round r

of RC4 PRGA. Then
(1) the same relations continue to hold in all subsequent rounds,
(2) a cycle of length N(N −1) is formed in the state-space and
(3) the output bytes z r+(N−1) , z r+2(N−1) ,..., z r+N(N−1) are a shift of S r .
Proof: Suppose that after round r of the RC4 PRGA, j r = i r + 1 and

S r [j r ] = 1. In the next round, i r+1 = i r

+ 1 and

j r+1 = j r + S r [i r+1 ]

= i r

+ 1 + 1

= i r

+ 2.

Now, the swap yields S r+1 [i r + 2] = 1 and S r+1 [i r + 1] = S r [i r + 2]. Thus,
the state at round r + 1 has the same relation among (S G ,i G ,j G ) as that
at round r. The same logic, when applied to round r + 1, yields the same
relations in round r + 2 and so on. This proves (1).
In each subsequent round, entries S G [y + 1] are moved back to S G [y] and
the value “1” moves up. After N rounds, the “1” returns to its original
position and the rest of the entries shift one position backwards. After N −1
such sets of N rounds, i.e., at round r + N(N −1), all the entries will return
to their original positions as in round r. Thus, a cycle of length N(N −1) is
formed in the state-space. This proves (2).
For a fixed value of i G , the entry S G [i G ] repeats it's value every N−1 steps
and the value of S G [j G ] remains 1 always. Thus the index S G [i G ] + S G [j G ]
of the output byte is repeated every N −1 steps. As proved in (2) above, the
value at this entry is rotated by one position to make room for the next value
in the cyclic order. Hence the N keystream output bytes, each separated by
N − 1 rounds from the previous, are nothing but a shift of the permutation.
This proves (3).
The cycle thus formed in the state space is called a Finney cycle. Since each
state in this cycle has the same relations (the preconditions of Lemma 5.1.1)
and the PRGA round is reversible (see Section 4.1), it is not possible to move
from a state not in this form to one that is. Such a state is called a Finney
state. Fortunately, the initialization i 0 = j 0 = 0 in RC4 PRGA prevents the
condition for a Finney cycle to occur in normal RC4 operation.
As an example, consider the permutation during the PRGA as shown in
Table 5.1.
If i G = 0 and j G = 1, this is a Finney state, since S G [1] = 1. Table 5.2