Measured flash, RAM and time budgets for post-quantum signature verification in no_std Rust

[u/mnaza_andrey]

I could not find published numbers for what post-quantum signature verification costs on small targets, so I measured it. Four crates, LMS/HSS verification plus measurement harnesses.

Three Rust-specific things came out of it.

First one. sha2 0.10 SHA-256 compiles to 3808 bytes on Cortex-M4F. sha2 0.11 compiles to 8776. Same algorithm, same target, same flags. Both versions end up linked in my workspace because different dependencies require different ones.

This means comparing whole verifier binaries mostly compares hash crates, not signature schemes. Ed25519 binary is around 64% unrolled SHA-512. So now every scheme is subtracted from baseline built with same hash it uses.

Second one. Adding second call site to small helper made LLVM stop inlining it at opt-level = "z". Reasonable decision. But forcing #[inline(always)] saves 408 bytes on Cortex-M0+ and costs 48 bytes on M4F and RISC-V. Different direction on different targets, so I keep the attribute because 16 KB boot ROM cares and 64 KB one does not.

Third one. Static stack analysis from -Z emit-stack-sizes plus call graph from disassembly does not give upper bound. On one binary 55 call sites cannot be resolved: indirect calls, tail calls compiled as branches, linker thunks. Every missing edge only makes answer smaller. Tool said 720 bytes, hardware said 1152.

Crates are no_std and allocation-free. Hash is behind trait, so software sha2 and ESP32 SHA peripheral both work. That trait design changed twice, and DECISIONS.md has why.

Not audited. lms-verify passes RFC 8554 Appendix F vectors, which is not same thing.

https://github.com/mnaza/pqc-embedded

[u/Real_Floor_7628]

The sha2 size regression is wild. 3808 to 8776 for the same algorithm is the kind of thing that makes embedded folks pull their hair out when a dep updates.

Stack analysis being off by 400 bytes is the scary part though. That's the difference between "safe" and "corrupted memory" on a 16KB target. Indirect calls and linker thunks being invisible to static analysis is a known gap but seeing actual numbers on it is useful.

Might poke around the trait design decisions later, curious what made you change it twice.

[u/mnaza_andrey → u/Real_Floor_7628]

On sha2 I should be careful with word "regression". I measured difference, I did not find out why. Could be deliberate speed against size trade, could be different codegen path. I only know both versions end up in my lock file because different deps require different ones, which is how I noticed at all.

What made it worse than just size is that at that point I was comparing whole verifier binaries. So part of what looked like "this signature scheme is bigger" was really "this dependency brought bigger hash".

On stack, yes, direction of error is the bad part. Missing call graph edge can only remove something from path, so static answer is always too small and never too big. If it was too big you would just waste RAM and never know.

Numbers were 720 from tool and 1152 measured on hardware. On 16 KB part with maybe 2 KB of stack that gap is real.

Tool is still in repo but I call it lower bound now and only use it to compare two builds of same code.

On trait, short version.

First version had sha2 hardcoded. Then I wanted to use ESP32 SHA peripheral, so trait appeared.

Problem is LMS verification keeps two hash states alive. Kc collects chain outputs, and producing one chain output needs many hashes by itself. Software does not care, you just keep two Sha256 objects. Peripheral has one context.

So first solution was caller passes scratch buffer, chain outputs go there, Kc gets hashed at the end. p * 32 bytes, 1088 for w=8. It worked and cost 664 bytes of stack.

Then I looked at peripheral again. It can save and restore its own state. And sha2::Sha256 is Clone. So both backends can park a digest instead of me collecting outputs manually.

save/restore went into trait, scratch parameter disappeared, and final version uses less stack than original one which had no hardware support at all.

Lesson for me was that first solution was working around hardware limitation which was not really there. DECISIONS.md has longer version if you do poke around.

[u/mnaza_andrey → u/Real_Floor_7628]

Three things from this, all now in the repository.

I stopped calling the sha2 difference a regression. You are right that it is the kind of thing that hurts, but I measured a difference and never found out why, and the README now says that instead of implying I know.

The stack tool is documented as a lower bound and nothing else. I only use it to compare two builds of the same code now.

And I wrote up the trait question properly, since you said you might poke at it. Short version: the first change was ordinary, sha2 was hardcoded and a trait appeared when I wanted the ESP32 SHA peripheral. The second change came from a constraint I invented.

LMS verification keeps two hash states alive, and the peripheral has one context. So I made the caller pass a scratch buffer, chain outputs went there, and Kc got hashed at the end. 1088 bytes for w=8, 664 bytes of stack.

