JEP draft: ML-KEM Quantum-Resistant Key Encapsulation Mechanism

OwnerWeijun Wang
TypeFeature
ScopeSE
StatusSubmitted
Componentsecurity-libs / javax.crypto
Discussionsecurity dash dev at openjdk dot org
EffortM
DurationS
Reviewed bySean Mullan
Created2024/08/26 18:33
Updated2024/10/29 16:20
Issue8339009

Summary

Enhance the security of the Java Platform by adding support for the quantum-resistant Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM). A key encapsulation mechanism (KEM) can be used by two parties to establish a shared secret over a public channel, which can then be used with symmetric-key cryptographic algorithms to perform basic tasks in secure communications, such as encryption and authentication. ML-KEM is designed to be secure against potential quantum computing attacks, and has been standardized by the National Institute of Standards and Technology (NIST) in their recent publication, FIPS 203.

Goals

Non Goals

Motivation

In recent years, there has been steady advancement in the field of quantum computing. These sophisticated systems operate on principles vastly different from classical computing. The realization of large-scale quantum computers poses a significant threat to the integrity of numerous cryptographic algorithms in use today. The primary risk comes from Shor’s Algorithm, which was created in 1994 and subsequently refined and expanded. This algorithm is capable of factoring integers and solving the discrete logarithm problem, thus compromising the security of public-key based algorithms such as Rivest-Shamir-Adleman (RSA) and Diffie-Hellman. These and other public-key algorithms at risk of being broken are supported by the JDK and used in protocols such as TLS to establish a shared key or to digitally sign artifacts such as a JAR file. An attack that might take supercomputers thousands to millions of years to complete today could be accomplished within hours by a cryptographically relevant quantum computer (CRQC) using Shor's Algorithm.

In 2016, NIST started a public initiative to choose new cryptographic algorithms that can resist quantum computer attacks — a field known as Post-Quantum Cryptography (PQC). After three rounds of evaluation and analysis, the first batch of four algorithms were chosen for the standardization process in August 2023: one for key establishment and three for digital signature. The key establishment algorithm chosen is the Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM) which is derived from the CRYSTALS-Kyber submission. The algorithm is based on polynomial lattices which cannot be defeated by Shor's Algorithm. This algorithm was published in FIPS 203, on August 13, 2024.

In September 2022, the National Security Agency (NSA) published the Commercial National Security Algorithm (CNSA) Suite 2.0 that is specifically designed for protection against a future deployment of a CRQC. CNSA 2.0 lists ML-KEM as the only asymmetric algorithm for key establishment and ML-DSA as the only asymmetric algorithm for digital signatures. Both algorithms are required to be deployed within the 2025-2033 timeframe by all National Security System (NSS) owners/operators.

In order to comply with NIST FIPS 203 and CNSA Suite 2.0 and defend against quantum computers, it is essential for the Java Platform to provide an implementation of ML-KEM.

The urgency of integrating a quantum-resistant key establishment algorithm into the Java Platform is critical due to the "harvest now, decrypt later" risk. Adversaries can currently gather encrypted data to decrypt later with advanced quantum capabilities. NIST and the NSA emphasize this risk, advocating for early adoption of quantum-resistant cryptography. Supporting standards like ML-KEM now allows the Java Platform to protect against future decryption threats and ensure long-term data security.

Description

As described in JEP 452, a KEM consists of three functions:

  1. A key pair generation function that returns a key pair containing a public key and a private key.
  2. A key encapsulation function, called by the sender, that takes the receiver's public key and an encryption option; it returns a secret key K and a key encapsulation message (called ciphertext in ISO 18033-2). The sender sends the key encapsulation message to the receiver.
  3. A key decapsulation function, called by the receiver, that takes the receiver's private key and the received key encapsulation message; it returns the secret key K.

For the first function, we will implement a KeyPairGenerator that generates ML-KEM key pairs. For the second and third functions, we will implement a KEM that negotiates shared secret keys based on an ML-KEM key pair. We will also implement a KeyFactory that converts ML-KEM keys to and from their encodings. These implementations will be added to the SunJCE provider.

In the Java Security Standard Algorithm Names Specification, we will define a new standard algorithm named "ML-KEM" for KeyPairGenerator, KeyFactory, and KEM. We will refer to ML-KEM as the family name in the rest of this proposal.

