KEM/DEM technique for hybrid encryption

From CryptoWiki
Jump to: navigation, search

The KEM/DEM technique for hybrid encryption is a paradigm combines the efficiency and large message space of secret key encryption with the advantages of public key cryptography.

Due to its simplicity and flexibility, the approach has ever since gained increased popularity and has been successfully adapted in encryption standards. In hybrid public key encryption (PKE), first a key encapsulation mechanism (KEM) is used to fix a random session key that is then fed into a highly efficient data encapsulation mechanism (DEM) to encrypt the actual message.

A ciphertext output from a hybrid cryptosystem has two components:

  • a key encapsulation mechanism (KEM);
  • a data encapsulation mechanism (DEM).

This KEM-DEM pair ciphertext can be written as

Hybenc kem 10en.PNG

Upon receipt of this pair, the receiver should decrypt the KEM block using her/his private key to obtain the ephemeral symmetric key K, and then using this key to decrypt the DEM block to retrieve Payload_Message.


The hybrid scheme operation principies

In applications, in particular in those which need encryption of bulk data, it is now a standard approach that encryption uses a hybrid scheme.

In such a scheme, public-key cryptography is used to encrypt a so called ephemeral key for keying a symmetric cryptosystem; this establishes the shared ephemeral key between a sender and a receiver; the bulk data payload is then encrypted under the shared ephemeral key using a symmetric cryptosystem.

Such a combined scheme achieves the best out of the two kinds of cryptosystems:

  • the ease of key distribution from public-key cryptosystems;
  • the efficiency from the symmetric cryptosystems.

Public Key Encapsulation Mechanisms

A public-key encapsulation mechanism Hybenc dem 1.PNG with associated key-space Hybenc dem 2.PNG consists of three polynomial-time algorithms.

  • via Hybenc dem 5.PNG the randomized key-generation algorithm produces keys for security parameter Hybenc kem 4.PNG;
  • via Hybenc dem 7.PNG, a key Hybenc dem 8.PNG together with a ciphertext C is created;
  • via Hybenc dem 9.PNG the possessor of secret key sk decrypts ciphertext C to get back a key or the rejection symbol ⊥.

Data Encapsulation Mechanisms

A (stateless) data encapsulation mechanism Hybenc kem 1.PNG consists of three polynomial-time algorithms:

  • via Hybenc kem 2.PNG the randomized key-generation algorithm produces a uniformly distributed key Hybenc kem 3.PNG for security parameter Hybenc kem 4.PNG;
  • via Hybenc kem 5.PNG a message m is encrypted under the key K;
  • via Hybenc kem 6.PNG a possessor of the key K decrypts the ciphertext C to get back a message or the special rejection symbol ⊥.

The hybrid scheme examples

Hybrid encryption schemes include several KEM-DEM schemes:

  • a scheme named FO proposed by Fujisaki and Okamoto;
  • a scheme named HD-RSA proposed by Pointcheval;
  • a scheme named DHAES proposed by Abdalla, Bellare and Rogaway.

FO scheme

The scheme of Fujisaki and Okamoto takes the following formulation:

Hybenc fo 1.PNG

where G, H are hash functions. In this scheme, the decryption result from the KEM block is pair Hybenc fo 2.PNG. The recipient uses разультатом расшифроваки блока KEM является пара Hybenc fo 2.PNG. Получатель использует число to "seed" the hash function G to obtain a symmetric key Hybenc fo 4.PNG; then using it to decrypt the DEM block.

Finally, the recipient can verify the correctness of the decryption by re-evaluation Hybenc fo 5.PNG. So this scheme allows the recipient to detect whether the ciphertext has been modified or corrupted en route. The detection of ciphertext alteration is the main technical enabler for a cryptosystem being secure against active attackers.


The HD-RSA scheme of Pointcheval is based on an intractability problem named dependent RSA: given an RSA ciphertext Hybenc hdrsa 1.PNG, find Hybenc hdrsa 2.PNG. This problem is apparently hard if one cannot find the e-th root of modulo the composite N (the RSA problem).

