Subject: Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Consensus and a way forward]

From: Adam Langley <[email-masked]>
Date: Mon, 1 Dec 2014 06:17:07 -0800

On Sun, Nov 30, 2014 at 7:33 PM, Robert Ransom <[email-masked]> wrote:
> Third, you appear to be arguing that ECDH operations would not use the
> Montgomery curve *isomorphic* to the Edwards curve in your Internet
> draft, but use a *different* Montgomery curve (PinkBikeShed) which is
> merely *isogenous* to the curve that you are proposing, in order to
> reduce the modifications required to make the many existing
> independent, interoperable implementations of Curve25519 operate on
> your curve.  This would *slightly* reduce the technical disadvantage
> of your proposal compared to Curve25519, but would clearly not
> eliminate it.  If you do intend to propose PinkBikeShed for ECDH,
> rather than the Montgomery curve isomorphic to the one specified in
> your Internet draft, then that needs to be stated explicitly in your
> draft.

Yes, I agree. The draft should specify the Montgomery curve and the
isogeny maps. I also very much hope that the CFRG doesn't just specify
curves, but also will provide detailed guidance about their use --
that's also missing from the draft at the moment.

> Interesting suggestion.
>
> Both 89747 and 121665 are 17 bits long (they are between 2^17 and 2^18
> - 1), and 89747 has a slightly greater Hamming weight than 121665 (10
> rather than 9); I would expect any performance improvement on due to
> that change in curve parameter to be quite small and only applicable
> to a very few implementation strategies.  Have you done any
> benchmarking to quantify the performance improvement that you are
> claiming as a technical benefit of PinkBikeShed?

