Inverse RC4

[foxgrrl]

Given the keystream output from RC4 (ARC4), is there an inverse RC4 function which would give me either the key schedule or even the original key.

I have the plaintext, the cyphertext, the key stream, and the nonce which is mixed with an unknown key. I'm trying to recover that unknown key part.

Assume that the first N-bytes of the keystream were not discarded.

Comments

[robbat2.livejournal.com]

You'd be going from keystream to seed (nonce+key). The fact you have the plaintext and ciphertext doesn't help. If they aren't doing a plain XOR, that may be of interest as well.

Do you know the overall seed length, and more importantly how the key was combined with the nonce to produce the RC4 input seed?

128-bit WEP did 104 bits of key, IIRC in the high order, followed by 24 bits of IV in the lower order bits (so they were NOT mixed together, but were instead totally independent). I've seen other uses that take a 256-bit key XOR w/ a real 256-bit random input, and use that as the RC4 generator input.

In any case, I suggest looking at the WEP attacks, as I know they can recover the original key, and it's RC4 as well ;-).

[davidsarah.livejournal.com]

AFAIK, there are no feasible published attacks against RC4 if you only have one keystream with a given nonce.

The fact that the first N bytes are not dropped is only helpful if you have lots of keystreams using the same nonce (which was the case in WEP). See http://en.wikipedia.org/wiki/Fluhrer,_Mantin,_and_Shamir_attack

Are you trying to attack a specific protocol or implementation that uses RC4? You can always hope that it has been implemented or used incorrectly, although it's one of the easiest ciphers to implement. How is the nonce combined with the rest of the key, and what is the source of randomness for the key?