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

[Robert Ransom <[e-mail]>]

On 11/26/14, Adam Langley <[e-mail]> wrote:
> On Wed, Nov 26, 2014 at 10:57 PM, Alyssa Rowan <[e-mail]> wrote:
>> 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?
>
> 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.

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.


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

Interesting suggestion.

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


>> I 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.
>
> 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?".

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