[tor-dev] Action items wrt ed25519 onion address verification in prop224 (was Re: [tor-project] Network team meetings notes from 17 April 2017)
iang at cs.uwaterloo.ca
Tue Apr 25 13:26:47 UTC 2017
On Tue, Apr 25, 2017 at 03:38:37PM +0300, George Kadianakis wrote:
> > 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).
> Good stuff Ian.
> I pushed a new branch `bug22006` that:
> - Checks that the pubkey is not the identity element itself.
> - Adds tests based on the points you listed above.
> Check it out here:
It looks to me as though you're only checking the pure torsion points
above. You should *add* one of those points to a valid pubkey in order
to get a point to check. For example, the points:
would be good additional tests (all should fail; they have order 8l, 4l,
This one should pass:
> Another thing:
> My understanding is that this is a special-case validation and it's
It's a single scalar multiplication (and packing, I suppose). I guess
"expensive" is relative; you might time it to see if the cost matters to
> so I opted to not perform it everytime we generate a new
> ed25519 keypair or when we receive one from the internet. So for
> example, I'm not doing it when we extract the ed25519 signing pubkey
> that signs the HS descriptor, since we don't care if there are
> equivalent forms of that key.
You indeed don't need to do it when you generate a key yourself in a
known-good way (unless you're paranoid about fault attacks, which I
don't think you are). I'm a little wary about ever not doing it on a
pubkey you receive from the Internet, though. I would want to know if
someone were sending me a malformed crypto-relevant value.
> So this validation function is currently unused, and I plan to only use it
> on the prop224 client-side when a client handles received onion addresses.
> Finally, how did you derive the list of points above? o.o
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 1476 bytes
Desc: not available
More information about the tor-dev