[curves] EdDSA specification

[Tim Ruffing]

Great to see a specification!

Some comments:

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

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

(Please double-check the code, and there may be a better way to do
it...)

I'm not sure 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.

Public domain:
I would use CC0 instead, that's exactly what it's made for:
"Dedicating works to the public domain is difficult if not impossible
for those wanting to contribute their works for public use before
applicable copyright or database protection terms expire. Few if any
jurisdictions have a process for doing so easily and reliably. Laws
vary from jurisdiction to jurisdiction as to what rights are
automatically granted and how and when they expire or may be
voluntarily relinquished. More challenging yet, many legal systems
effectively prohibit any attempt by these owners to surrender rights
automatically conferred by law, particularly moral rights, even when
the author wishing to do so is well informed and resolute about doing
so and contributing their work to the public domain."
(from https://creativecommons.org/share-your-work/public-domain/cc0/ )

Best,
Tim

On Thu, 2016-10-20 at 19:41 -0400, Trevor Perrin wrote:
> Hi curves,
> 
> I'm happy to announce that a spec for the "XEd25519" signature
> algorithm used in Signal is available at [1].
> 
> Based on ideas this list has discussed a few times, this allows
> signing and verifying Ed25519 signatures with X25519 key pairs, which
> gives a single format for key pairs, and may even allow a single key
> pair for DH and signatures in some cases.
> 
> The document also generalizes this signature algorithm to the 448
> curve, and extends it to include VRF functionality, which Signal
> might
> use in the future.  These extensions are somewhat new, and should
> probably get more public review before people rush to implement.
> 
> Feedback is welcome!
> 
> If we get editorial or design feedback that is too detailed for this
> list, we may create a more specific list for feedback.
> 
> Code implementing XEd25519 and VXEd25519 (the VRF extension) can be
> found in [1].
> 
> Trevor
> 
> [1]
> https://whispersystems.org/docs/
> https://whispersystems.org/docs/specifications/xeddsa/
> 
> [2]
> https://github.com/WhisperSystems/curve25519-java/
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves