Chapter 19 — Identity and cryptography

Chapter 19 — Identity and cryptography

Lesson map

Lesson 19 published. Map, example, EX037.

flowchart TD
  N0["Learning outcomes"]
  N1["19.1 Signatures and PKI"]
  N2["19.2 Hash-based signatures from first principles"]
  N3["19.3 Practical activity — Lab L"]
  N4["19.4 The standardized options"]
  N5["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5
  N5 --> EX["Worked example"]
  EX --> Q["Exercise EX037"]

Logical drawing

flowchart LR
  N0["Learning outcomes"]
  N1["19.1 Signatures and PKI"]
  N2["19.2 Hash-based signatures from first principles"]
  N3["19.3 Practical activity — Lab L"]
  N4["19.4 The standardized options"]
  N5["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> Q["EX037"]

[Learning outcomes]
    |
    v
[19.1 Signatures and PKI]
    |
    v
[19.2 Hash-based signatures from first principles]
    |
    v
[19.3 Practical activity — Lab L]
    |
    v
[19.4 The standardized options]
    |
    v
[Synthesis]
    |
    v
[Worked example] --> [Exercise EX037]

Learning outcomes

You will (1) explain digital signatures, certificates and PKI hierarchies; (2) understand one-time and many-time hash-based signatures; (3) compare ML-DSA, SLH-DSA, LMS/XMSS and the forthcoming FN-DSA; and (4) plan PKI migration including roots and long-lived signatures. It closes the foundations stage.

19.1 Signatures and PKI

A signature binds a message to a key; a certificate binds a key to an identity, signed by a certificate authority (CA); a chain leads to a root trusted by relying parties. Roots often live 20+ years, so a root key that a future CRQC could forge undermines every certificate beneath it.

Leaf certificates last about a year and are replaced routinely, so their algorithm can change at the next renewal. The root is different: relying parties must receive and trust a new root before any certificate it issues is accepted, which takes years for partners and devices. That is why BPA creates its post-quantum root first.

19.2 Hash-based signatures from first principles

A Lamport one-time signature publishes hashes of two random secrets per message-digest bit and reveals one secret per bit when signing. Security needs only a one-way hash. Using a key twice reveals both secrets at many positions, cutting the forger's work sharply; a few more uses make forgery practical. Merkle trees combine many one-time keys under one public key; LMS and XMSS (RFC 8554, RFC 8391, SP 800-208) do this statefully; SLH-DSA (FIPS 205) avoids state by using a hypertree with few-time signatures at the leaves, at the cost of larger signatures.

19.3 Practical activity — Lab L

# Lab L (ch 19): Lamport one-time signatures from SHA-256 - the idea under SLH-DSA, LMS and XMSS.
import hashlib, secrets
H = lambda b: hashlib.sha256(b).digest()
def keygen(bits=256):
    sk = [(secrets.token_bytes(32), secrets.token_bytes(32)) for _ in range(bits)]
    pk = [(H(a), H(b)) for a, b in sk]
    return sk, pk
def bits_of(msg):
    d = int.from_bytes(H(msg), "big"); return [(d >> (255 - i)) & 1 for i in range(256)]
def sign(sk, msg): return [sk[i][b] for i, b in enumerate(bits_of(msg))]
def verify(pk, msg, sig): return all(H(s) == pk[i][b] for i, (s, b) in enumerate(zip(sig, bits_of(msg))))
sk, pk = keygen()
s1 = sign(sk, b"firmware v1.0")
print("valid signature verifies:", verify(pk, b"firmware v1.0", s1))
print("tampered message rejected:", not verify(pk, b"firmware v1.1", s1))
s2 = sign(sk, b"firmware v1.1")          # KEY REUSE: never do this
revealed = sum(1 for i in range(256) if bits_of(b"firmware v1.0")[i] != bits_of(b"firmware v1.1")[i])
print(f"after one reuse, both secrets revealed at {revealed}/256 positions -> forging needs ~2^{256 - revealed} hashes, not 2^256")
print("signature size:", 256 * 32, "bytes; public key:", 2 * 256 * 32, "bytes")

Expected output:

valid signature verifies: True
tampered message rejected: True
after one reuse, both secrets revealed at 118/256 positions -> forging needs ~2^138 hashes, not 2^256
signature size: 8192 bytes; public key: 16384 bytes

The output shows both the scheme's strength and its fragility. A valid signature verifies and a changed message fails, using nothing but SHA-256. After one reuse, the two digests differ at 118 positions, where both secrets are now public; a forger needs a message whose digest matches the 138 remaining positions, about 2^138 hashes. Each further reuse halves the unknown positions on average, so after three signatures roughly 64 remain, within reach of large computations. The sizes, 8 KB per signature, explain why practical schemes compress Lamport keys with Winternitz chains and Merkle trees.

19.4 The standardized options

For BPA the table points to ML-DSA for general signing, LMS for firmware where state can be managed, and SLH-DSA where the signature size matters less than conservative assumptions. FN-DSA is noted for future use once FIPS 206 is final, since its small signatures suit constrained links. The choice for each use is recorded with the size figures from the table so later reviewers can check them.

19.5 Worked example

BPA's PKI plan: a new ML-DSA-87 root (or a composite traditional+PQC root, depending on relying-party support) created now and distributed; intermediates migrated over the next certificate cycle; LMS for firmware signing with HSM-protected state; SLH-DSA considered for a rarely used offline root because of its conservative assumption.

Distributing the new root takes time, so it is created before the intermediates need it; a root created in the first year can be in partners' trust stores by the time leaf certificates migrate. The offline root signs rarely, so SLH-DSA's large signatures matter little, while its reliance on hashes alone gives assurance if lattice schemes are weakened.

19.6 Common errors and limits

• Reusing one-time or stateful keys (state rollback after a backup restore is a classic failure).
• Migrating leaf certificates while leaving a vulnerable long-lived root.
• Quoting FN-DSA as a final standard.

Restoring a signing server from backup can reset the LMS counter, so the same one-time key signs two messages, exactly the reuse Lab L shows; BPA's HSM keeps the state and refuses to roll back. A post-quantum leaf under an RSA root still fails if the root can be forged. FN-DSA should be planned for, not deployed, until its standard is final.

Exercises

• EX037 — Lamport reuse. Explain from Lab L why signing two messages with one key enables forgery. Rubric: 3 = revealed-secret argument correct.
• EX038 — Scheme selection. Choose a signature scheme for (a) TLS server certificates, (b) crane firmware, (c) an offline root used twice a year. Rubric: 3 = ML-DSA; LMS/XMSS or ML-DSA with reasons; SLH-DSA or ML-DSA with reasons.

Synthesis

Signatures and PKI carry long-lived trust; hash-based schemes are conservative and either stateful or large; ML-DSA is the general-purpose choice; roots must migrate first.

Continue studying — chapter 19 of 50

← Chapter 18 (draft) · Course chapter index · Chapter 20 (draft) →