Re: [TLS] RC4 Considered Harmful (Was: RC4 deprecation path)

[[e-mail] (Martin Rex)]

Jacob Appelbaum wrote:
> On 4/19/14, Alyssa Rowan <[e-mail]> wrote:
>>
>> RC4 is either on the brink of being cracked, given the serious known
>> weaknesses pointed out in Section 1 of the draft, or it is already
>> over the brink (if that's the 'cryptanalytic breakthrough' GCHQ were
>> talking about that they got from NSA, and that seems plausible to me,
>> and to several others, including Schneier).
> 
> I think that RC4 is completely broken for certain adversaries. It
> should be totally abandoned.

While I have heard claims that RC4 would be "completely broken", I am
still not aware of the slightest indication why or how this break
would be performed.

RC4 is a stream cipher, and operates by xoring plaintext with
a pseudo-random keystream.  In order to "completely break" RC4,
it would be necessary to precompute future RC4 outputs from
some amount of *known* RC4 keystream, essentially re-creating
the internal state of the RC4 algorithm.

HTTP is a protocol with often quite a lot of known plaintext,
so recovering *some* amount of RC4 keystream will often be possible
with a low probability of error.  So that leaves us with the questions

  - are parts of the RC4 algorithm invertible?
  - is it possible to recreate the RC4 internal state from a certain
    amount of keystream octets.
  - how many keystream octets would be necessary
  - will those known keystream octets have to be from specific locations
    (or consecutive)
  - how big is the workfactor?


I'm _not_ saying that this hasn't happened.  But without the slightest
indication about a _real_ problem with the RC4 algorithm internals,
I refuse to be terrorized.


-Martin

PS: the most attractive target for breaking is the key exchange algorithm,
because that would make the traffic protection keys (MAC and encrypt)
available independent of the crypto an mac algorithms and their strength.
Considering that NSA has been pushing ECDSA+ECDHE for quite a while
(Suite B with NIST curves), I'm more worried about EC weaknesses than
RC4 bias or chained CBC-IVs.

ECDHE with Curve25519 and single-use(!!) DHE keypairs looks OK, but
that might not interoperable with a large fraction of the installed
base for another decade.