Subject: Re: [Cfrg] ECC reboot (Was: When's the decision?)

From: "Paterson, Kenny" <[email-masked]>
Date: Thu, 16 Oct 2014 16:08:18 +0000

Dear all,

Watson rightly pointed out that we are far behind the originally
advertised schedule for our process for selection of curves to recommend
to the TLS WG. Other parties in and beyond IETF are waiting on our
recommendations too.

The reasons for the delay are quite complex, and I won't go into reviewing
them here. Suffice to say we've had a lot of really informative technical
discussion about performance of the different options, benchmarking, etc,
so the slippage has not exactly been wasted.

Our first task should be to finalise the requirements that we will use to
guide the selection process. I think we are close, with a couple of
outstanding issues:

1. Amount of "wiggle room" that should be permitted.

2. A more nuanced set of hardware requirements.

I suggest we use the next *week* to try to finalise the requirements, and
then November to evaluate the candidates that we currently have (along
with any new candidates that might emerge) against the final set of
requirements. 

With this schedule, we'd miss the IETF 91 meeting for our decision, but I
don't think having our answer by mid-Novmeber is really feasible. We
should certainly be able to deliver an early Christmas present to the TLS
WG.

To make this work, we'd need the RG to focus on the requirements for a
short additional period of time.

So here's a proposal for a new schedule which I believe to be feasible:

24/10/14 (1 week from now): we finalise requirements, including hardware
requirements.
31/10/14 (2 weeks from now): we agree on whatever benchmarking system
we're going to use for performance measurements. (Right now, supercop
seems like the front runner to me.)
30/11/14 (6 weeks from now): we deliver our recommendations to the TLS WG.

Could people let me know if this looks workable, within the next 24-48
hours? Meantime, I'll send a message indicating where things stand on the
requirements list.

Thanks

Kenny 

On 06/10/2014 16:26, "Watson Ladd" <[email-masked]> wrote:

>Dear all,
>We were promised on July 27 a process running for 6 weeks. Doubling I
>get 12 weeks, which is three months, of which two (August, September)
>have already gone. Am I correct in supposing that we're on track for a
>decision by Halloween?
>
>If we aren't, what remaining issues need to be addressed/when can we
>expect a decision?
>
>Sincerely,
>Watson Ladd
>
>_______________________________________________
>Cfrg mailing list
>[email-masked]
>http://www.irtf.org/mailman/listinfo/cfrg

---

From: Johannes Merkle <[email-masked]>
Date: Thu, 16 Oct 2014 18:26:15 +0200

with respect to the second issue, we have just published a common position paper of the ECC Brainpool on the
requirements for new curves.
http://eprint.iacr.org/2014/832
Most, if not all, arguments have been expressed on this list before, but this is a consolidated statement.

Johannes

PS: The paper has already been submitted two weeks ago and had been stuck in the queue at the IACR editors until now.

-- 
Mit freundlichen Grüßen,
Dr. Johannes Merkle
Principal Beratung, Elektronische Identitäten
Public Sector
secunet Security Networks AG
Mergenthaler Allee 77
65760 Eschborn
Germany
Telefon +49 201 54 54-3091
Telefax +49 201 54 54-1325
Mobil   +49 175 2224439
[email-masked]
www.secunet.com

---

From: "Paterson, Kenny" <[email-masked]>
Date: Thu, 16 Oct 2014 16:46:16 +0000

Johannes,

Thanks for the pointer to this document. Everyone should read it to get a
hardware-centric perspective on the problem we are trying to solve.

What would now be really helpful would be if you could distill the entire
5-page document into a couple of succinct sentences that we can then
debate as possible hardware-specific requirements for our process - see
this post for examples of the kind of level of detail we're looking for
here:

http://www.ietf.org/mail-archive/web/cfrg/current/msg05068.html

Thanks,

Kenny 

On 16/10/2014 17:26, "Johannes Merkle" <[email-masked]> wrote:

>with respect to the second issue, we have just published a common
>position paper of the ECC Brainpool on the
>PS: The paper has already been submitted two weeks ago and had been stuck
>in the queue at the IACR editors until now.
>

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 16 Oct 2014 20:37:41 +0300

> this post for examples of the kind of level of detail we're looking for

What I consider short a summary of this topic:

General-purpose software requires special primes, extended-sidechannel-
security stuff requires (or at least is much easier with) random primes,
other hardware can use either with no preference.

Oh, and is there anything wrong with just using Brainpool for random
primes for extended-sidechannel-security applications? It even has TLS
codepoints.

Oh, and Weierstrass form. And cofactor 1. And unrestricted twist
cofactor. And uses SEC point formats.

-Ilari

---

From: Alyssa Rowan <[email-masked]>
Date: Thu, 16 Oct 2014 18:38:55 +0100

On 16/10/2014 17:26, Johannes Merkle wrote:

> position paper of the ECC Brainpool on the requirements for new
> curves. http://eprint.iacr.org/2014/832 Most, if not all, arguments
> have been expressed on this list before, but this is a consolidated
> statement.

Upon a read, and paraphrasing broadly (feel free to correct), what the
Brainpool members seem to think meets the hardware scenario best is
curves over "verifiably pseudo-random" primes, with points represented
in short-Weierstrass form - because that matches best with their
existing "high-assurance" pieces of hardware and the ways that they
attempt to address attacks within them. They (naturally) want to
minimise any changes to that general structure, to in turn minimise
the costs of those changes.

I note that none of the concrete, implemented proposals put forward so
far are VPR. Do they have such a proposal?

They have, of course, already specified a set of verifiably
pseudo-random curves, which would be the Brainpool curves. I'm not
totally clear what CFRG can positively add to that, because they are
already specified. (An xkcd about competing standards springs to mind.)

It seems that they also want a VPR curve(s?) to be
mandatory-to-implement, presumably for interoperability's sake?

I can see why they might want that, if VPR is the most convenient for
their implementations - but from what I see from the hesitant adoption
of Brainpool in the wider community, I have serious (albeit early)
doubts that will reach wide consensus either here or in any downstream
WG, due I suspect directly to the notoriously poor software
performance characteristics of pseudo-random primes and the complexity
required to correctly implement them in software. (This will of course
be quantified during evaluation of any contender they put forward.)

It seems to me at this stage that the requirements of the
existing-hardware stakeholders of the Brainpool may be not only
orthogonal, but actually (potentially) in direct opposition to the
requirements of the software stakeholders - and further their
requirements may (perhaps) already be satisfied by the Brainpool curves?

- -- 
/akr

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 16 Oct 2014 21:00:45 +0300

> requirements may (perhaps) already be satisfied by the Brainpool curves?

I think the requirements are in direct opposition.

And I know no reason why existing Brainpool curves wouldn't be usable
for "high-security" hardware.

Also, I think for other hardware, it doesn't really matter, since
special primes are apparently neither advantage or disadvantage.

-Ilari

---

From: Andy Lutomirski <[email-masked]>
Date: Thu, 16 Oct 2014 11:06:40 -0700

> for "high-security" hardware.

Are the Brainpool curves really VPR?  They're certainly far better in
that regard than the NIST curves, but the BADA55 paper points out
correctly that the "verifiably" part is weak.

(The BADA55 curves themselves might actually not be so bad.  They were
clearly fudged, but the BADA55 property seems highly unlikely to be a
cryptographic weakness, and fudging them to have some other unlikely
property as well would have been rather expensive.)

--Andy

---

From: Alyssa Rowan <[email-masked]>
Date: Thu, 16 Oct 2014 19:29:51 +0100

On 16/10/2014 17:08, Paterson, Kenny wrote:

> Our first task should be to finalise the requirements that we will
> use to guide the selection process. I think we are close, with a
> couple of outstanding issues:

Alright, so let's try to get things in high gear and argue those out…?

> 1. Amount of "wiggle room" that should be permitted.

Broadly: I think what we're aiming for is probably one faster/strong
curve, and one stronger/fast curve.

Given the strong preferences of some to minimise the number of curves,
it looks to me like ≈384 is almost-definitely dropped, leaving us
with something near ≈256 and something near ≈512.

We seem to be in agreement that wiggle room on ≈256 would include
fields of 2^255-19 as well as 2^256-189 in scope.

For the paranoid-strong, performance-second ≈512, 2^512-569 very
obviously falls within scope.

I put forth that 2^521-1 also falls within scope. It's not very far
away, and it's a true Mersenne prime rather than a pseudo-Mersenne,
and they do not grow on trees - no others fall near our criteria (the
next lowest is 2^127-1 which is way too small, and the next biggest is
2^607-1). They are very attractive - attractive enough for 4 (?)
independent research groups to independently arrive on E-521, and
SECG/NIST to have independently picked the same prime years ago for
secp521r1.

[Previous discussion countering this point: Sean Parkinson @ RSA
suggested stepping over a power of 2 is "only going to hurt
performance in the future". Phillip Hallam-Baker also thought anything
that is not less than a clean multiple of a power of two "may cause
severe performance hits on future architectures", mentioning 512-bit
memory buses on graphics cards?! - although I'm not convinced that's
actually primarily relevant to an implementation of a high-strength
curve. We will, of course, evaluate performance of contenders in Phase
II, future architectures can be more-or-less anything that works well,
and performance implications usually aren't anything like so obvious…
Aren't Mersennes actually particularly _good_ performance-wise?]

I put forth that 2^414-17 and 2^448-2^224-1 might fall outside "wiggle
room" there, although I do so very reluctantly as I think it's a shame
to exclude them on that basis if they have otherwise nice properties,
and they do seem to have very good performance for their strength.

> 2. A more nuanced set of hardware requirements.

See other thread.

> So here's a proposal for a new schedule which I believe to be
> feasible: 24/10/14 (1 week from now): we finalise requirements,
> including hardware requirements.

Optimistic? One way to find out. <g>

> 31/10/14 (2 weeks from now): we agree on whatever benchmarking
> system we're going to use for performance measurements. (Right now,
> supercop seems like the front runner to me.)

Consider this an early +1 to SUPERCOP.

> 30/11/14 (6 weeks from now): we deliver our recommendations to the

Let's give it a try!

- -- 
/akr

---

From: Johannes Merkle <[email-masked]>
Date: Fri, 17 Oct 2014 11:21:43 +0200

Alyssa Rowan wrote on 16.10.2014 19:38:
> I can see why they might want that, if VPR is the most convenient for their implementations - but from what I see
> from the hesitant adoption of Brainpool in the wider community,

this assertion is only true for software implementations. Brainpool curves are used by more than 50 million smart
cards rolled out and several vpn solutions (e.g., based on IPSec) widely used within German and EU public authorities.

-- 
Johannes

---

From: Alyssa Rowan <[email-masked]>
Date: Fri, 17 Oct 2014 10:40:01 +0100

On 17 October 2014 10:21:43 BST, Johannes Merkle <[email-masked]> wrote:

>this assertion is only true for software implementations. Brainpool curves are used by more than 50 million smartcards rolled out and several vpn solutions (e.g., based on IPSec) widely used within German and EU public authorities.

Yes, that's exactly my point. Brainpool usage seems to be concentrated under a relatively small, interlocked group of governmental stakeholders in specialist applications - not really rolled out in the wider community like the NIST curves, let alone like RSA.

Besides, those smartcards are surely already provisioned and keyed so not relevant to any new curve?

- --
/akr

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 17 Oct 2014 12:47:55 +0300

On Fri, Oct 17, 2014 at 11:21:43AM +0200, Johannes Merkle wrote:
> > I can see why they might want that, if VPR is the most convenient
> > for their implementations - but from what I see from the hesitant
> > adoption of Brainpool in the wider community,
> 
> this assertion is only true for software implementations. Brainpool
> curves are used by more than 50 million smart cards rolled out and
> several vpn solutions (e.g., based on IPSec) widely used within
> German and EU public authorities.

