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.

Authenticated KEMs

Let’s look first at how to create authenticated encryption in the KEM/DEM paradigm. The DEM used to encrypt the body of a message in the KEM/DEM paradigm already provides authenticated encryption, so the only work that needs to be done is to authenticate the KEM so that the recipient can be confident the encapsulated DEM key came from a trusted source. Although we could try to manually combine a KEM with some kind of authentication mechanism, it’s almost always better to define a single abstraction that provides both properties. In this case, we can extend our KEM interface to become an authenticated KEM or AKEM. An AKEM is like a KEM, but the encapsulation function takes the sender’s private key as an additional argument, and the decapsulation function takes the sender’s public key:
function auth_encapsulate(senderPrivateKey, recipientPublicKey): // returns (aesKey, encapsulatedKey) as beforefunction auth_decapsulate(senderPublicKey, recipientPrivateKey, encapsulatedKey): // returns either the original aesKey or an error if // authentication fails
A straightforward implementation of this idea would be to combine an existing (unauthenticated) KEM with a signature scheme. The KEM produces an encapsulated key, which we then sign with our private key so that the recipient can be sure that it really came from us:
function auth_encapsulate_sig(senderPrivateKey, recipientPublicKey): var (aesKey, encapsulatedKey) = KEM.encapsulate(recipientPublicKey); var signature = sign(senderPrivateKey, encapsulatedKey); return (aesKey, encapsulatedKey || signature);function auth_decapsulate_sig(senderPublicKey, recipientPrivateKey, encapsulatedSignedKey): var (encapsulatedKey, signature) = parse(encapsulatedSignedKey); if !verify_signature(senderPublicKey, encapsulatedKey, signature): return error; return KEM.decapsulate(recipientPrivateKey, encapsulatedKey);
This works, but it can produce very large encapsulated keys. For example, if you use RSA-KEM with an RSA signature scheme and 3072-bit keys, then the encapsulated key will end up being at least 768 bytes long. We can do better by removing the explicit signature and instead using implicit authentication, where we derive the DEM key in such a way that only the genuine sender could have calculated it. Any attempt to change the encapsulated key, without using the sender’s private key, will result in a different DEM key being calculated and the DEM authenticated decryption step will fail with an authentication error.

One way to achieve this is to adapt the elliptic curve Diffie-Hellman (ECDH) KEM to include the sender’s private key in the key agreement calculation. Rather than performing a single ECDH calculation between an ephemeral private key and the recipient’s public key, we additionally perform one between the sender’s private key and the recipient’s public key. The two derived shared secrets are then concatenated before being fed into the Key Derivation Function to produce the AES key:
function auth_encapsulate_ecdh(senderPrivateKey, recipientPublicKey): var (ephemeralSecretKey, ephemeralPublicKey) = generateKeyPair(recipientPublicKey.curve); var ess = ecdh(ephemeralSecretKey, recipientPublicKey); var sss = ecdh(senderPrivateKey, recipientPublicKey); var aesKey = sha256(ess || sss || ephemeralPublicKey); return (aesKey, ephemeralPublicKey);function ecdh_decapsulate_ecdh(senderPublicKey, recipientPrivateKey, ephemeralPublicKey): var ess = ecdh(recipientPrivateKey, ephemeralPublicKey); var sss = ecdh(recipientPrivateKey, senderPublicKey); return sha256(ess || sss || ephemeralPublicKey);
(Note: as before we include the ephemeral public key in the KDF step to ensure non-malleability, and we’re using SHA-256 as a cheap and cheerful stand-in for a real KDF).

The advantage of this approach is that the encapsulated key is still just an ephemeral public key—just 32 bytes for X25519. It’s also more deniable than the signature version. NIST call this scheme the One-Pass Unified Model, and it’s also broadly similar to the Noise “K” one-way handshake pattern and the AKEM defined for the upcoming HPKE standard. Although this scheme is more compact than the combination of a KEM plus a signature, it is still computationally quite expensive because of the two ECDH computations that are needed. More efficient options such as (one-pass) MQV can reduce this overhead, but these are not widely used in practice due to patent issues and potential weaknesses of some variants.

