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

[George Kadianakis]

Watson Ladd <watsonbladd at gmail.com> writes:

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

Thanks for the help!

Hmm, so everyone gets a shot at a single malleability "attack" with
everye d25519 sig? What's the point of the (RS[63] & 224) check then?

In this case, we can't use S as the replay cache index since the
attacker can mutate it and still get the sig to verify. Can we use R as
the replay cache index then? Can an attacker given (R,S) find (R',S')
such that the sig still verifies?