FIPS 203 specifies three parameter sets for ML-KEM. In order of increasing security strength and decreasing performance, these are "ML-KEM-512", "ML-KEM-768", and "ML-KEM-1024". These names will also be defined as standard algorithm names for KeyPairGenerator, KeyFactory, and KEM. We will refer to these names as parameter set names in the rest of this proposal.

The standardized parameter sets for ML-KEM are also represented by NamedParameterSpec constants with the names ML_KEM_512, ML_KEM_768, and ML_KEM_1024.

NIST Computer Security Objects Register has defined Object Identifiers (OIDs) for these parameter sets (2.16.840.1.101.3.4.4.1 for ML-KEM-512, 2.16.840.1.101.3.4.4.2 for ML-KEM-768, and 2.16.840.1.101.3.4.4.3 for ML-KEM-1024). They will be provided as aliases to the parameter set names.

KeyPairGenerator for ML-KEM

An ML-KEM key pair can be generated in one of the following ways.

First, a KeyPairGenerator can be instantiated with the family name and initialized with a parameter set name:

KeyPairGenerator g = KeyPairGenerator.getInstance("ML-KEM");
g.initialize(NamedParameterSpec.ML_KEM_512);
KeyPair kp = g.generateKeyPair(); // an ML-KEM-512 key pair

Or, if the KeyPairGenerator is not initialized with a parameter set, the JDK implementation will use ML-KEM-768 as the default:

KeyPairGenerator g = KeyPairGenerator.getInstance("ML-KEM");
KeyPair kp = g.generateKeyPair(); // an ML-KEM-768 key pair

Lastly, a KeyPairGenerator can be directly instantiated with a parameter set name:

KeyPairGenerator g = KeyPairGenerator.getInstance("ML-KEM-1024");
KeyPair kp = g.generateKeyPair(); // an ML-KEM-1024 key pair

Initializing a KeyPairGenerator with an integer keysize (instead of a NamedParameterSpec) is not supported and an InvalidParameterException will be thrown.

The keytool command will be enhanced to support generating ML-KEM key pairs and certificates. Here is an example that generates an ML-KEM keypair and signs the certificate with an EC key. The first command creates an EC key pair, and the second command creates an ML-KEM key pair and a certificate signed by the EC key. The reason we use an EC key to sign the certificate is because ML-KEM itself is not a signature algorithm and cannot be used to sign the certificate containing the ML-KEM public key.

keytool -keystore ks -storepass changeit -genkeypair -alias ec \
        -keyalg ec -dname CN=ec -ext bc
keytool -keystore ks -storepass changeit -genkeypair -alias mlkem \
        -keyalg ML-KEM -groupname ML-KEM-768 -dname CN=ML-KEM -signer ec

The parameter set name (ML-KEM-768) can also be provided directly with the -keyalg option:

keytool -keystore ks -storepass changeit -genkeypair -alias mlkem2 \
        -keyalg ML-KEM-768 -dname CN=ML-KEM2 -signer ec

KeyFactory for ML-KEM

The ML-KEM KeyFactory implementation can be used to convert an ML-KEM private key to or from its PKCS #8 encoding, or an ML-KEM public key to or from its X.509 encoding. The encoding follows the formats defined in Internet X.509 Public Key Infrastructure - Algorithm Identifiers for Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM). We will monitor this Internet Draft for any changes until it is published as an RFC.

For example, to convert a ML-KEM private key to its PKCS #8 encoding and vice-versa:

KeyFactory f = KeyFactory.getInstance("ML-KEM");
PKCS8EncodedKeySpec p8spec = f.getKeySpec(kp.getPrivate(),
        PKCS8EncodedKeySpec.class);
PrivateKey sk2 = f.generatePrivate(p8spec);

Similarly, to convert a ML-KEM public key to its X.509 encoding and vice-versa:

X509EncodedKeySpec x509spec = f.getKeySpec(kp.getPublic(),
        X509EncodedKeySpec.class);
PublicKey pk2 = f.generatePublic(x509spec);

The KeyFactory implementation can also translate a key from another provider using the translateKey method as long as its encoding format is supported. This includes "PKCS#8" for private keys and "X.509" for public keys.

The getAlgorithm method of Key objects generated by an ML-KEM KeyPairGenerator or KeyFactory implementation always returns the family name "ML-KEM", regardless of whether the KeyPairGenerator or KeyFactory was instantiated with the "ML-KEM" family name or one of the parameter set names. The getParams() method of the key returns a NamedParameterSpec object that matches the key's parameter set name.

If a KeyFactory object is instantiated with a family name, it encodes or decodes ML-KEM keys in the family with any parameter set. If the object is instantiated with a parameter set name, it only encodes or decodes ML-KEM keys that use this parameter set. Otherwise, the translateKey method will throw an InvalidKeyException, and the generatePrivate, generatePublic, and getKeySpec methods will throw an InvalidKeySpecException.

KEM for ML-KEM

The ML-KEM KEM implementation can be used to negotiate a shared secret key.

For example, the sender calls the encapsulation function and gets a secret key and a key encapsulation message:

KEM ks = KEM.getInstance("ML-KEM");
KEM.Encapsulator enc = ks.newEncapsulator(publicKey);
KEM.Encapsulated encap = enc.encapsulate();
byte[] msg = encap.encapsulation(); // send this to receiver
SecretKey sks = encap.key();

The receiver calls the decapsulation function and recovers the secret key from the key encapsulation message from the sender:

KEM kr = KEM.getInstance("ML-KEM");
KEM.Decapsulator dec = kr.newDecapsulator(privateKey);
SecretKey skr = dec.decapsulate(msg);

Now, both sks and skr contain the same key material, which is known only to the sender and the receiver.

If a KEM object is instantiated with a family name, it accepts ML-KEM keys in the family with any parameter set name. If the object is instantiated with a parameter set name, it only accepts ML-KEM keys that use this parameter set. Otherwise, the newEncapsulator and newDecapsulator methods will throw an InvalidKeyException.

Future Work

ML-KEM used in Transport Layer Security (TLS)

The initial step in a TLS handshake is key agreement, where both parties agree on a shared key. Currently, the most commonly used key agreement mechanisms rely on Diffie–Hellman, which could be compromised by Shor’s algorithm on a future quantum computer. This poses a long-term risk, as any key agreement exchanges stored today could potentially be decrypted in the future, exposing the shared key and compromising the confidentiality of past data communications.

Multiple IETF drafts have been published to resolve this issue. Many use a hybrid approach, combining a quantum-resistant Key Exchange Mechanism (KEM) algorithm with an existing Diffie-Hellman-based key exchange algorithm. Both mechanisms must be compromised to decrypt the key exchange, preserving Diffie-Hellman’s security until quantum computers become a reality. The Hybrid key exchange in TLS 1.3 draft outlines a general hybrid approach, while the Post-quantum hybrid ECDHE-MLKEM Key Agreement for TLSv1.3 draft proposes a specific scheme.

On the other hand, the ML-KEM Post-Quantum Key Agreement for TLS 1.3 draft introduces a new key agreement scheme based entirely on ML-KEM.

Quantum-resistant signature schemes are often less efficient than those based on classical cryptography. To improve on this potential inefficiency, the KEM-based Authentication for TLS 1.3 draft proposes to use KEM instead of a signature scheme during the authentication step of TLS.

We will be closely monitoring these drafts and deciding how best to add TLS support for ML-KEM in future versions of the Java Platform.

Alternatives

The Open Quantum Safe project provides a JNI wrapper for their liboqs C library, covering a collection of PQC algorithms that include both the original CRYSTALS-Kyber algorithm and ML-KEM. If Open Quantum Safe achieves its goal of becoming the primary PQC implementation for major projects such as OpenSSL, BoringSSL, OpenSSH, and Mozilla, it will gain substantial performance and robustness through widespread testing and usage.

However, a Java implementation of ML-KEM provides a key benefit over a native implementation, as it is directly integrated into the JDK. This integration would make it universally available across all Java SE supported environments. Furthermore, by including ML-KEM in the Java Platform, we lay the groundwork that will make it easier to adapt it to other Java technologies, such as Java Card enabled products (smart cards, etc.).

Testing

Testing will include: