On Mon, Apr 24, 2017 at 04:47:44PM +0300, George Kadianakis wrote: > Ian Goldberg <t...@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 _______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