And what's wrong with just using Brainpool for implementations that
need random primes for extended side channel resistance? Not rigid
enough? Not standard enough?

For software implementations only needing defenses against software
attack (including attacks from different process in the same host/VM)
there is plenty wrong with using Brainpool.

If attacker can get enough access to pull off EM attacks against most
of the endpoints, one has more severe problems than software vulernable
to EM attack.

There is a good reason (singular!) why NIST/NSA curves are used far far
more in TLS than Brainpool, despite there being codepoints for both:
Performance.

-Ilari

---

From: Johannes Merkle <[email-masked]>
Date: Fri, 17 Oct 2014 11:48:58 +0200

> correctly that the "verifiably" part is weak.

This assertion is very wrong, as I have already explained on this list. The BADA55 paper took much more freedom (in
several respects) than the Brainpool method did. It is also obvious that there approach worked only for one of the
relevant bit lengths.

As the NUMS paper correctly points out, there is no perfect rigidity as a certain degree of freedom in inevitable (e.g.,
there are many proposals for curves where the coefficients had been chosen to be minimal, so this approach is not fully
rigid either). However, to call the rigidity of the Brainpool curves "weak" is a gross exaggeration.

The Brainpool curve generation method was not just made up by BSI, but was openly discussed and agreed upon within the
Brainpool group (which comprises a diversity of companies, academic institutions and public authorities), and there were
no objections or reservations expressed. By the way, one of the authors of the BADA55 paper participated in that process
and didn't express any objections either.

-- 
Johannes

---

From: "David Leon Gil" <[email-masked]>
Date: Fri, 17 Oct 2014 09:07:40 -0700 (PDT)

Re the primes 2^521-1 and 2^607-1. Mersenne may be particularly good for hardware. Most of the large (expensive) blocks can be shared with side-channel-protected DSP blocks. And hardware designs for Mersenne multiplication are sufficiently old (Rader gives one), that there are no IP issues. (And this, I submit, should be a CFRG priority.)

They're obviously good software performers as well.

There is no problem with generating random curves mod M521; there are O(2^521-1) isomorphism classes. (About 1/4 are Edwards as well, IIRC.)

(Because of the width of DSPs needed in some applications, the prime M607 may not be significantly more expensive than M521 in hardware.)

---

From: "Hallof, Andreas" <[email-masked]>
Date: Fri, 17 Oct 2014 16:13:13 +0000

> And what's wrong with just using Brainpool for implementations that need random primes for extended side channel resistance?
Nothing is wrong about that. 

The point that Mr. Merkle is addressing, is that there is a huge world outside PC/Server-based TLS-Authentication.
I have the impression the current discussion at the cfrg is too narrowly focused on software implementations in unconstrained environments with only global timing SCA.

In the infrastructure surrounding the german eHealth-Card the majority of all TLS-Connection are based on smartcards on one communication-endpoint (the other being a server / non-smartcards).
The same is true for the smartmeter-infrastructure. 

Like it is stated in http://eprint.iacr.org/2014/832 a result of the current discussion at the cfrg could be that there are two sets of curves.
I have the impression the Brainpool-group would happily accept/(=> switch to) the one set (with random primes), that has the necessary cryptographic properties.
Thus reducing the implementation-costs at smartcards, Web-browsers, servers etc..

> Performance.
If a ECDSA-Brainpool-based-signaturecreation cost around 90 ms on a cheap smartcard, it is of little concern to me if it would be 20% faster or slower.
SCA-resistance is a concern for me.

Regards,
 Andreas Hallof

--
Andreas Hallof, Datenschutz und Datensicherheit / Kryptographie

-----Ursprüngliche Nachricht-----
Von: Cfrg [mailto:[email-masked]] Im Auftrag von Ilari Liusvaara
Gesendet: Freitag, 17. Oktober 2014 11:48
An: Johannes Merkle
Cc: [email-masked]
Betreff: Re: [Cfrg] ECC reboot (Was: When's the decision?)

On Fri, Oct 17, 2014 at 11:21:43AM +0200, Johannes Merkle wrote:
> several vpn solutions (e.g., based on IPSec) widely used within German 
> and EU public authorities.

And what's wrong with just using Brainpool for implementations that need random primes for extended side channel resistance? Not rigid enough? Not standard enough?

For software implementations only needing defenses against software attack (including attacks from different process in the same host/VM) there is plenty wrong with using Brainpool.

If attacker can get enough access to pull off EM attacks against most of the endpoints, one has more severe problems than software vulernable to EM attack.

There is a good reason (singular!) why NIST/NSA curves are used far far more in TLS than Brainpool, despite there being codepoints for both:
Performance.

-Ilari

---

From: Watson Ladd <[email-masked]>
Date: Fri, 17 Oct 2014 09:23:22 -0700

> Thus reducing the implementation-costs at smartcards, Web-browsers, servers etc..

What sort of decision do you think we are going to make? We obviously
cannot remove curves. So Brainpool will remain in TLS. The question is
about curves which make software implementations easier and faster.
Why does hardware matter for the choice we are going to make?

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Michael Hamburg <[email-masked]>
Date: Fri, 17 Oct 2014 10:58:59 -0700

> On Oct 17, 2014, at 9:23 AM, Watson Ladd <[email-masked]> wrote:
> 
> <[email-masked] <mailto:[email-masked]>> wrote:

I agree: what’s even the point of this tangent?

Lochter et al’s paper asks for curves which have exactly the same properties as the Brainpool curves.  This is mostly motivated by legacy constraints, with one secure hardware argument tossed in.  It also asks the CFRG not to do anything which would cause current Brainpool users to flee that standard.

It is eminently clear that Lochter et al are asking for the Brainpool curves to be included in any new standard.  Why would we just reroll the constants when the entire motivation for the exercise is legacy compatibility?

It’s also clear that enough of this forum cares about software performance that VPR cofactor-1 curves will not be the only curves chosen.

So is the thrust of this whole argument “have your special curves, but make Brainpool mandatory to implement”?  If so, just say so, and let the forum discuss it separately, and unblock the discussion of new curves.

Cheers,
— Mike

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 17 Oct 2014 16:22:47 -0400

On Thu, Oct 16, 2014 at 2:29 PM, Alyssa Rowan <[email-masked]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
>

Agree so far.

> SECG/NIST to have independently picked the same prime years ago for

It is a Mersenne but the performance advantage is compromised by it
being larger than 512 bits. That means every memory operation is going
to break stride. Which is a really bad tradeoff for the marginal
improvement in speed.

> memory buses on graphics cards?!

There is a good reason for that. What we call 'graphics cards' are
really just what we used to call a vector unit.

Getting someone to build purpose built ECC accelerators is hard and
expensive. I can buy an nvida card that with a ridiculous number of
cores that I can pretty much program to do anything I like.

Its not just a question of speed, its a question of the amount of
microcode required to implement ECC math as a native function of the
GPU.

> although I'm not convinced that's

That depends on whether you are looking for a reason to include or exclude.

At the ~512 level, what I am looking for is a curve that absolutely
nobody is going to be able to suggest is suspect as being bongoed.
2^512 is a round number that needs no explanation. 2^521 isn't.

The Web PKI will almost certainly be based exclusively on the ~512
level curve. The roots certainly will. So the performance advantage of
issuing end entity ~256 certs would be very small.

Where I think ~256 keys will be used is for ephemeral mix ins. So I
exchange a master session key M with the ~512 bit key, use an
ephemeral ~256 to create a second session key E and then derive my
encryption and authentication keys using a one way function on M and
E. That preserves the ~512 work factor for confidentiality and adds a
~256 work factor for forward secrecy.

So I am willing to be more flexible on ~256 than ~512 because for my
applications the attacker always has to break the ~512.

> and they do seem to have very good performance for their strength.

I agree. They are a little faster but we have to give up a lot of
security to get that speed. Its not 64 bits, its a 2^20 reduction in
work factor. I want them bits.

>> supercop seems like the front runner to me.)

I think a significant performance difference is a tie breaker but not
the best determinant. What I see as being convincing are:

1) Difficulty of screwing up the implementation (see Watson Ladd's post).

2) Legacy deployment.

Given the way that I think we are likely to use ~256 and given the
fact that DJB has established a large user base for the curve already.
I am willing to suggest we just let him win on that one unless there
is at least a 10%, maybe a 20% speed advantage he missed.

For ~512 I want the Platinum level security, whatever it takes.

---

From: Michael Hamburg <[email-masked]>
Date: Fri, 17 Oct 2014 14:27:46 -0700

> On Oct 17, 2014, at 1:22 PM, Phillip Hallam-Baker <[email-masked]> wrote:
> 

Why is this a bad tradeoff?  Will it lead to a more-than-marginal drop in speed, or is breaking stride bad for some other reason?

The best-performing implementations so far — at least the ones that use more than 4 machine words per element, and some that don't — have been those which store an n-bit number in more than n bits.  For example, Curve25519-Donna uses 320 bits to store a 255-bit number, and Curve41417 or Goldilocks or Ridinghood use 512 bits to store a 414- or 448- or 480-bit number.  This is why their primes are strictly less than 512 bits: so that they can fit in 512 bits with delayed carry propagation.

While doing a multiplication, of course, a vectorized 512-bit prime implementation would store at least 1024 bits and probably more.  But reducing back to 512 bits (and not, say, 576 bits) would come at a significant cost.

> microcode required to implement ECC math as a native function of the

Discrete graphics probably won’t be be a common crypto platform, though I agree that AVX-512F will be in a few years.

> 2^512 is a round number that needs no explanation. 2^521 isn’t.

I’m not sure what you mean by “bongoed”.  I do not believe that 2^521-1 has been struck rhythmically by hands, or has been played as a melody on bongos.

It is possible, if unlikely, that some mathematical property of Mersenne primes would make elliptic curves mod them weaker than mod other primes.  But at least 4 groups thought 2^521-1 was an obvious choice, and at least 3 of them came up with the same curve.  That’s about as unsuspicious as you’re going to get without some VPR performance art.

> issuing end entity ~256 certs would be very small.

Just the way they use ~15kbit RSA keys now, eschewing ~3072-bit keys as too weak, right?

I looked at Mozilla’s included CAs.  There are four ECC certs there, all of them on the NIST secp384r1 curve.  So they apparently do not consider ~512 bits necessary, but if the only choices are 256 and 512 I suppose they will go with 512.

The RSA-based roots are mostly 2048 bits long, equivalent to about a 224-bit ECC.  If the CAs consider this an acceptable level of security for hosts, I suspect that webmasters will be OK with ~256-bit curves.  That’s what Cloudflare uses for their universal SSL, for example.

> applications the attacker always has to break the ~512.

Maybe for your applications, but that’s not how TLS’s ECDHE works.

> work factor. I want them bits.

I basically get this sentiment.  But just so we can be clear: why do you want them bits?  Is it just an insatiable craving, or does a round 512 sound better in product advertisements, or is there a foreseeable attack that the extra bits will protect you from?

If most CAs today are OK with security equivalent to 224-bit curves, but they're hedging to 384 bits, why are you convinced that 384 or 414 or 448 or 480 bits would not be enough?  And if they aren’t enough, why not go to 607 or 640 or 1024 bits?

