[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 <iang at cs.uwaterloo.ca> writes:

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

Oops yes, I was actually testing the pure torsion points, instead of
generating fresh points P = b*B + t*T as I think you are suggesting.

Doing ed25519 addition in the tor unittests is kind of a PITA, so I'll
just borrow the points you are suggesting above and test those directly.

Pushed a fixup commit here:
https://gitweb.torproject.org/user/asn/tor.git/commit/?h=bug22006_v2&id=eb3530fc8999b3a3028d60f86bd04445273f247f

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

Hmm, and that's just to ensure that there are no equivalent forms of
those pubkeys, right? And also to ensure that no one is sending random
garbage to us. Because IIUC using an ed25519 pubkey with a torsion
component does not really affect the security of signature verification
in other ways.

Anyhow, these two commits do the validation in a bunch of places we
receive ed25519 pubkeys from the net:
        https://gitweb.torproject.org/user/asn/tor.git/commit/?h=bug22006_v2&id=e37c0c3fa5d572421e52d4cd144f0617ad4d10e0
        https://gitweb.torproject.org/user/asn/tor.git/commit/?h=bug22006_v2&id=8965bf278e5efe3f17e6d99123659a26da02c589

Thanks for the script as well! :)