JEP draft: ML-KEM Quantum-Resistant Key Encapsulation Mechanism
Owner | Weijun Wang |
Type | Feature |
Scope | SE |
Status | Submitted |
Component | security-libs / javax.crypto |
Discussion | security dash dev at openjdk dot org |
Effort | M |
Duration | S |
Reviewed by | Sean Mullan |
Created | 2024/08/26 18:33 |
Updated | 2024/10/02 18:38 |
Issue | 8339009 |
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
- Provide Java implementations of
KeyPairGenerator
,KeyFactory
, andKEM
for the ML-KEM algorithm and add support for the three standardized parameter sets ML-KEM-512, ML-KEM-768, and ML-KEM-1024 as defined in FIPS 203.
Non Goals
- It is not a goal to support the CRYSTALS-Kyber algorithm. While ML-KEM is derived from CRYSTALS-Kyber, NIST has made modifications and the two algorithms are not interoperable.
- It is not a goal to add support for ML-KEM in other components of the Java Platform, for example, in Transport Layer Security (TLS) key exchange mechanisms. These will be addressed in future enhancements. See the Future Work section for more details.
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:
- A key pair generation function that returns a key pair containing a public key and a private key.
- 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.
- 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:
- Unit tests that confirm the implementations comply with the specifications of
KeyGenerator
,KeyFactory
, andKEM
, including edge cases such as invalid input parameters, boundary values, and unsupported operations. - Known Answer Tests (KATs) will cover both valid cryptographic operations
(positive cases) and invalid operations or known vulnerabilities (negative cases),
ensuring comprehensive validation, including but not limited to:
- KATs (here et al) generated by NIST's Cryptographic Algorithm Validation Program (CAVP) service.
- Project Wycheproof. The ML-KEM tests are in development.
- Interop tests with other vendors, both Java and non-Java, including but not limited to
liboqs
.