[tor-dev] Action items wrt ed25519 onion address verification in prop224 (was Re: Proposition: Applying an AONT to Prop224 addresses?)

[Ian Goldberg]

On Thu, Apr 06, 2017 at 03:37:35PM +0300, George Kadianakis wrote:
> Hello again,
> 
> this is the second subthread of the AONT thread that grew too big for
> its own good, and it's about ed25519.
> 
> The topic of this subthread is the above ed25519 verification of onion
> addresses that Ian suggested a few times already.
> 
> So the idea is that before you use an onionaddress (as a client or
> whatever), you should extract its ed25519 pubkey and multiply it by the
> group order and make sure you get back the identity element to ensure
> that there are no torsion components to the key.

And also check that the key is not itself the identity element.

> I'm pretty weak on crypto so I have some questions about this defence:
> 
> - Why are we doing this? Are we doing this because if we allow torsion
>   components in the keys, someone could basically create multiple
>   equivalent keys for each legit ed25519 key, using the Z/8Z torsion
>   scalar as the tweak?

Yes, this one.  Also it would be good to be alerted if someone's
publishing malformed onion addresses for some reason.

>   Or is the reason to defend against small subgroup attacks? I think
>   not, because from my understanding these attacks mainly apply to DH
>   protocols which is not what we are doing with onion addresses.

Correct.

> - Is this something that we should be doing for _any_ received ed25519
>   ever, even in other parts of the protocol?

Whenever you receive a value that is supposed to be in the EC group,
it's safest to either (a) check that it is, and fail if not, or (b)
perform the operation in a way that will behave well in either case.  If
you really have received an arbitrary 256-bit value from the Internet,
and you want it to be in the ed25519 group, you really should do the
"multiply by l" check, since not only might it have a torsion component
(addressable by other means such as TSR in the other thread), but it may
not be in the group at all, but rather in the "twist" group.
Multiplying by l will simultaneously check both issues.  But sometimes
being in the wrong group isn't terrible; see the next paragraph.

> - Should we do this verification also for received x25519 (DH) keys? It
>   seems like RFC7748 is instead suggesting we ensure that the DH output
>   is not all-zeroes. Are these two defences equivalent for our purposes?

The x25519 DH operation automatically clears the torsion component,
since it insists your private key be a multiple of 8.  If someone
sends you a point on the twist instead of in the expected group, the DH
will fail (you won't end up with the same shared key as the other
party), but you will be saved from the small subgroup attack because of
that "8".  (That invariant of being a multiple of 8 is what you lose
during multiplicative blinding, and what TSR restores.)

   - Ian