Chapter 8 — Computer architecture
Lesson map
Lesson 08 published. Map, example, EX015.
flowchart TD
N0["Learning outcomes"]
N1["8.1 Performance features"]
N2["8.2 Side channels"]
N3["8.3 Memory and code size"]
N4["8.4 HSMs and secure elements"]
N5["Synthesis"]
N0 --> N1 --> N2 --> N3 --> N4 --> N5
N5 --> EX["Worked example"]
EX --> Q["Exercise EX015"]
Logical drawing
flowchart LR
N0["Learning outcomes"]
N1["8.1 Performance features"]
N2["8.2 Side channels"]
N3["8.3 Memory and code size"]
N4["8.4 HSMs and secure elements"]
N5["Synthesis"]
N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> Q["EX015"]
[Learning outcomes]
|
v
[8.1 Performance features]
|
v
[8.2 Side channels]
|
v
[8.3 Memory and code size]
|
v
[8.4 HSMs and secure elements]
|
v
[Synthesis]
|
v
[Worked example] --> [Exercise EX015]
Learning outcomes
You will (1) relate algorithm performance to processor features such as vector units and caches; (2) explain timing and power side channels; (3) assess memory and code size on constrained devices; and (4) understand hardware security modules (HSMs) and their migration constraints. It prepares implementation (Chapters 28 and 31) and performance (Chapter 36).
8.1 Performance features
Lattice schemes spend most of their time in polynomial multiplication via the number-theoretic transform and in hashing with SHAKE. Vector instructions (AVX2 on x86, NEON on ARM) parallelize coefficient operations, making ML-KEM very fast on servers. Constrained microcontrollers without vector units are slower but often still acceptable; memory, not speed, is usually the limit there.
For BPA this means the TLS servers will spend more time sending bytes than computing; benchmark results that show ML-KEM key generation faster than X25519 on a server do not carry over to a crane controller.
8.2 Side channels
Execution time, cache access patterns and power draw can reveal secrets if they depend on secret values. The "KyberSlash" findings showed that a division by a constant whose dividend depended on secret data leaked timing in several Kyber implementations (Bernstein et al. 2024). Constant-time coding — no secret-dependent branches, memory indices or variable-time instructions — is a requirement, not an optimization.
The fix in that case was to replace the division with a multiplication and shift that take the same time for every input. Reviews look for the same pattern elsewhere: any branch, table lookup or division whose input depends on a key or a decrypted value. Tools that run code with secret-marked inputs and flag such dependencies help, but they need to be run on the compiled binary, because compilers can reintroduce branches that the source did not have.
8.3 Memory and code size
ML-DSA signing needs several kilobytes of working memory; SLH-DSA signatures are large but keys are tiny; stateful hash-based schemes need non-volatile state that must never roll back. On a gate scanner with 64 KB of RAM, the choice of signature verification algorithm is an architecture decision.
An ML-DSA-44 verifier needs the 1,312-byte public key, the 2,420-byte signature and a working area for the matrix expansion, which some implementations keep small by generating rows on demand. A verifier that fits by recomputing data trades speed for memory, which a scanner verifying one update per month can easily afford. The architecture review records which trade-off was chosen and why.
8.4 HSMs and secure elements
Private keys at BPA's certificate authority live in an HSM. Migration needs HSM firmware that supports ML-DSA and possibly LMS/XMSS with state protection, validated under the relevant certification program. HSM upgrade cycles are often years long — a classic constraint on migration schedules.
BPA's plan therefore asks its HSM vendor three questions now: which post-quantum algorithms the current firmware supports, when certified firmware will be available, and whether existing hardware can be upgraded or must be replaced. The answers set the earliest date for issuing ML-DSA certificates, which in turn constrains every later migration step for authentication.
8.5 Worked example
BPA's crane controllers verify firmware signatures in a bootloader with 32 KB of flash available. ML-DSA-44 verification code and a 1,312-byte public key may fit; an LMS verifier is smaller and needs only hashing, and since only verification happens on the device, LMS's state problem stays at the signing server. The architecture review records both options and their memory budgets.
The decision also depends on how often firmware is signed. LMS keys can sign only a fixed number of messages, for example 2^10 or 2^15, and losing the signer's state can cause key reuse. With a few releases a year, a key with 2^15 signatures will last indefinitely, so the risk sits in the signing server's backup procedure, not in capacity.
8.6 Common errors and limits
- Benchmarking only on servers.
- Assuming a correct implementation is constant-time.
- Forgetting HSM procurement lead times.
Server benchmarks hide the memory limits that decide what fits on a gate scanner or crane controller, so each device class needs its own measurement. A correct implementation can still leak timing, as the KyberSlash case showed, which is why constant-time behaviour is tested separately from known answers. HSM upgrades can take years, so the request goes out before the software work starts, as BPA did with its certificate authority.
Exercises
- EX015 — Side-channel review. Identify the timing risk in
if secret_coeff > q//2: x = slow_path()and propose a fix. Rubric: 3 = identifies branch and gives branch-free alternative. - EX016 — Device fit. Compare ML-DSA-44 and LMS verification for a 32 KB bootloader. Rubric: 3 = memory, state location and standards (FIPS 204, SP 800-208) considered.
Synthesis
Architecture determines speed, memory fit and leakage: lattice schemes are fast with vector units, constant-time code is mandatory, constrained devices shape algorithm choice and HSM cycles shape schedules.
Continue studying — chapter 08 of 50
← Chapter 07 (draft) · Course chapter index · Chapter 09 (draft) →