[curves] EdDSA specification

[Trevor Perrin]

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/

[Ron Garret]

You derive DSA keys from DH keys using the bilateral equivalence relation and setting the sign bit to zero. Why not instead go the other way and derive DH keys from DSA keys? That way you get to keep the sign bit. One bit is not a big deal, but was there a reason for going DH->DSA instead of the other way?

Post by Trevor Perrin
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
https://moderncrypto.org/mailman/listinfo/curves

[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

Post by Trevor Perrin
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
https://moderncrypto.org/mailman/listinfo/curves

[Trevor Perrin]

On Fri, Oct 21, 2016 at 7:55 AM, Tim Ruffing

Post by Tim Ruffing
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).

Post by Tim Ruffing
"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
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.

Post by Tim Ruffing
- 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

[Gregory Maxwell]

Post by Trevor Perrin
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|.

Failing to specify a non-malleable form has resulted in
vulnerabilities in multiple protocols and systems.

For example, some users of openssl will blacklist certificates by
their hash. But you can take a valid ecdsa signature, change it to
another valid one under the same key, thus change the certificate
hash-- and bypass the blacklist. OpenSSL CVEed their fix for
DER-parser originated signature malleability related to blacklisting,
but still has the ecdsa algebraic one (adding half the order to s to
flip the sign of R).

All things equal it's preferable for cryptographic constructs to not
have surprising features which less cryptographically experienced
system integrators would not expect.

In libsecp256k1's implementation of ECDSA we accept signatures only in
a malleability prohibited form-- and require users to explicitly
normalize the signature themselves via an additional function call if
they wish to be more permissive. This is explained at
https://github.com/bitcoin-core/secp256k1/blob/master/include/secp256k1.h#L399

[Tim Ruffing]

Post by Gregory Maxwell
All things equal it's preferable for cryptographic constructs to not
have surprising features which less cryptographically experienced
system integrators would not expect.

Indeed. There are a lot of ways to shoot yourself in the foot if you
use crypto -- but we should at least try to avoid them when possible.

Sure, the malleable variant is a little simpler to implement, but only
a little. The checks really don't add much complexity.

Actually, omitting the checks may be more complex depending on the
application. If the developer wants to compute a hash of some data
structure containing the signature for example (Greg gave two specific
cases), then he can take extra care to handle malleability, e.g., by
first removing the signature from the data structure or by normalizing
the signature. However that adds a lot of complexity and is easy to
miss.

(I didn't read it carefully enough, so I assumed you went for non-
malleability.)


---

Post by Gregory Maxwell
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.

I think discussing this case would be a good idea, because it's
required here. You could also refer to
https://cryptocoding.net/index.php/Coding_rules#Avoid_branchings_contro
lled_by_secret_data


Tim

[Brian Smith]

Post by Trevor Perrin
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.

In the motivation for the randomized scheme, the document says "However, if
the same message is signed repeatedly, a glitch that affects the
calculation of h could cause this to happen (an observation due to Benedikt
Schmidt)." Could you provide a reference to a paper/message that explains
what is being referred to here, and/or add a description of the issue to
the paper?

In xeddsa_sign, why set:

r = hash1(a || M || Z)

instead of one of:

r = hash1(Z || a || m)
r = hash1(a || Z || M)?

It seems like it would be better to incorporate the randomness into the
state of the hash function as early as possible to reduce risk of some
(non-timing) differential side-channel attacks on the hashing step.

Why is Z fixed at 64 bytes? That is, why is its length not a function of
the size of the key and/or the digest function output length?

Do you have any suggestions for how one would mark a key as to whether it
is intended to be used for X25519 and/or EdDSA and/or XEdDSA and/or VXEdDSA?

The security considerations say that the caller "must pass in a new secret
and random 64 byte value each time the signing function is called." I
suggest s/64 byte value/**Z**/. Also, it would be nice to clarify the
extent of the badness if a Z value were to be reused.

Would you be open to using a different name than `q` for the order of the
base point? `q` is commonly used in code and specifications to refer to
what this paper calls `p`. Another name would be less confusing. The EdDSA
RFC uses `L`, IIRC.

Section 2.5 says "since the first |p| bits encode an integer greater than
p." I think it would be useful to add a clarification such as "(This is why
it is required 2**|p| - 1 - i > p.)" or otherwise clarify the motivation
for that precondition.

Cheers,
Brian

[Benedikt Schmidt]

Post by Trevor Perrin
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.
In the motivation for the randomized scheme, the document says "However,
if the same message is signed repeatedly, a glitch that affects the
calculation of h could cause this to happen (an observation due to
Benedikt Schmidt)." Could you provide a reference to a paper/message
that explains what is being referred to here, and/or add a description
of the issue to the paper?

The issue I mentioned to Trevor is just that for the deterministic
version with

r = hash1(a||M) (mod q) // no random Z
R = rB
h = hash(R||A||M) (mod q)
s = r + ha (mod q)

getting a valid signature R||s and a faulty signature R||s' where

h' = (hash(R||A||M) (mod q)) ^ delta // error or fault attack
s' = r + h'a (mod q)

allows for the same attack as reusing the same randomness for distinct
messages. For small messages or with pre-hashing
(M=Hash(large_message)), this is probably not important. For scenarios
where pre-hashing is not used, the same message might be signed more
than once, and where the time required for hashing is significant, it
might be preferable to add randomness.

Best,
Benedikt