I'll try to control the value of state[0], ..., state[9] after the
key scheduling algorithm: call it S[0..9]. In particular, we want to
set things up so that a ciphertext byte depends upon only S[0..9] and
one key byte.
Note that the first output ciphertext byte from RC4 is
S[S[1] + S[S[1]]]
(and it swaps state[1] and state[state[1]]). I want to set S[] up so that
S[1] <= 9, i.e. S[1] + S[S[1]] is known.
Now note that knowledge of S[10] and K[0..9] can be used to derive K[10]
with high probability (by observation <A> above). Therefore let's set up
S[] so that
(S[1] + S[S[1]]) % 256 = 10,
which means that the first byte of ciphertext tells us S[10].
For example, suppose K[0] = 10, K[1] = 255. Then S[0] = 10 & S[1] = 0
(so S[1] + S[S[1]] = 10) with probability 1/e^2 = 14%. Also note that
S[10] = known-state[K[10] + known-value]
with probability about 1/e = 37%, so knowledge of S[0..10] often gives
away the value of K[10]. Thus we can easily pick K[0..9] so that S[]
has the desired form -- then K[10] can be found once out of e^3 = 20
trials, and K[11..15] can be found with a brute force search over the
remaining 2^32 possibilities, for a total complexity of 2^36 << 2^40.
This can be improved a bit to reveal more K[] values. Let
T[n] = S[1] + S[2] + ... + S[n].
Suppose we ensure that
T[1] < 10, S[1] + S[T[1]] = 10
T[2] < 10, S[2] + S[T[2]] = 11
T[3] < 10, S[3] + S[T[3]] = 12;
then in this case, the first 3 ciphertext bytes will reveal K[10..12]
with high probability.
We can get the first 3 bytes to satisfy the criterion. Suppose
K[0..6] = {10,-1,-7,2,0,-13,3};
then we will have
S[0..6] = {10,0,5,1,x,6,11}
with probability 1/e^6 = 2.5%. If that holds, then the first 3 ciphertext
bytes will reveal K[10..12] with probability ~ 1/e^3. So 1/e^9 = .01% of
the time we can find the rest of the key with a brute force search over
2^16 possibilities, for a total complexity of 2^16 e^9 = 2^29 << 2^36.
(This doesn't take into account the fact that often the other 99.99% of
the time may reveal partial information about K[10..12].)
I hope I didn't make any arithmetic mistakes in there. Anyhow, this is
of very limited practical interest, but maybe someone'll be able to expand
it to be more interesting.
)
wnewrev.exe. After Windows 98 