Subject: Re: [Cfrg] new curves or old (was: Actual security levels for IETF crypto)

From: "Dan Harkins" <[email-masked]>
Date: Sun, 2 Nov 2014 00:13:42 -0700 (PDT)

On Fri, October 31, 2014 10:34 am, Paterson, Kenny wrote:
> Hi
>
> We could still go down the route of generating fresh curves if there's
> consensus for it on the list.
>
> So let's do a quick poll:
>
> - Who on the list would be in favour of using a to-be-agreed procedure to
> generate new curves, instead of selecting from amongst the curves that are
> currently on the table?
>
> (Keeping in mind that this may induce negative performance impacts, but
> could increase confidence in the outcome of our deliberations.)
>
> Replies should being with a one-word answer - "yes" or "no".
> Justifications for positions can be included if you wish, but right now
> I'm more interested in the raw, 1-bit answer.

  No. I'd actually be happy if we just chose E-521 and declared victory.

  Dan.

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Sun, 02 Nov 2014 14:06:18 +0100

On 31/10/2014 19:56, Yoav Nir wrote:
> 
>> On Oct 31, 2014, at 8:18 PM, Alyssa Rowan <[email-masked]> wrote:
>>
>>> - Who on the list would be in favour of using a to-be-agreed procedure to generate new curves, instead of selecting from amongst the curves that are currently on the table?
>>
>> No.
>>
>> • If we generated new curves with rigid processes and constraints, they'd likely match one of the contenders. (That's the point. See what happened with E-521.)
>>
>> • I think the already-existing Brainpool curves match random curve criteria fine.
>>
>> • Concerns about delay.
>>
>> There's nothing stopping us (or Brainpool) doing new random curves later, but I don't think this satisfies the TLS WG request on the table now.
> 
> +1. No.
> 
> I totally trust the Brainpool people to have picked the curves correctly and randomly. No reason to do it again.
> 
> The NUMS people have (I’m sure) done a fine job of doing the rigid process, and I don’t think we’ll come up with better rigid criteria unless we tailor the criteria to get a particular curve.
> 
> It’s time to do what IETF and IRTF usually do poorly - decide among several options, each with advantages and disadvantages.
>
No, and +1 on all points raised by Alyssa and Yoav (below).

Also, if Brainpool wants to generata a new set of VPR curves, I don't think they
need the CFRG for that, so the CFRG should rather concentrate on answering the
request from the TLS WG, and without additional delay.

Manuel.

---

From: "Nguyen Dr., Kim" <[email-masked]>
Date: Sun, 2 Nov 2014 22:34:04 +0100

I agree with Paul here, taking into account a variety of market applications
both from server as well as embedded view point is valuable.

So, my vote is a Yes.

Kim

Dr. Kim Nguyen

D-Trust GmbH

Geschäftsführer / Managing Director

Technology

Chief Scientist Security

-----------------------------------------------------------------------

Bundesdruckerei GmbH

Oranienstrasse 91 

10969 Berlin

GERMANY

D-Trust GmbH

Kommandantenstr. 15

10969 Berlin 

GERMANY

Phone:  + 49 (0) 30 - 2598-1194

Mobile: + 49 (0) 171 5641 909

Fax:    + 49 (0) 30 - 2598-6165

 <mailto:[email-masked]> [email-masked]

 <http://www.bundesdruckerei.de/> www.bundesdruckerei.de

Sitz der Gesellschaft: Berlin

Handelsregister: AG Berlin-Charlottenburg  HRB 80443.   Ust.-IdNr.:    DE
813210005 

Aufsichtsratsvorsitzender: Willi Berchtold

Geschäftsführer: Ulrich Hamann (Vorsitzender), Christian Helfrich

This message is intended only for the use of the individual or entity to
which it is addressed, and may contain information that is privileged,
confidential and exempt from disclosure under applicable law. If the reader
of this message is not the intended recipient, or the employee or agent
responsible for delivering the message to the intended recipient, we hereby
give notice that any dissemination, distribution or copying of this
communication is strictly prohibited. If you have received this message in
error, please delete the message and notify us immediately.

 

Von: Cfrg [mailto:[email-masked]] Im Auftrag von Paul Lambert
Gesendet: Freitag, 31. Oktober 2014 18:5
An: Paterson, Kenny
Cc: [email-masked]
Betreff: Re: [Cfrg] new curves or old (was: Actual security levels for IETF
crypto)

Yes.

Good options for optimized and random primes is valuable.

We should not be so focused on ‘the’ ultimate curve, but also ensure that
there are well documented options for a variety of market applications.

Paul

From: Benjamin Black <[email-masked]>
Date: Friday, October 31, 2014 at 10:46 AM
To: "Paterson, Kenny" <[email-masked]>
Cc: "[email-masked]" <[email-masked]>
Subject: Re: [Cfrg] new curves or old (was: Actual security levels for IETF
crypto)

Yes.

"Keeping in mind that this may induce negative performance impacts, but

could increase confidence in the outcome of our deliberations."

The process should allow both random and selected primes, even if CFRG
decides to only use one or the other to meet the TLS-WG request. Agreeing on
the process allows us to avoid this lengthy debate in future should other
curves be needed to meet specific requirements.

On Fri, Oct 31, 2014 at 10:34 AM, Paterson, Kenny
<[email-masked]> wrote:

Hi

Thanks,

Kenny

On 31/10/2014 14:39, "Benjamin Black" <[email-masked]> wrote:

>Right, I didn't say don't pick NUMS. I said I believe the process
>should've gone a direction it did not, which would've rejected _ALL_
>current candidates in favor of CFRG generating new ones. That is no more
>my saying "don't pick NUMS" than your
> saying you want genus 2 on the table is the same as your saying "don't
>pick Curve25519".
>
>On Fri, Oct 31, 2014 at 7:35 AM, Watson Ladd
><[email-masked]> wrote:
>
>On Fri, Oct 31, 2014 at 7:31 AM, Benjamin Black <[email-masked]> wrote:
>> Watson,
>>
>> Where exactly did I say "don't pick NUMS"?
>
>On October 29
>"I've also said repeatedly that we should be starting from
>requirements and then consider _generating_ curves to meet them,
>rather than limiting ourselves to the curves at hand or trying to
>contort the requirements to match an existing favorite."
>
>
>
>That seems to suggest that we don't pick any curves, but instead
>generate new ones.
>
>>
>>
>> b
>>
>> On Fri, Oct 31, 2014 at 7:14 AM, Watson Ladd <[email-masked]>
>>wrote:
>>>
>>> On Fri, Oct 31, 2014 at 7:10 AM, Stephen Farrell
>>> <[email-masked]> wrote:
>>> >
>>> >
>>> > On 31/10/14 14:05, Richard Barnes wrote:
>>> >> The idea that whiz-bang new crypto is the main barrier to 100% HTTPS
>>> >> adoption seems rather naïve.  It helps,
>>> >
>>> > I agree. Of course, having CFRG decide on precisely
>>> > which whiz-bang new crypto would be a good next step:-)
>>>
>>> But our choices are not the fastest ones! We've decided to have genus
>>> 1 prime, no CM, which is a very conservative choice, but not
>>> necessarily the fastest.
>>>
>>> Anyway, since Benjamin Black has said he doesn't actually think we
>>> should pick NUMS, but do our own picking, I think the answer is
>>> clear...
>>> >
>>> > S.
>>> >
>>> > _______________________________________________
>>> > Cfrg mailing list
>>> > [email-masked]
>>> > http://www.irtf.org/mailman/listinfo/cfrg
>>>
>>>
>>>
>>> --
>>> "Those who would give up Essential Liberty to purchase a little
>>> Temporary Safety deserve neither  Liberty nor Safety."
>>> -- Benjamin Franklin
>>>
>>> _______________________________________________
>>> Cfrg mailing list
>>> [email-masked]
>>> http://www.irtf.org/mailman/listinfo/cfrg
>>
>>
>
>
>
>--
>"Those who would give up Essential Liberty to purchase a little
>Temporary Safety deserve neither  Liberty nor Safety."
>-- Benjamin Franklin
>
>
>
>
>
>
>

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Sun, 2 Nov 2014 17:18:37 -0500

No

What we need is an unambiguous signal that ECC is now ready for prime
time. And the way to do that is to take all the options off the table
except for the performance curve and the backup.

If you can't or don't pick one winner then the whole exercise is
devalued. You are sending the signal that we don't know what we are
doing.

This is a standards exercise and the point of a standard is to make
choices that don't matter out of the design equation. One of the major
reasons that RSA has become dominant is that it offers a simple
proposition, a fixed set of key lengths, only one parameter (e).

In contrast NIST gave us a bazillion choices with no particular
guidance on how to chose between them.

---

From: Benjamin Black <[email-masked]>
Date: Sun, 2 Nov 2014 15:02:23 -0800

There are a larger bazillion choices for RSA. 512, 768, 1024, 1280, 1536,
2048, 3072, & 4096 (and probably others) have been or are in use. The
comparison doesn't hold, anyway, since RSA allows arbitrary bit lengths
while a given curve supports exactly one.

Regardless, I don't understand the insistence on rushing a decision. We're
talking about choices we will have to live with for 20 years. An extra
month or two won't kill us.

---

From: "D. J. Bernstein" <[email-masked]>
Date: 3 Nov 2014 08:27:43 -0000

Paterson, Kenny writes:
> - Who on the list would be in favour of using a to-be-agreed procedure
> to generate new curves

