On Thu, Oct 3, 2013 at 6:41 AM, Michael Rogers <mich...@briarproject.org>wrote:
> -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 > > On 29/09/13 20:24, Nico Williams wrote: > Just because curve25519 > accepts every 32-byte value as a public key > > doesn't mean that every 32-byte value is a valid public key (one > > resulting from applying the curve25519 operation). The Elligator > > paper discusses several methods for distinguishing valid public > > keys from random. > > On 30/09/13 05:55, Trevor Perrin wrote: > > Phrasing this better: check that x^3 + 486662x^2 + x is a square > > modulo 2^255-19 > > Thanks Nico and Trevor for your replies. If I understand right, you're > both pointing to the "most severe" distinguisher in section 1.1 of the > Elligator 2 paper. > Yes. I'm afraid I still don't understand what it means for curve25519 to > "accept" a string as a public key if that string isn't a valid public > key. Suppose you are a good guy with a static curve25519 key, and a bad guy is sending you 32-byte strings, claiming them to be ephemeral curve25519 public keys for use in an ephemeral-static Diffie-Hellman. You repeatedly perform your side of the ephemeral-static DH. I.e., you perform a curve25519 operation betweeen the bad guy's alleged ephemeral public key and your private key. After each DH, you give the bad guy, say, some MAC based on the Diffie-Hellman result. At issue is whether this is safe without checking that the bad guy's strings correspond to possible public keys. And it is, with curve25519! But with some other curves, it isn't. In particular, if the bad guy's "public key" can have small order (eg generates a group with, say, 7 elements), then the resulting DH shared-secret will be confined to 7 values. The bad guy can easily test all 7 values for the MAC key, thus learning the value of your private key modulo 7. By repeating this with other public keys of small order, and using the Chinese Remainder Theorem, the bad guy could solve for your private key. Curve25519 prevents this without requiring an explicit check. See discussion of "twist" and "small-subgroup attacks" in the Curve25519 paper for more: http://cr.yp.to/ecdh/curve25519-20060209.pdf Trevor
_______________________________________________ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
