When a KEM is not enough

In my previous post, I described the KEM/DEM paradigm for hybrid encryption. The key encapsulation mechanism is given the recipient’s public key and outputs a fresh AES key and an encapsulation of that key that the recipient can decapsulate to recover the AES key. In this post I want to talk about several ways that the KEM interface falls short and what to do about it:

  • As I’ve discussed before, the standard definition of public key encryption lacks any authentication of the sender, and the KEM-DEM paradigm is no exception. You often want to have some idea of where a message came from before you process it, so how can we add sender authentication?
  • If you want to send the same message to multiple recipients, a natural approach would be to encrypt the message once with a fresh AES key and then encrypt the AES key for each recipient. With the KEM approach though we’ll end up with a separate AES key for each recipient. How can we send the same message to multiple recipients without encrypting the whole thing separately for each one?
  • Finally, the definition of public key encryption used in the KEM/DEM paradigm doesn’t provide forward secrecy. If an attacker ever compromises the recipient’s long-term private key, they can decrypt every message ever sent to that recipient. Can we prevent this?

In this article I’ll tackle the first two issues and show how the KEM/DEM abstractions can be adjusted to cope with each. In a follow-up post I’ll then show how to tackle forward secrecy, along with replay attacks and other issues. Warning: this post is longer and has more technical details than the previous post. It’s really meant for people who already have some experience with cryptographic algorithms.

Continue reading “When a KEM is not enough”

Hybrid encryption and the KEM/DEM paradigm

If you know a bit about public key cryptography, you probably know that you don’t directly encrypt a message with a public key encryption algorithm like RSA. This is for many reasons, one of which being that it is incredibly slow. Instead you do what’s called hybrid encryption: first you generate a random AES key (*) and encrypt the message with that (using a suitable authenticated encryption mode), then you encrypt the AES key with the RSA public key. The recipient uses their RSA private key to decrypt the AES key and then uses that to decrypt the rest of the message. This is much faster than trying to encrypt a large message directly with RSA, so pretty much all sane implementations of RSA encryption do this.

Continue reading “Hybrid encryption and the KEM/DEM paradigm”