Key encapsulation mechanism

Not to be confused with Key Wrap.

In cryptographic protocols, a key encapsulation mechanism (KEM) is used to secure symmetric key material for transmission using asymmetric (public-key) algorithms. It is commonly used in hybrid cryptosystems. In practice, public key systems are clumsy to use in transmitting long messages. Instead they are often used to exchange symmetric keys, which are relatively short. The symmetric key is then used to encrypt the longer message. The traditional approach to sending a symmetric key with public key systems is to first generate a random symmetric key and then encrypt it using the chosen public key algorithm. The recipient then decrypts the public key message to recover the symmetric key. As the symmetric key is generally short, padding is required for full security and proofs of security for padding schemes are often less than complete. KEMs simplify the process by generating a random element in the finite group underlying the public key system and deriving the symmetric key by hashing that element, eliminating the need for padding.

Example using RSA encryption

Using the same notation employed in the RSA system 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, for example. Note that the public key $n$ is typically 1024-bits or even longer, thus much larger than typical symmetric keys. 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 turns M into a larger integer $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 message 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 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 one-way. 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.

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

Envelope encryption

Envelope encryption is a term used by cloud service providers to describe their usage of key encapsulation. It is used by all major cloud service providers, often as part of centralized key management systems in cloud computing.

Envelope encryption gives names to the keys used in key encapsulation: Data Encryption Keys (abbreviated DEK, and used to encrypt data) and Key Encryption Keys (abbreviated KEK, and used to encrypt the DEKs). In a cloud environment, encryption with envelope encryption involves generating a DEK locally, encrypting one's data using the DEK, and then issuing a request to wrap (encrypt) the DEK with a KEK stored in a potentially more secure service. Then, this wrapped DEK and encrypted message constitute a ciphertext for the scheme. To decrypt a ciphertext, the wrapped DEK is unwrapped (decrypted) via a call to a service, and then the wrapped DEK is used to decrypt the encrypted message. In addition to the normal advantages of key encapsulation, using asymmetric encryption for the KEK in a cloud context provides easier key management and separation of roles, but can be slower.

In cloud systems, such as Google Cloud Platform and Amazon Web Services, a key management system (KMS) can be available as a service. In some cases, the key management system will store keys in hardware security modules, which are hardware systems that protect keys with hardware features like intrusion resistance. This means that KEKs can also be more secure because they are stored on secure specialized hardware. Envelope encryption makes centralized key management easier because a centralized key management system only needs to store KEKs, which occupy less space, and requests to the KMS only involve sending wrapped and unwrapped DEKs, which use less bandwidth than transmitting entire messages. Since one KEK can be used to encrypt many DEKs, this also allows for less storage space to be used in the KMS. This also allows for centralized auditing and access control at one point of access.

See also

• Key Wrap
• Optimal Asymmetric Encryption Padding