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

[George Kadianakis]

isis agora lovecruft <isis at torproject.org> writes:

> 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.
>
> <snip>
>
>> Perhaps use the *output* of the hash H(R,A,M)?  Or the pair
>> (R, S mod l)?
>
> H(R || A || M) might be okay… but it's still a little icky given that it's
> still not strictly tied to the secret key that produces the eventual
> signature (cf. the calculation of `V` below).
>
> I would highly advise reusing Trevor Perrin's work on building a VRF into
> Generalised EdDSA, [0] which solves precisely this problem (i.e. "how do I get
> verifiable randomness, given an ed25519 signature?") in the following way:
>  |
>  | The VXEdDSA signing algorithm takes the same inputs as XEdDSA. The output
>  | is a pair of values. First, a signature (V || h || s), which is a byte
>  | sequence of length 3b bits, where V encodes a point and h and s encode
>  | integers modulo q. Second, a VRF output byte sequence v of length equal to
>  | b bits, formed by multiplying the V output by the cofactor c.
>  |
>  | The VXEdDSA verification algorithm takes the same inputs as XEdDSA, except
>  | with a VXEdDSA signature instead of an XEdDSA signature. If VXEdDSA
>  | verification is successful, it returns a VRF output byte sequence v of
>  | length equal to b bits; otherwise it returns false.)
>  |
>  |    vxeddsa_sign(k, M, Z):
>  |        A, a = calculate_key_pair(k)
>  |        B_{v} = hash_to_point(A || M)
>  |        V = a B_{v}
>  |        r = hash3(a || V || Z)     (mod q)
>  |        R = r B
>  |        R_{v} = r B_{v}
>  |        h = hash4(A || V || R || Rv || M) (mod q)
>  |        s = r + ha (mod q)
>  |        v = hash5(c V) (mod 2^{b})
>  |        return (V || h || s), v
>
> (Trevor is using q, where you, Ian, and I are using \ell, and floodyberry
> uses n.  Also ignore the `calculate_key_pair` function, that's just because
> Signal stores keys in Montgomery form.  Also ignore the numbers after the
> hashes, that's just denoting the labelset system for domain separation.)
>
> Personally, I'd redefine `hash_to_point` such that it does two elligator2
> encodings from a 512-bit hash, and then adds the points together, before
> multiplying by the cofactor, to ensure it produces all (instead of roughly
> half of all) possible points.
>
> Also, (shameless plug) you get all of this basically for free if you just do
> generalised EdDSA with Ristretto, [1] since the cofactor is elliminated.
> I've been working with Trevor on this, it's called D.A.V.R.O.S. and it'll
> be done… (as) soon (as I have more free time to finish it).
>

Hello Isis and thanks for the help!

I found some time to read about XEdDSA and VXEdDSA: they seem like very
interesting constructions and indeed the latter seems like the thing we
should be using here!

That said, my impression is that swapping ed25519 for VXEdDSA in the HS
protoocl is not gonna be easy (especially since we are hoping to fit
this in 034), because then HSDirs will need to be able to verify both
ed25519 and VXEdDSA signatures, which IIUC are different constructions
(that is, an HSDir node can't produce a VRF output with an ed25519 sig).

IMO, a reasonable plan for now is to use either (R, S mod l) or H(R,A,M)
in the replay cache and only *after* the desc signature has been
verified.  Then perhaps in the future we should consider whether we can
eventually swap out ed25519 for VXEdDSA so that we can use its VRF
output directly.

I hope this makes sense. I'm gonna start implementing this concept this
week, in hopes that we can fit it in the 034 schedule, because otherwise
revision counters are gonna linger around for longer!

Thanks! :)