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

[Ian Goldberg]

On Thu, Apr 19, 2018 at 06:19:29PM +0000, isis agora lovecruft wrote:
> Ian Goldberg transcribed 2.5K bytes:
> > On Wed, Apr 18, 2018 at 04:53:59PM +0300, George Kadianakis wrote:
> > > 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.
> > 
> > You could still use (S mod l) as the cache index, though, right?
> 
> Yes, although with the caveat that this is somewhat expensive.
> 
> > > 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?
> > 
> > Using R itself should, AFAICT, be safe against malleability.  More
> > concretely, whatever representation of R is used in the hash H(R,A,M)
> > used to compute S (and to verify the signature).  But is malleability
> > the only attack you should be worried about?
> 
> R is malleable as well, because it's not guaranteed to not have a small
> torsion component.

But given (R,S), mutating R to R+kT will cause H(R,A,M) to change, and
so S will change unpredictably (to someone who doesn't know the private
key).

> Also, I think it's also not exactly strictly guaranteed
> to be both random and tied to the domain of the secret key which produced
> the signature, i.e. if normally R is produced as:
> 
>     r = H(H(a)[32:] || M)   mod l
>     R = rB
> 
> but one could also do:
> 
>     r = H(H("yog-shoggoth")[32:] || M)   mod l
>     R = rB
> 
> which is still a random thing, albeit not tied to the context of the creator
> of the signature.  That signature obviously wouldn't verify, but again,
> you'd have to do the fairly expensive thing of double-checking that the
> signature is valid before using the R as a source of randomness provided by
> the actually legit and well-behaved onion service.

I think *anything* you do with the cache label can only be done *after*
you verify the signature.  Otherwise, there are way too many avenues for
attack on the cache that come from crafting arbitrary bitstrings that
don't even make sense.

Your point about everything being better if signatures are unique is
definitely a good one (and it obviously makes any WUF system
automatically SUF.)