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

[isis agora lovecruft]

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

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

Yes, replay is also possible, and both the small torsion attack and the
wonkiness above is possible by any party with access to the HS descriptor,
and an unreduced scalar with some multiple(s) of R = 2^260 (mod 2^252 +
27742317777372353535851937790883648493) should also be possible by the HS
itself, depending on which curve library you're using.

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

[0]: https://signal.org/docs/specifications/xeddsa/#vxeddsa
[1]: https://doc-internal.dalek.rs/curve25519_dalek/ristretto/index.html

Best regards,
-- 
 ♥Ⓐ isis agora lovecruft
_________________________________________________________
OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35
Current Keys: https://fyb.patternsinthevoid.net/isis.txt
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 1240 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20180419/ec253ef4/attachment.sig>