ML-DSA on a Cortex-M33: From 140 ms to 27 ms, One Table at a Time

TL;DR

I needed post-quantum signatures (ML-DSA, FIPS 204) on an STM32U5A5, a Cortex-M33 at 160 MHz. I started from mldsa-native, a portable, formally verified C implementation, in its low-stack configuration. From there, ML-DSA-65 signing went from 22.4 M cycles (140 ms) to 4.4 M cycles (27 ms) and verification from 3.9 M to 0.45 M cycles. That’s 5.1× and 8.6× faster, and every signature is still byte-for-byte identical to upstream’s. The price is about 11 KB more flash and 46 KB of RAM per loaded key pair. Most of the gain didn’t come from clever assembly. It came from noticing which work never changes between calls, computing it once, and then keeping the result small.

This post walks through every step, including the ones that made things slower.

ML-DSA-65, CPU cycles from flash	upstream (REDUCE_RAM)	now
sign (internal function)	22,355,909	4,387,990	5.1×
verify	3,901,006	454,391	8.6×
keypair	3,839,196	3,082,302	1.25×
signing stack (internal function)	13.1 KB	14.6 KB
RAM per loaded key pair	0	46.8 KB
library flash	11.5 KB	22.6 KB

The Setting

The device is a test fixture: an STM32U5A5 (NUCLEO-U5A5ZJ-Q) sits between a device under test and a Raspberry Pi. It will need to verify its own firmware updates and sign what it reports. That makes two long-lived keys: a public key that update images are signed with, and a key pair of the fixture’s own. P-256 ECDSA on this board is covered (the U5A5 even has a PKA peripheral for it). For anything meant to outlive the coming decade, though, the post-quantum standard is ML-DSA.

The constraints are the usual embedded ones, plus a few house rules:

• No heap. Everything is static or on a FreeRTOS task stack.
• Hardening is not negotiable. -ftrivial-auto-var-init=zero and -fstack-protector-strong stay on everywhere, unaligned accesses trap, and so do divisions by zero.
• Flash matters. A future target in the same product line has 1 MB of flash.
• Correctness is checked, not assumed. Known answers, Wycheproof vectors, and byte-for-byte comparison against upstream.

Starting Point: mldsa-native

mldsa-native is a good place to start. It’s plain C11, proven memory-safe and type-safe with CBMC, its native backends for x86-64 and AArch64 are proven correct with HOL Light, and it has a configuration header for just about everything. Its native backends are for AArch64, x86-64 and RV32IM, so on a Cortex-M33 everything runs as portable C.

Here is what the plain build costs on the board, with code running from SRAM:

	keypair	sign	verify	stack sign
ML-DSA-44, -Os	2.48 M	8.02 M	2.60 M	53 KB
ML-DSA-65, -Os	4.27 M	11.70 M	4.31 M	79 KB
ML-DSA-87, -Os	7.26 M	13.98 M	7.31 M	112 KB

The speed is fine. The stack is not: 79 KB for one signature doesn’t belong on a task stack. mldsa-native has an answer for that, MLD_CONFIG_REDUCE_RAM:

operation	ML-DSA-44	ML-DSA-65	ML-DSA-87
sign	53 → 11 KB	79 → 13 KB	112 → 15 KB
verify	30 → 11 KB	47 → 12 KB	74 → 15 KB
keypair	32 → 14 KB	51 → 17 KB	80 → 21 KB

It leaves keypair and verify within 1% of their speed, but signing gets 1.9 to 2.3 times slower. To see why, you need a rough picture of what ML-DSA signing does.

ML-DSA in One Screen

Everything lives in the ring \(R_q = \mathbb{Z}_q[X]/(X^{256}+1)\) with \(q = 8{,}380{,}417\), a prime just below \(2^{23}\). A key pair has a public matrix \(A \in R_q^{k \times \ell}\) (k = 6, ℓ = 5 for ML-DSA-65). \(A\) is never stored: it is expanded from a 32-byte seed \(\rho\) with SHAKE128. The secret key holds short vectors \(s_1, s_2\), and the public key holds \(t_1\), the high bits of \(t = A s_1 + s_2\).

