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! :)