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.
But there’s a problem with this approach. An AES key is at most only 32 bytes long, while RSA wants to encrypt things that are approximately the same size as the modulus – i.e., 256 bytes for 2048-bit RSA keys, 384 bytes for 3072-bit keys, and so on. To make this work, we have to add some padding to the AES key until it is the right size. This sounds simple enough, but you may be surprised to find out that padding is one of the most dangerous things you can do in cryptography:
Although it’s possible to get padding right, the historical record is not good. So it would be really nice to not have to do this fiddly padding at all. But how can we do hybrid encryption without padding?
Key encapsulation
It turns out that we can do hybrid encryption without resorting to padding, by changing the way that we think about hybrid encryption. Rather than generating a fresh random AES key and then encrypting that with RSA, we can instead define an API that we call with the recipient’s public key and it returns a fresh AES key and it’s encrypted form all in one go. That is, rather than doing these two steps:
var aesKey = generate_aes_key();
var encryptedKey = rsa_encrypt(aesKey, rsaPublicKey);We instead do this one step:
var (aesKey, encryptedKey) = rsa_encapsulate(rsaPublicKey);This new function is known as a Key Encapsulation Mechanism (KEM), and the change of API makes all the difference. The trick is that a KEM doesn’t have to directly encrypt the AES key. Instead it can encrypt something else from which the AES key can be derived. In particular, it can encrypt something that is exactly the right size for the RSA key being used, so no padding is required. This is exactly what RSA-KEM does. In RSA-KEM, the encapsulation mechanism generates a random value between 2 and n-1 (where n is the RSA modulus: a large number around 2048 bits or more), and then encrypts that using the RSA public key. The random number is then fed through a Key Derivation Function (KDF), which can be as simple as a secure hash function like SHA-256 (although there are better alternatives), to derive the AES key:
function rsa_encapsulate(publicKey):
var random = generate_secure_random(2..publicKey.modulus-1);
var encryptedKey = rsa_encrypt(random, publicKey);
var aesKey = sha256(random);
return (aesKey, encryptedKey);Here rsa_encrypt is plain “textbook” RSA encryption with no padding. This would normally be completely insecure, but because the random value is the same size as the modulus it is secure in this case. Indeed, RSA-KEM has a nice proof of security (it’s pretty clear to see how an attack on RSA-KEM would imply an attack on RSA itself). The term “encapsulation” refers to the fact that an attacker doesn’t get to choose or even see the input to the RSA encryption function (the random value), only the output of the (one-way) hash function, which makes it much harder to attack.
The AES key is then used to encrypt the message and the encrypted message and the encapsulated key are both sent to the recipient. The recipient then decrypts the random value and runs it through the KDF again to recover the AES key:
function rsa_decapsulate(encryptedKey, rsaPrivateKey):
var random = rsa_decrypt(encryptedKey, rsaPrivateKey);
return sha256(random);Data encapsulation
When a KEM is being used for hybrid encryption, it’s common to refer to encrypting the message with the derived AES key as the Data Encapsulation Mechanism (DEM). Because the KEM guarantees that a fresh key is returned every time, we can actually relax the security requirements of the symmetric encryption scheme to only provide one-time security. This means that you could, in theory, get away with using a constant nonce/IV for the encryption scheme, although I wouldn’t recommend this unless you know what you’re doing. (It’s too easy for a well-meaning developer to “optimise” the KEM to reuse the same value for a few messages).
Update (23 Jan): I found a nice paper from 2012 by G.M. Zaverucha that shows that the deterministic nature of a DEM leads to attacks in a multi-user setting, so a randomized symmetric encryption scheme should always be preferred.
The definition of a DEM ensures both confidentiality and integrity, and allows associated data to be authenticated but not encrypted. You can therefore think of it as (possibly deterministic) Authenticated Encryption with Associated Data (AEAD), which is the standard modern definition of symmetric encryption.
The KEM/DEM paradigm is then just the use of a KEM with a DEM to implement public key encryption:
function encrypt(message, publicKey):
var (aesKey, encryptedKey) = kem.encapsulate(publicKey);
var ciphertext = dem.encrypt(aesKey, message);
return encryptedKey || ciphertext;This combination is guaranteed to be secure against adaptive chosen ciphertext attacks if the KEM and DEM both are.
KEMs without RSA
Another advantage of the KEM approach is that it is much more natural to define KEMs for algorithms other than RSA. For example, you can easily define a KEM based on elliptic-curve Diffie-Hellman key agreement (ECDH):
function ecdh_encapsulate(recipientPublicKey):
var (ephemeralSecret, ephemeralPublic) = generateKeyPair(recipientPublicKey.curve);
var sharedSecret = ecdh(ephemeralSecret, recipientPublicKey);
var aesKey = sha256(sharedSecret || ephemeralPublic); // NB "||" is concatenation
return (aesKey, ephemeralPublic);
function ecdh_decapsulate(ephemeralPublic, recipientPrivateKey):
var sharedSecret = ecdh(recipientPrivateKey, ephemeralPublic);
return sha256(sharedSecret || ephemeralPublic);This corresponds to the widely-used ECIES encryption scheme (known as ECDH-ES in JOSE, for example). Here the “encryption” of the AES key is just an ephemeral public key, from which the AES key can be derived.
Summary
This approach and terminology, known as the KEM-DEM paradigm, was first proposed by Victor Shoup and has since become popular in academic cryptography. The basic idea, as shown in this article, is to combine generating a fresh random AES key and encrypting it into a single step. This turns out to make RSA encryption much easier, and to more naturally accommodate other cryptographic primitives.
The ability of the KEM paradigm to easily accommodate cryptographic schemes that are quite different to RSA makes it attractive, and this seems now very much the Right Way to think about hybrid encryption. When NIST announced a competition to design new post-quantum cryptographic algorithms, they explicitly included KEMs as a security goal, and many KEMs were proposed. It’s clear that the KEM-DEM paradigm will be important to the future of public key encryption.
The discussion in this article leaves out a lot of details, such as how to fit public key authenticated encryption into this paradigm (hint), how to achieve forward secrecy, or how to encrypt a message to multiple recipients. These are discussed further in part 2 and part 3.
