Summary

Add API support for the Leighton-Micali Signature (LMS) system with the Hierarchical Signature System (HSS) as defined in RFC 8554: Leighton-Micali Hash-Based Signatures. Provide a software-based signature verification implementation.

Non Goals

• An API for private key management, including mechanisms for persisting keys and maintaining key states.

• An API for LM-OTS and plain LMS.

• An implementation for key pair and signature generation.

Motivation

The Leighton-Micali Signature system, along with its multi-tree variant, the Hierarchical Signature System (HSS), is a stateful hash-based signature (HBS) scheme. All currently widely used digital signature schemes, including DSA, RSA, ECDSA, and EdDSA, have the potential to be broken if large scale quantum computers are ever built. However, the security of LMS depends only on the security of the underlying hash functions, and it is believed that the security of hash functions will not be broken by the development of large-scale quantum computers.

HSS/LMS is one of the two approved stateful HBS schemes listed in NIST Special Publication 800-208 published in October 2020. The Commercial National Security Algorithm Suite 2.0, published by NSA in September 2022, approves and recommends LMS as a quantum-resistant algorithm for software and firmware signing for National Security Systems.

The base of HSS/LMS is the Leighton-Micali One-Time Signature (LM-OTS) scheme, where a single private key can only be used to sign one message. The LMS signature system stores a large set of LM-OTS public keys as the leaves of a Merkle hash tree, and calculates hash values from the leaves all the way up to the root node. The hash value at the root node is publicized as the long-term public key for the whole tree. When using LM-OTS to sign a message with a private key associated with a leaf, the LM-OTS signature is combined with the node values from the leaf to the root node as the LMS signature, and thus allows the message receiver to verify it with the LMS public key. To further simplify the generation of LMS trees and allow more LM-OTS key pairs to be used, multiple LMS trees can be chained into a hierarchy called an HSS, where each leaf in an LMS tree signs the next level LMS tree in the hierarchy. The hash value of the top level tree will be used as the public key for the whole hierarchy. Because each LM-OTS key pair can be only used once, it's extremely important to remember which leaves are already used in each tree in the hierarchy. This is why this kind of signature system is stateful.

Stateful HBS schemes are not suitable for general use because they require careful state management that is often difficult to ensure. Instead, stateful HBS schemes are primarily intended for applications with the following characteristics:

1) it is necessary to implement a digital signature scheme in the near future; 2) the implementation will have a long lifetime; and 3) it would not be practical to transition to a different digital signature scheme once the implementation has been deployed.

An application that may fit this profile is the authentication of software bundles or updates.

In order to support these use cases, we will provide APIs for all aspects of the HSS/LMS algorithm, including key pair generation, signature generation, and signature verification. This allows a third-party provider to provide full support for the algorithm and ensures that applications are able to call these functions in a consistent manner. However, the builtin security provider inside the JDK will only include the implementation for signature verification. In the Introduction section, NIST SP 800-208 explicitly pointed out that

This recommendation requires that key and signature generation be performed in hardware cryptographic modules that do not allow secret keying material to be exported, even in encrypted form.

Description

In the Java Security Standard Algorithm Names Specification, we will define a new standard algorithm named "HSS/LMS" for Signature, KeyPairGenerator, and KeyFactory.

We will define new APIs for representing HSS/LMS public and private keys, and algorithm parameters for generating those keys with a KeyPairGenerator. These keys can then be used to generate and verify signatures using the HSS/LMS algorithm. No new APIs (ex: algorithm parameters) are specifically needed for Signature.

Key Interfaces

Two new HSS/LMS key APIs will be defined in the java.security.interfaces package. HSSLMSPrivateKey represents an HSS/LMS private key and HSSLMSPublicKey represents an HSS/LMS public key, defined as follows:

public interface HSSLMSPrivateKey extends PrivateKey {
    // Returns parameters for all trees
    LMSSystemParameters[] getParams();
    int keysRemaining();
}

public interface HSSLMSPublicKey extends PublicKey {
    // Returns parameters for the top level tree 
    LMSSystemParameters getParams();
}

An HSSLMSPrivateKey is stateful because it needs to maintain what the next LM-OTS key will be used. The keysRemaining method returns how many LM-OTS keys are available.

The getParams method of HSSLMSPrivateKey returns an array of LMSSystemParameters, each of which describes the parameters of an LMS tree in the HSS hierarchy. The getParams method of HSSLMSPublicKey returns an LMSSystemParameters which describes the top level tree in the HSS hierarchy. The LMSSystemParameters class, also in the java.security package, is a record defined as follows:

// LMS system parameters: LM-OTS parameters and LM parameters of an LMS tree
public record LMSSystemParameters(LMSParameters lmsParams, LMOTSParameters lmOtsParams) {}

// LM-OTS parameters: identifier, width, signature size, number of left-shift bits, hash algorithm
public record LMOTSParameters(int lmOtsAlgorithmType, int n, int w, int p, int ls, String H) {}

// LMS parameters: identifier, height, number of node data, hash algorithm
public record LMSParameters(int lmsAlgorithmType, int h, int m, String H) {}

Users can inspect the parameters of an HSS/LSS key by calling these methods. For example, RFC 8708, Section 5 requires that the digest algorithm and signature algorithm must match each other in a CMS Signed-Data structure. Users can retrieve the H fields from the parameters and compare them with the digest algorithm.

KeyPairGenerator algorithm parameters

A new AlgorithmParameterSpec child class named HSSGenParameterSpec will be defined in the java.security package. This class can be used to initialize an HSS/LMS KeyPairGenerator.

public class HSSGenParameterSpec implements AlgorithmParameterSpec {
    public HSSGenParameterSpec(List<LMSGenParameterSpec> params);
    public List<LMSGenParameterSpec> getLMSGenParameterSpecs();
}

