Subject: Re: [Cfrg] matching AES security

From: Alex Elsayed <[email-masked]>
Date: Fri, 01 Aug 2014 01:53:50 -0700

On Wednesday, July 30, 2014 12:33:36 PM D. J. Bernstein wrote:
<Snip detailed, informative explanation of why matching security levels is 
nowhere near as simple as matching bit-lengths of keys>

I snip because I want to make a point that is considerably shorter:

Matching bit-lengths has value not in the _technicals_, but because it's a 
Schelling point. Using a 512-or-so-bit curve may very well not provide any 
computational security benefit over a 414-bit curve; nonetheless the 
_psychological_ simplification of "Oh, hashes and ECC need about 2x work 
factor bits, and symmetric keys need about 1x" is a security benefit in 
dealing with the world of humans, especially as regards deployment.

At the security parameters involved at that level, the sacrifice of 
performance involved is unlikely to be a killer (if it was, the user is 
probably using work-factor 128 systems, which happen to be roughly bit-length-
matched anyway).

---

From: Alyssa Rowan <[email-masked]>
Date: Fri, 01 Aug 2014 14:03:56 +0100

On 1 August 2014 09:53:50 BST, Alex Elsayed <[email-masked]> wrote:

>Matching bit-lengths has value not in the _technicals_, but because it's a Schelling point.

I think recommendations need to be made on solid technical and practical grounds, not fluffy marketing and psychological ones.

Users wouldn't typically know Rho work factor is actually lower than they thought at 0.886√ℓ, or might just think the 521-bit curves just typoed 512. Not to mention the eye-roll I know most of us feel when we see "military-grade" crypto marketed (probably with clearly-visible penguins), and the number of times we've all seen people copy-paste SSL configs.

We need fast, strong cryptosystems. But I don't think specific aesthetics of the bit lengths of those matter outside their security and performance effects, and I don't think it'll have an appreciable effect on adoption either way.

- --
/akr

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 1 Aug 2014 09:32:58 -0400

On Fri, Aug 1, 2014 at 9:03 AM, Alyssa Rowan <[email-masked]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
>

Such as?

The problem here is that we don't have solid technical reasons because
we don't know the attacker capabilities. In fact we can't ever know
that.

Yesterday someone claimed in another forum that 'performance' was an
objective factor, as if every algorithm executed as fast (or at least
relatively) on each architecture. The likelihood of a split decision
with algorithm A faster on Intel and B faster on AMD didn't occur to
them.

The needs of marketechture align perfectly with the goal of rigidity.
There is absolutely no way that any of the academics can tell us that
we need exactly 123 or 129 bits. So we stick to round multiples of
128.

Now curve 25519 is not perfectly rigid, but as I pointed out
previously, rigidity is a better argument than performance at the
WF256 level and performance is a better argument than rigidity at the
WF128 level

> Users wouldn't typically know Rho work factor is actually lower than they thought at 0.886√ℓ, or might just think the 521-bit curves just typoed 512. Not to mention the eye-roll I know most of us f…

I never used the term because most military crypto has been crap.
Weekend before last I was watching Daniel Ellsberg in the Chelsea
Manning room talking to Edward Snowden on a video link. None of those
names would have been known if the NSA had been remotely competent.

> We need fast, strong cryptosystems. But I don't think specific aesthetics of the bit lengths of those matter outside their security and performance effects, and I don't think it'll have an apprecia…

How many customers have you talked to about crypto?

Most people who use crypto will use the crypto that the CA industry
tells them to use. And we will pick crypto on the basis of arguments
we can explain to our customers.

And that is the way it should be. The choice of Twisted-Montgomery
versus Do-Whap Weinerschnitzel is not something we need to explain
even exists. But they do understand bit lengths even if they don't
understand the implications.

I can make a really solid marketing argument for Curve25519 and I can
make a really solid argument for NUMS-512-569.

To argue for E521 I have to make the case that 'Dan Bernstein told me
he likes it' which is not very convincing to the people who don't know
who he is.

---

From: Dan Brown <[email-masked]>
Date: Fri, 1 Aug 2014 15:39:07 +0000

I mostly agree with the discussions on this thread, but want to add one more 
theoretical (*) point.

(*) This is not something to lose sleep over, rather something for insomniacs 
to ponder at night.

It seems to me that even in the single-key setting, a 256-bit ECC key fares 
better than a 128-bit AES key, because of the tradeoff between computation and 
success rate.

To make it concrete, consider a TLS session protected with a one-use ECDHE key 
and a one-use AES key.

The following simplistic back-of-the-envelope calculation shows that a typical 
adversary would far prefer to attack the AES key.

Some variables:
- v = value of session plaintext to adversary
- s = success rate of adversary
- g = sv = expected gain of adversary
- c = computational cost of adversary
- r = g/c = sv/c = overall return on investment for adversary [left as an 
exercise]
- j = dg/dc = incremental return on investment for adversary computation

Consider a form of exhaustive search algorithm: pick a random 128-bit key AES 
against a target session ciphertext, decrypting it to confirm the guessed key. 
This assumes that the plaintext has an easily checkable form of redundancy of 
at least 128 bits, enabling the adversary to confirm the correctness of a 
guessed key.  Repeat ~c times.  This algorithm is such that

c/s ~ 2^128

So, s ~ c / 2^128.  I'm using ~ for proportional: so multiply the RHS by the 
cost of AES decryption plus plaintext redundancy verification.

Now, ignoring memory costs, Shank's baby-step-giant-step algorithm against a 
256-bit ECC is such that

