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

[Watson Ladd]

On Wed, Apr 18, 2018 at 6:15 AM, George Kadianakis <desnacked at riseup.net> wrote:
> 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).

This seems right. Malleability is not part of the standard security
definition for signatures.
>
> 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! :)
> _______________________________________________
> tor-dev mailing list
> tor-dev at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev



-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.