I've not done any benchmarking, it's just a guess. But the Edward's d
parameter for the curve isomorphic to Curve25519 isn't 121665, it's
+/- 121665/121666 [http://eprint.iacr.org/2007/286.pdf, section 2].
That value doesn't have a small representation so I think that the
PinkBikeShed curve does get to use a multiplication by a small
constant in place of a multiplication by a large constant. That might
be a small help.

> Do you believe that that possible performance improvement is a
> sufficiently large technical benefit over Curve25519 to outweigh the
> technical disadvantages of your proposal that you were aware of at the
> time that you submitted it?

No. I think the prevalence of Curve25519 alone is enough that the CFRG
should adopt it. PinkBikeShed isn't what I want, but it's close and
it's something that I can live with in order to move forward.

Cheers

AGL

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

---

From: "Lochter, Manfred" <[email-masked]>
Date: Mon, 1 Dec 2014 17:27:29 +0100

+1

__________ ursprüngliche Nachricht __________

Von:		Joppe Bos <[email-masked]>
Datum:	Donnerstag, 27. November 2014, 07:17:32
An:		"[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>
Kopie:	
Betr.:	Re: [Cfrg] Consensus and a way forward

> This draft presents algorithms to “generate domain parameters at any
> security level for modern (twisted) Edwards curves” given as input prime.
> In the Test Vectors section curves defined over primes of a special shape
> are given. Please note that one can also use this draft to select curves
> which are defined over primes which do not have a special shape: something
> which has been requested by different people on this list. I hope that we
> will use this draft to (also) select curves over primes which do not have a
> special shape to accommodate all the needs in the cryptographic (and wider
> security) community.
>
> Best regards,
>
> Joppe
>
>
>
> From: Cfrg [mailto:[email-masked]] On Behalf Of Benjamin Black
> Sent: Thursday, November 27, 2014 5:25 AM
> To: [email-masked]
> Subject: [Cfrg] Consensus and a way forward
>
>
>
> All,
>
>
>
> Over the past couple of weeks we have been working with Adam Langley to see
> if we could find a compromise with which we could all live. I'm pleased to
> say we have been successful in accommodating our respective performance and
> trustworthy generation concerns, and I hope the resulting proposal will be
> attractive to others, as well. The generation procedure is document in a
> draft I've just posted that can be found at
> http://www.ietf.org/id/draft-black-rpgecc-00.txt .
>
>
>
> The simplest summary is that we have combined the prime preferred by Adam
> and others at the 128-bit security level with the rigid parameter
> generation we view as essential for producing the most trustworthy curves.
> We have used the generation procedure to produce a new twisted Edwards
> curve based on 2^255 - 19 and a new Edwards curve based on 2^384 - 317.
> These new curves are given as test vectors in the draft, and are also given
> below.
>
>
>
> These 2 curves are sufficient for meeting the request from TLS. However, if
> there is strong interest in a 3rd curve for the 256-bit security level, the
> generation procedure​​ gives the same curve with p =2^521 - 1 as several
> teams produced.
>
>
>
>
>
> b
>
>
>
> --
>
>
>
> 2^255 - 19
>
>
>
>    p = 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
>
>          FFFFFFFFFFED
>
>    d = 0x15E93
>
>    r = 0x2000000000000000000000000000000016241E6093B2CE59B6B9
>
>          8FD8849FAF35
>
> x(P) = 0x3B7C1D83A0EF56F1355A0B5471E42537C26115EDE4C948391714
>
>          C0F582AA22E2
>
> y(P) = 0x775BE0DEC362A16E78EFFE0FF4E35DA7E17B31DC1611475CB4BE
>
>          1DA9A3E5A819
>
>    h = 0x4
>
>
>
>
>
> 2^384 - 317
>
>
>
>      p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
>
>            FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC3
>
>      d = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
>
>            FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD19F
>
>      r = 0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE2471A1
>
>            CB46BE1CF61E4555AAB35C87920B9DCC4E6A3897D
>
>   x(P) = 0x61B111FB45A9266CC0B6A2129AE55DB5B30BF446E5BE4C005763FFA
>
>            8F33163406FF292B16545941350D540E46C206BDE
>
>   y(P) = 0x82983E67B9A6EEB08738B1A423B10DD716AD8274F1425F56830F98F
>
>            7F645964B0072B0F946EC48DC9D8D03E1F0729392
>
>      h = 0x4

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

Postfach 20 03 63
53133 Bonn

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

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 1 Dec 2014 19:53:44 +0200

> constant in place of a multiplication by a large constant. That might

The isogeny that lets one in effect have small d and a24 at the same time
also exists for Curve25519.

AFAICT:

Complete Twisted Edwards curve:

-x^2+y^2=1+121665x^2*y^2 (mod 2^255-19)

With base point:

x=8343919484931660353238246604028044872330114539683257561218125599081866236258
y=10591048728587107161910258178281284043396286849160988064050992288107790236293

Mapped by:
u = -y^2/x^2
v = y*(-x^2+y^2-2)/(i*x^3)

Where (square root of -1):
i=38214883241950591754978413199355411911188925816896391856984770930832735035197

Maps to complete Montgomery curve:

v^2 = u^3 + 486662 * u^2 + u  (mod 2^255-19)

With base point:

u=9
v=14781619447589544791020593568409986887264606134616475288964881837755586237401

Mapped by:
w=u+19298681539552699237261830834781317975544997444273427339909597334652188435537

Maps to Weierstrass curve v^2=w^3+a*w+b:
a=19298681539552699237261830834781317975544997444273427339909597334573241639236
b=55751746669818908907645289078257140818241103727901012315294400837956729358436

With base point:
w=19298681539552699237261830834781317975544997444273427339909597334652188435546
v=14781619447589544791020593568409986887264606134616475288964881837755586237401

All the curves have base order of:
7237005577332262213973186563042994240857116359379907606001950938285454250989

The middle curve and base point match Curve25519 data from Safecurves after
changing variable names (x,y)->(u,v).

The v(x,y) formula looks messy, but for single-coordinate Montgomery, one only
needs u(x,y), which is reasonably fast. And looks like one can compute v(x,y)
together with u(x,y) pretty cheaply (few extra multiplications and additions).

The reverse maps x(u,v) and y(u,v) are more annoying, seemingly containing
two square roots and an inversion (among with few other ops).

-Ilari

---

From: Robert Ransom <[email-masked]>
Date: Mon, 1 Dec 2014 10:06:05 -0800

> two square roots and an inversion (among with few other ops).

That's because the map you are using is an isogeny, not an
isomorphism.  You don't compute a point's pre-image under an isogeny,
you get back to the original curve by applying the ‘dual isogeny’
(another rational map).  This isogeny (which I'll denote F for a
moment) is a 4-isogeny, so there is a dual isogeny G such that G(F(P))
= 4*P.

Robert Ransom

---

From: Benjamin Black <[email-masked]>
Date: Mon, 1 Dec 2014 16:18:33 -0800

Several of the responses to this proposal leave me a bit confused as it
appears they were written without having read the draft. If your
perspective is that Curve25519 must be adopted, and under no circumstances
will alternatives be considered, then it will be difficult to reach an
accommodation. If instead you are interested in achieving consensus, the
first step should be understanding alternative viewpoints and considering
how we might find a middle ground. The draft documents such a middle ground.

The draft we (Microsoft, Google and NXP) posted describes rigid generation
of parameters for (twisted) Edwards curves. The generation process is about
as minimalist as can be for generation of secure curves. Additional rules
intended to produce a specific outcome are the definition of flexibility.
Constructing a curve explicitly for a specific implementation technique is
a short-sighted and contrary to good engineering process.

In addition, having a clear, rigid generation process for the parameters
allows those in need of curves for specific applications to easily and
deterministically produce them. Several people involved in hardware
implementation have expressed their concern with only producing curves
based on special primes. For such scenarios, a random prime selection
section could be added to the draft and the resulting curves need not find
their way into TLS at all. Again, being creative in accommodating the needs
of the participants is the key to consensus.

Recall that our preference was for similarly rigid generation of 3 mod 4
special primes. We still hold that preference, but we believe so strongly
in finding a middle ground acceptable on performance and security that we
have agreed to a process that does not produce most of the "NUMS" curves
and does not include our preferred prime at the 256-bit level. p = 2^255 -
19 with rigidly generated parameters is that performant and secure middle
ground.

The generated curve for p = 2^255 - 19 is not Curve25519 and is not
isogenous to the Montgomery curve in X25519. It is, however, not vulnerable
to the extremely minor concern that a private key is a multiple of the
group order. The isogenous minimum A Montgomery curve does have that
concern, and as has already been mentioned it is a trivial problem with a
trivial solution. Those working with signatures or ECDH with x,y points,
which are the majority of scenarios outside TLS ECDH via X-only point
format (and associated Montgomery isogeny), don't need to worry about it at
all.

As some have noted, this new curve can actually be faster than Curve25519.
Preliminary benchmarking of our implementation of it bears that out. It is
unfortunate that, having argued at great length for the primacy of
performance in selection, people are rejecting similar performance gains
because some code has already been deployed or multiplying by 8 instead of
4 represents a security threat.

We were expecting implementation considerations, such as requiring use of
compressed points for x,y and x-only for ECDH at the 128-bit security
level, to be addressed in another draft. That would decouple the generation
draft from the needs of a specific working group or scenario.

There is no perfect answer, there are only acceptable arrangements of trade
offs. To echo Adam, this is something we can live with to move forward.

b

---

From: Watson Ladd <[email-masked]>
Date: Mon, 1 Dec 2014 17:56:37 -0800

On Mon, Dec 1, 2014 at 4:18 PM, Benjamin Black <[email-masked]> wrote:
> appears they were written without having read the draft. If your perspective
> is that Curve25519 must be adopted, and under no circumstances will
> alternatives be considered, then it will be difficult to reach an
> Constructing a curve explicitly for a specific implementation technique is a
> short-sighted and contrary to good engineering process.

To reach that middle ground you changed the generation procedure from
the initial draft to match E-521. Professor Bernstein has pointed out
that there is an (admittedly minor) security related reason why he
rejected PinkBikeShed. Why not add this criterion to the generation
method? You already did it to get the right curve modulo 2^521-1 after
all. You also changed the choice of primes. Why not change the choice
of prime near 2^384 as well?

Were the initial parameters not rigid, or are these new parameters less rigid?

> implementation have expressed their concern with only producing curves based
> on special primes. For such scenarios, a random prime selection section
> could be added to the draft and the resulting curves need not find their way
> into TLS at all. Again, being creative in accommodating the needs of the
> participants is the key to consensus.

What do random primes have to do with anything related to the request
from the TLS WG, particularly if we don't recommend them for TLS?

> special primes. We still hold that preference, but we believe so strongly in
> finding a middle ground acceptable on performance and security that we have
> agreed to a process that does not produce most of the "NUMS" curves and does
> not include our preferred prime at the 256-bit level. p = 2^255 - 19 with
> rigidly generated parameters is that performant and secure middle ground.

What about the 384 bit level, where the choice made in the draft is
not a middle ground between performance and (mythical) security, but
rather to favor a rather poor choice of prime? This was a clearly
political exercise.

> to the extremely minor concern that a private key is a multiple of the group
> order. The isogenous minimum A Montgomery curve does have that concern, and
> as has already been mentioned it is a trivial problem with a trivial
> solution. Those working with signatures or ECDH with x,y points, which are
> the majority of scenarios outside TLS ECDH via X-only point format (and
> associated Montgomery isogeny), don't need to worry about it at all.
>
> because some code has already been deployed or multiplying by 8 instead of 4
> represents a security threat.

I'm having trouble seeing how a change between constants of roughly
the same size can lead to a 10-15% performance gain. What I can see is
how an implementor can compare a highly optimized implementation of
one curve to a less-well optimized implementation of another, then
make a claim about the curves.

Unless the benchmarking code is made publicly available, I'm skeptical
of such claims.

Sincerely,
Watson Ladd

---

From: Tony Arcieri <[email-masked]>
Date: Mon, 1 Dec 2014 18:27:41 -0800

On Mon, Dec 1, 2014 at 4:18 PM, Benjamin Black <[email-masked]> wrote:

> accommodation.

Can you please respond to djb's concerns about twist security?

> If instead you are interested in achieving consensus, the first step
> should be understanding alternative viewpoints and considering how we might
> find a middle ground. The draft documents such a middle ground.
>

The draft overlooks djb's concerns. At the very least it should give a
counterpoint to djb's arguments.

-- 
Tony Arcieri

---

From: Benjamin Black <[email-masked]>
Date: Mon, 1 Dec 2014 21:06:15 -0800

The concerns do not apply to the twisted Edwards curve we generated, only
to the isogenous Montgomery curve. If one insists on using the Montgomery
ladder and on clearing cofactors, which is not required for ECDH, then
multiplication by 8 is the simplest answer. Note that X25519 also has
specific guidance about its use in non-DH protocols and failing to heed it
results in security problems. There is no free lunch.

My counterpoint is that all of this complexity is introduced by insisting
on the use of the ladder. Instead of debating how to hack around the
problems that introduces, use the twisted Edwards curve. It is extremely
fast and has far fewer sharp edges.

---

From: Alyssa Rowan <[email-masked]>
Date: Tue, 02 Dec 2014 07:59:39 +0000

On 02/12/2014 00:18, Benjamin Black wrote:

> If your perspective is that Curve25519 must be adopted, and under
> no circumstances will alternatives be considered, then it will be 
> difficult to reach an accommodation.

That's an odd position, given the extremely close similarity between
PinkBikeShed and Curve25519. Why is that?

On what TECHNICAL ground do you believe PinkBikeShed is superior?

On what SECURITY ground do you reject Curve25519?

What's the blocker for you? Why are you refusing to consider it?
Please answer, clearly.

Because even agl, a co-author of your draft, clearly believes that
what you propose is not the best choice. And if it's clearly not the
best choice, we shouldn't choose it.

If you cannot answer those questions, then it will be difficult to reach
an accommodation.

I think you're wrong; that you're simply unwilling to admit you're
wrong; and you want to compromise on some kind of frankencurve to save
face. But with the greatest respect, your ego has sod all to do with
this. I am unwilling to compromise the quality of cryptography on the
internet to save your ego. Design by committee has always been a very
bad call.

I believe that we will be able to find a rough consensus, and we
certainly have running code, for Curve25519. Pick that one.

I believe that will absolutely not be the case with your proposal.

It is for the chairs to call for consensus: I will leave that to them.

- -- 
/akr

---

From: "D. J. Bernstein" <[email-masked]>
Date: 2 Dec 2014 09:28:47 -0000

Benjamin Black writes:
> The concerns do not apply to the twisted Edwards curve we generated, 
> only to the isogenous Montgomery curve. 

False.

Invalid-curve attacks completely break the simplest DH implementations
in Montgomery coordinates _and_ in Edwards coordinates. Rather than
blaming the implementor, we eliminate these security failures by

   * adding twist security, for both Montgomery and Edwards, and
   * switching to single-coordinate ladders.

This is the primary motivation for twist security (and a closer look,
as I've explained in detail, shows a twist-security criterion that's met
by Curve25519 and not by PinkBikeShed). This has nothing to do with the
superficial differences between the Montgomery x and the Edwards y, both
of which support ladders.

If you disagree, please explain why you're requiring _any_ type of twist
security for Edwards curves. Why aren't you saying something like "The
larger d forced by 'twist security' is a violation of rigidity" and
objecting to the whole concept of twist security for Edwards curves?

---Dan

---

From: Robert Ransom <[email-masked]>
Date: Tue, 2 Dec 2014 23:13:22 -0800

On 12/1/14, Adam Langley <[email-masked]> wrote:
> isogeny maps.

You are listed as a co-author of the draft.  If you believed that
those pieces of information should be included in it, why did you not
include them into the draft?

> I also very much hope that the CFRG doesn't just specify

The previous proposal draft-turner-thecurve25519function-01 includes a
complete statement of the Montgomery ladder.  It was submitted ‘in
full conformance with the provisions of BCP 78 and BCP 79’, and does
not include any notice forbidding modifications to it.  Thus, other
IETF participants -- including you -- are permitted to copy text from
that draft into other Internet drafts.  Why did you not include that
description of the Montgomery ladder into the draft that you
co-authored?

Your co-authors wrote a paper (listed as one of the draft's
references) which specifies algorithms to perform several
scalar-multiplication tasks.  Did you ask them to provide plain-text
descriptions of those algorithms for inclusion in the draft itself?

> constant in place of a multiplication by a large constant. That might

In order to claim that your proposal only requires changing the
curve-parameter constant (A - 2)/4 from one small integer to another
in an existing Curve25519 implementation, you proposed to use the
Montgomery curve with A=358990 (i.e. PinkBikeShed) for ECDH.
PinkBikeShed is isomorphic to an Edwards curve with d equal to a ratio
of small integers, exactly like Curve25519.

Both Curve25519 and PinkBikeShed are *isogenous* to Edwards curves
with small-integer d; neither of them is *isomorphic* to one.

> it's something that I can live with in order to move forward.

Do you believe that there is *any* benefit (technical, procedural, or
otherwise) in further consideration of the draft that you co-authored,
draft-black-rpgecc-00, over the previously submitted
draft-turner-thecurve25519function-01?

Robert Ransom

---

From: Benjamin Black <[email-masked]>
Date: Mon, 8 Dec 2014 13:56:59 -0800

>of which support ladders.

The additional criterion you are describing is difficult to see as "twist
security". The curves in the draft are twist secure by any reasonable
definition, including your own SafeCurves twist security requirements.
Looking at your Curve25519 paper there is a single mention of requirements
on cofactors: "Multiply the secret key by a small power of 2 to account for
cofactors in the curve group and the twist group". There is no reading of
this that indicates selection of (8,4) is needed or was even a
consideration at the time. In the recent Curve41417 paper I similarly find
a single mention of cofactor requirements: "For security we ... insist on
the same level of twist-security as Curve25519 — the cofactors of the curve
and its twist are in {4, 8}." No mention of either requiring the cofactors
be equal or that they be minimal (which they aren't).

Suggesting that (4,8) vs (8,4) introduces security risk is not a technical
argument about the strength of the curve. A sloppy implementor could just
as easily misread guidance and clear cofactor 4 on Curve25519. A sloppy
implementor could even more easily skip checks for weak keys when using
Montgomery Curve25519 outside of DH. All Curve25519 documentation makes
clear all 32-byte strings are valid keys. That this is so only for DH is
easily forgotten and I've not found a Curve25519 implementation that
performs the required check.

Further, using p = 1 mod 4 primes introduces the concern you are raising.
Rather than blaming the implementor for clearing the "wrong" cofactor, we
can eliminate this "security failure" by using p = 3 mod 4 to ensure the
cofactors are equal, which is the choice you made for both Curve1174 and
Curve41417. Looking to SafeCurves rigidity criteria we see Curve1174
described with "Curve and twist orders chosen as {4*prime,4*prime} for
security", but for Curve25519 we see "Curve and twist orders required to be
{4*prime,8*prime} for security". Once again, no indication that (8,4) is
required.

Looking through all the curves you list, we see a wide variety of
justifications for any given choice, with qualitative comments about
"security", "performance", or "efficiency", but little consistency in the
results:

Curve1174: "Curve and twist orders chosen as {4*prime,4*prime} for security"
Curve25519: "Curve and twist orders required to be {4*prime,8*prime} for
security"
Curve41417: "Curve and twist cofactors limited to {4,8} for security"

Curve1174: "Edwards curve shape x^2+y^2=1+dx^2y^2 chosen for efficiency."
Curve25519: "Montgomery curve shape y^2=x^3+Ax^2+x chosen for efficiency"
Curve41417: "Edwards curve shape x^2+y^2=1+dx^2y^2 chosen for efficiency"

Curve1174: "Complete Edwards curve chosen for security."
Curve25519: No such statement.
Curve41417: "Complete Edwards curve chosen for security."

It is difficult to see this as rigidity.

I do not agree with your assertion that "adding twist security" _and_
"switching to single-coordinate ladders" is the solution against security
failures when it comes to invalid-curve attacks. Windowing implementations
on complete Edwards curves can be implemented securely and eliminate any
risks against those attacks. So it is correct to say that in practice "the
concerns do not apply to the twisted Edwards curve we generated, only to
the isogenous Montgomery curve". In fact, looking at the Curve41417 paper,
you eschew the Montgomery (or Edwards) ladder in favor of windowing. In
this case, the performance advantages of Edwards trump the irrefutable and
essential requirement for eliminating "security failures" above via use of
single-coordinate ladders. Obviously, single-coordinate ladders are not a
hard requirement.

>objecting to the whole concept of twist security for Edwards curves?

I am not objecting to twist security and the curves in the draft are twist
secure. I am objecting to the notion that cofactors (8,4) are in any way
more secure than (4,8). Your own statements on SafeCurves and in the
Curve25519 and Curve41417 papers support there being no difference. I am
also objecting to your repeated claims, contradicted by your own work, that
single-coordinate ladders are required. And since there is no such
requirement and no security difference, I want the curve generated via the
process with fewest qualitative, opinion-based constraints.

b

On Tue, Dec 2, 2014 at 1:28 AM, D. J. Bernstein <[email-masked]> wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Watson Ladd <[email-masked]>
Date: Mon, 8 Dec 2014 18:58:55 -0800

On Mon, Dec 8, 2014 at 1:56 PM, Benjamin Black <[email-masked]> wrote:
> this that indicates selection of (8,4) is needed or was even a consideration
> at the time. In the recent Curve41417 paper I similarly find a single
> mention of cofactor requirements: "For security we ... insist on the same
> level of twist-security as Curve25519 — the cofactors of the curve and its
> twist are in {4, 8}." No mention of either requiring the cofactors be equal
> or that they be minimal (which they aren't).

All DJB is saying is that a PinkBikeShed implementation using the
Montgomery ladder, which doesn't validate points, and clears the low 2
bits, not 3, leaks one additional bit, whereas a Curve25519
implementation will not.

> argument about the strength of the curve. A sloppy implementor could just as
> easily misread guidance and clear cofactor 4 on Curve25519. A sloppy

Have you seen implementations that don't deal only with DH? A protocol
that requires points to be torsion points would need implementations
that do check, and PinkBikeShed doesn't change this property.

> It is difficult to see this as rigidity.

Put "BADA55ECC" into the hexadecimal constants of a curve selected by
the methodology DJB used to pick Curve25519. It's easy to see that
Microsoft had equally substantial freedom to manipulate it's curve
choice, as shown by the fact that the new generation method produces
the same curve modulo 2^521-1.

Most of the reduction in DOF comes from requiring minimal parameters
for some reasonable model subject to some reasonable criteria,
together with forcing primes of the form 2^s-c. Arguing that one
choice is "more rigid" than another is aesthetics.

> concerns do not apply to the twisted Edwards curve we generated, only to the
> isogenous Montgomery curve". In fact, looking at the Curve41417 paper, you
> eschew the Montgomery (or Edwards) ladder in favor of windowing. In this
> case, the performance advantages of Edwards trump the irrefutable and

The same is true for short Weierstrass curves. But I don't see why the
choices a particular implementation, written very carefully by experts
in the field, reduces the impact of traps for the nonexperts who write
the majority of implementations.

By requiring twist security, we've already chosen to support
single-coordinate ladders. If a check was enough, twist security would
not be required. Why not design the ladder in such a way to never leak
bits? Given that we are using cofactor multiplication to ensure that
matching test vectors is enough, we will have to multiply by
2*cofactor for PinkBikeShed to have the same security.

> process with fewest qualitative, opinion-based constraints.

-Some people think twist security is not required
-Some people think cofactor 1 is required
-Some people think we need to specify short Weierstrass curves
-Some people think we need random primes
-Some people think we should keep c small and vary s in 2^s-c.

While debating the fate of a single bit might be far less
controversial than the above, I don't see how it is more or less a
qualitative constraint then the others, some have which been accepted
by the NUMS group, and some of which have not.

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

---

From: "Paterson, Kenny" <[email-masked]>
Date: Fri, 12 Dec 2014 10:13:31 +0000

Dear Ben,

Thanks for your continued contributions to this discussion. I think you
make quite powerful arguments for keeping  draft-black-rpgecc-00 the way
it is and not adding an extra criterion concerning divisibility of
co-factors.

Nevertheless, based on previous discussions on list (and discussions off
list that Alexei and I have been having in our role as co-chairs), we have
reason to believe that we will have a strong chance of making progress as
a group, and unblocking our current logjam, if your team were to add this
criterion to the draft.

If you were also to add explicit isogenies enabling mapping to Montgomery
form curves for the specific primes/curves at the 128-bit and 192-bit
security levels, then this would also help move things along too.

As co-chairs, then, we would like to strongly recommend that your team
take these two significant steps to modify your draft. Modulo my
understanding of IRTF processes, we would then be in a position to call
for consensus on formal adoption of the draft by CFRG.

As a side note to *everyone* who has been contributing to our discussions
to date: we are rapidly getting to the point where the process might well
be taken away from us and solutions imposed from outside. CFRG's inability
to reach a decision will not stand us in good stead as the preferred
supplier of "crypto clue" to IETF.

Regards,

Kenny   

On 09/12/2014 05:56, "Benjamin Black" <[email-masked]> wrote:

>Looking at your Curve25519 paper there
> is a single mention of requirements on cofactors: "Multiply the secret
>key by a small power of 2 to account for cofactors in the curve group and
>the twist group". There is no reading of this that indicates selection of
>(8,4) is needed or was even a consideration
>level of twist-security as Curve25519 ‹ the cofactors of the curve and
>its twist are in {4, 8}." No mention of either
> requiring the cofactors be equal or that they be minimal (which they
>aren't).
>
>
>Suggesting that (4,8) vs (8,4) introduces security risk is not a
>technical argument about the strength of the curve. A sloppy implementor
>could just as easily misread guidance and clear cofactor 4 on Curve25519.
>A sloppy implementor could even more easily
> skip checks for weak keys when using Montgomery Curve25519 outside of
>DH. All Curve25519 documentation makes clear all 32-byte strings are
>valid keys. That this is so only for DH is easily forgotten and I've not
>found a Curve25519 implementation that performs
> the required check.
>
>
>cofactors are equal, which is the
> choice you made for both Curve1174 and Curve41417. Looking to SafeCurves
>rigidity criteria we see Curve1174 described with "Curve and twist orders
>chosen as {4*prime,4*prime} for security", but for Curve25519 we see
>"Curve and twist orders required to be {4*prime,8*prime}
> for security". Once again, no indication that (8,4) is required.
>
>
>failures when it comes to invalid-curve attacks. Windowing
>implementations on complete Edwards curves can be
> implemented securely and eliminate any risks against those attacks. So
>it is correct to say that in practice "the concerns do not apply to the
>twisted Edwards curve we generated, only to the isogenous Montgomery
>curve". In fact, looking at the Curve41417 paper,
>this case, the performance advantages of Edwards trump the irrefutable
>and essential requirement for eliminating "security failures" above via
>use of single-coordinate ladders. Obviously,
> single-coordinate ladders are not a hard requirement.
>
>
>I am not objecting to twist security and the curves in the draft are
>twist secure. I am objecting to the notion that cofactors (8,4) are in
>any way more secure than (4,8). Your own statements on SafeCurves and in
>the Curve25519 and Curve41417 papers support
> there being no difference. I am also objecting to your repeated claims,
>contradicted by your own work, that single-coordinate ladders are
>required. And since there is no such requirement and no security
>difference, I want the curve generated via the process
> with fewest qualitative, opinion-based constraints.
>
>
>
>
>b
>
>
>
>
>
>

---

From: Alyssa Rowan <[email-masked]>
Date: Fri, 12 Dec 2014 11:29:49 +0000

On 12 December 2014 10:13:31 GMT+00:00, "Paterson, Kenny" <[email-masked]> wrote:

>…we have reason to believe that we will have a strong chance of making progress as a group, and unblocking our current logjam, if your team were to add this criterion [divisibility of co-factors] to the draft.

>If you were also to add explicit isogenies enabling mapping to Montgomery form curves for the specific primes/curves at the 128-bit and 192-bit security levels, then this would also help move things along too.

As per my previous statements on and off the list, I support these two suggestions, and I also think that would be a sensible way to move forward overall.

- --
/akr

---

From: Watson Ladd <[email-masked]>
Date: Fri, 12 Dec 2014 17:15:13 -0800

> for consensus on formal adoption of the draft by CFRG.

Why can't the turner-curve25519 draft be adopted? We could add the
curves for the 2^389-21 prime that Ilari has computed. As one of the
coauthors I'm surprised that no discussion of the shortcomings of this
draft, has taken place, instead we've been modifying a draft that was
further from being useful until it can be adopted.

I'm also surprised that we aren't using 2^389-21 for the same reasons
cited for using 2^255-19. We do not need complete agreement to go
forward. If we want a consensus result we'll still have gratuitous
incompatibilities and an unforced loss of additional performance, in
order to get one particular group on board. A process justified as
being driven by technical criteria has devolved into an openly
political horse trade, where we're supposed to be happy that the
2^255-19 prime is used, and ignore the issues with 2^384-317.

I'm happy to assist in writing whatever material is required to
specify the algorithms that we need to produce, such as a signature
algorithm and standalone description of the key exchange method.
Existing drafts and RFCs have fallen short here in the past. I can
only hope this does not take another 9 months.

> supplier of "crypto clue" to IETF.

Honestly, if the past 9 months is the best we can do, we deserve it.
(Not that the IETF works much better: the codec debate in RTCweb,
etc.) It would be a shame if the result was no clue in the IETF at
all, and I hope that we can figure out a way to make the CFRG more
effective.

While this conversation was going on I caught yet another draft with a
crypto problem, which got fixed. The authors had probably not realized
that there was a possible issue.

Sincerely,
Watson Ladd

---

From: Benjamin Black <[email-masked]>
Date: Fri, 12 Dec 2014 20:39:28 -0800

Kenny,

While we remain convinced there is no compelling technical reason to make
the change, we will acquiesce to the will of the co-chairs in the interest
of seeing this move forward.

b

---

From: Robert Ransom <[email-masked]>
Date: Sun, 14 Dec 2014 13:16:12 -0800

> further from being useful until it can be adopted.

I second Watson Ladd's concern about the chairs' apparent preference
for adopting a document based on draft-black-rpgecc-00 instead of
draft-turner-thecurve25519function-01.  By the authors' own public
statements, draft-black-rpgecc-00 was knowingly and intentionally
technically inferior to draft-turner-thecurve25519function-01 in each
of the following ways:

* draft-black-rpgecc-00 specifies a curve modulo the prime 2^255-19
  which is neither isomorphic nor isogenous to the widely deployed
  Curve25519, and which thus is not compatible with the many existing
  independent, interoperable implementations of ECDH on Curve25519.
  This incompatibility is likely to prevent the reuse of much of the
  implementation experience which Curve25519 has acquired.

  (<http://www.ietf.org/mail-archive/web/cfrg/current/msg05606.html>
  and
  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05631.html>;
  see also
  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05629.html>
  and
  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05646.html>)

* draft-black-rpgecc-00 specifies a curve modulo the prime 2^255-19
  which introduces a security vulnerability into implementations of
  ECDH (and some implementations of other protocols) which rely on the
  simplest implementation strategy, i.e. the Montgomery ladder, which
  does not exist for the existing, widely implemented and deployed
  Curve25519.

  (<http://www.ietf.org/mail-archive/web/cfrg/current/msg05606.html>;
  see also
  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05629.html>)

* draft-black-rpgecc-00 does not state, in the text of the draft
  itself, any algorithms to perform point addition or scalar
  multiplication on the curves that it specifies.

  (<http://www.ietf.org/mail-archive/web/cfrg/current/msg05631.html>
  states that this omission is a flaw in draft-black-rpgecc-00;
  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05637.html>
  states that the omission of such algorithms is intentional)

* Section 10 (‘Intellectual Property Rights’) of draft-black-rpgecc-00
  makes a general statement about the IPR status of the curves
  specified in the document.  Although that is not a statement about
  ‘specific IPR’, which section 11 of RFC 3979 (BCP 79) explicitly
  forbids, I believe that the IPR statement in draft-black-rpgecc-00
  raises some of the same concerns which section 11 of RFC 3979 states
  as the rationale for forbidding IETF Documents and RFC Editor
  Documents from including statements about ‘specific IPR’.  Thus, I
  believe that section 10 of draft-black-rpgecc-00 is in violation of
  BCP 79.  The authors of draft-black-rpgecc-00 stated in the draft
  that it was ‘submitted in full conformance with the provisions of
  BCP 78 and BCP 79’.

In addition to the above flaws which were known to and intended by the
authors of draft-black-rpgecc-00 at the time that they submitted it,
draft-black-rpgecc-00 omits several technical details of ECDH (the
precise point format and handling of ‘invalid’ public-key bitstring
inputs) which the extensive implementation experience of Curve25519
has shown are needed to ensure interoperability and forward
compatibility and to protect the privacy of users of ECDH
implementations on the Internet.
draft-turner-thecurve25519function-01 includes those technical
details.

Adopting draft-black-rpgecc-00 (or a revised version) as a CFRG
document, instead of (a version of) the previously existing
draft-turner-thecurve25519function-01, would raise two serious
concerns:

* As Watson Ladd has noted, draft-black-rpgecc-00 would require more
  effort, and thus more time, for CFRG to modify it into a useful
  product than draft-turner-thecurve25519function-01 would.

* Adoption of draft-black-rpgecc-00 would reward its authors, both by
  crediting them as authors of CFRG's resulting document and by giving
  them greater control over CFRG's product.  It is inappropriate for
  IETF to reward the authors of draft-black-rpgecc-00 for submitting a
  document to CFRG that they knew to be inferior to a previous
  submission.

The CFRG chairs have expressed a preference for adopting a version of
draft-black-rpgecc, instead of a version of
draft-turner-thecurve25519function.  Given the above concerns, why do
the chairs believe that adoption of draft-black-rpgecc as a CFRG
document is in the best interests of CFRG and of the Internet as a
whole?

> 2^255-19 prime is used, and ignore the issues with 2^384-317.

I second this concern as well.  I have seen very little support in the
CFRG for the 384-bit curve specified in draft-black-rpgecc-00, and I
do not believe that the short discussion of 2^389-21 as a modulus for
elliptic-curve cryptography constitutes a consensus of CFRG or shows
that 2^389-21 is technically superior to or has implementation
experience comparable to 2^414-17 or 2^448-2^224-1 as moduli for ECC.

I have a further concern regarding the intentional omission of point
addition and scalar multiplication algorithms from the text of
draft-black-rpgecc-00.

Instead of providing such algorithms in the text of the draft,
draft-black-rpgecc-00 lists <https://eprint.iacr.org/2014/130.pdf>,
which contains several scalar multiplication algorithms for those
curves, as an informative reference (listed as [MSR] in the draft).
(I reviewed each of the draft's references (non-RFC references were
accessed on 2014-12-10); no other document listed as a reference
contains a point addition algorithm for Edwards curves, and no other
document that I was able to retrieve contains a scalar multiplication
algorithm for any type of elliptic curve.)

Mike Hamburg has informed the CFRG that he believes the fixed-base
scalar multiplication algorithm stated in [MSR] and used in Microsoft
Corporation's software implemented based on [MSR] is Covered by patent
US7602907.  That patent is assigned to Microsoft Corporation, and thus
meets the conditions of section 6.6 of RFC 3979 (part of BCP 79) for
each employee of Microsoft Corporation or its subsidiary Microsoft
Research.

I believe that patent US7602907, which Covers an algorithm to be used
in elliptic-curve cryptography, was ‘reasonably and personally known’,
as defined in BCP 79, to each Microsoft Corporation employee who
participated in this IETF Internet Standards Process regarding
elliptic-curve cryptography throughout their participation.

Further, each of the authors of draft-black-rpgecc-00 has actually
known of patent US7602907, and of Mike Hamburg's belief that it Covers
an algorithm stated in [MSR] and used in Microsoft's software, since
no later than Mike Hamburg's public statement to CFRG on 2014-09-16.

(<http://www.ietf.org/mail-archive/web/cfrg/current/msg05130.html> and
<http://www.ietf.org/mail-archive/web/cfrg/current/msg05132.html>)

It is troubling to me that the authors of draft-black-rpgecc-00 would
direct readers of their draft to [MSR] as the only source of point
addition or scalar multiplication algorithms for the curves specified
in the draft, given that they indisputably knew at the time that they
submitted the draft that [MSR] contains an algorithm which some of the
authors would clearly be required, by the text of section 6.1.1 of RFC
3979 (BCP 79), to provide an IPR disclosure for if they had included
it in the text of their draft.

Given the patent situation regarding [MSR], it is also troubling to me
that two of the intentional technical flaws of draft-black-rpgecc-00
-- incompatibility with existing Curve25519 software, and an
unnecessary security vulnerability in implementations based on the
simple Montgomery-ladder algorithm -- would have made readers of the
draft more likely to write new implementations of the curve specified
therein, and thus more likely to rely on the implementation guidance
provided in [MSR].

I learned of this patent Covering an algorithm specified in [MSR]
during an off-list conversation that I initiated with Marsh Ray of
Microsoft Corporation on 2014-09-04.  I placed Mike Hamburg, Alyssa
Rowan, and another person on the CC list of my message, with the
intent that they serve as witnesses to that off-list conversation.
Marsh Ray included Brian LaMacchia and Benjamin Black into that
conversation when he replied; Mike Hamburg and Alyssa Rowan also
participated in the conversation.

I learned of patent US7602907 and its connection to [MSR] from Mike
Hamburg on 2014-09-08, in the course of that off-list conversation.
Marsh Ray, Brian LaMacchia, and Benjamin Black also received that
message on 2014-09-08, eight days before Mike Hamburg provided that
information to CFRG.  I was not aware of any effort by those
participants to provide that information to CFRG.

I believe that neither I nor CFRG would have learned of patent
US7602907 and its connection to [MSR] if I had not initiated that
off-list conversation, or if I had not included Mike Hamburg in that
conversation, or if Mike Hamburg had not previously performed a search
for patents relevant to ECC in order to write software that would not
be Covered by them.

I have two questions on this matter for the CFRG chairs:

* Do the chairs believe that it is ethically acceptable for the
  authors of an Internet draft to

    (a) list as a reference a document which they authored themselves,
        knowing that if they had included the contents of the
        reference into the Internet draft itself, they would have been
        indisputably required by section 6 of RFC 3979 (BCP 79) to
        submit an IPR disclosure regarding that material; and

    (b) make other technical decisions in the contents of the Internet
        draft which are likely to cause the draft's readers to rely on
        the contents of the reference Covered by IPR?

* Do the chairs believe that such conduct should be rewarded by
  adoption of the resulting Internet draft as a group document?

Robert Ransom

---

From: Paul Hoffman <[email-masked]>
Date: Mon, 15 Dec 2014 08:04:31 -0800

Robert's assertions are both surprising and troubling to me. Resolution of them would certainly affect my views on draft-black-rpgecc, particularly on the hole it has for implementation. These need to be discussed more thoroughly before we can move forwards on the document.

--Paul Hoffman

---

From: Alexey Melnikov <[email-masked]>
Date: Mon, 15 Dec 2014 17:33:25 +0000

> Robert's assertions are both surprising and troubling to me. Resolution of them would certainly affect my views on draft-black-rpgecc, particularly on the hole it has for implementation. These need…
Agreed. On behalf of CFRG chairs, I would ask people not to comment on 
this thread until chairs have some time to discuss/investigate.

---

From: "Paterson, Kenny" <[email-masked]>
Date: Thu, 18 Dec 2014 20:51:28 +0000

Dear Robert,

I am going to respond to some of the early points in your message below on
behalf of the chairs. Separately, Alexei will respond to some of the other
points. Between us, we may not cover everything in your long e-mail. I
apologise in advance if this is the case.

On 14/12/2014 21:16, "Robert Ransom" <[email-masked]> wrote:

>draft-turner-thecurve25519function-01.

Note that the documents are not directly comparable, as you seem to imply
here. draft-turner-thecurve25519function-01 specifies a particular
key-agreement scheme based on Curve25519. draft-black-rpgecc-00 specifies
a curve generation method that can, inter alia, generate curves at a
variety of security levels. Its output is not directly usable by
implementors, of course, and more work would be needed by this group to
take its output and make it suitable for delivery to the TLS WG, assuming
that this is the direction CFRG wants to go in (an assumption I am not
making at this stage, but something that I will happily admit that I do
hope will happen given the way in which this group has been deadlocked for
some time now).

>By the authors' own public

In my opinion, this is unhelpful language. I believe that your arguments
would have greater impact if you were to try to approach matters in a less
inflammatory way.

>  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05646.html>
><http://www.ietf.org/mail-archive/web/cfrg/current/msg05646.html%3E>)

Whether this makes it technically inferior or not depends on your
definition of "technical". Personally, I don't consider the existence of
existing implementations for Curve25519 to be a *technical* issue. It's
certainly a consideration for this RG in adopting the MGN proposal. Also,
see my point immediately below.

><http://www.ietf.org/mail-archive/web/cfrg/current/msg05629.html%3E>)

The chairs have asked MGN to address this weakness, and they have agreed
to do so. This point will therefore soon be moot.

>  states that the omission of such algorithms is intentional)

This is correct, but I don't believe it is relevant for a document that
is focussed on curve generation. As noted above, if CFRG adopts this
draft, then more work could be put into making it easily usable for
implementors. That is an area where your evidently extensive experience
of ECC implementation could be put to very great use.

>* Section 10 (ŒIntellectual Property Rights¹) of draft-black-rpgecc-00
>  Œspecific IPR¹, which section 11 of RFC 3979 (BCP 79) explicitly
>  Documents from including statements about Œspecific IPR¹.  Thus, I
>  that it was Œsubmitted in full conformance with the provisions of
>  BCP 78 and BCP 79¹.
>
>

Again, your use of the word "intended" is unhelpful here. I can't speak
for the authors of the draft, but I'd point out that the flaw is
Relatively minor, leaks at most one bit of a private value, and only
then in certain protocols.

Yes, it would be preferable to avoid the defect if we can, but your
message, more specifically, its somewhat hyperbolic language, might
well lead experts to think that "the sky is falling". I'd urge you
to exercise more restraint.

>precise point format and handling of Œinvalid¹ public-key bitstring

Let me repeat. This is correct, but I don't believe it to be relevant for
a document that is focussed on curve generation.

>  product than draft-turner-thecurve25519function-01 would.

But draft-turner-thecurve25519function-01 only specifies a single ECDH
algorithm for a single curve. And this is not what the RG has been asked
to produce for recommendation to the TLS WG. Rather, we were asked for
curves at different security levels (and implicitly, recommendations about
how to use those curves to do key exchange and signatures). So substantial
work would also be needed to turn draft-turner-thecurve25519function-01
into what the RG needs to produce.

In short, you are comparing apples and aardvarks here.

>  document to CFRG that they knew to be inferior to a previous

This is not about rewards. It's about meeting the request of the TLS WG.
And I contend that it's not inferior to
draft-turner-thecurve25519function-01,
but a different beast entirely.

>document is in the best interests of CFRG and of the Internet as a

See above. In summary: we believe that, with some modifications to enhance
security (to which MGN have agreed), and additional work to provide
guidance as to how to use these curves in specific algorithms (ECDH and
signatures), we can produce a document (or documents) that meet(s) the
request from the TLS WG.

>experience comparable to 2^414-17 or 2^448-2^224-1 as moduli for ECC.

Here I agree with you that the specific prime 2^389-21 has not had much
discussion and therefore not gained consensus in CFRG. But I'm not aware
of any specific security or implementation concerns about it that would
not also apply to other "sparse" primes. Can you point to some? For
example, is there any reason to believe it will be any more difficult to
make secure against side-channel attacks than other choices at roughly the
same security level? Is it the case that the "implementation experience"
that you cite for primes 2^414-17 or 2^448-2^224-1, or any other
pseudo-Mersenne primes, would NOT transfer to this choice of prime? It
would be really helpful to the group if you could be more specific in
expressing your concerns here.

>addition and scalar multiplication algorithms from the text of

I expect this *was* intentional on the part of the authors, given my
assumption that it was their intention to provide a clean document that
focusses on curve generation rather than low level details of their usage
in cryptographic primitives. But reading on further in your message, I
think you mean to imply something more sinister here.

>algorithm for any type of elliptic curve.)

Perhaps the draft's authors would consider adding further references to
the extensive literature on ECC implementation, particular papers by Dan
Bernstein, Tanja Lange, and their co-authors (who have done so much to
spur the development of elliptic curve cryptography in its modern form).
However, I don't believe that's really the point here - this draft is
about specifying curves, not operations for those curves.

>in elliptic-curve cryptography, was Œreasonably and personally known¹,
><http://www.ietf.org/mail-archive/web/cfrg/current/msg05132.html>
><http://www.ietf.org/mail-archive/web/cfrg/current/msg05132.html%3E>)
>

Once again, I would request that you desist from the use of such strong
language. Not only because it is unhelpful, but also because (I believe)
it undermines the arguments you are trying to make.

>for patents relevant to ECC in order to write software that would not

If this is the case, then you will have made a useful contribution to the
work of the group for which I would like to publicly thank you.

However, I'd also point out - and I think this is key - that (based on my
own reading of this patent, and heavily caveated by the usual disclaimers
about none of us being lawyers) it's perfectly possible to implement the
basic arithmetic procedures (point addition, scalar multiplication) and
higher level algorithms (ECDH, signatures) for the curves produced by the
MGN procedure (as for any other similar curves) without having to use any
of the techniques that might be covered by this patent. After all, the
curves it produces are Edwards form, or twisted Edwards form, so I would
assume that the extensive code that is available under generous open
source licences would be directly usable here.

>        submit an IPR disclosure regarding that material; and

I think that would be ethically unacceptable. But I don't believe it's
what has happened here.

>        the contents of the reference Covered by IPR?

I think that would be ethically unacceptable. But I don't believe it's
what has happened here.

>  adoption of the resulting Internet draft as a group document?

It's not about rewarding any one or any organisation with anything.

Regards,

Kenny (on behalf of the chairs)

---

From: Alexey Melnikov <[email-masked]>
Date: Fri, 19 Dec 2014 00:04:44 +0000

Robert,

On 14/12/2014 21:16, Robert Ransom wrote:
>    Documents from including statements about ‘specific IPR’.
The statement in the draft is not a declaration of IPR specific or 
general - it's a confirmation that the authors know of *no* IPR. I am 
pretty sure that authors included this in order to be helpful and save 
RG participants a datatracker search, and not for any nefarious reason.

So I don't believe that your reaction to this section being present is 
warranted.
>    Thus, I
I think calling this a "violation" is uncalled for, since the statement 
by the authors is not a declaration of IPR. So at best, this is a nit 
that could easily be addressed by removing the section. The authors 
would not even need to make any IPR declaration in the datatracker, 
since they apparently know of no IPR and the datatracker doesn't even 
offer to record these cases.

So by including the statement as they did, the authors are actually 
giving the RG more information that would otherwise be available, which 
is a good thing IMO.

Alexey,
As a co-chair.

---

From: Watson Ladd <[email-masked]>
Date: Thu, 18 Dec 2014 20:52:18 -0800

> hope will happen given the way in which this group has been deadlocked for

The requested modification to draft black makes it generate curve25519
as I understand, but with potentially different generators. If this
request is met, and we add the description of the algorithms, we will
arrive at the contents of draft-turner25519. Why not start there?

We have 6 days, or we will have missed a deadline for the second time.

> a document that is focussed on curve generation.

That's not the document we were asked to produce, and it's not a
document that will help implementors. How does a generation method
help with addressing the request for two or three curves, at security
levels we feel are relevant?

> into what the RG needs to produce.

Changing a single constant or two is not "substantial work". I've
asked repeatedly for input on what signature format would be
preferred,  and gotten little response: my plan this weekend was to
write a version with signatures or a separate document.

> but a different beast entirely.

Which one is closer to meeting the express desires of the TLS WG? The
TLS WG does not want a generation method, but rather new curves. And
they don't want new "curves" but rather want us to do the hard work of
specifying a better mechanism. We've already ruled out random primes,
and short Weierstrass cofactor 1, in some cases in the face of
determined opposition. What's so special about the minority holding
out for slow choices of c that we need to appease them also?

> signatures), we can produce a document (or documents) that meet(s) the

