Re: [Cfrg] matching AES security

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

> Is the attack DJB mentioned an attack on AES?  No: AES matches the PRP
> security definition. Is it an attack on Salsa20? No: it meets the security
> claim.
> 
> Rather it's the obvious point that a man who strains half a lake has half the
> fish.
> 
> This has been pointed out before on this list, and is really on the level of
> an exercise in probability.

In that case (probability game) this attack does not seem realistic, let
alone plausible. 

How many plaintext pairs can you store (alternatively, which one "master"
plaintext would you use)? For how many keys? How do various encryption modes
impact your ability to search your tables (i.e., might using IV interfere
with it)? How are you planning to identify that magic plaintext encryption
in the traffic stream? What do your resulting probabilities look like in
real world, after all of this has been taken into account?

I won't dump my AES-128 just yet. :-)

>> > On Wed, Jul 30, 2014 at 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. 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
>> >
>> >
>> >
>> > _______________________________________________
>> > Cfrg mailing list
>> > [e-mail]
>> > http://www.irtf.org/mailman/listinfo/cfrg
>> >