5 ms·

Using Ed25519 signing keys for encryption

56 points by axiomdata316 7y ago

galadran 7y ago
> What remains open for future work is checking for cross-protocol attacks. [...] I can't see such an attack, but if you can, let me know on Twitter. So we know using the same key for signing and encryption is catastrophic for general public key schemes. We don't know of any attacks in the Curve25519 case. Does anyone know of any proofs or partial results that might apply? Proof by absence of tweets feels a tad unsatisfactory.
- SAI_Peregrinus 7y ago
  Cryptographers tend to study things they think journals will find interesting. Attacking a theoretical construction that uses a known-vulnerable sub-method is unlikely to get grant money. After all, who would even make such a silly thing? So no one has attacked it that I've seen in the e-prints, though I haven't searched and am going from memory. Then someone notices that the naivé attack doesn't work in one case. Sure, that case doesn't claim security against the attack, but they go ahead anyway. Now it might be worth attacking. Especially if this gets used anywhere. Absence of attacks is not evidence of security. Absence of attacks against non-weakened versions with attacks against weakened versions and plenty of margin is. EG reduced-round block ciphers.
- aasasd 7y ago
  > using the same key for signing and encryption is catastrophic for general public key schemes Weird thing, I'm fifteen years in web programming with an interest in crypto, but it's the first time I hear that, at least in such categorical form. On the contrary, it's usually “public-key crypto allows you to have both this and that.”
  - cyphar 7y ago
    Almost every scheme that does signing and encryption has separate keys for each (even in cases like GnuPG which pretends to have a single key). In fact, TFA explicitly mentions an example of this causing a security problem[1]. In addition, not all public-key cryptosystems can be used to create both encryption and signing primitives[2]. [1]: https://eprint.iacr.org/2011/615.pdf https://eprint.iacr.org/2011/615.pdf [2]: https://www.cs.cornell.edu/courses/cs5430/2015sp/notes/rsa_sign_vs_dec.php https://www.cs.cornell.edu/courses/cs5430/2015sp/notes/rsa_s...
  - ptoomey3 7y ago
    The bit being referred to is how signing and encryption can be inverse operations of each other in some schemes. The canonical example is textbook RSA. Signing is the same operation/math as decryption. Likewise, verifying signatures and encryption are the same operation/math. So, if one used textbook RSA for both things under the same key pair, then an encrypted blob under public key PK could be decrypted if you can get the same person to sign that same blob using secret key SK. In other words, in textbook RSA sign(private, encrypt(public, message)) == message. There are things that make this less trivial to exploit for non-textbook cases. But, either way, it is generally easier to mostly go with “don’t use the same key for both signing and encryption” so you don’t have to do a bunch of stuff to figure out if a given construction is safe. If Filippo is supporting RSA ssh keys, I’d love a post walking through the way to prove that reusing RSA keys turns out to be safe if done carefully/thoughtfully.
y0ghur7_xxx 7y ago
> @Benjojo12 and I are building an encryption tool that will also support SSH keys as recipients, because everyone effectively already publishes their SSH public keys on GitHub. Is this not already possible with tools like https://ssh-vault.com/ https://ssh-vault.com/ and (shameless plug) https://sshenc.sh/ https://sshenc.sh/? Those tools use the RSA keys to encrypt a symmetric key that is then used to encrypt the data, but the outcome is effectively the same. No?
- akerl_ 7y ago
  Don’t those run afoul of the linked white paper (under “dangerous” in the 2nd paragraph), which talks about the attack paths made available if an RSA key is used for signing and encryption?
  - y0ghur7_xxx 7y ago
    I don't think so: neither of those tools sign the message with the same RSA keypair. sshenc.sh for example does not sign the message whatsoever. An attacker could just intercept a ciphertext, drop it, encrypt a different message and send that. Those tools are not meant for sender authentication. If you want that you would have to first share the senders pubkey with the recipient, and sign your message with the corresponding privkey.
    - ptoomey3 7y ago
      While the tools themselves might not use the same key for both operations, I think the question was asking about whether it is problematic that a user’s SSH keys, used in SSH for signing, are also used by these tools for encrypting. In other words, the concern being the same key is used for two different operations, even if not in the same tool. As I commented in https://news.ycombinator.com/item?id=19953623 https://news.ycombinator.com/item?id=19953623, I’d love to see another blog post walking folks through why/how the “dangerous” RSA keys are in fact useable for both operations because the textbook RSA concerns aren’t a concern because of X, Y, and Z.