And that work has been largely done for Curve25519.

Are the chairs committed to the choice of Curve 25519 at the 256 size
at this point? Or would they like until Purim for a revised version of
the generation method, an argument about the generators, some debate
over picking a different protocol, and further impatience from the
multiple working groups now blocked on our work? If we can get the
Curve25519 work out the door, with the promise that the larger curve
will use a similar protocol, this should buy us more time to consider
the higher security levels.

> expressing your concerns here.

One set of concerns is how efficient it will be compared to Ed448. We
have guesses: there is no substitute for implementations.

Furthermore, the choice of bitlengths is not set in stone. If Ed448
could offer the same performance as the 384 bit prime, there would be
no reason not to go for the larger, effectively free length. It
probably won't, but until we have working implementations we don't
know.

Furthermore, accepting the black draft does not mean picking 2^389-21.
It means picking 2^384-big, where big is sufficiently large to make
Ed448 approximately as fast, and make vectorized implementations slow.

> about specifying curves, not operations for those curves.

And once again, the final product needs to be about providing working
algorithms. Several issues with original draft for Curve25519 in TLS
stemmed from the absence of a description of the Curve25519 function
except in a paper of Daniel J. Bernstein. A document that merely
contains curves, without the algorithms, does not satisfy the request.

Furthermore, we still need to determine what points are sent on what
model. Our job will not be done if we simply accept the Black et al.
draft.