Both of these AKEM designs suffer from some security weaknesses:

• They are both vulnerable to something called Key Compromise Impersonation (KCI) attacks. What this means is that if an attacker compromises your long-term secret key, they can not only pretend to be you when sending messages to other people, but can pretend to be anyone else when sending messages to you! For the ECDH scheme they can immediately do this. The KEM-then-sign variant is a bit stronger, in that an attacker would have to capture at least one message sent to you by the party they want to impersonate, but in practice this is often possible. Preventing KCI generally involves either an interactive authentication protocol or signing the entire message, both of which I’ll leave out of this article.
• Neither design incorporates any notion of the identity of the users involved. In some cases this can lead to Unknown Key Share attacks, in which we think we’re communicating with Alice but actually are talking to Bob. You can solve this problem by including identity information and long-term public keys in the signature or key-derivation steps. It can be useful to add a general “context” argument to the encapsulate and decapsulate functions to allow additional data to be included in the KDF:

function auth_encapsulate_ecdh(senderPrivateKey, recipientPublicKey, context): var (ephemeralSecretKey, ephemeralPublicKey) = generateKeyPair(recipientPublicKey.curve); var ess = ecdh(ephemeralSecretKey, recipientPublicKey); var sss = ecdh(senderPrivateKey, recipientPublicKey); var aesKey = sha256(ess || sss || ephemeralPublicKey || context); return (aesKey, ephemeralPublicKey);function ecdh_decapsulate_ecdh(senderPublicKey, recipientPrivateKey, ephemeralPublicKey, context): var ess = ecdh(recipientPrivateKey, ephemeralPublicKey); var sss = ecdh(recipientPrivateKey, senderPublicKey); return sha256(ess || sss || ephemeralPublicKey || context);

Sending to multiple recipients

The basic KEM/DEM paradigm runs into a problem if we want to send the same message to multiple recipients. In the traditional approach to hybrid encryption before KEMs, you’d simply generate a random AES key and then encrypt it for each recipient. But this doesn’t work for KEMs: we’d have to run the KEM separately for each recipient, obtaining a separate AES key for each one, and then encrypt the entire message with each AES key. This is very inefficient.

We can solve this problem by introducing a notion called symmetric key-wrapping, where we use one AES key to encrypt (“wrap”) another AES key. In principle, any secure authenticated encryption scheme (such as a DEM) could be used, but there are some specialised algorithms that are more compact.

The idea is a bit like the original version of hybrid encryption, but instead of directly encrypting the AES key for each recipient, we will instead use the KEM to derive a key-encryption key (KEK) for each recipient, and then use that to encrypt the random AES key (which we’ll call the Data Encryption Key, or DEK):

1. Generate a random DEK, dek = DEM.keygen()
2. Encrypt the message with dk: ciphertext = DEM.encrypt(dek, message);
3. For each recipient, r, calculate the Key Encryption Key:
   kek[r], encapsulatedKey[r] = KEM.encapsulate(r.publicKey);
4. For each KEK, encrypt the DEK: wrappedKey[r] = wrap(kek[r], dk);
5. Send the encrypted ciphertext, the wrapped keys, and the encapsulated keys to the recipients.

Each recipient then runs the KEM to decapsulate their encapsulated key and uses the result to decrypt (“unwrap”) the DEK. They then use the DEK to decrypt the rest of the message.

There is still an inefficiency here though, in that we’ll have a separate encapsulated key for each recipient. For the ECDH-KEM the encapsulated key is an ephemeral public key, and we can safely reuse the same ephemeral key pair for every recipient. This saves a costly key-pair generation step for each recipient and reduces the size of the final ciphertext, but we can’t achieve this with the existing KEM API.

Once again, we can adapt the KEM interface to natively support this. The encapsulation function is changed to take a set of public keys for the recipients rather than just one. The result is known as an mKEM, and you can find more details in this article by Nigel Smart (*cough* over here). For example, here’s an unauthenticated mKEM based on ECDH:
function mkem_encapsulate(recipientPublicKeys): var aesKey = DEM.keygen(); var (ephemeralSecretKey, ephemeralPublicKey) = generateKeyPair(); var wrappedKeys = []; for pk in recipientPublicKeys: var ss = ecdh(ephemeralSecretKey, pk); var kek = sha256(ss || ephemeralPublicKey); var wrappedKey = wrap(kek, aesKey); wrappedKeys += wrappedKey; end return (aesKey, ephemeralPublicKey || wrappedKeys);

Authenticated mKEMs

It’s easy to see how we could adapt the generic mKEM approach of the previous section to provide authenticated encryption (AmKEM? mAKEM?): simply add the sender’s private key to the interface and then perform an authenticated key derivation for each recipient, just as we did for the single-recipient AKEM:
function auth_mkem_encapsulate(senderPrivateKey, recipientPublicKeys): var aesKey = DEM.keygen(); var (ephemeralSecretKey, ephemeralPublicKey) = generateKeyPair(); var wrappedKeys = []; for pk in recipientPublicKeys: var ess = ecdh(ephemeralSecretKey, pk); var sss = ecdh(senderPrivateKey, pk); var kek = sha256(ess || sss || ephemeralPublicKey); var wrappedKey = wrap(kek, aesKey); wrappedKeys += wrappedKey; end return (aesKey, ephemeralPublicKey || wrappedKeys);
This does provide authenticated encryption, but only if all the recipients are honest. If any of the recipients is malicious, or have had their private key compromised, they can create a new message that appears to come from the original sender:

• First they decapsulate the genuine message to obtain the DEM key, dek.
• They then create a new message and encrypt it using the DEM and the same DEK: var c2 = DEM.encrypt(dek, "My new message");
• Finally, they re-attach the wrapped keys and ephemeral public key from the original message and send the whole thing to the same recipients (or a subset of them).

When the recipients decrypt the message it will appear that it is a genuine message from the original sender. This can happen regardless of whether you use signatures or implicit authentication in the AKEM. The fundamental reason is that neither the encapsulated keys nor the wrapped keys are in any way tied to the actual message. The KEM ensures the authenticity of the data encryption key, and the DEM ensures that a message could only have been created by someone who had access to that DEK. The problem is that the set of people who have access to the DEK is the original sender and all of the recipients.

Protecting against this kind of attack is known as insider security, and to solve it we’ll need to give up some measure of deniability. We could just sign the entire message, in which case we give up all deniability: any third party can verify that we sent that message, not just our intended recipients. Let’s call this outsider non-repudiation. What we really want is a slightly weaker guarantee: the recipients can prove to each other that the message came from the original sender (or didn’t in the case of a forgery), but they can’t prove that to anyone outside the group. We’ll call this insider non-repudiation.

For example, if Alice sends a message to Bob and Charlie, then Bob can prove to Charlie that Alice really did send that message (even if Charlie failed to receive it), but Bob can’t prove anything about the origin of the message to Delilah, who wasn’t in the original set of recipients. As far as Delilah is concerned, Bob could have fabricated the message.

It turns out that we can quite easily solve this problem, but first we need a little detour.

Tag-KEM: KEMs with associated data

The original formulation of the KEM/DEM paradigm required both the KEM and the DEM to be secure against chosen ciphertext attacks (CCA). This is a strong notion of security, but was found to be too strong in some cases. There are efficient hybrid encryption schemes in which either the KEM or the DEM is not CCA-secure, but when combined in the right way can achieve CCA-secure public key encryption. Some of these schemes are more efficient than they would be otherwise. To accommodate these schemes into the KEM/DEM paradigm, a new variant known as Tag-KEM was introduced. A Tag-KEM (TKEM) splits the encapsulation of a symmetric key into two phases:

• First, a function is called with the recipient’s public key and it outputs an AES key to use with the DEM and a private state value:
  var (aesKey, state) = TKEM.key(recipientPublicKey);
• Then, after the message has been encrypted with the DEM, a second function of the TKEM is called to generate an encapsulated key from the internal state and a tag. The tag is some arbitrary associated data that will be linked to the encapsulated key. You can think of it a bit like the context argument we added earlier to allow user identities to be bound to the encapsulated key.
  var encapsulatedKey = TKEM.encapsulate(state, tag);
• To decapsulate the key, the recipient has to provide the same tag. If they provide a different tag then an error is returned.

In the original paper, this is used to allow the DEM to be a simple CPA-secure (unauthenticated) encryption algorithm. The entire encrypted ciphertext from the DEM is passed in as the tag to the TKEM. The TKEM then applies a MAC to the tag as part of the encapsulation process, effectively transforming it into a secure Encrypt-then-MAC scheme. We can use the same mechanism to ensure that the key encapsulation is tied to the message to prevent insider attacks against authenticated KEMs, by ensuring that the tag is included in the authentication step. The same idea has been used to construct secure signcryption schemes from Tag-KEM (signcryption is a strong form of public key authenticated encryption that provides the same authenticity guarantees as a signature, and so provides the stronger outsider non-repudiation we want to avoid).

There are two ways that we could accomplish this:

• We can add a tag argument to the AKEM mechanism, so that the tag is directly included in the authentication provided by the AKEM. For example, using the context argument we described earlier. If the AKEM is based on signatures, then this effectively becomes a signcryption scheme, which has the advantage of also preventing KCI attacks, but destroys deniability.
• If we are using key-wrapping, and the key-wrapping function allows associated data (SIV-AES does, AES-KW doesn’t) then we can include the tag there instead. This better preserves deniability, but remains vulnerable to KCI.

If we’re using a KEM based on ECDH with a strong KDF like HKDF, then these two options are pretty similar: the tag ends up getting included in a strong MAC (PRF) protected by a key known only to the sender and an individual recipient. If the tag is the whole message, then this ensures that a new message can’t be created with the same encapsulated DEK without the other recipients being able to detect this.

mATKEMs

Putting it all together, we’d get a multi-recipient authenticated Tag-KEM, or mATKEM for short! A mATKEM has the following functions:

• keygen() – generates public and private keys for a sender/recipient and returns them.
• key(senderPrivateKey, recipientPublicKeys) – returns a fresh DEM key and a private state object that is tied to the sender, recipients, and the DEM key.
• auth_encapsulate(state, tag) – encapsulates the DEM key for each of the recipients in a way that they can authenticate the sender, with the tag also authenticated (but not encapsulated). Returns the encapsulated key.
• auth_decapsulate(senderPublicKey, recipientPrivateKey, encapsulatedKey, tag) – authenticates that the encapsulated key was produced by the given sender with the given tag, and then decapsulates and returns the DEM key. If authentication fails then an error is returned instead.

A sketch of an implementation of a secure mATKEM based on ECDH with key-wrapping is shown below. This is just a sketch of how such a thing could be implemented, I haven’t rigorously analysed it or attempted to prove it correct.
function key(senderPrivateKey, recipientPublicKeys): var dek = DEM.keygen(); var state = (dek, senderPrivateKey, recipientPublicKeys); return (dek, state);function auth_encapsulate(state, tag): var (dek, senderPrivateKey, recipientPublicKeys) = state; var (ephemeralSecretKey, ephemeralPublicKey) = generateKeyPair(); var wrappedKeys = []; for pk in recipientPublicKeys: var ess = ecdh(ephemeralSecretKey, pk); var sss = ecdh(senderPrivateKey, pk); var kek = KDF(ess || sss || ephemeralPublicKey || tag); var wrappedKey = wrap(kek, dek); wrappedKeys += wrappedKey; end return ephemeralPublicKey || wrappedKeys;function auth_decapsulate(senderPublicKey, recipientPrivateKey, encapsulatedKey, tag): var ephemeralPublicKey || wrappedKeys = encapsulatedKey; var ess = ecdh(recipientPrivateKey, ephemeralPublicKey); var sss = ecdh(recipientPrivateKey, senderPublicKey); var kek = KDF(ess || sss || ephemeralPublicKey || tag); for wrappedKey in wrappedKeys: var dek = unwrap(kek, wrappedKey); if dek != error: return dek end return error;

Compactly committing DEMs

In the original formulation of a Tag-KEM, the tag input is the full ciphertext output of the (unauthenticated) DEM. But in the mATKEM implementation this entire ciphertext gets passed into the KDF or MAC for every recipient, which is very inefficient for long messages. This can be optimised in the multi-recipient case by hashing the tag once with a collision-resistant hash function rather than including the whole ciphertext in the KEM or key-wrap calculation for every recipient.

An alternative approach would be to use an authenticated DEM that is compactly committing (which I’ll refer to as ccDEM) and then use the MAC tag from the DEM as the tag for the authenticated TKEM. The advantage of reusing the authentication tag from the DEM rather than calculating it in the KEM, is that it allows us to use DEM schemes that are not based on Encrypt-then-MAC, for example misuse-resistant modes like SIV-AES.

Not all authenticated encryption algorithms are compactly committing, and several popular algorithms such as AES-GCM and ChaCha20-Poly1305 are definitely not. Although those algorithms prevent an attacker who doesn’t know the DEK from altering or forging new ciphertexts, if the attacker does know the key (as in insider security) then they can actually find other messages that have the same tag. The same is true for CMAC used by SIV and CCM. The definition of a compactly committing encryption algorithm requires that the MAC is a collision-resistant pseudorandom function (PRF) such as HMAC. If we assume that Alice (the sender) is honest then we should be able to get away with just second-preimage resistance instead for this application, which allows us to use shorter tags.

A ccDEM would be a DEM that takes a key, message, and (optional) associated data and returns a ciphertext and compactly committing authentication tag. An insider-secure multi-recipient authenticated public key encryption scheme (phew!) can then be built as the following generic composition:
function encrypt(senderPrivateKey, recipientPublicKeys, plaintext): var (dek, state) = mATKEM.key(senderPrivateKey, recipientPublicKeys); var (ciphertext, tag) = ccDEM.encrypt(dek, plaintext); var encapsulatedKey = mATKEM.auth_encapsulate(state, tag); return (encapsulatedKey, ciphertext, tag);function decrypt(senderPublicKey, recipientPrivateKey, receivedMessage): var (encapsulatedKey, ciphertext, tag) = receivedMessage; var dek = mATKEM.auth_decapsulate(senderPublicKey, recipientPrivateKey, encapsulatedKey, tag); if dek = error: return error; return DEM.decrypt(dek, ciphertext, tag);
The combination of a compactly committing DEM and an authenticated Tag-KEM seems like a powerful way of thinking about secure public key encryption schemes. This was first suggested to me by Paul Grubbs on the CFRG mailing list, but as he says it has not been formally analysed so please don’t rush to deploy such a scheme in production. Hopefully a real cryptographer will find this problem interesting and decide to fill in the gaps.

That concludes this look at building authenticated KEMs for multiple recipients. We’ve seen how the original KEM interface can be adapted to accommodate stronger security goals. As with the original KEM proposal, finding the right API is an important part of building secure software, and the wrong API can leave you constantly fighting subtle security issues or inefficiencies. In the next article, I look at forward secrecy and how that tantalising state argument in the Tag-KEM API can be a bridge towards secure interactive protocols like Signal or Noise.

https://neilmadden.blog/2021/02/16/when-a-kem-is-not-enough/

#authenticatedEncryption #cryptography #kemDemParadigm #publicKeyEncryption

Neil Madden

2021-01-22 14:29:47

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:

• Bleichenbacher’s attack against PKCS#1 v1.5 padding for RSA encryption broke SSL and SSH. It still regularly resurfaces.
• Padding oracle attacks against AES in CBC mode with PKCS#7 / PKCS#5 padding also broke SSL.
• Even after fixes were introduced, these attacks can often be revived using side-channel attacks or implementation flaws. Even improved padding schemes like OAEP, which were supposed to remove these attacks, have been found to be vulnerable in practice.

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.

(*) Other symmetric encryption algorithms are available. I’ll use “AES” in this article to generically refer to symmetric authenticated encryption.

https://neilmadden.blog/2021/01/22/hybrid-encryption-and-the-kem-dem-paradigm/

#hybridEncryption #kemDemParadigm #publicKeyEncryption