- tptacek 7y ago
neokantian 7y ago
The edcurve.js project( https://www.npmjs.com/package/ed2curve https://www.npmjs.com/package/ed2curve ) was apparently doing something similar already, but the author disclaimed: "Note that there's currently no proof that this is safe to do." while referring to a 2013 stackexchange discussion on the subject: https://crypto.stackexchange.com/questions/3260/using-same-keypair-for-diffie-hellman-and-signing/3311#3311 https://crypto.stackexchange.com/questions/3260/using-same-k.... It may be necessary to formally prove that combined use does not introduce new vulnerabilities. The phrase "What remains open for future work is checking for cross-protocol attacks", is quite ominous in this respect. For example, combined use could gradually leak private bits to the attacker. Therefore, the status of this combined use strategy is still the same as ever before: doubtful.
thanatos_dem 7y ago
NATS is moving to an Ed25519 based auth system as well - https://github.com/nats-io/nkeys https://github.com/nats-io/nkeys
deleted 7y ago
[deleted]
kwantam 7y ago
It's possible to rule out some (but not necessarily all) cross-protocol attacks with a simple and cheap tweak. I have not proved that this rules out everything, but it appears to be no weaker than the scheme sans tweak, and proofs shouldn't be too hard. The high-level idea is to derive a new encryption key from the recipient's signing key, such that only the recipient knows the secret. This is similar to HD wallets[1] and some recent work by Dauterman et al.[2]. It's easy to show, following the work of Morita et al.[3], that EdDSA is secure against (certain) related-key attacks. This means that, even if an adversary has a signing oracle for the derived key, it cannot forge signatures under the original key. Alas, this is incomparable with giving the adversary a decryption oracle for the derived key, which means it's worth thinking about whether it's possible to prove some extra properties. It's also worth thinking about the other direction: does a signing oracle for the original key let an attacker break the encryption scheme? Again, I haven't proved these things, but it seems like it ought to be possible. Here's the idea in detail. First, definitions: - q = 2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed, the order of the Curve25519 group [1] - (SK, PK) = (s, s * G) is an Ed25519 key pair (base point is G, * is elliptic curve scalar multiplication) - <PK> is some well-known encoding of PK as a bitstring - a || b is the concatenation of a and b - ID is some fixed string that identifies this ciphersuite, say, "age_ssh_ed25519_encrypt_v1" - I2OSP and OS2IP are standard conversions between integers and byte strings as defined in RFC8017 [5] Now, to encrypt to the derived key, do the following: 1. Let t = OS2IP(SHA256(ID || I2OSP(0, 1) || <PK>) || SHA256(ID || I2OSP(1, 1) || <PK>)) mod q. In other words, t is a (nearly) uniformly random element of Zq obtained by hashing the recipient's public key. 2. Let PK' = t * PK, where * represents elliptic curve scalar multiplication. 3. Encrypt your message to PK' rather than to PK. Finally, to decrypt, the recipient does the following: 1. Compute t exactly as above. 2. Let s' = s * t, where s = SK is the secret key. 3. Decrypt the message using s' as the secret key. Note that in this scheme, everyone who encrypts to the recipient who owns (SK, PK) uses the same key. It's possible to derive a per-message key instead: choose a random nonce, hash it along with <PK> in the first step, and send it along with the message. Alternatively, you could derive a per-sender key by hashing both the sender's and recipient's keys. It's not obvious to me that per-message/per-sender keys improve security at all, and it's plausible that they somehow weaken it (since letting the attacker set the input to the hash allows it to choose among polynomially many PK'). So unless you decide that per-message keys are necessary for security, I wouldn't bother. [1] https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki https://github.com/bitcoin/bips/blob/master/bip-0032.mediawi... [2] https://arxiv.org/abs/1810.04660 https://arxiv.org/abs/1810.04660 [3] https://eprint.iacr.org/2015/1135 https://eprint.iacr.org/2015/1135 [4] https://cr.yp.to/ecdh.html https://cr.yp.to/ecdh.html [5] https://tools.ietf.org/html/rfc8017 https://tools.ietf.org/html/rfc8017

