On 6/3/14, Trevor Perrin <[email protected]> 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 _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
