Huge problem with RC4?

[MTGAP]

Preface: I know that RC4 is no longer considered secure. But I found the biggest break ever. Please tell me why I am wrong.

From Wikipedia: "In the event that part or all of its state has been revealed (or guessed correctly), it should be impossible to reconstruct the stream of random numbers prior to the revelation."

However, this is clearly not the case with RC4. Here is the number generation algorithm (in C, but it works pretty much the same way in any language). i and j are the iterators and S is the 256-byte array.

i = (i + 1) % 256;
j = (j + S[i]) % 256;
swap(S[i], S[j]);

return S[(S[i] + S[j]) % 256];

Given the values of i and j, we can easily determine the previous value of i by subtracting one. And we can easily find the value of j by subtracting S[i]. So it is trivial to "reconstruct the stream of random numbers prior to the revalation."

P.S. What are some secure and relatively simple CSPRNGs? All I've found are the eStream ciphers, but there's not many very good resources on them and some of them are weird.
_________________
This statement is false.

[Antrax]

Good stream ciphers are a bit tricky. RC4 is still very commonly used despite its glaring weaknesses. Either RC5 or RC6 are improvements over it (the other is a block cipher, I never remember which is which). Eli Biham has his own stream cipher, which is probably safe, called Py. Adi Shamir once showed a pretty impressive cipher, but I have no clue how he named it and a quick google doesn't reveal it, so I guess it was flawed.
What is also often used is a good block cipher. To encrypt the stream you encode the block number under some (static) key, and XOR with the plaintext. Given standard assumptions, this "stream" cipher is as strong as the block cipher. The price is computations, which is also why RC4 is still so popular.

As for your first question, I'm not very knowledgeable about stream ciphers, but it seems the permutation S is also a part of the state. In fact, that's the "key". The other problem is that even given an S at some point in time, S is updated with every cycle, so it's not necessarily true that you can compute S[i] in time t-1, even given S and i in time t.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[MTGAP]

[Antrax]

No, I'm saying that in time t+1, what used to be S[i] in time t (that you want to calculate) is now S[j], and j is what you're trying to find out.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[raekuul]

[MTGAP]

[raekuul]

[worm]

[Dented Ford]

[worm]

just don't go into any wormholes looking for the alternate universe where you're a multi-millionaire. I really wish they'd change the name already.

Btw, if you could successfully get the cat in the box, it's not simultaneously dead and alive until an observer opens the box. The cat is the only observer necessary.

[raekuul]

We really should get back to talking about encryption/decryption. The Schroedinger's Cat thing was supposed to be a throwaway joke.

[MTGAP]

[Antrax]

It should be pretty easy to get an implemented RC4 cipher, so you'll know it's bug-free.
It's not impossible under some ill-chosen key you'll get stuck in a loop shorter than the maximum possible length (within the permutation) and then you'll get zero occurrences of some numbers. If you're REALLY interested, I can call up someone I've known back in college, he's doing a PhD under Biham and I think he dealt a lot with RC4.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[MTGAP]

[Antrax]

I think you can still late-register to winter semester at the Technion, then.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[MTGAP]