xmss: XMSS^MT height-40 keys never return KeyExhausted; signing after exhaustion returns Ok with an invalid signature #1453

Found with AI-assisted static analysis; manually verified by running the PoC and the patch below.

Summary

For the 21 XMSS^MT parameter sets with full_height = 40 (*_40_*, raw OIDs
0x03-05, 0x0b-0d, 0x13-15, 0x1b-1d, 0x23-25, 0x2b-2d, 0x33-35), a signing key
that has used its last index is not detected as exhausted. Every later
sign() returns Ok(..) with a signature that does not verify, instead of
Err(Error::KeyExhausted).

No key material is reused or leaked: the secret seed and PRF key are wiped
after the last valid signature, so this is not an OTS-reuse or forgery issue.
It is a fail-open state-handling bug. A stateful-HBS deployment that relies on
KeyExhausted to rotate keys keeps producing invalid signatures with no error.

Cause

xmss/src/xmss_core.rs, xmssmt_core_sign (commit 72ebaa1):

• After signing at idx == max_idx, the index field is overwritten with the
  0xFF… "exhausted" marker (lines ~190-196).
• On the next call only idx > max_idx is rejected (line ~171).
• For XMSS^MT, index_bytes = ceil(full_height / 8). For full_height = 40
  that is exactly 5 bytes, so the marker 0xFF_FFFF_FFFF equals
  max_idx = 2^40 - 1 and the check never fires.

h=20 (3 bytes) and h=60 (8 bytes) are fine because the marker is larger than
max_idx there, and XMSS (d=1) uses 4 bytes and is fine too. (The XMSS
reference implementation has the same > vs. marker pattern.)

Reproduction

The test sets the imported key's index to max_idx and signs twice. It uses
_192 sets to stay clear of #1442.

//! poc
#![allow(missing_docs, clippy::all)]
use xmss::{KeyPair, SigningKey, XmssMtSha2_40_8_192, XmssMtSha2_20_4_192};

fn run<P: xmss::XmssParameter>(name: &str, idx_len: usize, max: u64) {
    let seed = [7u8; 72];
    let mut kp = KeyPair::<P>::from_seed(&seed).unwrap();
    let vk = kp.verifying_key().clone();
    let mut bytes = kp.signing_key().as_ref().to_vec();
    let be = max.to_be_bytes();
    bytes[4..4 + idx_len].copy_from_slice(&be[8 - idx_len..]);
    let mut sk = SigningKey::<P>::try_from(bytes.as_slice()).unwrap();
    let s1 = sk.sign(b"last").expect("sign at max idx");
    println!("[{name}] sign#1 at idx=max: verify = {:?}", vk.verify(&s1).map(|_| ()));
    println!("[{name}] sk index bytes after #1: {:02x?}", &sk.as_ref()[4..4 + idx_len]);
    match sk.sign(b"after-exhaustion") {
        Err(e) => println!("[{name}] sign#2: Err({e:?})  (expected)"),
        Ok(s2) => println!("[{name}] sign#2: Ok(..) returned after exhaustion! verify = {:?}", vk.verify(&s2).map(|_| ())),
    }
}

#[test]
fn poc_exhaust() {
    run::<XmssMtSha2_20_4_192>("XMSSMT-20/4 (3 idx bytes)", 3, (1u64 << 20) - 1);
    run::<XmssMtSha2_40_8_192>("XMSSMT-40/8 (5 idx bytes)", 5, (1u64 << 40) - 1);
}

Output on master:

[XMSSMT-20/4 (3 idx bytes)] sign#1 at idx=max: verify = Ok(())
[XMSSMT-20/4 (3 idx bytes)] sign#2: Err(KeyExhausted)  (expected)
[XMSSMT-40/8 (5 idx bytes)] sign#1 at idx=max: verify = Ok(())
[XMSSMT-40/8 (5 idx bytes)] sk index bytes after #1: [ff, ff, ff, ff, ff]
[XMSSMT-40/8 (5 idx bytes)] sign#2: Ok(..) returned after exhaustion! verify = Err(..)

Proposed fix

When idx == max_idx, the index alone can't distinguish "last index still
unused" from "exhausted". The secret seed and PRF key are zeroed after the
last signature, so treat that state as exhausted:

diff --git a/xmss/src/xmss_core.rs b/xmss/src/xmss_core.rs
index d626f53..65f2fff 100644
--- a/xmss/src/xmss_core.rs
+++ b/xmss/src/xmss_core.rs
@@ -171,6 +171,16 @@ pub fn xmssmt_core_sign(params: &XmssParams, sk: &mut [u8], m: &[u8]) -> XmssRes
     if idx > max_idx {
         return Err(Error::KeyExhausted);
     }
+    // When `index_bytes * 8 == full_height` (the XMSS^MT h=40 sets) the
+    // all-0xFF exhaustion marker equals `max_idx`, so the index alone cannot
+    // tell "last index still unused" from "exhausted". After the last
+    // signature the secret seed and PRF key are wiped to zero; treat that
+    // state as exhausted.
+    if idx == max_idx
+        && sk[sk_seed_start..sk_prf_start + n].iter().all(|&b| b == 0)
+    {
+        return Err(Error::KeyExhausted);
+    }
 
     // Copy secret values out before mutating sk.
     let mut sk_seed = sk[sk_seed_start..sk_seed_start + n].to_vec();

With this patch the PoC prints sign#2: Err(KeyExhausted) for both sets, and
cargo test -p xmss --release passes (10 tests). An alternative is a separate
exhausted flag outside the index field. Happy to open a PR with the fix and a
regression test for an h=40 set.