Please Stop Encrypting with RSA Directly

Let me state up front that, while we’re going to be talking about an open source project that was recently submitted to Hacker News’s “Show HN” section, the intent of this post is not at all to shame the developer who tried their damnedest to do the right thing. They’re the victim, not the culprit.

RSA, Ya Don’t Say

Earlier this week, an HN user shared their open source fork of a Facebook’s messenger client, with added encryption. Their motivation was, as stated in the readme:

It is known that Facebook scans your messages. If you need to keep using Facebook messenger but care about privacy, Zuccnet might help.

It’s pretty simple: you and your friend have Zuccnet installed. Your friend gives you their Zuccnet public key. Then, when you send a message to your friend on Zuccnet, your message is encrypted on your machine before it is sent across Facebook to your friend. Then, your friend’s Zuccnet decrypts the message. Facebook never sees the content of your message.

I’m not a security person and there’s probably some stuff I’ve missed – any contributions are very welcome! This is very beta, don’t take it too seriously.

From Zuccnet’s very humble README.

So far, so good. Facebook is abysmal for privacy, so trying to take matters into your own hands to encrypt data so Facebook can’t see what you’re talking about is, in spirit, a wonderful idea.

However, there is a problem with the execution of this idea. And this isn’t a problem unique to Zuccnet. Several times per year, I come across some well-meaning software project that makes the same mistake: Encrypting messages with RSA directly is bad.

From the Zuccnet source code:

const encryptMessage = (message, recipientPublicKey) => {
  const encryptedMessage = crypto.publicEncrypt(
    {
      key: recipientPublicKey,
      padding: crypto.constants.RSA_PKCS1_OAEP_PADDING,
      oaepHash: "sha256",
    },
    Buffer.from(message),
  );

  return encryptedMessage.toString("base64");
};

/**
 *
 * @param {String} encryptedMessage - base64 encoded string
 */
const decryptMessage = encryptedMessage => {
  const encryptedMessageBuffer = Buffer.from(encryptedMessage, "base64");
  const { privateKey } = getOrCreateZuccnetKeyPair();
  const message = crypto.privateDecrypt(
    {
      key: privateKey,
      padding: crypto.constants.RSA_PKCS1_OAEP_PADDING,
      oaepHash: "sha256",
    },
    Buffer.from(encryptedMessageBuffer),
  );
};

To the Zuccnet author’s credit, they’re using OAEP padding, not PKCS#1 v1.5 padding. This means their code isn’t vulnerable to Bleichenbacher’s 1998 padding oracle attack (n.b. most of the RSA code I encounter in the wild is vulnerable to this attack).

However, there are other problems with this code:

1. If you try to encrypt a message longer than 256 bytes with a 2048-bit RSA public key, it will fail. (Bytes matter here, not characters, even for English speakers–because emoji.)
2. This design (encrypting with a static RSA public key per recipient) completely lacks forward secrecy. This is the same reason that PGP encryption sucks (or, at least, one of the reasons PGP sucks).

There are many ways to work around the first limitation.

Some cryptography libraries let you treat RSA as a block cipher in ECB mode and encrypt each chunk independently. This is an incredibly stupid API deign choice: It’s slow (asymmetric cryptography operations are on the order of tens-to-hundreds-of-thousands times slower than symmetric cryptography) and you can drop/reorder/replay blocks, since ECB mode provides no semantic security.

A much better strategy is to encrypt the data with a symmetric key, then encrypt that key with RSA. (See the end of the post for special treatment options that are especially helpful for RSA with PKCS#1 v1.5 padding.)

Working around the second problem usually requires an Authenticated Key Exchange (AKE), similar to what I covered in my Guide to End-to-End Encryption. Working around this second problem also solves the first problem, so it’s usually better to just implement a forward-secret key exchange protocol than try to make RSA secure.

(You can get forward secrecy without an AKE, by regularly rotating keys, but AKEs make forward secrecy automatic and on-by-default without forcing humans to make a decision to rotate a credential– something most people don’t do unless they have to. AKEs trade user experience complexity for protocol complexity–and this trade-off is almost universally worth taking.)

Although AKEs are extremely useful, they’re a bit complex for most software developers to pick up without prior cryptography experience. (If they were easier, after all, there wouldn’t be so much software that encrypts messages directly with RSA in the first place.)

Note: RSA itself isn’t the reason that this lacks forward secrecy. The problem is how RSA is used.

Recommendations

For Developers

First, consider not using RSA. Hell, while you’re at it, don’t write any cryptography code that you don’t have to.

Libsodium (which you should use) does most of this for you, and can easily be turned into an AKE comparable to the one Signal uses. The less cryptography code you have to write, the less can go catastrophically wrong–especially in production systems.

If jettisoning RSA from your designs is a non-starter, you should at least consider taking the Dhole Moments Pledge for Software Developers:

I will not encrypt messages directly with RSA, or any other asymmetric primitive.

Simple enough, right?

Instead, if you find yourself needing to encrypt a message with RSA, remind yourself that RSA is for encrypting symmetric keys, not messages. And then plan your protocol design accordingly.

Also, I’m pretty sure RSA isn’t random-key robust. Ask your favorite cryptographer if it matters for whatever you’re building.

(But seriously, you’re better off not using RSA at all.)

For Cryptography Libraries

Let’s ask ourselves, “Why are we forcing developers to know or even care about these details?”

Libsodium doesn’t encumber developers with unnecessary decisions like this. Why does the crypto module built into JavaScript? Why does the crypto module built into most programming languages that offer one, for that matter? (Go is a notable exception here, because their security team is awesome and forward-thinking.)

In my opinion, we should stop shipping cryptography interfaces that…

• Mix symmetric and asymmetric cryptography in the same API
• Allow developers to encrypt directly with asymmetric primitives
• Force developers to manage their own nonces/initialization vectors
• Allow public/private keys to easily get confused (e.g. lack of type safety)

For example: Dhole Crypto is close to my ideal for general-purpose encryption.

Addendum: Securing RSA with PKCS#1 v1.5

Update: Neil Madden informs me that what I wrote here is actually very similar to a standard construction called RSA-KEM. You should use RSA-KEM instead of what I’ve sketched out, since that’s better studied by cryptographers.

(I’ve removed the original sketch below, to prevent accidental misuse.)