Subject: [Cfrg] A draft merging rpgecc and thecurve25519function.

From: Adam Langley <[email-masked]>
Date: Thu, 1 Jan 2015 14:00:28 -0800

Since everyone is agreed to within an isogeny of curve25519 at ~128
bits, and since there's no performance reason to pick one isogeny over
another (see my mail from yesterday), I've created an outline for what
currently appears (to me) to be the only way that we might reach
agreement.

It takes the generation procedure from draft-black-rpgecc-01,
generates the resulting curve with p=2^255-19 and then ends up with
curve25519 by pointing out that there's no difference in security
between isogenies and motivates it by compatibility with existing
practice.

Then it includes draft-turner-thecurve25519function in order to nail
down the wire-format and describe how to perform ECDH.

The resulting agglomeration is at
https://cdn.rawgit.com/agl/cfrgcurve/master/cfrgcurve.xml (requires
XSLT support in the browser) and https://github.com/agl/cfrgcurve.
(Although, until there's clarity on whether the outline is viable, the
details in the draft are unimportant.)

I have not listed the authors of the two source documents as authors
yet because that might suggest that they support the result. Instead
I've made the sources clear in section 1.

It does not suggest a signature scheme, despite several people
suggesting that it would be required in recent days, because I don't
think that we're at that point yet.

Cheers

AGL

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

---

From: Adam Langley <[email-masked]>
Date: Thu, 1 Jan 2015 15:31:39 -0800

On Thu, Jan 1, 2015 at 2:00 PM, Adam Langley <[email-masked]> wrote:
> XSLT support in the browser)

Tanja points out that that I had 2^255-19 as 3 mod 4. Getting rawgit
to serve XSLT and sorting out the caching is a real pain, so forget
that link and use
https://www.imperialviolet.org/cfrgcurve/cfrgcurve.xml instead. (Still
uses XSLT support in the browser.)

Cheers

AGL

---

From: Watson Ladd <[email-masked]>
Date: Thu, 1 Jan 2015 19:08:08 -0500

> uses XSLT support in the browser.)

Is it just me, or is this the draft I uploaded a couple weeks ago,
plus typos, and a section about an algorithm that gets used only to
have its result ignored? Should cat be a coauthor?

This is especially true when discussing the Edwards form at all, given
that we are talking about ECDH with the equivalent Montgomery form. If
we're going to use the NUMS generation algorithm (and we might as
well: it's what we've been doing all along now) over other primes,
then we should discuss the relation between the Edwards form and
Montgomery form, as otherwise the reader has no idea where the magic
numbers are coming from, or even why we are discussing Edwards form,
given that the presented algorithms don't use it.

I can't speak for my coauthors, but the above issues seem surmountable
with a bit of editing, and would give us a document that's easy to
extend when we select the higher strength prime.

Sincerely,
Watson

> _______________________________________________
> 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: Adam Langley <[email-masked]>
Date: Thu, 1 Jan 2015 16:51:18 -0800

On Thu, Jan 1, 2015 at 4:08 PM, Watson Ladd <[email-masked]> wrote:
> have its result ignored?

Is "the draft I uploaded a couple weeks ago" referring to
draft-turner-thecurve25519function-01? If so, then somewhat yes. (The
only other draft I see from you is draft-ladd-spake2 but it's quite
possible that I've missed something in all the recent emails.)

However, I don't agree that the algorithm is simply ignored. It's
clearly important to some that the generation algorithm be explicit
and transparent. Yes, it's odd that at the end we have to do an
arbitrary isogeny but I think the motivation for that is clear and
it's a "safe" step (i.e. we can't have hidden anything dodgy in there
to my knowledge.)

The algorithm could be written to reflect how curve25519 was
developed: i.e. that it output a Montgomery curve and then the twisted
Edwards is the obvious isomorphism from there (if needed). That might
well be clearer if we don't recommend any other curves.

But dealing with Edwards curves and having the algorithm generate them
makes it easier if we recommend another, or in the optimistic scenario
that we also end up specifying a signature scheme.

As far as making the wording clearer: lots of rewriting is called for
*if* this draft isn't dead-on-arrival.

(As an aside: does the existing algorithm output Curve41417,
Goldilocks or E-521 when given the corresponding prime? I suspect not
for Curve41417 since the curve/twist cofactors are {8,8} not {4,4}.
Goldilocks might work though.)

> Should cat be a coauthor?

If there's anyone I've left out, I'll add them immediately. And if
anyone wants to move from the "credit" section to the list of authors
I'll do that too. (The reason for not listing people as authors is in
section 1.)

Cheers

AGL

---

From: Adam Langley <[email-masked]>
Date: Thu, 1 Jan 2015 17:16:33 -0800

> that we also end up specifying a signature scheme.

I think I've fallen into the "details" trap in that reply.

However the generation is structured to make it most clear, and
whether or not we mention (twisted) Edwards curves, I think that the
important point is this:

Unless the chairs believe, and state within weeks, that we can move
forward with something shaped like this draft (whether it's based on
it or not) then I don't think that this RG will be able to recommend
any specific curves. I don't think anything will be more generally
agreeable.

If we can't recommend curves then the best that we might be able to do
is to put out a document that states the requirements for safe
elliptic curves and mentions that curve25519, curve25519-isogeny,
41417, Goldilocks, E-521, etc are all fine, cryptographically. Then
other WGs will have to do the picking.

Cheers

AGL

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 1 Jan 2015 18:17:19 -0800

> think that we're at that point yet.

I was one of those folks, and a few folks off-list walked me through why I was incorrect when I said it was needed for TLS. I want a signature scheme for EC, and I would prefer that it have better operational security properties than ECDSA. If we can get agreement on that soon, great, but if not, it should not deter CFRG from giving the TLS WG a 128-strength solution.

--Paul Hoffman

---

From: Mike Hamburg <[email-masked]>
Date: Fri, 02 Jan 2015 03:12:27 -0800

> Goldilocks might work though.)
I believe that Goldilocks and E-521 come out of this procedure; the 
twist of Ridinghood comes out (because I restricted my parameters to #E 
< #E'); and Curve41417 does not come out because it has cofactor 8.  
These all have different generators from the Safecurves site, but that 
doesn't really matter because nobody has deployed implementations AFAIK.

Section 6.1 is fine in terms of "let's be clear that this is the 
simplest safe thing".  But you may want to switch the conditions for 
clarity/simplicity/speed.  In particular, I think only negative d can 
come out of 6.1.  Also cofactor 4 and twist cofactor 4 imply d nonsquare 
and 1-d nonsquare, so you can remove the one condition or add the other 
if you want.

Happy 2015,
-- Mike

---

From: Brian Smith <[email-masked]>
Date: Fri, 2 Jan 2015 04:04:12 -0800

Adam Langley <[email-masked]> wrote:
> I've created an outline for what currently appears (to me) to
> be the only way that we might reach agreement.

As far as Curve25519 is concerned, whether or not agreement is reached
within CFRG seems to not matter any more, because Curve25519 is
already clearly the choice at the 128-bit security level, and it is
also now the default choice if no agreement is reached. It's already
implemented and documented elsewhere so no new CFRG document is even
really needed for it, though it would be nice to have one.

It isn't clear that it is best to restrict the choices in the stronger
security levels to the generation procedure in this document. More
importantly, that isn't something that needs to be decided before
everybody can move forward with Curve25519.

There are a lot of people that don't care much about the curves
stronger than Curve25519 and who don't intend to implement them. The
problem with your suggested approach is that all these people are
likely to join in support of this document in order to ensure
Curve25519 move forward, causing the people that *do* care about the
higher-security curves to get steamrolled, even if they have a
stronger case. In other words, politics would trump technical
arguments. That's bad.

Consequently, CFRG should wrap up the process for Curve25519, and
separately decide what to do at the higher security levels. This would
more likely ensure that the better technical choices are made at the
higher security levels. This makes sense because the urgency for
Curve25519 is notably higher than the urgency for the other security
levels.

It does seem reasonable to say that, before a curve that doesn't
result from the generation procedures is chosen at a higher security
level, there should be a clear, strong justification for that choice.
But, I don't think we should exclude the possibility of such a strong
justification existing for some curve(s). Further, I don't think we
should exclude the possibility of the generation procedure being
tweaked again, like when it was tweaked to make Curve25519 fit.

Cheers,
Brian

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 02 Jan 2015 19:31:20 +0000

(Speaking as a random RG participant, not as an IESG member...)

I just had a quick read of that, and while I'm not qualified
to judge all the details this seems like a fine text to me
and also seems to me to meet what I understand are the main
reasonable constraints that folks have expressed.

I'm sure the RG could figure out how to split that text into
multiple documents easily enough when considering how to deal
with other security levels so I don't think Brian's concern
is a showstopper (his concern is one that needs to be dealt
with I agree).

If the chairs were able to determine if the RG had reached
rough consensus on the meaty content of [1], but that there
is still work to be done, then I think we'd have made
significant progress.

Cheers,
S.

[1] https://www.imperialviolet.org/cfrgcurve/cfrgcurve.xml

---

From: Alexey Melnikov <[email-masked]>
Date: Mon, 05 Jan 2015 18:38:04 +0000

On 02/01/2015 01:16, Adam Langley wrote:
> it or not)
Chairs believe that your draft is a very reasonable compromise  (in IETF 
sense, not in security sense) between technically sound proposals and 
will initiate Last Call on acceptance of your document as a starting 
point for CFRG document shortly.
> then I don't think that this RG will be able to recommend
Agreed.
> other WGs will have to do the picking.
Indeed. This outcome would be suboptimal (IMHO), but still a bit better 
than "no consensus on anything in CFRG".