[curves] curve25519 public keys with high bit set

Trevor Perrin trevp at trevp.net
Tue Jun 3 16:57:18 PDT 2014


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.

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

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?


Trevor


More information about the Curves mailing list