[curves] EdDSA specification

[Trevor Perrin]

On Fri, Oct 21, 2016 at 7:55 AM, Tim Ruffing
<tim.ruffing at 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