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

This is the third part of my series on Key Encapsulation Mechanisms (KEMs) and why you should care about them. Part 1 looked at what a KEM is and the KEM/DEM paradigm for constructing public key encryption schemes. Part 2 looked at cases where the basic KEM abstraction is not sufficient and showed how it can be extended to add support for multiple recipients and sender authentication. At the end of part 2, I promised to write a follow-up about tackling forward-secrecy and replay attacks in the KEM/DEM paradigm, so here it is. In this article we’ll go from simple one-way message encryption to a toy version of the Signal Protocol that provides forward secrecy and strong authentication of two (or more) parties.

WARNING: please pay attention to the word “toy” in the previous sentence. This is a blog post, not a thorough treatment of how to write a real end-to-end encrypted messaging protocol.

The problems to be solved

There were three major issues left unsolved by the previous blog posts, whichh are the following:

• The confidentiality of messages is protected if only the sender’s long-term secret key is compromised. But if the recipient’s long-term key is compromised then all previous messages to that recipient can be decrypted. In technical terms, we’d say that the encryption lacks forward secrecy. (More specifically, it only has sender-compromise forward secrecy).
• Messages can be captured and replayed by an attacker. Although the recipient can be assured that a message was originally authored by a trusted party (if an authenticated KEM is used), they have no guarantee that it was that same party that just sent them the message. For example, if the message authorizes the sender’s bank to transfer some money to the attacker, the attacker can capture and replay the message multiple times to get more and more money. In this case, we say that the message authentication doesn’t guarantee freshness.
• Finally, without signing the entire message content, the encryption schemes seen so far are vulnerable to Key Compromise Impersonation (KCI) attacks: if an attacker compromises your secret key they can not only pretend to be you to other people, but can pretend to be other people when talking to you.

The first two issues are connected with time: in both cases we want the message to be connected to the time that it is created, either to ensure it cannot be replayed later or that it cannot be decrypted later. By solving these problems we will also fix the vulnerability to KCI attacks too. To do this, we’ll move from an offline message encryption scheme to an online interactive protocol.

Varieties of Diffie-Hellman worth wanting*

If you’ve got this far in the series, you probably have a good idea of what Diffie-Hellman (DH) key agreement is all about. Two parties exchange public keys and then perform a DH between their own secret key and the other party’s public key to derive a shared secret that they can then use to encrypt and authenticate messages to each other.

In its most basic form, each party uses their long-lived (“static”) keys for DH, and so always derive the same shared secret. This “static-static” DH key agreement operation provides authentication of both the sender and the recipient, but is vulnerable to replay attacks and doesn’t provide forward secrecy. If we want to ensure that a fresh key is derived every time (as required for a KEM) we can either mix a random value (nonce) into the key derivation step, or we can replace one of the static keys with a fresh temporary (“ephemeral”) key.

This is what the DHIES (Diffie-Hellman Integrated Encryption Scheme) and the elliptic curve variant (ECIES) do: the sender’s static key is replaced with an ephemeral key, producing an ephemeral-static DH agreement. The ephemeral public key is then attached to the message. Ephemeral-static key agreement has forward secrecy against sender key compromise (but not recipient key compromise), but is still vulnerable to replay attacks (unless the recipient remembers all previously seen ephemeral keys). It also lacks sender authentication because the sender’s secret key has been replaced with an ephemeral one that anyone could have generated. This is why the authenticated KEM in part 2 of this blog series used two key agreements: an ephemeral-static one to ensure fresh message keys, and a static-static one to ensure sender authentication.

To prevent replay attacks and ensure forward-secrecy against recipient key compromise, there is another variant of DH we can use: static-ephemeral DH. In this mode, the recipient generates an ephemeral key pair and sends the ephemeral public key to the sender. The sender then performs a DH key agreement between that ephemeral public key and their own static secret key and uses the resulting shared secret to encrypt and authenticate a message to the recipient. The recipient uses the ephemeral secret key and the sender’s static public key to derive the same secret and decrypt the message. The recipient is assured of the identity of the sender and is protected against replay attacks because the sender can only have derived the shared secret after seeing the ephemeral public key. If the recipient deletes the ephemeral secret key immediately after decrypting the message from the sender then this also ensures forward secrecy against recipient key compromise.

This static-ephemeral DH also eliminates KCI attacks. The ephemeral public key effectively acts as a challenge in a challenge-response protocol, ensuring that the sender is positively authenticated.

The security properties of these different variants of Diffie-Hellman, along with a pure ephemeral-ephemeral DH, are summarised in the following table:

Security properties of different Diffie-Hellman variants
By combining different modes of DH, we can achieve much stronger security properties than a single DH can achieve on its own. If we feed the outputs of each DH into a single secure key derivation function then we can achieve the best security properties of each individual key agreement. The Noise Protocol Framework is an extended study of the security properties of different DH combinations, referred to as “handshake patterns”. In particular, we can see that handshakes that combine an ephemeral-static DH and a static-ephemeral DH achieve the strongest security properties once the handshake completes. By combining these with a static-static DH we can achieve stronger security properties also during the handshake itself (useful if you want to exchange some “early data” during the handshake to save time).

Signed prekeys

We’ve seen that interactive handshake protocols can solve our problems with replay attacks, forward secrecy, and KCI, but how does this relate to KEMs? With a KEM the sender is able to send messages to a recipient just by knowing the recipient’s static public key. So how does a (recipient-generated) ephemeral challenge come into the picture? The sender could first contact the recipient to get an ephemeral challenge, but what if the recipient is offline?

This problem is faced by secure messaging services such as Signal. The solution they came up with is to use signed prekeys. A prekey is simply an ephemeral key pair that the recipient generates ahead of time and uploads to some central server that all users have access to. For example, Bob can generate a bunch of ephemeral key pairs and upload the public key parts to the server while storing the ephemeral secret keys somewhere safe on his local device. If Alice wants to send a message to Bob she contacts the server, which sends her one of Bob’s prekeys (and then deletes it). Alice then uses her KEM to construct a message to Bob, using the prekey as if it was Bob’s static public key. To assure Alice that this prekey really did come from Bob, Bob can sign the prekeys using his static private key. Effectively each prekey is a one-time-use ephemeral certificate.

When Bob receives the message from Alice, he can use the corresponding ephemeral secret key (stored on his device) along with Alice’s public key to decrypt and authenticate the message. He then deletes that ephemeral prekey to prevent it being reused, ensuring protection against replay attacks and forward secrecy.

If Alice is using the ECDH authenticated KEM from the previous blog post, then she will effectively end up doing two key agreement steps:

• An ephemeral-ephemeral key agreement between a fresh ephemeral secret key generated by the KEM and Bob’s ephemeral prekey.
• A static-ephemeral key agreement between Alice’s static secret key and Bob’s ephemeral prekey.

If you look back to the table of security properties, this combination ticks all of the boxes apart from recipient authentication—which is handled by the signature on the prekey.

So signed pre-keys together with an authenticated KEM can solve our problems and make a very secure communication system. But what happens if you run out of prekeys? You could just say that Bob can’t receive any more messages until he replenishes the supply, effectively making prekeys work as a form of rate-limiting. Or you could allow Alice to fallback to a normal authenticated KEM with Bob’s static public key. Signal adopts a middle ground and has Bob publish a “semi-static” (or “semi-ephemeral” depending on your point of view) signed prekey along with a bundle of normal prekeys. Alice can then fallback to using this semi-static prekey if there are no ephemeral prekeys left and Bob will rotate this prekey the next time he is online.

Reply-able encryption and ratcheting

Signal only uses prekeys when establishing a new conversation between Alice and Bob. Once they have exchanged messages, they can use the authenticated communication channel they’ve established to exchange fresh ephemeral keys periodically. Signal actually does this on every message that Alice and Bob exchange. When Alice sends a message to Bob, she attaches a fresh ephemeral public key that Bob can use to encrypt his reply. Once she receives this reply from Bob, she discards the old ephemeral secret key and generates a new one. This process ensures that fresh encryption and authentication keys are continually being derived in a process known as ratcheting. (So called because it is impossible to reverse the process to figure out what previous keys were used). You can read more about it in Signal’s excellent documentation.

The ECDH AKEM developed in the last blog post already generates fresh ephemeral keys for each message and attaches them to the ciphertext as the encapsulated key. The authentication provided by the KEM assures Bob that Alice is the source of this ephemeral key, much like the signature in a signed prekey. So in principle, Bob could use this ephemeral public key in the place of Alice’s static public key when constructing a reply.

But the problem is that the AKEM destroys the ephemeral secret key as soon as the message to Bob has been sent. So if Bob replies using that ephemeral key then Alice won’t be able to decrypt Bob’s messages. What we need is some way to keep track of the state of the interaction from one message to the next. Well, this is exactly what the Tag-KEM abstraction allows. Recall that in a Tag-KEM, when Alice wants to send a message to Bob she first calls a key() function with her secret key and Bob’s public key. This returns a data encryption key (DEK) that she can use to encrypt the message and an opaque state object. She then calls a separate auth_encapsulate function passing in this state object and a “tag”, which returns the encapsulated key.

We can adapt the Tag-KEM API so that the encapsulate operation returns a new state along with the encapsulated key. Alice can then keep this state around and use it to process the response from Bob. I’m going to call this notion replyable encryption (abusing the English language a little), and an AKEM that supports replying to a received message a replyable KEM or rKEM. An rKEM acts just like an AKEM for the first message from Alice to Bob, but then allows Bob to reply to that message upgrading the exchange to an interactive handshake providing stronger security properties as discussed in the Noise specification.

Warning: as with some material in the previous blog post, this appears to be an entirely novel construction that hasn’t been studied extensively by cryptographers. The point of these blog posts is to explore interesting perspectives on cryptography. There may be fatal weaknesses in what follows! Use Noise or Signal if you want something for production.

An rKEM has the following operations:

• rKEM.keygen() generates the long-term public and secret keys for a party.
• rKEM.begin(mySecretKey, theirPublicKey) starts a conversation between the local party’s secret key and the remote party’s public key. It returns an opaque state object.
• rKEM.key(state) returns a Data Encryption Key (DEK) to use for sending a message to the other party.
• rKEM.auth_encap(state, tag) encapsulates the DEK and returns the encapsulated key and a new state object. The new state object encapsulates the ephemeral secret key used by the KEM.
• rKEM.auth_decap(state, encapsulatedKey, tag) authenticates the encapsulated key and tag based on the current state object and returns the DEK and a new state object (encapsulating the received ephemeral public key), or returns an error if authentication failed.

To send a first message to Bob, Alice carries out the following steps:

var state = rKEM.begin(aliceSecretKey, bobPublicKey);var dek = rKEM.key(state);var (ciphertext, tag) = DEM.encrypt(dek, message);var (encapKey, state) = rKEM.auth_encap(state, tag);// Alice then sends encapKey, ciphertext, tag to Bob

On the other side, Bob receives the message from Alice and then runs the following operations to decrypt it and send a reply:

var state = rKEM.begin(bobSecretKey, alicePublicKey);var (dek, state) = rKEM.auth_decap(state, encapKey, tag);var message = DEM.decrypt(dek, ciphertext, tag);// Now compose replyvar dek = rKEM.key(state);var (ciphertext, tag) = DEM.encrypt(dek, reply);var (encapKey, state) = rKEM.auth_encap(state, tag);// Send encapKey, ciphertext, tag back to Alice

Alice can then perform the same process on her end using her remembered state from the first message to decrypt the response and generate another reply, and so on. At each step the sender and recipient keys in the state are replaced by fresh ephemeral keys, ensuring that the keys are ratcheted on every new message.

I created a very basic (and probably very insecure!) implementation of this concept on GitHub, along with some implementations of other KEM variants discussed in the articles. You can also see a unit test version of the Alice and Bob conversation with lots of debug logging to see how it all works. This version also partially supports multiple recipients, providing a tantalising glimpse of secure end-to-end encrypted group chat. A fun project would be to flesh out the implementation to keep track of the full Noise handshake state rather than just ephemeral keys, to ensure derived keys depend on a hash of the history of all previous interactions too.

Conclusions

In this post we’ve seen how to solve the thorny problems of forward secrecy, replay protection, and resistance to key compromise impersonation. By first introducing signed prekeys and then adapting our KEM interface to support interactive handshake protocols we can solve all of these problems using the security properties of different Diffie-Hellman key agreement configurations.

It turns out that the Tag-KEM abstraction that was developed for entirely different reasons is always half way to being an interactive protocol by adding the crucial notion of a state. The notion of replyable encryption and rKEMs bridges the gap between a non-interactive KEM and a fully interactive protocol by threading that state into every operation and allowing a new state to be returned. The result transforms the humble KEM into a secure protocol state machine.

I hope you’ve enjoyed this series of articles on KEMs. We started by showing how the KEM/DEM paradigm is the right way to think about public key encryption, and have then incrementally adapted that abstraction to encompass more and more features: sender authentication, multiple recipients, security against insider threats, and finally to interactive protocols that can (in theory) achieve quite strong security properties. It’s been a fun learning exercise for me writing them and I hope you learned something from reading them. I think the notion of KEM as a unifying abstraction for teaching cryptography concepts has a lot to recommend it.

One notable absence from most of these discussions has been that of signatures. I hope to write a blog post about signatures soon, because there are some fascinating connections here that also illuminate good reasons not to use them. Or at least, to use them sparingly in specific circumstances. Until the next time…

https://neilmadden.blog/2021/04/08/from-kems-to-protocols/

#cryptography #hybridEncryption #kemDemParadigm #protocols #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

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

Dhole Moments

2021-01-21 04:56:24

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.

(Art by Khia.)

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.

I have strong opinions about cryptographic library design.
(Art by Swizz.)

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.)

https://soatok.blog/2021/01/20/please-stop-encrypting-with-rsa-directly/

#asymmetricCryptography #cryptography #RSA #SecurityGuidance #symmetricCryptography