There's an important ambiguity here:

   * Is the idea to throw away all of the current curve proposals, such
     as Curve25519 and E-521 and Microsoft's "NUMS" curves?

     This is clearly what Torsten Schütze's "yes" means. He says that
     the disadvantage of having to "wait" for new curves is outweighed
     by the need for "TRUST" in "the selected curves". Evidently he's
     claiming that CFRG can't trust any of the existing proposals. (If
     CFRG _does_ trust one of the proposals, then it can simply take
     that one without having to wait, so the argument makes no sense.)

   * Or is the idea to have CFRG pick a new curve _and_ one of the
     current curves?

     This is clearly what Paul Lambert's "yes" means: "Good options for
     optimized and random primes is valuable. ... ensure that there are
     well documented options for a variety of market applications." This
     is asking CFRG to pick a random-prime option _and_ to pick a faster
     option, based on the claim that having both options would provide
     benefits for applications; there's nothing here saying that the
     faster options on the table should be thrown away.
     
     It's not as clear if this is what Benjamin Black's "yes" means. He
     advocates a "process" to "allow both random and selected primes";
     on the other hand, what he had said earlier was that he wanted to
     reject "_ALL_ current candidates in favor of CFRG generating new
     ones". I can't figure out whether he's advocating throwing away the
     "NUMS" curves, for example.

     Dan Brown's "yes" is even less clear. He says that he wants a
     "random" curve using a "special prime"---this part is clear enough,
     and quite different from taking a random prime---but I have no idea
     whether he's asking for this "random" curve to coexist with a
     better-optimized curve using the same prime, or to coexist with a
     better-optimized curve using a different prime, or to be the sole
     CFRG output.

Apparently the motivation for some people to ask for "new curves" is
that they want some sort of "randomness", but they can't even agree on
what the desired "randomness" actually is (prime? curve? hashing? ...),
and whether the resulting "random" curve is supposed to be the sole CFRG
output or merely an extra option.

My own view is that

   * the best curves have already been found---for example, if CFRG
     wants a curve at a stratospheric >2^250 security level, then E-521
     is the best choice;

   * _replacing_ these curves with other curves at similar security
     levels would be a mistake---especially if the replacements use
     random primes, forcing users down to much lower security levels for
     any particular performance level; and

   * _supplementing_ these curves with additional options at similar
     security levels would also be a mistake---we have enough trouble
     getting security right without this sort of distraction.

Many arguments have already been given in favor of the current
proposals, and I won't repeat those arguments here, but let me add a
suggestion for people who think that it's possible to do better: please
_first_ generate your curves and _then_ ask CFRG to consider them. This
is particularly important for "random" curves:

   * Decades of successful attacks show that it's much, much, much
     easier to say "generate a random number" than to actually do it in
     a secure way---and that's in the easy situation of generating
     random numbers for oneself, whereas CFRG is facing the tougher
     problem of convincing third parties years later that the results
     weren't manipulated.

   * Brainpool claimed to have "verifiably pseudo-random curves" from
     hashing "seeds that are generated in a systematic and comprehensive
     way" as a substitute for true randomness, but we showed that more
     than a million curves could be generated with similar explanations
     (and Johannes Merkle has already admitted several bits of this
     flexibility---we can discuss the other bits if necessary).

   * Dan Brown said back in April that he would specify "a method to
     generate random curves (and constants)" but as far as I know he
     never followed through.

It's natural to overestimate the security, simplicity, and speed of a
solution that hasn't actually been specified yet.

I realize that curves can be costly to generate (for example, quite a
bit of CPU time was spent locating E-521, and I've heard amusing ideas
for even more expensive curve-generation procedures), but I don't see
any excuse for not producing scaled-down prototypes. Concrete curve
proposals are important as a basis for comparison.

---Dan

---

From: Alyssa Rowan <[email-masked]>
Date: Mon, 03 Nov 2014 09:10:28 +0000

On 2 November 2014 23:02:23 GMT+00:00, Benjamin Black <[email-masked]> wrote:

>Regardless, I don't understand the insistence on rushing a decision. We're talking about choices we will have to live with for 20 years. An extra month or two won't kill us.

Because other people have deadlines, Ben.

