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

[George Kadianakis]

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

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...

Cheers!