56 points by axiomdata316 7y ago

> What remains open for future work is checking for cross-protocol attacks. [...] I can't see such an attack, but if you can, let me know on Twitter. So we know using the same key for signing and encryption is catastrophic for general public key schemes. We don't know of any attacks in the Curve25519 case. Does anyone know of any proofs or partial results that might apply? Proof by absence of tweets feels a tad unsatisfactory.

SAI_Peregrinus 7y ago
Cryptographers tend to study things they think journals will find interesting. Attacking a theoretical construction that uses a known-vulnerable sub-method is unlikely to get grant money. After all, who would even make such a silly thing? So no one has attacked it that I've seen in the e-prints, though I haven't searched and am going from memory. Then someone notices that the naivé attack doesn't work in one case. Sure, that case doesn't claim security against the attack, but they go ahead anyway. Now it might be worth attacking. Especially if this gets used anywhere. Absence of attacks is not evidence of security. Absence of attacks against non-weakened versions with attacks against weakened versions and plenty of margin is. EG reduced-round block ciphers.
aasasd 7y ago
> using the same key for signing and encryption is catastrophic for general public key schemes Weird thing, I'm fifteen years in web programming with an interest in crypto, but it's the first time I hear that, at least in such categorical form. On the contrary, it's usually “public-key crypto allows you to have both this and that.”
- cyphar 7y ago
  Almost every scheme that does signing and encryption has separate keys for each (even in cases like GnuPG which pretends to have a single key). In fact, TFA explicitly mentions an example of this causing a security problem[1]. In addition, not all public-key cryptosystems can be used to create both encryption and signing primitives[2]. [1]: https://eprint.iacr.org/2011/615.pdf https://eprint.iacr.org/2011/615.pdf [2]: https://www.cs.cornell.edu/courses/cs5430/2015sp/notes/rsa_sign_vs_dec.php https://www.cs.cornell.edu/courses/cs5430/2015sp/notes/rsa_s...
- ptoomey3 7y ago
  The bit being referred to is how signing and encryption can be inverse operations of each other in some schemes. The canonical example is textbook RSA. Signing is the same operation/math as decryption. Likewise, verifying signatures and encryption are the same operation/math. So, if one used textbook RSA for both things under the same key pair, then an encrypted blob under public key PK could be decrypted if you can get the same person to sign that same blob using secret key SK. In other words, in textbook RSA sign(private, encrypt(public, message)) == message. There are things that make this less trivial to exploit for non-textbook cases. But, either way, it is generally easier to mostly go with “don’t use the same key for both signing and encryption” so you don’t have to do a bunch of stuff to figure out if a given construction is safe. If Filippo is supporting RSA ssh keys, I’d love a post walking through the way to prove that reusing RSA keys turns out to be safe if done carefully/thoughtfully.

y0ghur7_xxx 7y ago

> @Benjojo12 and I are building an encryption tool that will also support SSH keys as recipients, because everyone effectively already publishes their SSH public keys on GitHub. Is this not already possible with tools like https://ssh-vault.com/ https://ssh-vault.com/ and (shameless plug) https://sshenc.sh/ https://sshenc.sh/? Those tools use the RSA keys to encrypt a symmetric key that is then used to encrypt the data, but the outcome is effectively the same. No?

akerl_ 7y ago
Don’t those run afoul of the linked white paper (under “dangerous” in the 2nd paragraph), which talks about the attack paths made available if an RSA key is used for signing and encryption?
- y0ghur7_xxx 7y ago
  I don't think so: neither of those tools sign the message with the same RSA keypair. sshenc.sh for example does not sign the message whatsoever. An attacker could just intercept a ciphertext, drop it, encrypt a different message and send that. Those tools are not meant for sender authentication. If you want that you would have to first share the senders pubkey with the recipient, and sign your message with the corresponding privkey.
  - ptoomey3 7y ago
    While the tools themselves might not use the same key for both operations, I think the question was asking about whether it is problematic that a user’s SSH keys, used in SSH for signing, are also used by these tools for encrypting. In other words, the concern being the same key is used for two different operations, even if not in the same tool. As I commented in https://news.ycombinator.com/item?id=19953623 https://news.ycombinator.com/item?id=19953623, I’d love to see another blog post walking folks through why/how the “dangerous” RSA keys are in fact useable for both operations because the textbook RSA concerns aren’t a concern because of X, Y, and Z.