> source licences would be directly usable here.

Much of that code assumes that the addition law is complete. On the
new curves in the recent draft, I believe this assumption is
satisfied. However, the original NUMS submission presented an
algorithm that infringed on the patent. While it would be possible to
avoid the patent, the cited reference and presentation made in April
suggested an algorithm that ran smack into the patent. The new draft
makes it substantially easier to avoid the patent, by permitting
complete addition laws.

<snip>
> It's not about rewarding any one or any organisation with anything.

Really? The entire argument for this "compromise" assumes that the
authors of the NUMS draft have something to offer in return for our
accepting a slower prime at the 384 bit level. They don't: IETF
working groups (and I imagine IRTF working groups) regularly reach
conclusions in the face of vocal opposition, in most cases far more
valid than the objections of Benjamin Black to special primes. For
example, this working group has decided to proceed with a last call on
a PAKE that doesn't have a security proof. The TLS WG decided to
pursue ALPN over NPN, despite concerns about client fingerprinting vs.
server fingerprinting. I am certain there are more decisions of a
similar nature to be found. I don't think these are commendable
actions, but I do think that we should consider the relative merits of
2^384-big vs 2^389-21, regardless of the loudness of the supporters of
one side or the other, and should be aware of what the basis for
making a decision actually is.

Remember that we are effectively committed to recommending Curve25519.
Any argument about the superior "rigidity" of 2^384-big has to imagine
someone unwilling to accept 2^389-21 for exactly the same reasons they
accepted 2^255-19, namely the extremely limited number of primes of
this shape.

If the leadership is committed to compromise for the sake of
compromise, so be it. But logrolling is not the same as rough
consensus, and the IETF rules clearly and explicitly point this out.
Nothing has changed about the relative performance of 2^384-big vs
Ed448 since April. The choice of 2^389-21 vs. Ed448 is more difficult:
my instinct suggests the smaller, with Ed448 and E521 as options for
those who desire significantly more security.

Sincerely,
Watson Ladd

---

From: "Paterson, Kenny" <[email-masked]>
Date: Fri, 19 Dec 2014 10:45:45 +0000

Dear Watson,

>arrive at the contents of draft-turner25519. Why not start there?

We could indeed have done that. On the other hand, I believe it's more
appealing to agree on a rigid curve generation method and then recommend
its outputs, delivering that along with appropriate implementation advice.
Perhaps we can even borrow some text from draft-turner25519 to speed
things along? Is some of that reusable, do you think?

>We have 6 days, or we will have missed a deadline for the second time.

Indeed.

>levels we feel are relevant?

It's a document that will produce what we were asked to produce, in a way
whose rigidity can be demonstrated (modulo the selection of input primes).
This is important to some people here.

I know there are people who will object to the fact that the method was
tweaked and that the primes have been changed. Personally, though, I don't
see that tweaking in order to improve security, as motivated by remarks
made by Dan Bernstein, is a bad thing. As for the primes, there we can
argue about performance, as you eloquently do below. If there are
compelling performance reasons to change the 192-bit level prime, then we
should consider doing it. See below for more on this.

>write a version with signatures or a separate document.

Timing is everything in I*TF. I think you were asking for the input at the
wrong point in the process. Worth reflecting on for the next time, perhaps.

>out for slow choices of c that we need to appease them also?

I don't think it's really a minority - things seem more balanced than that
to me, based on my reading of the list.

A minute ago you said that it was not hard work to specify multiple curves
and algorithms - just a matter of changing some constants! If that's the
case, then great, I'd hope you'd get involved in developing
draft-black-rpgecc-00-.txt and help do that work there, to turn it into
what you think we need to deliver.

>the higher security levels.

That would be one way of skinning this particular cat. Another way would
be to get involved with draft-black-rpgecc-00-.txt and help push it
forward. That's what the chairs are proposing.

>Ed448 approximately as fast, and make vectorized implementations slow.

Sorry, I mis-wrote here. You are quite right that the draft proposes
2^384-317. That's what you get when your chairs are working late at night
after long days doing their day jobs....

I'd be grateful if the folks from the MGN team could say more on the list
why they chose this particular prime, and give some insight into the
performance impact of choosing it over near neighbours such as 2^389-21.

Others should chime in too - for example, people should feel free to
repeat performance numbers from earlier in our discussions (they are out
there in the archive somewhere!).

Please let's collaborate and see if we can swiftly resolve whether there
is a significant performance impact or not.

>contains curves, without the algorithms, does not satisfy the request.

Agreed.

>model. Our job will not be done if we simply accept the Black et al.

Agreed. No-one was saying this, as far as I recall. Certainly not me.
(Please reread my messages carefully.)

>makes it substantially easier to avoid the patent, by permitting

Well, that's good then, no?

>accepting a slower prime at the 384 bit level. They don't:

I think the draft does have something to offer: a well-defined, repeatable
process for generating curves that meet all the identified security
criteria. The choice of prime then becomes a performance question (given
the current state-of-the-art in our knowledge about the DLOG problem).

But you are right to ask what the performance impact is of the particular
choice of prime 2^384-317. Let's try to hash that out with solid numbers.

>IETF

I agree. I was temporarily confused about which prime was in
draft-black-rpgecc-00-.txt. That was really unhelpful of me.

>accepted 2^255-19, namely the extremely limited number of primes of

I agree. (Wow, all this agreement suddenly breaking out!). Above, I've
asked for a discussion on this very point, focussing on the relative
performance of the options 2^389-21 and 2^384-317. Let's see if we can
resolve this quickly.

>my instinct suggests the smaller,

Let's get past instinct to hard numbers.

>with Ed448 and E521 as options for

Likewise,

Kenny

---

From: Harry Halpin <[email-masked]>
Date: Fri, 19 Dec 2014 13:44:28 +0100

> things along? Is some of that reusable, do you think?

Indeed, I think this approach squares the circle by allowing Curve 25519
as well as the other "security levels" to be generated. If we could
*merge* the drafts and recommend Curve 25519 as a specific curve along
with the curves at other security levels, this might finally break the
deadlock.

Note that W3C Web Cryptography API has a deadline as well - our deadline
for CFRG making a firm decision in order for WebCrypto to add in any new
curves is March 12th, which would trigger another Last Call for us.

https://lists.w3.org/Archives/Member/chairs/2014OctDec/0181.html

Otherwise, WebCrypto will progress without them, possibly adding them in
later via an errata process.

Further details on the debate here under 1.3 "Adding new elliptic curves":

http://www.w3.org/2012/webcrypto/DispositionOfComments/WebCryptoDispositionOfComments.html

  cheers,
        harry

---

From: Paul Hoffman <[email-masked]>
Date: Fri, 19 Dec 2014 08:46:30 -0800

On Dec 18, 2014, at 8:52 PM, Watson Ladd <[email-masked]> wrote:
> The
> specifying a better mechanism.

That. Please!

--Paul Hoffman

---

From: Watson Ladd <[email-masked]>
Date: Fri, 19 Dec 2014 11:16:32 -0800

> with the curves at other security levels, this might finally break the

It's like the difference with being engaged, and being married. We're
all in agreement that we need to specify the curve formulas and the
actual algorithms to be used but until that statement is made, we
haven't made it. Regardless of the change history of the draft, we
know what that says, regardless of the form it takes. I don't say this
to be flippant, but to point out that apparently agreement is not
enough: we need something to point to to say "this is it" even if we
find and fix mistakes either.

What we need is a clear, unambiguous statement from the chairs saying
that we are going to use X-coordinate Montgomery only on Curve25519
just like in DJB's paper, and X-coordinate only Montgomery on whatever
other curve it is, making the appropriate changes, and that signatures
will be whatever we've decided they are. This doesn't require editing
drafts before making this statement: they can be modified to
accommodate, and will need extensive review in any case.

If we are going to slip the schedule again, it would be nice to know
this clearly, along with a plan for how we going to meet the deadline
this 3rd time around. The TLS WG did in fact permit us to move forward
on the 128 bit option before the high security one, as shown in
http://www.ietf.org/mail-archive/web/cfrg/current/msg04663.html. This
would seem to buy us more time, while giving the TLS WG something
concrete at this point, and would seem to give the W3C Web Crypto
group the more widely used option ahead of schedule.

Sincerely,
Watson Ladd

---

From: Tanja Lange <[email-masked]>
Date: Tue, 23 Dec 2014 02:54:30 +0100

Dear Kenny,
This is a late reply to your reply to Watson. 

> what you think we need to deliver.
To me this sounds like an ideal moment to follow through on the plans
made earlier. Is there a final requirements list? Is there a date when
the list of curves to evaluate will be stable? What will be the deadline
for comparing performance of arithmetic in different prime fields and
comparing performance of arithmetic on different curve shapes? What
will be the deadline for quantifying wiggle room in generation
procedures?

We will not get optimal results by tweaking one meta proposal when 
creating a meta proposal was not the original mission and there has 
been very little discussion about requirements for meta proposals
while we discussed requirements for curves. We will not receive 
transparency by engaging in horse trading.

'Compromise' is a word that should be banned from this discussion; we
already have (potentially) compromised curves!

> is a significant performance impact or not.
I think a competition has more to offer than a 'collaboration' where 
parties get more influence by having more people send emails to the list.
What should count are the merits of papers, implementations, and internet 
drafts so that proposals get more influence by being objectively better.

> Let's get past instinct to hard numbers.
... but I think this needs clear requirements, deadlines etc.

	Tanja

---

From: "Salz, Rich" <[email-masked]>
Date: Tue, 23 Dec 2014 14:58:45 -0500

Is there any question about the way Curve25519 was generated?  As I understand it, the RPGECC authors are willing to modify their document so that 25519 can be generated.  Then why can't we just approve the current 25519 draft and say we'll have the overall framework out soon.  (I'm not smart enough to try to pick a date -- or, perhaps, I'm too smart to try.)

Programmers often have this tendency to think that going bigger and doing yet another abstraction will result in a clean comprehensive solution that fits nicely into the mindset.  It rarely works.  Sometimes going back to first principles is just going backward.

Santa, I've been pretty good this year.  Can I please have 25519 in a nice pretty wrapping?   The rest of it can wait until the end of Advent.

	/r$

--  
Principal Security Engineer, Akamai Technologies
IM: [email-masked] Twitter: RichSalz

---

From: Tony Arcieri <[email-masked]>
Date: Fri, 26 Dec 2014 15:32:23 -0700

On Tuesday, December 23, 2014, Salz, Rich <[email-masked]> wrote:

> Is there any question about the way Curve25519 was generated?  As I
> understand it, the RPGECC authors are willing to modify their document so
> that 25519 can be generated.  Then why can't we just approve the current
> 25519 draft and say we'll have the overall framework out soon.
>

As a mere observer watching from the CFRG peanut gallery, I second this. It
seems there's something of an informal consensus that Curve25519 is
acceptable as a curve with a 128-bit security level by all parties
involved. Do the chairs plan on officially adopting it soon? It seems like
everything else (rigid curve generation guidelines, higher security level
curves) are a lower priority.

-- 
Tony Arcieri

---

From: "D. J. Bernstein" <[email-masked]>
Date: 30 Dec 2014 21:34:58 -0000

I think it's important for the public record to be clear on the security
advantages of Curve25519 over PinkBikeShed.

I realize that most people don't see this as important---"Microsoft has
abandoned the PinkBikeShed proposal now; you're beating a dead horse"---
but I have serious concerns about the procedures that have brought CFRG
to this point. This message first discusses the procedures, and then
discusses the technology issues. Some of these issues are also of
interest beyond PinkBikeShed.

Timeline review:

   * 19 May 2005: http://cr.yp.to/talks/2005.05.19/slides.pdf was the
     original presentation of what I now call PinkBikeShed. At the time
     I didn't give it a name (the talk said "Curve"), and the curve
     didn't last long---very soon afterwards I had thought through the
     security issues carefully enough to see that Curve25519 was better.

   * 16 October 2014: One of the CFRG chairs proposed taking two weeks
     to finalize requirements and agree on "whatever benchmarking system
     we're going to use for performance measurements", and then a month
     to measure and settle on the final "recommendations to the TLS WG".

   * 2 November 2014: Benjamin Black wrote "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."

     Notice the calm long-term perspective here, quite consistent with
     the idea that CFRG wanted to take time to think carefully through
     curve-selection issues---a process I respect and have been happy to
     contribute to.

   * 3 November 2014: The chair wrote "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. ... 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[out] unduly compromising efficiency and
     security, then I am prepared to sacrifice some extra time to
     achieve it. ... And the longer we take, the better answers we can
     hope to get on the things that really matter."

   * 26 November 2014: The chair foreshadowed "significant developments
     ... that will help us move forward with that main work of selecting
     curves to recommend to the TLS WG." What would these developments
     be? Finally the requirements list? The details of the publicly
     verifiable benchmarking process?

   * 26 November 2014, after sundown: Night of the Living PinkBikeShed.

   * Subsequent days: Various followup discussion, both inside and
     outside CFRG. For example, Felix von Leitner characterized
     Microsoft's approach as "embrace+extend", and Trevor Perrin
     characterized Microsoft's approach as a "meaningless tweak" and a
     "terrible idea" given its impact on the existing and future code
     base. (Microsoft can afford this sort of fragmentation, but most
     ECC implementors can't.)
   
   * 28 November 2014: I sent my first "Mishandling twist attacks"
     message, carefully explaining one of the security reasons to reject
     PinkBikeShed. (In my messages to the CFRG mailing list, I've been
     careful to focus on intrinsic long-term merits of curve choices,
     rather than on how well established Curve25519 already is.)

   * 1 December 2014: Black claimed that twist attacks don't apply to
     PinkBikeShed if the curve-specifying document presents the Edwards
     view of PinkBikeShed rather than the Montgomery view.

   * 2 December 2014: I asked how Black could justify _any_ form of
     twist security in his Edwards proposals if he believes his claim;
     this question is still unanswered weeks later. I also explained why
     his claim was wrong.

   * 8 December 2014: Black, in the guise of responding to my message,
     made many erroneous comments about related issues. I was extremely
     busy and didn't have a chance to respond to this before now.

   * 12 December 2014: The chair characterized Black's comments as
     "quite powerful arguments" but said that Black should abandon those
     arguments for the sake of "unblocking our current logjam" and
     "making progress".

     There was no explanation of why CFRG was suddenly in a rush, or why
     CFRG was suddenly in a "logjam", or why CFRG should abandon its
     ongoing process of settling requirements and evaluating curves
     according to those requirements.

   * 12 December 2014: Black wrote "we will acquiesce to the will of the
     co-chairs in the interest of seeing this move forward."

Some of Black's errors related to PinkBikeShed were already pointed out
in the brief period between 8 December and 12 December, but certainly
not all, and after 12 December people seem to have decided that no
further comment was required on his message.

It's easy to imagine how someone looking back at this record could
imagine that Black had raised real technical objections that at this
point are still unaddressed---and that the result was dictated by
non-transparent politics rather than by technology. Look at the
situation from the future reader's perspective:

   * If Black's arguments were plainly bogus, or were considered and
     rejected, or were considered and judged to be outweighed by more
     important factors, then why did the chair four days later declare
     the objections to be "quite powerful arguments"?
     
   * Black's recent behavior is quite explicitly the type of
     "compromise" blasted in RFC 7282---and behind the scenes there's
     even worse "horse-trading" going on. The people who sent me private
     email along the lines of "we'll convince them to stop complaining
     about Curve25519 if you give them their pet 384-bit prime" ought to
     be ashamed of themselves. If a company can so easily push its pet
     cryptography into standards, what stops an attacker from doing the
     same with secretly weak cryptography?

   * Last month Black and the chair were saying how important it was to
     obtain "the highest possible levels of trustworthiness" in "choices
     we will have to live with for 20 years"---and suddenly this month
     they're rushing towards a call for "consensus" on a highly
     questionable new Black document.

The reader should also be faced with the technical evaluation: no, Black
never had good arguments for regressing from Curve25519 to PinkBikeShed;
no, his arguments aren't "powerful"; no, PinkBikeShed isn't some sort of
superior Microsoft technology being repressed by politics.

Enough about procedures; let me now focus on the technology.

In my first "Mishandling twist attacks" message I wrote "every major ECC
standard already multiplies scalars by the curve's cofactor" and then
analyzed the worrisome impact on PinkBikeShed if a "protocol multiplies
the secret scalar s by the cofactor 4 exactly as the standards say".
This security issue for PinkBikeShed is eliminated by Curve25519.

Here's the centerpiece of Black's response: "A sloppy implementor could
just as easily misread guidance and clear cofactor 4 on Curve25519."

Let's think this through, starting from the facts.

The DH factor used in IEEE P1363-2000 Section 7.2.2 is "k", which by
definition is the "cofactor k = #E/r"; of course, "r" is a big "prime
integer" and is the order of the specified generator. The MQV cofactor
in Section 7.2.4 is also k. The DH factor in ANSI X9.63 Section 5.4 is
"h", the same cofactor under a different name. The MQV factor in ANSI
X9.63 Section 5.5 is the same cofactor. I could keep going like this for
a while. There are explanations all over the place, in these standards
and elsewhere, of why you should multiply by the curve's cofactor.

In the case of Curve25519, the curve's cofactor is amply documented as
being 8, and the consistent message of these standards is to multiply by
8. There's no ambiguity here, and Black gives no indication of how a
"sloppy implementor" (or protocol designer) could "misread" any of this.

It's true that, in the types of protocols I've been talking about,
taking cofactor 4 on Curve25519 would cause very similar damage to
taking cofactor 4 on PinkBikeShed. However, to judge the impact of
conceivable failures, one has to rationally evaluate the probability of
the failures. For PinkBikeShed, multiplying by 4 is _exactly_ what all
of these standards recommend, and it's easy to see how the failures
would happen. For Curve25519, Black's imaginary multiplication by 4 is
_contrary_ to what all of these standards recommend. Black's claim of
equal probability ("just as easily") isn't even marginally plausible.

Benjamin Black writes:
> I am objecting to the notion that cofactors (8,4) are in any way more
> secure than (4,8).

See my first "Mishandling twist attacks" message, and see above.

> twist secure.

This doesn't answer the question that I asked on 2 December. Let me try
phrasing it differently.

You claim that, because of your choice to specify curves in Edwards form
rather than Montgomery form, the advanced twist attacks that I'm talking
about "do not apply" to your draft. You therefore claim that "rigidity"
requires taking a smaller coefficient (PinkBikeShed) rather than a
coefficient protected against these attacks (Curve25519).

Obvious analogy: You claim that, because of exactly the same choice,
_no_ twist attacks apply to your draft. You therefore claim that
"rigidity" requires taking a smaller (in fact, _much_ smaller)
coefficient, ignoring _all_ twist attacks.

But wait a minute: you _don't_ seem to be making these last two claims;
these claims aren't consistent with any of the curves you've proposed.
You must therefore have some reason for believing that Edwards curves
_are_ subject to twist attacks. What exactly is this reason, and why do
you think that it _doesn't_ apply to more advanced twist attacks?

> "switching to single-coordinate ladders" is the solution against
> security failures when it comes to invalid-curve attacks. Windowing
> implementations on complete Edwards curves can be implemented securely
> and eliminate any risks against those attacks.

Yes, the implementor _can_ check whether the incoming point is on the
curve. However, it's very easy to see how an implementor could end up
using a scalarmult routine that doesn't include this check---see

   https://duckduckgo.com/?q=elliptic+curve+scalar+multiplication

for many, many, many examples---and then the attacker wins. As I wrote
before: "Rather than blaming the implementor, we eliminate these
security failures by adding twist security, for both Montgomery and
Edwards, and switching to single-coordinate ladders."

You say that you don't agree that this is "the solution". You instead
advocate ignoring the problem on the protocol level, and relying on the
implementor to be careful to do this right. The simple fact is that your
"solution" is fragile (even Hugo Krawczyk was bitten by these attacks!)
while mine is not.

More examples of the same general phenomenon, and a more detailed
discussion of this example, appear in the "General context" section of
my first "Mishandling twist attacks" message.

> In fact, looking at the Curve41417 paper, you eschew the
> Montgomery (or Edwards) ladder in favor of windowing.

No, the paper does not "eschew" the Montgomery ladder. It says that (for
this number of bits on this platform, and of course disregarding the
differences in inputs) Montgomery-ladder scalarmult is "not quite as
fast" as windowed-Edwards scalarmult, but it also says that the
Montgomery ladder "has the advantage of fitting the computation into
less SRAM", says that "each curve in Edwards form is birationally
equivalent to one in Montgomery form, so there is no need to choose one
over the other", and mentions the importance of twist-security when
"only the [Montgomery] x-coordinate is transmitted and used".

Furthermore, you're once again confusing the choice of _computation_
with the choice of _coordinates_. I feel like a broken record here---
starting in my first message to CFRG in July, I've pointed out a number
of errors from your team stemming from this rather basic confusion, and
your team has consistently dodged rather than responding.

> In this case, the performance advantages of Edwards trump the
> irrefutable and essential requirement for eliminating "security
> failures" above via use of single-coordinate ladders.

No, the paper says nothing of the sort; it simply evaluates the speed of
scalar multiplication. Furthermore, you're _again_ confusing the choice
of computation with the choice of coordinates.

> I am also objecting to your repeated claims, contradicted by your own
> work, that single-coordinate ladders are required.

Precisely what do you think you mean by "single-coordinate ladders are
required", and precisely which claims do you think you're objecting to?
Exact quotes in context, please, not careless paraphrases.

Here's a sampling of what I've actually written. The Montgomery ladder
is a remarkably simple, fast, constant-time algorithm for single-scalar
multiplication on (e.g.) Curve25519:

   x2,z2,x3,z3 = 1,0,x1,1
   for i in reversed(range(255)):
     bit = 1 & (n >> i)
     x2,x3 = cswap(x2,x3,bit)
     z2,z3 = cswap(z2,z3,bit)
     x3,z3 = ((x2*x3-z2*z3)^2,x1*(x2*z3-z2*x3)^2)
     x2,z2 = ((x2^2-z2^2)^2,4*x2*z2*(x2^2+A*x2*z2+z2^2))
     x2,x3 = cswap(x2,x3,bit)
     z2,z3 = cswap(z2,z3,bit)
   return x2*z2^(p-2)

For DH I've repeatedly said that the Montgomery ladder minimizes
tensions between speed, simplicity, and security; I've seen no arguments
to the contrary. My primary reason for objecting to cofactor-1 curves is
that those curves fail to provide this important option to DH protocol
designers and DH implementors.

There are many situations---most obviously, signatures---where most
implementors will want to do something different from the Montgomery
ladder. If you think that I've told them "No, you have to use the
Montgomery ladder!" then you're mistaken. If you think that specifying a
Montgomery curve forces people to use the Montgomery ladder then you're
again mistaken.

> technical argument about the strength of the curve.

Are you trying to say that twist security isn't a technical issue, or
that leaks of scalar bits inside existing and future protocols aren't a
technical issue, or that you have some more limited notion of curve
"strength" that doesn't cover these security issues?

> The additional criterion you are describing is difficult to see as
> "twist security".

That depends on how broad your protocol view is. As I said before,
unless the RNG is backdoored, standard DH is _not_ noticeably damaged by
this particular type of leak of scalar bits; but there are other
protocols that _are_ seriously damaged.

> The curves in the draft are twist secure by any reasonable definition,
> including your own SafeCurves twist security requirements.

There's one attack paper after another showing how to break
implementations of standard ECC (and of semi-standard ECC making similar
mistakes, such as Bitcoin). I'm talking about major failures in major
protocols such as DH and signatures.

The traditional response to these problems is to blame the implementor.
SafeCurves blames the curve choices, declaring the underlying curves to
be "unsafe", since we know exactly how the underlying implementation
pitfalls are eliminated by better choices of curves. SafeCurves is
completely explicit about what it means by "safe", and about why it is
drawing that line.

If some particular curve is labeled as "safe" by SafeCurves, can you
conclude that it has identical security to all of the other curves
labeled "safe" by SafeCurves? Of course not: this conclusion is silly,
and certainly isn't justified by anything SafeCurves says.

It should also be obvious, as a procedural matter, that CFRG needs more
stringent requirements than SafeCurves. The BADA55 paper shows that
there are more than a million "safe" curves (including Brainpool-level
rigidity) even without exploiting variations in primes; something is
seriously wrong if CFRG is actively recommending all of those curves for
deployment.

> A sloppy implementor could even more easily skip checks for weak keys
> when using Montgomery Curve25519 outside of DH. All Curve25519
> documentation makes clear all 32-byte strings are valid keys. That
> this is so only for DH is easily forgotten and I've not found a
> Curve25519 implementation that performs the required check.

Let me get this straight. You think that the amazing simplicity and
robustness of Montgomery coordinates for DH are _bad_ things since

   (1) you think they might encourage implementors to oversimplify some
       unusual protocol that relies on "contributory" behavior and

   (2) you think this oversimplification would be less likely if
       implementors were forced to use other coordinates for DH?

Even if the (many) unclear details in this argument were filled in, the
argument would be completely missing the incredible importance of DH.
DH obviously outweighs all of the "contributory" protocols that have
ever been invented.

The analogy to the PinkBikeShed/Curve25519 comparison also doesn't work.
For PinkBikeShed/Curve25519, the DH situation is the same and the
lesser-known protocols are the tiebreaker.

> using p = 1 mod 4 primes introduces the concern you are raising

First, this isn't an argument for PinkBikeShed over Curve25519; they
both use the same prime.

Second, this argument is incorrect. I'm talking about curves where
multiplying by the curve cofactor doesn't clear the twist cofactor.
Curve25519 is _not_ one of these curves, but the prime _is_ 1 mod 4.

> Rather than blaming the implementor for clearing the "wrong" cofactor,
> we can eliminate this "security failure" by using p = 3 mod 4 to
> ensure the cofactors are equal, which is the choice you made for both
> Curve1174 and Curve41417.

First, this isn't an argument for PinkBikeShed over Curve25519.

Second, this argument gets the technical facts all wrong. Taking primes
that are 3 mod 4 _allows_ equal cofactors but doesn't "ensure" them.
More importantly, having the twist cofactor _divide_ the curve cofactor
fully solves the problem I'm talking about; there is no reason to have
the cofactors equal.

Third, this argument gets the historical facts all wrong. The prime for
Curve41417 was the output of a performance-focused search, and it
happened to be 3 mod 4. Curve1174 _did_ require 3 mod 4---but the reason
for this requirement had nothing to do with cofactors; the reason was to
give an example of a curve supporting the Elligator 1 function. The
introduction of the Elligator paper is completely explicit in saying "we
introduce a high-security high-speed elliptic curve that supports the
[Elligator 1] function".

> Looking at your Curve25519 paper there is a single mention of
> requirements on cofactors: "Multiply the secret key by a small power
> of 2 to account for cofactors in the curve group and the twist group".

Actually, the paper contains a considerably more detailed discussion of
cofactor requirements, although to see this you have to read the paper
and understand what some formulas are saying---a naive word search isn't
adequate.

In particular, in the "Security" section, the "Small-subgroup attacks"
subsection gives a unified description of small-subgroup attacks and
twist attacks, describes the information leaked considering the curve
cofactor 8 and the twist cofactor 4, and observes that the
multiplication of scalars by 8 eliminates the leak.

For the security analysis in the paper, it's irrelevant whether this
multiplication is

   * by the curve cofactor (as all the standards say) or
   * by the lcm of curve and twist cofactors (as the paper introduction
     says).
   
The reason it's irrelevant is that for Curve25519 these two options are
identical. This is exactly where PinkBikeShed would have created an
unnecessary conflict, begging implementations to do the wrong thing.

> It is difficult to see this as rigidity.

All of these curves can be viewed as Montgomery curves _and_ as complete
Edwards curves. The Edwards view is better for signatures and similar
speed for DH (depending on exact sizes, compression, etc.), although
Montgomery is by far the simplest DH option.

The reason that Curve25519 didn't require completeness in Edwards form
is obvious from the following timeline:

   * ECC 2005: I introduced Curve25519.

   * 2007: Tanja Lange and I went to a surprising talk by Edwards
     presenting what are now called "original Edwards curves". We then
     introduced "Edwards curves", in particular introduced "complete
     Edwards curves" (none of which are original Edwards curves), and
     introduced fast algorithms for arithmetic on Edwards curves.

Surely you understand that it would have been rather difficult to make
efficiency choices and security choices on the basis of tools that
nobody knew about until two years later. You can think of Curve25519 as
being lucky for also meeting the newer requirements, and then the fact
that it was introduced so early makes it arguably _more_ rigid---curve
manipulation would have had to be based on secret attacks known in 2005.

Of course, any manipulation of, e.g., NIST P-224 would have had to be
based on attacks known in the 1990s. The critical difference is that
P-224 _doesn't_ meet newer public requirements. For example, P-224
doesn't meet the SafeCurves twist-security requirements. P-224 turns out
to be at the attacker's perfect level of twist-insecurity, similar to
DES, breakable at moderate cost while still being plausibly deniable.

> In the recent Curve41417 paper I similarly find a single mention of
> cofactor requirements: "For security we ... insist on the same level
> of twist-security as Curve25519 — the cofactors of the curve and its
> twist are in {4, 8}." No mention of either requiring the cofactors be
> equal or that they be minimal (which they aren't).

Obviously very large cofactors aren't compatible with security, but very
specific rules such as cofactor _minimality_ and cofactor _equality_
aren't required. Even NIST managed to get this right in the original
NIST-curve specification: it advocated minimal cofactors for
"efficiency", not for security.

What ultimately matters is the tradeoff between the security level and
performance. This is influenced in a complicated, but measurable, way by
choices of primes, cofactors, etc. In the case of Curve41417, we
obtained a surprisingly small d by allowing (8,8), although of course
this also reduced the rho security from 2^205.8 to 2^205.3.

---Dan

---

From: "Paterson, Kenny" <[email-masked]>
Date: Wed, 31 Dec 2014 17:28:21 +0000

Hi Tanja,

>This is a late reply to your reply to Watson.

And this is a slightly less late reply to your message, which arrived
shortly after my Christmas break had begun.

>made earlier. Is there a final requirements list?

No. I believe we reached agreement on all but a couple of the criteria,
but the chairs' attempts to bring about a meaningful discussion about
quantifying degrees of rigidity/wiggle room were unsuccessful at that time
(mid-October). We did not also reach agreement on requirements for
hardware. See my messages:

https://www.ietf.org/mail-archive/web/cfrg/current/msg05286.html

https://www.ietf.org/mail-archive/web/cfrg/current/msg05610.html

>Is there a date when

It doesn't seem to be working in that mechanistic way, I'm afraid, even
though it would have been my preferred approach. Rather, we tried a
structured, requirements-driven approach, and I think it's fair to say
that, while we made progress and found some common ground, we did not
reach complete agreement on a set of requirements (more succinctly: we
failed). The chairs (actually, me) called for a discussion of the
remaining points of contention around requirements, namely hardware
requirements and quantifying wiggle room.

We had a long thread on the former, which degenerated into a discussion
about special primes versus random primes, belatedly resulting in my
message (https://www.ietf.org/mail-archive/web/cfrg/current/msg05610.html)
in which I wrote that:

"I think that we should focus in the immediate future on selecting curves
for special primes for recommendation to the TLS".

No-one objected to this message, as far as I recall from the subsequent
discussions, so I consider that issue settled for the purposes of our
current task. I consider it to be a corollary of this that are no
particular hardware considerations for us to take into account, beyond the
obvious ones with which we started.

Concerning the latter ("quantifying wiggle room"): there was no on-list
discussion that I saw after my message. I understand that it's a delicate
task and that everyone may have had many other things to work on with
higher priority (indeed we are all part-timers here, despite the volume of
messages that may suggest the contrary).

Meanwhile, events have moved on, and, from late November, we (the CFRG
chairs) started to receive messages from our superiors in IRTF and IETF,
namely the IRTF chair (Lars Eggert) and one of the IETF Security Area
Directors (Stephen Farrell) asking us to try to move things more rapidly
towards a conclusion.

When the MGN proposal was put forward, it seemed to the chairs that it
represented a reasonable basis for discussion that, with fine tuning as ,
could meet with the approval of the group.

>while we discussed requirements for curves.

Point taken. But when the original mission fails and the external clock is
ticking, it is surely time to try something else. And the particular
curves that are produced by the (tweaked) meta proposal that is currently
on the table seem to meet all of our agreed security requirements and have
reasonable-to-execllent performance to boot.

> We will not receive

That's indeed an unfortunate collision! However, I think we know what we
mean when we say "compromise" here.

>parties get more influence by having more people send emails to the list.

1. This process has never been a competition, in the AES or SHA-3 sense.
It was not set up that way, and it was not intended to run as such. Maybe
people really are under that misapprehension - it would certainly explain
some of the behaviour and petty point scoring that I've seen on the list.

2. If you want to make an accusation that specific parties have been
"DoSing the list" then I think you need to be more specific than this. You
can direct your comments to the chairs or to Lars Eggert off list if you
wish.

>drafts so that proposals get more influence by being objectively better.

I could not agree more. But what what you have to remember, I think, is
that no single party or group has a monopoly on papers or implementations
in this area. While no-one doubts the high value of the contributions that
you and your co-authors have made over a period of many years to the
development of "modern ECC", there are now plenty of other people who have
learned from and built upon your work.

>... but I think this needs clear requirements, deadlines etc.

And I'll repeat what I wrote above, in short form: we tried to extract
requirements, and while we made progress, we did not complete even this
initial task satisfactorily. I am not apportioning blame for that, and I
will happily take my share of it (and, believe me, some people have been
quick to e-mail me off-list to tell me exactly what my due share of it
is!).

More to follow in the coming days on deadlines and process.

Cheers

Kenny

---

From: Tanja Lange <[email-masked]>
Date: Wed, 31 Dec 2014 19:10:52 +0100

Dear Kenny,
Just one short reply since your reply shows me that my comment has been 
misunderstood.

> learned from and built upon your work.
This was not meant to point at past achievements and I'm sorry if it was
misunderstood this way.

I'm calling for internet drafts (once we know what the requirements are) 
so that then we can write those papers and implementations and then
benchmark them (for some value of 'we' which is likely to include me).

All the best
	Tanja

---

From: "Paterson, Kenny" <[email-masked]>
Date: Wed, 31 Dec 2014 18:30:36 +0000

Dan,

I was going through the recent CFRG messages in order, and then I spotted
the one below, and decided (after consultation with my co-chair Alexey
Melnikov) that it deserved a more immediate response.

Our view is that you have crossed the line of acceptable behaviour in the
way that you are acting on the list, particularly with respect to, but not
exclusively limited to, the message below. Specifically, the tone of the
language and the way you impute motives to other CFRG participants falls
below the levels of professional behaviour that we expect from
participants in the group.

In short: it's time to stop trying to score petty points, making personal
attacks, and using what we can only assume to be deliberately provocative
language. Instead, it's time to start focussing on helping CFRG deliver
the best solution we can, given the externally imposed time constraints
that we are under, and to do so using respectful, constructive language.

I credit you with way too much intelligence not to realise a) what is at
stake here (not only for this particular process, but also for the
reputation of CFRG as a whole) and b) how your recent behaviour will
negatively affect the process. I also know that you are perfectly capable
of restraining yourself. Please start doing so.

Thanks,

Kenny (for the chairs)

On 30/12/2014 21:34, "D. J. Bernstein" <[email-masked]> wrote:

>> of twist-security as Curve25519 < the cofactors of the curve and its

---

From: "D. J. Bernstein" <[email-masked]>
Date: 31 Dec 2014 22:52:45 -0000

Wow. Make a little "Night of the Living PinkBikeShed" joke and suddenly
the chairs go bonkers. :-)