> 1) Difficulty of screwing up the implementation (see Watson Ladd's post).

The only new bigger-than-256-bit curve which would ease legacy transition is E-521.

> For ~512 I want the Platinum level security, whatever it takes.

Platinum is heavy and very, very expensive.  It resists corrosion phenomenally well, but not cutting.  Quite the metaphor.

— Mike

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 17 Oct 2014 22:30:55 +0100

On 17/10/14 18:58, Michael Hamburg wrote:
> So is the thrust of this whole argument “have your special curves,
> but make Brainpool mandatory to implement”?  If so, just say so, and
> let the forum discuss it separately, and unblock the discussion of
> new curves.

If that were the case then CFRG would be the wrong forum. Which algs
are MTI for which IETF protocols is an IETF issue.

S.

---

From: Watson Ladd <[email-masked]>
Date: Fri, 17 Oct 2014 14:45:25 -0700

> to break stride. Which is a really bad tradeoff for the marginal

Shouldn't this show up in benchmarks? Or is this a performance issue that
doesn't actually do anything with performance?

> cores that I can pretty much program to do anything I like.

Actually,  there are major issues with offloading to graphics cards in
latency. My guess is that CPU performance is fast enough that graphics
cards don't win out.

> microcode required to implement ECC math as a native function of the

Right: an extra load is so hard.
> work factor. I want them bits.

As Mike Hamburg points out downthread, TLS doesn't work that way.

Furthermore, P384 is in use now. I wish someone would toss it into eBATS,
but I think both Curve 41417 and Goldilocks are faster by something, can't
recall what.

> 1) Difficulty of screwing up the implementation (see Watson Ladd's post).

Which has little to nothing to do with curves. See DJB's curves coordinates
and computations email.

> 2) Legacy deployment.

See above.
>http://www.irtf.org/mailman/listinfo/
<http://www.irtf.org/mailman/listinfo/cfrg>cfrg

---

From: James Cloos <[email-masked]>
Date: Fri, 17 Oct 2014 19:11:23 -0400

>>>>> "MH" == Michael Hamburg <[email-masked]> writes:

MH> I looked at Mozilla’s included CAs.  There are four ECC certs there,
MH> all of them on the NIST secp384r1 curve.  So they apparently do not
MH> consider ~512 bits necessary, but if the only choices are 256 and 512
MH> I suppose they will go with 512.

The nist 2^521-1 curve probably wasn't available in enough software.

Presumably for the same reason suite-B lost it.  (Which, AIUI, was some
ipr claim, yes?)

-JimC
-- 
James Cloos <[email-masked]>         OpenPGP: 0x997A9F17ED7DAEA6

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 17 Oct 2014 19:31:05 -0400

On Fri, Oct 17, 2014 at 5:27 PM, Michael Hamburg <[email-masked]> wrote:

> Discrete graphics probably won’t be be a common crypto platform, though I
> agree that AVX-512F will be in a few years.

I think that we will find the CPU choices will end up being limited to CPU
cores and GPU cores long term because those are the areas where all the big
R&D bucks are going.

Its like when I try to buy motors for my robots. There are no motors made
for the purpose of driving a dalek or an R2D2. There are motors made for
scooters and wheelchairs because those are the markets with the big enough
markets.

AVX-512F looks tasty though.

> I’m not sure what you mean by “bongoed”.  I do not believe that 2^521-1
> has been struck rhythmically by hands, or has been played as a melody on
> bongos.
>

Got at by the NSA.

> It is possible, if unlikely, that some mathematical property of Mersenne
> primes would make elliptic curves mod them weaker than mod other primes.
> But at least 4 groups thought 2^521-1 was an obvious choice, and at least 3
> of them came up with the same curve.  That’s about as unsuspicious as
> you’re going to get without some VPR performance art.
>

The only reason we are interested in ECC is that RSA stops giving
meaningful increases in work factor at 2048 bits. 4096 bits is a lot more
work for the defender for a rather modest improvement in work factor.

I looked at Mozilla’s included CAs.  There are four ECC certs there, all of
> them on the NIST secp384r1 curve.  So they apparently do not consider ~512
> bits necessary, but if the only choices are 256 and 512 I suppose they will
> go with 512.
>
> The RSA-based roots are mostly 2048 bits long, equivalent to about a
> 224-bit ECC.  If the CAs consider this an acceptable level of security for
> hosts, I suspect that webmasters will be OK with ~256-bit curves.  That’s
> what Cloudflare uses for their universal SSL, for example.

The only reason to deploy ECC is if we are unsatisfied with RSA. It is not
the case that RSA2048 is satisfactory. It is merely 'adequate'.

> Maybe for your applications, but that’s not how TLS’s ECDHE works.

Not relevant because we have to cut a new OID set anyhow. In fact there is
quite a raft of changes likely to happen in parallel.

> I basically get this sentiment.  But just so we can be clear: why do you
> want them bits?  Is it just an insatiable craving, or does a round 512
> sound better in product advertisements, or is there a foreseeable attack
> that the extra bits will protect you from?
>

If a competitor launches a 512 bit ECC cert then I will have to.

> If most CAs today are OK with security equivalent to 224-bit curves, but
> they're hedging to 384 bits, why are you convinced that 384 or 414 or 448
> or 480 bits would not be enough?  And if they aren’t enough, why not go to
> 607 or 640 or 1024 bits?

Same reason as 2048 and 1024 the next nearest power of 2 that gives close
to the desired work factor.

When we chose 1024 we were working with 2^80 as an acceptable work factor.
Now we are generally looking for 128 and 256. So RSA2048 is showing its age.

Making the choice for TLS is perhaps not ideal as TLS is a transport
protocol and so we are not that worried about long term security. For
S/MIME we really do want 30 year security.

> The only new bigger-than-256-bit curve which would ease legacy transition

I think the legacy argument is a lot stronger for Curve 25519. Not in the
TLS space but he has got a lot of mindshare elsewhere.

> Platinum is heavy and very, very expensive.  It resists corrosion
> phenomenally well, but not cutting.  Quite the metaphor.
>

I rejected diamond because its brittle.

---

From: Benjamin Black <[email-masked]>
Date: Fri, 17 Oct 2014 16:47:48 -0700

On Fri, Oct 17, 2014 at 4:31 PM, Phillip Hallam-Baker <[email-masked]
>> has been struck rhythmically by hands, or has been played as a melody on

If the NSA is capable of causing numbers to be Mersenne primes then we
should all pack it in immediately.

b

---

From: Benjamin Black <[email-masked]>
Date: Fri, 17 Oct 2014 17:10:00 -0700

