KEM/DEM technique for hybrid encryption

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

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 with associated key-space consists of three polynomial-time algorithms.

via the randomized key-generation algorithm produces keys for security parameter ;
via , a key together with a ciphertext C is created;
via 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 consists of three polynomial-time algorithms:

via the randomized key-generation algorithm produces a uniformly distributed key for security parameter ;
via a message m is encrypted under the key K;
via 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:

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

Finally, the recipient can verify the correctness of the decryption by re-evaluation . 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.

HD-RSA

The HD-RSA scheme of Pointcheval is based on an intractability problem named dependent RSA: given an RSA ciphertext , find . 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 for a random . The recipient as the owner of N can of course extract r from and then construct B. The scheme uses 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: where is the KEM block and is the recipient's public key.

Clearly, the owner of the public key can operate the private key v on the KEM block to obtain , and thereby reconstruct 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 given , is called hash Diffie-Hellman (HDH) problem.

Example

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

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

To decrypt this hybrid ciphertext, Alice does the following:

Uses her private key to decrypt the symmetric key contained in the key encapsulation segment.
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.