[tor-dev] Action items wrt ed25519 onion address verification in prop224 (was Re: [tor-project] Network team meetings notes from 17 April 2017)

[Ian Goldberg]

On Mon, Apr 24, 2017 at 04:47:44PM +0300, George Kadianakis wrote:
> Ian Goldberg <tor at cypherpunks.ca> writes:
> 
> > On Thu, Apr 20, 2017 at 03:40:58PM +0300, George Kadianakis wrote:
> >> Hey Ian,
> >> 
> >> so the current problem with ed25519-donna is that when I'm doing the
> >> above, I'm getting the following 32-byte key after ge25519_pack(). Here
> >> it is hexed up:
> >> 
> >>        0x0100000000000000000000000000000000000000000000000000000000000000
> >> 
> >> I don't see any methods in ed25519-donna for checking a point or a
> >> packed point to see if it's the point at infinity (identity element).
> >
> > There actually is such a function, but it's buried in a weird place.
> > ge25519_is_neutral_vartime in ed25519-donna-batchverify.h does what you
> > want, but it's static, so you would need to copy it (and remove the line
> > involving batch_point_buffer).  Probably not worthwhile.
> >
> > I can easily believe the representation of the identity (neutral)
> > element in ed25519 is the hex value above.  (And it is; see below.)
> >
> >> I've been assuming that the point at infinity would be an all-zeroes
> >> 32-byte array, because that's what we are doing in curve25519, but I
> >> actually have no idea how the array representation of ge25519_pack()
> >> works. Here is our process for curve25519:
> >>        https://gitweb.torproject.org/tor.git/tree/src/common/crypto_curve25519.c#n123
> >
> > Curve25519 only outputs the x coordinate, which is indeed 0, so you get
> > the all-zero value.  ed25519 outputs the y coordinate (which is the
> > 255-bit value 0x000...0001 in little-endian format) and the single-bit
> > parity of the x coordinate (which is 0), so you do get the hex you give
> > above.  (The identity element is the point (0,1) in Edwards curves, not
> > actually the point at infinity.)
> >
> >> The above packed point is an all zeroes 32-byte string, apart from the
> >> very first bit which is set. Could it be that the first bit is the
> >> compressed sign of the 'x' coordinate or something, and that's actually
> >> the point at infinity?
> >> 
> >> But then what's the right way to check for the point at infinity? Check
> >> that everything is 0 apart from the first sign bit?
> >
> > Yes, pack the point, and compare it to the above 32-byte value.
> >
> >> And after I figure this out, I need to do the same for the reference
> >> implementation of ed25519, because as it seems Tor uses two simultaneous
> >> implementations of ed25519:
> >>         https://gitweb.torproject.org/tor.git/tree/src/ext/ed25519
> >
> > Yes, hopefully that implementation packs points in the same way!
> >
> >> Thanks for the help Ian :) Very much appreciated!
> >
> > No worries.
> >
> 
> [CCing tor-dev since people might find it interesting]
> 
> Thanks for the advice Ian :)
> 
> With your help, I have now implemented the validation check. Check out
> the ticket #22006 and the branch `bug22006` here:
>     https://gitweb.torproject.org/user/asn/tor.git/commit/?h=bug22006&id=628dd1adfdc4cbde449d6ec6808a9f6aa6f6f6c4

You should also check that the point it not *itself* the identity
element.

> One last thing I'd like to do here is test our validation function
> against a pubkey with torsion component to make sure that it gets
> rejected. How would you go about generating such a pubkey?
> 
> I was thinking of using the CRT to find an integer a \in Z, s.t
>    a == 0 (mod l) && a == 1 (mod 8)
> but then I didn't know how to go from that scalar with a torsion
> component to an ed25519 point...

It turns out the point whose packed representation is 32 bytes of 0x00
is a torsion point; it is the point (-1,0).

Indeed, these are the 7 pure torsion points in ed25519:

26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc05
0000000000000000000000000000000000000000000000000000000000000000 =(-1,0)
c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac037a
ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f =(0,-1)
c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac03fa
0000000000000000000000000000000000000000000000000000000000000080 =(1,0)
26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc85

So just take any of the above points, and add it to a valid pubkey to
get an invalid pubkey.

You should probably also check points not on the curve at all, such as:

e19c65de75c68cf3b7643ea732ba9eb1a3d20d6d57ba223c2ece1df66feb5af0

If you generate a 32-byte string at random, about 1/2 the time it won't
be on the curve at all (that is, if P is the unpack of those 32 bytes,
8*l*P is *not* the identity), about 7/16 of the time it is on the curve,
but has a torsion component (8*l*P is the identity, but l*P is not), and
1/16 of the time it's a valid pubkey (l*P is the identity, but P is
not).

   - Ian