> Presumably for the same reason suite-B lost it.  (Which, AIUI, was some
Per an earlier thread, P521 was not intended to be in Suite B, but AES-192
was. Since AES-192 was not broadly implemented, P384 was paired with
AES-256, instead.

b

---

From: Michael Hamburg <[email-masked]>
Date: Fri, 17 Oct 2014 20:35:03 -0700

> On Oct 17, 2014, at 4:31 PM, Phillip Hallam-Baker <[email-masked]> wrote:
> 
>> Phillip Hallam-Baker <[email-masked]> wrote:
>> 

Maybe I should expand on this.  Sometimes precious metals or gemstones are used for protection (platinum for corrosion, sapphire for abrasion, …) because they’re genuinely the best material to survive a particular harsh environment.  Sometimes they’re used for marketing reasons.  Sometimes it’s a combination.

It’s clear from your email that you want this 512-bit “Platinum level security" for marketing reasons.  If your competitor offers it, you’ll need to as well.  521 bits is not so round, not so shiny. And 414 or 448 or 480, well, everyone knows those are less than 512.  You don’t know, and I don’t know, what the possible threats are against curves like this, or whether more bits (and how many) will help resist them.  But you want 512 anyway, whatever it takes.

And you know what?  I get that.  Especially post-Snowden, marketability is an important part of any new security standard.  But that won’t stop me from pushing a solution that gives similar security at half the cost.

— Mike

---

From: Watson Ladd <[email-masked]>
Date: Sat, 18 Oct 2014 07:56:59 -0700

> hours? Meantime, I'll send a message indicating where things stand on the

This looks workable, assuming the requirements doesn't become settling
the issue of point formats. (This seems to have quieted down, but
probably out of exhaustion rather than agreement) If we give ourselves
the month to do that, I think this makes sense. (Waiting around for
benchmark results can easily be done while doing other things)

I second the recommendation for Supercop: it has very good diversity
of systems, easy to develop for, and already contains many contenders.
Sadly, my P256 entry clearly needs work: the reference implementation
is outperforming it on many CPUs! (This is probably due to the lack of
a precomputed table of points for basepoint multiplications, or having
the wrong window size, or some other similar issue: I'll investigate
further) A state of the art P256 implementation and P384
implementation would make comparing the benefits of the new curves
easy.

One feature I would like to see is an easy way to plot multiple
different primitives on the same graph, across machines. Reading the
numbers from the per machine charts and accumulating them manually
gets tired fast, and the graphs with all primitives are very crowded,
including primitives that while fast are not on the table (for odd
reasons: we should be able to work out a way to put Kummer surfaces
into TLS to reduce CPU costs)

Sincerely,
Watson Ladd

---

From: Rob Stradling <[email-masked]>
Date: Mon, 20 Oct 2014 10:40:47 +0100

On 18/10/14 01:10, Benjamin Black wrote:
> On Fri, Oct 17, 2014 at 4:11 PM, James Cloos <[email-masked]
> <mailto:[email-masked]>> wrote:
>
>      >>>>> "MH" == Michael Hamburg <[email-masked]
>     <mailto:[email-masked]>> writes:
>

When we generated our ECC root CA keys in 2008, secp384r1 seemed like 
the best choice.  secp521r1 wasn't in Suite B, and it seemed likely that 
Suite B compliance would be a requirement for some of our customers.

BTW, I strongly suspect that secp521r1/SHA-512 certificate signatures 
are in practice unusable in WebPKI TLS.  RSA/SHA-512 certificate 
signatures are definitely unusable.  The problem isn't lack of support 
for any of the algorithms in the crypto libraries.  Rather, the problem 
is that TLS clients commonly don't specify RSA/SHA-512 and ECDSA/SHA-512 
in the TLS signature_algorithms extension.  Some servers respond by 
refusing to serve certs with SHA-512 signatures.

> Per an earlier thread, P521 was not intended to be in Suite B, but
> AES-192 was. Since AES-192 was not broadly implemented, P384 was paired
> with AES-256, instead.

-- 
Rob Stradling
Senior Research & Development Scientist
COMODO - Creating Trust Online

---

From: Alyssa Rowan <[email-masked]>
Date: Mon, 20 Oct 2014 14:05:13 +0100

On 20 October 2014 10:40:47 BST, Rob Stradling <[email-masked]> wrote:

>When we generated our ECC root CA keys in 2008, secp384r1 seemed like the best choice.  secp521r1 wasn't in Suite B, and it seemed likely that Suite B compliance would be a requirement for some of our customers.

Why not secp256r1? (I'm guessing the big reason was because the TS profile required ≈WF192 and you wanted one root to be suitable for both profiles if you could?)

It's a bit early to say, but (open question to all) if we picked one curve at ≈WF128, would you in principle be comfortable with having roots of that strength?

What about if we picked two: one fast secure curve at 128 and one at some higher "paranoid" grade (be it 384, 448, 480, 512, 521, 607...)? Which would you perhaps consider using when? Would you have one root at each level, or a shared root at the paranoid level?

What kinds of things would you need to be able to have such a root? I'm guessing, bringing it back home to the weekly topic, that 'high-assurance' crypto hardware of some form would be highly desirable for that. But what does that mean to *you*?

I say this because I don't think the initial target market for these new curves necessarily includes those mandated to use Suite B (although never say never!), I don't think government approval will drive adoption this time, and also the assurances people ask of Web PKI CAs in particular seem to be strengthening considerably relative to where they were (cf: Certificate Transparency, et al).

>TLS clients commonly don't specify RSA/SHA-512 and ECDSA/SHA-512  in the TLS signature_algorithms extension.  Some servers respond by refusing to serve certs with SHA-512 signatures.

Thanks for that note. The TLS WG and user-agent participants should probably bear this in mind, down the line, if whatever we come up with is to be accepted and used.

- --
/akr

---

From: Harry Halpin <[email-masked]>
Date: Mon, 20 Oct 2014 21:49:54 +0200

Note that there has been a vigorous discussion over exposing whatever
curves the CFRG recommends to the IETF TLS WG as part of the W3C
WebCryto API.

For those who are interested, see here:

https://www.w3.org/Bugs/Public/show_bug.cgi?id=25839
https://www.w3.org/Bugs/Public/show_bug.cgi?id=25618

In particular, there is debate over extensions for ECC curves for
WebCrypto, which currently only the NIST curves. Developers have
requested non-NIST curves during our public "Last Call" review. The
opinions in the Working Group are wide-ranging.

Microsoft has already provided a change request for the NUMS curve and
Trevor Perrin has provided an extension spec for Curve 25519.

With my W3C hat on, I'm just going to announce that due to this
situation there's a possible dependency with WebCrypto on this decision.
Since W3C has a rather strict process and timetable for Working Groups,
knowing the precise schedule for the decision helps our process run
smoother and allows us to co-ordinate our schedule.

   cheers,
         harry

---

From: "Lochter, Manfred" <[email-masked]>
Date: Tue, 21 Oct 2014 10:27:13 +0200

__________ ursprüngliche Nachricht __________

Von:		Stephen Farrell <[email-masked]>
Datum:	Freitag, 17. Oktober 2014, 23:30:55
An:		Michael Hamburg <[email-masked]>
Kopie:	"[email-masked]" <[email-masked]>
Betr.:	Re: [Cfrg] ECC reboot (Was: When's the decision?)

> are MTI for which IETF protocols is an IETF issue.

I can assure you that this is not the case. The Brainpool paper 
eprint.iacr.org/2014/832 discusses selection criteria for secure elliptic 
curves and their use. We basically look at different attack models and derive 
requirements on secure elliptic curves. (A very simplistic way of describing 
the attack models is HW vs. SW).
In my understandig that is exactly the topic of the cfrg discussion.  

Actually, we do not even propose that the cfrg choose the Brainpool curves, we 
just propose to generate two sets of curves, one using special primes and one 
using special primes. Here we assume the generation process to be a trusted 
pocess. We also note that a flexible approach that allows an easy replacement 
of curves is very desirable.

As the cfrg  also discusses parameter lengths I would like to add that it is 
completely adequate to use 384 bit curves even for highest security demands. 
So, 384 bit curves must be included in any proposed set of curves.

Manfred

-- 
Lochter, Manfred
--------------------------------------------
Bundesamt für Sicherheit in der Informationstechnik (BSI)
Referat K21
Godesberger Allee 185 -189
53175 Bonn

Postfach 20 03 63
53133 Bonn

Telefon: +49 (0)228 99 9582 5643
Telefax: +49 (0)228 99 10 9582 5643
E-Mail: [email-masked]
Internet:
www.bsi.bund.de
www.bsi-fuer-buerger.de

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 21 Oct 2014 12:05:29 +0300

> of curves is very desirable.

You mean pseudorandom primes and special primes, right?

And what would advantage of generating a new pseudorandom set be, compared to
just using Brainpool if pseudorandom primes are needed?

I don't see any advantage (at least based on properties you have claimed to
be desirable and properties you have claimed for Brainpool to have). Nor do
I see such curves would be used much in practice.

> So, 384 bit curves must be included in any proposed set of curves.

Not if you can get more security at less or equal cost. There are some above-
384bit primes with very good performance (there doesn't seem to be that good
primes near 384bit).

-Ilari

---

From: "Lochter, Manfred" <[email-masked]>
Date: Tue, 21 Oct 2014 11:27:52 +0200

Von:		Ilari Liusvaara <[email-masked]>
Datum:	Dienstag, 21. Oktober 2014, 11:05:29
An:		"Lochter, Manfred" <[email-masked]>
Kopie:	[email-masked]
Betr.:	Re: [Cfrg] ECC reboot (Was: When's the decision?)

> > Actually, we do not even propose that the cfrg choose the Brainpool
> > curves, we just propose to generate two sets of curves, one using special
> > primes and one using special primes. Here we assume the generation
> > process to be a trusted pocess. We also note that a flexible approach
> > that allows an easy replacement of curves is very desirable.
>

Yes. Thank you!
>
> And what would advantage of generating a new pseudorandom set be, compared
> to just using Brainpool if pseudorandom primes are needed?

I strongly believe that pseudorandom primes are needed. There is no immediate 
advantage in generating new curves. The proposal to generate new curves has 
two main driving factors.
a) We want to be open to an approach where an widely agreed generation method 
is used.
b) The original Brainpool curves have falsely been discredited  in the 
BADA55-paper.
> I see such curves would be used much in practice.

Is this opinion based on our papers or on the discussion within cfrg?
>
> > As the cfrg  also discusses parameter lengths I would like to add that it
> > is completely adequate to use 384 bit curves even for highest security
> > demands. So, 384 bit curves must be included in any proposed set of
> > curves.
>
> Not if you can get more security at less or equal cost. There are some
> above- 384bit primes with very good performance (there doesn't seem to be
> that good primes near 384bit).

Here 384 refers to random primes. The main point is that there has been the 
proposal to drop 384 (or similar) at all, and to just propose 256 and 512 bit 
curves.

Manfred

Postfach 20 03 63
53133 Bonn

---

From: Tanja Lange <[email-masked]>
Date: Tue, 21 Oct 2014 13:40:03 +0200

Dear Manfred,

> b) The original Brainpool curves have falsely been discredited  in the 

What do you claim to be false in that paper?

We show -- and as far as I know are the first to show -- that the
approach to generate the BP curves allows the designer of that
approach to hide a one-in-a-million weakness in the resulting 
curve, should he or she have found such a weakness.

Regards
	Tanja

---

From: Alyssa Rowan <[email-masked]>
Date: Tue, 21 Oct 2014 14:12:46 +0100

On 21 October 2014 09:27:13 BST, "Lochter, Manfred" <[email-masked]> wrote:

>>> [MH] So is the thrust of this whole argument “have your special curves, but make Brainpool mandatory to implement”?  If so, just say so, and let the forum discuss it separately, and unblock the discussion of new curves.
>> [SF] If that were the case then CFRG would be the wrong forum. Which algs are MTI for which IETF protocols is an IETF issue.
> [ML] I can assure you that this is not the case. Actually, we do not even propose that the cfrg choose the Brainpool curves, we just propose to generate two sets of curves, one using special primes and one using [pseudorandom] primes. Here we assume the generation process to be a trusted process.

Perhaps I'm confused, or perhaps there's a language barrier? The position paper you posted says that Brainpool wants pseudorandom prime curves, whose description *exactly* matches those of the existing Brainpool curves, but generated via some (unspecified, yet assumed trusted) new process; that you want these alongside special curves; and you want the PSR curves to be mandatory to implement.

Um... Wasn't this what Brainpool was for? Don't you already have some? They've got codepoints assigned and everything, and not even all that long ago. The Brainpool hardware stakeholders were quite clear that what they wanted was, basically, Brainpool - which is why I assume they are in Brainpool. We have pointed out that they've already got that, and no change obviously unbeatably minimises the changes to deployed crypto hardware, which they were quite clear was one of their goals!

If you wanted another Brainpool: why, and what is stopping Brainpool from doing it? You didn't need to do it here before. You seem to be worried the BADA55 paper discredits the Brainpool curves by showing a plausible way they could have been rigged. It doesn't prove that they actually were rigged (indeed, Brainpool is listed on Safecurves as "somewhat rigid" and still has a tick in that box). Where's the fire?

And you aren't clear how you could avoid making enough choices in any new VPR process to address the BADA55 criticisms, because you haven't suggested any new VPR process, just assumed one will exist and be agreed within our timescales. A bold assumption.

I'm relatively new, but my understanding is that Stephen is correctly pointing out that mandatory-to-implement anything is way out-of-scope here. We make suggestions, recommendations; downstream WGs in IETF decide whether they have rough consensus to adopt them, and then implementers decide whether they actually care to.

I have expressed scepticism that pseudorandom Brainpool-style curves will meet the needs of the TLS WG bringing this request to us. They'll almost certainly come dead last in performance and complexity in most scenarios, and rigidity is, as the BADA55 paper points out, tricky to argue. You haven't refuted that.

>As the cfrg  also discusses parameter lengths I would like to add that it is completely adequate to use 384 bit curves even for highest security demands.

I agree, although there aren't any convenient special primes around that area. (I also think 256 is fine.)

>So, 384 bit curves must be included in any proposed set of curves.

Um, how does that follow? Do you propose just 256 and 384, then? Or...?

Why is 384-bit a must? What's so magical about it? Why not 417? 448? 512? 521? 607? 31337?

I'm just not clear about what you want from us, and why you don't already have it.

- --
/akr

---

From: "Lochter, Manfred" <[email-masked]>
Date: Wed, 22 Oct 2014 14:04:36 +0200

>
> If you wanted another Brainpool: why, and what is stopping Brainpool from
> doing it? You didn't need to do it here before. You seem to be worried the
> BADA55 paper discredits the Brainpool curves by showing a plausible way
> they could have been rigged. It doesn't prove that they actually were
> rigged (indeed, Brainpool is listed on Safecurves as "somewhat rigid" and
> still has a tick in that box). Where's the fire?

For examle here:
> correctly that the "verifiably" part is weak.

And for me the reasoning from the BADA55 paper does not appear to be 
plausible.

>
> I'm relatively new, but my understanding is that Stephen is correctly
> pointing out that mandatory-to-implement anything is way out-of-scope here.
> We make suggestions, recommendations; downstream WGs in IETF decide whether
> they have rough consensus to adopt them, and then implementers decide
> whether they actually care to.

Where did I suggest to make anything mandatory? I searched all my postings 
for "mandatory" without finding that source.

> > demands.

You can see this statement as a direct answer to your own posting from 
September 14, where you stated "If it's optional, I definitely say drop 192 
from requirement SE6". There you did not write about 31337, did you?

To make it perfectly clear: If the group is going to only propose curves for 
two security-levels I'm opting for 128 and 192. 

Manfred

Postfach 20 03 63
53133 Bonn

---

From: Alyssa Rowan <[email-masked]>
Date: Wed, 22 Oct 2014 13:59:36 +0100

On 22 October 2014 13:04:36 BST, "Lochter, Manfred" <[email-masked]> wrote:
>And for me the reasoning from the BADA55 paper does not appear to be plausible.

I understand your defending your position, but there does appear to be professional disagreement on that point. (I think myself they are indeed plausible but not too likely, as the approach taken by Brainpool would have likely been the most obvious one at the time. However, I have not investigated this in detail.)

Like I've said, if you want new pseudorandom curves, nothing stopped you before and nothing's stopping you now - but: I don't think that's what the TLS WG asked us for; I don't think that's what anyone other than the Brainpool participants want; I don't think Brainpool needs our help to get the things it wants because it's already got them; I don't agree at all it's the best approach to take even in hardware, and; I don't think any further discussion on this point will bring our diametrically-opposed requirements into unison, it'll just delay matters and we don't want that.

I propose therefore, simply, that no changes need to be made to the curve criteria to accommodate the request of the Brainpool group. Let's move on from this.

>> …mandatory-to-implement anything is way out-of-scope here.
>Where did I suggest to make anything mandatory? I searched all my postings for "mandatory" without finding that source.

Um. It's… right there in the conclusions of the position paper you co-authored and linked here, Manfred.

