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

["Paterson, Kenny" <[e-mail]>]

On 23/04/2014 16:54, "Watson Ladd" <[e-mail]> wrote:

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

Me neither. 

Jacob Applebaum has said this kind of thing in various fora. I think it's
time he put some detail behind the claim (or stopped making it).

However, whether this is correct or not does not diminish the other
well-justified arguments for deprecating RC4. It's looking distinctly
unwell to me.


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


Indeed, the use of language models is mentioned as an enhancement in our
paper. Based on my experience of using such models in a different context,
I think they would make a big difference in reducing the attacks'
ciphertext requirements when the plaintext being targeted is "natural
language", and possibly even passwords. But this is less likely to be
effective for session cookies. It would be a great student project to
investigate this angle.


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


I don't immediately know how you'd do that, but I'm willing to be
educated! Maybe you're assuming ASCII or binary plaintext, and then
aggregating most significant bit estimates over many ciphertext positions?
Do you have an estimate for how much ciphertext would be needed to achieve
a certain confidence level here?


>-Remember wepcrack? RC4 leaks key information


Right now, we do not know how to exploit key leakage into the keystream
when RC4 is used in TLS. To understand why, you have to look at how the
RC4 key for each session/connection is computed in TLS compared to how it
is computed for each frame in WEP. If you can make progress here, then you
would have a very nice research paper (and probably an improved attack on
RC4 in TLS).



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


But then it's unwise to speculate, Watson! By contrast, many people have
studied RC4 fairly intensively over the years, and the state of the art is
what it is (modulo claims by Jacob Applebaum). I'd recommend you either do
think about RC4 hard, or go read the literature, rather than just
speculating.


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


I can almost agree with this, except for your comments about key leakage
into the keystream.


Cheers,

Kenny