Well I think there are two issues:
1. if the public key is derived from a password (like a bitcoin
brainwallet), or as in EC based PAKE systems) then if the point derived from
your password isnt on the curve, then you know that is not a candidate
password, hence you can for free narrow the password search. (Which
particularly for PAKE systems weakens their security).
2. if the software doesnt properly validate that the point is on the curve,
and tries to do an operation involving a private key or secret, anyway, it
may leak some of the secret. DJB has some slides saying he found some
software does not check.
This is what elligator is about, a more deterministic way to hash keys to
curves. Which is an improvement with a more friendly curve to the approach
used by eg http://tools.ietf.org/html/draft-harkins-tls-pwd-03 where the way
you do it is x = hash2curve( password, counter ), test (x,y) on curve, start
counter at 0, and repeat until the point is on the curve. Thats bad because
you have to do it lots of times, to be fairly sure it'll work its timing
dependent so that leaks password entropy etc. Its much easier to aim for
constant time with elligator technique and curves.
Adam
On Thu, Oct 03, 2013 at 02:41:30PM +0100, Michael Rogers 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.
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. Does it just mean that the function has a defined output for that
input, even though that output isn't cryptographically useful?
Silently accepting invalid input and producing useless output seems
like a bug rather than a feature, so I feel like I must still be
misunderstanding the real meaning of "accepts".
Cheers,
Michael
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
iQEcBAEBAgAGBQJSTXQKAAoJEBEET9GfxSfMIJkH/jmClrIJ6kD3D/h5MMf7cvIp
BVLMmGROGwIFhIrfFZwfqEFGQzBZNpMP06BYJsyPbMRf1uLxFixIYHhSYXCcA+IJ
ZvcLMkMptNVb2xPr9jkdC3tXd47udo23Pxo8pP3uo0i265TMkdNOyY4WwJlrnCGQ
B7FDXeNXRAtNxdbfrFR2hpCd6yyVk+rqDl3AxNCQ01Slf8HmfOKtcZu7WHHwxQFZ
4ECVtlQmdcAaO8JiNdhWzyzbFW7GEEzvCdzYl3hZTqyXfXM+asGFw90K4qXKAoZS
l3S7Q5Pl7tg0KxDL6iHz0XVUMpxH31Mac09DM+dZWT9hp7PEFWiF79XzD0AGi+4=
=qqWu
-----END PGP SIGNATURE-----
_______________________________________________
cryptography mailing list
[email protected]
http://lists.randombit.net/mailman/listinfo/cryptography
_______________________________________________
cryptography mailing list
[email protected]
http://lists.randombit.net/mailman/listinfo/cryptography
