JEP draft: Key Encapsulation Mechanism API

OwnerWeijun Wang
TypeFeature
ScopeSE
StatusDraft
Componentsecurity-libs / javax.crypto
Discussionsecurity dash dev at openjdk dot org
EffortM
DurationM
Reviewed bySean Mullan
Created2023/01/25 03:48
Updated2023/03/24 18:12
Issue8301034

Summary

Define an API for Key Encapsulation Mechanism (KEM). KEM is an encryption technique for securing symmetric keys using public key cryptography.

Goals

Motivation

KEM is a modern cryptographic technique that is designed to encrypt symmetric keys using asymmetric or public key cryptography. It is different from the more traditional technique which encrypts a randomly generated symmetric key with a public key. Instead, KEM uses a different approach that typically uses properties of the public key to derive the symmetric key. This mechanism is simpler and addresses several of the disadvantages of the traditional approach.

The notion of KEM was introduced by Crammer and Shoup in Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack (section 7.1 of https://eprint.iacr.org/2001/108.pdf). Shoup later proposed it as an ISO standard in A Proposal for an ISO Standard for Public Key Encryption (section 3.1 of https://eprint.iacr.org/2001/112). It was accepted as ISO 18033-2 and published in May 2006.

KEM is used as a building block for HPKE. The NIST PQC standardization process explicitly calls for KEMs and digital signature algorithms to be evaluated as candidates for the next generation of standard public key cryptography algorithms. The DH key exchange step in TLS 1.3 can also be modeled as a KEM.

KEM can also be referred to as “Key-Establishment Mechanism”.

Third-party Java providers (BouncyCastle, IAIK, Entrust) have expressed a need for a standard KEM API that they can plug their algorithm implementations into.

KEMs are increasing in popularity and will be an important cryptographic mechanism for providing protection against quantum computers. The Java Platform contains a comprehensive set of cryptographic APIs called the JCA. Although we evaluated several of these APIs as to whether it would be feasible to implement KEM with them, each of them had major drawbacks - these issues are explained in more detail in the Alternatives section. Therefore, we believe it is important that the Java Platform provides a specific API for KEMs.

Description

A KEM contains 3 functions:

Secret key (b) should be identical to secret key (a). Thus, it is a shared secret.

The key encapsulation message is called ciphertext in ISO 18033-2. In more recent definitions of KEM, such as section 4 of RFC 9180, and NIST's PQC KEM API Notes, it is called key encapsulation message. We will use the new name throughout this JEP.

The key pair generation function is already covered by the existing KeyPairGenerator API. This JEP defines a new class named KEM for the encapsulation and decapsulation functions:

package javax.crypto;

public final class KEM {

    public record Encapsulated(SecretKey key, byte[] encapsulation, byte[] params) {}

    public static final class Encapsulator {
        Provider provider();
        int secretSize();
        int encapsulationSize();
        KEM.Encapsulated encapsulate();
        KEM.Encapsulated encapsulate(int from, int to, String algorithm);
    }

    public static final class Decapsulator {
        Provider provider();
        int secretSize();
        int encapsulationSize();
        SecretKey decapsulate(byte[] encapsulation) throws DecapsulateException;
        SecretKey decapsulate(byte[] encapsulation, int from, int to, String algorithm)
                throws DecapsulateException;
    }

    public static KEM getInstance(String alg)
        throws NoSuchAlgorithmException;
    public static KEM getInstance(String alg, Provider p)
        throws NoSuchAlgorithmException;
    public static KEM getInstance(String alg, String p)
        throws NoSuchAlgorithmException, NoSuchProviderException;

    public Encapsulator newEncapsulator(PublicKey pk)
            throws InvalidKeyException;
    public Encapsulator newEncapsulator(PublicKey pk, SecureRandom sr)
            throws InvalidKeyException;
    public Encapsulator newEncapsulator(PublicKey pk, AlgorithmParameterSpec spec, SecureRandom sr)
            throws InvalidAlgorithmParameterException, InvalidKeyException;

    public Decapsulator newDecapsulator(PrivateKey sk)
            throws InvalidKeyException;
    public Decapsulator newDecapsulator(PrivateKey sk, AlgorithmParameterSpec spec)
            throws InvalidAlgorithmParameterException, InvalidKeyException;
}

public class DecapsulateException extends GeneralSecurityException;

public interface KEMSpi {

    interface EncapsulatorSpi {
        int engineSecretSize();
        int engineEncapsulationSize();
        KEM.Encapsulated engineEncapsulate(int from, int to, String algorithm);
    }

    interface DecapsulatorSpi {
        int engineSecretSize();
        int engineEncapsulationSize();
        SecretKey engineDecapsulate(byte[] encapsulation, int from, int to, String algorithm)
                throws DecapsulateException;
    }

    EncapsulatorSpi engineNewEncapsulator(PublicKey pk, AlgorithmParameterSpec spec, SecureRandom sr)
            throws InvalidAlgorithmParameterException, InvalidKeyException;
    DecapsulatorSpi engineNewDecapsulator(PrivateKey sk, AlgorithmParameterSpec spec)
            throws InvalidAlgorithmParameterException, InvalidKeyException;
}

The getInstance method creates a new KEM object that implements the specified algorithm.

The newEncapsulator method is called by the sender. It takes in the receiver's public key and returns an Encapsulator object. The sender can then call one of its two encapsulate methods to get an Encapsulated record, which contains a SecretKey and a key encapsulation message. The encapsulate() method returns a key containing the full shared secret with an algorithm name of “Generic”. This key is usually passed into a key derivation function. The encapsulate(from, to, algorithm) method returns a key with an algorithm name of algorithm. Its key material is a sub-array of the shared secret, beginning at the byte specified by from (inclusive) and ending at the byte specified by to (exclusive).

An algorithm can define an AlgorithmParameterSpec child class to provide extra information to the newEncapsulator method. This is especially useful if the same key can be used to derive shared secrets in different ways. An AlgorithmParameterSpec child class should be implemented immutable. If any extra information inside this AlgorithmParameterSpec object needs to be transmitted along with the key encapsulation message so that the receiver is able to create a matching decapsulator, it will be included as a byte array in the params field inside the Encapsulated result. In this case, the security provider should provide an AlgorithmParameters implementation using the same algorithm name as the KEM. The receiver can initiate such an AlgorithmParameters instance with the params byte array received and recover an AlgorithmParameterSpec object to be used in its newDecapsulator call.

The newDecapsulator method is called by the receiver. It takes in the receiver's private key and returns a Decapsulator object. The receiver can then call one of the decapsulate methods that takes in the key encapsulation message received and returns the shared secret in a SecretKey. Similar to the sender side, decapsulate(encapsulation) returns a "Generic" key with the full shared secret, and decapsulate(encapsulation, from, to, algorithm) returns a key with the user-specified algorithm and key material.

It should be safe to invoke multiple encapsulate and decapsulate methods on the same object at the same time. Each invocation of encapsulate will generate a new shared secret and encapsulation.

The secretSize() and encapsulationSize() methods in either the Encapsulator and Decapsulator interface return the size of the shared secret and key encapsulation message, respectively.

A KEM implementation must implement the KEMSpi interface.

An implementation must implement the EncapsulatorSpi and DecapsulatorSpi interfaces, and return objects of these types in engineNewEncapsulator and engineNewDecapsulator methods of its KEMSpi implementation. A user's secretSize, encapsulationSize, encapsulate, and decapsulate calls on a KEM.Encapsulator or KEM.Decapsulator object are delegated to engineSecretSize, engineEncapsulationSize, engineEncapsulate, and engineDecapsulate methods in these EncapsulatorSpi and DecapsulatorSpi implementations.

Here is an example using a fictional ABC-KEM. Before the key encapsulation and decapsulation, the receiver needs to generate an "ABC" key pair and publish the public key.

// Receiver side
KeyPairGenerator g = KeyPairGenerator.getInstance("ABC");
KeyPair kp = g.generateKeyPair();
publishKey(kp.getPublic());

// Sender side
KEM kemS = KEM.getInstance("ABC-KEM");
PublicKey pkR = retrieveKey();
ABCKEMParameterSpec specS = new ABCKEMParameterSpec(...);
KEM.Encapsulator e = kemS.newEncapsulator(pkR, null, specS);
KEM.Encapsulated enc = e.encapsulate();
SecretKey secS = enc.key();
sendBytes(enc.encapsulation());
sendBytes(enc.params());

// Receiver side
byte[] em = receiveBytes();
byte[] params = receiveBytes();

KEM kemR = KEM.getInstance("ABC-KEM");
AlgorithmParameters algParams = AlgorithmParameters.getInstance("ABC-KEM");
algParams.init(params);
ABCKEMParameterSpec specR = algParams.getParameterSpec(ABCKEMParameterSpec.class);
KEM.Decapsulator d = kemR.newDecapsulator(kp.getPrivate(), specR);
SecretKey secR = d.decapsulate(em);

// secS and secR will be identical

KEM configurations

A single KEM algorithm may have multiple "configurations". These configurations may accept different types of public or private keys, using different methods to derive the shared secrets, and emit different key encapsulation messages. Each configuration should map to a specific algorithm that creates a fixed size shared secret and a fixed size key encapsulation message. The configuration should be unambiguously determined by three pieces of information:

  1. The algorithm name passed to getInstance
  2. The type of the key passed to newEncapsulator and newDecapsulator
  3. The (optional) AlgorithmParameterSpec object passed to newEncapsulator

For example, the Kyber family of KEMs may have a single algorithm named Kyber, but the implementation may support different configurations based on key types, which might be Kyber-512, Kyber-768, or Kyber-1024.

Another example is the RSA-KEM family of KEMs. The algorithm name may be simply RSA-KEM, but the implementation may support different configurations based on different RSA key sizes and different KDF settings. The different KDF settings may be expressed with an RSAKEMParameterSpec object.

In both cases, the configuration can only be determined after either newEncapsulator or newDecapsulator is called.

Delayed provider selection

The newEncapsulator and newDecapsulator methods take a key as their argument. Sometimes, the key is only recognized by a certain provider. This means the provider of a KEM algorithm cannot be determined until after the getInstance call, when the key is passed into the newEncapsulator or newDecapsulator methods. This is called delayed provider selection. Several other cryptographic services share the same feature, for example, Signature and KeyAgreement.

Each new newEncapsulator and newDecapsulator call may choose a different provider. The user can find out which provider is used by calling the provider method of the Encapsulator or Decapsulator class.

Key pair generation

All KEM definitions referenced above contain a keypair generation function. However, we don't think a generateKeyPair method should be included here because it would be confusing for a provider to decide whether to provide the keypair generation function here or in a KeyPairGenerator, or both. The user would also need to know which key pair generation API to use for a given algorithm.

About "encryption option"

ISO 18033-2 defines an "encryption option" for the encapsulate function because some asymmetric ciphers allow certain types of scheme-specific options to be passed to the encryption algorithm. This "encryption option" is not mentioned in either RFC 9180 or NIST's PQC KEM API Notes. We will not provide this function in this JEP. If this becomes necessary for a certain algorithm, a follow-on enhancement can add an overloaded encapsulate method that takes an extra algorithm-specific AlgorithmParameterSpec espec argument as the option.

Shared secret output

All existing KEM definitions referenced above return shared secrets in a byte array. However, in Java, a security provider might be backed by a native implementation and the shared secret may not be extractable. Therefore it's not always possible to return the shared secret in a byte array. The encapsulate and decapsulate methods in this JEP always return the shared secret in a SecretKey object.

If the key is extractable, the format of the key must be "RAW", and the getEncoded method must return either the full shared secret or the slice of the shared secret specified by the from and to arguments.

If the key is not extractable, the getFormat and getEncoded methods must return null, although internally the key material is either the full shared secret or contains the bytes as specified by the from and to parameters.

The implementation of these methods must be able to encapsulate or decapsulate keys with a “Generic” algorithm, a from value of 0, and a to value of the shared secret’s length. Otherwise, it can choose to throw an UnsupportedOperationException if the combination of arguments is not supported. For example, if the algorithm name cannot be mapped into an internal key type, the size of the key does not match the algorithm, or the implementation does not support slicing the shared secret freely.

The encapsulationSize and secretSize methods

Some higher-level protocols concatenate the key encapsulation message with other data directly without providing any length information. For example, Hybrid TLS Key Exchange concatenates two key encapsulating messages into a single key_exchange field, and RSA-KEM concatenates the key encapsulation with the wrapped keying data into a single "encrypted keying data". These protocols assume that the length of the key encapsulation message is fixed and well-known once the KEM configuration is fixed. Therefore, we will provide an encapsulationSize method to retrieve the size of the key encapsulation in case an application needs to extract the key encapsulation message from such concatenated data.

Also, a fixed KEM configuration always generates a fixed-size shared secret, and the size can be obtained by the secretSize method.

In summary, these methods are designed to help the application input parameters that satisfy the requirements of the KEM implementation.

Alternatives

We have considered using the existing KeyGenerator, KeyAgreement or Cipher APIs to implement KEMs, but each of them has significant issues; either they don't support the required feature set or the API does not match the KEM functions.

A KeyGenerator is able to generate a SecretKey, but not the key encapsulation message at the same time. As a workaround, we could potentially encode both the shared secret and the key encapsulation message as the encoded form of the SecretKey. However, this only works when the shared secret is extractable and this is not always true as explained in the “Shared secret output” section. For keys that can be extracted, it still requires the application to extract the secret and the key encapsulation message from the encoded form of the SecretKey, which is complex and error-prone. Alternatively, we could store the key encapsulation message inside the SecretKey as a separate field. However, that would require a new SecretKey child class that has a public method to retrieve the key encapsulation message.

A KeyAgreement is able to return both a key encapsulation message as a phase key and the shared secret with different methods. However, a KeyAgreement object was meant to be initialized with the caller's own private key, but for KEM there is no need to create a private key on the sender side. Also, the key encapsulation message in KEM is defined as an opaque byte array but KeyAgreement returns the phase key as a Key object. Additional KeyFactory and EncodedKeySpec classes would need to be created to translate between the key encapsulation message and a key.

A Cipher is able to wrap an existing key and then unwrap it. However, in KEM the shared secret is generated inside the encapsulation process. We could potentially pass in a dummy (or null) key and store the actual shared secret in the output. This has the same problem as KeyGenerator which only works when the shared secret is extractable and the application has to manually extract the key and the key encapsulation message from the wrap result. Also, the key wrapped was meant to be the same as the result of the unwrap method, a dummy input passed into the wrap method does not conform to this convention.

In short, each of these alternatives would be hacks to work around an API that was not designed to represent a KEM. While it's possible to shoehorn KEM into one of these existing APIs, it's not what these APIs were designed for. Extra classes and methods may need to be added, and the implementations would be complicated, controversial, and fragile. Without a standard KEM API, security providers are likely to implement KEMs in inconsistent and awkward ways which will make it extremely difficult for applications to use. Since KEM has already been standardized and is well-defined, it's time to treat it as a new kind of cryptographic primitive and provide a dedicated API for it in the Java Platform.

The DHKEM implementation

We will provide an implementation of KEM for the DH-Based KEM algorithm (DHKEM) defined in section 4.1 of RFC 9180: Hybrid Public Key Encryption.

Testing

We will add conformance tests on input, output, and exceptions.

We will ensure that the DHKEM implementation passes the DHKEM Known-Answer Tests in RFC 9180.