<div><div>Just a quick question: Not reusing keys requires no security proofs at all. Is there really a benefit that justifies key reuse? (I suppose that if you really need a verifiable PoP of a Curve25519 key...)</div><div> </div>I, personally, am rather uncomfortable with Gap-DH. Especially when CDH is what you're giving up.</div><div> <div>(And as a note to folks who may not be aware, I believe that Adam Langley has implemented this: <a href="https://github.com/agl/ed25519/tree/master/extra25519">https://github.com/agl/ed25519/tree/master/extra25519</a>)</div> </div><div> </div>On Monday, June 16, 2014, Trevor Perrin <<a href="mailto:trevp@trevp.net">trevp@trevp.net</a>> wrote: <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> 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] <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.8213" target="_blank">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.8213</a> [2] <a href="http://www.cs.ucdavis.edu/~rogaway/papers/dhies.pdf" target="_blank">http://www.cs.ucdavis.edu/~rogaway/papers/dhies.pdf</a> [3] <a href="http://research.microsoft.com/pubs/81673/strongake-submitted.pdf" target="_blank">http://research.microsoft.com/pubs/81673/strongake-submitted.pdf</a> [4] <a href="http://cacr.uwaterloo.ca/techreports/2011/cacr2011-11.pdf" target="_blank">http://cacr.uwaterloo.ca/techreports/2011/cacr2011-11.pdf</a> [5] <a href="http://www.isg.rhul.ac.uk/~kp/ModularProofs.pdf" target="_blank">http://www.isg.rhul.ac.uk/~kp/ModularProofs.pdf</a> [6] <a href="http://eprint.iacr.org/2010/638" target="_blank">http://eprint.iacr.org/2010/638</a> [7] <a href="http://eprint.iacr.org/2011/615" target="_blank">http://eprint.iacr.org/2011/615</a> [8] <a href="http://ed25519.cr.yp.to/ed25519-20110926.pdf" target="_blank">http://ed25519.cr.yp.to/ed25519-20110926.pdf</a> [9] <a href="https://datatracker.ietf.org/doc/draft-jivsov-ecc-compact/?include_text=1" target="_blank">https://datatracker.ietf.org/doc/draft-jivsov-ecc-compact/?include_text=1</a> _______________________________________________ Curves mailing list <a href="javascript:;" onclick="_e(event, 'cvml', 'Curves@moderncrypto.org')">Curves@moderncrypto.org</a> <a href="https://moderncrypto.org/mailman/listinfo/curves" target="_blank">https://moderncrypto.org/mailman/listinfo/curves</a> </blockquote>