JEP 496: Quantum-Resistant Module-Lattice-Based Key Encapsulation Mechanism

Summary

Enhance the security of Java applications by providing an implementation of the quantum-resistant Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM). Key encapsulation mechanisms (KEMs) are used to secure symmetric keys over insecure communication channels using public key cryptography. ML-KEM is designed to be secure against future quantum computing attacks. It has been standardized by the United States National Institute of Standards and Technology (NIST) in FIPS 203.

Goals

• Provide ML-KEM implementations of the KeyPairGenerator, KEM, and KeyFactory APIs, with support for the parameter sets ML-KEM-512, ML-KEM-768, and ML-KEM-1024 standardized in FIPS 203.

Non Goals

• It is not a goal to implement the Kyber algorithm, from which ML-KEM was derived. The two algorithms are not interoperable.

• It is not a goal to add support for ML-KEM to components of the Java Platform for which the necessary standards do not yet exist. That is the case for, in particular, the implementation of Transport Layer Security (TLS) in the javax.net.ssl package. We will add such support once the standards do exist.

Motivation

The field of quantum computing has been advancing steadily for years. A future large-scale quantum computer could use Shor’s algorithm, which is capable of factoring integers and solving the discrete logarithm problem, to compromise the security of widely-deployed public-key based algorithms including Rivest-Shamir-Adleman (RSA) and Diffie-Hellman. Such algorithms are used by the Java Platform to, among other things, digitally sign JAR files and establish secure network connections via the Transport Layer Security (TLS) protocol. An attack that a conventional supercomputer might need thousands to millions of years to complete could be accomplished by a quantum computer using Shor's algorithm in mere hours.

Cryptographers have responded to this threat by inventing quantum-resistant cryptographic algorithms, which cannot be defeated by Shor's algorithm. Switching to quantum-resistant algorithms is urgent even though large-scale quantum computers do not yet exist, since an adversary could harvest encrypted data today, store it, and decrypt it once such computers become available.

For the purpose of exchanging keys in a quantum-resistant fashion, NIST standardized the Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM) in FIPS 203. In the United States, government computer systems that handle sensitive information must be upgraded over the next decade to use ML-KEM. It is thus essential for the Java Platform to provide an implementation of this algorithm.

Description

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

• A key pair generation function returns a key pair containing a public key and a private key.

• A key encapsulation function, called by the sender, takes the receiver's public key and an encryption option; it returns a secret key K and a key encapsulation message. The sender sends the key encapsulation message to the receiver.

• A key decapsulation function, called by the receiver, takes the receiver's private key and the received key encapsulation message; it returns the secret key K.

For the first function, we will provide an implementation of the KeyPairGenerator API that generates ML-KEM key pairs. For the second and third functions, we will provide an implementation of the KEM API that negotiates shared secret keys based on an ML-KEM key pair. We will also provide an implementation of the KeyFactory API that converts ML-KEM keys to and from their encodings.

In the Java Security Standard Algorithm Names Specification, we will define a new standard algorithm family name, "ML-KEM", for the KeyPairGenerator, KEM, and KeyFactory APIs.

FIPS 203 specifies three parameter sets for ML-KEM. In order of increasing security strength and decreasing performance, they are named "ML-KEM-512", "ML-KEM-768", and "ML-KEM-1024". These parameter-set names will also be defined as standard algorithm names for the KeyPairGenerator, KEM, and KeyFactory APIs, and, further, will be represented by the new NamedParameterSpec constants ML_KEM_512, ML_KEM_768, and ML_KEM_1024.

Generating ML-KEM key pairs

You can generate an ML-KEM key pair in one of three ways:

• Instantiate a KeyPairGenerator with the family name and initialize it 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

• If you do not initialize the KeyPairGenerator with a parameter set, the 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

• Directly instantiate a KeyPairGenerator with a parameter-set name:

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

The KeyPairGenerator API allows an integer key size to be specified during initialization, but this is not supported for ML-KEM key pairs and will cause an InvalidParameterException to be thrown.

The keytool command will support generating ML-KEM key pairs and certificates. For example, to generate an ML-KEM key pair and sign the certificate with an EC 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 first command creates an EC key pair; the second command creates an ML-KEM key pair and a certificate signed by the EC key. We use an EC key to sign the certificate because ML-KEM itself is not a signature algorithm and thus cannot be used to sign the certificate containing the ML-KEM public key.

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

Encapsulating and decapsulating ML-KEM keys

You can use the ML-KEM KEM implementation to negotiate a shared secret key.

For example, a sender can call the encapsulation function to get 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();

A receiver can then call the decapsulation function to recover the secret key from the key encapsulation message sent by the sender:

byte[] msg = ...;                       // received from sender
KEM kr = KEM.getInstance("ML-KEM");
KEM.Decapsulator dec = kr.newDecapsulator(privateKey);
SecretKey skr = dec.decapsulate(msg);

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. If it is instantiated with a parameter-set name, it only accepts ML-KEM keys that use that parameter set; otherwise, the newEncapsulator and newDecapsulator methods throw an InvalidKeyException.

Encoding and decoding ML-KEM keys

You can use the ML-KEM KeyFactory implementation 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.

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 security provider using the translateKey method, as long as its encoding format is supported.

The getAlgorithm method of a Key object 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 an ML-KEM 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 it is instantiated with a parameter-set name, it only encodes or decodes ML-KEM keys that use that parameter set; otherwise, the translateKey method throws an InvalidKeyException, and the generatePrivate, generatePublic, and getKeySpec methods throw an InvalidKeySpecException.

The encoding used by the ML-KEM KeyFactory is defined in a draft IETF RFC. We will track changes in this draft until it is published.

Alternatives

• The Open Quantum Safe project provides a JNI wrapper for their liboqs C library, which implements a collection of quantum-resistant algorithms including Kyber and ML-KEM. If Open Quantum Safe achieves its goal of becoming the primary quantum-resistant cryptography implementation for major projects such as OpenSSL, BoringSSL, OpenSSH, and Mozilla, then it will gain substantial performance and robustness through widespread testing and usage.

  Compared to a native implementation, a Java implementation of ML-KEM provides the key benefit of being integrated directly into the JDK. This makes it immediately available on all of the platforms to which the JDK is already ported.

Testing

• Unit tests will confirm that the implementations comply with the specifications of the KeyGenerator, KeyFactory, and KEM APIs, 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. These will include but not be limited to:

  • KATs (here and here) generated by NIST's Cryptographic Algorithm Validation Program service, and

  • The ML-KEM tests from Project Wycheproof, which are are in development.

• Interoperation tests with implementations from other vendors, including but not limited to liboqs, will confirm that our ML-KEM implementation works well with others.