Key encapsulation mechanism

Not to be confused with key wrap.

In cryptography, a key encapsulation mechanism, or KEM, is a public-key cryptosystem that allows a sender to generate a short secret key and transmit it to a receiver securely, in spite of eavesdropping and intercepting adversaries.

A KEM allows a sender who knows a public key to simultaneously generate a short random secret key and an encapsulation or ciphertext of the secret key by the KEM's encapsulation algorithm. The receiver who knows the private key corresponding to the public key can recover the same random secret key from the encapsulation by the KEM's decapsulation algorithm.

The security goal of a KEM is to prevent anyone who doesn't know the private key from recovering any information about the encapsulated secret keys, even after eavesdropping or submitting other encapsulations to the receiver to study how the receiver reacts.

Difference from public-key encryption

The difference between a public-key encryption scheme and a KEM is that a public-key encryption scheme allows a sender to choose an arbitrary message from some space of possible messages, while a KEM chooses a short secret key at random for the sender.

The sender may take the random secret key produced by a KEM and use it as a symmetric key for an authenticated cipher whose ciphertext is sent alongside the encapsulation to the receiver. This serves to compose a public-key encryption scheme out of a KEM and a symmetric-key authenticated cipher in a hybrid cryptosystem.

Most public-key encryption schemes such as RSAES-PKCS1-v1_5, RSAES-OAEP, and Elgamal encryption are limited to small messages and are almost always used to encrypt a short random secret key in a hybrid cryptosystem anyway. And although a public-key encryption scheme can conversely be converted to a KEM by choosing a random secret key and encrypting it as a message, it is easier to design and analyze a secure KEM than to design a secure public-key encryption scheme as a basis. So most modern public-key encryption schemes are based on KEMs rather than the other way around.

Definition

Syntax

A KEM consists of three algorithms:

1. Key generation, $({\mathit {pk}},{\mathit {sk}}):=\operatorname {Gen} ()$, takes no inputs and returns a pair of a public key ${\mathit {pk}}$ and a private key ${\mathit {sk}}$.
2. Encapsulation, $(k,c):=\operatorname {Encap} ({\mathit {pk}})$, takes a public key ${\mathit {pk}}$, randomly chooses a secret key $k$, and returns $k$ along with its encapsulation $c$.
3. Decapsulation, $k':=\operatorname {Decap} ({\mathit {sk}},c')$, takes a private key ${\mathit {sk}}$ and an encapsulation $c'$, and either returns an encapsulated secret key $k'$ or fails, sometimes denoted by returning $\bot$.

Correctness

A KEM is correct if, for any key pair $({\mathit {pk}},{\mathit {sk}})$ generated by $\operatorname {KeyGen}$, decapsulating an encapsulation $c$ returned by $(k,c):=\operatorname {Encap} ({\mathit {pk}})$ with high probability yields the same key $k$, $\operatorname {Decap} ({\mathit {sk}},c)=k$.

Security: IND-CCA

Security of a KEM is quantified by its indistinguishability against chosen-ciphertext attack, IND-CCA, which is loosely how much better an adversary can do than a coin toss to tell whether, given a random key and an encapsulation, the key is encapsulated by that encapsulation or is an independent random key.

Specifically, in the IND-CCA game:

1. The key generation algorithm is run to generate $({\mathit {pk}},{\mathit {sk}}):=\operatorname {Gen} ()$.
2. ${\mathit {pk}}$ is revealed to the adversary.
3. The adversary can query $\operatorname {Decap} ({\mathit {sk}},c')$ for arbitrary encapsulations $c'$ of the adversary's choice.
4. The encapsulation algorithm is run to randomly generate a secret key and encapsulation $(k_{0},c):=\operatorname {Encap} ({\mathit {pk}})$, and another secret key $k_{1}$ is generated independently at random.
5. A fair coin is tossed, giving an outcome $b\in \{0,1\}$.
6. The pair $(k_{b},c)$ is revealed to the adversary.
7. The adversary can again query ${\mathit {Decap}}({\mathit {sk}},c')$ for arbitrary encapsulations $c'$ of the adversary's choice, except for $c$.
8. The adversary returns a guess $b'\in \{0,1\}$, and wins the game if $b=b'$.

The IND-CCA advantage of the adversary is $\left|\Pr[b'=b]-1/2\right|$, that is, the probability beyond a fair coin toss at correctly distinguishing an encapsulated key from an independently randomly chosen key.

Example using RSA encryption

Using the same notation employed in the RSA article, say Alice has transmitted her public key (n, e) to Bob, while keeping her private key secret, as usual. Bob then wishes to send symmetric key M to Alice. M might be a 128- or 256-bit AES key (suitably padded for security reasons), for example. The key modulus n is typically 2048 bits or more in length, thus much larger than typical symmetric keys. Without suitable padding, if e is small enough that M^e < n, then the encryption can be quickly broken using ordinary integer arithmetic.

To avoid such potential weakness, Bob first maps M to a larger integer m, where 1 < m < n, by using an agreed-upon reversible protocol known as a padding scheme, such as OAEP. He then computes the ciphertext c corresponding to:

$c\equiv m^{e}{\pmod {n}}.$

Alice can recover m from c by using her private key exponent d by the following computation:

$m\equiv c^{d}{\pmod {n}}.$

Given m, she recovers the original key M by reversing the padding scheme.

With KEM the process is simplified as follows:

Instead of generating a random symmetric key M, Bob first generates a random m with 1 < m < n. He derives his symmetric key M by M = KDF(m), where KDF is a key derivation function, such as a cryptographic hash. He then computes the ciphertext c corresponding to m:

$c\equiv m^{e}{\pmod {n}}.$

Alice then recovers m from c by using her private key exponent d by the same method as above:

$m\equiv c^{d}{\pmod {n}}.$

Given m, she can recover the symmetric key M by M = KDF(m).

The KEM eliminates the complexity of the padding scheme and the proofs needed to show that the padding is secure. Note that while M can be calculated from m in the KEM approach, the reverse is not possible, assuming the key derivation function is a secure one-way function. An attacker who somehow recovers M cannot get the plaintext m. With the padding approach, he can. Thus KEM is said to encapsulate the key.

Note that if the same m is used to encapsulate keys for e or more recipients, and the receivers share the same exponent e, but different p, q and n, then one can recover m via the Chinese remainder theorem. Thus, if key encapsulations for several recipients need to be computed, independent values m should be used.

Earlier versions of Transport Layer Security used RSA for key exchange, before they were deprecated in favour of the more efficient elliptic-curve cryptography.

Similar techniques are available for Diffie–Hellman key exchange and other public key methods.

See also

• Key Wrap
• Optimal Asymmetric Encryption Padding
• Hybrid Cryptosystem