JEP draft: ML-DSA Quantum-Resistant Signature Algorithm

OwnerWeijun Wang
TypeFeature
ScopeSE
StatusSubmitted
Componentsecurity-libs / java.security
Discussionsecurity dash dev at openjdk dot org
EffortM
DurationM
Reviewed bySean Mullan
Created2024/08/26 18:34
Updated2024/10/02 18:38
Issue8339010

Summary

Enhance the security of the Java Platform by adding support for the quantum-resistant Module-Lattice-Based Digital Signature Algorithm (ML-DSA). Digital signatures are used to detect unauthorized modifications to data and to authenticate the identity of the signatory. ML-DSA 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 204.

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 Transport Layer Security (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. One of the signature algorithms chosen is the Module-Lattice-Based Digital Signature Algorithm (ML-DSA) which is derived from the CRYSTALS-Dilithium submission. The algorithm is based on polynomial lattices which cannot be defeated by Shor's Algorithm. This algorithm was published in FIPS 204, 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-DSA.

Description

We will provide an implementation of ML-DSA in the Sun provider consisting of a KeyPairGenerator that generates ML-DSA key pairs, a KeyFactory that converts ML-DSA keys to and from their encodings, and a Signature that signs and verifies signatures using an ML-DSA key pair.

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

FIPS 204 specifies three parameter sets for ML-DSA. In order of increasing security strength and decreasing performance, these are "ML-DSA-44", "ML-DSA-65", and "ML-DSA-87". These names will also be defined as standard algorithm names for KeyPairGenerator, KeyFactory, and Signature. We will refer to these names as parameter set names in the rest of this proposal.

The standardized parameter sets for ML-DSA are also represented by NamedParameterSpec constants with the names ML_DSA_44, ML_DSA_65, and ML_DSA_87.

NIST Computer Security Objects Register has defined Object Identifiers (OIDs) for these parameter sets (2.16.840.1.101.3.4.3.17 for ML-DSA-44, 2.16.840.1.101.3.4.3.18 for ML-DSA-65, and 2.16.840.1.101.3.4.3.18 for ML-DSA-87). They will be provided as aliases to the parameter set names.

KeyPairGenerator for ML-DSA

An ML-DSA 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-DSA");
g.initialize(NamedParameterSpec.ML_DSA_44);
KeyPair kp = g.generateKeyPair(); // an ML-DSA-44 key pair

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

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

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

KeyPairGenerator g = KeyPairGenerator.getInstance("ML-DSA-87");
KeyPair kp = g.generateKeyPair(); // an ML-DSA-87 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-DSA key pairs and certificates. For example:

keytool -keystore ks -storepass changeit -genkeypair -alias mldsa \
        -keyalg ML-DSA -groupname ML-DSA-65 -dname CN=ML-DSA

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

keytool -keystore ks -storepass changeit -genkeypair -alias mldsa \
        -keyalg ML-DSA-65 -dname CN=ML-DSA

KeyFactory for ML-DSA

The ML-DSA KeyFactory implementation can be used to convert an ML-DSA private key to or from its PKCS #8 encoding, or an ML-DSA 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 ML-DSA. We will monitor this Internet Draft for any changes until it is published as an RFC.

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

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

Similarly, to convert a ML-DSA 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-DSA KeyPairGenerator or KeyFactory implementation always returns the family name "ML-DSA", regardless of whether the KeyPairGenerator or KeyFactory was instantiated with the "ML-DSA" 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-DSA keys in the family with any parameter set. If the object is instantiated with a parameter set name, it only encodes or decodes ML-DSA 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.

Signature for ML-DSA

The ML-DSA Signature implementation can be used to sign or verify ML-DSA signatures.

For example, to sign a message using a private key:

Signature ss = Signature.getInstance("ML-DSA");
ss.initSign(privateKey);
ss.update(msg);
byte[] sig = ss.sign();

To verify a signature with a public key:

Signature sv = Signature.getInstance("ML-DSA");
sv.initVerify(publicKey);
sv.update(msg);
boolean result = sv.verify(sig);

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

Future Work

TLS employs signatures during the authentication step, where the server typically provides a certificate and a certificate verify message to the client to prove it's the genuine owner of the certificate. Although there are no IETF drafts recommending ML-DSA as a signature scheme, the industry is beginning to explore how it can be supported. A major challenge is that ML-DSA signatures and public keys are significantly larger than those of existing schemes. We are actively monitoring the improvements in this area and deciding how best to add TLS support for ML-DSA in future versions of the Java Platform.

ML-DSA can also be used in Cryptographic Message Syntax (CMS), the format used for signing JAR files. Once a new RFC defines the recommended digest algorithms for various ML-DSA parameter sets, we can incorporate this feature into the JDK's jarsigner tool.

FIPS 204 supports Pre-Hash ML-DSA and allows user to provide an application-specific context string. We may add support for these features in a future JDK release.

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-Dilithium algorithm and ML-DSA. 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-DSA 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-DSA 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: