Re: [Cfrg] matching AES security

[Michael Hamburg <[e-mail]>]

Thanks, DJB, for advancing this argument for non-512-bit curves.  As the other guy with a 400-and-something-bit curve, I was going to have to do it sometime this week as well, and you made the argument more coherently than I would have.

On Jul 30, 2014, at 11:12 AM, Watson Ladd <[e-mail]> wrote:

> 
> On Jul 30, 2014 10:40 AM, "Benjamin Black" <[e-mail]> wrote:
> >
> > AES is not the only symmetric cipher in use today and we can expect new ciphers to supersede it during the service life of the new curves under discussion. The goal is matching security levels of the suite components as designed, not adjusting things based on attacks that emerge against a given component over its service life.
> 
> 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.
> 
> Sincerely, 
> Watson Ladd
> 

To answer Uri’s question, yes, this attack requires a shared known plaintext block across all the connections.  This is most likely to happen through the use of CTR mode with a deterministic nonce; or the MAC of the empty string; or explicit key confirmation.

Also, the attack is not realistic for AES-128 in the near future, and we don’t have to warn users about it.  But it’s more realistic than a 128-bit key exhaustion.

But even in a single-target model, you can’t just compare the brute-force security levels of, say, AES-192 and NIST-P384.  Brute force is not a realistic threat to either one.  Instead you have to consider the risk that an attacker with a given budget can hack you.  This risk would encompass things like:

* Value of the keys.  The long-term ECC keys are worth more.
* Protocol tightness.  Time/memory/data attacks are not necessarily limited to multiple-user attacks, and are likely to weaken AES more than ECC.
* Chosen-plaintext are more likely to affect AES.
* Quantum computation.  More bits of AES buys you more resistance, but more bits of ECC does not.
* Mathematical breakthrough.  Hard to quantify.
* Side channels.  More bits don’t buy you much more security.

My conclusions from this would be:

* Past 192 bits of security, brute force security ratings are basically meaningless even with linear time/data tradeoffs.  Stronger ciphers are mostly a hedge against breakthroughs.
* We use 256-bit AES because it’s not much more expensive than 192-bit AES.
* We should consider a more-than-384-bit elliptic curve if and only if it’s not much more expensive than a 384-bit curve.
* There’s not much point to ed-512-mers if it costs twice as much as ed-384-mers.
* The unusual-sized curves Curve41417 and Ed448-Goldilocks should be considered if and only if they’re not much more expensive than the 384-bit alternatives.  This has been demonstrated for Goldilocks, which is 6% slower than ed-384-mers on Sandy Bridge.  I believe that it will also be true for Curve41417, but so far I’ve only heard numbers for Cortex A8 NEON, and none of the alternatives have optimized implementations on that platform.

Cheers,
— Mike