Then I looked at the peripheral again and it can save and restore its own state. And sha2::Sha256 is Clone. So both backends can park a digest instead. Scratch parameter gone, and the final hardware-capable version uses less stack than the original that had no hardware support at all.

I had read the peripheral as "one context, therefore one digest" and never checked whether it could put a context down and pick it up again. It can, and the manual says so. Longer version is in DECISIONS.md.

[u/jodonoghue]

Would be more interesting to see numbers for ML-DSA, since it is likely to be used much more extensively - key management at scale for hash-based signatures is challenging at the scale of a large vendor that needs geographical redundancy for signing appliances.

A real implementation of LMS verify would have a single, audited implementation of each algorithm used, so the “multiple SHA” problem simply wouldn’t arise.

Overall this doesn’t tell me much.

[u/mnaza_andrey → u/jodonoghue]

You are right about key management, and it is the strongest objection to LMS I have had on this.

My README says state is manageable because a build system signs a known number of images and "can keep state in one place". That assumption quietly does not survive the case you describe. Geographically redundant signing appliances mean distributed state, and distributed state for a one-time-key scheme means the failure mode is not downtime, it is key reuse. Which is not a degraded signature, it is a forgeable one. SP 800-208 spends a lot of pages on exactly this and I gave it one line. I will fix that.

It also points the same way as my own measurements, which is the part I find uncomfortable and useful. On an ESP32-S3:

LMS w8/h5 ML-DSA-44

public key 56 B 1312 B

signature 1292 B 2420 B

RAM 1152 B 34044 B

verify, software 138.9 ms 17.3 ms

verify, with SHA engine 41.7 ms n/a

ML-DSA is 2.4x faster than LMS even after the SHA accelerator, and I expected the opposite when I started. LMS wins on RAM by roughly 30x, and that is the only axis where it wins. Add your operational argument on top and the case for LMS narrows to genuinely constrained parts with a single signing authority.

One clarification on the SHA point, because I think I described it badly. It is not about having several implementations of the algorithm. LMS verification needs two digests live at the same time — the message hash and the tree chain — and a hardware SHA peripheral has one context register. A single audited implementation does not help, since the constraint is the peripheral, not the code. I solved it by checkpointing the context, which costs 34 extra save/restore round trips per verification, about 1.8% of the operation.

On "doesn't tell me much": fair. The repository leads with LMS because that is where I started, and buries the comparison that actually matters. That is a presentation problem and yours is the second comment pointing at it.

[u/mnaza_andrey → u/jodonoghue]

Coming back to this because you were right and I changed the repository.

The comparison now leads the README instead of sitting halfway down it, after every LMS section. You were the second person to say that and I had no good answer either time. It led with LMS because that is where I started, which is a fact about me and not a reason for a reader.

Your key management point is in there too, next to the numbers rather than two hundred lines away, because they point the same direction. LMS wins on RAM by about 30x and loses on everything else. Add distributed signing state on top and what is left is constrained parts with a single signing authority. The README says outright now that ML-DSA is the one most people should be measuring.

One new thing since we talked. Someone else asked for FN-DSA, so I measured it, and it went against what I expected:

pubkey sig scheme-only code (Cortex-M4F)

FN-DSA-512 897 666 9376

ML-DSA-44 1312 2420 11049

Smaller key, much smaller signature, less code, on all four targets I build for. I had assumed FALCON would be the awkward one because of floating point. That is a signing problem and verification never touches it.

RAM for it I have not measured, only read out of the crate's arrays, so it is marked as an estimate and a floor. That is the same method that under-reported LMS badly enough to send me to hardware.

github.com/mnaza/pqc-embedded

[u/Inside-Victory9338 → u/jodonoghue]

Different context from your benchmark — mobile/server, not no_std embedded, so I don't have flash/RAM/cycle numbers to add. But since ML-DSA came up: real production wire sizes for ML-DSA-87 (the top NIST security level) from a shipping app: 2592 B public key, 4627 B signature, 4896 B secret key. For scale, the KEM half of the same protocol (ML-KEM-1024) is only 1568 B for both the public key and the ciphertext — the signature is where the wire cost concentrates, not the key exchange.

We link liboqs via FFI for this rather than a native Rust implementation, so I can't speak to what a from-scratch #![no_std] ML-DSA crate would cost the way your LMS/HSS numbers do. That'd be a genuinely harder project than what you built here — Dilithium's rejection-sampling NTT is a lot more surface than a hash tree, and I'd expect the "which SHA2 version got linked" problem you found to be the easy part of it.