[curves] curve25519 public keys with high bit set

[Robert Ransom]

On 6/3/14, Trevor Perrin <trevp at trevp.net> wrote:
> Hi,
>
> I'd like to argue that the high bit of encoded curve25519 public keys
> should be masked to zero.
>
> The paper specifies "liberal in what you accept, conservative in what
> you send" behavior:
>
> http://cr.yp.to/ecdh/curve25519-20060209.pdf
> "The set of Curve25519 public keys is, by definition, {0, 1, ..., 255}^32"
> ...
> "Note that Curve25519 is not surjective: in particular, its final
> output bit is always 0 and need not be transmitted."
>
>
> Some curve25519 implementations masked off the high bit of received
> public keys, since it should never be set.  But it was pointed out
> that DJB's reference implementation treats the input public key as a
> full 256-bit value to be reduced mod 2^255-19.

That wasn't DJB's reference implementation, that was the ‘ref’
implementation (horribly slow with 8-bit limbs, written by someone
other than DJB, and considerably later than the implementation which
accompanied the Curve25519 paper) in NaCl and SUPERCOP.

I agree that Dr. Bernstein labeled it in a manner that implies that it
is a reference implementation, but it didn't match the de-facto
standard that had already been set by Dr. Bernstein's original
implementation and curve25519-donna/-donna-c64.

(For what it's worth, I do think that masking off the high bit was
originally a bug -- it didn't match the behaviour specified in the
paper, or on Dr. Bernstein's Curve25519 web page -- but it's not only
the de-facto standard now, it's also a good idea.)


> So libsodium and curve25519-donna changed to match:
>
> http://www.ietf.org/mail-archive/web/cfrg/current/msg04333.html
> https://github.com/jedisct1/libsodium/issues/78
> https://github.com/agl/curve25519-donna/commit/81b6dcb6cf5b983ec6391f36aa061caef07c58ad
>
>
> I think this is bad, we should mask the bit:
>
> If some implementations accept full 256-bit keys, then eventually some
> implementations will start *producing* full 256-bit keys, which will
> break older libsodium / donna, and require everyone to support full
> 256-bit values.  (Hopefully no-one's producing such awful /
> noncompliant pubkeys yet, so it's not too late!)

It's not quite that bad:

* scalarmult implementations which encode points in a non-‘standard’
way will fail to interoperate with the existing implementations which
do not.

* scalarmult/dh_keypair implementations which do not reduce their
outputs modulo 2^255-19 might (and should be presumed to) leak
information about the secret key.

So I don't expect anyone to use the high bit as anything other than a
sign bit for use in non-DH applications.


> Also: reserving the 256th-bit allows the curve25519 encoding to be
> easily augmented to a "unified encoding" that can encode both
> curve25519 and ed25519 public keys, using the (montgomery_x,
> edwards_x_sign_bit) idea that Robert and Watson discussed earlier:
>
> https://moderncrypto.org/mail-archive/curves/2014/000002.html
>
> Do people agree that masking is the best practice?

I still believe that using the high bit to transmit a sign bit (and
thus masking off the high bit in scalarmult implementations) is the
best practice.


Robert Ransom