[Cryptography] IETF discussion on new ECC curves.

[Trevor Perrin]

On Fri, Aug 1, 2014 at 2:26 PM, Phillip Hallam-Baker
<phill at hallambaker.com> wrote:
> On Fri, Aug 1, 2014 at 2:42 PM, Trevor Perrin <trevp at trevp.net> wrote:
>> a 512-bit twisted Edwards curve like Microsoft's will have keys of
>> 510 bits, not 512, so you must mean a 514-bit prime?
>
> The attacks are also a lot more expensive than one AES operation. So
> we don't need to be precise to the bit.

You were making a precise rigidity argument.  Since that didn't point
at your favorite prime, now anything close is acceptable?

That means other NUMS primes at 510-514 bits should be on the table,
so we're in BADA55 territory - what you're pretending is a rigid
"exclusion criteria" is actually somewhat arbitrary.


> Here the competitors on offer are:
>
> E-521
> E-512
> E-480
> E-448
>
> E-480 is not just slightly less secure than E-512, the work factor is
> reduced by 2^16, that's 65,536 times less security than we asked for.
> And the so-called 'Goldilocks curve' is twice as fast but the E-512 is
> 4 billion times harder to break.

You're overstating security differences - against known nonquantum
algorithms the "work factor" for those curves is impossibly huge.
Against quantum algorithms, they can all be broken for about the same
cost.

A "meet-in-the-middle" fear against EC is irrational - EC key sizes
are already twice the "Pollard Rho" work factor to account for
collision attacks.  But to humor that - if some breakthrough cuts
those security levels in half, they still can't be broken.  If things
get cut in half again, they all break.

The numbers just aren't that different.


> E-521 is only an order of magnitude more secure and. It is a little
> faster on typical architectures but dramatically slower on machines
> with an internal 512 bit data bus like most modern GPUs.
>
> So no, I think the argument for the 512 bit prime is pretty clear.

So you're ruling out primes less than 512 bits since their superior
performance doesn't matter, and primes more than 512 due to
performance?

That's some slippery arguing!


> Tell people to pick one or the other. They can have bleeding edge
> performance with a curve that is chosen for speed or they can choose a
> curve with no security compromises.
>
> It is as simple as that: Performance or No-Security-Compromise.

That's awful, I want performance and high-security.  So do many
people.  The crypto that gets used is crypto that meets *both*
criteria.

There's a reason no-one likes 16K RSA, despite "matching" a 256-bit
work factor.  Don't be 16K RSA!


> I don't want you to be deciding that I should be using a curve that is
> three or seven orders of magnitude less secure than I asked for in the
> name of 'security'. If you want performance go for the smaller curve.

You can use whatever you want.  But for a widely-implemented standard,
security and performance should be balanced to maximize utility for
the largest number of people.


> The problem is that the arguments have to be understood by people who
> are not in the field. And that means that they have to be straight as
> a die.

RSA has been used forever without any straight match with symmetric-key sizes.

NIST elliptic curves are mostly used without matching sizes (e.g.
AES-256 and P-384 or P-521).

Curve25519's prime size and security level aren't double 128.

But now people are going to spazz if AES256 gets used with a 448 or
480-bit curve?

I don't buy it.  Here's how I imagine things:

 1: why 448?
 2: it's a good combination of speed and security
 1: how much slower is it than 25519?
 2: 3-4x
 1: OK

---

 1: why 512?
 2: it's twice the largest AES key length
 1: how much slower is it than 25519?
 2: 6-8x
 1: Ouch


> To start using these curves we have to explain why we are not using
> the NIST curves. And that has nothing to do with performance.

I completely disagree.  Much of the interest in new curves comes from
performance.


> The reason that we are changing is that we cannot make an unqualified
> argument to someone not in the field that there is no possibility that
> they have been bongoed. And once we put that possibility on the table
> we have to make sure that nobody can raise the same argument against
> us.

Good luck selling curves from an NSA-chaired standards committee, then.


>> I don't agree that performance is a "subjective" criteria.  It depends
>> on implementation techniques which depend on specific curve decisions
>> (in particular, field primes that allow efficient reduction, efficient
>> splitting of field elements into reduced-radix limbs, and Karatsuba).
>
> It depends on what machine you have for a start. Performance has
> always been highly subjective.

With current implementations, efficiency is *not* looking that
subjective - 41417 and Goldilocks are clear standouts.  Once we can
compare them on the same architectures, I predict one will slightly
edge the other, for reasons that can be traced back to curve choice.


>> The current curve proposers have probably not yet put their best foot
>> forward in terms of efficient implementation and performance analysis.
>> For example, the Microsoft implementations I believe use full-radix
>> limbs, so have more room to improve than Goldilocks / Curve41417.  And
>> we need more comparison and analysis between Curve41417, Goldilocks,
>> and E-521.
>
> Exactly. I don't think we are going to find performance is a useful
> discriminator.

I think we will find it a useful discriminator.  I imagine the curve
proposers are busy preparing their best implementations and
performance arguments, so let's give them time and see.


> I would not use DSA to authenticate the ephemeral key. I would use
> ECDH to establish a master secret and use that to authenticate the PFS
> exchange and derive the encryption keys as a one-way function of both.
>
> That way I have WF256 encryption guaranteed and WF128 forward secrecy.

We got into this in the context of TLS, when you said:
"""
For the TLS group, there is a big performance issue and so a 2^128
work factor is defensible, particularly for PFS keys.
"""
http://www.metzdowd.com/pipermail/cryptography/2014-July/022311.html

TLS uses ephemeral DH in the same way as most IETF protocols - it
derives data encryption keys from ephemeral DH values, and uses
long-term keypairs only for authentication.

Since the ephemeral keys provide long-term forward-secrecy, it would
be great if they could use a high-security curve.

But perhaps this is one of our differences:  I'd like to see an
efficient high-security curve get widely adopted, even in TLS.

You'd rather leave those use cases to the "regular-strength" curve if
it means "compromising" on the less-efficient curve you've set your
heart on.


Trevor