Recovering state of modified RC4 key scheduling algorithm

Question

Consider this algorithm:

def ksa(k):
    L = length(k)
    j = 0
    for i from 0 to L: #[0..L-1] (non inclusive "to")
            j = (j + k[k[i] % L])%L
            swap(k[i], k[j])

k is an array of integers $0 \leq x < 256$. The questions is how to enumerate all possible arrays k resulting in an array with given prefix $P$. In other words if k'=ksa(k), and if $P=[1,2,3]$, then how to generate all k, so that $prefix(k',length(P))=P$? Enumeration would be best, but constructing just one such k is good too. Solution for a variant with for i from 0 to C where $C \leq L$ would be interesting too.

This is a variation of the key schedule for encryption algorithm RC4.

Answer 1

The algorithm you describe seems to have a class of special states (similar to the Finney states of RC4) consisting of the states such that $i = j$ and $k_x \bmod L = 1$, where $x := k_i \bmod L$.

If we are at a state that belongs to this class at the beginning of the loop, the effect of the loop will be simply to swap $k_i$ and $k_{i+1}$ and to increment both $i$ and $j$ by one. Thus, as long as we also have $x \notin \{k, k+1\}$, the state at the next iteration of the loop will also belong to this class of special states.

In particular, consider what happens if, before the algorithm, we have $k_0 = L-1$ and $k_{L-1} = 1$. Then the initial state $i = j = 0$ belongs to the special class described above, and this will continue to hold almost to the end of the algorithm. The second to last iteration, where $i = L-2$, does take us out of the class, leaving us with $i = j = x = k_x = L-1$, but this just causes the last two elements of the array $k$ to be swapped a second time on the last iteration, leaving us with $k_{L-2} = L-1$ and $k_{L-1} = 1$.

Meanwhile, all the other elements of the array, between the $L-1$ at the beginning and the $1$ at the end, just get shifted down by one position as the $L-1$ element bubbles up past them. Thus, from an initial array $$(L-1, a, b, c, \dotsc, y, z, 1) \tag{1}$$ we end up with the final state $$(a, b, c, \dotsc, y, z, L-1, 1) \tag{2}$$ regardless of the values of the unknown elements $a, b, c, \dotsc, y, z$. Conversely, to end up in any final state of the form given in $(2)$ above, it suffices to start with the corresponding initial state $(1)$.

(The same trick works also for loops terminating at some $i = C < L-1$, except that the initial $L-1$ element then ends up at $k_{C+1}$ rather than at $k_{L-2}$.)

---

In fact, I just wrote a little program to test this. Here's a sample run with $L = 10$, one line per iteration, starting with eight random values bracketed between $L-1 = 9$ and $1$:

k = (9, 144, 165, 42, 43, 56, 231, 72, 53, 1), i = 0, j = 0
k = (144, 9, 165, 42, 43, 56, 231, 72, 53, 1), i = 1, j = 1
k = (144, 165, 9, 42, 43, 56, 231, 72, 53, 1), i = 2, j = 2
k = (144, 165, 42, 9, 43, 56, 231, 72, 53, 1), i = 3, j = 3
k = (144, 165, 42, 43, 9, 56, 231, 72, 53, 1), i = 4, j = 4
k = (144, 165, 42, 43, 56, 9, 231, 72, 53, 1), i = 5, j = 5
k = (144, 165, 42, 43, 56, 231, 9, 72, 53, 1), i = 6, j = 6
k = (144, 165, 42, 43, 56, 231, 72, 9, 53, 1), i = 7, j = 7
k = (144, 165, 42, 43, 56, 231, 72, 53, 9, 1), i = 8, j = 8
k = (144, 165, 42, 43, 56, 231, 72, 53, 1, 9), i = 9, j = 9
k = (144, 165, 42, 43, 56, 231, 72, 53, 9, 1), j = 8, end of loop