M4 / Signatures

Which algorithm for which job

FoundationsPractitionerAdvisor

After this lesson you can

  • Justify why code signing (especially long-lived, non-updatable firmware) is a different algorithm decision from general TLS/PKI, and when stateful hash-based options really make sense

Before thisHQC status and the additional signature candidates in IR 8610

Mental model

From M2 to M4 you have seen four signature families: ML-DSA (lattice, general purpose), SLH-DSA (hash-based, stateless, general purpose but larger), LMS/XMSS (hash-based, stateful, for narrow scenarios), and FN-DSA (lattice, the smallest, but not even a draft yet). In this lesson we turn that list into a decision tree: which family for which job.

The size difference from classical counterparts, in concrete numbers

The goal at the start of this module was to compare PQC signature sizes with their classical counterparts; let us do that now. The classical signatures defined by the still-current FIPS 186-5: an RSA-2048 signature is 256 BDERIVED, an ECDSA-P256 signature 64-72 BDERIVED. Against these, the ML-DSA-65 signature is 3309 BSOURCED (12.93×DERIVED times RSA-2048), and the SLH-DSA-SHA2-128s signature is 7856 BSOURCED (30.69×DERIVED times). The difference is real, but outside narrow scenarios like smart cards and APDUs it is not a practical barrier in most general PKI/TLS infrastructure; the real operational effect is that storage and transmission assumptions must be reviewed in advance (PRACTITIONER/ADVISOR: you will see these two concrete examples in detail in the M9 lessons pq-and-smart-cards and key-ceremony-and-kmip).

General PKI/TLS: the default is simple

For most of the bank’s scenarios (TLS certificates, general e-signatures, API authentication) the default is simple: ML-DSA-65 from the first lesson of M4 (category 3, balanced size and security), or SLH-DSA in scenarios where size is not critical but zero state risk is wanted. FN-DSA is not on this list today, because it does not even have a draft.

Code signing: why it is a different question

Code signing, especially firmware signing, is a different decision. SP 800-208’s own definition of use, which you saw in M2, frames it clearly: stateful hash-based schemes (LMS/XMSS) make sense when three conditions hold together: a signature scheme is needed soon, the deployment is long-lived, and changing the scheme after deployment is impractical. The example NIST itself gives is exactly this: “the authentication of firmware updates for constrained devices… these devices will need to have a secure mechanism for receiving firmware updates, and it may not be practical to change the code for verifying signatures on updates once the devices have been deployed.”

All three conditions rarely hold at once; most bank systems (TLS servers, application servers) can update their software regularly, so the third condition (unchangeability) does not hold, and in these scenarios LMS/XMSS’s state risk is not worth its size advantage. But for a device whose signature verification logic really cannot be changed once deployed (an HSM’s hardware-embedded boot loader, an ATM’s unchangeable firmware, a long-lived IoT device), if you can keep state in hardware (in a non-exportable way), LMS/XMSS’s small signature is a real engineering gain (PRACTITIONER/ADVISOR: you will see a concrete example of this hardware-level state guarantee in M9).

The decision tree, in summary

When you face a signing scenario, ask in order: (1) Does this scenario satisfy all three conditions of SP 800-208 (needed soon, long life, unchangeable)? If not, LMS/XMSS drops off the list. (2) Can you guarantee state in hardware, in a non-exportable way (PRACTITIONER/ADVISOR: the M9 lesson hsm-validation-reality shows how to verify this)? If you cannot, LMS/XMSS drops off again; move to SLH-DSA. (3) For the remaining general scenarios ML-DSA-65 is the default; ML-DSA-44 if size is critical and category 2 really is enough; ML-DSA-87 if the highest assurance is needed. FN-DSA is not an option today on any branch of this tree until FIPS 206 is final.

Numbers to know

  • NIST's own definition of use (SP 800-208 §1.1): stateful hash-based schemes make sense when 3 conditions hold together: (1) a signature scheme is needed soon, (2) the deployment is long-lived, (3) changing the scheme after deployment is impractical; NIST's own example is firmware updates for constrained devices
  • Classical counterparts: RSA-2048 signature 256 B, ECDSA-P256 signature 64-72 B; ML-DSA-65 signature 3309 B (~13 times RSA-2048), SLH-DSA-SHA2-128s signature 7856 B (~31 times). The size difference is real, but as you will see in M9 it is not a practical barrier in most scenarios outside APDU and storage planning

Lab: Test your own scenario against the three conditions

[not run] This is a decision-making exercise, not a runnable command

Requires: . Check your setup

shell
# Take a signing scenario in your organization (TLS certificate, code signing, document signature) and test it against the three conditions of SP 800-208
Recorded output
If all three hold (needed soon + long life + unchangeable), LMS/XMSS is a candidate; if any one does not (especially if it is changeable), SLH-DSA or ML-DSA is the more defensible default

At the table

How to say this in a bank meeting.

To an executive
The bank's signing needs will not be solved by a single algorithm: ML-DSA/SLH-DSA for TLS certificates and general PKI, but for long-lived scenarios where field updates are hard, such as the firmware of hardware security modules or ATMs, LMS/XMSS should be evaluated separately.
To an architect
The decision tree is simple: can the scenario provide controlled, hardware-protected state tracking, as in M9, and is it really long-lived and unchangeable? If yes, LMS/XMSS's small signature is an advantage; if no, the state risk is unnecessary, so move to SLH-DSA (or ML-DSA for general PKI).
Objection
“"Let's have one signature algorithm standard to reduce complexity, and use ML-DSA for everything."”
Answer
That is a correct default for general PKI and TLS, but code signing is a special case: NIST's own SP 800-208 specifically recommended LMS/XMSS for exactly this scenario (long-lived device firmware that cannot be updated in the field), because if the state risk can be controlled in hardware, you gain a much smaller signature (a real constraint on constrained devices). The simplicity of 'one standard everywhere' here means putting the wrong tool on the wrong job.

Sources

Checkpoint

Answer first, then compare with the model answer and score yourself against the rubric. Saved in this browser only.

  1. 01Recall

    According to NIST's own definition of use, when is a stateful hash-based signature (LMS/XMSS) really appropriate?

  2. 02Scenario

    A bank wants to sign the firmware of its ATMs. The devices will stay in the field for 15 years and are designed so the software cannot be updated without changing hardware. Which algorithm family do you recommend, and why?

  3. 03Scenario

    The same bank proposes using the same algorithm for customer TLS certificates too, for consistency. What do you say?

  4. 04Hostile

    An architect says 'Code signing is a signature and a TLS certificate is a signature. Why a different algorithm?' Answer by summarizing all the lessons of M2 and M4.

Project linkThe last row of the algorithm selection matrix in Project 4 (capstone): the decision tree for which signature family to choose by use case (general PKI versus long-lived firmware).