[curves] curve25519 public keys with high bit set

[Robert Ransom]

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
(<http://www.ietf.org/mail-archive/web/tls/current/msg11957.html>)
that he had decided to forbid public keys with the high bit set
instead.


> 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.
<https://moderncrypto.org/mail-archive/curves/2014/000007.html>).


Robert Ransom