"Requirements for Standard Elliptic Curves: Position of the ECC Brainpool", Cryptology ePrint Archive: Report 2014/832 <https://eprint.iacr.org/2014/832>:
>A potential compromise is the construction of new curves with similar properties as the Brainpool Curves, i.e., with verifiably pseudo-random primes, and make this set mandatory to implement.

I hope that clears that up for you. And as before, any mandatory agreement is not really within our gift to give, so that's not a compromise we can really make.

>To make it perfectly clear: If the group is going to only propose curves for two security-levels I'm opting for 128 and 192.

If 192 is strong enough, surely bigger ones would be stronger and also fine?

If 192 is not a good efficiency::security inflexion point, we'd probably rather choose another. If stronger ones are more efficient (and they are: Curve41417, Ed448-Goldilocks) we'd probably rather choose those, unless we can very clearly justify why 192, and not, say 256.

Why would you pick 192, in particular, given there are really no very good special primes in that area and, for example, AES-192 is seldom used? (secp384r1 and SHA-384 is only used anywhere because NSA Suite B picked it; even they couldn't get anyone who actually used AES-192.) This is, after all, the kind of thing meant by "rigidity": clear, justifiable, obvious reasoning, without arbitrary unexplained choices.

- --
/akr

---

From: Johannes Merkle <[email-masked]>
Date: Thu, 23 Oct 2014 11:46:58 +0200

Dear Tanja,

please allow me to answer your question. I have repeatedly expressed my feeling that the discrediting of the Brainpool
curves by the BAD55 paper is wrongful and unfair.

First of all, I would like to emphasize that I was not involved in the generation of the Brainpool curves, as I started
participating in the Brainpool group not before end of 2005. (I don't need to tell you that, as you had been a Brainpool
member in that time but others on this list will not know.)

In your paper, you explain, how you were able to create an elliptic curve with a BADA55 string in the coefficient a: As
you put it, the basic idea was "to try all possible combinations of hash functions, seed length, initial seed constant,
and so on, until he [Jerry] finds a curve that exhibits the desired vulnerability." Thus, you chose a general with
design variations that result in almost 20 bits of freedom or, equivalently, almost 2^20 combinations. According to your
paper, the following variations were used:
- 73 natural constants
- 10 different hash functions.
- 6 block size configurations of the hash function
- 2 endian-formats for the seed
- 5 counter lengths for the seed update function
- 2 orders for the concatenation of counter and seed
- 2 methods of shortening the seed to the right length
- 8 "different ways to update the counter between generation of a and b and to choose the order of generating a and b"

While your approach is scientifically sound and ingenious, I object to the conclusion that it is comparable to the
approach taken for the Brainpool curves. In this case, the number of plausible variations is much smaller:

1. Choice of the natural constants.  Brainpool curves used Pi to generate the primes and e to generate the curve
coefficients. Apart from 0, 1 and 2, or i, these are by far the most prominent mathematical constants. Period. It
doesn't matter what constants are used in some hash or symmetric encryption functions (where mathematical theory is much
less prevalent than in asymmetric crypto); when it comes to rigidity and trust, you have to choose the most natural
looking, obvious seeds.
If you ask a random mathematician about which constant is most prominent, you will get Pi as an answer with overwhelming
probability, and on second place, there will almost certainly be e. For instance,
http://en.wikipedia.org/wiki/Mathematical_constant lists these two as the first in the list of mathematical constants,
and only two others (sqrt(2) and i) as "Common mathematical constants". Nobody would answer  zeta(3), zeta(5), sin(1),
sin(2), cos(1), cos(2), tan(1), tan(2), sqrt(3), sqrt(5), sqrt(7), log(2), or any of their reciprocals, very few would
respond with the Euler–Mascheroni gamma (or any other like listed in Wikipedia as "Constants in advanced mathematics").
The golden ratio phi = (1 + sqrt(5))/2 is certainly quite prominent, but without doubt, the numbers Pi and e are by far
more "fundamental" in that they appear in so many important results. Leaves only sqrt(2) as an alternative choice;
however, sqrt(2) is algebraic, and transcendental numbers are widely felt as being less comprehensible and structured.
(Also, one could argue that deriving seeds from algebraic numbers may give it a "bad small" for the generation of
algebraic curves, but this is a weak argument as the hash function should destroy any algebraic relation.)
The conclusion is that even if you are willing to accept sqrt(2) and the golden ratio as comparably prominent and
eligible as e, Pi is outstanding and, thus, I could only imagine Pi alone, Pi+e, Pi+phi, Pi+sqrt(2), as well as reversed
orders of the combinations as being an acceptably obvious choice. This makes 7 choices, as compared to 73.

2. Choice of hash function. The Brainpool members used the approach of ANSI X9.62 to derive integers from the seeds.
This was (and is) by far the most relevant standard for elliptic curves, and I can see no reason to deviate from that
method; for a PRNG, SHA-1 was (and still is) sufficiently secure [1]. Thus, although SHA-2 was already standardized in
that time, there was no reason to change the hash function. Beside from deviating from the existing standard, using
SHA-2 would have implied additional options w.r.t the output length, which is undesirable for rigidity. IMHO, anything
else than SHA-1 would have looked less plausible. Thus, I do not really see any freedom here.

3. Seed length. ANSI X9.62 requires the seeds to be at least 160 bits long. This requirement is implied by the output
length of SHA-1. In fact, all seeds used for the NIST curves had exactly 160 bits. Again, there as no reason to deviate
from this existing example, thus, using 160 bit was the most natural choice. In addition, where there is no maximum, the
minimum is the only distinguished value.

4. Block size configurations of the hash function. This configuration option is not available for SHA-1 (and, BTW, not
for SHA-2 either).

5. Endian-formats for the seed. The Brainpool group used the same integer representation as ANSI X9.62 and all other
relevant standards for elliptic curves. IMO, any deviation would have looked suspicious.

6. Counter lengths for the seed update function. I don't know, if the option of a dedicated counter had been considered
by the Brainpool group, but for me using a counter in addition to the seeds adds unnecessary flexibility and is, thus,
undesirable.

7. Orders for the concatenation of counter and seed. No counter, no order.

8. Methods of shortening the seed to the right length. To me, the idea of rounding sounds quite unusual in the context
of cryptographic derivation functions. But to be fair, I admit that the expansion of the constants by 1120 bits, e.g.,
setting Seed = 2^1120*Pi, and the subsequent truncation of one nibble at the right hand side gives a few options. They
could have set Seed = 2^1118*Pi, which would have eliminated the need for truncation. Or they could have truncated on
the left hand side. If we add the two options of ordering the seeds according to the individual bit lengths (Seed_160 on
the left side and Seed_512 on the ride hand side, or vice-versa), we get 6 options.

9. Method to update the counter between generation of a and b and to choose the order of generating a and b. The natural
order of a and b is given by the alphabet, and, IMO, reversing this in the generation method would look a bit
artificial. For updating the seed after generation of b, the Brainpool method simply uses the seed update function. This
is the simplest approach, which is generally preferable for rigidity. But lets assume that applying the hash function s
-> h(s) was also an option, which makes 2 options.

10. There is an additional source of flexibility: It has been observed (initially in RFC 5639) that the derivation
method differs from that in ANSI X9.62 in that both coefficients are derived directly from the seeds, whereas ANSI
derives just r = a^3/b^2 mod p and leaves definition of a and b open. As explained in RFC 5639, the objective of the
Brainpool members was to generate for each bit length two isomorphic curves, one with random a and one with a=-3. The
motivation behind this was that random coefficients may facilitate avoiding patents in implementations. Since the ANSI
method does not specify how to obtain a verifiably pseudo-random a, a deviation seems unavoidable to achieve this
objective. And the most simple approach is to generate a and b using the same method as specified by ANSI for r. And by
the way, the same method (with different seed) was also used to generate the prime p.

When I multiply all the options, I get 7*6*2=84 options. Even if you don't agree with all my statements above and add
some options at one aspect or the other, there is a big difference to the estimation of 1.4 million possibilities
estimated in your paper. Furthermore, in all aspects where flexibility was possible, the choice of the Brainpool group
was among the simplest and most plausible. Of course, any assessments of plausibility is subjective and can be
controversially discussed - presumably without reaching consensus.

On the other hand, the approach taken for the Curve25519, i.e. to choose minimal coefficients, is also not 100% rigid.
In his Curve25519 paper, Dan writes:
> I rejected A = 358990 because one of its primes is slightly smaller
> than 2^252, raising the question of how standards and implementations should
> handle the theoretical possibility of a user's secret key matching the prime;
> discussing this question is more difficult than switching to another A. I rejected
> 464586 for the same reason. So I ended up with A = 486662.

These are valid arguments but, nevertheless, the conclusion is subjective. Furthermore, Bos, Costello, Longa, and
Naehrig, took quite the same approach and arrived at different curves (the NUMS curves), even at different primes. As
they write, "Full rigidity is virtually impossible in practice" [2]. I fully agree with that.

The best approach to address this is to openly discuss (with open outcome) the generation method in a large audience of
interested parties. This exactly was done in the ECC Brainpool, which is an open group which everybody (even private
persons) can join without registration, feed, or restrictions, and which includes virtually all stakeholders of ECC
standardization in Germany. In this open forum, the generation method was presented and discussed, and there was a
consensus that it is eligible. Actually, you know that better than me, because you had been an active member at that
time and you participated these discussions.

All the more, I was surprised to find you among the authors of the BADA55 paper, which, IMHO, casts a damning light of
suspicion on the Brainpool curves. And Dan's statement on this list is even more explicit in that:

> However, the following recent analysis shows that the Brainpool curves,
> which were advertised as "generated in a systematic and comprehensive
> way" covering several different security levels, actually gave the curve
> generator the flexibility to secretly choose from among more than
> 1000000 curves for any particular prime:

I have already met users (with limited knowledge in cryptology) telling me they have read that the Brainpool curves are
not trustworthy. Considering the process that had been taken by the Brainpool group, this statement is unjustified and
misleading, and considering that the curves are already rolled out in more than 50 million national ID cards and
passports, this damage of reputation is very serious.

I fully respect your scientific work in the area of elliptic curves and your contribution to the current standardization
effort, but consider the impact of your paper to the reputation of the Brainpool curves as very unfortunate.

Best regards,
Johannes

[1] NIST Special Publication 800-57. Recommendation for Key Management – Part 1: General (Revision 3). 2012
[2] J. Bos, C. Costello, P. Longa, and M. Naehrig: Selecting Elliptic Curves for Cryptography - A presentation for the
Crypto Forum Research Group (CFRG).
http://patricklonga.webs.com/Presentation_CFRG_Selecting_Elliptic_Curves_for_Cryptography.pdf

-- 
Viele Grüße,
Johannes Merkle

---

From: Rob Stradling <[email-masked]>
Date: Thu, 23 Oct 2014 11:43:46 +0100

> Why not secp256r1? (I'm guessing the big reason was because the TS profile required ≈WF192 and you wanted one root to be suitable for both profiles if you could?)

That was certainly part of the reason.  The other part was that a 
competitor had already chosen secp384r1, so it seemed safest to follow 
suit.  :-)

> It's a bit early to say, but (open question to all) if we picked one curve at ≈WF128, would you in principle be comfortable with having roots of that strength?

In principle, yes, but...

> What about if we picked two: one fast secure curve at 128 and one at some higher "paranoid" grade (be it 384, 448, 480, 512, 521, 607...)? Which would you perhaps consider using when? Would you hav…

I'm inclined to agree with my colleague PHB, who wrote recently:
"The Web PKI will almost certainly be based exclusively on the ~512
level curve. The roots certainly will."

