11
$\begingroup$

The libsodium documentation contains a function crypto_sign_ed25519_pk_to_curve25519 that converts an Ed25519 key into a Curve25519 one, so it can be used for both key exchange/encryption and signing:

"Ed25519 keys can be converted to Curve25519 keys, so that the same key pair can be used both for authenticated encryption (crypto_box) and for signatures (crypto_sign)."

The same page ends "Notes: If you can afford it, using distinct keys for signing and for encryption is still highly recommended."

My question is whether reusing an Ed25519 keypair for both uses has been proven secure anywhere, for example in the sense of Joint Security of Encryption and Signature or a similar paper?

The two constructions seem to be:

  • EdDSA signature (i.e. "Schnorr signature done properly")
  • Ephemeral DH key exchange using a one-time keypair on the sender side and the recipient's public key (mapped to Curve25519).

Both involve a one-time ephemeral keypair and a hash function, I'm fine with the random oracle model (so we can assume the EdDSA nonce, which is actually a function of the key and message, is really random) and one can get domain separation by including a separation tag in the key exchange, i.e. when Alice wants to send a file to Bob whose public key is Q, she picks a pair (r, r.P) and sets the key as k = H(r.Q, "this is a key not a signature") or something similar.

Intuitively this should be fine in the random oracle model; has someone actually (dis)proved it though?

$\endgroup$
  • 3
    $\begingroup$ That's kind of unfair. I think it is not recommended because security would be hard to proof :) $\endgroup$ – Maarten Bodewes Jul 22 '16 at 11:07
  • 1
    $\begingroup$ @MaartenBodewes I don't expect it to be hard to prove if you're willing to assume that XSalsa20 and SHA512 are independent hash functions modeled as random oracles. $\endgroup$ – CodesInChaos Jul 22 '16 at 14:44
  • $\begingroup$ @CodesInChaos I guess. But I expect you'd have to do it yourself. The proof has a high "meh" factor ... it won't drop any jaws unless you prove that it is not secure. So for the question about "has somebody actually (dis)proved it...probably not, but nobody is going to answer "no", which is the general issue with these kind of questions. It's not completely asking for refs, but it's close. And a "no" can easily turn into a "yes" given time as well ,so the "no" answer would be useless for others. $\endgroup$ – Maarten Bodewes Jul 23 '16 at 20:31
  • 4
    $\begingroup$ I was hoping DH+EdDSA was such a standard combination that someone had done it in the appendix of their paper somewhere as part of a larger work ... on its own it's only really worth an eprint, I agree with Maarten here. But considering that libsodium has a function for doing this in practice, it's probably worth someone trying just to be sure. It would make a good first proof for a PhD student perhaps. $\endgroup$ – Bristol Jul 24 '16 at 8:47
5
$\begingroup$

The paper On the Joint Security of Encryption and Signature in EMV is very close. Section 4.4, "On the Joint Security of ECIES and EC-Schnorr", states the following result:

Theorem 2. In the random oracle model ECIES-KEM and EC-Schnorr are jointly secure if the gap-DLP problem and gap-DH problem are both hard.

Obviously, this does not apply to EdDSA/DH out of the box: ECIES is a certain application of Diffie-Hellman, and EdDSA is a slightly modified variant of elliptic-curve Schnorr signatures. However, the proof sketches in the paper should be easily adaptable to EdDSA combined with any other reasonable Diffie-Hellman incarnation. (The details of this depend a little on how the DH shared secret is used for symmetric (authenticated) encryption, but it seems possible to modify the proof for all realistic settings.)

$\endgroup$
  • $\begingroup$ That's interesting! I am working in a commercial company with both ed25519 and x25519 and we would love to use just one key pair, but so far we haven't. Actually, we would be willing to pay for someone to prove this. But who can do it? Finding such expertise seems hard. $\endgroup$ – Frans Lundberg Feb 7 '18 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.