Re: [Cfrg] matching AES security

[Paul Lambert <[e-mail]>]

On 7/30/14, 5:33 AM, "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.
>
>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.
>
>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.
>
>These attacks assume that the attacker sees ciphertext for, e.g., an
>all-zero block encrypted under all of the keys.

So, would this attack be mitigated by a change in algorithm mode?
In particular, if this is true for AES-CCM or AES-GCM, it does
not look like it would apply to AES-SIV.

Paul


>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.
>
>For comparison, if we're talking about Curve25519 keys rather than
>AES-128 keys, the fastest attacks to find one out of 2^50 keys are as
>slow as the fastest attack to find a single targeted key. (This isn't
>just an observation about known attacks; it's a theorem about _all_
>attacks, following easily from the "random self-reducibility" of
>Curve25519 DL, a very strong type of "worst-case-to-average-case
>reduction".) Exactly the same comment applies to any other curve---I'm
>using Curve25519 as a concrete illustration but don't mean to suggest
>that it's special in this respect.
>
>A standard batching mechanism (1999 Escott--Sager--Selkirk--Tsapakidis,
>also crediting Silverman--Stapleton; for further analysis see 2001
>Kuhn--Struik, 2004 Hitchcock--Montague--Carter--Dawson, 2006 Bernstein,
>2012 Lee--Cheon--Hong, and 2012 Bernstein--Lange) finds all of the 2^50
>Curve25519 keys more quickly than 2^50 separate DL computations, but
>still takes time 2^150, millions of times more difficult than breaking
>an AES-128 key.
>
>If you scale down to more plausible amounts of future computation, such
>as 2^100, then the comparison becomes even more lopsided. The attacker
>is going to find millions of the users' AES-128 keys, but has chance
>only about 1/2^50 of finding even _one_ of the Curve25519 keys.
>
>> What benefit do you derive from including a stronger
>> algorithm in a chain made of weaker algorithms?
>
>Do you realize that you're arguing _against_ mixing AES-256 with a curve
>as large as 512 bits?
>
>In a world of 2^50 AES-256 keys, there's an attack that already has a
>high probability of finding a key in time "only" 2^206. This is nicely
>matched with the cost of breaking Curve41417. (I admit that Curve41417
>is slightly more secure when the inner-loop cost is taken into account,
>but let's not quibble.) What benefit do you think you're obtaining from
>larger curves, such as NIST P-521 or E-521 or Microsoft's 512-bit curve?
>
>The argument that AES-256 "matches" 512-bit ECC is supported only by an
>oversimplified analysis of single-key attacks. Multiple-key attacks are
>much faster for AES-256, and are obviously preferable for the attacker;
>inferior attacks make no sense as a basis for evaluating security. If
>you actually want a cipher that doesn't compromise the quantitative
>security level of 512-bit ECC then you need to go far beyond 256-bit
>cipher keys.
>
>The point I'm making here is orthogonal to
>
>   * Adam's point that comparing 2^200 computation to 2^250 computation
>     is meaningless---we'll never do such big computations (see
>     https://www.imperialviolet.org/2014/05/25/strengthmatching.html);
>
>   * Mike's point that what actually matters up at this level is the
>     risk of breakthroughs---e.g., quantum computers running Shor;
>     
>   * the point that several people have made about the low cost of
>     moving from 192-bit ciphers to 256-bit ciphers (and the high cost
>     of supporting an excessive spectrum of options)---so usage of
>     256-bit ciphers doesn't imply that users want 2^256 security;
>
>   * the point that it's already common practice to combine, e.g.,
>     RSA-2048 with AES-128 and sometimes even AES-256, illustrating that
>     the users' performance constraints are the biggest issue;
>
>and various other arguments against the whole concept of "matching
>security levels". What I'm saying is that if you _do_ want to "match
>security levels"---for example, Joe Salowey wrote
>
>   TLS supports 256-bit symmetric key ciphers and we want to have
>   recommended curves to match this key strength
>
>---then it's a huge quantitative error to pair AES-256 with 512-bit ECC.
>All of the attack costs that I'm describing are thoroughly established
>by the public cryptanalytic literature; I'm not aware of any dispute.
>
>Perhaps CFRG should issue a warning about AES-128 being feasible to
>break under plausible assumptions. A reasonable response to this threat
>is to move to a 256-bit (or merely 192-bit, but see above regarding
>options) cipher with Curve25519 (or Microsoft's 256-bit curve); this
>would push all known attacks above 2^120, ample protection for the
>foreseeable future. A 256-bit cipher with Curve41417 would push all
>known attacks above 2^200.
>
>---Dan
>
>_______________________________________________
>Cfrg mailing list
>[e-mail]
>http://www.irtf.org/mailman/listinfo/cfrg