The various browser root programs place limits on the total number of 
roots per CA.  So whilst a ≈WF128 root could be useful, I think there's 
a very good chance that we won't have the option to embed both ≈WF128 
and ≈WF<paranoid> roots.

> What kinds of things would you need to be able to have such a root? I'm guessing, bringing it back home to the weekly topic, that 'high-assurance' crypto hardware of some form would be highly desir…

Yes, we would need at least one HSM that can generate keys and 
signatures on the new curves.  The speed of the implementation won't 
matter much.  If the new curves are to be used with ECDSA (unlikely?) 
then I think it might even be possible to persuade existing HSMs to do 
the job.  PKCS#11 supports ANSI x9.62 "EC domain parameters" as well as 
named curves, for example.

> I say this because I don't think the initial target market for these new curves necessarily includes those mandated to use Suite B (although never say never!), I don't think government approval wil…

Agreed.

> -----BEGIN PGP SIGNATURE-----
> Version: APG v1.1.1
>
> iQI3BAEBCgAhBQJURQiIGhxBbHlzc2EgUm93YW4gPGFrckBha3IuaW8+AAoJEOyE
> jtkWi2t6lFAP/04NXnjKWHI34cZ2OYIs+qCP4q35hKFvbtAX+7MECPmlF+4lrpbS
> /Hzu8bjjsLVphsTWbXo8bW7sXCLWzHGkcL4QuvZM56ArngvP17EK3tZIgkFiOjKY
> D+hlGskjcAgXDhRvyaEvimuUHQ9BVWmGft0XPnMSucBckq634Bbw3VSdzhq+0yAV
> 5awXzKeTkrI9sYrwSXZ/P9TN/ejVjfI0t3KU+RxdMPWTY8psbmXsuaMT8ny4EkOi
> PhskwFNb5rndfRBEq/rnenhXAgTnUJVf51vBhU8YOKZLy2NojcZ2Wjy5YOQuDepQ
> GE3phWRqxCA4hnhbnNHcguxnlh5B6y5OzEYd/9/Iaia/brj7H3eYvc84RnG1H9Fl
> VTkBrAZUUmtcmdnTlNnEBQQ/pmSlGWZsIhLYPueXD43yAggMvP8YffURKADFfm6J
> Om5BmI2JVWjFpDjQA7e9NKL6niTJUccqUkHNjm54wEwIuh0zcKJCBzZ4P4cUU+vk
> T5BDy3AoVLFT9uVOXV/vXkTA3xcOtlLaUgnTa3CzRR9IuoIewPncK1MurP6I37jA
> XzcupAFmTgiDcITjKAm2xzaVzJwWByBbtuvaMBKRFbA1UK++y9/YWnhalwsEmNYf
> lo5LnvTuJa/SvmPcpLHqtqeTIIV3rWVdn5GVbZOx5jxao5KK19b/7kMF
> =tB0e
> -----END PGP SIGNATURE-----
>

-- 
Rob Stradling
Senior Research & Development Scientist
COMODO - Creating Trust Online
Office Tel: +44.(0)1274.730505
Office Fax: +44.(0)1274.730909
www.comodo.com

COMODO CA Limited, Registered in England No. 04058690
Registered Office:
   3rd Floor, 26 Office Village, Exchange Quay,
   Trafford Road, Salford, Manchester M5 3EQ

This e-mail and any files transmitted with it are confidential and 
intended solely for the use of the individual or entity to whom they are 
addressed.  If you have received this email in error please notify the 
sender by replying to the e-mail containing this attachment. Replies to 
this email may be monitored by COMODO for operational or business 
reasons. Whilst every endeavour is taken to ensure that e-mails are free 
from viruses, no liability can be accepted and the recipient is 
requested to use their own virus checking software.

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 23 Oct 2014 15:01:40 +0300

> 1. Amount of "wiggle room" that should be permitted.

Barring unforseen new way to implement base field math, there will
not be much wiggle room if performance is important consideration
and curve parameters are choosen minimally.

Heck, just see the amount of problems trying to find truly high-
performance curve near 384 bits.

> 2. A more nuanced set of hardware requirements.

Quite blunt, but: Hardware implementations are no consideration.

Why:
- This is for IETF TLS, and vast majority of endpoints are software.
- Software-optimized curves are not too bad for most hardware.
- And if they are too bad for some specialized kind of hardware,
  there already are more suitable curves in TLS.
- The kind of hardware needing such curves should not be
  contacting random peers, so making those peers capable of
  dealing with the necressary curves is feasible.

-Ilari

---

From: Watson Ladd <[email-masked]>
Date: Thu, 23 Oct 2014 07:27:08 -0700

On Thu, Oct 23, 2014 at 3:43 AM, Rob Stradling <[email-masked]> wrote:
>>> When we generated our ECC root CA keys in 2008, secp384r1 seemed like the
>>> best choice.  secp521r1 wasn't in Suite B, and it seemed likely that Suite B
>>> compliance would be a requirement for some of our customers.
>>
>>
>> Why not secp256r1? (I'm guessing the big reason was because the TS profile
>> required ≈WF192 and you wanted one root to be suitable for both profiles if
>> you could?)
>
>
> That was certainly part of the reason.  The other part was that a competitor
> had already chosen secp384r1, so it seemed safest to follow suit.  :-)
>
>> It's a bit early to say, but (open question to all) if we picked one curve
>> at ≈WF128, would you in principle be comfortable with having roots of that
>> strength?
>
>
>> What about if we picked two: one fast secure curve at 128 and one at some
>> higher "paranoid" grade (be it 384, 448, 480, 512, 521, 607...)? Which would
>> you perhaps consider using when? Would you have one root at each level, or a
>> shared root at the paranoid level?
>
>

Previously, when given a choice of curves, the one with size 384 or
thereabouts was picked. Now you are saying you want the biggest
possible curve, regardless of the performance impact. I've heard
complaints that P384 is already painfully slow to verify on mobile.
It's a lot more sensible to pick Goldilocks: just as fast as what you
have now, but a few hundred bits bigger.

If you really needed 512, you would have already done it. So the fact
that you haven't tells me that you don't actually need a 512 or 521
length root key and are perfectly fine with anything above 384 in
length. The performance of verification is an issue for some clients
already: we don't need to make it worse.

>
> The various browser root programs place limits on the total number of roots
> per CA.  So whilst a ≈WF128 root could be useful, I think there's a very
> good chance that we won't have the option to embed both ≈WF128 and
> ≈WF<paranoid> roots.
>
>> What kinds of things would you need to be able to have such a root? I'm
>> guessing, bringing it back home to the weekly topic, that 'high-assurance'
>> crypto hardware of some form would be highly desirable for that. But what
>> does that mean to *you*?
>
>
> Yes, we would need at least one HSM that can generate keys and signatures on
> the new curves.  The speed of the implementation won't matter much.  If the
> new curves are to be used with ECDSA (unlikely?) then I think it might even
> be possible to persuade existing HSMs to do the job.  PKCS#11 supports ANSI
> x9.62 "EC domain parameters" as well as named curves, for example.

There is a technical issue here. While you could express the curve in
Weierstrass form for signatures, that won't give the same results as
using Edwards form. So if you wanted to reuse HSMs, that means that we
would need to have Weierstrass form keys for signing, and would need
to continue the use of a signature algorithm that isn't batchable and
is painful because it requires arithmetic modulo the group order.

How long do you think it would take to make an HSM that supports our
choice? Is this a matter of grab an ARM chip, add some custom
firmware, bypass caps, and epoxy (say ~ 6 months), or is it a more
involved process?

