LMS: first signature per LMSPrivateKeyParameters instance rebuilds the whole Merkle tree (~keygen cost); getEncoded() omits the tree cache so every rehydration pays it again

[Arpan0995]

Summary

For LMS (org.bouncycastle.pqc.crypto.lms), the first signature made with any
LMSPrivateKeyParameters instance rebuilds the entire Merkle tree, costing
roughly as much as key generation. Because LMSPrivateKeyParameters.getEncoded()
does not serialize the tree cache (tCache), a key restored from its PKCS#8/raw
encoding pays this full rebuild again on its next signature. Steady-state
signatures on a warm instance are ~500x faster.

This makes any signing service that reloads an LMS key per request (or per small
batch) — a common pattern for stateful HBS, where operators persist advancing
state to shared storage after each use — pay a keygen-equivalent cost on every
reload. The cost scales as O(2^h), so at production tree heights it is seconds to
minutes per cold signature.

Environment

• Bouncy Castle bcprov-jdk18on 1.85 (also present in earlier 1.8x)
• JDK 24 (Corretto), Apple Silicon macOS; reproduced with the provider jar alone

Reproduction

Standalone, single-jar repro (also at
https://github.com/Arpan0995/pqc-hbs-state-management/blob/main/docs/lms-tree-rebuild-repro/LmsTreeRebuildRepro.java):

import org.bouncycastle.jce.provider.BouncyCastleProvider;
import org.bouncycastle.pqc.crypto.lms.LMOtsParameters;
import org.bouncycastle.pqc.crypto.lms.LMSigParameters;
import org.bouncycastle.pqc.jcajce.spec.LMSKeyGenParameterSpec;
import java.security.*;
import java.security.spec.PKCS8EncodedKeySpec;

public class LmsTreeRebuildRepro {
    public static void main(String[] args) throws Exception {
        Security.addProvider(new BouncyCastleProvider());
        System.out.println("trial, keygen_ms, sign1_ms, sign2_ms, sign3_ms");
        for (int t = 0; t < 6; t++) {
            long a = System.nanoTime();
            KeyPair kp = freshKey();               double keygen = ms(a);
            a = System.nanoTime(); sign(kp.getPrivate()); double s1 = ms(a);
            a = System.nanoTime(); sign(kp.getPrivate()); double s2 = ms(a);
            a = System.nanoTime(); sign(kp.getPrivate()); double s3 = ms(a);
            System.out.printf("%d, %8.1f, %8.1f, %8.3f, %8.3f%n", t, keygen, s1, s2, s3);
        }
        System.out.println("\ntrial, decode_ms, sign1_ms, sign2_ms");
        for (int t = 0; t < 6; t++) {
            KeyPair kp = freshKey(); sign(kp.getPrivate());
            byte[] enc = kp.getPrivate().getEncoded();
            long a = System.nanoTime();
            PrivateKey dec = KeyFactory.getInstance("LMS","BC")
                    .generatePrivate(new PKCS8EncodedKeySpec(enc));  double decode = ms(a);
            a = System.nanoTime(); sign(dec); double s1 = ms(a);
            a = System.nanoTime(); sign(dec); double s2 = ms(a);
            System.out.printf("%d, %8.3f, %8.1f, %8.3f%n", t, decode, s1, s2);
        }
    }
    static KeyPair freshKey() throws Exception {
        KeyPairGenerator kpg = KeyPairGenerator.getInstance("LMS","BC");
        kpg.initialize(new LMSKeyGenParameterSpec(
                LMSigParameters.lms_sha256_n32_h10, LMOtsParameters.sha256_n32_w4));
        return kpg.generateKeyPair();
    }
    static void sign(PrivateKey k) throws Exception {
        Signature s = Signature.getInstance("LMS","BC");
        s.initSign(k); s.update("m".getBytes()); s.sign();
    }
    static double ms(long t) { return (System.nanoTime()-t)/1e6; }
}

Run: java -cp bcprov-jdk18on-1.85.jar LmsTreeRebuildRepro.java

Observed (6 trials each, milliseconds)

fresh key:   keygen ~217   sign#1 ~217   sign#2 ~0.40   sign#3 ~0.14
decoded key: decode ~0.09  sign#1 ~217   sign#2 ~0.37

So the ~217 ms tree build is paid on the first signature of every
LMSPrivateKeyParameters object: once after key generation, and once after
every decode. Decode itself is cheap; the cost is entirely in the first sign.

Root cause

• LMSPrivateKeyParameters.getEncoded() serializes only
  version, type, ots type, I, q, maxQ, masterSecret — the tCache
  (private final Map<CacheKey, byte[]> tCache) is not included.
• On first use, findT(int) → calcT(int) recomputes the authentication-path
  nodes, which for the top of the tree covers ~2^h leaves (i.e. ~the whole
  tree), each requiring an LM-OTS public-key evaluation.
• The tree computed during key generation is likewise not reused by the signer,
  so even a freshly generated key pays the rebuild on its first signature.

Expected / suggested fix

Any of, in rough order of value:

1. Reuse the tree built at key generation for the first signature, so a
   freshly generated key does not recompute it.
2. Include the cached tree (or the top-of-tree nodes) in getEncoded() so a
   rehydrated key can restore the cache instead of rebuilding. The private-key
   encoding is already BC-proprietary ("there is no formal specification for the
   encoding of private keys"), so this is backward-compatible to extend behind a
   version tag. XMSS's getEncoded() already serializes its BDS traversal state,
   which is why XMSS does not exhibit this (its rehydration is a one-time ~19 ms,
   not a per-first-sign ~217 ms).
3. At minimum, document that LMS keys should be kept warm for the lifetime of
   a signing process and not rehydrated per signature.

Happy to test a patch against the repro above.