This class contains a list of LMSGenParameterSpec, one for each tree in the hierarchy, which is defined as follows:

public record LMSGenParameterSpec(int lmsAlgorithmType, int lmOtsAlgorithmType) {
    public LMSGenParameterSpec(LMSType type, LMOTSType otsType);
}

The lmsAlgorithmType and lmOtsAlgorithmType parameters are numerical identifiers for the LMS and LM-OTS parameters as defined in RFC 8554. NIST SP 800-208 has proposed more parameters using different hash algorithms. The new parameters can also be found in the IETF draft draft-fluhrer-lms-more-parm-sets.

We deliberately have not included the full LMOTSParameters or LMSParameters information inside LMSGenParameterSpec. Only the security provider can decide what combinations of LMOTSParameters and LMSParameters are supported. Users need to request them using the numerical identifiers. LMOTSParameters and LMSParameters objects for the requested numerical identifiers are then created by the provider and returned by the getParams methods of new key interfaces.

The second constructor of LMSGenParameterSpec uses enum types defined for known parameters in RFC 8554. More enum fields can be added later when they become standardized. These enums, also in the java.security package, are defined as follows:

public enum LMSType {
    LMS_SHA256_M32_H5(5),
    LMS_SHA256_M32_H10(6),
    LMS_SHA256_M32_H15(7),
    LMS_SHA256_M32_H20(8),
    LMS_SHA256_M32_H25(9);

    LMSType(int id);
    public final int getId();
}

public enum LMOTSType {
    LMOTS_SHA256_N32_W1(1),
    LMOTS_SHA256_N32_W2(2),
    LMOTS_SHA256_N32_W4(3),
    LMOTS_SHA256_N32_W8(4);

    LMOTSType(int id);
    public final int getId();
}

An HSS/LMS KeyPairGenerator implementation should support initializing with an HSSGenParameterSpec. It can choose to support a default parameters setting or throw a ProviderException if no default is defined. An implementation can choose to extend HSSGenParameterSpec to include more instructions on how the keypair should be generated, for example, to support advanced features like Distributed Multi-Tree Hash-Based Signatures as described in Section 7 of NIST SP 800-208.

Example

This example shows how to generate an HSS/LMS key pair and use it to generate and verify signatures. This assumes we have implementations that support all these operations from registered security providers.

var ALG = "HSS/LMS";
var msg = "hello, world".getBytes(StandardCharsets.UTF_8);

// --- The key pair generation ---

var g = KeyPairGenerator.getInstance(ALG);
g.initialize(new HSSGenParameterSpec(List.of(
        new LMSGenParameterSpec(LMSType.LMS_SHA256_M32_H5, LMOTSType.LMOTS_SHA256_N32_W1),
        new LMSGenParameterSpec(LMSType.LMS_SHA256_M32_H10, LMOTSType.LMOTS_SHA256_N32_W2))));
var kp = g.generateKeyPair();

var sk = (java.security.interfaces.HSSLMSPrivateKey) kp.getPrivate();
var pk = (java.security.interfaces.HSSLMSPublicKey) kp.getPublic();

System.out.println(pk.getParams());
System.out.println(Arrays.toString(sk.getParams()));

// publicize the public key
byte[] pkEncoded = pk.getEncoded();

// --- The signing side ---

var s = Signature.getInstance(ALG);
s.initSign(sk);
s.update(msg);
var sig = s.sign();

// --- The verification side ---

// Verification provider may be different, so convert encoded public key into a type it supports
var f = KeyFactory.getInstance(ALG);
var keySpec = new X509EncodedKeySpec(pkEncoded);
var pk2 = f.generatePublic(keySpec);

var s2 = Signature.getInstance(ALG);
s2.initVerify(pk2);
s2.update(msg);
System.out.println(s2.verify(sig));

Provider Implementation Notes

This section lists some recommendations for provider implementations of HSS/LMS.

• The implementation should only support the HSS format of public key and signatures, that is to say, the L header of the public key and the Npsk header of the signature must be present, even if it's only for a single tree LMS, where L = 1 and Npsk = 0.

• Besides the parameters defined in RFC 8554, a provider can support extra parameters defined in a future IETF RFC/draft or for private use. In this case, a user can create a LMSGenParameterSpec using the new LMSGenParameterSpec(int lmsAlgorithmType, int lmOtsAlgorithmType) constructor. For parameters defined in RFC 8554, we recommend using the new LMSGenParameterSpec(LMSType type, LMOTSType otstype) constructor, which uses different types for the LMS parameters and the LM-OTS parameters to avoid providing them in the wrong order.

• The object identifier for HSS/LMS is defined in RFC 8708, Section 3 as:

    id-alg-hss-lms-hashsig OBJECT IDENTIFIER ::= { iso(1)
        member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs9(9)
        smime(16) alg(3) 17 }

  A provider is recommended to support the object identifier as an OID alias for the standard name, i.e. "OID.1.2.840.113549.1.9.16.3.17".

The SUN implementation

We will add HSS/LMS implementations of the following APIs to the “SUN” provider:

• A KeyFactory implementation that translates between the X.509 key format and an HSSLMSPublicKey object.
• A Signature implementation that supports signature verification.

Signature generation will not be supported so this implementation will not be chosen when trying to call initSign with a private key. If the SUN provider is specified when instantiating the signature, the initSign method will throw an UnsupportedOperationException.

There is no KeyPairGenerator implementation.

The KeyFactory and Signature implementations on the verification side ensure that the JDK is able to verify an HSS/LMS signature out-of-box. This is sufficient to verify an X.509 certificate or a JAR file signed with HSS/LMS.

Testing

• Functional tests
• Interoperability tests with other implementation(s)
• Known Answer Tests in RFC 8554, Appendix F