(I'm also unsure of how ECDSA handles cofactors. Will check this)
>
>> I say this because I don't think the initial target market for these new
>> curves necessarily includes those mandated to use Suite B (although never
>> say never!), I don't think government approval will drive adoption this
>> time, and also the assurances people ask of Web PKI CAs in particular seem
>> to be strengthening considerably relative to where they were (cf:
>> Certificate Transparency, et al).
>
>
> Agreed.
>
>>> TLS clients commonly don't specify RSA/SHA-512 and ECDSA/SHA-512  in the
>>> TLS signature_algorithms extension.  Some servers respond by refusing to
>>> serve certs with SHA-512 signatures.
>>
>>
>> Thanks for that note. The TLS WG and user-agent participants should
>> probably bear this in mind, down the line, if whatever we come up with is to
>> be accepted and used.
>>
>> - --
>> /akr
> This e-mail and any files transmitted with it are confidential and intended
> solely for the use of the individual or entity to whom they are addressed.
> If you have received this email in error please notify the sender by
> replying to the e-mail containing this attachment. Replies to this email may
> be monitored by COMODO for operational or business reasons. Whilst every
> endeavour is taken to ensure that e-mails are free from viruses, no
> liability can be accepted and the recipient is requested to use their own
> virus checking software.
>
>

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 23 Oct 2014 10:43:21 -0400

On Thu, Oct 23, 2014 at 6:43 AM, Rob Stradling <[email-masked]>
wrote:

>> Why not secp256r1? (I'm guessing the big reason was because the TS
>> profile required ≈WF192 and you wanted one root to be suitable for both
>> profiles if you could?)
>>
>
>  It's a bit early to say, but (open question to all) if we picked one
>> curve at ≈WF128, would you in principle be comfortable with having roots of
>> that strength?
>>
>
>> higher "paranoid" grade (be it 384, 448, 480, 512, 521, 607...)? Which
>> would you perhaps consider using when? Would you have one root at each
>> level, or a shared root at the paranoid level?
>>
>
> roots per CA.  So whilst a ≈WF128 root could be useful, I think there's a
> very good chance that we won't have the option to embed both ≈WF128 and
> ≈WF<paranoid> roots.

Just to clarify here since the nomenclature tends to switch between WF and
bits.

I think we will end up at 512 bits which is actually rather more than
 ≈WF256 but is considered ≈WF256 because the rule of thumb is to halve.

Perhaps if we call it P512?

Marketing might seem a trivial issue but what we are talking about here is
how do we make the ECC story an easy one to explain to the non technical
and how do we come to one choice for the industry that has a good chance of
sticking.

I can form a really good argument for P512 and either P256 or P255 that
won't get any objections from the non-technical and the only complaints
from technical folk will be on performance grounds:

* WF 128 is generally considered to be sufficient unless the algorithm
itself is compromised by a new attack

* WF 256 is the largest work factor currently supported by industry
standard algorithms.

* P256 is a very round number
* P255 is almost P256 and can be considered an established algorithm

* The field has generally favored bit sizes that are a power of 2. Using
powers of 2 provides maximum compatibility with general purpose hardware
which has progressed from 8 to 16 to 32 to 64 bits for general arithmetic
operations with some architectures supporting 128 bit floats and 512 bit
integers. Data paths are up to 512 bits.

* Going just above a power of 2 means a more complicated implementation. In
particular code optimizations are now different depending on whether we are
on a 32 or 64 bit machine.

If we get into discussion of performance then we are on a slippery slope.
We have admitted that we are accepting a tradeoff for a start. And we have
to explain that it is the work factor ratio that is important and all sorts
of things.

The objective here is to arrive at a set of curves that everyone is
confident are secure and do not appear to be odd in any way.

Curve 255 is being widely used because the implementation is so short, the
speed is probably secondary.

To implement P512 fast I would write a 512 bit fixed size bignum library.

To implement P521 fast I would have to write a 544 or 576 bit bignum
library depending on the architecture.

Those 9 extra bits are actually a heap of extra complexity.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 23 Oct 2014 11:09:16 -0400

On Thu, Oct 23, 2014 at 10:27 AM, Watson Ladd <[email-masked]> wrote:
> would

That really depends on your mobile. Whatever numbers are picked there will
always be a significant number of devices being made that are not suited to
doing repeated public key operations. There are more 8 bit devices being
made today than at any time in the past.

But equally important, nobody is looking at ECC as a fast alternative to
RSA2048 in consumer oriented devices any more. Commodity processors are
cheap enough and low power enough to do RSA2048 without breaking sweat.

> already: we don't need to make it worse.

We don't really 'need' ECC at all. Unless something happens to RSA2048 that
is unexpected, TLS is almost certainly fine for quite a few years yet.

Given the mess the NSA has created here, we have to put clear water between
our new curves and the old. It is not enough for me to be satisfied that
the system is secure. Its the general Internet population that has to be
confident that they are safe from having their crypto cracked.

> firmware, bypass caps, and epoxy (say ~ 6 months), or is it a more

Vastly more involved and producing the hardware and software for the HSM is
at most 25% of the effort required.

The requirement is for a certified HSM, not just something that we are
confident is secure. This is an area where we are likely to require
assistance from NIST because they have the only widely used certification
program.

As a practical matter it is much easier for the NIST people to add a new
512 bit curve to their stable than to add in an additional 384 curve whose
advantage over the previous curves is being demonstrably free of perfidy by
NIST.

---

From: Alyssa Rowan <[email-masked]>
Date: Thu, 23 Oct 2014 18:41:05 +0100

On 23/10/2014 15:27, Watson Ladd wrote:

>>  "The Web PKI will almost certainly be based exclusively on the 
>> ~512 level curve. The roots certainly will."
> possible curve, regardless of the performance impact.

Not wishing to speak for Rob, but what I _think_ he means here is simply
that if there was one curve picked, he'd use it in principle; but given
the choice between two curves (a strong fast curve, and a paranoid
curve), he'd probably be tempted to go for the paranoid one for the roots?

Seems sensible to me: they're the Web PKI roots, after all. They're much
longer-lived signing keys than servers, and they will in practice be
under sustained, well-funded attack from nation state adversaries. Under
those circumstances, the more paranoid level may seem appropriate, but a
server key would probably far rather plump for the strong fast curve.

I echo your concerns about verification performance and secp384r1, but
that _is_ a particularly ugly baby. We can do better than that, even if
we pick a curve which is more secure, which is indeed the selling point
of Curve41417 and/or Ed448-Goldilocks. (I actually wonder how a
well-optimised E-521 would do, even. I guess we'll find out.)

Future reference note: May be useful to have state-of-the-art
implementations of NIST secp256r1, NIST secp384r1, NIST secp521r1 in the
performance shootout as anchors?

The way the sign/verify workload is on ECDSA works out well for many
servers (where sign's the bottleneck) but it's a little unfortunate for
roots (where verify is).

> How long do you think it would take to make an HSM that supports 
> our choice?

Depends: from what I've seen a few HSMs are flexible enough to run
whatever we choose. (I'll refrain from discussion of specific vendors:
it is for them to speak up if they wish.)

By the way, as a matter of practicality, would we perhaps be looking at
some kind of hybrid transition period where existing ECDSA-P384-SHA384
roots sign (purely by way of example) EdDSA-Curve25519-SHA512 end-entity
certificates? How would the choice of end-entity algorithms be
restrained by the signing algorithms and curves used on the roots, or
not? (I appreciate that may not really be a question for here, but for
upstream in TLS or PKIX.)

> Is this a matter of grab an ARM chip, add some custom firmware, 
> bypass caps, and epoxy (say ~ 6 months), or is it a more involved 
> process?

Yes, you _could_ indeed do that. It depends what you want out of it;
whether that's a _good_ approach is another question entirely. (Epoxy
doesn't really do a lot of good, by the way! <g>)

But it's _certifying_ one that's the ridiculously involved process, as
Philip raises. The big challenge in making a commodity security
device today is not cryptography, but bureaucracy!

However, I have an inkling that those who mistrust the NIST curves may
not entirely trust the NIST certifications for _exactly_ the same
reasons - so in practice, I wonder about its actual relevance, or the
relevance of other certifications. (Besides, we're not picking
NIST-approved curves here.)

Transparency and open verifiability will probably be way more important
in practice to what we're doing here than any government/other existing
certifications. An openly-verifiable HSM would be highly desirable.

> (I'm also unsure of how ECDSA handles cofactors. Will check this)

I think djb posted about that one?

Picking a new curve but using an old, relatively-fragile signature
scheme when we know we could do better and safer now that the Schnorr
patent expired seems a little silly to me, too. That's a discussion for
a future date, however.

- -- 
/akr

---

From: Andy Lutomirski <[email-masked]>
Date: Thu, 23 Oct 2014 10:49:17 -0700

> it is for them to speak up if they wish.)

This seems like a good time to point out that Intel SGX is coming
soon.  With SGX, some performance-critical HSM applications could be
replaced with hardware-assisted secure *software* enclaves on
supported Intel chips.

For this application, the relevant factors will be software speed
(because it's just x86 software), freedom from timing attacks, and
freedom from secrets being leaked in memory access patterns.

Some users might require certification, but there will be no
additional hardware development effort whatsoever to add new curves.

--Andy

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 23 Oct 2014 14:17:35 -0400

> additional hardware development effort whatsoever to add new curves.

And the AVX-512 extensions provide 512 bit native registers.

I don't think it very likely we can persuade any chip vendor to lay down
extra signal lines for 521 bits and if they did a 1024 bit data path we
would be looking at using all of it, not just 9 extra bits.

256 and 512 bit wide paths are already starting to appear of their own
accord as a multipurpose feature.

---

From: Andy Lutomirski <[email-masked]>
Date: Thu, 23 Oct 2014 11:22:02 -0700

> And the AVX-512 extensions provide 512 bit native registers.

I feel like you're arguing against a straw man here.  Unless I
misunderstand, the fastest implementations of 512-bit curves don't fit
in 512-bit registers either.

Ed448-goldilocks, on the other hand, might.  Mike?

> would be looking at using all of it, not just 9 extra bits.

Wait, what?  Are you suggesting using primes closer to 1024 bits?
That seems even more excessive that 512 or 521 bits.

--Andy

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 23 Oct 2014 22:28:01 +0300

> And the AVX-512 extensions provide 512 bit native registers.

Those are vectored registers. The widest multiply appears to be
64x64->128.

Even if 2^512-569 seems like it fits into 8x64 bits, unless you have
good carry handling (you don't for SIMD on Intel CPUs), you need 9x64
bits for optimal speed.

Now, the 9x64 bits could also store 2^521-1 (or 2^522-2), which have
faster reductions due to constant being small and power of two (or 1).

This explains why 2^521-1 is faster than 2^512-567, despite having to
do 9 extra bits and seemingly break word boundary.

Similarly, current fastest implementations for Curve25519 use 5x64
bits, not 4x64 bits.

-Ilari

---

From: Michael Hamburg <[email-masked]>
Date: Thu, 23 Oct 2014 13:14:05 -0700

> On Oct 23, 2014, at 11:22 AM, Andy Lutomirski <[email-masked]> wrote:
> 

We don’t actually have alternative implementation of NUMS p512, so it’s hard to conclusively say that a 9x57 implementation will be faster, but it seems reasonably likely.

Goldilocks should work well in 512-bit registers.  If Intel has single-cycle PMUL[U]DQ on 512 bits, that will become the largest multiplier on the chip: 8x32x32 -> 8x64 compared to the 64x64->128 scalar multiplier.  The ARM NEON Karatsuba implementation should translate pretty well to that primitive, but the devil is in the details.

On the other hand, Broadwell is slated to introduce ADCX/ADOX scalar carry-handling primitives which should mitigate some of the carry handling issues for packed NUMSp512 math.  It probably won’t be as big a difference as AVX-512, but it’s something.

@PHB: How much experience do you have actually implementing elliptic curves or similar primitives?  You have an awful lot to say about why 512 will be fast in the long run, and I’m curious where that comes from.  Is it “just common sense”, or have you done experiments?

— Mike

---

From: Rob Stradling <[email-masked]>
Date: Thu, 23 Oct 2014 21:43:50 +0100

> curve), he'd probably be tempted to go for the paranoid one for the roots?

Yes.

<snip>
> certificates?

Either that or existing RSA roots cross-certifying next generation ECC 
roots.

> How would the choice of end-entity algorithms be

Not.

BTW, we're in a hybrid transition period at the moment: our 
ECDSA-P384-SHA384 roots are cross-certified by our old RSA roots.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 23 Oct 2014 16:52:13 -0400

On Thu, Oct 23, 2014 at 4:14 PM, Michael Hamburg <[email-masked]> wrote:

> Goldilocks should work well in 512-bit registers.  If Intel has
> single-cycle PMUL[U]DQ on 512 bits, that will become the largest multiplier
> on the chip: 8x32x32 -> 8x64 compared to the 64x64->128 scalar multiplier.
> The ARM NEON Karatsuba implementation should translate pretty well to that
> primitive, but the devil is in the details.
>

OK so that is an important data point.

What I am trying to get to here is to get people to explain those details
in terms more abstract than 'I ran X on Y and got time Z'.

On the other hand, Broadwell is slated to introduce ADCX/ADOX scalar
> carry-handling primitives which should mitigate some of the carry handling
> issues for packed NUMSp512 math.  It probably won’t be as big a difference
> as AVX-512, but it’s something.
>

Thats the point, if there is a 512 bit wide register and there is an
application that can be accelerated if 512 wide instructions are available
there is a reasonable expectation that we can get them implemented.

Adding in a Manchester carry chain isn't a big cost, nor is providing a
primitive for a fast 512 bit multiply. 512 bit multiply

> @PHB: How much experience do you have actually implementing elliptic
> curves or similar primitives?  You have an awful lot to say about why 512
> will be fast in the long run, and I’m curious where that comes from.  Is it
> “just common sense”, or have you done experiments?
>

Having built large parallel machines and used them for very large tasks, I
am going by a little more than common sense. 512 bit arithmetic operations
are certainly going to be faster than 521. Now what that implies for
implementing
Knotted Weierstrass curves with a double Irish Dutch sandwich or whatever
is what I am looking for an explanation of in terms that I can explain to
the general security community.

What I began arguing is that 521 is going to break stride on a 512 bit
architecture and should be taken off the table unless the speed advantage
is enormous. I don't think we need to implement the algorithm to see that.

Now if you are arguing that 512 will also break stride on a 512 bit
architecture then that is an important data point that by the same logic
argues for looking at a curve that does fit and maybe Golilocks is actually
the one.

But before conceding that point I would like to see more of an explanation
of the optimization being used and how much it delivers.

---

From: Andy Lutomirski <[email-masked]>
Date: Thu, 23 Oct 2014 13:58:40 -0700

On Thu, Oct 23, 2014 at 1:52 PM, Phillip Hallam-Baker
<[email-masked]> wrote:
> Knotted Weierstrass curves with a double Irish Dutch sandwich or whatever is
> what I am looking for an explanation of in terms that I can explain to the
> general security community.
>
>
> architecture and should be taken off the table unless the speed advantage is
> enormous. I don't think we need to implement the algorithm to see that.
>

I'm really having trouble understanding what you mean by "break
stride".  I doubt that any implementation of any of these algorithms
is even close to fast enough that the time it takes to shove data
across the bus is relevant.  If someone really builds special-purpose
ASICs for this, they they can presumably back a 521-bit register (or
any other size register) by a far smaller bus and get excellent
performance.

--Andy

---

From: Watson Ladd <[email-masked]>
Date: Thu, 23 Oct 2014 14:43:38 -0700

This is wrong. Many vector units operate on two independent halves
internally, introducing an extra delay for any operation that crosses the
halves. Furthermore, maximal gate delay times force strict limits on
circuit depth.

ADOX, ADCX, and MULX are nothing special in comparison.  They use existing
hardware in slightly nicer ways. The carryless multiply and AES
instructions are much more similar to what you propose, and took a long
time to get into silicon. Even then the multiply instruction was a
sixteenth of the size of what you propose.

>
>
> Having built large parallel machines and used them for very large tasks,
I am going by a little more than common sense. 512 bit arithmetic
operations are certainly going to be faster than 521. Now what that implies
for implementing

But it impacts performance in ways that don't show up in benchmarks. If you
think 512 can go faster, roll up your sleeves and send it to SUPERCOP. If
what you want is hardware support, you will have to explain why it hasn't
already happened.

If you want to say performance doesn't matter, and the prime picking we use
isn't rigid enough, make that argument.  But don't say "this is faster"
when the benchmarks say otherwise.

Sincerely,
Watson Ladd
>
> But before conceding that point I would like to see more of an
explanation of the optimization being used and how much it delivers.

---

From: Samuel Neves <[email-masked]>
Date: Thu, 23 Oct 2014 23:21:59 +0100

> Goldilocks should work well in 512-bit registers.  If Intel has single-cycle PMUL[U]DQ on 512 bits, that will become the largest multiplier on the chip: 8x32x32 -> 8x64 compared to the 64x64->128 s…

AVX-512 has better than VPMUL[U]DQ. Not only does AVX-512* have VPMULLQ (64x64->64), which is useful on its own, but
also VPMADD52{L,H}UQ, which does a 52-bit multiply followed by a 64-bit addition of either the lower or upper 52 bits of
the product. This latter instruction seems to expose the floating-point circuitry to the user.

* The fancy version of AVX-512, expected to be in Skylake; Knight's Corner only has a limited subset named AVX-512F.

---

From: Michael Hamburg <[email-masked]>
Date: Thu, 23 Oct 2014 16:14:35 -0700

> On Oct 23, 2014, at 3:21 PM, Samuel Neves <[email-masked]> wrote:
> 

Oh, huh, that’s pretty neat.  At first glance, it looks like it’d be most useful for an implementation of a 384-bit prime with radix 2^48.

Curve41417 or a curve over 2^416-2^208-1 would also work with radix 2^52 (since 8*52 = 416), but you’d have to reduce almost completely before multiplying which would offset the gains.

A final possibility is that since the register file of AVX512 is gi-freaking-normous, you could try to do 2-4 multiplies at a time using the extended addition formula.  Then you wouldn’t have to worry as much about the 416-bit input size of this operation, and it would be easier to apply to other primes.

— Mike

---

From: Michael Hamburg <[email-masked]>
Date: Thu, 23 Oct 2014 20:27:03 -0700

> On Oct 23, 2014, at 1:52 PM, Phillip Hallam-Baker <[email-masked]> wrote:
> 
> Now if you are arguing that 512 will also break stride on a 512 bit architecture then that is an important data point that by the same logic argues for looking at a curve that does fit and maybe Golilocks is actually the one. 
> 
> But before conceding that point I would like to see more of an explanation of the optimization being used and how much it delivers. 
> 

I really ought to write this up in a proper paper.  But here’s a sketch.

First of all, many modern implementations use reduced-radix arithmetic.  So curve25519-donna uses 5x51-bit words, and ed448-goldilocks uses 8x56-bit words, or 16x28-bit words on 32-bit platforms.  Let’s consider Goldilocks on 64-bit.

The multiply routine can accumulate several 112-bit products in a 128-bit register pair without carrying.  This is important because carry handling slows you down even on x86-64 and arm-scalar.  It’s even more important with vector units such as NEON, because carry handling is much slower when you have to exchange elements between vectors.  The 448-bit size is chosen so that the whole multiply routine can run on a 32-bit platform (like NEON) without propagating any carries until the end.  For a 64-bit platform, there’s more headroom and fewer multiplies in that routine, so the next prime up in the family (2^480 - 2^240 - 1, “Ed480-Ridinghood”) could be used instead.  But I wanted to ensure that NEON would be fast, so I went with 448.  Conveniently, at this size the working state for a multiply fits exactly in the NEON register file.

Reduced radix also speeds up addition and subtraction, which can now be vectorized.  With too many additions or subtractions, you’ll need to reduce to avoid overflow (conservatively, of course, since you can’t usually check in constant-time software).  But in the “hot” routines like point additions, most numbers only go through at most one addition or subtraction before being multiplied.  So they don’t need to be reduced if the multiply routine has a little extra slack.  For Goldilocks, this is true on 64 bit.  On 32-bit, there’s enough slack for an addition in each multiplicand, but not for two subtractions unless the implementation uses signed numbers (which it currently doesn’t).  So it’s on the edge with a small performance penalty for reductions, and could probably be tuned a bit more.

OK, so that’s one reason that the prime is less than 512 bits: it’s designed to be represented internally in 512 bits, but some of those bits are headroom for carries.  It’s probably the biggest prime that can do this on a 32-bit machine.  (The biggest such “Crandall” prime is DJB's 2^414-17.)

The other main design point is the “golden Solinas” form p = t^2 - t - 1, where t = 2^224.  I’m calling it “golden” (and Goldilocks) because t is the golden ratio mod p.  This is a Solinas trinomial, the sparsest kind of prime except for Mersenne primes like 2^521-1.  The NIST curves taught us a lesson about Solinas primes: they can be fast, but the coefficients are constraining.  Since most of the NIST primes have lots of 32-bit aligned coefficients, they suck on 64-bit machines and prevent you from reducing the radix to eg 28 bits.

The Goldilocks prime mitigates that problem by having only one coefficient, right in the middle.  So if you are representing your numbers in an even number of words, reduction is really simple.  This makes any word size favorable if it is equal to (full radix) or slightly less than (reduced radix) a divisor of 448/2: [1, 2, 4, 7, 8, 14, 16, 28, 32, 56, 112, 224].  So while it doesn’t work perfectly on every word size, it should work well on full-radix 16, full- or reduced-radix 32, or full-radix 64-bit machines.  Many of the options involve 2^n limbs in reduced-radix mode, which vectorizes really well.

In short, because it’s a Solinas trinomial, p has the second most efficient reduction algorithm after Mersenne primes.  You don’t get quite as many choices of efficient word layout as with a Crandall prime 2^big - small (which has no internal coefficient), but the golden-ratio structure is pretty much the best you can get on a Solinas prime.

There are only a few options for bit lengths of primes of this shape.  The crypto-sized ones are 216, 322, 416, 448, 450 and 480.  Note also that 2^448 - p ~ sqrt(p).  So security issues such as biases from not being really close to a power of 2 are always less than 1/sqrt(p), which is your security target anyway.  Likewise, the curve’s order will look basically the same as for a Crandall prime.

There’s one more advantage to the golden-ratio structure.  The Goldilocks prime works very well with Karatsuba multiplication.  Recall that Karatsuba computes (a + bt) (c + dt) = ac + bdt^2 + ((a+b)(c+d)-ac-bd)t, where t is either a polynomial term or a multiple of the word size.  So it saves one multiplication at the cost of several additions.  This is usually combined with reduced-radix math so that you don’t have to handle carries in (a+b) and (c+d).

Let t = 2^224, so that t^2 = t+1 mod the Goldilocks prime.  Reducing the above, (a+bt)(c+dt) == ac + bd + ((a+b)(c+d)-ac)t.  That is, reduction mod p makes the Karatsuba formula slightly simpler instead of more complex.

The products above — ac etc. — will be wider than t, and so will also need to be reduced.  So it’s also important that this formula multiplied by t is also simple:

(a+bt)(c+dt)t = (a+b)(c+d)(1+t) + bdt - ac.

The actual math code uses variants of these formulas depending on the platform, for better locality or pipelining or whatever, but the basic idea is the same.  Since a and b are 4x56-bit numbers, they can be added with a single 4-lane vectorized add; likewise for c and d.  All in all, this Karatsuba technique may or may not be profitable on AVX-512, but it is definitely profitable on x86-64 and NEON.

So for example, on a 64-bit machine, the Goldilocks field multiply uses approximately:
* 2x4x64-bit vector adds
* 5 widening multiplies and 43 multiply-accumulates
* 5 128-bit additions and 4 128-bit subtractions
* Two final 64-bit for a total of about 54 ADD/SUB and 52 ADC/SBB.  I’m not looking at asm though, so I probably missed some.
* 10 radix adjustments (mask and shift a 128-bit variable).

The multiplies are easy to interleave at different place values, because carries don’t propagate.  This improves performance noticeably on some platforms.

Without Karatsuba, you’d need at least 64 multiply-accumulates.  Or with packed math at this size, you’d need 49 multiplies (48 accumulates), but the accumulates would be wider, 192 bits, and thus much slower.

A Goldilocks add takes:
* 2x4x64-bit vector adds
It should be done in a few cycles, maybe less if it’s inline.

By comparison, a 512-bit packed multiply (Comba like in MS NUMS) uses:
* 1 widening multiply
* 3 64x64->128-bit multiply-accumulates
* 60 64x64->192-bit multiply-accumulates, if I’ve calculated right 
* 8 small multiply-accumulates (64x64->128 bits) for reduction
* at least one, maybe two rounds of carry propagation after the reduction

This comes out to order of 80 ADD and 140 ADC instructions.  Remember that MUL isn’t that much more expensive than ADC on recent Intel cores, and even on AMD it’s only twice as expensive.  It’s still possible to interleave the multiplications, but it’s trickier because of carry propagation.

Some platforms have faster carry propagation, including ARM scalar (UMAAL) and the upcoming Intel Broadwell (MULX/ADCX/ADOX).  But usually vector units don’t have this, and ARM's NEON vector unit is a huge win — like triple the performance — if you can use it efficiently.

A packed NUMSp512 add takes:
* one add
* 7 adds with carry in a chain
* a multplication for the reduction
* probably two rounds of carry propagation

This sort of carry propagation is most of why NUMSp512 takes about twice as long as Goldilocks.

Overall, these optimizations give a curve which is 64 bits longer than NUMS p384 with <10% worse performance, and 64 bits shorter than NUMS p512 with about double the performance.  So if you mock up an “efficiency” metric which trades off bit length for speed, Goldilocks scores very well.  Its main competitors in this region would be its 480-bit cousin (but not on 32-bit), or 2^521-1, which I still think is pretty good despite your criticism.

There are other families of fast primes, as outlined in my email on prime performance, but at a size of “between about 384 bits and about 512 bits”, Goldilocks is one of only a few really good ones.

Cheers,
— Mike

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 24 Oct 2014 14:37:18 +0300

> well-optimised E-521 would do, even. I guess we'll find out.)

There's also 416-bit prime equally fast to Ed448 prime (-> ~7% faster
scalarmult for 16 less bits of security).

> performance shootout as anchors?

I think definitely so. I would set CPU budget for high curve at secp384r1.

This should give at least ~190 bits of security, possibly >200.

> servers (where sign's the bottleneck) but it's a little unfortunate for

Simple idea: One could cache CA certificate validations (and also sites
using exceptionally long keys).

There shouldn't be THAT many CA certificates out there in open internet
for that to be a serious storage challenge. And while there are undoubtedly
more in private, one typically does not see very much of those.

> upstream in TLS or PKIX.)

I think this is technically possible (dunno if it is a good idea).

> doesn't really do a lot of good, by the way! <g>)

E.g. doesn't stop EM attacks. And apparently even if software is hardened
against software attacks, it tends to be rather vulernable to EM attacks.

I would imagine such software would be written to apply heavy blinding,
at great cost for signing time. But such signing doesn't occur that
often.

> patent expired seems a little silly to me, too. That's a discussion for

Heck, there are even older signature schemes that are easier
(no need for private inversion when signing).

-Ilari