c^2 / s ~ 2^256

against with other constants of proportion to be multiplied onto the RHS.  I'm 
guessing that memory-efficient algorithms like Pollard rho have the similar 
tradeoff, but please correct me if I'm wrong.

Solving for s gives s ~ c^2 / 2^256.

Plugging this back into the incremental ROI per computation gives

j_aes128 ~ v / 2^128
j_ecc256 ~ 2vc / 2^256

So, when c ~ 2^128 these are about the same, but for smaller c values, 
j_ecc256 is smaller, and thus the adversary gets more return from attacking 
the AES128 key.

In other words, the adversary's initial computation are most effectively spent 
on the AES key, because if the adversary gets lucky.  That is, *IF* the 
adversary has the computational power such that it pays off to try exhaustive 
search on AES128, then this pays off much more than trying to solve the DLP on 
ECC256 using a generic algorithm.  Of course, that's a big if.

Note that I used a heuristic of differentiation to get the j values.  This is 
inaccurate, especially for j_aes128 as c approaches 2^128.  More precisely, a 
better exhaustive search algorithm than above does try random keys, but rather 
loops through keys, never repeating, so the incremental return on investment 
actually improves per guessed key.  This means that even for large c ~2^128, 
it may still be better to run the algorithm against AES128 instead of DLP 
ECC256.

Note that in the setting above, the DH and AES keys are used once only for the 
same purpose.  In other situations, such as key transport or DH key re-use, 
the value of v would differ for the different keys, and thus may significantly 
alter the adversary's optimal strategy.

Note that the 256-bit ECC DLP algorithm cost can also be written as c/ sqrt(s) 
~ 2^128, hence the label 128-bit security for 256-bit ECC.

Note that I ignored the option of using the MAC tag to confirm AES128 key 
guesses.  Since the MAC would use a different key, I deferred its use to 
further discussion.

---

From: "Dan Harkins" <[email-masked]>
Date: Fri, 1 Aug 2014 09:21:45 -0700 (PDT)

On Thu, July 31, 2014 8:57 am, Brian Smith wrote:
> On Wed, Jul 30, 2014 at 5:33 AM, D. J. Bernstein <[email-masked]> wrote:
>> 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.
>
> I agree that it would be better to not need to randomize blocks to
> avoid the attacks you alluded to. However, it seems like randomizing
> the blocks is often easy; for example, I think it would be pretty easy
> to define AES-GCM and ChaCaa20-Poly1305 cipher suites for TLS in a way
> where the initial nonce is comes from the PRF and then incremented.

  That's basically the SIV mode of AES (RFC 5297). Perhaps that
deserves another look (I tried interesting the TLS WG in that mode
ages ago).

  Dan.

---

From: Ilari Liusvaara <[email-masked]>
Date: Sat, 2 Aug 2014 17:51:08 +0300

> with algorithm A faster on Intel and B faster on AMD didn't occur to

For better argument, try Intel vs. ARM (There are way more ARM CPUs
shipped than x86 CPUs).

The platforms I see as most relevant are:
- amd64 (a.k.a. x86-64)
- arm32 (there will likely be billions of these not yet manufactured).
- arm64 (a.k.a. aarch64)

As to how similar arm32 and arm64 are optimization-wise, I don't know. 

As for AMD, their amd64 CPUs should have relatively similar performance
characteristics as Intel ones, but of course, their ARMs are a different
story.

> we need exactly 123 or 129 bits. So we stick to round multiples of

So does "speed, speed, speed".

This comes to threat model: Given random curve meeting state-of-the-art
criteria, what is the probablity it is actually weak?

Of course, that is unknowable. But if that probability is not very
low (the highest such probabilites I have heard thrown around are
on order of 10^-6), things get problematic anyway.

How many very fast curves you think there are?

> WF256 level and performance is a better argument than rigidity at the

This assumes there is some conflict between rigidity and speed.

I don't think such conflict exists, because I don't think big class
of efficient primes exist.

And pushing out such class is useless, because there will be internal
performance differences, making it very difficult to steer selection
in any sort of "useful" direction.

The primes that have been thrown around are PMs and STs. There aren't
a lot of those at all, and very few are standouts in terms of
performance.

Taking the Curve25519 generation process explained in the paper and
replacing k=8 with k=16, as to get WF256 curve will give a prime of
2^510+15 [1]. 

On WF192-level, there is also 2^379-19. [1]

If one only has 32-bit multiplier, those constants quickly become
troublesome (64-bit one gives much more freedom).

> even exists.

Those choices are internal mathematical details, because one can just
mix and match the forms (if one has curve where the needed forms are
valid).

E.g. If doing ECDH, start with (Twisted) Edwards and then switch to
Montgomery. Or for ECDSA, do calculations using (Twisted) Edwards and
use Weierstrass on wire.

Also, while WF256 might be a good idea for CA certificates, where
performance doesn't matter that much (all signing is offline, and
verification is dumped on clients[2]), servers, even with high
security might want to run WF192 since need to deal with ECC
for every connection (and more usual servers with WF128).

Note that WF128 is regarded as quite a bit above RSA2048 in difficulty
of breaking (I think it is regarded as about equivalent with RSA3072).

Security levels above 2^210 curve ops seem to have very very
little actual usage.

BTW: The relative performance difference between P-384 and P-521
seems about similar as AES-192 vs. AES-256. Which says something
about how bad the P-384 prime is. But of course, because ECC is
so much heavier than AES, in practice it matters much more.

[1] Dunno if it is any good performance-wise.
[2] Client certs are rare.

-Ilari