[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 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:
>          https://gitweb.torproject.org/user/asn/tor.git/log/?h=bug22006_v2

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:

300ef2e64e588e1df55b48e4da0416ffb64cc85d5b00af6463d5cc6c2b1c185e
f43e3a046db8749164c6e69b193f1e942c7452e7d888736f40b98093d814d5e7
c9fff3af0471c28e33e98c2043e44f779d0427b1e37c521a6bddc011ed1869af

would be good additional tests (all should fail; they have order 8l, 4l,
2l respectively).

This one should pass:

4ba2e44760dff4c559ef3c38768c1c14a8a54740c782c8d70803e9d6e3ad8794

> Another thing:
> 
> My understanding is that this is a special-case validation and it's
> expensive,

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

> 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

Attached.

   - Ian
-------------- next part --------------
A non-text attachment was scrubbed...
Name: curvestruct.c
Type: text/x-csrc
Size: 1476 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20170425/58bbfac6/attachment.c>