[cryptography] A question about public keys

Adam Back adam at cypherspace.org
Thu Oct 3 13:45:32 EDT 2013

On Thu, Oct 03, 2013 at 04:53:09PM +0100, Michael Rogers wrote:
>Presumably if you ensure that the private key is valid, the public key
>derived from it must be a point on the curve.  So it's a matter of
>validating private rather than public keys.
>I understand what you're saying about a timing side-channel in the
>draft-harkins-tls-pwd approach, but here I'm not concerned with validating
>a public key after generating it, but rather with the puzzling statement
>that there's no need to validate a public key after receiving it:
>"How do I validate Curve25519 public keys?
>Don't. The Curve25519 function was carefully designed to allow all
>32-byte strings as Diffie-Hellman public keys."

Well consider an EC point is an x,y coordinate both coordinates modulo p,
some 256-bit prime.  There are a number of points on the curve l and for a
given base point a number of points generated by that point n.  For prime
order curves typically the co-factor h = 1 so l=n.  (This is analogous to
the difference between p = 2q+1 in normal diffie hellman over prime fields. 
Ther are p values but the group generated by g will hold q possible values
before wrapping around where q divides p-1.)

So now back to EC to note that n and p are almost the same size (both
256-bit but n<p, however clearly the number of potential points is in fact
2p (because X=(x,y) and -X=(x,-y) are both points on the curve).  But 2p>n
nearly 2p is nearly 2x n (n the number of points on the curve).  So
therefore around half of the points you could start from are not on the
curve, there is no solution when you try to solve for y from the curve
equation.  As you see in the harkin draft in that type of curve it is
because x^3+ax+b has no square root.

So you know about point compression?  Basically you can almost recover a
point from the x-coord only because each point is (x,f(x)) but with one
caveat that because its a symmetric curve about the x-axis you also need to
say whether thats f(x) or -f(x).  So people would send the x-coord and one
bit for the sign.

Its getting kind of complicated but it seems to me DJB ensures all 32 byte
encoded points are points by a kind of definitional trick that a point is
not the x-coord and sign bit, but the number x multiplied by a base point
(9,f(9)) which of course is a valid point because (9,f(9)) is a generator.

Its an equally valid encoding method and is probably faster.

However if you call (9,f(9))=G, you cant use DJB point encoding when you're
doing PAKE because well if password attempt pwd1 you get pwd1.G and then you
do some DH thing with it, send to the otherside they do Y=x.pwd1.G and send
back, thats bad because you can revise pwd1 to pwd2 by division:
pwd2.pwd1^-1.Y = pwd2.pwd1^-1.x.G=x.pwd2.G and then you can offline grind
the PAKE key exchange which is bad.

So for that you really need to start from x = H(password) and point
G=(x,f(x)) and that was what the hunt and peck algorithm in Harkins is
about.  DJB has a solution for that too in his Elligator paper which is
constant time (as I recall worst case two tries) because he can use a
different method relating to the more flexible and and more efficient curves
he chose.

Is it just me or could we better replace NIST by DJB ? ;)  He can do that EC
crypto, and do constant time coding (nacl), and non-hackable mail servers
(qmail), and worst-time databases (cdb).  Most people in the world look like
rank amateurs or no-real-programming understanding niche-bound math geeks
compared to DJB!


>Hash: SHA1
>On 03/10/13 15:14, Adam Back wrote:
>> 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.
>Hmm, so perhaps the statement quoted above simply means "Curve25519
>contains its own key validation code, and will complain if the string
>you give it isn't a valid public key?"
>Version: GnuPG v1.4.10 (GNU/Linux)

More information about the cryptography mailing list