tptacek 7y ago

neokantian 7y ago

The edcurve.js project( https://www.npmjs.com/package/ed2curve https://www.npmjs.com/package/ed2curve ) was apparently doing something similar already, but the author disclaimed: "Note that there's currently no proof that this is safe to do." while referring to a 2013 stackexchange discussion on the subject: https://crypto.stackexchange.com/questions/3260/using-same-keypair-for-diffie-hellman-and-signing/3311#3311 https://crypto.stackexchange.com/questions/3260/using-same-k.... It may be necessary to formally prove that combined use does not introduce new vulnerabilities. The phrase "What remains open for future work is checking for cross-protocol attacks", is quite ominous in this respect. For example, combined use could gradually leak private bits to the attacker. Therefore, the status of this combined use strategy is still the same as ever before: doubtful.

thanatos_dem 7y ago

NATS is moving to an Ed25519 based auth system as well - https://github.com/nats-io/nkeys https://github.com/nats-io/nkeys

deleted 7y ago

[deleted]

kwantam 7y ago

It's possible to rule out some (but not necessarily all) cross-protocol attacks with a simple and cheap tweak. I have not proved that this rules out everything, but it appears to be no weaker than the scheme sans tweak, and proofs shouldn't be too hard. The high-level idea is to derive a new encryption key from the recipient's signing key, such that only the recipient knows the secret. This is similar to HD wallets[1] and some recent work by Dauterman et al.[2]. It's easy to show, following the work of Morita et al.[3], that EdDSA is secure against (certain) related-key attacks. This means that, even if an adversary has a signing oracle for the derived key, it cannot forge signatures under the original key. Alas, this is incomparable with giving the adversary a decryption oracle for the derived key, which means it's worth thinking about whether it's possible to prove some extra properties. It's also worth thinking about the other direction: does a signing oracle for the original key let an attacker break the encryption scheme? Again, I haven't proved these things, but it seems like it ought to be possible. Here's the idea in detail. First, definitions: - q = 2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed, the order of the Curve25519 group [1] - (SK, PK) = (s, s * G) is an Ed25519 key pair (base point is G, * is elliptic curve scalar multiplication) - <PK> is some well-known encoding of PK as a bitstring - a || b is the concatenation of a and b - ID is some fixed string that identifies this ciphersuite, say, "age_ssh_ed25519_encrypt_v1" - I2OSP and OS2IP are standard conversions between integers and byte strings as defined in RFC8017 [5] Now, to encrypt to the derived key, do the following: 1. Let t = OS2IP(SHA256(ID || I2OSP(0, 1) || <PK>) || SHA256(ID || I2OSP(1, 1) || <PK>)) mod q. In other words, t is a (nearly) uniformly random element of Zq obtained by hashing the recipient's public key. 2. Let PK' = t * PK, where * represents elliptic curve scalar multiplication. 3. Encrypt your message to PK' rather than to PK. Finally, to decrypt, the recipient does the following: 1. Compute t exactly as above. 2. Let s' = s * t, where s = SK is the secret key. 3. Decrypt the message using s' as the secret key. Note that in this scheme, everyone who encrypts to the recipient who owns (SK, PK) uses the same key. It's possible to derive a per-message key instead: choose a random nonce, hash it along with <PK> in the first step, and send it along with the message. Alternatively, you could derive a per-sender key by hashing both the sender's and recipient's keys. It's not obvious to me that per-message/per-sender keys improve security at all, and it's plausible that they somehow weaken it (since letting the attacker set the input to the hash allows it to choose among polynomially many PK'). So unless you decide that per-message keys are necessary for security, I wouldn't bother. [1] https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki https://github.com/bitcoin/bips/blob/master/bip-0032.mediawi... [2] https://arxiv.org/abs/1810.04660 https://arxiv.org/abs/1810.04660 [3] https://eprint.iacr.org/2015/1135 https://eprint.iacr.org/2015/1135 [4] https://cr.yp.to/ecdh.html https://cr.yp.to/ecdh.html [5] https://tools.ietf.org/html/rfc8017 https://tools.ietf.org/html/rfc8017