Signing is rejection sampling. Each attempt:

1. draws a mask \(y\) (SHAKE256),
2. computes \(w = A y\) and hashes its high bits into a challenge \(c\) (a sparse polynomial with ±1 coefficients),
3. computes \(z = y + c s_1\) and checks it against \(s_2\) and \(t_0\),
4. if any norm check fails, throws everything away and tries again.

At ML-DSA-65 that takes 5.1 attempts on average. Polynomial products go through the NTT, the number-theoretic version of an FFT, so \(A\), \(s_1\), \(s_2\) and \(t_0\) are used in their NTT form \(\hat{A}, \hat{s}_1, \ldots\).

The default build keeps \(\hat{A}\) and the NTTs of the secret vectors around for the whole signature, which is where the 79 KB of stack goes. REDUCE_RAM keeps none of it: it re-samples each entry of \(A\) when it needs it and recomputes the NTTs of \(s_1, s_2, t_0\) in every attempt. That’s a clean time-for-memory trade, and it’s the configuration I started from.

Things That Didn’t Help

Before optimizing anything, I built every combination of options I could think of as its own benchmark image: 25 variants at first, each checked against upstream’s known answers, timed on the board and profiled under QEMU. A few results were surprising.

• -O2 and -O3 are slower than -Os. -O2 is 5 to 11% slower and 2.4 KB larger. QEMU’s instruction counts agree, so it isn’t the instruction fetch. The profiler found the cause: at -O2 the Keccak permutation takes 15,532 instructions instead of 13,128 (+18%), and Keccak is half of a signature.
• A single compilation unit gains nothing. LTO already sees the whole library: same cycles, within 70 bytes.
• The API-exclusion options save no flash. --gc-sections and LTO already drop what isn’t called. The options document intent; they don’t shrink anything.
• The project’s hardening costs 1.3 to 1.6% of time. That’s cheap enough to stop thinking about.
• The 4-way Keccak goes. mldsa-native can hash four streams at once, which pays off with SIMD. On a core without it, the four streams are four plain permutations that cost more stack. Going fully serial (MLD_CONFIG_SERIAL_FIPS202_ONLY) was free in time and saved 3 to 6 KB of stack and 1 KB of flash. Its one consumer, an MVE backend for the Cortex-M55, only showed up in QEMU instruction counts on a core the product doesn’t use. So it was dropped for good.

Where the Time Goes

Measuring beats guessing, so I wrote a small QEMU TCG plugin that counts instructions per function under a chosen root function. For ML-DSA-44 signing with REDUCE_RAM it said: Keccak-f[1600] is 62% of the instructions, at 13,128 instructions per permutation and 212.7 permutations per signature. Verification of ML-DSA-87 was 70% Keccak. Before anything else, the hash had to get faster.

Keccak on a 32-Bit Core

Keccak’s state is 25 lanes of 64 bits, and its θ, ρ and ι steps rotate those lanes. A 64-bit rotation on a 32-bit core is four instructions (two shifts and two ORs, using the barrel shifter), and Keccak does a lot of them.

The standard trick, used by XKCP and every fast Cortex-M Keccak, is bit interleaving. Store each lane not as its low and high halves but as its even-numbered bits \(E\) and its odd-numbered bits \(O\). A rotation of the lane by \(r\) then becomes:

\[\mathrm{rot}_{64}(L, r) \;\Rightarrow\; \begin{cases} E' = \mathrm{rot}_{32}(E, s),\ \ O' = \mathrm{rot}_{32}(O, s) & r = 2s \\ E' = \mathrm{rot}_{32}(O, s+1),\ \ O' = \mathrm{rot}_{32}(E, s) & r = 2s+1 \end{cases}\]

