Are Hardware Wallets Ready to Produce Post-Quantum Signatures?

Disclaimer. This research did not aim to rank wallets or claim that some devices are better than others. We made all the benchmarks based on the same reference C libraries [1, 2, 3] on every tested wallet (with some per-wallet adoptions); we don’t claim it’s the most optimized or effective; it’s fairly average. Of course, the teams behind these wallets have deep knowledge of their own devices and may well achieve better results. We’d be glad to share any results, techniques, and implementations that beat our numbers. Anyway, a huge thank you to all teams behind for supporting self-custodial Bitcoin.

Acknowledgements. We want to thank Jade Team, especially Rich Grambergs, for sending a developer Jade Plus wallet; Ledger Team, represented by Charles Guillemet, for pointing out how we can launch custom apps on Ledgers; SatoshiLabs Group for the (almost) painless process of uploading a custom firmware even on non-developer wallets; and the BitBox team, especially Jad, for shipping us a developer BitBox02 Nova wallet. We want to thank Anastasiia Sapozhkova and Pavel Kravchenko for helping us get some of the dev devices. Last but not least - Jonas Nick, Mike Kudinov, Viktor Mashtaliar, and Yaroslava Chopa: thank you for the careful review and valuable feedback.

The State of the Problem

There is a popular concern that post-quantum (PQ) cryptography is hard, or even impossible, to implement on existing hardware wallets. Several interviews, threads, and posts raise this important topic.

We aren’t ready to generalize this statement to all PQ primitives because only part of the work is done, but one thing is already clear: PQ signature schemes can run on all popular hardware wallets.

This post demonstrates that claim through implementations and benchmarks on real devices.

To be precise about what we claim: this post is about generating signatures on the device, and only for hash-based schemes. It is not about verifying post-quantum firmware (a separate, not easier problem), and it does not cover lattices (also seems possible) or isogenies, which shall be tested later.

Preamble. A while ago, we started investigating hash-based signatures and how well they fit Bitcoin. Blockstream Research (including our modest participation) has done a lot of interesting work here:

• “Hash-based signatures for Bitcoin”
• Proposals for SHRINCS and SHRIMPS signature schemes both covered in our blog
• The SHRINCS specification and security proofs¹
• The first SHRINCS verifier, written on Simplicity and deployed on the Liquid Network (together with companion C++ and C implementations)
• Scripts and a visualization site for parameter selection, covered in this post

This post answers a simple but existential question: can existing hardware wallets actually run hash-based PQ signatures?

Surprisingly, they can do a lot.

Wallets and Signature Candidates

We tested four popular hardware wallets, with benchmark implementations available for each device: Jade, Trezor, Ledger [7, 8, 9], and BitBox02, and evaluated five hash-based signature schemes:

1. Classic SLH-DSA-128s (FIPS 205): 7,856-byte signature, 2^64 signatures, stateless. It’s a “minimal” SLH-DSA parameter set.
2. A reduced variant of SPHINCS+: 5,776-byte signature, 2^40 signatures, stateless. This is a promising candidate for the stateless part of SHRINCS.
3. UXMSS (the stateful part of SHRINCS-B): 324+ byte signature, stateful (the smallest SHRINCS signature).
4. UXMSS (a stateful part of SHRINCS-L): 1,092+ byte signature with and without overgrinding (Swn = 140/96)², stateful (that’s exactly the signature the verifier of which we have deployed on Liquid previously)
5. XMSS: a stateful 696-byte signature with 2^10 signature budget.

Implementation Details

As noted in the disclaimer, we tested the same "average" implementation of the signatures on all devices. An exact apple-to-apple comparison across wallets is very hard, because they differ in many ways:

• Different ways to run the code. Ledger lets us ship the app that runs inside the secure element through its operating system and call the OS’s crypto functions (we noticed significant syscall overhead and decided to use a custom SHA-256 implementation in the app to speed this up). On Jade, it runs on a general-purpose chip. Trezor and BitBox02 run custom firmware on their main microcontroller units; their secure elements only protect the PIN and secrets, and the signing math runs on the main chip.
• Different cryptoprimitives. Jade uses libwally, a wrapper around libsecp256k1 and its hash functions; Trezor has its own trezor-crypto; BitBox02 has its own; Ledger exposes its cxlib calls. We had to glue our reference library onto components that each device already provides, and in some places, we reused the device’s internal hash and endianness helpers instead of the library’s, which also affects the numbers.
• Different toolchains and hardware implementations of hash functions.
• Different CPU frequency (from 70 to 240 MHz).
• Different data transmission time.