People are waiting on our recommendations: both downstream WGs like TLS and other groups like W3C. But the need to actually deploy universal encryption is pressing, and we are quite simply not important enough to wait very long for (we've probably already missed the train for WebCrypto?).

If we cannot make very clear choices, if we cannot make them very soon (e.g., early December/*before* Christmas), or if the choices we make aren't very good ones, implementers will just go and make their own choices. (Some, like SSH, already have.)

We now have a menu of excellent choices on the table, and reasonable ways to evaluate them. They mostly look like they'd all be fine for 20 years (excepting quantum computers). So let's do that. There really is no excuse for dithering around meaninglessly otherwise.

- --
/akr

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Mon, 3 Nov 2014 13:18:31 +0000

The "big" choice seems to be between endorsing a fixed curve (or a set of curves), and endorsing a verifiably-random curve generation process/algorithm. It is all about endorsement.

There are plenty of samples in each group to select from, so it does not have to be something CFRG-invented from scratch (because people are too afraid to trust anything already existing).

CFRG may decide that Brainpool generation algorithm (and curves) are fine, and endorse it. CFRG may endorse another generation algorithm, or settle on a bunch of already proposed curves.

--
Regards,
Uri Blumenthal Voice: (781) 981-1638
Cyber Systems and Technology Fax: (781) 981-0186
MIT Lincoln Laboratory Cell: (339) 223-5363
244 Wood Street, Lexington, MA 02420-9185

Web: http://www.ll.mit.edu/CST/
MIT LL Root CA: <https://www.ll.mit.edu/labcertificateauthority.html>

From: Benjamin Black [mailto:[email-masked]]
Sent: Sunday, November 02, 2014 06:02 PM
To: Phillip Hallam-Baker <[email-masked]>
Cc: [email-masked] <[email-masked]>
Subject: Re: [Cfrg] new curves or old (was: Actual security levels for IETF crypto)

There are a larger bazillion choices for RSA. 512, 768, 1024, 1280, 1536, 2048, 3072, & 4096 (and probably others) have been or are in use. The comparison doesn't hold, anyway, since RSA allows arbitrary bit lengths while a given curve supports exactly one.

On Sun, Nov 2, 2014 at 2:18 PM, Phillip Hallam-Baker <[email-masked]<mailto:[email-masked]>> wrote:
No

On Fri, Oct 31, 2014 at 1:34 PM, Paterson, Kenny
<[email-masked]<mailto:[email-masked]>> wrote:
> On 31/10/2014 14:39, "Benjamin Black" <[email-masked]<mailto:[email-masked]>> wrote:
>
>><[email-masked]<mailto:[email-masked]>> wrote:
>>
>>On Fri, Oct 31, 2014 at 7:31 AM, Benjamin Black <[email-masked]<mailto:[email-masked]>> wrote:
>>> Watson,
>>>
>>> On Fri, Oct 31, 2014 at 7:14 AM, Watson Ladd <[email-masked]<mailto:[email-masked]>>
>>>wrote:
>>>>
>>>> <[email-masked]<mailto:[email-masked]>> wrote:
>>>> >
>>>> >
>>>> > [email-masked]<mailto:[email-masked]>
>>>> [email-masked]<mailto:[email-masked]>
> [email-masked]<mailto:[email-masked]>

---

From: "Paterson, Kenny" <[email-masked]>
Date: Mon, 3 Nov 2014 16:18:09 +0000

Alyssa,

On 03/11/2014 09:10, "Alyssa Rowan" <[email-masked]> wrote:

>-----BEGIN PGP SIGNED MESSAGE-----
>Hash: SHA512
>
>>Regardless, I don't understand the insistence on rushing a decision.
>>We're talking about choices we will have to live with for 20 years. An
>>extra month or two won't kill us.
>
>People are waiting on our recommendations: both downstream WGs like TLS
>and other groups like W3C. But the need to actually deploy universal
>encryption is pressing, and we are quite simply not important enough to
>wait very long for (we've probably already missed the train for
>WebCrypto?).

No. We are in fairly regular contact with the W3C folks, and while it's
true that they are waiting with bated breath for our recommendations, we
are not about to miss any trains.

>
>If we cannot make very clear choices, if we cannot make them very soon
>(e.g., early December/*before* Christmas), or if the choices we make
>aren't very good ones, implementers will just go and make their own
>choices. (Some, like SSH, already have.)

OpenSSH has, which is indeed most of SSH deployment. But they've always
made their own choices, including some bad ones (e.g. a broken version of
CBC mode that has only just been removed from their codebase in version
6.7, 5 years after http://www.openssh.com/txt/cbc.adv)

>We now have a menu of excellent choices on the table, and reasonable ways
>to evaluate them. They mostly look like they'd all be fine for 20 years
>(excepting quantum computers). So let's do that. There really is no
>excuse for dithering around meaninglessly otherwise.

I agree with the sentiment that we have excellent choices already before
us.

However, if there's a reasonably simple way to ensure the highest possible
levels of trustworthiness in our recommendations with unduly compromising
efficiency and security, then I am prepared to sacrifice some extra time
to achieve it.

Regards

Kenny

---

From: Watson Ladd <[email-masked]>
Date: Mon, 3 Nov 2014 08:37:39 -0800

> Alyssa,
<snip>
> efficiency and security, then I am prepared to sacrifice some extra time

That assumes that picking a generation method would "ensure the
highest possible levels of trustworthiness". It's not clear to me that
it would. Opponents of the performance approach can demonstrate the
flexibility they insist exists by putting BADA55 in the hexadecimal
form of the coefficients obtained by taking the minimal equation
satisfying reasonable constraints on a performance-oriented prime. Or
they can explain what concerns are addressed by their proposal and how
they are addressed: I still don't know, because the proponents of
generation have made nothing more then repeated bare assertions that
it does address concerns.

The fact that the people voting "yes" don't agree with each other on
what a yes looks like is a very bad sign. It means that generation
requires reopening discussions that have basically yielded no fruit
since April. It's remarkable that we can't agree on the security
picture for intensively studied, well-understood, 30 year old crypto,
and even more remarkable that we can't agree that widely adopted,
performance, crypto with no security problems, can be used on the
Internet.

Furthermore, picking curves isn't the only thing we have to do. We've
got PAKEs on the agenda. We've got a massive W3C related task telling
people what not to do with WebCrypto. We've got ChaCha20-Poly1305 on
the table, which is needed because of timing attacks on AES on most
processors. The longer it takes to do things, the less we can do.

---

From: Adam Langley <[email-masked]>
Date: Mon, 3 Nov 2014 08:42:38 -0800

No.

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: "Paterson, Kenny" <[email-masked]>
Date: Mon, 3 Nov 2014 16:43:08 +0000

Hi Dan,

Indeed, there's ambiguity in your post and in the ones to which it refers.

The full and explicit intention of my question was this: do we want to
clear the table completely and generate some fresh curves according to
some to-be-agreed procedure, or not.

If the RG said "yes" to this question, then the procedure we use would be
up for discussion.

The agreed upon procedure need not involve any randomness, and it could be
one that leads to curves already on the table, which would (if we don't
cook the books in writing down the procedure!) validate the rigidity of
the process by which those curves were produced in the first place. If so,
then great, we'd have further evidence of the unimpeachability of our
recommendations.

The agreed upon procedure might involve randomness, in which case it would
be much less likely to produce curves which are currently on the table.

It would be for the RG to decide, by consensus if possible, by majority if
not, by fiat if necessary, what the procedure would be.

Cheers

Kenny

---

From: "Paterson, Kenny" <[email-masked]>
Date: Mon, 3 Nov 2014 16:57:07 +0000

Watson,

On 03/11/2014 16:37, "Watson Ladd" <[email-masked]> wrote:

>what a yes looks like is a very bad sign.

I disagree. I think the question could have been posed more precisely by
me, and some of that lack of agreement would have been avoided. As I just
said in my reply to Dan, the procedure that would need to be agreed upon
by the RG need not involve any (verifiable) randomness, even if it is the
presumption of some people saying "yes" that it would. Indeed, we could
end up back where we started, with a few families of well understood
curves. We can then toss a suitably many-sided coin. But going through
that process might give us a stronger sense of having done as much due
diligence as possible given the RG's limited resources.

>It means that generation
>since April.
> It's remarkable that we can't agree on the security

That's because it's mostly not 30 years old, and because it's not yet that
well understood outside a small circle of experts.

To expand: all of the Edwards and twisted Edwards stuff is much newer
(less than 10 years old, by my reckoning), has not been widely deployed
and runs counter to the existing settled ECC consensus as represented by
current deployment of ECC (which basically involves prime order curves in
Weierstrass form). It might look trivial to you as a mathematician, but
it's far from trivial to almost everyone else. This is not to say that we
cannot or should not recommend "modern" ECC to the TLS WG. But I think
it's worth keeping in mind as context.

>got PAKEs on the agenda.

We do, but there's a relatively small intersection of people, and
responding to the TLS WG's request *is* our priority at the moment.
 
>We've got a massive W3C related task telling
>people what not to do with WebCrypto.

For some definition of "we". It's not CFRG's job, AFAIK.

>We've got ChaCha20-Poly1305 on
>processors. 

Yes, that's passed through last call rather smoothly and is already with
the IESG document shepherds.

>The longer it takes to do things, the less we can do.

And the longer we take, the better answers we can hope to get on the
things that really matter.

Cheers

Kenny

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 3 Nov 2014 13:05:08 -0500

The problem here is not to find curves we are confident in. It is
finding curves that we can make other people confident in.

If it was just about convincing ourselves and people willing to engage
in abstract mathematical discussions, the problem would be
straightforward.

Remember that every one of the curves we are considering is to the
best of our knowledge secure for the foreseeable future. Think of the
way a bank building is constructed with neoclassical pillars and stone
walls, none of which add to the security of the vault in the
slightest. The point of that fancy stonework is not to make the bank
secure, it is to show that the bankers can afford the security.

The arguments for P256 and P512 are very simple. I can convince
someone that Curve P256 is a acceptably secure and not likely to have
been sabotaged to the satisfaction of the typical IETF attendee or a
customer or come to that a judge sitting in chambers in a few minutes.
I can convince someone that P512 puts the security of the crypto
beyond dispute unless there is a development (e.g. practical QM) that
is so powerful that it puts all options in dispute.

Every step away from those positions makes the task of explanation
harder. Curve 25519 is a harder sell than P256 but the argument is not
too difficult to make. The alternatives to P512 are a much harder
sell.

If we re-open the door to random curves then the explanation challenge
becomes orders of magnitude greater because it is not a single point
in a mathematical space I have to justify, it is the entire process
under which the curves were created.

I know how to develop a cryptographic ceremony that provides a very
high degree of assurance that there was no subterfuge. In fact I once
taught a (very expensive) two week course. But I know that any process
we develop is going to be sufficiently complex for Roswell and moon
landing conspiracy theorists to dispute the circumstances.

The PKI industry is currently building an infrastructure that is
likely to end up costing of the order of $5-25 million/year to build
and operate. The reason we are having to do that is the DigiNotar
incident. Which might seem reasonable to people because the risk that
a non-authorized CA might issue a cert for your domain, yada yada.
Meanwhile we have a revocation infrastructure which is far more
critical to the operation of the WebPKI that is being pared back and
de-activated. End entity keys get stolen by crooks every single day,
the failure rate for CA keys is once a decade. [Note that TRANS is
only motivated by DigiNotar, CAA is sufficient for the minor
breaches].

The reason for this situation is that confidence is more than simply a
'marketing concern'. Confidence is the product.

Trust is the degree of confidence a party has in being able to predict
the outcome of an action.

---

From: Alyssa Rowan <[email-masked]>
Date: Mon, 03 Nov 2014 19:01:57 +0000

On 03/11/2014 16:18, Paterson, Kenny wrote:

>> […] (we've probably already missed the train for WebCrypto?).
> No. We are in fairly regular contact with the W3C folks, and while
>  it's true that they are waiting with bated breath for our 
> recommendations, we are not about to miss any trains.

Well, that at least is encouraging. (I was a little concerned of the
potential adoption consequences of being WebCrypto spec extensions.)

>> […] implementers will just go and make their own choices. (Some,
>>  like SSH, already have.)
> OpenSSH has, which is indeed most of SSH deployment. But they've 
> always made their own choices, including some bad ones […]

Historically, yes. Here, I think they perceived an urgent need, and
addressed it.

In a way, I suppose that's kind of my point. If we wait too long to
make recommendations, we run a greater risk they may not be followed.

I remember back in July, there were hopes it was going to take around
8 weeks for us to put forth, evaluate and approve candidates. :)

> I agree with the sentiment that we have excellent choices already 
> before us. However, if there's a reasonably simple way to ensure
> the highest possible levels of trustworthiness in our
> recommendations with unduly compromising efficiency and security,
> then I am prepared to sacrifice some extra time to achieve it.

I appreciate that.

My point is: if we did do the curve generation process from scratch,
given the criteria of efficiency, security, simplicity, rigidity,
interoperability and intellectual property, we are highly likely to
simply end up with one or more of the excellent choices already before
us, precisely because of that rigidity; the solution space seems
fairly well-explored (although of course we should explore it
thoroughly when selecting recommendations).

- -- 
/akr

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Mon, 3 Nov 2014 14:32:32 -0500

> thoroughly when selecting recommendations).

And in my opinion it would be a perfectly acceptable outcome. 

For example, Brainpool looks perfectly fine (Tanja Lange participated in the Brainpool process - so she should know whether they subverted it or not; or should her co-authorhship on the Dan's paper be considered as a veiled confession? ;-))

I can also live with SEGC or Brainpool algorithms being tweaked by this group, assuming this tweaking is accompanied by published cryptographic justifications that are beyond reproach.

---

From: Watson Ladd <[email-masked]>
Date: Mon, 3 Nov 2014 12:12:23 -0800

On Nov 3, 2014 11:32 AM, "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
wrote:
> For example, Brainpool looks perfectly fine (Tanja Lange participated in
the Brainpool process - so she should know whether they subverted it or
not; or should her co-authorhship on the Dan's paper be considered as a
veiled confession? ;-))

How is this different from picking Brainpool then? And Brainpool is not
perfectly fine: massive performance slowdowns, gratuitous use of
endomorphisms, and some really dodgy generation choices.

>
> I can also live with SEGC or Brainpool algorithms being tweaked by this
group, assuming this tweaking is accompanied by published cryptographic
justifications that are beyond reproach.

But can you live with Edwards curves over a field picked to be near a power
of two as the NUMS group suggest, or for performance/beauty as everyone
else suggests?

If we clarified the suggestion, this would change your vote it seems.
Living in CA I'm all to aware of how easy it is to support an abstract
principal and never the application.

Has anyone changed their minds in the past 3 months? Anyone? Is anyone
going to change their minds in the future? We could keep this discussion
alive indefinitely at this pace, and end up not making any difference in
security.

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Mon, 3 Nov 2014 16:32:55 -0500

On Nov 3, 2014, at 15:12 , Watson Ladd <[email-masked]> wrote:
> > > My point is: if we did do the curve generation process from scratch, given the criteria of efficiency, security, simplicity, rigidity,
> How is this different from picking Brainpool then?
> 
As I said, I'm OK with this group endorsing/recommending Brainpool.

> And Brainpool is not perfectly fine:
> 
OK, not *perfectly* fine. :-)

> massive performance slowdowns,
> 
I can live with them.

> gratuitous use of endomorphisms,
> 
I can live with them.

> and some really dodgy generation choices.
> 
Complain to Tanja - it's her work (among others :). :-)

(Though I personally don't find those choice dodgy at all.)

> But can you live with Edwards curves over a field picked to be near a power of two as the NUMS group suggest, or for performance/beauty as everyone else suggests?
> 
Do I like them, or believe they've been studied sufficiently from cryptographic point of view? No. (P.S. Beauty is in the eye of the beholder. :)

Can I live with them? Yes.

> If we clarified the suggestion, this would change your vote it seems. Living in CA I'm all to aware of how easy it is to support an abstract principal and never the application.
> 
As I stated, my *preference* is an endorsed mechanism for generating *verifiably random* curves, with the ability to generate *new* conforming curves using that algorithm.

But if, for example, it's NUMS that's chosen, I'm OK with it.

---

From: "Torsten Schütze" <[email-masked]>
Date: Mon, 3 Nov 2014 22:54:29 +0100

Dan,

D.J. Bernstein wrote:
> Gesendet: Montag, 03. November 2014 um 09:27 Uhr
> Von: "D. J. Bernstein" <[email-masked]>
> An: [email-masked]
> Betreff: Re: [Cfrg] new curves or old (was: Actual security levels for IETF crypto)
>
> Paterson, Kenny writes:

It's always fun if one gets explained what was the meaning of one's own mail ;-)

No. I do not say that we should throw away all current curve proposals such as Curve25519, 
E-521 and MS's NUMS. What I do say: Let us define a clear requirements catalog and only 
then check if the proposed (and existing) curves match ALL/MOST of these requirements.

As far as I understood, it is up to now not yet clear if we consider only software 
implementations in a secured environment (or software for short) or if we consider in 
addition implementations in a hostile environment (software and/or "old, rusty" 
hardware, hardware for short).

It could well be that one of the special primes proposals wins the race for the "software 
in a secured environment" category. For "hardware or software in hostile environments" the 
outcome is not so clear to me. In this category, I would like to see a verifiable pseudo-random 
prime for reasons explained earlier. And, yes, this would probably (hopefully) lead to some 
Brainpool-like curve. 

Dan, can you provide ONE example where one of your favorites, e.g. Curve25519, has been 
implemented and evaluated/certified against ALL of the usual side-channel attacks with 
high assurance level? Especially, not only global timing attacks. We all know that you 
don't like CC or similar schemes, but at least they are better than nothing.

Regarding trust: I'm really surprised. Who wrote the paper/gave the talks, with paragraphs like

"In the same vein the German ECC Brainpool [4] consortium raised scepticism and suggested using
natural constants in place of random seeds. They coined the term "verifiably pseudorandom" for this
method of generating seeds. Others speak of "nothing-up-my-sleeves numbers"...
We comment that "nothing-up-my-sleeves numbers" also appear in other areas of cryptography and
CAN BE MANIPULATED IN SIMILAR WAYS [highlighting by TS], but this paper focuses on manipulation 
of elliptic curves."

The question is not if I (or we as a cryptographic community) trust the CFRG, the question is 
if the consumers of cryptography, i.e., not the specialists in ECC, re-gain trust in Elliptic 
Curve Cryptography. 

Or what do you think is the effect on an average crypto user which reads the following from 
an interview with Tanja from a German IT online security magazine?
"Lange empfahl der CFRG dabei, auf jeden Fall auf neuere Kurvenvarianten zu setzen. 

...
Ein Kernproblem vieler verfügbarer Standardkurven – darunter neben den NIST-Kurven auch die von Frankreichs Agence Nationale de la Sécurité des Systèmes d'Information und die vom Bundesamt für Sicherheit in der Informationstechnik vorgeschlagenen Brainpool-Kurven – ist, dass sich zu leicht Fehler im Betrieb einschleichen."
http://www.heise.de/security/artikel/Nach-Snowden-Wenig-Schlaf-fuer-Kryptoforscher-2392236.html

In your talks you always argue with the difficulty/complexity of using affine points for addition/doubling. But who really uses affine points? I've never seen this for years, most of the implementations I've seen (high-assurance and/or smartcards) use some kind of projective coordinates with Montgomery ladder/Lucas chain. Yes, they are slower than your Edwards curves, but that doesn't mean they are insecure or not safe.

>    * Or is the idea to have CFRG pick a new curve _and_ one of the

I, personally, could live with

a) either Brainpool curves or new Brainpool-like curves for both categories

b) special prime curves with cofactor 1 and twist security (for high performance 
software in secured environments) AND verifiably pseudo-random primes, i.e., Brainpool 
curves or Brainpool-like curves for the other category (high-assurance in hostile environments)

The new Brainpool-like curves would be an offer to improve / document the curve selection 
process to (re-)gain trust (This doesn't mean, of course, that I distrust the current BP-like curves).

> output or merely an extra option.

Of course, it's easier to say "no randomness at all" than to define the exact 
degree of randomness. For me it would be at least vpr primes. I am realistic and do not believe
that a random curve would be the sole CFRG output. But saying, CFRG specifies a new special
prime curve, for the rest you could take Brainpool curves is not quite the same as scenario b) above 
after all the "Brainpool bashing".

>      flexibility---we can discuss the other bits if necessary).

For example, we, the CFRG, could define in a documented way the curve 
generation process. For example, lets use e and Pi, lets use SHA-3 with 
512-bit output, define the seed procedure, etc. And then let's generate 
the curve and live with that. Maybe it's not the fastest curve, but Moore's 
law works for us.

Of course, in 10 or 15 years someone may accuse the CFRG of conspiracy. So, 
full rigidity is not possible! 

And no, it's not the same if we _first_ generate the curves and _then_ discuss 
the requirements (even if later generally agreed).

Torsten

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 3 Nov 2014 15:46:35 -0800

> On Nov 3, 2014, at 1:54 PM, Torsten Schütze <[email-masked]> wrote:
> 
> http://www.heise.de/security/artikel/Nach-Snowden-Wenig-Schlaf-fuer-Kryptoforscher-2392236.html <http://www.heise.de/security/artikel/Nach-Snowden-Wenig-Schlaf-fuer-Kryptoforscher-2392236.html>

This warning is about cofactor-1 curves, not about VPR issues.

> In your talks you always argue with the difficulty/complexity of using affine points for addition/doubling. But who really uses affine points? I've never seen this for years, most of the implementa…

The incompleteness problems with the formulas appear in projective / Jacobian form in pretty much the same ways that they do in affine.  For example, if you try to add a point to itself, you'll get 0 : 0 : 0 instead of the doubled point.

In some applications, either this can’t happen for structural reasons, or it happens only with negligible probability.  But in some applications (eg, MQV) the attacker can force it to happen and can exploit the result.

Working around this disadvantage is a pain.  See, for example, the innovative solution in Appendix C.1 of Microsoft’s NUMS paper (they deal with Weierstrass curves in that paper in addition to Edwards).

> curves or Brainpool-like curves for the other category (high-assurance in hostile environments)

Many contributors to this forum feel that cofactor 4 is superior to cofactor 1, because it’s easier to deal with small-subgroup attacks than it is to deal with incompleteness problems, especially if side channels are a concern.  Also, we all know cofactor-4 curves are faster.

> the curve and live with that. Maybe it's not the fastest curve, but Moore's 

I, for one, don’t think that “verifiably pseudorandom” is possible.  I think that instead we would need actual randomization and a collaborative process.  Perhaps we could agree on a generation and verification script; commit to subseeds; reveal our commitments; concatenate the seeds in a fixed order and SHA them.  The generation script would generate a curve, and create a certificate that the (much simpler) verification script can use to check that the procedure has been carried out faithfully.

This would take a lot of work to do correctly, and as you said would not give a proof to later conspiracy theorists that it had’n been monkeyed with.

Cheers,
— Mike

---

From: Tony Arcieri <[email-masked]>
Date: Mon, 3 Nov 2014 16:06:38 -0800

No.

The process has been dragging on for quite awhile as-is. There are many
good options already on the table, and this change sounds like it would
further slow down the process.

-- 
Tony Arcieri

---

From: Watson Ladd <[email-masked]>
Date: Mon, 3 Nov 2014 19:25:01 -0800

> in abstract mathematical discussions, the problem would be

But that is the problem. We're tasked with using our expertise to help
the IETF make better decisions about cryptography, not to make the
decisions they could make. As DJB so succinctly put it, "threa

> secure, it is to show that the bankers can afford the security.

This is oversimplifying the state of play significantly: the
advantages of performance curves in completely masking operations as
mentioned by DJB, the errors in implementations of Weierstrass curves
which the lack of a complete addition formula worsens, the
vulnerability of software to off-curve attacks which the Montgomery
ladder eliminates. What is true is that the discrete log problem is
hard on all the curves.

It's completely wrong about banking. Banks do not spend money on
marble to advertise the security of the vaults. They do it to
advertise their wealth. This is because bank deposits are bearer
bonds: whoever comes first gets paid in full, whoever comes last gets
nothing when the bank goes down. If you suspect that the owners of a
bank can't pay, there will be a run. Showing wealth reduces that risk.

> is so powerful that it puts all options in dispute.

Why is this the case? You've asserted this point repeatedly, and I can
see why it's easier than Brainpool. But I don't see why 1 out of 40
possible primes, and then the minimal coefficient, is much harder to
explain as not being backdoored. Repetition is not argument. Nor is
dressing up the assertion with an analogy that presupposes the
validity of the assertion.

> too difficult to make. The alternatives to P512 are a much harder

E-521 was discovered by three teams independently. It's the only
Mersenne prime in the ranges we are interested in. Why isn't this an
easier sell than Curve25519?

> under which the curves were created.

But if the process is truly unpredictable, by depending on closing
prices of the S&P 500 for instance, how could an attacker manipulate
the process to get a curve they want? Of course, they could provide an
obfuscated program for accepting the curve, but this would be
suspicious.

To make this concrete, why don't we use the SEC1 process but with a
starting seed consisting of a SHA256 hash of the closing prices of all
S&P 500 components on some day in the future, each on a line, in
decimal form with no extra characters that gets incremented each time
we want a new output? What's the way in which that can be manipulated?

If what you want is to know the superiority of one choice over another
in a way that's easily explainable, performance works. If you want to
know why one curve, and not another, performance is an excellent,
quantifiable answer. But if you want to know why a curve wasn't
sabotaged, being picked from a list of 40 primes, independently
discovered by 3 teams, or dependent on the S&P 500 closing prices on a
day in the future is an excellent answer.

I'm not saying being close to a power of 2 wouldn't work. What I am
saying is that the differences you make such a big deal out of are far
less significant than you think and are unlikely to affect public
acceptability.

> landing conspiracy theorists to dispute the circumstances.

Likewise, there are cranks who say all sorts of things about powers of
2. Is this really the problem here?

> only motivated by DigiNotar, CAA is sufficient for the minor

If by CAA you mean RFC 6844, it doesn't address compromise of CAs or
end certificates at all. It does address a CA being told to issue a
certificate by someone who isn't the person who controls the DNS entry
for the website.

As for revocation infrastructure being pared back and deactivated, I
think that OCSP stapling and provisioning of CRLs to clients as
described in https://www.imperialviolet.org/2012/02/05/crlsets.html is
expanding the usefulness of this infrastructure, not paring it back. I
also think that the externalities of end cert compromise are more
easily dealt with, then CA compromise.

I still don't understand the relevance of this to our discussion: this
isn't PKIX, and it has little to nothing to do with changing elliptic
curves.

> 'marketing concern'. Confidence is the product.

If the milkman sells milk, who sells confidence? We should make our
judgements based on what will actually improve security, not what will
look like it improves security. Part of that is performance. The
danger with any other method is that the customer finds out.

> the outcome of an action.

?? Again, I question the relevance.

Sincerely,
Watson Ladd

---

From: Yoav Nir <[email-masked]>
Date: Tue, 4 Nov 2014 08:57:29 +0200

> On Nov 3, 2014, at 8:05 PM, Phillip Hallam-Baker <[email-masked]> wrote:
> 

Who are these other people that we need to explain this to?  The people who participate in the TLS and IPsecME working groups are almost indistinguishable from the people who participate in CFRG, and even if they’ve never learned advanced algebra, they can all use a search engine well enough to find out that Curve25519 (as an example) is currently considered secure by practitioners in the field. Could this be wrong? Sure, but just as (most of us) assume that climate change is actually happening and that it is caused by human activity, those of us who are not cryptographers are going to trust the consensus.

Implementers are much the same. Are you referring to policy-makers? The people who work for governments and write conformance documents?  They tend to be a more conservative bunch, but ultimately they tend to be reasonable (and they really like randomization). If we choose Curve25519 or have a coin-flipping session and NIST doesn’t “bless” the curve, it’s not going to be because they don’t trust the procedure enough. It might be because they didn’t invent it.

So who are these people who can’t be confident in this process and yet can see through the argument that Cuve25519 is better than P-256 because 25519>256 ?

Yoav

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 4 Nov 2014 08:30:46 -0500

On Tue, Nov 4, 2014 at 1:57 AM, Yoav Nir <[email-masked]> wrote:
> Who are these other people that we need to explain this to?

The people who use the Internet and Web.

> So who are these people who can’t be confident in this process and yet can see through the argument that Cuve25519 is better than P-256 because 25519>256 ?

The topic of this thread is the random part rather than that choice.

P-256 and P512 are the easiest to explain.
Curve 25519 requires a little more explanation.
P521 requires quite a bit more explanation

These are all cases that can be made in an elevator pitch. the first
only takes a few floors, P521 requires a taller building.

The problem with randomness is that the explanation is going to be too
long even for the Sears tower. And there isn't any way to take the
'trust me' part out of the equation. No matter what the controls that
are proposed, folk looking at the curves after they have been cut are
going to have to rely on the assurances that the process was followed.

Take the example Watson gave of the closing price of the stock market.
That is actually very easy to game, just pick a day in the past that
meets the criteria. There is also a slightly harder attack which is to
manipulate the market to get the desired result. It certainly isn't
inconceivable that the NSA would order the wall street traders to
close the market at a given price if you are a Roswell class
conspiracy nut. But even if you don't go that far, the SEC just fined
a bunch of banks billions for manipulating the LIBOR rate.

NOMCON is a very poor example to draw analogies from here. The reward
to the attacker of biasing the NOMCON simply isn't great enough for an
attack to be worth while. The community interested in the decision is
going to check the results (I usually do) before the NOMCON is seated.

We are proposing to use ECC to secure the global e-commerce
infrastructure worth several trillion dollars a year. It is going to
be very hard to suggest that an attack isn't worth bothering about.

No matter how many controls you try to throw in, the explanation of
the randomness approach isn't going to be feasible until we have a
space elevator to give us enough time for the explanation.

And that is assuming that we can agree on a randomness process in the
first place. Which I think is highly unlikely.

The elevator pitch criteria is decisive for randomness. Whether it is
decisive for P256/P512 or not is a different matter and probably
depends on the part of the country you are in. DJB is in Chicago with
the Sears Tower. The West coast folk have rather shorter buildings due
to the San Andreas fault.

---

From: Yoav Nir <[email-masked]>
Date: Tue, 4 Nov 2014 16:35:29 +0200

> On Nov 4, 2014, at 3:30 PM, Phillip Hallam-Baker <[email-masked]> wrote:
> 

I really don’t want to be flip, but that group includes my 80-year-old mother and 10-year-old daughter. Neither of them deals with choosing curves. There is a group of people who know what TLS is, what PFS is, why group size matters, and that traditionally sizes of security elements were measured in powers of two. These people use the web, but within the big group of web users, their fraction is vanishingly small.  And I think these people are able to use google and find out why P-521 was chosen, same as you and I.

> only takes a few floors, P521 requires a taller building.

Why? 521 > 512, and bigger is better. The fact that we chose to go that extra mile because of performance rather than to get that extra few bits of security doesn’t change that.

> long even for the Sears tower.

I don’t think so. The idea that randomization prevents manipulation and targeting is pretty much accepted among anyone in the security field.

> And there isn't any way to take the
> 'trust me' part out of the equation.

That’s the big one. Unless your target audience is cryptographers, you can’t take the “trust me” part out of the equation anyway. Even having a degrees in computer science and/or mathematics does not allow people to analyze your choice of curves. Randomization evens the playing field because even cryptographers have to trust you if they weren’t there to verify that the procedure was followed. But most of the web users will have to trust us in any case.

> No matter what the controls that

There are better sources of randomness - coin flipping sessions. Enough of them can be audited to be free from manipulation.
> space elevator to give us enough time for the explanation.

Former IETFers are hard at work: http://lunarelevator.com

> first place. Which I think is highly unlikely.

On this, I’m with you.

> to the San Andreas fault.

Californians pitch ideas at the espresso machine, not in an elevator.

Yoav

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 4 Nov 2014 10:10:43 -0500

> I don’t think so. The idea that randomization prevents manipulation and targeting is pretty much accepted among anyone in the security field.

But are they random?

http://dilbert.com/dyn/str_strip/000000000/00000000/0000000/000000/00000/2000/300/2318/2318.strip.gif

> That’s the big one. Unless your target audience is cryptographers, you can’t take the “trust me” part out of the equation anyway.

I can explain the rigidity argument to high school students and they
can check it with high school math.

> There are better sources of randomness - coin flipping sessions. Enough of them can be audited to be free from manipulation.

But you end up having to trust the auditor. The audit is a one time
event and cannot be repeated in the future.

Transparency means that anyone can audit using publicly available information.

>> first place. Which I think is highly unlikely.

It would take an infinite amount of time because anyone can bike shed
the process with a way to corrupt the process.

We had a long discussion on this on Perry's Cryptography list. I can
provide a process that provides the participants with an assurance
that it is free from interference. But I can't provide a mechanism
that allows them to provide absolute proof it wasn't interfered with
after the fact.

---

From: Dan Brown <[email-masked]>
Date: Tue, 4 Nov 2014 15:03:05 +0000

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Phillip Hallam-Baker
> >
> These are all cases that can be made in an elevator pitch. the first only 
> takes a
> few floors, P521 requires a taller building.
>
> The problem with randomness is that the explanation is going to be too long
> even for the Sears tower. And there isn't any way to take the 'trust me' 
> part

[DB] Wouldn't you need a wider building to fit all the people who use the 
Internet and Web?  Inverting the metaphors, the width of elevator might 
correspond to some different source of trust than verification of argument, 
perhaps some kind of accountability, instead, maybe?

---

From: Watson Ladd <[email-masked]>
Date: Tue, 4 Nov 2014 07:36:44 -0800

> http://dilbert.com/dyn/str_strip/000000000/00000000/0000000/000000/00000/2000/300/2318/2318.strip.gif

This is exactly right.

> can check it with high school math.

What exactly is "the rigidity argument"? Is it that there is only 1
smallest prime greater than 2^256? Because there is also one prime
equal to 2^255-19. Does this help with security? No: you need to know
that the coefficient is correct, and showing minimality of the
coefficient is a considerable PITA computationally.

(How do they know the numbers you claim are prime are in fact prime?
For 2^521-1 it's somewhat easier, but still hours of computation by
hand)

The fact that you can't explain this argument to us is not convincing
me you can explain it to high school students.

Sincerely,
Watson Ladd

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Tue, 04 Nov 2014 16:44:10 +0100

> endomorphisms, and some really dodgy generation choices.
Sorry if this is obvious, but what do you mean by use of endomorphisms? Are you
refering to the fact that they give 2 isomorphic representations of each curve,
one with a = -3 and the other with a pseudorandom? Or is it something else?

Thanks,
Manuel.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 4 Nov 2014 10:53:01 -0500

> coefficient is a considerable PITA computationally.

I think you mean greatest prime smaller than 2^256. And as I pointed
out, I think the arguments for ~256 and ~512 are different and I am
quite happy to take 2^255-19. Its ~512 where the rule isn't so clear.

> For 2^521-1 it's somewhat easier, but still hours of computation by

Same way we do it for RSA keys, use the probaballistic algorithm.
Anyone can check to a very high degree of assurance within a minute.
As in the probability that the probability of getting the wrong result
as a result of machine failure is much higher than the uncertainty due
to the test procedure.

> me you can explain it to high school students.

Oh so your argument is that failing to convince you is not convincing you?

As with quantum mechanics, the more you know, the more complex the
explanations get. But you have to get to a fairly high level of
sophistication to understand the difference between P521 and P512.

The proposition that the NUMS curves are not rigid according to their
selection criteria is falsifiable by anyone who does the math.

The proposition that a random seed was generated in an unbiased
fashion is not falsifiable. There is no test I can propose after the
fact that allows me to prove that it was honest.

---

From: "D. J. Bernstein" <[email-masked]>
Date: 4 Nov 2014 16:14:59 -0000

Yoav Nir writes:
> traditionally sizes of security elements were measured in powers of two.

No.

The original DES used 56-bit keys. Triple DES, in the form standardized
for (and widely deployed in) the financial industry, uses 112-bit keys.

NSA's Skipjack (1998) uses 80-bit keys. The PRESENT cipher---much newer,
and standardized by ISO a few years ago---normally uses an 80-bit key.

All AES candidates were required to, and do, support key sizes of not
just 128 bits and 256 bits but also 192 bits.

NIST's standard hash output sizes are 160 bits, 224 bits, 256 bits, 384
bits, and 512 bits. Yes, 160 is deprecated now, but that's because 160
is too small, not because of some weird "power of 2" rule.

You meant public keys? NIST's SP 800-57 recommends RSA key sizes of
1024, 2048, 3072, 7680, and 15360 with 112-bit Triple DES, 168-bit
Triple DES, AES-128, AES-192, and AES-256 for security levels 80, 112,
128, 192, and 256 respectively.

IETF's recommendations for RSA key sizes in DNSSEC over the past fifteen
years, as I mentioned earlier in this thread, have included 704 bits,
"about" 924 bits, 1024 bits, "about" 1200 bits, 1300 bits, "about" 1900
bits, and 2048 bits. DNSSEC TLDs today mostly use 1024 or 1280.

You meant ECC? Let's try the NIST curves: 163 bits, 192 bits, 224 bits,
233 bits, 256 bits, 283 bits, 384 bits, 409 bits, 521 bits, 571 bits.

Or the ANSI curves: 163 bits, 176 bits, 191 bits, 192 bits, 208 bits,
239 bits, 256 bits, 272 bits, 304 bits, 359 bits, 368 bits, 431 bits. 

Or SEC 2 version 1.0: 112 bits (seriously!), 113 bits, 128 bits, 131
bits, 160 bits, 163 bits, 192 bits, 224 bits, 233 bits, 239 bits, 256
bits, 283 bits, 384 bits, 409 bits, 521 bits, 571 bits.  

Or the Brainpool curves: 160 bits, 192 bits, 224 bits, 256 bits, 320
bits, 384 bits, 512 bits.

Or NSA's Suite B curves: 256 bits, 384 bits.

---Dan

---

From: Watson Ladd <[email-masked]>
Date: Tue, 4 Nov 2014 08:17:46 -0800

> one with a = -3 and the other with a pseudorandom? Or is it something else?

The point that goes on the wire is the point on the pseudorandom curve
if I understand the specifications correctly, but the point people
want to use is the one on the a=-3 curve. Why have 2 choices for the
same thing?

Sincerely,
Watson Ladd

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 4 Nov 2014 11:24:03 -0500

And which of these choices did the community adopt widely?
c
AES 128
AES 256
RSA 512
RSA 1024
RSA 2408
RSA 4096
MD5 (128 bits)
SHA1 (160 bits)
SHA-2 (256 / 512 bits)

The only choice not a power of 2 that was widely used is SHA-1 at
160Bits. But that was largely chosen by default after MD5 was found
wanting.

Use of RSA1280 is limited to DNSSEC which has very peculiar limitations.

Yes, lots of folk have tried lots of different key sizes over the
years. But thats not the point. The point is which key sizes have
become ubiquitous choices.

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Tue, 04 Nov 2014 17:26:50 +0100

On 04/11/2014 17:17, Watson Ladd wrote:
> want to use is the one on the a=-3 curve.

Ok. Your wording with "endomorphisms" made me wonder if you meant something else.

> Why have 2 choices for the same thing?
> 
I'm not arguing for (or against) that, I just wanted to make sure I got your
message correctly, or if you were referring to some other problem I wasn't aware of.

Manuel.

---

From: Watson Ladd <[email-masked]>
Date: Tue, 4 Nov 2014 08:32:27 -0800

> quite happy to take 2^255-19. Its ~512 where the rule isn't so clear.

Let me make this as concrete as possible: Why do you think that the
only Mersenne prime in the range of exponents we are considering is a
suspicious rule, but primes close to a power of 2 is not? Minimal c is
very constraining: I think we got at most 60 primes. Is that still too
many?
We picked between them on the basis of performance: that seems very
hard to game as performance is very restrictive.

> Oh so your argument is that failing to convince you is not convincing you?

Exactly: You are saying that 2^521-1 is much more suspicious than
2^512-whatever, because you can explain the choice of 2^512-whatever
more easily than 2^521-1. But you haven't been able to give me an
explanation, so why should I assume you can give someone else an
explanation?

> sophistication to understand the difference between P521 and P512.

I don't consider it possible to explain QM to anyone without talking
about Hilbert spaces. But I can explain that the stronger curve goes
faster by pointing them to a benchmark, which they can run themselves.

> selection criteria is falsifiable by anyone who does the math.

So is the proposition that the parameters for the other curves depend
only on the prime. They do. The question comes down to which prime.

> fact that allows me to prove that it was honest.

I agree with you on that point.

---

From: Watson Ladd <[email-masked]>
Date: Tue, 4 Nov 2014 08:44:12 -0800

> 160Bits. But that was largely chosen by default after MD5 was found

Wrong: Triple-DES was and is used widely in banking. Binary curves are
used widely in hardware.

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Tue, 4 Nov 2014 17:01:17 +0000

On 11/4/14, 11:44 , "Watson Ladd" <[email-masked]> wrote:

>> AES 128, AES 256, RSA 512, RSA 1024, RSA 2408, …….
>>
>Wrong: Triple-DES was and is used widely in banking.

IMHO, Triple-DES does not represent community thinking and community
choices. DES had 64 bits for key, of which 8 were fixed as parity -
leaving 56 actual/effective key bits. There was no alternative to DES for
a very long time, so it was Hobson’s choice. Triple-DES does DES three
times. That means 56*2=112 or 56*3=168 key bits.

Triple-DES is still used, mostly to interoperate with sites too resistant
to change. The number of those goes down every day.

---

From: "Torsten Schütze" <[email-masked]>
Date: Tue, 4 Nov 2014 18:12:20 +0100

Watson Ladd wrote:
> Wrong: ... Binary curves are
> used widely in hardware.

Not in Germany and in Austria. In the late 1990s/the beginning 2000s there were a number of GF(2^n) smart card projects in these countries. They have ALL been replaced by GF(p) curves. Even Car2Car chooses GF(p), although there are HUGE performance requirements. It's not that easy to find high performance hardware implementations for GF(p) with general p. (I was looking for some of them for C2C some years ago.)

So coming back to E-521/P-521. I understand the performance aspects of this special prime quite well. Neglecting for a moment the Mersenne structure and only considering bit length:
Some years ago (>10 y) we did some smart card implementations with NIST and Brainpool curves (256, 384 and 512/521 bit). The unfortunate thing about 521 is that, in this case, and ONLY in this case, the randomization buffer (to the register boundary 540 bit plus some underflow buffer of x-bit) becomes smaller than usual, i.e., with 512 bit (and of course 256/384 bit) we used larger blinding factors than with 521. This was with Crypto@2304 bit, so registers 576/1152/2304 (minus 32 bit underflow). Of course, one could have used the larger registers, but only with some performance drawbacks. So, bit lengths exceeding powers of two matter, in this case security-wise.

Yes, this "old, rusty hardware" again ;-) Alyssa, is there a copyright on this?

Torsten

PS: Before someone asks: Yes, the crypto coprocessor can use variable length of registers, but there is an upper boundary. So you don't have to compute with 512 bit numbers if your number is only 400 bit wide.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 4 Nov 2014 13:02:40 -0500

> very constraining: I think we got at most 60 primes. Is that still too

I think we both agree that the argument I made does exclude the random
curves which was the main point I was making.

I don't think that there is one clear decisive approach for ~512.

> hard to game as performance is very restrictive.

But thats the problem, the hand picking part. I understand you aren't
trying to pull something but others have to have some explanation.

> explanation, so why should I assume you can give someone else an

You are demanding an explanation for 'best'. What I am looking for is
to prove to someone that there isn't any jiggery going on. Its a
different criteria.

> only on the prime. They do. The question comes down to which prime.

Exactly. And we need a decision procedure for the decision procedure.

I think the decision space comes down to:

1) Curve 25519 versus P256
2) P512 or P521

At this point I think Curve25519 looks like the better choice at ~256.
We are going to have to deal with it anyway. Its the Performance
curve.

~512 is a harder decision because there are two possible decision
criteria that can be applied.

We could throw it out to a poll on Boing Boing.

---

From: Yoav Nir <[email-masked]>
Date: Tue, 4 Nov 2014 21:21:08 +0200

> criteria that can be applied.

That assumes that there has been a decision to select a ~512 curve. Many of us prefer that we select goldilocks for the performance gain vs both P512 and E-521.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 4 Nov 2014 14:37:06 -0500

> That assumes that there has been a decision to select a ~512 curve. Many of us prefer that we select goldilocks for the performance gain vs both P512 and E-521.

OK so we add P448 and P480 back in, happy?

While I was looking up the security level, I found this:
http://sourceforge.net/p/ed448goldilocks/wiki/Home/

Ed448-Goldilocks is the elliptic curve:

x2 + y2 ≣ 1 - 39081x2y2 mod 2448 - 2224 - 1

This is a 448-bit Edwards curve with a 223-bit conjectured security
level. It is designed for spinal tap grade security.

I think the term 'spinal tap grade security' describes the criteria
here. The main problem with ED448 is that it does not meet the naive
'double the key size' criteria to make the 2^256 Work Factor criteria
even though some folk have argued that the work factor is considerably
better than 2^256.

>From a decision point of view I think Watson's approach of taking the
fastest curve of 512 bits or more is easier to defend than going
lower.

---

From: Yoav Nir <[email-masked]>
Date: Tue, 4 Nov 2014 22:14:12 +0200

> On Nov 4, 2014, at 9:37 PM, Phillip Hallam-Baker <[email-masked]> wrote:
> 

Ecstatic.

> level. It is designed for spinal tap grade security.

If 223-bit is turning the dial to 11, then what is 256-bit? Does your dial go to 12?

> even though some folk have argued that the work factor is considerably

So who’s criterion is it that we need 2^256 work factor? Only you are arguing for it, and even you are speaking on behalf of some unnamed other people.

> fastest curve of 512 bits or more is easier to defend than going

My concern is that if we’re specifying two curves, most implementations will implement both, and set the faster one as default or preferred. At some point, two things might happen.

First, some flaw could be found in the lower curve that necessitates switching, but does not invalidate the whole class of curves. Because everyone implemented the stronger curve, everyone switches to using it. I think it’s important to have the stronger curve have good enough performance that server operators are not left with the choice of using a broken curve or having their servers crumble under the load of handshakes. IOW we should get as much work factor as we can without impacting the performance too much.

Second, some government agency in some country or some group of auditors might decide to “turn the dial all the way to 11”, and mandate the stronger curve. This is not far-fetched. We’re already seeing auditors requiring AES-256, NIST P-384, and on occasion, RSA 4096 and IKE Diffie-Hellman group 18 (that’s 8192-bit FF DHE). For the unfortunate souls who have to deal with such auditors, we should treat the choice of the stronger curve as something that is likely to see actual use, not as some doomsday device that we keep locked away in the basement. Watson’s approach is along those lines, but doesn’t IMO go far enough.

Yoav

---

From: Benjamin Black <[email-masked]>
Date: Tue, 4 Nov 2014 12:37:46 -0800

Speed of a specific implementation, even the fastest available today for a
given curve on a given platform, is not rigid. Where is the formal
performance model by which curves will be judged? Where is the evidence
that sacrificing some security for small performance gains for some
implementations on some benchmarks on some platforms is a reasonable
trade-off? If you want to argue cycles per bit of security, even assuming a
performance model, then what evidence is there that 25519, which you
suggest, is the most efficient near the 128-bit level?

There are some odd arguments being made here that powers of 2 are arbitrary
but "about" 128-bit as the "right" security level is not. If you accept the
argument made previously that AES-128 is only 80-bit secure and that
performance is paramount, then one conclusion is we only need an 80-bit
secure curve, which will be far faster than anything being discussed near
128-bits. If, instead, you argue that 128(ish)-bits of security is the
"right" level, and the symmetric cipher strength should be increased to
meet or exceed it, then you get AES-256 which gets you a 25%+ performance
hit.

I have trouble reconciling these arguments for performance and rigidity
when they are so contradictory, arbitrary, and informal.

b

On Tue, Nov 4, 2014 at 11:37 AM, Phillip Hallam-Baker <[email-masked]

> > That assumes that there has been a decision to select a ~512 curve. Many
> of us prefer that we select goldilocks for the performance gain vs both
> P512 and E-521.
>

---

From: Watson Ladd <[email-masked]>
Date: Tue, 4 Nov 2014 12:51:49 -0800

On Nov 4, 2014 9:12 AM, Torsten Schütze <[email-masked]> wrote:
> Not in Germany and in Austria. In the late 1990s/the beginning 2000s
there were a number of GF(2^n) smart card projects in these countries. They
have ALL been replaced by GF(p) curves. Even Car2Car chooses GF(p),
although there are HUGE performance requirements. It's not that easy to
find high performance hardware implementations for GF(p) with general p. (I
was looking for some of them for C2C some years ago.)

I'd love to know more about this, probably offlist. Why is C2C not using
endomorphisms? Why was GF(p) liked more: I could guess some reasons but
they would be wrong.

>
> So coming back to E-521/P-521. I understand the performance aspects of
this special prime quite well. Neglecting for a moment the Mersenne
structure and only considering bit length:
> Some years ago (>10 y) we did some smart card implementations with NIST
and Brainpool curves (256, 384 and 512/521 bit). The unfortunate thing
about 521 is that, in this case, and ONLY in this case, the randomization
buffer (to the register boundary 540 bit plus some underflow buffer of
x-bit) becomes smaller than usual, i.e., with 512 bit (and of course
256/384 bit) we used larger blinding factors than with 521. This was with
Crypto@2304 bit, so registers 576/1152/2304 (minus 32 bit underflow). Of
course, one could have used the larger registers, but only with some
performance drawbacks. So, bit lengths exceeding powers of two matter, in
this case security-wise.

If the hardware had ten extra bits, it would have fit fine, unless I'm
missing something. Why should we worry about one particular unfortunate set
of choices?

Furthermore,  in software faster field arithmetic permits the use of
projective blinding. Brainpool's choice of random primes makes additive
blinding somewhat attractive.

But most users don't care about this sort of attack environment. Why should
we force a 2x slowdown on everyone for benefit of some hardware
implementations?

> PS: Before someone asks: Yes, the crypto coprocessor can use variable
length of registers, but there is an upper boundary. So you don't have to
compute with 512 bit numbers if your number is only 400 bit wide.

---

From: Michael Hamburg <[email-masked]>
Date: Tue, 4 Nov 2014 14:46:08 -0800

> On Nov 4, 2014, at 12:37 PM, Benjamin Black <[email-masked]> wrote:
> 
> Speed of a specific implementation, even the fastest available today for a given curve on a given platform, is not rigid.

Do you have a specific disagreement with the argument I presented earlier, that only perhaps tens of primes in the interval (2^384, 2^512) support close to optimal performance?

> Where is the formal performance model by which curves will be judged? Where is the evidence that sacrificing some security for small performance gains for some implementations on some benchmarks on some platforms is a reasonable trade-off?

There isn’t a formal model.

Consider the AES competition, or the SHA3 competition, or CAESAR or PHC.  These were actual formally organized competitions which ran, or are running, for years.  They were concerned with performance on a variety of platforms, but none of them set a formal standard for the trade-off between performance and other metrics.  Just as in those settings, performance is just one metric to be used to compare the options.  It is not the last or only metric, but it is a useful one.

Likewise, “rigidity” is an important metric, but it is also somewhat difficult to evaluate.  You certainly know this, having waffled from d = (1-) 78296 to d = 637608 for ed-512-mers; and having chosen a different E-521 from the three other groups who searched mod that prime; and having chosen the more dangerous incomplete twisted Edwards curves over untwisted Edwards for a very small performance gain.

When I designed Ed448-Goldilocks, it was actually as a middle-security curve, like so:

* Everyday curve: maximum performance (and/or simplicity) with strong resistance to all known and foreseen (non-QC) attacks.  Curve25519, Kumfp127g, etc.

* Usable but hedged: still performant enough for most uses, with a large hedge against unknown attacks.  This is explicitly a performance vs hedge tradeoff.  Curve41417, Ed448-Goldilocks, etc.

* ECC’s last stand: a curve which is very slow and conservative, to be deployed but rarely used.  Must have a random prime and j-invariant, with no major constraints that aren't known to improve security.  If in 20 years somehow all the other curves are broken in a surprise announcement, we can switch to this one with a small config change and a huge performance drop, to tide TLSv2.7 over until we can roll out lattices or McEliece or braids or whatever in v2.8.  Brainpool p512 might be enough for this, or we might even want a bigger curve.

Note that NUMSp512 and E-521 are no better than Goldilocks for the “ECC’s last stand" category: it’s important that the prime and curve be random, with no large constraints other than resistance to known attacks, and performance is barely a consideration at all.  But that curve will have terrible performance, so it should not be expected to be widely used.

> If you want to argue cycles per bit of security, even assuming a performance model, then what evidence is there that 25519, which you suggest, is the most efficient near the 128-bit level?

It isn’t.  We aren’t looking for the best possible curve, just the best choice available.  Curve25519 is nice because it’s fast, but also because it’s already trusted, implemented on many platforms, and widely deployed.  Otherwise, it might work better to use some other curve and some other field, like I dunno, 2^256 - 2^194 - 1, or GF((2^127-1)^2), or maybe even something crazy like 2^250 - 26 * 2^200 - 1.

> There are some odd arguments being made here that powers of 2 are arbitrary but "about" 128-bit as the "right" security level is not. If you accept the argument made previously that AES-128 is only 80-bit secure and that performance is paramount, then one conclusion is we only need an 80-bit secure curve, which will be far faster than anything being discussed near 128-bits. If, instead, you argue that 128(ish)-bits of security is the "right" level, and the symmetric cipher strength should be increased to meet or exceed it, then you get AES-256 which gets you a 25%+ performance hit.

It’s a matter of threat model.  ECC does not degrade as much when stronger threat models are considered.  This means that time/memory/data/multikey threat models are a good reason to choose a stronger symmetric system, even if the existing one is WF128 secure against single-target attacks.  But they aren’t as good a reason to choose a stronger elliptic curve.  Just because AES-128 is only WF80 secure vs a strong threat model, doesn’t mean it’s OK to choose ECC which is only WF80 secure against an ordinary threat model.

It seems likely that WF80 was within the reach of intelligence agencies a decade ago or more (see suggestions involving a billion dollar factoring machine).  It is possible that in another couple decades, WF100 will be within reach.  Given that we are talking about new curves partially in reaction to Snowden, I think it should be a clear goal to be safely out of range of this sort of predictable progress for at least a couple decades.  Perhaps WF110 is enough, but it seems reasonable to hedge to WF120+ since the performance cost is reasonable.  Note that the same argument doesn’t hold at all for 384 vs 448 vs 512: we don’t know what the attacks might look like there.

As for stronger symmetric ciphers, people do this.  For example, NaCl pairs Curve25519 with XSalsa20 or AES256GCM.

> I have trouble reconciling these arguments for performance and rigidity when they are so contradictory, arbitrary, and informal.
> 
> b

You are welcome to propose a formal framework if you can argue that it accurately reflects reality.  Otherwise, please recognize that 2^512 is about as arbitrary as perf * log(curve size) ^ (1 + log2(3)).

Cheers,
— Mike

---

From: Watson Ladd <[email-masked]>
Date: Tue, 4 Nov 2014 18:20:46 -0800

> Second, some government agency in some country or some group of auditors might decide to “turn the dial all the way to 11”, and mandate the stronger curve. This is not far-fetched. We’re already se…

NIST does have a bigger curve that could be called for.  But I'd like
to clarify my thinking. I'm not attached to any particular number of
curves: I do think that a curve less expensive than E-521 and more
secure than Curve25519 would be useful. I think it should be Ed448
Goldilocks, but I can see why NUMS-384 (after fixing the idiotic twist
issue) would be useful: the tradeoff goes either way depending on
priorities: a lot more security for a little more time.

I feel much more strongly about E-521 vs NUMS-512 as both security and
performance favor the larger curve. But I see no reason why we need to
argue between E-521 and Goldilocks: we can specify three curves
easily.

Sincerely,
Watson Ladd

---

From: Benjamin Black <[email-masked]>
Date: Tue, 4 Nov 2014 19:30:35 -0800

Please refrain from calling decisions with which you disagree "idiotic" or
similar.

On Tue, Nov 4, 2014 at 6:20 PM, Watson Ladd <[email-masked]> wrote:

> >>> That assumes that there has been a decision to select a ~512 curve.
> Many of us prefer that we select goldilocks for the performance gain vs
> both P512 and E-521.
> >>
> > So who’s criterion is it that we need 2^256 work factor? Only you are
> arguing for it, and even you are speaking on behalf of some unnamed other
> people.
> >
> > My concern is that if we’re specifying two curves, most implementations
> will implement both, and set the faster one as default or preferred. At
> some point, two things might happen.
> >
> > First, some flaw could be found in the lower curve that necessitates
> switching, but does not invalidate the whole class of curves. Because
> everyone implemented the stronger curve, everyone switches to using it. I
> think it’s important to have the stronger curve have good enough
> performance that server operators are not left with the choice of using a
> broken curve or having their servers crumble under the load of handshakes.
> IOW we should get as much work factor as we can without impacting the
> performance too much.
> >
> > Second, some government agency in some country or some group of auditors
> might decide to “turn the dial all the way to 11”, and mandate the stronger
> curve. This is not far-fetched. We’re already seeing auditors requiring
> AES-256, NIST P-384, and on occasion, RSA 4096 and IKE Diffie-Hellman group
> 18 (that’s 8192-bit FF DHE). For the unfortunate souls who have to deal
> with such auditors, we should treat the choice of the stronger curve as
> something that is likely to see actual use, not as some doomsday device
> that we keep locked away in the basement. Watson’s approach is along those
> lines, but doesn’t IMO go far enough.
>

---

From: Benjamin Black <[email-masked]>
Date: Tue, 4 Nov 2014 20:10:42 -0800

On Tue, Nov 4, 2014 at 2:46 PM, Michael Hamburg <[email-masked]> wrote:

> > Where is the formal performance model by which curves will be judged?
> Where is the evidence that sacrificing some security for small performance
> gains for some implementations on some benchmarks on some platforms is a
> reasonable trade-off?
>
> Consider the AES competition, or the SHA3 competition, or CAESAR or PHC.
> These were actual formally organized competitions which ran, or are
> running, for years.  They were concerned with performance on a variety of
> platforms, but none of them set a formal standard for the trade-off between
> performance and other metrics.  Just as in those settings, performance is
> just one metric to be used to compare the options.  It is not the last or
> only metric, but it is a useful one.
>
>
As I have argued from the start.

> Likewise, “rigidity” is an important metric, but it is also somewhat
> difficult to evaluate.  You certainly know this, having waffled from d =
> (1-) 78296 to d = 637608 for ed-512-mers; and having chosen a different
> E-521 from the three other groups who searched mod that prime; and having
> chosen the more dangerous incomplete twisted Edwards curves over untwisted
> Edwards for a very small performance gain.
>
>
"More dangerous" is a bit of hyperbole and I suggest whether a potential
reduction in security (and "more dangerous" here does not imply any such
reduction) in exchange for some performance is subjective, as we have
discussed for some time in the context of other candidates.

> > If you want to argue cycles per bit of security, even assuming a

> It isn’t.  We aren’t looking for the best possible curve, just the best
> choice available.  Curve25519 is nice because it’s fast, but also because
> it’s already trusted, implemented on many platforms, and widely deployed.
> Otherwise, it might work better to use some other curve and some other
> field, like I dunno, 2^256 - 2^194 - 1, or GF((2^127-1)^2), or maybe even
> something crazy like 2^250 - 26 * 2^200 - 1.
>
>
I've seen only presumption that the point of this process was to merely
select between a few existing curves. The request I read was for new curves
with no mention whatsoever of existing options. In this context, broad
implementation and "widely deployed", a vague term on which we disagree,
would point to continuing to use the NIST curves. If the NIST curves
falling short on trust is reason we are doing this, then that seems a very
important requirement which shouldn't be swept aside because it is
difficult to quantify.

>
> It’s a matter of threat model.  ECC does not degrade as much when stronger
> threat models are considered.  This means that time/memory/data/multikey
> threat models are a good reason to choose a stronger symmetric system, even
> if the existing one is WF128 secure against single-target attacks.  But
> they aren’t as good a reason to choose a stronger elliptic curve.  Just
> because AES-128 is only WF80 secure vs a strong threat model, doesn’t mean
> it’s OK to choose ECC which is only WF80 secure against an ordinary threat
> model.
>
>
I'm not actually arguing in favor of a WF80 curve, only pointing out the
absurdity of demanding performance dominate the decision process.

> It seems likely that WF80 was within the reach of intelligence agencies a
> decade ago or more (see suggestions involving a billion dollar factoring
> machine).  It is possible that in another couple decades, WF100 will be
> within reach.  Given that we are talking about new curves partially in
> reaction to Snowden, I think it should be a clear goal to be safely out of
> range of this sort of predictable progress for at least a couple decades.
> Perhaps WF110 is enough, but it seems reasonable to hedge to WF120+ since
> the performance cost is reasonable.  Note that the same argument doesn’t
> hold at all for 384 vs 448 vs 512: we don’t know what the attacks might
> look like there.
>
>
Again, good arguments in favor of finding something faster than 25519 to
minimize the performance impact of achieving the WF120 target you suggest.

> As for stronger symmetric ciphers, people do this.  For example, NaCl
> pairs Curve25519 with XSalsa20 or AES256GCM.
>
>
Both djb and djb do this? ;)

> You are welcome to propose a formal framework if you can argue that it
> accurately reflects reality.  Otherwise, please recognize that 2^512 is
> about as arbitrary as perf * log(curve size) ^ (1 + log2(3)).
>
>
A 3rd option is to recognize that matching the sizes of the most commonly
deployed curves (P256 and P384) is more rigid exactly because it is an
arbitrary choice made by others with no ability to directly manipulate this
process rather than an argument based on attacks which may or may not be
the best possible.

b

---

From: Mike Hamburg <[email-masked]>
Date: Tue, 04 Nov 2014 22:15:37 -0800

On 11/04/2014 08:10 PM, Benjamin Black wrote:
> On Tue, Nov 4, 2014 at 2:46 PM, Michael Hamburg <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     It isn’t.  We aren’t looking for the best possible curve, just the
>     best choice available.  Curve25519 is nice because it’s fast, but
>     also because it’s already trusted, implemented on many platforms,
>     and widely deployed. Otherwise, it might work better to use some
>     other curve and some other field, like I dunno, 2^256 - 2^194 - 1,
>     or GF((2^127-1)^2), or maybe even something crazy like 2^250 - 26
>     * 2^200 - 1.
>
>
> I've seen only presumption that the point of this process was to 
> merely select between a few existing curves.  The request I read was 
> for new curves with no mention whatsoever of existing options.
Oh, I see!  I read that as "new to TLS", not necessarily "newly 
generated".  I don't see any advantage to requiring the curve not to 
have been known before.  Is that actually the intention of this exercise?

We can, of course, choose requirements instead of curves.  But since at 
least 4 teams went and generated curves based on their favored 
requirements, whatever requirements we choose will probably have a 
proposed curve that satisfies them pretty well.  So it's pretty much the 
same thing.

Still, you may be right.  Maybe we'll pick requirements that an existing 
curve satisfies, but some other yet-ungenerated curve satisfies better, 
and some other team will find it.  I'm fine with that outcome, so long 
as we do all this in a reasonable amount of time.  Ideally this year.  
Generating curves with specific properties is usually a pretty quick 
exercise, so a time limit of a week or two after requirements should be 
fine, right?
> In this context, broad implementation and "widely deployed", a vague 
> term on which we disagree, would point to continuing to use the NIST 
> curves.  If the NIST curves falling short on trust is reason we are 
> doing this, then that seems a very important requirement which 
> shouldn't be swept aside because it is difficult to quantify.
I think that most of the community trusts Curve25519, and trusts at 
least some of its implementations.   I don't understand how being 
trusted can be a disadvantage.
>
>     ... it seems reasonable to hedge to WF120+ since the performance
>     cost is reasonable.
>
>
> Again, good arguments in favor of finding something faster than 25519 
> to minimize the performance impact of achieving the WF120 target you 
> suggest.
Go for it.  You might start with http://bench.cr.yp.to/results-dh.html.

WF128 curves are a very well-trodden area of research.  This is why I -- 
and I'm guessing DJB et al and Barreto et al -- didn't generate any 
WF128 curves for this round.  There are dozens of curves out there by 
dozens of authors, and Curve25519 is still regarded as generally a solid 
choice on pretty much any platform.  I suspect that if the requirements 
allow Curve25519, it will be a strong contender if not actually the best.

For example, a few years ago I benchmarked curves mod 2^252 - 2^232 - 1 
and 2^256 - 2^194 - 1.  They were a bit faster than 25519 on x86-64 and 
vectorless Cortex A9, but rather slower on NEON.  And there are 
definitely faster curves if you allow genus-2 or composite fields or 
endomorphisms.
>
>     You are welcome to propose a formal framework if you can argue
>     that it accurately reflects reality. Otherwise, please recognize
>     that 2^512 is about as arbitrary as perf * log(curve size) ^ (1 +
>     log2(3)).
>
>
> A 3rd option is to recognize that matching the sizes of the most 
> commonly deployed curves (P256 and P384) is more rigid exactly because 
> it is an arbitrary choice made by others with no ability to directly 
> manipulate this process rather than an argument based on attacks which 
> may or may not be the best possible.
>
> b
... and P521 too, right? Or is it not broadly-enough deployed to remove 
suspicion from the Mersenne prime?

-- Mike

---

From: Alyssa Rowan <[email-masked]>
Date: Thu, 06 Nov 2014 21:31:25 +0000

On 03/11/2014 09:10, Alyssa Rowan wrote:

> If we cannot make very clear choices, if we cannot make them very
> soon (e.g., early December/*before* Christmas), or if the choices
> we make aren't very good ones, implementers will just go and make
> their own choices.

A quick update along these lines: As you may have seen, GnuPG 2.1.0
just added the NIST curves, the Brainpool curves - and Ed25519.

If we do have any pertinent recommendations regarding elliptic curves,
then I really do think we ought to make them while they are relevant.

Or we could just wait for everyone else to pick Curve25519 as the
de-facto winner of ≈WF128 for us - that works too, and is in my view
the best choice in its class anyway.

- -- 
/akr