[curves] curve25519 public keys with high bit set

Robert Ransom rransom.8774 at gmail.com
Wed Jun 4 12:41:27 PDT 2014

On 6/4/14, CodesInChaos <codesinchaos at gmail.com> wrote:
> On Wed, Jun 4, 2014 at 4:36 PM, Watson Ladd <watsonbladd at gmail.com> wrote:
>> On Wed, Jun 4, 2014 at 7:06 AM, CodesInChaos <codesinchaos at gmail.com>
>> wrote:
>>> No matter which way is chosen, it's important to get the IETF TLS
>>> specification for Curve25519 to match what's chosen and to include
>>> test-vectors for it.
>> Please, please try to follow the CFRG: that's where this specifying is
>> going on. If they get it right we are happy.
>> If not, we aren't. Anyone can contribute: it really does matter.
> I mentioned this issue on the CFRG list on March 3rd in the email
> Trevor linked in the OP.
> In April the draft was updated to say that any public key with the
> with the last bit set SHOULD be rejected to avoid different
> interpretations in different implementations.

That's disappointing.  I had argued that implementations should
discard that bit (i.e. set it to zero) in January (starting in
<http://www.ietf.org/mail-archive/web/tls/current/msg11163.html> and
<http://www.ietf.org/mail-archive/web/tls/current/msg11167.html>), and
I thought that the author was agreeing to my suggested change.

There was no mention in the author's announcement of the revised draft
that he had decided to forbid public keys with the high bit set

> In the context of ephemeral TLS keys that's a reasonable restriction,
> but in many other contexts it's better to accept all 32 byte values
> and interpret them consistently.

It doesn't seem like a reasonable restriction to me.

>>  This complicates exposing a simple scalarmult operation.
> I think we need separate scalarmult and scalarmult-x operations
> anyways in order to take advantage of x-only montgomery ladders.
> I know no constant time, variable base scalar multiplication
> implementations that include the sign bit, even in Edwards form.

I implemented one (which outputs a Montgomery-form x coordinate and
the sign bit of an Edwards-form x coordinate), partly in order to
cross-validate my Edwards routines against the Montgomery ladder, and
partly to investigate its performance.  (Unfortunately, I still don't
have a place to publish that library.)  I wouldn't recommend using it
for DH -- the Montgomery ladder turned out to be faster.

>> I'm hard pressed to think of a situation where you don't know if you
>> are doing ECDH or signatures.
> There are a bunch of protocols which would like to use the same long
> term key for both DH based authentication (in a protocol like CurveCP,
> Noise or the OTR variant TextSecure uses) and signatures.

That's one of the major reasons I gave for ignoring the high bit of a
Curve25519 DH public key in TLS, as well as one of the major reasons
that I've been fighting for point formats based on the Montgomery-form
x coordinate (rather than an Edwards-form y coordinate) in general
(see that thread on the TLS list, and e.g.

Robert Ransom

More information about the Curves mailing list