So, it’s difficult to make a fair comparison between wallets, but as discussed above, this post focuses on the claim that all of them can produce hash-based signatures.

The Numbers

All presented numbers are averages after 100 executions of the corresponding operation.

KeyGen³

As shown, SLH-DSA, SPHINCS+ 2^40, and SHRINCS-L are practical for almost all devices. SHRINCS-B uses a bigger Winternitz parameter (w=256) and requires building an entire stateful tree during the KeyGen operation, thereby increasing runtime. XMSS takes from 1 minute to generate keys, but with caching, the signature generation might be very efficient.

SigGen

Summary:

• SLH-DSA: the signature takes from ~53 s to 120 s. Slow? Arguably. Impossible? No. SPHINCS+ with 2^40 signatures is a little faster.
• UXMSS (SHRINCS-B) takes 22-42 seconds on the same hardware.
• UXMSS (SHRINCS-L): Due to overgrinding, the signing gets much slower - from ~226 s to ~573 s. That’s a reasonable trade-off if you want to significantly reduce verification complexity. If we remove overgrinding, the signature takes 3+ seconds.
• XMSS: 58-118 seconds per signature in a cold mode. Comparable with SLH-DSA, but can be accelerated effectively with caching (not a subject of this post).

Cache It

The table above assumes that everything is recomputed from scratch each time the user generates the signature (cold mode). But hash-based signatures have a structure that presumes repeating much of the same work for each signature. The first reasonable question is “Can we save some of our computation results for future reuse?”. The answer is yes; for more details, check this article.

In our next post, we will try to define practical bounds and how efficient caching might be on hardware wallets. Stay tuned!

Bonus. Don’t Make Signature Generation Boring

We don’t think a couple of minutes for signature generation is a big deal for managing Bitcoin. Of course, it would be nice to have something faster for the Lightning Network, but again, with stateful signatures and caching, it also seems like a practical option.

Still, it might be annoying, so we recommend that wallet manufacturers consider larger displays to add a bit of fun. In our collection of wallets for testing hash-based signatures, we spent some time experimenting with the Trezor Safe 7. The user presses “Sign”, and… welcome to a Bitcoin racing game 🙂 (Tetris and Chess⁴ would work too; Pac-Man really requires a bigger display for comfortable gameplay).

Under the hood, Safe 7 switches between two processes: one generates the PQ signature, the other renders the game and handles the user’s input. It doesn’t support multithreading, only process switching, so the faster the game, the longer signing takes. Turn the game off, and you get exactly the numbers in the table above.

One nice side effect we are joking about internally is that the user can sample entropy from gameplay. Please don’t tell me you’ve never dragged the mouse or chaotically tortured the keyboard to obtain "sufficient" entropy (like TrueCrypt or a recent Privacy Pools’ trusted setup ceremony). A hash-based signature still needs a randomizer - so, you’re welcome.

At the same time, it shouldn’t be considered as a “side-channel countermeasure”. One can imagine the extra wallet activity (rendering the road, spawning the traffic, and reacting to panicked users’ actions) obfuscates the signing and confuses an attacker. But it really doesn’t - adding noise on its own is a weak protection method as shown in [10] and [11]. Real side-channel protection usually utilizes masking [10, 11, 12] (splitting the secret value into randomized shares to remove the correlation).

While we were working on final benchmarks and polishing the blog, we found other beautiful examples [13, 14] of what a wallet with a large enough display can do!

Conclusion

The concern that existing hardware wallets cannot produce PQ signatures does not hold up, at least for hash-based schemes. SLH-DSA signs in about a minute, and the stateful part of SHRINCS takes only seconds, on hardware wallets that people can buy and use today.

The remaining questions are no longer about basic feasibility. They are engineering questions: optimization, latency, caching, and hash acceleration.

---

Footnotes

1. The specification is in the progress and hasn’t been published yet. ↩
2. This variant uses WOTS+C one-time signature in leaves. Additionally to the reduced signature size, this approach allows to trade the signature generation cost for the signature verification complexity. ↩
3. Note that the full SHRINCS key generation procedure is a combination of the stateful and stateless KeyGens, so the total runtime is the sum of the two. ↩
4. It requires and additional 20-30KB RAM for the game search stack. ↩