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,