[Cryptography] RC4 again (actual security, scalability and other discussion)

[Jerry Leichter]

On Mar 9, 2014, at 6:26 PM, Watson Ladd <watsonbladd at gmail.com> wrote:
> Well, here is the paper about RC4:
> http://www.isg.rhul.ac.uk/tls/RC4biases.pdf.
Thanks for the pointer.

The paper references two different kinds of biases in RC4.  The first is single-byte biases after key setup.  The second is double-byte biases in the "steady state", long after key setup.

The first of these doesn't really surprise me.  From the first time I saw RC4 described, the key setup bothered me.  The basic algorithm assumed implicitly that the permutation table was random.  But as the algorithm is described, it requires both that the result of running the stream generation process randomize the table, *and* that the initial key setup do so as well.  Running the key generation process for a while during key setup eliminates the second assumption for very little cost.  I don't see this as "using RC4 in a secure way"; I see it as a change in the key setup procedure, produce a new RC4' algorithm that avoids the single-byte biases.

The double-byte biases, on the other hand, are killers.  They're present in the long-term state of the algorithm, and while small, are demonstrably sufficient to actually break encrypted text with a reasonable amount of input.  This isn't a matter of how RC4 is used; it's a fundamental weakness.  It's interesting that the biases were found in 1978, but apparently no one until now tried to apply the - fairly straightforward - statistical attacks needed.  It's long been assumed that a modern cipher has to be secure against a chosen-plaintext attack.  The difficulty here was in setting up the chosen plaintext inside of a browser session; but the whole reason we assume we need chosen-plaintext security is that it's been proven repeatedly that a determined adversary can always, somehow, manage to pull it off.

That's convinced me personally.  RIP RC4.
                                                       -- Jerry