Using Ed25519 signing keys for encryption | Hacker News Reader

Using Ed25519 signing keys for encryption

blog.filippo.io

56 pointsaxiomdata31616 comments

The edcurve.js project( 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-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.

> 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.

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.

> 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.”

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 [2]: https://www.cs.cornell.edu/courses/cs5430/2015sp/notes/rsa_s...

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.

> @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/ and (shameless plug) 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?

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?

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.

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, 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.

The point of the tool isn't to use SSH keys; that's just a nice feature of it. The normal usage for the tool doesn't involve SSH keys at all.

I don’t know if that’s really the case, given https://docs.google.com/document/d/11yHom20CrsuX8KQJXBBw04s8...

> Goals

> * The option to encrypt to SSH keys, with built-in GitHub .keys support

And lower on the page, it shows the use of built-in command-line syntax for “github:$recipientname”.

It definitely works for keys that aren’t used for SSH, but support for SSH keys seems to be a large part of the rational for the ed25519 support (otherwise it would just be a tool that operated on X25519 keys directly).

That's true, I'm just saying, the rationale for the existence of the tool isn't "build something that encrypts with SSH keys", but rather, "build a modern replacement for PGP file encryption".

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

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.mediawi...

[2] https://arxiv.org/abs/1810.04660

[3] https://eprint.iacr.org/2015/1135

[4] https://cr.yp.to/ecdh.html

[5] https://tools.ietf.org/html/rfc8017

I don’t honestly see what kind of attack could be defeated by multiplying by a fixed value (maybe because there isn’t one, or likely because I simply can’t) but sure, why not! It feels like good hygiene, can be done with just the X25519 function and a scalar field multiplication, and I imagine it can help with proofs.

Any reason not to use a simpler SHA-512(ID || <PK>) value for t?

BTW, I was about to report an errata for RFC 8017, until I realized they inverted both the order and the starting index in going from X_n to x_n... yeah, as much as I’d like not to redefine that function every time, I might keep calling it big endian fixed size encoding.

Reply on news.ycombinator.com