Two 32-bit rotations, and on Arm a 32-bit rotation is usually free, because it folds into the operand of whatever instruction consumes the value (eor r0, r1, r2, ror #7).

Attempt 1: plug it in behind mldsa-native’s permutation hook. mldsa-native has a hook for a native x1 permutation, so I put XKCP’s portable C in-place rounds behind it. mldsa-native keeps the state as plain 64-bit lanes, so each call interleaves the 25 lanes, runs 24 rounds, and converts back. Result: 7 to 11% slower. The rounds themselves were 13% cheaper than upstream’s, but converting the whole state twice per permutation cost about 2,000 instructions. Forcing the conversion helpers inline saved only 326 of those, because the conversion is real shift-and-mask work, not call overhead.

Attempt 2: keep the state interleaved. mldsa-native documents an interface for replacing its entire FIPS 202 layer. With that, the SHAKE context itself holds the state as 50 interleaved uint32_t words for its whole life. Absorbing interleaves the incoming bytes, squeezing de-interleaves only the bytes requested, and the permutation never converts anything. The conversion moved to the boundary: a squeezed block costs 982 instructions instead of 738, but ML-DSA permutes far more often than it squeezes, so overall it came out ahead. Getting the boundary code right took a few rounds:

• splitting partial lanes from whole lanes,
• XORing SHAKE’s padding straight into the interleaved words (byte \(j\) of a lane puts its even bits at bits \(4j..4j{+}3\) of \(E\) and its odd bits at the same place in \(O\)),
• loading whole aligned words with memcpy from __builtin_assume_aligned, which stays within the aliasing rules,
• falling back to bytes otherwise, since unaligned word accesses trap on this board.

Attempt 3: better rounds. I tried three variants on top of the persistent state:

variant (QEMU instructions per permutation)	rounds
upstream C	13,128
XKCP in-place C	11,421
+ early parity (generated)	12,165
+ lazy rotation (generated)	10,575
Adomnicăi’s ARMv7-M assembly	9,163

Early parity accumulates the next round’s column parities while writing outputs. In C it lost: GCC can’t keep ten extra accumulators in registers, so it spills them. Lazy rotation is the trick from Adomnicăi’s assembly (TCHES 2024), done in C by a generator script. Every value carries a rotation that’s known at generation time instead of being applied, so χ’s (~a) & b becomes a single bic with a rotated operand rather than mvn plus and. It cut 141 instructions per four rounds. The assembly is still better, because it keeps in registers what GCC spills.

Instruction Counts Lie a Little

On the board the picture shrank. From SRAM, ML-DSA-44 verify runs at 1.29 cycles per instruction with upstream’s Keccak, but at 1.40 to 1.51 with the interleaved variants: they are load- and store-heavy, and code fetched from SRAM shares the bus with its own data. The assembly’s 18% fewer instructions turned into 5% fewer cycles.

Running from flash, as firmware does, through the instruction cache, the gains roughly doubled again. The benchmarks had been running from SRAM to avoid wearing out flash, so I built a second flash image holding every benchmark variant as a selectable entry. Fitting 53 variants into it took some deduplication. The assembly files are now emitted as COMDAT groups, so the linker keeps one copy of the Keccak and NTT code instead of 27 and 11. That took the image from 1.1 MB to 482 KB. From flash, the persistent state with the assembly rounds is 8 to 13% faster than upstream. A respectable win, but not a game changer.

The Real Win: Stop Recomputing Things

Look at the signing algorithm again with long-lived keys in mind. For a given key, these are the same on every call:

• \(\hat{A}\), sampled from \(\rho\) with SHAKE128 (most of verification’s Keccak work: about 280 of 312 permutations at ML-DSA-87),
• \(tr = H(pk)\), a hash of the whole 1.3–2.6 KB public key,
• \(\hat{s}_1, \hat{s}_2, \hat{t}_0\), which REDUCE_RAM recomputes in every single attempt,
• \(\widehat{t_1 \cdot 2^d}\) for verification.

So compute them once, into expanded keys: plain C structs in static RAM.

typedef struct {
    uint32_t magic;
    uint32_t digest;          /* XXH32 of everything below, see later */
    uint8_t  tr[64];
    uint32_t a[K][L][192];    /* A-hat, packed 24 bits per coefficient (see the end) */
    int32_t  t1hat[K][256];   /* NTT(t1 * 2^d) */
} voltsoft_mldsa_expanded_public_key;

typedef struct {
    uint32_t magic;
    uint8_t  key[32];
    uint8_t  tr[64];
    int32_t  s1hat[L][256], s2hat[K][256], t0hat[K][256];
} voltsoft_mldsa_expanded_secret_key;

The signing, verification and key-generation code that uses them follows mldsa-native’s step for step, calling its own helpers, so the output is identical. The tests check exactly that: every Wycheproof sample vector, plus random messages, contexts and rnd values at all three parameter sets, must produce a signature equal to upstream’s byte for byte. The whole Wycheproof corpus also runs through the expanded verifier on the host.

Since this is a fork of upstream logic, it needs a guard against upstream changing underneath it. CMake hashes the upstream sources and headers the fork follows, including the headers that define the NTT bounds its arithmetic relies on, and refuses to configure when they change, until someone has re-reviewed the fork and updated the digest. A submodule bump can’t silently leave the fork behind.

Storing Keys: 32 Bytes, Not 46 KB

The tables are big, so they are never stored. A key pair is stored as its 32-byte seed \(\xi\); FIPS 204 derives everything from it. Loading runs key generation and expansion in one pass: \(\hat{A}\) is sampled once, straight into the table, \(t\) is computed row by row, and \(tr\) is hashed while the public key’s bytes are being formed. Neither the packed secret key nor the public key ever exists in memory. Loading costs 3.26 M cycles (20 ms) at ML-DSA-65, 6% more than plain key generation, and 2.6 to 6.7 KB less stack.

flowchart LR
    seed["seed ξ (32 bytes, flash)"] -->|"expand_key_pair: 3.3 M cycles, once"| tables["expanded keys (RAM)"]
    pk["encoded public key (1,952 bytes, flash)"] -->|"expand_public_key: 2.5 M cycles"| tables
    tables -->|"4.4 M cycles"| sign[sign]
    tables -->|"0.45 M cycles"| verify[verify]

When does expanding pay off?

• Signing pays from the first signature. Without expanded keys, ML-DSA-65 signs in 16.9 M cycles. Loading plus one signature costs 3.26 M + 4.39 M.
• Verification pays clearly from the second. At ML-DSA-87, verifying straight from the encoded public key costs 5.26 M cycles every time. Expanding the public key costs 4.49 M cycles once, after which each verification costs 0.60 M. One verification: 4.49 M + 0.60 M = 5.09 M against 5.26 M, only 3% less. Two: 5.69 M against 10.52 M, 46% less, and each one after that saves another 4.66 M. A key verified once per boot, such as an OTA key checking one update, isn’t worth about 50 KB of RAM for 3%, so verify that one directly. (These figures are from flash, measured before this week’s packing of \(\hat{A}\), which made verification 1 to 5% slower.)

The NTT Is Next

Expanded keys took most of the hashing out of signing. In the REDUCE_RAM build, every attempt re-sampled all 30 entries of \(\hat{A}\) (k × ℓ = 6 × 5 at ML-DSA-65) with SHAKE128, and that sampling now happens once, when the key is loaded. What Keccak still does per attempt is draw the mask \(y\) (25 SHAKE256 blocks) and hash \(w_1\) into the challenge, and that already runs on the assembly rounds from the previous section. That left the NTTs as the biggest remaining item: in the profile of an expanded ML-DSA-65 signing attempt, the inverse NTT was 31% of the instructions and the forward NTT 12%. pqm4 has a well-known Armv7E-M NTT for exactly this ring, and mldsa-native has native-backend hooks for it. The pqm4 NTT keeps the reference coefficient order and stays within mldsa-native’s documented output bounds, so plugging it in changes nothing else. A test checks it against the C version value for value, and against the bounds contract on extreme and random inputs.

One worry: the NTT multiplies secret values with SMULL/SMLAL. On the Cortex-M3, long multiplies terminate early depending on their operands, which is a timing leak. Arm’s documentation for the M33 doesn’t say, so I measured it. 24 operand pairs (zero, all-ones, either side of the 8- and 16-bit boundaries, small negatives, asymmetric pairs in both orders) and a dependent chain of Montgomery multiplications each took exactly the same number of cycles. That’s evidence, not proof, and it applies to this core only.

Shaving the Expanded Code

With the big structural changes done, the expanded code itself became worth profiling. Each of these was measured on the board, paired against the same image with that one change undone, using the same key and the same rnd values so every variant takes the same attempts.

A three-instruction Montgomery reduction. mldsa-native reduces a 64-bit product \(a\) as \(t = a \cdot q^{-1} \bmod 2^{32}\), \(r = (a - t q) / 2^{32}\). GCC at -Os makes that seven instructions. Negating the constant gives a congruent result with the same bound:

\[t' = a \cdot (-q^{-1}) \bmod 2^{32}, \qquad r = \frac{a + t' q}{2^{32}}\]

