# RC4 : Keystream reconstruction?

First up: it's a step in some challenge found on the Internet, where we get an application and a file. The application must be feed with that file and a password (the password is the flag for the challenge).

So, after reversing the application, I found that the algorithm used is RC4 with a small change in the "S" array, which was not initialized to the identity but initialized to $S[i]= 0xFF -i$ .

The information I get from the challenge is that the file once decrypted has the INTEL HEX FORMAT which has a quiet regular format (like the : at each line).

At this point, I get some information about the keystream (i.e a partial keystream). My question is there some relation between the element of the keystream, and is it possible to reconstruct the total keystream from my partial keystream?

All what I found on the RC4 was for attacking WEP, based on the fact that it use the same (IV+key) to encrypt multiple packets, and I don't think it's possible to use this in my case.

-
What challenge is this from? –  Ben Mar 30 '12 at 16:25
I don't think it's good to give here the link of the challenge because it was released on 16 of this month, So I will send it to you via PM mine is Kiyohime.Shoji[a]mail.com if you want. –  Kiyohime Shoji Mar 30 '12 at 18:54

## 1 Answer

If what the program does is "take your password, use that as-is as the key to a (modified) RC4 encryption algorithm, and use that keystream to decrypt the entire file", well, there is no obvious weakness to take advantage of. Partial information doesn't help you much (for that matter, they could have given you the entire decrypted file, and it wouldn't help you to recover the key -- RC4 is pretty good at hiding that information). As for the S[i] = 0xFF - i modification, well, there's no obvious weakness that causes. At worse, that would change how certain related key attacks would work; since related key attacks do not appear to be relevant here, that is unimportant.

So, you can obviously do brute-force on the password, but unless the password is only a couple of characters long (or they give more clues about it), that's not likely to yield a result.

Hence, the obvious question is "is that a true representation of the challenge"? Or, do they (say) reset the RC4 algorithm periodically (rerunning the Key Setup Algorithm from the original key)? Do they stir in something when they reset the algorithm?

BTW: as for WEP, they don't use the same IV+Key to encrypt multiple packets. Instead, they use different IVs (and the same key), and just concatinate they two when forming the key they give to RC4. Because the RC4 Key Setup Algorithm doesn't do a great job of hiding information and so leaves some correlations between the original key and the initial parts of the key stream. These correlations aren't enough to take advantage of if you're given one key stream (or even a few hundred), but given enough, it allows us to deduce the original key.

-
Yes your are alright for what the program does. I will try the brute-force solution, but i don't think this will work (no information about the password). For your question about the reset of RC4 algorithm, no they use only once the original key with the KSA and after that they load byte by byte the crypted file and do a XOR with the output of the PRGA. The main purpose of the challenge is to test the reverse/network skill and not crypto (at the first step we get just a network dump file), now you confirmed my fear that even with the entire decrypted file i can't get the password. Thank you. –  Kiyohime Shoji Mar 30 '12 at 15:35