For the record, it was never my intention to characterize Microsoft as a
company that supports zombies. Since PinkBikeShed is a curve that I had
found and publicly rejected a decade ago, and one where Microsoft's
support here didn't even last three weeks, I don't see how anyone could
possibly be offended by this small bit of humor in my message.

I also don't see how people who actually _read_ my message would agree
with the chairs' puzzling list of accusations (namely, that I'm making
"personal attacks"; imputing "motives to other CFRG participants"; using
"deliberately provocative language"; not taking a "professional" tone;
crossing "the line of acceptable behavior"; etc.). Of course, anyone who
_does_ see a problem anywhere in any of my CFRG messages is welcome to
discuss the details with me, in private or in public; but I would
suggest to everyone here---including the chairs---that the CFRG mailing
list should focus on technical issues rather than such side discussions.
My own message started with the relevant procedural background but was
almost entirely about the technical issues, and obviously my messages
overall are very close to 100% about the technical issues, despite the
chairs now (to my disappointment) dragging the percentage down.

I also don't expect my message to cause discussion out of proportion to
the importance of the underlying issues. The reason for the message, as
I said, is for the security advantages of Curve25519 over PinkBikeShed
to be clear for the public record. I don't see any actual technical
dispute remaining; perhaps there will be a few more messages in the
"Mishandling twist attacks" thread, but people who aren't interested can
easily disregard those messages. Of course, it's possible that some of
the related issues will be important for curves that are still on the
table; those issues can and should start new threads.

---Dan

P.S. Happy new year, everybody! Let's try to get the whole Internet
properly authenticated and encrypted in 2015.

---

From: "Salz, Rich" <[email-masked]>
Date: Wed, 31 Dec 2014 17:54:23 -0500

> P.S. Happy new year, everybody! Let's try to get the whole Internet properly
> authenticated and encrypted in 2015.

Hear, hear!