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

[Ian Goldberg]

[Warning: recovering from illness.  Brain may not be operating at
nominal capacity.  :-p ]

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?

> 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?  What if one party produces
two descriptors for two different services, but reuses R to cause a
cache collision?  Presumably some untoward badness would result.
Perhaps use the *output* of the hash H(R,A,M)?  Or the pair
(R, S mod l)?

It's also not true that malleability is not part of the standard
security definition for signatures.  That's exactly the difference
between the WUF and SUF (weakly / strongly unforgeable) security
properties.  In a WUF system, the attacker, given a signing oracle,
cannot produce a valid signature on a message she does not present to
the signing orable.  In a SUF system, the attacker cannot produce a
valid (message,signature) _pair_ she does not send to / receive from the
signing oracle.  A system with malleable signatures can be WUF, but
cannot be SUF.

   - Ian