The addition is now a multiply-accumulate, so the whole reduction is SMULL, MUL, SMLAL. Two details matter. The constant goes through an empty asm so the optimizer can’t rebuild it from shifts and adds for every coefficient at -Os. And the expression has to be written out inside the loop body, or GCC falls back to ADDS/ADC.

One reduction instead of two in verification. Verification computes \(A z - c\, t_1 2^d\). Negating \(\hat{c}\) once turns the subtraction into one more multiply-accumulate in the same 64-bit sum, with a single reduction per coefficient. A preprocessor #error checks that \(\ell \cdot q \cdot B_{NTT} + B_{NTT}^2 < 2^{31} q\), so the sum stays inside the reduction’s input range: −3.6% of a verification.

Fusing passes. Add-reduce-norm-check in one loop instead of three: −1.9% of a signature for 178 bytes. Decompose plus w1 packing in one pass: −0.9% for 58 bytes. QEMU counted the fused versions as slightly more instructions. The board counts memory traffic and taken branches, and there they win.

flatten. mldsa-native’s tiny per-coefficient helpers (mld_decompose, mld_caddq, mld_use_hint) are plain static inline, and at -Os LTO left them out of line: 7,562 calls of mld_decompose per signature, each doing a few instructions of work. __attribute__((flatten)) on just the hot loops gave 5.6% faster signing and 20% faster verification for 390 bytes. Forcing those helpers inline across the whole library would have grown everything.

Integrity: A Fault Check That Didn’t Check

The wrapper verifies every signature before releasing it, which is standard fault-attack hardening: a fault in the computation produces an invalid signature, and that’s never released. With expanded keys, though, the check verifies against the same \(\hat{A}\) in RAM that signing used. A fault-injection test showed the hole: corrupt one polynomial of \(\hat{A}\) and you get a signature that passes the check and does not verify against the real public key.

The fix is a digest of the public tables, taken at expansion and compared after the check. The first version used two running sums, and a review found a correlated corruption that defeats it: \(+1, -2, +1\) in the same coefficient of three equally spaced polynomials cancels both sums whatever the data. The digest is now XXH32, which isn’t linear in any one ring, so that kind of cancellation doesn’t carry over. It is a fingerprint against accidental corruption (bit flips, stuck words, stray writes), not a MAC against tampering: whoever can write the table can write the digest too. It costs about 1.2% of a signature. The STM32’s hardware CRC unit was measured too, and it was slower than XXH32 in software here, at about 2.1 cycles per byte fed by the CPU.

Latency Is a Distribution

Each attempt succeeds with roughly the same probability, so the number of attempts is geometric: the mean is 5.1 at ML-DSA-65, but the tail is long. Timing 256 hedged signatures one by one through the wrapper: median 4.25 M cycles, p99 20.3 M, worst seen 32.7 M (204 ms). Over 16,384 signatures on the host, the geometric model matched the measured tail out to one in ten thousand. Extrapolating, one signature in a million needs more than about 64 attempts.

A hard deadline can’t be guaranteed per signature, but it can be per call: MlDsa::sign takes an MlDsaAttemptBudget. When the budget runs out it returns AttemptsExhausted with the signature zeroed and the workspace wiped, the caller signs again with a fresh rnd, and no fault is counted. A budget of 10 bounds a call to about 9.6 M cycles at ML-DSA-65 and leaves roughly one call in nine to retry.

Today: Making the Tables Smaller

A review this week turned up two more things, both about memory.

Packing \(\hat{A}\) into 24 bits. Every coefficient of \(\hat{A}\) lies in \([0, q)\), and \(q < 2^{23}\). Storing them as int32_t wastes a byte each. Packing four coefficients into three words:

/* coefficient 4m + r, r a compile-time constant after inlining */
r == 0: w[0]                         & 0xFFFFFF
r == 1: (w[0] >> 24) | (w[1] << 8)   & 0xFFFFFF
r == 2: (w[1] >> 16) | (w[2] << 16)  & 0xFFFFFF
r == 3: w[2] >> 8

The row loops process four coefficients per iteration, so r is a constant and each extraction is one or two aligned loads and at most three ALU instructions. This saves 7,680 bytes per expanded public key at ML-DSA-65 (36,936 → 29,256) and 14 KB at ML-DSA-87. The magic number changed, so a table in the old layout is refused rather than misread.

Not keeping \(y\). An attempt needed both the mask \(y\) (for \(z = y + c s_1\)) and its NTT \(\hat{y}\) (for \(w = A y\)): 2 × 5 KB at ML-DSA-65. But the inverse NTT in mldsa-native multiplies by the Montgomery factor \(2^{32}\), and the Montgomery reduction divides by it. So:

\[\mathrm{INTT}_{\text{tomont}}\Big(\mathrm{redc}\big(\hat{c} \circ \hat{s}_1 + \hat{y}\big)\Big) = \mathrm{INTT}\big((\hat{c}\circ\hat{s}_1 + \hat{y})\cdot 2^{-32}\big)\cdot 2^{32} = c\, s_1 + y \pmod q\]

\(\hat{y}\) is just one more addend in the multiply-accumulate, and \(z\) can be computed in place over \(\hat{y}\). Since \(\lvert y + c s_1\rvert < 2^{19} \ll q/2\), the centered reduction recovers exactly the same integer, so the signatures stay byte-identical, as the tests confirm. A compile-time check verifies that \(B_{NTT}^2 + B_{NTT} < 2^{31} q\). The result is L−1 fewer polynomials in the workspace: the signing stack through the wrapper went from 19,128 to 15,072 bytes, and signing got 1.9% faster even after paying for the packing above, since the copy of \(y\) and its separate addition pass are gone.

The packing isn’t free. Verification is 1 to 5% slower, depending on the image, since it reads all of \(\hat{A}\) once and gets nothing back from the \(y\) change. Code grew by 512 bytes. A smaller table also makes the digest check 20% cheaper. For a device where RAM is the scarce resource, that’s the right trade.

Where It Ended Up

ML-DSA-65 with REDUCE_RAM, CPU cycles on the board from flash, before this week’s two changes:

configuration	keypair	sign	verify	stack sign / verify	library flash
upstream	3,839,196	22,355,909	3,901,006	13.1 / 12.3 KB	11.5 KB
+ interleaved Keccak (asm) + pqm4 NTT	3,082,761	16,928,619	3,049,331	12.9 / 12.2 KB	19.3 KB
+ expanded keys	3,082,302	4,387,990	454,391	18.7 / 9.7 KB	22.6 KB

Through the wrapper, with rnd drawn from the DRBG, the check before release and the digest, a signature costs about 4.97 M cycles (31 ms) on the benchmark’s inputs. This week’s changes then made signing 1.8–1.9% faster and verification 1–5% slower (measured from SRAM), cut the signing stack to 15.1 KB, and brought the tables to 46.8 KB per ML-DSA-65 key pair.

Lessons

• Profile, then think about the algorithm, then tune. The biggest win (5×) was recognizing that a long-lived key makes most of signing a constant. The hand-written Keccak and NTT together were worth about 1.3×.
• Instruction counts are a guide, not a verdict. QEMU’s counts ranked the fused loops as a loss and inlining as nearly free. The board said the opposite, and code running from SRAM versus flash shifted the gains by a factor of two. The final word is always cycles on the real part, running the way firmware runs.
• Keep one source of truth for correctness. Every variant reproduces upstream’s signatures byte for byte, and the fork refuses to build when upstream changes under it. That’s what made it safe to try 50-odd variants, including the ones that lost.
• Write down the negative results. The 4-way Keccak, early parity, the per-permutation conversion and -O2 each cost a day to find out. Writing them down keeps them from being proposed again.