[tor-dev] HS desc replay protection and ed25519 malleability

[George Kadianakis]

Hello Ian, isis, and other crypto people around here!

Here is an intro: In HSv3 we've been using revision counters
(integers++) to do HS desc replay protection, so that bad HSDirs cannot
replay old descs to other HSDirs. We recently learned that this is a bad
idea from a scalability prespective (multiple sites need to track rev
counter...), and also it's needless complexity in the code (tor needs to
cache the counters etc.). See ticket #25552 for more details:
      https://trac.torproject.org/projects/tor/ticket/25552
      https://gitweb.torproject.org/torspec.git/tree/rend-spec-v3.txt#n1078

In #25552 we've been making plans to ditch the rev counters and replace
them with a casual replay cache. (These replay caches also don't need to
be big, since descriptors are only replayable for a day before the
ephemeral blinded key changes, and the cache can be reset).

Anyhow, now we've been playing the game of "which part of the desc
should we use in the replay cache"? The latest plan here has been to use
the ed25519 descriptor signature since it's something small, simple and
necessarily changes with every fresh descriptor. And this is how we
entered the ed25519 malleability scene.

The basic question here is, can we use the ed25519 signature in our
replay cache and consider it immutable by attackers without the private
key? And should we use R, or S, or both?

According to RFC8032:

             Ed25519 and Ed448 signatures are not malleable due to the
             check that decoded S is smaller than l.  Without this
             check, one can add a multiple of l into a scalar part and
             still pass signature verification, resulting in malleable
             signatures.

However, neither donna or ref10 include such a check explicitly
IIUC. Instead they check whether (RS[63] & 224), which basically ensures
that the high 3 bits of S are zeroed, which ensures S < 2^253. Is that
equivalent to the RFC check? Because if I'm counting right, for most
legit S values you can still add a single l as the attacker and get an
S' = S + l < 2^253 equivalent signature (you can't add 2*l tho).

So what's the state of ed25519 malleability? I know that after the
Bitcoin incident, people have thought about this a lot, so I doubt we
are in a broken state, but I just wanted to make sure that we will not
mess something up. :)

Thanks for the help! :)