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

[Watson Ladd <[e-mail]>]

On Wed, Apr 23, 2014 at 8:07 AM, Martin Rex <[e-mail]> wrote:
> 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.

Yes, that would be terribly bad of a break. We don't have one like
that now. 5 years from now I would not be surprised. We need to start
moving now to be ready for the inevitable. I would prefer not to have
my banking secrets spread across the Internet before we decide we have
a problem.

However, even before you predict keystream from a handful of bytes you
can do the following:
-Use multiple connections sharing similar data together with hidden
markov models to recover text
-Use byte biases to determine what kind of information is flowing into
and out of a server: yes we can tell if you have binaries or text and
serve them up over RC4.
-Remember wepcrack? RC4 leaks key information

The RC4 state update is weak: it always changes an even permutation to
an odd one. There are probably other rep theoretic issues: I've not
thought very hard about it.

All of this is possible today. It won't stop being possible, and our
understanding of the weaknesses in RC4 will only grow. Already, users
assumptions of the security they have is not met by RC4.

Given uptake times, we need to start pushing for a fix now if we want
it ready in 5 years. Supposedly, algorithm agility was supposed to
work for this eventuality: it should be relatively trivial to change
configurations to use block ciphers if you don't care about BEAST and
Lucky 13. If you do, upgrade to TLS 1.2. We have a fix: it needs to be
deployed, and people need to know they have to.

>
>
> -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.

You shouldn't be. EC has been around since 1985 with no real
scratches. Do you know something we don't? Show me a discrete log on
P256 (with all the usual points about how to do it so I know you
didn't cheat) and I'll get worried. Show me a new weak class of curves
(prime fields only) and I'll be interested.

>
> 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.

Single-use only because implementors don't take elementary precautions
against side channels. The Curve25519 impl. has no side-channels.
The security difference between Curve25519 and P256 is entirely a
result of poor implementations. The speed difference is a result of
careful choices.

There is no known attack against properly implemented Suite B
protocols known in the open literature. Nor is there likely to be one
anytime soon: extensive analysis over the past decades has found
nothing. However, implementation quality can be low.

Sincerely,
Watson Ladd

>
>
>
> _______________________________________________
> TLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/tls



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin