Subject: [Cfrg] Consensus and a way forward

From: Benjamin Black <[email-masked]>
Date: Wed, 26 Nov 2014 20:25:29 -0800

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

---

From: Watson Ladd <[email-masked]>
Date: Wed, 26 Nov 2014 21:26:10 -0800

> http://www.ietf.org/id/draft-black-rpgecc-00.txt .

This document doesn't address the most important questions:

1: What goes on the wire for ECDH? Montgomery points, points native to
each curve formula, or Weierstrass points?
2: How are signatures computed?
3: Clear bits, multiply by cofactors, or check group membership?
4: Point compression or no point compression?

Given that generators are recorded for a prime order subgroup, it
would seem that we are checking group membership, which will lead to
the check being omitted and resultant, albeit minor, security issues.

> 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.

Why 2^384-317 and not 2^383-31 or 2^389-21? This choice of prime
really pinches the allowable radixes for carry-free multiplication
reduction, and thus hurts efficiency, more than the 2^255-19 vs
2^256-189 decision at the lower security level. Far from being a
simultaneous accommodation of the performance concerns and the
generation concerns, this is clearly horse trading, with performance
being given the choice of the 255 bit prime, and a similar improvement
not happening at the 384 bit prime.

> generation procedure gives the same curve with p =2^521 - 1 as several teams
> produced.

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

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

---

From: Joppe Bos <[email-masked]>
Date: Thu, 27 Nov 2014 06:17:32 +0000

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

         FFFFFFFFFFED

   d = 0x15E93

         8FD8849FAF35

         C0F582AA22E2

         1DA9A3E5A819

   h = 0x4

2^384 - 317

     h = 0x4

---

From: Hannes Tschofenig <[email-masked]>
Date: Thu, 27 Nov 2014 07:51:11 +0100

Hi Benjamin,

while I applaud that you are trying to find a way forward your mail
almost sounds like you are acting is one of the chairs of the group.

From a process point of view only the chairs can call for consensus; I
am sure it is just unfortunate wording and you are providing another
proposal for the group to consider.

Ciao
Hannes

On 11/27/2014 05:25 AM, Benjamin Black wrote:
> 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
> 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
>

---

From: Alyssa Rowan <[email-masked]>
Date: Thu, 27 Nov 2014 06:57:55 +0000

On 27/11/2014 04:25, Benjamin Black wrote:

> 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 

An interesting proposal (of course, not a consensus as Hannes has
pointed out, only a proposal representing a compromise between the
authors).

The IPR section in that draft is remarkably short: of course you
cannot patent numbers. (That's copyright's job. <g>) In order to
satisfy IP1 and IP2 requirements we're going to need more information
about the status of specific algorithms on those curves which people
will actually use. As Dan Brown's recent message should highlight, we
should evaluate the patent status and can't ignore it (unless we plan
on ignoring them for long enough that they go away, and in that case,
we need to know when!).

In order to evaluate the performance of simple and secure
implementations of algorithms over these curves, of course we are also
going to need safe, efficient implementations for those algorithms,
ideally available under a liberal licence so stakeholders can actually
use it (specifically I'm afraid Apache 2.0 won't do due to its licence
incompatibilities), which also satisfy our patent concerns. Do you
have such an implementation ready to publish that we can plug into
SUPERCOP?

As this is an exercise in transparency, which is the most important
thing that we hope to differentiate anything we produce from, say, the
NIST curves, kindly disclose onto this list all of the technical
discussions which have produced these compromise in criteria between
the authors (or, in the alternative, hold them here afresh and let's
see if they produce the same consensus). That is a discussion that I
feel should be properly held publicly here, and at the very least,
absolutely requires public documentation for posterity.

I note that if you run your algorithm on 2^521-1 you get E-521. If you
ran it on 2^255-19, why didn't you get the twisted Edwards form of
Curve25519? Kindly elucidate your objections to the same.

- -- 
/akr

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 27 Nov 2014 09:07:49 +0200

> > http://www.ietf.org/id/draft-black-rpgecc-00.txt .

Theoretically, the following Safecurves criteria could fail, even with p
at 205 bits or above (which guarantees Rho passes):
- Multiplicative transfer
- CM Discriminant
- Twist Multiplicative transfer

But any failure here would be VERY unlikely. I think there actually might
be values of p, which cause the algorithm presented to generate a known-
weak curve (but finding such p would be too hard to do currently).

> the check being omitted and resultant, albeit minor, security issues.

Well, many ECC algos assume prime order subgroup.

Complete Edwards curves with h=4 and h=8 have quick check for low-order
points.

Also, I would like to see:

- The inverse Montgomery parameter (1/a24). This can be arranged to be
  small using suitable isomorphism and possibly quadratic twist.
- Conversion from Edwards form to Montgomery form.
- The Montgomery u corresponding to the base point.

For the first curve, those look to be:

1/a24 = -89748
u = (1+y)/(1-y)
u(P) = 11437681968289677273267944528525036915198860913446821942098597381479763892770

The transform has extra cost of 1 addition and 1 substraction (the division
is free, because it would be needed anyway).

> not happening at the 384 bit prime.

Well, at least 2^383-31 is 1 mod 8, which makes difficult to compute square
roots.

Looks like 2^389-21 saves a word on both 32 and 64 bit compared to
2^384-317 when using minimal-carry rational-base implementation.

-Ilari

---

From: Adam Langley <[email-masked]>
Date: Wed, 26 Nov 2014 23:22:34 -0800

> have such an implementation ready to publish that we can plug into

For the curve over GF(2^255-19), I certainly agree that
implementations are needed but I believe that there's strong evidence
that the performance would be equal to curve25519.

The Edwards curve in question is isogenous to Curve25519 with A=358990
and, while some uses may want to drop the new curves into existing
code, I hope that this RG can recommend that ECDH operations for the
most part transmit the Montgomery X value. Thus curve25519
implementations should just need to change the (A-2)/4 value.

For implementations of the Edwards curve, the smaller d value, if
anything, might allow a slight speedup over Edwards curve25519.
(Although those implementations would need changes to the scalar
reduction function and any precomputed tables.)

> Curve25519? Kindly elucidate your objections to the same.

As djb noted in the curve25519 paper[1], the A value for curve25519 is
not minimal. draft-black-rpgecc-00 finds a curve isogenous to the
minimal A. The minimal (and second minimal) value was originally
rejected because, when generating private keys, there's a possibility
of generating a multiple of the order. This can be taken care of with
(I think) a single memcmp, although I need to confirm that just one is
sufficient when I'm back home.

[1] http://cr.yp.to/ecdh/curve25519-20060209.pdf, section "Why this curve?".

Cheers

AGL

---

From: Alyssa Rowan <[email-masked]>
Date: Thu, 27 Nov 2014 07:54:45 +0000

On 27 November 2014 07:22:34 GMT+00:00, Adam Langley <[email-masked]> wrote:

>> I note that if you run your algorithm on 2^521-1 you get E-521. If you ran it on 2^255-19, why didn't you get the twisted Edwards form of Curve25519? Kindly elucidate your objections to the same.

Yes,  that's just what I thought.

As the greater value of A used in Curve25519 produces a simpler secure implementation with no weak private keys to check for, and that is the only big difference between Curve25519 and this proposal, I should prefer Curve25519 according to our selection criteria. Why *not* that, then?

- --
/akr

---

From: Mike Hamburg <[email-masked]>
Date: Thu, 27 Nov 2014 00:14:49 -0800

> As the greater value of A used in Curve25519 produces a simpler secure implementation with no weak private keys to check for, and that is the only big difference between Curve25519 and this proposa…
Ask anyone who's implemented ECDSA on NIST-P160 :-)

Curve25519 has no weak keys because its order is 2^252+O(2^126), i.e. 
slightly over a power of 2.  Many curve generation procedures specify 
that the order must be slightly under a power of 2 rather than slightly 
over, because that also has advantages.  It permits slightly easier 
Barrett reduction mod the order, avoids special cases involving an extra 
bit, and for a few cases (MQV, I think) avoids having to do an extra 
point op in constant time algorithms just in case that bit might be set.

-- Mike

---

From: Alyssa Rowan <[email-masked]>
Date: Thu, 27 Nov 2014 09:19:10 +0000

On 27 November 2014 08:14:49 GMT+00:00, Mike Hamburg <[email-masked]> wrote:
>> Why *not* [Curve25519], then?

Yes, I think the first question I'd ask anyone who did that would also be: "why?" :)

>Curve25519 has no weak keys because its order is 2^252+O(2^126), i.e. slightly over a power of 2.  Many curve generation procedures specify that the order must be slightly under a power of 2 rather than slightly over, because that also has advantages.

...this curve generation procedure doesn't, so that's a bit of a stretch.

We'll need to weigh advantages (MQV? Not exactly a key-exchange frontrunner anymore... When does the FHMQV patent expire again? I prefer Axolotl's approach) against disadvantages (such as the https://xkcd.com/927/ point, given Curve25519 already achieved pretty wide adoption while we dithered).

It almost matches Curve25519, and the reasoning for it not matching is weak: the value of convergence for consensus and rigidity is far greater than the value of differing for just this reason, in my mind.

It does seem like a sensible way of generating the ultra-strong security curve, certainly, to me. What happens if we constrain 2^x-n to n<32 for efficiency reasons, x=384 and step x upwards until this criteria is met? How similar is that to djb's Curve41417? Is Curve41417 faster than this... I suppose it'd be rpg384r1 curve?

- --
/akr

---

From: "Paterson, Kenny" <[email-masked]>
Date: Thu, 27 Nov 2014 10:01:22 +0000

Dear Joppe,

Your point is well-noted.

Recently, I closely read all the messages on the list about random primes
versus special primes. It's clear that we did not reach a consensus on
this issue (and indeed there was no prospect of reaching one).

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

I would be delighted if, after that process is complete, we would return
to the question of coming up with a set of curves for random primes. I
think CFRG should sponsor such an effort in due course. Naturally, whereas
there is a limited set of sensible choices for special primes, this is not
the case for random primes. So we would also need to agree on a procedure
or ceremony for generating the primes themselves. I would like to defer
further discussion of that until the current workflow for special primes
and curves is completed. Of course, you and others can be thinking about
how to do it in the background.

I realise that there is a big decision implied by my e-mail: special
primes rather than random primes.

Given this, let me also state I do not want to re-open the debate about
the pros and cons of this choice now, as I believe they were already
well-ventilated on the list over the last few months.

Of course, I cannot stop anyone posting on this topic! However, I'd remind
everyone who thinks about doing so that we already had a lot of discussion
about it, that we did not reach consensus, and that in such a situation it
becomes necessary for (and indeed the responsibility of) the chairs to
make a decision to enable things to move forward.

Regards,

Kenny 

On 27/11/2014 06:17, "Joppe Bos" <[email-masked]> wrote:

>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
> 
>performance and trustworthy
> generation concerns, and I hope the resulting proposal will be
>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.
>
> 
>

---

From: "Paterson, Kenny" <[email-masked]>
Date: Thu, 27 Nov 2014 10:05:43 +0000

Hannes,

To be fair to Ben, the chairs have been dragging their heels here, so it's
not surprising that other people have stepped in to fill the apparent
vacuum. 

You are technically correct that only chairs should call for consensus. I
think Ben's use of the word referred to a different kind of consensus: one
between Google and Microsoft.

Like you, I think it's helpful that Google and Microsoft have combined to
make this proposal in an effort to move things forward. I hope we can
discuss it dispassionately.

Regards,

Kenny

---

From: "Paterson, Kenny" <[email-masked]>
Date: Thu, 27 Nov 2014 10:20:17 +0000

Hi Watson,

On 27/11/2014 05:26, "Watson Ladd" <[email-masked]> wrote:

>>see

These things would all follow in due course, if the proposal were
acceptable to CFRG.

Anyway, as far as I can see, none of these is very hard, given the many
discussion we've had on the list and the education I've thereby received.
Here's some suggestions that we can come back to later (once we've agreed
whether we want to go down this route or not):

1. Points in Montgomery form for ECDH (remember, we are at liberty to
specify new point formats on the wire for these curves for TLS).
2. Using EC-DSA (oh yes!).
3. Multiply by co-factors, as per the EC-DSA standards, IIRC; plus
whatever Montgomery form needs (please feel free to re-inform me).
4. Not relevant for EC-DSA signatures; for Montgomery form, x-coordindate
only would be best, right?

Cheers

Kenny

>>Adam
>>generation

---

From: Benjamin Black <[email-masked]>
Date: Thu, 27 Nov 2014 12:36:06 -0800

> on ignoring them for long enough that they go away, and in that case,

We are aware of no IP whatsoever covering the contents of the draft. I will
update the IPR statement to be more clear.

b

---

From: Alexey Melnikov <[email-masked]>
Date: Thu, 27 Nov 2014 20:45:01 +0000

Hi Alyssa,

> On 27/11/2014 06:57, Alyssa Rowan wrote:
> authors
Of course. CFRG consensus would be determined by the chairs, after discussion of the proposal.
> ).
While it would be nice to have an open source implementation with a liberal license, there is no requirement to have an open source implementation to consider this proposal. And IRTF process doesn't require that either.
> absolutely requires public documentation for posterity.
I don't think asking for a transcript of all such discussions is reasonable. Repeating some of the discussion, in particular in response to clarifying questions might be. People should treat the draft as any other contribution to the ECC discussion in the RG.

Best Regards,
Alexey, as co-chair

---

From: Michael Hamburg <[email-masked]>
Date: Thu, 27 Nov 2014 13:47:25 -0800

Hi Benjamin,

That reminds me — not that this has much bearing on the latest draft — but did that Microsoft investigation into the ‘907 patent ever conclude one way or the other?

Thanks,
— Mike

> On Nov 27, 2014, at 12:36 PM, Benjamin Black <[email-masked]> wrote:
> 
> On Wed, Nov 26, 2014 at 10:57 PM, Alyssa Rowan <[email-masked] <mailto:[email-masked]>> wrote:
> 
> We are aware of no IP whatsoever covering the contents of the draft. I will update the IPR statement to be more clear.
>  
> 
> b

---

From: Benjamin Black <[email-masked]>
Date: Thu, 27 Nov 2014 13:49:11 -0800

I will follow up with folks after the holiday to see where we are.

b

On Thursday, November 27, 2014, Michael Hamburg <[email-masked]> wrote:

> Hi Benjamin,
>
> That reminds me — not that this has much bearing on the latest draft — but
> did that Microsoft investigation into the ‘907 patent ever conclude one way
> or the other?
>
> Thanks,
> — Mike
>
> On Nov 27, 2014, at 12:36 PM, Benjamin Black <[email-masked]
> <javascript:_e(%7B%7D,'cvml',[email-masked]');>> wrote:
>
> On Wed, Nov 26, 2014 at 10:57 PM, Alyssa Rowan <[email-masked]
> <javascript:_e(%7B%7D,'cvml',[email-masked]');>> wrote:
>>
>>
> We are aware of no IP whatsoever covering the contents of the draft. I
> will update the IPR statement to be more clear.
>
>
> b
> [email-masked] <javascript:_e(%7B%7D,'cvml',[email-masked]');>

---

From: Alyssa Rowan <[email-masked]>
Date: Thu, 27 Nov 2014 22:13:28 +0000

On 27/11/2014 20:45, Alexey Melnikov wrote:

> While it would be nice to have an open source implementation with
> a liberal license, there is no requirement to have an open source 
> implementation to consider this proposal. And IRTF process doesn't 
> require that either.

Indeed. But given the previous comments about benchmarking, how would
we fairly evaluate it otherwise - and moreover, how attractive would the
resulting proposal actually be to others?

As Adam's pointed out, this proposal has generated something extremely
close to an existing curve that's already on the table. I am not sure
that there is a good clear justification for the only thing
differentiating this proposal from that proposal; I don't currently
think it's an improvement there.

If we added - on the basis of wanting to ensure secure implementations
of many possible things we might use it for (such as ECDH) are as simple
as possible - the pretty reasonable criteria that there should be no
weak keys, it would generate Curve25519, I understand. I would accept
that outcome: and it has been very warmly received by the RG before, I
recall. And then we'd have an equally clear process for a larger curve.
(I bear Mike's comments in mind, of course; it needs discussion.)

If we didn't want to do that, I'd want to be crystal-clear about the
value of why not, and hence why anyone outside would ever want to
choose this proposal above Curve25519. (Because right now, I wouldn't.)

> I don't think asking for a transcript of all such discussions is 
> reasonable. Repeating some of the discussion, in particular in 
> response to clarifying questions might be.

Having reconsidered: perhaps you're right! I simply wish the process to
be as transparently and openly argued as possible, that's all: that is,
after all, the primary value of IRTF making such recommendations, rather
than major players such as Google and Microsoft making them by fiat.

> People should treat the draft as any other contribution to the ECC 
> discussion in the RG.

Indeed; I think it is a very encouraging sign overall, and provides a
very good base narrowing the points (if you'll forgive the pun!) of
technical contention. Hopefully we can converge on curves which are
widely acceptable.

- -- 
/akr

---

From: Robert Ransom <[email-masked]>
Date: Sun, 30 Nov 2014 19:33:06 -0800

> implementations should just need to change the (A-2)/4 value.

First, what you are referring to as “Curve25519 with A=358990” is a
curve different from Curve25519; it can more correctly be referred to
as “the Montgomery curve with A=358990 over the same coordinate field
as Curve25519”.  Since you have not proposed a concise name for this
Montgomery curve, I will use the name that Dr. Bernstein has just
suggested for it, i.e. “PinkBikeShed”.

Second, as you have stated, existing Curve25519 implementations would
need to be changed in order to operate on PinkBikeShed (or any curve
isogenous to it).  That is a major technical disadvantage compared
with using Curve25519 itself, even if the only change required is to
replace the curve-parameter constant.

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.

> reduction function and any precomputed tables.)

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?

> [1] http://cr.yp.to/ecdh/curve25519-20060209.pdf, section "Why this

As Dr. Bernstein noted in the Curve25519 paper, the value of (A - 2)/4
for Curve25519 is indeed minimal subject to an additional security
criterion.  (I do not know or care whether A is minimal subject to any
set of constraints for either Curve25519 or PinkBikeShed.)  By
discarding that additional security criterion, you have knowingly and
intentionally introduced a very small security vulnerability in your
proposal (another technical disadvantage of PinkBikeShed compared to
Curve25519): the simplest implementation strategy for ECDH
(Montgomery-ladder scalar multiplication on PinkBikeShed) produces
zero as an output for one (non-zero) secret key when computing a
shared secret with any input public key (point) on the twist.

(I note that you did not disclose this security vulnerability in your
draft's ‘Security Considerations’ section.)

In order to mitigate that vulnerability, you recommend that ECDH
implementations call the standard C library function ‘memcmp’ on every
secret key to check for that one (slightly) weak key.  This adds
complexity to every ECDH implementation, and requires that
applications or protocols which derive secret keys deterministically
(e.g. by hashing some other secret) devise a backup plan in case that
one secret key is ever generated.  Worse, your proposed mitigation
introduces a further security vulnerability (much worse than the one
it is intended to protect against): a typical implementation of memcmp
will leak information about *every* secret key to a timing
side-channel attack.

(And as Dr. Bernstein has pointed out, further, more severe, security
vulnerabilities are possible in implementations of some protocols
based on PinkBikeShed, but not in implementations of the same
protocols based on Curve25519.)

You have stated two technical disadvantages that you knew of at the
time that you submitted your proposal: the deliberate incompatibility
with existing Curve25519 software, and the deliberate introduction of
a security vulnerability that is not present in Curve25519.  You have
stated only one possible technical benefit of your proposal over
Curve25519: a small performance improvement in some (not all)
implementations due to a slightly smaller curve-parameter constant.

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?  If not, did you have in mind any other
technical benefit of your proposal over the use of unmodified
Curve25519 that you consider to outweigh your proposal's technical
disadvantages?

Robert Ransom