RC4 : Keystream reconstruction?

Question

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.

Answer 1

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.