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](https://www.rfc-editor.org/rfc/rfc8554.html).
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](https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-208.pdf)
published in October 2020. The
[Commercial National Security Algorithm Suite 2.0](https://media.defense.gov/2022/Sep/07/2003071834/-1/-1/0/CSA_CNSA_2.0_ALGORITHMS_.PDF),
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](https://docs.oracle.com/en/java/javase/19/docs/specs/security/standard-names.html),
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](https://www.rfc-editor.org/rfc/rfc8708.html#name-signed-data-conventions)
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](https://datatracker.ietf.org/doc/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](https://www.rfc-editor.org/rfc/rfc8708.html#name-algorithm-identifiers-and-p)
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](https://www.rfc-editor.org/rfc/rfc8554.html#appendix-F)