Re: [Cfrg] matching AES security

[Ilari Liusvaara <[e-mail]>]

On Fri, Aug 01, 2014 at 09:32:58AM -0400, Phillip Hallam-Baker wrote:
> On Fri, Aug 1, 2014 at 9:03 AM, Alyssa Rowan <[e-mail]> wrote:
> > -----BEGIN PGP SIGNED MESSAGE-----
> > Hash: SHA512
> >
> > On 1 August 2014 09:53:50 BST, Alex Elsayed <[e-mail]> 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.
> 
> Such as?
> 
> 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.

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.

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

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?

> 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

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

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

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