Subject: [Cfrg] Adoption of draft-agl-cfrgcurve-00 as a RG document

From: Alexey Melnikov <[email-masked]>
Date: Mon, 05 Jan 2015 19:15:22 +0000

This message starts 2 weeks adoption call (ending on January 19th 2015) on:

https://www.imperialviolet.org/cfrgcurve/cfrgcurve.xml

as the starting point for the CFRG document which describes an algorithm 
for safe curve parameter generation for a particular security level and 
also recommends a specific curve (2^255-19) for the 128-bit security level.

Please reply to this message or directly to CFRG chairs, stating whether 
you support (or not) adoption of this document. If you do not support 
adoption of this document, please state whether you support adoption of 
any alternative document or whether you want a particular change be made 
to the document before adoption.

Chairs ask not to reiterate previously expressed technical opinions or 
arguments. But clarifying questions on the adoption call are welcome.

While making your decision, please keep in mind

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

Alexey,
On behalf of CFRG chairs.

P.S. Editors of draft-black-rpgecc-01 and 
draft-turner-thecurve25519function-01 can become co-editors of the 
adopted document, if they choose to do so. Email chairs directly if you 
are willing or not willing to do so.

---

From: Adam Langley <[email-masked]>
Date: Mon, 5 Jan 2015 11:49:47 -0800

On Mon, Jan 5, 2015 at 11:15 AM, Alexey Melnikov
<[email-masked]> wrote:
> whether you want a particular change be made to the
> document before adoption.

The structure of the current draft anticipates an additional curve and
also signature work so I'd like to point out a couple of changes to
save others having to do so:

1) If no other curves end up being recommended, then the current
generation process is overly complicated and could well be replaced
with a description that mirrors how curve25519 was actually chosen:
i.e. that the minimal sensible A value in Montgomery form be chosen.
It really depends on how important a generic procedure is seen to be.

2) The procedure for generating base points is currently unused and,
if change (1) is done, it could be tweaked to reflect how the
curve25519 base point was generated.

3) If we don't end up saying anything about signatures, all mention of
Edwards curves could conceivably be dropped.

Not to mention that several sections should be greatly expanded upon,
clarified etc. I think such changes can be considered as a given.

To contrast, if you desire changes like "a different curve should be
recommended" then I think that translates to not supporting adoption.

Cheers

AGL

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

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 05 Jan 2015 19:56:58 +0000

On 05/01/15 19:15, Alexey Melnikov wrote:
> you support (or not) adoption of this document.

I support adoption of AGL's text. I don't care how the text
ends up in one or more cfrg documents and am fine that that
be figured out after the chairs have evaluated the level of
consensus for the content. I'm also fine if changes are made
later to the generation text, (section 6 of [1]) but if the
chairs do conclude that there is consensus for Curve25519 as
part of the output of this exercise then I would have a
problem were that to change later on (assuming no substantive
show-stopper reason is found of course).

S.

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

---

From: Watson Ladd <[email-masked]>
Date: Mon, 5 Jan 2015 15:11:35 -0500

> It really depends on how important a generic procedure is seen to be.

Minimal Montgomery is as generic as minimal Edwards unless I am missing
something.

> clarified etc. I think such changes can be considered as a given.

Were above made, I believe said draft would be largely identical to the
version of draft Turner in github, which has added a description of the
generation proceedure.

I support adoption of either one.

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

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Mon, 5 Jan 2015 20:25:42 +0000

>It really depends on how important a generic procedure is seen to be.

It may be that no other curves are recommended *now*. IMHO it would still
make sense to keep the door open for the possible future need.

>curve25519 base point was generated.

IMHO, it should not be done.

>Edwards curves could conceivably be dropped.

Likewise. I’d keep this stuff in.

---

From: Adam Langley <[email-masked]>
Date: Mon, 5 Jan 2015 12:38:13 -0800

> Minimal Montgomery is as generic as minimal Edwards unless I am missing

That's true, but the world seems to have collectively decided to
minimise the Edwards 'd' these days (NUMS, 41417, Goldilocks, E-521).
So, if we want to publish a generation procedure, an Edward's focused
one might be more helpful.

I don't have strong feelings on this point.

Cheers

AGL

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 5 Jan 2015 23:18:18 +0200

> It really depends on how important a generic procedure is seen to be.

I think curve generation procedure should be there.
 
> curve25519 base point was generated.

Also, the past precent on base point generation on Edwards curves seems
to be the least y, least x with big prime order.

But the procedure here looks acceptable as well.

> Edwards curves could conceivably be dropped.

Also, depending on exact signature scheme, having full isogeny/isomorphism
chains to Weierstrass (these are easy enough to either find or derive, but
still) and back (the dual isogeny for Edwards and Montgomery is more
difficult to find) would be useful.

Specifically, the place where that dual isogneny would be useful is
if using ECDSA (yes, I know) with Weierstrass public keys. That would
avoid implementing Weierstrass (which is somewhat annoying, even if
doing public-only computations and having the field routines).

-Ilari

---

From: Rene Struik <[email-masked]>
Date: Mon, 05 Jan 2015 16:42:22 -0500

Hi Alexey:

Just a small process note here: there is no such thing as an IETF draft 
called draft-agl-cfrgcurve-00.

Given the history of the topic area of this draft, I would strongly 
recommend first submitting this as an IETF/IRTF draft using the ordinary 
IETF submission process. The resulting draft would then be frozen and 
the system would make it easy to track evolution over time. The adoption 
call can then be re-issued with reference to a draft that is actually in 
the IETF system.

Best regards, Rene

On 1/5/2015 2:15 PM, Alexey Melnikov wrote:
> as the starting point for the CFRG document which describes an 
> algorithm for safe curve parameter generation for a particular 
> security level and also recommends a specific curve (2^255-19) for the 
> 128-bit security level.
>
> Please reply to this message or directly to CFRG chairs, stating 
> whether you support (or not) adoption of this document. If you do not 
> support adoption of this document, please state whether you support 
> adoption of any alternative document or whether you want a particular 
> change be made to the document before adoption.
>
> adopted document, if they choose to do so. Email chairs directly if 
> you are willing or not willing to do so.
>

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: Tony Arcieri <[email-masked]>
Date: Mon, 5 Jan 2015 14:00:53 -0800

On Mon, Jan 5, 2015 at 11:15 AM, Alexey Melnikov <[email-masked]>
wrote:

> adoption of this document, please state whether you support adoption of any
> alternative document or whether you want a particular change be made to the

My support of this document is contextual: at present it does not provide a
similar defense for Ed25519 (despite the rigid curve selection guidelines
dealing primarily in Edwards curves) as it does for Curve25519 (which is
Montgomery)

I hope the CFRG does not paint itself into a corner with this document, and
when the question of a signature system arises, I hope Ed25519 will not be
struck down due to an incompatibility with the outlined rigid curve
selection guidelines.

I'm not saying the CFRG should adopt Ed25519, but I would prefer the door
remained open for them to do so.

tl;dr: I would accept this draft so long as it's not a blocker for Ed25519

-- 
Tony Arcieri

---

From: Paul Lambert <[email-masked]>
Date: Mon, 5 Jan 2015 14:07:44 -0800

>to the document before adoption.

Suport!
Excellent start for clear specification

>arguments. But clarifying questions on the adoption call are welcome.

Initial Review Comments:
 - order, #Ed(GF(p)) should be defined in section 5
 - the draft must (eventually) also include a definition of a signature
mechanism
   Picking a curve just for DH would miss system requirements to have
   other public key protocol mechanisms available besides raw DH

Paul

---

From: David Leon Gil <[email-masked]>
Date: Mon, 05 Jan 2015 22:08:03 +0000

Is there any particular need to choose between minimal A and minimal d? Why
not simply specify that both are acceptable options?

This is a minuscule loss to rigidity; two curves versus one per prime.
On Mon, Jan 5, 2015 at 2:01 PM Tony Arcieri <[email-masked]> wrote:

> On Mon, Jan 5, 2015 at 11:15 AM, Alexey Melnikov <
> [email-masked]> wrote:
>
> My support of this document is contextual: at present it does not provide
> a similar defense for Ed25519 (despite the rigid curve selection guidelines
> I hope the CFRG does not paint itself into a corner with this document,
> and when the question of a signature system arises, I hope Ed25519 will not
> be struck down due to an incompatibility with the outlined rigid curve
> selection guidelines.
>

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 5 Jan 2015 14:11:00 -0800

Support, though I agree that minor changes are important for clarity.

Also, I thought Curve25519 used minimal (2 mod 4) A.  Isn’t that equivalent to minimal d due to the isogeny?

Cheers,
— Mike

> On Jan 5, 2015, at 2:08 PM, David Leon Gil <[email-masked]> wrote:
> 
> Is there any particular need to choose between minimal A and minimal d? Why not simply specify that both are acceptable options?
> 
> On Mon, Jan 5, 2015 at 2:01 PM Tony Arcieri <[email-masked] <mailto:[email-masked]>> wrote:
> On Mon, Jan 5, 2015 at 11:15 AM, Alexey Melnikov <[email-masked] <mailto:[email-masked]>> wrote:
> https://www.imperialviolet.org/cfrgcurve/cfrgcurve.xml <https://www.imperialviolet.org/cfrgcurve/cfrgcurve.xml>
> 
> as the starting point for the CFRG document which describes an algorithm for safe curve parameter generation for a particular security level and also recommends a specific curve (2^255-19) for the 128-bit security level.
> 
> Please reply to this message or directly to CFRG chairs, stating whether you support (or not) adoption of this document. If you do not support adoption of this document, please state whether you support adoption of any alternative document or whether you want a particular change be made to the document before adoption.
> 
> My support of this document is contextual: at present it does not provide a similar defense for Ed25519 (despite the rigid curve selection guidelines dealing primarily in Edwards curves) as it does for Curve25519 (which is Montgomery)
> 
> I hope the CFRG does not paint itself into a corner with this document, and when the question of a signature system arises, I hope Ed25519 will not be struck down due to an incompatibility with the outlined rigid curve selection guidelines.
> 
> I'm not saying the CFRG should adopt Ed25519, but I would prefer the door remained open for them to do so.
> 
> [email-masked] <mailto:[email-masked]>
> http://www.irtf.org/mailman/listinfo/cfrg <http://www.irtf.org/mailman/listinfo/cfrg>

---

From: Alyssa Rowan <[email-masked]>
Date: Tue, 06 Jan 2015 10:03:54 +0000

>as the starting point for the CFRG document which describes an algorithm for safe curve parameter generation for a particular security level and also recommends a specific curve (2^255-19) for the 1…

Support.

Needs some work doing, of course, but it's a good draft representing where we are.

Regarding Rene's point: Agreed. In particular, for everyone's protection and peace of mind, please be mindful that the IPR disclosure rules ought to stay in full effect for all contributions to this document and throughout this process. (Easily editable where it is, but move it here on CFRG adoption: is that the plan?)

Regarding Tony's point: also agreed, in the main. Signatures will be needed in due course (but perhaps not quite as urgently as the rest?). Ed25519 is one potential candidate on the table, and I don't think we've really explored signatures enough to rule anything out at this stage. We can deal with that later on, I hope.

- --
/akr

---

From: Dan Brown <[email-masked]>
Date: Tue, 6 Jan 2015 16:28:38 +0000

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Alexey Melnikov
> 
for
> safe curve parameter generation for a particular security level and also
> recommends a specific curve (2^255-19) for the 128-bit security level.
> 
you
> support (or not) adoption of this document. 

[DB] I would definitely support this if the CFRG is open to later (say,
perhaps after a six-month cooling-off period) discussion of some alternative
elliptic curves, such as, a similar set of curves with say random
j-invariant, and perhaps some other security characteristics.

I trust the other CFRG members to have verified that the current proposals
have made improvements over older curves on side channel resistance,
ease-of-implementation, and efficiency (which can also be useful for a
security by boosting the curve size).  So, I think any future curves should
maintain those characteristics: my condition above does not hinge on
revisiting those issues.

I agree that a rigidity-like property does indeed slightly reduce the
security risk compared to an inexplicably-chosen curve.  I'm for
risk-reduction. I think there is room to reduce the security risk further
(or at least in a different direction), compared to the rigid-type curves,
hence the condition on my support.  I am not too worried on the details of
how rigidity is achieved, since it is rather small thing compared to
resisting known attacks (e.g. side channels, error-prone complexity), and
compared to what I think are the more realistic risks, or at least possibly
better risk-reduction methods. So, if the current logjam in CFRG consensus
is only about which rigidity-like properties to prefer, with the effect that
the other more substantial security improvements are being delayed, then I
support the chairs pushing ahead.  That leaves a small risk between flavours
of rigidity, but I see that small risk as worth the other substantial
security gains, especially if we are open to revisiting risk-reduction in
the future.

Best regards,

Dan

---

From: David Gil <[email-masked]>
Date: Tue, 6 Jan 2015 18:53:48 +0000 (UTC)

Support.

---

From: Alexey Melnikov <[email-masked]>
Date: Tue, 6 Jan 2015 20:18:52 +0000

Hi Rene,

> On 5 Jan 2015, at 21:42, Rene Struik <[email-masked]> wrote:
> 
> Hi Alexey:
> 
> Just a small process note here: there is no such thing as an IETF draft called draft-agl-cfrgcurve-00.

True. I was referring the document on Adam's website.

> Given the history of the topic area of this draft, I would strongly recommend first submitting this as an IETF/IRTF draft using the ordinary IETF submission process. The resulting draft would then be frozen and the system would make it easy to track evolution over time. The adoption call can then be re-issued with reference to a draft that is actually in the IETF system.

There is no requirement to post a draft as IETF draft before asking for adoption, but obviously the draft need to be posted as an IRTF draft, if it ends up being adopted by CFRG. But considering that Adam copied text from two existing drafts and Adam's history of participation in IETF/IRTF, I don't foresee any problems.

Anyway, I asked Adam to post his version to datatracker. In the meantime, I would ask people to continue to comment on the version on Adam's website.

>> Chairs ask not to reiterate previously expressed technical opinions or arguments. But clarifying questions on the adoption call are welcome.
>> 
>> P.S. Editors of draft-black-rpgecc-01 and draft-turner-thecurve25519function-01 can become co-editors of the adopted document, if they choose to do so. Email chairs directly if you are willing or not willing to do so.
>>

---

From: Sean Turner <[email-masked]>
Date: Tue, 6 Jan 2015 19:19:56 -0500

support adoption

These nits can be fixed whenever:

0) In s9, Watson/Tanja reminded me that we got this wrong in our draft (fixed in the editor’s working copy but not published):

old:
	e.g., as mask(s_t) = 1 - s_t
new:
	e.g., as mask(s_t) = 0 - s_t

1) In s9.1 (from a comment Rich Barnes made on our draft):

old:
	where 9 is the number 9
new:
	where 9 is the number 9, represented as a 32-byte
	integer in the little-endian representation described
	in Section 8.

2) In s9 & s9.1: (also from Richard):

There are a couple of magic values that appear, a24 in Section 4 and 9 in Section 5.  For a24, it would be helpful just to say "(see [Curve25519])" to reinforce that this document isn't making it up.  For 9, it would be helpful to note that this fixed value is simply the chosen base point for Curve25519 (in the language of traditional ECDH).

3) In s9.1 (also from Richard):

r/leftmost/most significant
r/rightmost/least significant

4) Needs a security considerations and an iana considerations section.

spt

---

From: Alexey Melnikov <[email-masked]>
Date: Thu, 8 Jan 2015 13:17:13 +0000

Hi Rene,

> On 6 Jan 2015, at 20:18, Alexey Melnikov <[email-masked]> wrote:
> 
> Hi Rene,
> 

Adam done that.

---

From: Andrey Jivsov <[email-masked]>
Date: Thu, 08 Jan 2015 13:36:21 -0800

For http://tools.ietf.org/html/draft-agl-cfrgcurve-00:
>
> 9. Elliptic Curve Diffie-Hellman
>
>
...
>        z_2 = E * (AA + a24 * E)
>        // Conditional swap; see text below.
>        (x_2, x_3) = cswap (s_t, x_2, x_3)
>        (z_2, z_3) = cswap (s_t, z_2, z_3)
>    Return x_2 * (z_2^(p - 1))

should be

      Return x_2 * (z_2^(p - 2))

> 8. Wire-format of field elements

>    When transmitting field elements in the Diffie-Hellman protocol
>    below, they MUST be encoded as an array of bytes, x,

I would like to see an uncompressed format allowed as (x,y) as an 
optional format. This avoids ~10% performance penalty for some 
applications, v.s. the case when only (x) is sent.

the y above can be calculated for "free" at the end of Montgomery ladder 
calculation due to the above z_2^-1 inverse calculation, using a method 
described in section 5 (p.13-14) in 
http://ed25519.cr.yp.to/ed25519-20110705.pdf. The code would be needed 
anyway for decompression with signatures that use compressed point.

Likewise, receiving (x,y) allows a conversion to a projective form of 
twisted Edwards coordinates for "free" for a peer. At the same time a 
peer is free to ignore y and proceed with the Montgomery ladder 
multiplication exactly as described in sec 9.

Therefore, (x,y) on the wire allows the most suitable choice of 
implementation for ECDH, whereas (x) limits it to Montgomery ladder 
given that one needs to overcome the 10% penalty of recovering y with a 
square root.

Many applications and protocols will require generation of a new ECDH 
key pair (i.e. they cannot reuse it). For these applications fixed-base 
scalar multiplication on Edwards curve is much faster. These 
applications may prefer to use the same code for variable-base scalar 
multiplication as well. Likewise, the code reuse argument applies to 
applications that support signatures on Curve25519.

I support the draft with the above tweak.

---

From: Watson Ladd <[email-masked]>
Date: Thu, 8 Jan 2015 16:51:18 -0500

On Thu, Jan 8, 2015 at 4:36 PM, Andrey Jivsov <[email-masked]> wrote:
> I would like to see an uncompressed format allowed as (x,y) as an optional
> format. This avoids ~10% performance penalty for some applications, v.s. the
> case when only (x) is sent.
>

Three points:

1: There are recurring security issues caused by not sending
compressed points, as well as additional complexity
2: We're not talking about signatures in this draft.
3: Options are bad.

> twisted Edwards coordinates for "free" for a peer. At the same time a peer
> is free to ignore y and proceed with the Montgomery ladder multiplication
> exactly as described in sec 9.
>
> implementation for ECDH, whereas (x) limits it to Montgomery ladder given
> that one needs to overcome the 10% penalty of recovering y with a square
> root.
>
> Many applications and protocols will require generation of a new ECDH key
> pair (i.e. they cannot reuse it). For these applications fixed-base scalar
> multiplication on Edwards curve is much faster. These applications may
> prefer to use the same code for variable-base scalar multiplication as well.
> Likewise, the code reuse argument applies to applications that support
> signatures on Curve25519.

4: Fixed based scalar optimizations already require different code
from variable base for maximal speed: combs vs. radix. The Montgomery
ladder is so small that using it for variable base multiplication
isn't a major complexity increase.

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

---

From: Adam Langley <[email-masked]>
Date: Thu, 8 Jan 2015 14:36:06 -0800

>      Return x_2 * (z_2^(p - 2))

Thanks, fixed in Github.

Cheers

AGL

---

From: Andrey Jivsov <[email-masked]>
Date: Thu, 08 Jan 2015 16:11:05 -0800

> 2: We're not talking about signatures in this draft.

Regarding options, this draft is a foundational document of a low-level 
crypto primitive. Protocols above can still pick a single wire format.

The spec should allow, for example, S/MIME to select (x) for space 
saving, while TLS to select (x,y) for performance. (I am not making 
these choices here).

The entire document is an optional primitive. SuiteB and Brainpool 
curves will be around for awhile.

One might say that the proposed tweak retains a single format, which is 
(x,y), with an available (internal) optimization to use x with a 
Montgomery ladder.

Re: security issues, the easiest fix would be to add one paragraph to to 
check that (x,y) is on the curve. The spec already deals with the 
cofactor>1 in section 9.1.

---

From: Watson Ladd <[email-masked]>
Date: Thu, 8 Jan 2015 19:50:14 -0500

On Thu, Jan 8, 2015 at 7:11 PM, Andrey Jivsov <[email-masked]> wrote:
> The spec should allow, for example, S/MIME to select (x) for space saving,
> while TLS to select (x,y) for performance. (I am not making these choices
> here).

The performance gain you've been repeatedly citing is nonexistent for
variable base multiplications, and can be achieved for fixed based
mults anyway. Let's look at Curve25519 in detail:

A Montgomery ladder implementation does 255 rounds of a differential
addition and doubling, each differential addition 8.2 multiplications
(z=1 initially) This is a total cost of 2091 multiplications. At the
end there is an inversion, cost around 400 multiplications, grand
total 2491.

An Edwards-based implementation, using the fastest coordinates (which
are incomplete: I'll neglect this) with a window of width 5 will first
compute 31 multiples of the basepoint, then carry out 51 additions and
254 doublings. Each point addition costs 9.8 muls, each doubling 6.2
muls. The cheapest computation of the table is 15 doublings and 15
additions. At the end there is again an inversion, cost around 400
multiplications. The cost of this computation is 2714 multiplications.

Now, you could object that I've not used a large enough window, but
larger windows slow down side-channel protected lookups. You could
also object to my eschewing wNAF or some other advanced encoding, but
these are harder to protect against side-channels due to an irregular
pattern of additions. You could try to add in additional inversions to
save on multiplications by forcing z=1, but for curves this size the
gains are small. You could object to my inversion numbers: they are
probably too large.

For fixed based multiplications we use combs, so there is a speedup,
but Montgomery wire format doesn't interfere with this operation.

Furthermore, the TLS WG doesn't know nearly as much about cryptography
as we do. Other WGs are likely to know even less.

>
> The entire document is an optional primitive. SuiteB and Brainpool curves
> will be around for awhile.
>
> (x,y), with an available (internal) optimization to use x with a Montgomery
> ladder.
>
>
> check that (x,y) is on the curve. The spec already deals with the cofactor>1
> in section 9.1.

An implementer who omits clearing the low bits isn't going to
completely break everything. One who omits this check will. Despite
lots of documents explaining the necessity of validation, plenty of
implementations fail to do it consistently.

Sincerely,
Watson Ladd

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 09 Jan 2015 09:38:01 +0000

Hiya,

Not on the crypto but on the options bit, and with an IETF
participant hat firmly on my head...

I would hope that CFRG will not include any optional things
unless there is a significant benefit from doing so *and*
very very clear guidance for non-security experts on when
to pick which option.

Having options that only offer a marginal benefit would I
think be fairly clearly harmful. I'm happy that CFRG folks
can and will evaluate the performance and side channel
etc. aspects of that. If some help is needed with information
as to whether there's a possible significant benefit for
some particular (kind of) protocol, then I'm very happy
to help find the right developers or IETF folk to ask.
(I'm sure Alexey would do that anyway though, but I can
help if needed.)

If the result of this exercise does have some options, then
it'll be very important that those come with very clear and
easy to understand guidance as to when to choose which option.
That guidance needs to be understandable by a non-security
expert - there are many cases where non-security folks add
security features to their protocols and by the time those
do get reviewed by someone who'd understand ECC it can be
too late to make changes to PDU formats, management models
etc.

If CFRG cannot include such explanatory text, then I really
hope you just pick one of the optional things and drop the
rest.

The reasons to not like options here are that IETF WGs and
then implementers will make different choices leading to
a lack of interop and tooling difficulty.

The interop issue would likely arise if the guidance on
when to use which option wasn't sufficiently clear. Or if
a protocol has use-cases that match the guidance for more
than one option. In either case protocol designers will
probably just include all the options and pass on the
difficulty to implementers and deployments. And when those
make different choices we'd see interop issues.

The tooling issue would be arise if different protocols
make different choices. In that case, we'd likely see tools
developed that only support one option and that could delay
deployment for protocols that need one of the other options.

So pretty please, no options without significant benefits
*and* utterly crisp and easily understood guidance as to
when to use which option.

Thanks,
S.

---

From: Alexey Melnikov <[email-masked]>
Date: Fri, 9 Jan 2015 12:18:08 +0000

Hi,
I would like to remind people to rename subjects when changing topics in order to help people to follow discussions.

Thank you,
Alexey

---

From: Joppe Bos <[email-masked]>
Date: Fri, 9 Jan 2015 13:59:45 +0000

Hi all,

The current version of the draft contains methods for parameter selection
(section 6) and a single recommended curve (section 7). 
IMO the natural approach would be to first agree upon a parameter selection
procedure (one draft) and subsequently, when a large portion of the
community agrees that this selection procedure is sound, use this procedure
to select new curves (another draft). Currently, we are changing the
selection procedure to match an existing curve. If we want curve25519
because it is fast and widely deployed then we should state this clearly and
refrain from modifying the selection procedures because this might have a
negative impact on the potential selection of curves in the future. 

Please find below some comments on the current version of the draft.

Section 7: 
- The specification of the parameters is done either in formula form (p), in
decimal (d) or a formula + hexadecimal (order). Maybe use the same notation
(e.g. either decimal or hexadecimal) everywhere to avoid confusion?
- For completeness it might be good to give the corresponding (short)
Weierstrass form of the curve(s).

Section 8-10:
These sections are curve25519 specific, this should be stated much clearer.

Section 8:
As far as my understanding goes there was no consensus on the wire format of
field elements. 
This section states that "when transmitting field elements in the
Diffie-Hellman protocol below, they MUST be encoded as an array of bytes, x,
in little-endian order". Maybe some notation got confused here, what is this
x-coordinate? The only x defined are on the Edwards curve while I think here
the Montgomery curve is meant (the u-coordinate from section 7). This should
be fixed or stated clearer to avoid confusion.

Section 9:
- It is not entirely clear to me why such low-level details are provided in
this draft. Is it expected from the CFRG to deliver implementation details
for algorithms or just a specification of curves plus related info (such as
wire formats)? If we want to provide such low-level details then why not
also state how to implement the field arithmetic?
- Why is only the approach based on the Montgomery ladder stated in this
section? There is nothing wrong with the Montgomery ladder but it is not the
best solution for all reasonable definitions of best. The implementer has
the choice, as stated before on this list, to compute DH on (for instance)
the corresponding Edwards or Weierstrass curve. Currently it looks as if the
CFRG recommends to use the Montgomery ladder for all scenarios;  something
we know is suboptimal in terms of performance for higher security levels.
Moreover, imagine the scenarios where people use (twisted) Edwards curves
for signatures. Then implementing DH using the Montgomery ladder implies
managing code for both the Montgomery and the twisted Edwards curve and,
following the reasoning expressed by some people on this list, a larger code
base implies more room for errors which implies a less secure approach. 
- This ladder implementation defines the usage of cswap ("due to the
existence of side-channels in commodity hardware"). Although this adds some
protection this algorithm is not secure in many realistic threat models
(e.g. in hardware security). To me, it looks quite arbitrary to just protect
against one type of attack and not against a whole range of other
side-channel attacks. The threat model should depend on where the
implementation will be used and therefore it is up to the implementer to
make the appropriate design decisions and introduce the adequate
countermeasures. 

Best regards,

Joppe

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of Alexey Melnikov
Sent: Monday, January 05, 2015 8:15 PM
To: [email-masked]
Subject: [Cfrg] Adoption of draft-agl-cfrgcurve-00 as a RG document

as the starting point for the CFRG document which describes an algorithm for
safe curve parameter generation for a particular security level and also
recommends a specific curve (2^255-19) for the 128-bit security level.

Please reply to this message or directly to CFRG chairs, stating whether you
support (or not) adoption of this document. If you do not support adoption
of this document, please state whether you support adoption of any
alternative document or whether you want a particular change be made to the
document before adoption.

Alexey,

P.S. Editors of draft-black-rpgecc-01 and
draft-turner-thecurve25519function-01 can become co-editors of the adopted
document, if they choose to do so. Email chairs directly if you are willing
or not willing to do so.

---

From: Paul Hoffman <[email-masked]>
Date: Fri, 9 Jan 2015 08:09:02 -0800

+1 to everything Stephen said about "please don't give us options unless you explain them very clearly, and maybe not even then". IPsec implementers and, more importantly, users have suffered badly over the past two decades due to excessive optionality, particularly in the crypto. TLS has this problem too, of course.

--Paul Hoffman

---

From: Andrey Jivsov <[email-masked]>
Date: Fri, 09 Jan 2015 12:51:10 -0800

Hello Stephen. I agree in general that fewer options is a good thing.

The current format on the wire:
   (x)
proposal:
   (x,y)

The second covers the first.

While the point representation negotiation defined in TLS works OK IMO, 
the de-facto standard on the Internet is to use uncompressed point. 
(x,y) above is a natural choice then. (If you like Montgomery ladder, 
just ignore the other 32 bytes representing the y; one shouldn't care 
about 32 bytes in a ~4Kb TLS handshake).

Assessing significance is subjective. Not sending y means square root 
calculation for some implementations, which has cost of recovering y at 
~10%, which narrows the choice of implementations (including the future 
ones). I would say that I care about 10% because Curve25519 Montgomery 
ladder is ~60% faster than P-256 on modern x86.

There is likely to be a greater performance benefit to send y at 
security level beyond P-256. A single format across security strengths 
and algorithm types means fewer options.

---

From: Alyssa Rowan <[email-masked]>
Date: Sat, 10 Jan 2015 12:35:26 +0000

> Hello Stephen. I agree in general that fewer options is a good 

Agreed there too.

> A single format across security strengths and algorithm types means
> fewer options.

Now, the upstream WG asking for these curves has actually already
covered this point (if you'll excuse the pun!).

The TLS WG discussed point compression specifically¹ and thought there
was value for TLS 1.3.

In Hawaii² they decided to use uncompressed points for existing NIST &
Brainpool curves (due to the inertia you noted, and the now-expired
patent, essentially nobody used compressed points with the NIST &
Brainpool curves) - but to allow new curves (i.e. us) to define their
own wire format individually, which is what is done in the draft, and
that this could be compressed. (X25519, as Curve25519, was in fact
specifically raised within that discussion³.) So…

> …the point representation negotiation defined in TLS…

…is being removed from TLS 1.3. And we can do pretty much what we want.

> (If you like Montgomery ladder, just ignore the other 32 bytes 
> representing the y; one shouldn't care about 32 bytes in a ~4Kb TLS
> handshake).

"Ignore it if you like" is just an option (to ignore it) in a fancy hat.
Drawback: fingerprinting. An attacker can tell which ignore y and which
don't (and therefore which might have omitted or screwed up a vital
validation step).

I also note patent US6563928 appears (to me, and others) to claim on
point validation to avoid small-subgroup attacks⁴ in some contexts. Dan
Brown disclosed this patent previously on the list, querying whether it
may impact twist security⁵. It expires (I believe) mid-May 2015 - and I
(again) do not specifically address its applicability or validity here,
merely note the concerns.

djb, in Curve25519, specifically used the point format from Miller
[1986], and deliberately doesn't compute y. So…

> …the de-facto standard on the Internet is to use uncompressed 
> point.

…the de-facto standard for _this curve_ is to use _compressed_ point, as
in the draft. It:

• is simpler as it doesn't need a (critical) point validation check;
• seems to have clearer IPR, because that check may have patent claims;
• is slightly smaller; and,
• is already supported by all the widely-deployed code for this curve.

No sale on a change there, as far as I'm concerned: I don't see the
significant benefit.

> I would say that I care about 10% because Curve25519 Montgomery 

Um, perhaps I just haven't had enough tea this morning to follow what
you mean here?

I'm also not sure the performance gap is that wide anymore, see Intel's
nistz256 contribution to OpenSSL.

___

Footnotes (for easy reference):

[1] <https://www.ietf.org/mail-archive/web/tls/current/msg14087.html>

[2]
<https://www.ietf.org/proceedings/interim/2014/11/09/tls/minutes/minutes-interim-2014-tls-4>

[3] <https://www.ietf.org/mail-archive/web/tls/current/msg14088.html>

[4] US6563928, Menezes-Qu-Vanstone, Certicom
<https://www.google.com/patents/US6563928>

[5] <https://www.ietf.org/mail-archive/web/cfrg/current/msg05588.html>
although you may find it easier to read
<https://www.ietf.org/mail-archive/web/cfrg/current/msg05589.html> and
down. Short answer: no.

[6] <https://www.ietf.org/mail-archive/web/cfrg/current/msg04766.html>

- -- 
/akr

---

From: Andrey Jivsov <[email-masked]>
Date: Mon, 12 Jan 2015 01:00:11 -0800

On 01/10/2015 04:35 AM, Alyssa Rowan wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
>

It looks reasonable to remove compression negotiation packets from TLS.

To allow other implementations besides the Montgomery ladder y is 
probably need to be a part of point format on the wire to avoid the ~10% 
penalty to recover it.

> don't (and therefore which might have omitted or screwed up a vital

One would likely need (x,y) to allow the choice of (internal, invisible 
to a peer) implementations. It's almost certain that sending only x 
significantly benefits the Montgomery ladder implementation, because 
there will unlikely be a faster implementation that uses only x (or 
doesn't benefit from the input point being in affine form, so that z!=1 
can be used without cost).

When both (x,y) are used in the scalar multiplication formula, 
re-computing y from x has ~10% cost.

> • is simpler as it doesn't need a (critical) point validation check;

I think 'critical' is arguable for twist-secure curves and TLS ECDH, 
however, please note that the Montgomery ladder is an implementation 
choice when one doesn't wants these checks.

> • seems to have clearer IPR, because that check may have patent claims;

The abstract of the patent telling to multiply by a cofactor (8) to 
avoid a small subgroup is also an issue.

> No sale on a change there, as far as I'm concerned: I don't see the

Thank you for the feedback, Alyssa.

> nistz256 contribution to OpenSSL.

The ratio is from 
http://www.ietf.org/mail-archive/web/cfrg/current/msg05251.html . It's 
about the same 60% on Haswell.

...

---

From: Robert Ransom <[email-masked]>
Date: Sun, 18 Jan 2015 23:32:57 -0800

> also recommends a specific curve (2^255-19) for the 128-bit security level.

My comments below are based on the document submitted to IETF and
published as the Internet draft draft-agl-cfrgcurve-00.  That document
is dated 2015-01-06, after you published your call for adoption.

I have not attempted to determine whether there are any other
differences between the draft posted at the URL you specify at the
time of the call for adoption and the Internet draft.

> to the document before adoption.

I strongly oppose adoption of this document:

* Adam Langley was listed as a co-author of draft-black-rpgecc-00 and
  draft-black-rpgecc-01.  No one who co-authored either of those two
  documents should be considered as an editor or co-editor of any
  future CFRG document.

* The curve selection procedures specified in draft-agl-cfrgcurve-00
  were derived from the curve selection process specified in
  <https://eprint.iacr.org/2014/130> (referenced by
  draft-black-rpgecc-00 as [MSR]), and accordingly, the authors of
  [MSR] may require that their paper be cited as a reference by
  draft-agl-cfrgcurve-00.  For reasons which have already been
  discussed, inclusion of [MSR] as a reference in any CFRG document is
  unacceptable.  Thus, these curve selection procedures must not be
  included in any CFRG document.

I also oppose adoption of this document for other reasons which have
previously been raised; see below.

I would support adoption of draft-turner-thecurve25519function,
provided that it is never changed to include in its text any curve
selection procedure derived from [MSR] or from any Internet-Draft by
the authors of [MSR].

> arguments. But clarifying questions on the adoption call are welcome.

The following technical issues were raised prior to your call for
adoption of draft-agl-cfrgcurve-00:

* Curve3617 (also known as Curve41417) has cofactor 8, and is defined
  over a field of order congruent to 3 mod 4.  Accordingly, the curve
  selection procedure in draft-agl-cfrgcurve-00 will choose a
  different curve if applied to the field used for Curve3617.  (This
  point was previously raised to CFRG in
  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05788.html>.)

  The curve selection procedure specified in draft-agl-cfrgcurve-00
  will instead choose a curve with d > 2^19 (found by D. J. Bernstein
  (et al. ?), found again by Mike Hamburg, and found yet again and
  published recently by David Leon Gil), compared to d=3617 < 2^12 for
  Curve3617.  The parameter value for the twist-secure curve with
  cofactor 4 is so much larger than the parameter value for cofactor 8
  that the performance of at least one implementation strategy of some
  significance would be harmed by insisting on cofactor 4: current
  FPGAs contain 18-bit multipliers, and d > 2^19 almost guarantees a
  greater cost to multiply by the curve parameter.

  With the point format specified in draft-agl-cfrgcurve-00, there is
  no technical benefit to switching to a curve with cofactor 4 over
  the field used for Curve3617.

* It is possible that the point format specified in section 9 of
  draft-agl-cfrgcurve-00 for ECDH (in order to match Curve25519 ECDH
  implementations) may be suboptimal for future curves.  Mike Hamburg
  has developed a compressed point format which can only represent
  points of odd order on curves with cofactor 4, and which seems to be
  compatible with the Montgomery ladder.  (This point was previously
  raised to CFRG in
  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05654.html>.)

  A modern Schnorr-like signature (like EdDSA) usually consists of one
  group element and one scalar, to allow for batch verification.  On
  elliptic-curve groups of composite order, a malicious signer can
  generate signatures which will pass batch verification and fail the
  simplest, fastest single-signature verification procedure, and
  vice-versa.  Thus, implementors of single-signature verification
  have an engineering trade-off regarding whether to verify single
  signatures as quickly as possible or match the behaviour of batch
  verification; and implementors also have an engineering trade-off
  regarding whether to attempt to use batch verification at all.

  In some applications -- notably anonymity systems, but other systems
  are severely affected as well -- implementation-distinguishing
  attacks such as those can be quite severe.

  Mike Hamburg's new point format would eliminate those cofactor-based
  implementation-distinguishing attacks, but only for curves with
  cofactor 4.  Thus, it may be appropriate for CFRG to recommend a
  curve other than Curve25519 for signatures, in order to obtain this
  technical benefit.

  Note that ECDH can be designed (with careful attention to proper
  handling of edge cases) to not have implementation-distinguishing
  attacks.  Curve25519 ECDH, as it is currently widely implemented,
  has come to have an especially well-specified behaviour, and I
  believe that CFRG should not delay use of Curve25519 ECDH in
  IETF-controlled protocols further in the hope of switching to a
  different curve in order to use the new point format.

* The basepoint selection procedure specified in section 6.3 of
  draft-agl-cfrgcurve-00 generates a different basepoint for
  Curve25519 than the standard basepoint currently in use for
  Curve25519, which is specified implicitly in the draft in section
  9.1.  (This point was previously raised to CFRG in
  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05709.html>.)

  The simplest implementation strategy for ECDH is to implement both
  key generation and shared-secret computation using the same
  variable-base single-scalar multiplication routine.  This
  implementation strategy can be made easier, simpler, and less
  error-prone to implement, at absolutely no cost to any other
  implementation strategy, by choosing the basepoint to have a simple
  form when expressed in the point format chosen for public keys.  For
  example, the Curve25519 standard basepoint is the number 9,
  expressed as a 32-byte little-endian integer.

  It appears to me that the basepoint selection procedure specified in
  draft-agl-cfrgcurve-00 will not generate a basepoint of a simple
  form for any point format which might plausibly be used, so that
  basepoint selection procedure should be discarded entirely.

* The curve selection procedure specified in draft-agl-cfrgcurve-00
  for fields of order congruent to 1 mod 4 was concocted, at the
  direction of the CFRG chairs, solely to reproduce a curve isogenous
  to Curve25519.  This is diametrically opposed to the purpose which
  the CFRG chairs claim that the curve selection procedure is supposed
  to perform.  (This point was previously raised to CFRG in
  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05637.html>.)

  Including a curve selection procedure which has been evaluated
  solely based on whether it will reproduce one curve or a small
  number of curves in a CFRG document may cause harm to people who use
  that curve selection procedure to produce additional curves.

  This point has been raised to CFRG again during this call for
  adoption of draft-agl-cfrgcurve, in
  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05860.html>,
  despite the chairs' request that technical issues previously brought
  to CFRG's attention not be raised again.

* The curve selection procedure specified in draft-agl-cfrgcurve-00
  for fields of order congruent to 1 mod 4 does not require that both
  the curve and twist subgroup orders be greater than a power of 2
  near q/8, even in fields of order sufficiently close to a power of 2
  that such a requirement is feasible and is sufficient to allow a
  simple bit-masking procedure to generate scalars which act as
  non-zero on all curve and twist points of large order.  (This point
  was previously raised to CFRG in
  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05606.html>
  and
  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05629.html>.)

  Over the specific field used for Curve25519, this property is
  implied by the other criteria already used in the curve selection
  procedure.  Since the CFRG chairs' goal was to create a curve
  selection procedure which would reproduce Curve25519, not to create
  a curve selection procedure for general use, they apparently did not
  realize that the curve selection procedure might retain this issue
  when used over other fields.

* If CFRG chooses the curve generation procedure, point format, and
  basepoint selection procedure specified in draft-agl-cfrgcurve-00
  based solely on the fact that they reproduce the current Curve25519
  ECDH protocol, as is currently the case, then CFRG's resulting
  document may make decisions that would be inappropriate for future
  curves.  (This point was previously raised to CFRG in
  <http://www.ietf.org/mail-archive/web/cfrg/current/msg05793.html>.)

I believe that each of these previously stated technical issues is
sufficient to oppose adoption of draft-agl-cfrgcurve-00.  Why have the
CFRG chairs asked that these issues not be discussed further?

Robert Ransom

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 19 Jan 2015 16:39:29 +0200

>   greater cost to multiply by the curve parameter.

I got d=-142113 (#E<p)  (d=142114 if one additionally requires #E>p)

These numbers are 18-bit in absolute value.

-Ilari

---

From: Robert Ransom <[email-masked]>
Date: Mon, 19 Jan 2015 17:32:42 -0800

> These numbers are 18-bit in absolute value.

Thank you for the correction!  (David Leon Gil had reported a curve in
the isogeny class of a=1, d=-547072.)

I've recomputed the trace of the curve with a=1, d=-142113 using GP,
and it and its twist are indeed of order 4*prime.  The prime-order
subgroup of that curve has maximal multiplicative embedding degree
(r-1), and its twist's subgroup has multiplicative embedding degree
(r'-1)/4; the discriminant of its endomorphism ring is large; and the
factorizations involved in verifying those are fairly easy.

The parameter d=-142113 is still large enough to require more carrying
after multiplication by the curve parameter in an implementation which
uses 16-bit limbs and must reduce limbs to 16 bits each before
multiplication.  I'm not certain whether this would be the case for
FPGA-based implementations, but it is still enough of a difference in
parameter size that I would strongly prefer d=3617 for use with the
point format specified in draft-agl-cfrgcurve-00.

Robert Ransom

---

From: Alexey Melnikov <[email-masked]>
Date: Tue, 20 Jan 2015 11:14:34 +0000

Robert,

On 19/01/2015 07:32, Robert Ransom wrote:
> On 1/5/15, Alexey Melnikov<[email-masked]>  wrote:
  [snip]
>    documents should be considered as an editor or co-editor of any
Decisions about who edit a particular CFRG document belongs to CFRG 
chairs (according to IETF and IRTF rules). In particular chairs can fire 
and hire editors of documents.
So this is not a valid excuse for not adopting a draft.

Concerns about editors of CFRG documents should be voiced *privately* to 
chairs.

Best Regards,
Alexey

---

From: Alexey Melnikov <[email-masked]>
Date: Wed, 21 Jan 2015 19:24:59 +0000

Robert,

  [snip]
  [snip]
>    included in any CFRG document.
If you are referring to the Microsoft patent, then it doesn't apply to 
the curve selection procedure, so this is a non issue.

Best Regards,
Alexey

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 22 Jan 2015 13:53:05 -0800

> tl;dr: I would accept this draft so long as it's not a blocker for Ed25519

agl addressed my concerns in a separate thread, so I will officially say
support now

-- 
Tony Arcieri

---

From: Alexey Melnikov <[email-masked]>
Date: Sat, 24 Jan 2015 17:57:25 +0000

Dear CFRG participants,

> http://www.ietf.org/mail-archive/web/cfrg/current/msg05813.html
Thank you for all the constructive feedback.

Chairs have reviewed responses to this message (both public and some 
private) and can confirm that there is rough consensus for adopting 
draft-agl-cfrgcurve-00 as a RG document. Some people supported the 
document with conditions that some changes would (or would not) be done 
to it, although the majority of people supported it unconditionally. 
Some people who objected to the document being adopted asked about 
changes that were also asked by people who supported the document, so we 
are hoping that a future revision of the draft might become acceptable 
even to them.

Chairs are asking Adam to republish draft-agl-cfrgcurve-00 as 
draft-irtf-cfrg-curves-00. Chairs are in the process of discussing who 
would be editors of the CFRG document.

Best Regards,
Alexey,

---

From: Stephen Farrell <[email-masked]>
Date: Sat, 24 Jan 2015 18:27:54 +0000

Excellent! Thanks (to the chairs and us all) for solidifying this
useful bit of progress. I hope subsequent bits can build on this
more easily than has been the case up until now:-)

Cheers,
S.

---

From: Rene Struik <[email-masked]>
Date: Tue, 27 Jan 2015 13:15:22 -0500

Dear colleagues:

It seems that draft-agl-cfrgcurve-00 contains a few technical flaws, 
including:
a) Section 9, p. 10:
The Montgomery ladder works on projective points of the form (X:Y:Z), or 
(X::Z) {if the Y-coordinate is deleted}, where x=X/Z, y=Y/Z, and where 
the point at infinity is (1::0).
If so, one has Q-Q'=(x1::z1)=(u::1), Q'=(x2::z2)=(1::0) {the point at 
infinity}, and Q=(x3::z3)=(u::1).
With the draft, one mistakenly has (x2::z2)=(0::1), i.e., the 
representation of the affine point (0,0) of order two. In that case 
Montgomery Adds results in (u::1) + (0::1) = (4::4u^3)~ (1:: u^3). So, 
the procedure outputs on input Q:=(u::1) and scalar k=1, the incorrect 
output R:=(1::u^3) (with x-coordinate u^{-3}), rather than simply u.
b) Section 9, p. 10:
The Montgomery ladder should produce, on input Q=(x1::z1) and scalar k, 
the output R:=kQ=(x2::z2), which can be mapped to an affine point with 
x-coordinate x2/z2.
With the draft, one mistakenly takes 1/z2 = z2^{p-1}, whereas this 
should obviously be z2^{p-2} (if z2 is nonzero).
c) Section 9, p. 10:
The Montgomery ladder does not produce the output R=kQ for each input Q 
and scalar k, since, e.g., (after correcting the flaw identified in #a 
above), one can end up with the unidentified string projective point 
(0::0) in some cases. So, one should clarify what the input/output 
behavior of the Montgomery ladder is more clearly. {Does this work for 
all Montgomery curves, e.g., also when the curve y^2 = x^3 + A x^2 + x 
for which A^2 <>4?, etc.}
d) Section 9.1, p. 11:
With the draft, the output of the Diffie-Hellman protocol, as presented, 
succumbs to the small subgroup attack (e.g., DH(f,0)=0), no matter the 
value of f contributed by A).
e) Section 9.1, p. 11:
With the draft one has some annoying editorial glitches, including
-- "Alice then transmits K_A=DH(f,9) to Bob, where 9 is the number 9" 
should most likely read "Alice then transmits K_A=DH(f,g) to Bob, where 
g is the number 9".
-- "Alice computes DH(f,DH(g,9))" should read "Alice computes 
DH(f,K_B)"; etc., and vice-versa for Bob.
f) Section 9, pp. 9-11:
-- With the draft, the first part of Section 9 (till Section 9.1) is 
about scalar multiplication and probably deserves a separate subsection 
to that effect.
-- With the draft, not sure why scalar multiplication ineptly uses the 
acronym "DH" (as in DH(s,u). I would strongly suggest avoiding any 
language that could put people on the wrong footing, due to connotations 
ubiquitous in the crypto literature.
-- With the draft, one seems to introduce lots of new variables to 
denote objects (e.g., why not use scalar k, point G, Q, DH key K= a Qb, 
co-factor h, etc., if one wants to cross a message most effectively)?
-- With the draft, outsiders who are not necessarily be versed in 
cryptography would have a hard time following/verifying esoteric 
language and certainly would not be familiar with "quadratic 
extensions", "projection maps ... extended, so". I would suggest that 
clarity of language is key here.

Notes: Andrey Jivsov noted error #b above. I tried to retrace other 
errors to cut-and-paste errors from 
draft-turner-thecurve25519function-01, but that original draft also 
contains these errors (despite mentioned review by Tanja Lange, 
according to acknowledgements). The turner draft does contain an 
implicit reference to flaw #d above, although in nebulous terms 
("contributory behavior").

For now, I refrain from other comments, but hope that we at least get 
the technical details right. (I was hoping that the adoption call would 
end with someone else noticing the errors above, but did not see this 
(except for #b above), so reluctantly go to the CFRG list to mention 
some of this here. [I have my private thoughts about how many people 
actually read the entire draft...].)

Best regards, Rene

-------- Forwarded Message --------
Subject: 	Re: [Cfrg] Adoption of draft-agl-cfrgcurve-00 as a RG document
Date: 	Sat, 24 Jan 2015 17:57:25 +0000
From: 	Alexey Melnikov <[email-masked]>
To: 	[email-masked] <[email-masked]>

Dear CFRG participants,

Best Regards,
Alexey,

---

From: Adam Langley <[email-masked]>
Date: Tue, 27 Jan 2015 16:16:16 -0800

> It seems that draft-agl-cfrgcurve-00 contains a few technical flaws,

Thank you very much for this. It prompted me to make some changes that I've
been planning.

a) Section 9, p. 10:
> (X::Z) {if the Y-coordinate is deleted}, where x=X/Z, y=Y/Z, and where the
> point at infinity is (1::0).
> Montgomery Adds results in (u::1) + (0::1) = (4::4u^3)~ (1:: u^3). So, the
> procedure outputs on input Q:=(u::1) and scalar k=1, the incorrect output
> R:=(1::u^3) (with x-coordinate u^{-3}), rather than simply u.
>

You are quite correct. I've fixed this.

> With the draft, one mistakenly takes 1/z2 = z2^{p-1}, whereas this should
> obviously be z2^{p-2} (if z2 is nonzero).
>

I had fixed this on GitHub after Andrey's note and it'll be in
draft-irtf-cfrg-curves-00.

> above), one can end up with the unidentified string projective point (0::0)
> in some cases. So, one should clarify what the input/output behavior of the
> Montgomery ladder is more clearly. {Does this work for all Montgomery
> curves, e.g., also when the curve y^2 = x^3 + A x^2 + x for which A^2 <>4?,
> etc.}
>

The curve25519 function is defined as a function from ([32]byte, [32]byte)
-> [32]byte. As such, it does have a defined behaviour when the resulting
point is (0::0) as it'll output all zero bytes. Although the draft was
written with the possibility in mind that we might define several curves,
my estimation at the moment if that the CFRG won't actually do that. Things
might turn out differently but, for the moment, I'm changing the document
to be more curve25519 specific rather than specifying the Montgomery ladder
more generally.

> value of f contributed by A).

It's certainly possible to extract the value of the scalar mod the cofactor
from curve25519, but the scalar construction ensures that value is zero.
I've made a note about the "non-contributory" behaviour of curve25519 in
the draft.

> should most likely read "Alice then transmits K_A=DH(f,g) to Bob, where g
> is the number 9".
> -- "Alice computes DH(f,DH(g,9))" should read "Alice computes DH(f,K_B)";
> etc., and vice-versa for Bob.
>

Both fixed, thanks.

> f) Section 9, pp. 9-11:
> -- With the draft, the first part of Section 9 (till Section 9.1) is about
> scalar multiplication and probably deserves a separate subsection to that
> effect.
>

I've split the scalar-mult function into its own section and moved the DH
bits into a separate one.

> acronym "DH" (as in DH(s,u). I would strongly suggest avoiding any language
> that could put people on the wrong footing, due to connotations ubiquitous
> in the crypto literature.
>

That's my screwup. The scalar-mult function was called "curve25519" and I
changed it to DH in anticipation that more curves might be defined. Since I
get the feeling that won't happen now, I've switched back to calling it
"curve25519".

> -- With the draft, one seems to introduce lots of new variables to denote
> objects (e.g., why not use scalar k, point G, Q, DH key K= a Qb, co-factor
> h, etc., if one wants to cross a message most effectively)?
>

This is still an open issue as I have it now. In order to be consistent,
I've called the coordinates on the Montgomery curve (u, v) and those on the
(twisted) Edwards (x, y). We need to figure out whether the existing
specification for generating curves is called for if we're not going to
have any others. If not, then we could have (x,y)  for the Montgomery curve
and at least be a little more consistent. I have, at least, make the scalar
be 'k'.

> cryptography would have a hard time following/verifying esoteric language
> and certainly would not be familiar with "quadratic extensions",
> "projection maps ... extended, so". I would suggest that clarity of
> language is key here.
>

I agree and have removed that language.

> Notes: Andrey Jivsov noted error #b above. I tried to retrace other errors
> to cut-and-paste errors from draft-turner-thecurve25519function-01, but
> that original draft also contains these errors (despite mentioned review by
> Tanja Lange, according to acknowledgements). The turner draft does contain
> an implicit reference to flaw #d above, although in nebulous terms
> For now, I refrain from other comments, but hope that we at least get the
> technical details right. (I was hoping that the adoption call would end
> with someone else noticing the errors above, but did not see this (except
> for #b above), so reluctantly go to the CFRG list to mention some of this
> here. [I have my private thoughts about how many people actually read the
> entire draft...].)
>
> Best regards, Rene
>
> -------- Forwarded Message --------  Subject: Re: [Cfrg] Adoption of
> draft-agl-cfrgcurve-00 as a RG document  Date: Sat, 24 Jan 2015 17:57:25
> +0000  From: Alexey Melnikov <[email-masked]>
> <[email-masked]>  To: [email-masked] <[email-masked]>
> <[email-masked]>
>
> Dear CFRG participants,
>
> Cfrg mailing [email-masked]://www.irtf.org/mailman/listinfo/cfrg
>
>
>
>

---

From: Rene Struik <[email-masked]>
Date: Tue, 27 Jan 2015 21:25:07 -0500

Hi Adam:

Thanks for the quick feedback and willingness to accommodate my 
suggestions to improve the draft.

I will revisit your email later. However, just another brief process note:
I would like to strongly suggest first re-publishing your individual 
internet draft draft-agl-cfrgcurve-00, but now as 
draft-irtf-cfrg-curve-00 (i.e., verbatim copy, except change of title 
and submission date) and only then make changes to the resulting 
document. As I said in my previous process note (Jan 5, 2015, 4.42pm 
EST), this allows easy to keep track of evolution over time.

Please forgive me my "rigid" approach here, but the "rigid curve 
selection criteria" we started out with seem to have to apply to the 
processes of this (somewhat dysfunctional) IRTF group as well. I hope 
you appreciate this; this is not a personal criticism. BTW - this 
republication suggestion is precisely what Alexey Melnikov suggested in 
his Sat Jan 24, 2015 adoption email.

Best regards, Rene

On 1/27/2015 7:16 PM, Adam Langley wrote:
> On Tue, Jan 27, 2015 at 10:15 AM, Rene Struik <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     It seems that draft-agl-cfrgcurve-00 contains a few technical
>     flaws, including:
>
>
> Thank you very much for this. It prompted me to make some changes that 
> I've been planning.
>
>     a) Section 9, p. 10:
>     The Montgomery ladder works on projective points of the form
>     (X:Y:Z), or (X::Z) {if the Y-coordinate is deleted}, where x=X/Z,
>     y=Y/Z, and where the point at infinity is (1::0).
>     If so, one has Q-Q'=(x1::z1)=(u::1), Q'=(x2::z2)=(1::0) {the point
>     at infinity}, and Q=(x3::z3)=(u::1).
>     representation of the affine point (0,0) of order two. In that
>     case Montgomery Adds results in (u::1) + (0::1) = (4::4u^3)~ (1::
>     u^3). So, the procedure outputs on input Q:=(u::1) and scalar k=1,
>     the incorrect output R:=(1::u^3) (with x-coordinate u^{-3}),
>     rather than simply u.
>
>
>     The Montgomery ladder should produce, on input Q=(x1::z1) and
>     scalar k, the output R:=kQ=(x2::z2), which can be mapped to an
>     affine point with x-coordinate x2/z2.
>     The Montgomery ladder does not produce the output R=kQ for each
>     input Q and scalar k, since, e.g., (after correcting the flaw
>     identified in #a above), one can end up with the unidentified
>     string projective point (0::0) in some cases. So, one should
>     clarify what the input/output behavior of the Montgomery ladder is
>     more clearly. {Does this work for all Montgomery curves, e.g.,
>     also when the curve y^2 = x^3 + A x^2 + x for which A^2 <>4?, etc.}
>
>
> The curve25519 function is defined as a function from ([32]byte, 
> [32]byte) -> [32]byte. As such, it does have a defined behaviour when 
> the resulting point is (0::0) as it'll output all zero bytes. Although 
> the draft was written with the possibility in mind that we might 
> define several curves, my estimation at the moment if that the CFRG 
> won't actually do that. Things might turn out differently but, for the 
> moment, I'm changing the document to be more curve25519 specific 
> rather than specifying the Montgomery ladder more generally.
>
>     d) Section 9.1, p. 11:
>     With the draft, the output of the Diffie-Hellman protocol, as
>     presented, succumbs to the small subgroup attack (e.g.,
>     DH(f,0)=0), no matter the value of f contributed by A).
>
>
> It's certainly possible to extract the value of the scalar mod the 
> cofactor from curve25519, but the scalar construction ensures that 
> value is zero. I've made a note about the "non-contributory" behaviour 
> of curve25519 in the draft.
>
>     e) Section 9.1, p. 11:
>     -- "Alice then transmits K_A=DH(f,9) to Bob, where 9 is the number
>     9" should most likely read "Alice then transmits K_A=DH(f,g) to
>     Bob, where g is the number 9".
>     -- With the draft, the first part of Section 9 (till Section 9.1)
>     is about scalar multiplication and probably deserves a separate
>     subsection to that effect.
>
>
> I've split the scalar-mult function into its own section and moved the 
> DH bits into a separate one.
>
>     -- With the draft, not sure why scalar multiplication ineptly uses
>     the acronym "DH" (as in DH(s,u). I would strongly suggest avoiding
>     any language that could put people on the wrong footing, due to
>     connotations ubiquitous in the crypto literature.
>
>
> That's my screwup. The scalar-mult function was called "curve25519" 
> and I changed it to DH in anticipation that more curves might be 
> defined. Since I get the feeling that won't happen now, I've switched 
> back to calling it "curve25519".
>
>     denote objects (e.g., why not use scalar k, point G, Q, DH key K=
>     a Qb, co-factor h, etc., if one wants to cross a message most
>     effectively)?
>
>
> This is still an open issue as I have it now. In order to be 
> consistent, I've called the coordinates on the Montgomery curve (u, v) 
> and those on the (twisted) Edwards (x, y). We need to figure out 
> whether the existing specification for generating curves is called for 
> if we're not going to have any others. If not, then we could have 
> (x,y)  for the Montgomery curve and at least be a little more 
> consistent. I have, at least, make the scalar be 'k'.
>
>     extensions", "projection maps ... extended, so". I would suggest
>     that clarity of language is key here.
>
>
>     Notes: Andrey Jivsov noted error #b above. I tried to retrace
>     other errors to cut-and-paste errors from
>     draft-turner-thecurve25519function-01, but that original draft
>     also contains these errors (despite mentioned review by Tanja
>     Lange, according to acknowledgements). The turner draft does
>     contain an implicit reference to flaw #d above, although in
>     nebulous terms ("contributory behavior").
>
>     For now, I refrain from other comments, but hope that we at least
>     get the technical details right. (I was hoping that the adoption
>     call would end with someone else noticing the errors above, but
>     did not see this (except for #b above), so reluctantly go to the
>     CFRG list to mention some of this here. [I have my private
>     thoughts about how many people actually read the entire draft...].)
>
>     Best regards, Rene
>
>     <mailto:[email-masked]>
>     To: 	[email-masked] <mailto:[email-masked]> <[email-masked]>
>     <mailto:[email-masked]>
>
>
>
>     Dear CFRG participants,
>
> Adam Langley [email-masked] <mailto:[email-masked]> 
> https://www.imperialviolet.org

---

From: Adam Langley <[email-masked]>
Date: Wed, 28 Jan 2015 09:10:02 -0800

On Tue, Jan 27, 2015 at 6:25 PM, Rene Struik <[email-masked]> wrote:
> I would like to strongly suggest first re-publishing your individual internet draft draft-agl-cfrgcurve-00, but now as draft-irtf-cfrg-curve-00 (i.e., verbatim copy, except change of title and submission date) and only then make changes to the resulting document. As I said in my previous process note (Jan 5, 2015, 4.42pm EST), this allows easy to keep track of evolution over time.

I've submitted draft-agl-cfrgcurve-00 as draft-irtf-cfrg-curve-00
(it's pending chair approval) with no changes other than the name.
Once that's published, I'll quickly follow up with -01 which will be
similar to what's currently in git: https://github.com/agl/cfrgcurve

Cheers

AGL