[cryptography] A question about public keys

Adam Back adam at cypherspace.org
Thu Oct 3 10:14:06 EDT 2013

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.


On Thu, Oct 03, 2013 at 02:41:30PM +0100, Michael Rogers wrote:
>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".
>Version: GnuPG v1.4.10 (GNU/Linux)
>cryptography mailing list
>cryptography at randombit.net

More information about the cryptography mailing list