[curves] Ed25519 signatures from Curve25519 keys

[Trevor Perrin]

Hi,

I'm wondering about using Curve25519 keys to create and verify Ed25519
signatures.  For example, imagine you have existing Curve25519
long-term keys being used for a DH protocol, and you'd like to sign
with these keys.

Below is an attempt to provide security analysis, and work out the details.

I've run parts of this by a few people (Mike Hamburg, Robert Ransom,
CodesInChaos).  I try to credit them where appropriate, but that
doesn't imply they endorse all of this.


Joint security of signatures and DH
----
Schnorr signatures (like Ed25519) have a security proof in the Random
Oracle Model based on the (Elliptic Curve ) Discrete Log assumption
[1].

Many DH protocols have security proofs in a model where the attacker
has access to a "Decision Diffie-Hellman" oracle.   Often the attacker
can choose an arbitrary public key, cause a targeted key to perform a
DH operation with the chosen public key, and then "reveal" the hashed
output.   By hashing different inputs and seeing if the result equals
the revealed value, the attacker gains a DDH oracle involving the
targeted key and her chosen key.   These protocols can often be proven
secure in the Random Oracle Model based on the "Gap-DH" assumption:
i.e. the assumption that the Computational DH problem is hard even
when given a DDH oracle.  Protocols that can be proven secure in such
a model include ECIES [2], NAXOS [3], Ntor [4], Kudla-Paterson [5],
HOMQV [6], and others.

As in [7] section 4.4, it seems fairly easy to argue for "joint
security" when the same key is used for Schnorr signatures and for a
protocol with a Gap-DH/ROM security proof, provided the hash function
is used carefully so that RO queries for the signature can be
distinguished from RO queries for the DH-protocol.

In particular:
 - Giving the DH-protocol adversary a signing oracle doesn't help it,
as the signing oracle can be simulated in the ROM without knowledge of
the secret key [1,7].
 - Giving the signature adversary access to parties running the
DH-protocol (e.g. an eCK experiment [3] where the secret key is held
by an honest party) doesn't help if the protocol can be simulated
without knowledge of the secret key but with a DDH oracle.  If the
signature adversary + simulator could use the DDH oracle to break the
DL problem, then the Gap-DH assumption would be violated [7].

So in principle this seems secure, do people agree?


Public-key conversion
----
A Curve25519 public-key is encoded as a 255-bit x-coordinate.  An
Ed25519 public-key is encoded as a 255-bit y-coordinate, plus a "sign"
bit.

For a "unified" public-key format, I think it makes sense to stick
with Curve25519:
 - Curve25519 has seen more deployment than Ed25519, so existing
public-keys are more likely to use the Curve25519 format.
 - The sign bit isn't strictly necessary, since it can be assumed to
be zero, and the private key can be adjusted to match (see below).
 - The Curve25519 format is more efficient for DH since it can be used
directly with the Montgomery ladder.  For signature verification, the
conversion from Curve25519 format to an Ed25519 point can be combined
with decompression, so using Curve25519 public keys to verify Ed25519
signatures can be almost as fast for verification as Ed25519 public
keys (according to Mike Hamburg).
 - If code simplicity is more of a concern than speed, it's easy to
convert the curve25519 x-coordinate into an ed25519 y-coordinate by
ed_y = (curve_x - 1) / (curve_x + 1) mod 2^255-19 (page 8 of [8], hat
tip Robert Ransom).  The inversion takes perhaps 10-20% (?) of the
time for a variable-base scalar mult.  The y-coordinate can then be
encoded along with a sign bit of 0, allowing existing Ed25519 code to
be used.


Private-key conversion
----
If the Ed25519 public-key sign-bit is assumed to be zero, the private
key may need to be adjusted (per Jivsov [9]).  In other words, if
multiplying the Curve25519 private key by the Ed25519 base point
yields an Ed25519 x-coordinate that's "negative" as defined in [8],
the private key (a) must be negated modulo the order of the base point
(q), i.e. a = q - a.

Some existing curve25519 implementations set bit 254 of the private
key within the scalarmult function, so will interfere with this
negation (observation due CodesInChaos).   Robert Ransom proposed
another way to implement the negation that avoids having to modify
that code:
 - Before hashing, flip the sign bit of R
 - Before hashing, encode the sign bit of A as zero
 - As the last step, negate S, i.e. S = q - S

Jivsov argues that fixing the sign bit doesn't lose security, even
against Pollard rho (anyone care to double-check the argument? - [9]
section 8).  A side-channel that leaks only whether this negation was
performed (or not) only reveals the sign bit of the original private
key, so I think also doesn't reduce security.


Hash inputs
----
Ed25519 calculates SHA512(R || A || M), where:
 - R is an Ed25519-encoded Schnorr commitment  (= nonce *  base point)
 - A is an Ed25519-encoded public key
 - M is the message to sign

The key-derivation in the DH protocol must hash distinct inputs for
the ROM security argument to hold.  CodesInChaos suggested beginning
the key-derivation hash with 32 bytes of 0xFF, as this is an invalid
Ed25519 point.


Signature nonce
----
In the original Ed25519 implementation [8], a single master key is
used to derive both (a) the Ed25519 private scalar and (b) a secret
key for nonce generation.  Without such a master key, either
 - the nonce-generation key would have to be explicitly generated and stored
 - the nonce would have to be taken from a (strong!) RNG
 - the private scalar would have to be used as the nonce-generation key

All of these seem adequate.  Not sure which is best?

Anyways, what else have I missed?


Trevor


[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.8213
[2] http://www.cs.ucdavis.edu/~rogaway/papers/dhies.pdf
[3] http://research.microsoft.com/pubs/81673/strongake-submitted.pdf
[4] http://cacr.uwaterloo.ca/techreports/2011/cacr2011-11.pdf
[5] http://www.isg.rhul.ac.uk/~kp/ModularProofs.pdf
[6] http://eprint.iacr.org/2010/638
[7] http://eprint.iacr.org/2011/615
[8] http://ed25519.cr.yp.to/ed25519-20110926.pdf
[9] https://datatracker.ietf.org/doc/draft-jivsov-ecc-compact/?include_text=1