On Fri, Oct 21, 2016 at 7:55 AM, Tim Ruffing <tim.ruff...@mmci.uni-saarland.de> wrote: > > I've actually never seen this in practice, but I think a real > specification should at least state what the expected security > guarantee is for each scheme is. In this case, what kind of > unforgeability can I expect, strong or weak? > (Section 5 suggests that you went for strong unforgeability?)
Sure, it would be good to have more security analysis, maybe in a separate paper or appendix. Existential unforgeability under chosen message attack (EUF-CMA) is the usual security goal for signatures. VXEdDSA adds the VRF requirements from the referenced Dodis or Micali papers (VRF output = provably unique, and pseudorandom). "Strong" unforgeability / non-malleability [1] isn't usually that important. See the discussions of malleability in the Ed25519 and EdDSA papers [2,3]. That's a non-goal here too - for example, if (R,s) is a valid signature the verifier would accept (R,s+q) as well, if s+q satisfies the check s < 2^|q|. Precisely defining this behavior is a security goal, so that implementations can't be distinguished in anonymity use cases. But this check (for s) was chosen for simplicity and to match existing implementations, rather than maximum strictness (which would check s < q). If you want a provably nonmalleable ( / deterministic / unique) output from the signature scheme, then you want a VRF (or a VUF, maybe, to split hairs, but VRFs are the stronger notion). > Section 8: > "The hash_to_point function also uses conditional branching (within > elligator2) and should be made constant time, even though it only > handles the message, not secret keys." > > If this is a concern, then I think it's better to provide non-branching > pseudocode, maybe like that: > elligator2(r): > u1 = -A * inv(1 + nr^2) (mod p) > w1 = u1(u1^2 + Au1 + 1) (mod p) > leg = w1^((p-1)/2 (mod p) > u12 = ((leg - 1)/2)*A + leg*w1 (mod p) > return u12 Some presentations of Elligator 2 do that [4,5], but I think that obscures the underlying logic (set up a nonsquare ratio so that numerator or denominator is square, and choose the square). Mike Hamburg's explanations in [6,7] are much more intuitive, so I wanted to focus on that. We could add more discussion about const-time implementation though, e.g. discuss how to do a const-time "conditional move" of byte sequences, and how that could be used here. > - If a constant-time implementation is not important, then the > idea "if H(m) is a valid x-coordinate, use that point, otherwise try > H(m+1), ..." is much simpler and fine (as far as I know). > - If a constant-time implementation is important, then Elligator 2 is > the way to do it but then you should say "must" instead of "should" in > the spec. > - If your paradigm is that constant-time implementations are the > "right way" in general, even if it's unclear if secrets are involved, > then you should still make it a hard requirement. Once we move away from secret keys and start considering sidechannel leakage of message contents or public keys, the value of const-time code becomes debateable. For example: message contents might be secret, justifying a const-time Elligator, but what's the likelihood the rest of the code that parses and operates on the message is constant-time, or that there will be sidechannel attacks as damaging as crypto key recovery? Often low, on both counts. I suspect implementations of Elligator2 and hash-to-point functions will get re-used in other contexts like PAKE, where the input is a secret password, so that's a good reason to encourage const-time implementation. But for many uses of signatures, it won't matter. So I feel like the best we can do is just discuss the issue and encourage const-time code as safer in general. Trevor [1] http://crypto.stanford.edu/~dabo/papers/strongsigs.pdf [2] https://ed25519.cr.yp.to/ed25519-20110926.pdf [3] https://ed25519.cr.yp.to/eddsa-20150704.pdf [4] https://elligator.cr.yp.to/elligator-20130828.pdf [5] https://www.imperialviolet.org/2013/12/25/elligator.html [6] http://ecc2015.math.u-bordeaux1.fr/documents/hamburg.pdf [7] https://moderncrypto.org/mail-archive/curves/2015/000424.html _______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves