[Cfrg] matching AES security

["D. J. Bernstein" <[e-mail]>]

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