[cryptography] A question about public keys

Trevor Perrin trevp at trevp.net
Thu Oct 3 11:45:31 EDT 2013


On Thu, Oct 3, 2013 at 6:41 AM, Michael Rogers <michael at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20131003/4310ce6d/attachment.html>


More information about the cryptography mailing list