Encrypting between nodes that have RSA keys: Diffie-Hellman or random secret key?

I have two peers with RSA keys; they want to encrypt a non-trivially sized message between them, so I want a random AES symmetric secret key, which is encrypted with Bob's public RSA key, and sent along with the AES ciphertext.

I believe this idea is pretty standard. The question is: do I generate the AES key using Java's SecureRandom.getInstanceStrong(), or do I implement Diffie-Hellman between the two nodes?

I assume the main advantage of DH is forward secrecy. Are there any other considerations? How difficult is it to implement DH securely?

If you're using RSA as a key encapsulation mechanism, then there is no need to use Diffie-Hellman to generate the shared secret.

Diffie-Hellman provides key agreement: Both Bob and Alice will end up with the same shared secret. No party a priori selects what that secret will be, it is determined by whatever $$({g^a})^b \equiv ({g^b})^a$$ happens to be.

If you did use Diffie-Hellman to generate the shared secret, then both Alice and Bob will already have the shared secret. Having Alice then encapsulate that and send it to Bob via RSA does not accomplish much.

How difficult is it to implement DH securely?

It's difficult - you are not expected to do so, and you should not need to do so. Perfectly good, free libraries that have already solved this problem exist.

Note

If it is at all possible, consider using an existing protocol and library such as TLS or libsodium instead of re-inventing this particular wheel.

If your current crypto library forces you to make these types of decisions, it's not a library you want to use.

A good crypto library will offer high level constructions that solve specific problems, rather then requiring you to combine low level constructs into a solution that you think/hope might work.

I believe this idea is pretty standard.

Quoth the bear, Nevermore

Actually, using RSA for this is not that great of an idea and is being phased out in general.

RSA-based key agreement (or transport, or exchange) with PKCS#1 v1.5 is vulnerable to Bleichenbacher attacks. OAEP (from PKCS#1 v2.0) is better, though it requires implementation to not leak partial information on failure causes, otherwise Manger's attack applies (which is like Bleichenbacher's, but more efficient). That's the first reason RSA key exchange is being discouraged.

The second reason is that RSA key generation is expensive (and hard to make constant-time)(there is a constant-time RSA keygen in BearSSL), so you don't want to make a new RSA key pair for each incoming connection. Reusing encryption keys goes contrary to forward secrecy, and forward secrecy has become a selling point (though it's a bit overhyped, in my opinion).

The third reason is basically performance, or at least performance perceived through the filter of microbenchmarks. An RSA private key operation is an order of magnitude more expensive than some ECDH.

Source: the Bear says so (excerpt from a private conversation)

• Don't I lose forward secrecy without DH? If Bob's RSA keys are compromised an attacker who saved older messages could decrypt the random key and thus the entire message. This is for encrypting REST message payloads; we already use TLS in the transport layer. But imagine that Bob's load balancer terminates the TLS connection and then forwards the REST call via plaintext HTTP. That's why we want to further encrypt the payload, but don't want to use RSA because the POST body is larger than the RSA key size. – cantara256 Feb 7 '19 at 19:55
• Also note that the you use a secure padding when sending the key encapsulated with RSA. There have been several padding oracle attacks on various messengers which did the same thing. – VincBreaker Feb 7 '19 at 19:56
• @VincBreaker Basically the point of the answer was to indicate that generally you would use Diffie-Hellman or RSA for establishing the key; Computing a DH shared secret then sending it via RSA is pointless. To be more explicit: If you're going to use DH, then just use DH. But that's besides the point: you still want to use libsodium, which uses ECDH. – Ella Rose Feb 7 '19 at 20:06
• @RaulAcevedo There is the "Encrypted streams and file encryption" section that mentions forward secrecy – Ella Rose Feb 14 '19 at 1:47
• @RaulAcevedo The key exchange section discusses how to use asymmetric keys to get a symmetric key (this is the problem that DH solves). Do note that if you are sending public keys on the wire, you'll need some way to authenticate them on the other side, or your application will be vulnerable to a man-in-the-middle attack (if you notice lots of details piling up here, this is why a pre-built solution such as TLS is recommended if it is at all possible to use it) – Ella Rose Feb 15 '19 at 0:26

Don't implement your own protocol if you can possibly avoid it. If you can get a direct TCP connection between the peers, use TLS. If you can't, either use TLS (but you'll have to work a bit to relay the packets) or Signal.

If you really have to write your own protocol, avoid using RSA encryption. RSA decryption is tricky. Absolutely do not use PKCS#1 v1.5 encryption, which is vulnerable to a class of attacks due to Bleichenbacher that hasn't said its last word yet. Avoid using OAEP, which is less tricky but still delicate. OAEP is difficult to implement, but at least for the most part, if you have a good implementation of it, you're ok. V1.5 decryption is not only tricky to implement but also to use because it's extremely sensitive to how you handle failures either of the decryption itself or of decoding the decrypted data. In particular, if you expect to decrypt a key of a given length and you get data that's of a different length, what do you do? You must not do anything different depending on whether the data is valid or not! Even tiny timing differences inside your code can be observable over time. If an adversary sends you carefully-constructed ciphertexts and can find out which ones are valid, they can use this information to decrypt the legitimate ciphertexts.

RSA signature is less tricky to use than decryption. So base your protocol on signature rather than decryption. This is a generic observation about asymmetric cryptography, not limited to RSA. With encryption, decryption is the operation that both uses the private key (so it may leak information if not done correctly) and works with data that comes from the outside (and so may have been crafted by an attacker). With signature, the signature operation usually works with trusted data, so there are fewer error conditions to cope with, while the verification operation doesn't have the private key so it only needs to be functionally correct and doesn't need to be protected against side channel attacks.

Another reason to prefer signature-based protocols to asymmetric-encryption-based protocols if that if there is a breach and an adversary can forge signatures, that typically only helps them attack still-live systems, and they may still be thwarted by additional controls, or caught by verification logs. On the other hand, if an adversary can breach an encryption-based system, it's likely that they'll be able to decrypt old data without even you knowing precisely what they gained access to.

In addition, as you note, sharing ephemeral keys through a key agreement mechanism rather than having one side encrypt a key and send it to the other party has the advantage of forward secrecy: if an adversary gains access to one side's private key, they still won't be able to decrypt old data, only data encrypted with ephemeral keys generated while they had access to the system.

The basic principle to establish a symmetric key between two parties that have each other's long-term public key is:

1. Generate an ephemeral (EC)DH key.
2. Send the ephemeral public key and other metadata.