Then, the KEM block of the HD-RSA scheme is simply Hybenc hdrsa 1.PNG for a random Hybenc hdrsa 3.PNG. The recipient as the owner of N can of course extract r from and then construct B. The scheme uses Hybenc hdrsa 4.PNG as the symmetric key for the DEM block, as in the hybrid scheme of Fujisaki-Okamoto.

DHAES scheme

The DHAES scheme of Abdalla, Bellare and Rogaway is a hybrid scheme where the DEM block also attaches a message authentication code as a means for data integrity validation. The two symmetric keys (one for the DEM block and one for the MAC block) are derived from a hash function formulation: Hybenc dhaes 1.PNG where Hybenc dhaes 2.PNG is the KEM block and Hybenc dhaes 3.PNG is the recipient's public key.

Clearly, the owner of the public key Hybenc dhaes 3.PNG can operate the private key v on the KEM block Hybenc dhaes 2.PNG to obtain Hybenc dhaes 4.PNG, and thereby reconstruct Hybenc dhaes 1.PNG for further derivation of the two symmetric keys.

Without using the private key v, the task of decryption seems to be something similar to solving the computational Diffie-Hellman problem. The problem for finding Hybenc dhaes 1.PNG given Hybenc dhaes 2.PNG, Hybenc dhaes 4.PNG is called hash Diffie-Hellman (HDH) problem.


To encrypt a message addressed to Alice in a hybrid cryptosystem, Bob does the following:

  1. Obtains Alice's public key.
  2. Generates a fresh symmetric key for the data encapsulation scheme.
  3. Encrypts the message under the data encapsulation scheme, using the symmetric key just generated.
  4. Encrypt the symmetric key under the key encapsulation scheme, using Alice's public key.
  5. Send both of these encryptions to Alice.

To decrypt this hybrid ciphertext, Alice does the following:

  1. Uses her private key to decrypt the symmetric key contained in the key encapsulation segment.
  2. Uses this symmetric key to decrypt the message contained in the data encapsulation segment.

The hybrid scheme using

A widely used combination of public-key and symmetric-key cryptosystems in cryptographic protocols is a so-called digital envelope technique. This is the combination of the RSA cryptosystem with a symmetric-key cryptosystem such as the DES, the 3DES or the AES. This common combination RSA + DES(3DES) is the basic mode for the secure sockets layer protocol.

SSL protocol has been used in popular Web-browsers and Web-servers. In the SSL protocol, the initiator of the protocol (let it be Alice, usually in the position of a Web client) will first download the public-key material of the other communication party (let it be Bob, usually in the position of a Web server); then Alice (in fact, her web-browser software) will generate a random session key, encrypts ("envelopes") the session key using Bob's public key and send the "envelope" to Bob. After Bob (in fact, his web-server software) has decrypted the "envelope" and retrieved the session key, the two parties can then use the session key to key a symmetric encryption scheme for their subsequent confidential communications.

The hybrid scheme vulnerabilities

In the context of protocols, the simple hybrid encryption scheme is conceptually very simple. But it has two limitations:

  • First, the scheme uses a session key which is created by one party (the message sender or the protocol initiator); the other party (the message receiver or the protocol responder) will have to completely rely on the sender's or the protocol initiator's competence (or honesty) in key generation for security. This may not be desirable in some circumstances, for instance, in the SSL protocol's client-server setting where the client is the sender and is implemented in software which is notoriously weak in generation of randomness.
  • The second limitation of the simple hybrid encryption scheme is due to its nonevanescent property. In hybrid encryption scheme, an eavesdropper who can coerce the receiver into revealing her/his private key can then recover the full Payload_Message. This weakness is often referred to as lack of "forward secrecy property." The forward secrecy property means it is impossible for an eavesdropper to recover the plaintext message in a future time using the ciphertext messages sent in the past, either by means of cryptanalysis or even by means of coercion.

These two limitations can be overcome if the public-key cryptographic part of a hybrid encryption scheme uses the Diffie-Hellman key exchange protocol.



Go to list of references for section "The KEM/DEM technique for hybrid encryption".


Krivtsov V., 2015