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...)
I, personally, am rather uncomfortable with Gap-DH. Especially when CDH is what you're giving up. (And as a note to folks who may not be aware, I believe that Adam Langley has implemented this: https://github.com/agl/ed25519/tree/master/extra25519 ) On Monday, June 16, 2014, Trevor Perrin <[email protected]> wrote: > 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 > _______________________________________________ > Curves mailing list > [email protected] <javascript:;> > https://moderncrypto.org/mailman/listinfo/curves >
_______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
