Re: [Cfrg] matching AES security

["Blumenthal, Uri - 0558 - MITLL" <[e-mail]>]

On 7/30/14 8:33 , "D. J. Bernstein" <[e-mail]> wrote:

>Blumenthal, Uri - 0668 - MITLL writes:
>> IMHO, the logic/reason of matching security levels of the
>> cryptographic algorithms employed in a protocol suite is fairly
>> obvious and does not need an explicit justification.
>
>Let's think through what "matching security levels" actually means for
>matching elliptic curves with AES.

Sure.

>In the foreseeable future there will be billions of devices that users
>are relying on for cryptographic computations, and it's easy to imagine
>that a typical device will use at least one new key every minute, i.e.,
>a million new keys within two years. That's more than 2^50 keys overall.

This does not appear realistic. But I find the following more interesting:

>There are standard attacks that break _all_ of 2^50 AES-128 keys using a
>_total_ of 2^128 easy computations. Even worse, there are standard
>attacks that find _at least one_ of the keys using just 2^78 easy
>computations, a feasible computation today.

Could you please point me at a decent reference/description of this attack?

>These attacks assume that the attacker sees

[And can identify as such]

>ciphertext for, e.g., an all-zero block encrypted under all of the keys.

You are saying that there has to be _the same_ known plaintext pair for
_all_ of these 2^50 keys in order for the attack to work? And it takes
2^128 computations?

What happens if there's fewer keys than 2^50? What happens if you only
have probable plaintext? What happens if you have known plaintext pairs
but they differ across the 2^N keys?


>Sometimes protocols randomize their blocks to try to stop these
>attacks---but putting
>complications into protocols to compensate for a cipher's deficient
>security is _not_ a smart way to design a cryptographic system. For the
>past decade I've been recommending moving to larger cipher keys,
>precisely because of this attack against 128-bit keys.

You have a point. But let's evaluate/discuss this attack (its basics,
costs, applicability, etc) before figuring out costs of defending against
it.

>The argument that AES-256 "matches" 512-bit ECC is supported only by an
>oversimplified analysis of single-key attacks.

Which is what most people are concerned about, and IMHO justly so. But
let's discuss.

>Multiple-key attacks are
>much faster for AES-256, and are obviously preferable for the attacker;
>.......................

The question is whether they are plausible and/or feasible.


>All of the attack costs that I'm describing are thoroughly established
>by the public cryptanalytic literature; I'm not aware of any dispute.

"Multiple-key attacks" reference please?


>Perhaps CFRG should issue a warning about AES-128 being feasible to
>break under plausible assumptions.

I'd like to get a better understanding of both the attacks and the
assumptions. Probably the entire group (CFRG) should evaluate their
plausibility.

TNX!