|

Are Hardware Wallets Ready to Produce Post-Quantum Signatures?

Are Hardware Wallets Ready to Produce Post-Quantum Signatures?

Are Hardware Wallets Ready to Produce Post-Quantum Signatures?

Disclaimer. This analysis didn’t intention to rank wallets or declare that some gadgets are higher than others. We made all of the benchmarks primarily based on the identical reference C libraries [1, 2, 3] on each examined pockets (with some per-wallet adoptions); we don’t declare it’s essentially the most optimized or efficient; it’s pretty common. Of course, the groups behind these wallets have deep information of their very own gadgets and should properly obtain higher outcomes. We’d be glad to share any outcomes, methods, and implementations that beat our numbers. Anyway, an enormous thanks to all groups behind for supporting self-custodial Bitcoin.

Acknowledgements. We need to thank Jade Team, particularly Rich Grambergs, for sending a developer Jade Plus pockets; Ledger Team, represented by Charles Guillemet, for mentioning how we are able to launch customized apps on Ledgers; SatoshiLabs Group for the (virtually) painless strategy of importing a customized firmware even on non-developer wallets; and the BitBox group, particularly Jad, for transport us a developer BitBox02 Nova pockets. We need to thank Anastasiia Sapozhkova and Pavel Kravchenko for serving to us get a number of the dev gadgets. Last however not least – Jonas Nick, Mike Kudinov, Viktor Mashtaliar, and Yaroslava Chopa: thanks for the cautious overview and invaluable suggestions.

The State of the Problem

There is a well-liked concern that post-quantum (PQ) cryptography is difficult, and even unimaginable, to implement on present {hardware} wallets. Several interviews, threads, and posts increase this necessary subject.

We aren’t prepared to generalize this assertion to all PQ primitives as a result of solely a part of the work is finished, however one factor is already clear: PQ signature schemes can run on all fashionable {hardware} wallets.

This put up demonstrates that declare by way of implementations and benchmarks on actual gadgets.

To be exact about what we declare: this put up is about producing signatures on the system, and just for hash-based schemes. It is just not about verifying post-quantum firmware (a separate, not simpler drawback), and it doesn’t cowl lattices (additionally appears possible) or isogenies, which shall be examined later.

Preamble. Some time in the past, we began investigating hash-based signatures and the way properly they match Bitcoin. Blockstream Research (together with our modest participation) has performed a number of attention-grabbing work right here:

This put up solutions a easy however existential query: can present {hardware} wallets really run hash-based PQ signatures?

Surprisingly, they’ll do rather a lot.

Wallets and Signature Candidates

We examined 4 fashionable {hardware} wallets, with benchmark implementations obtainable for every system: Jade, Trezor, Ledger [7, 8, 9], and BitBox02, and evaluated 5 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 lowered variant of SPHINCS+: 5,776-byte signature, 2^40 signatures, stateless. This is a promising candidate for the stateless a part of SHRINCS.
  3. UXMSS (the stateful a part of SHRINCS-B): 324+ byte signature, stateful (the smallest SHRINCS signature).
  4. UXMSS (a stateful a part of SHRINCS-L): 1,092+ byte signature with and with out overgrinding (Swn = 140/96)2, stateful (that’s precisely the signature the verifier of which we now have deployed on Liquid beforehand)
  5. XMSS: a stateful 696-byte signature with 2^10 signature finances.

Implementation Details

As famous within the disclaimer, we examined the identical “common” implementation of the signatures on all gadgets. An actual apple-to-apple comparability throughout wallets may be very arduous, as a result of they differ in some ways:

  • Different methods to run the code. Ledger lets us ship the app that runs contained in the safe component by way of its working system and name the OS’s crypto features (we seen vital syscall overhead and determined to use a customized SHA-256 implementation within the app to velocity this up). On Jade, it runs on a general-purpose chip. Trezor and BitBox02 run customized firmware on their most important microcontroller models; their safe parts solely shield the PIN and secrets and techniques, and the signing math runs on the primary chip.
  • Different cryptoprimitives. Jade makes use of libwally, a wrapper round libsecp256k1 and its hash features; Trezor has its personal trezor-crypto; BitBox02 has its personal; Ledger exposes its cxlib calls. We had to glue our reference library onto elements that every system already gives, and in some locations, we reused the system’s inside hash and endianness helpers as an alternative of the library’s, which additionally impacts the numbers.
  • Different toolchains and {hardware} implementations of hash features.
  • Different CPU frequency (from 70 to 240 MHz).
  • Different knowledge transmission time.

So, it’s troublesome to make a good comparability between wallets, however as mentioned above, this put up focuses on the declare that every one of them can produce hash-based signatures.

The Numbers

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

KeyGen3

KeyGen / Wallet Jade Plus Trezor Safe 3 Ledger Nano gen5/s+ BitBox02 Nova
SLH-DSA-SHA2-128 7.06 s 8.64 s 15.82 s 12.7 s
SPHINCS+ 2^40
UXMSS (SHRINCS-L) 1.81 s 2.35 s 6.1 s 3.3 s
UXMSS (SHRINCS-B) 18.87 s 22.8 s 40.18 s 28.8 s
XMSS 2^10 57.78 s 75.64 s 117.85 s 79.5 s

As proven, SLH-DSA, SPHINCS+ 2^40, and SHRINCS-L are sensible for nearly all gadgets. SHRINCS-B makes use of an even bigger Winternitz parameter (w=256) and requires constructing a complete stateful tree throughout the KeyGen operation, thereby growing runtime. XMSS takes from 1 minute to generate keys, however with caching, the signature technology is likely to be very environment friendly.

SigGen

Signature / Wallet Jade Plus Trezor Safe 3/5/7 Ledger Nano gen5/s+ BitBox02 Nova
SLH-DSA-SHA2-128 (7856 B) 52.85 s 65.31 s 120.12 s 100.1 s
SPHINCS+ 2^40 (5776 B) 43.28 s 53.45 s 94.98 s 78.4 s
SHRINCS-L (swn=96, 1092 B) 3.31 s 3.01 s 8.04 s 5.5 s
UXMSS (SHRINCS-L) (swn=140, 1092 B) 225.63 s 264.74 s 572.78 s 334.6 s
UXMSS (SHRINCS-B) (324 B) 21.75 s 25.82 s 41.83 s 30.9 s
XMSS 2^10 (696 B) 57.8 s 75.63 s 118.2 s 79.6 s

Summary:

  • SLH-DSA: the signature takes from ~53 s to 120 s. Slow? Arguably. Impossible? No. SPHINCS+ with 2^40 signatures is a bit of quicker.
  • UXMSS (SHRINCS-B) takes 22-42 seconds on the identical {hardware}.
  • UXMSS (SHRINCS-L): Due to overgrinding, the signing will get a lot slower – from ~226 s to ~573 s. That’s an affordable trade-off if you would like to considerably scale back verification complexity. If we take away overgrinding, the signature takes 3+ seconds.
  • XMSS: 58-118 seconds per signature in a chilly mode. Comparable with SLH-DSA, however could be accelerated successfully with caching (not a topic of this put up).

Cache It

The desk above assumes that all the pieces is recomputed from scratch every time the consumer generates the signature (chilly mode). But hash-based signatures have a construction that presumes repeating a lot of the identical work for every signature. The first affordable query is “Can we save a few of our computation outcomes for future reuse?”. The reply is sure; for extra particulars, verify this article.

In our subsequent put up, we’ll strive to outline sensible bounds and the way environment friendly caching is likely to be on {hardware} wallets. Stay tuned!

Bonus. Don’t Make Signature Generation Boring

We don’t suppose a few minutes for signature technology is an enormous deal for managing Bitcoin. Of course, it could be good to have one thing quicker for the Lightning Network, however once more, with stateful signatures and caching, it additionally looks as if a sensible choice.

Still, it is likely to be annoying, so we advocate that pockets producers think about bigger shows to add a little bit of enjoyable. In our assortment of wallets for testing hash-based signatures, we spent a while experimenting with the Trezor Safe 7. The consumer presses “Sign”, and… welcome to a Bitcoin racing recreation 🙂 (Tetris and Chess4 would work too; Pac-Man actually requires an even bigger show for comfy gameplay).

Are Hardware Wallets Ready to Produce Post-Quantum Signatures?

Under the hood, Safe 7 switches between two processes: one generates the PQ signature, the opposite renders the sport and handles the consumer’s enter. It doesn’t assist multithreading, solely course of switching, so the quicker the sport, the longer signing takes. Turn the sport off, and also you get precisely the numbers within the desk above.

One good aspect impact we’re joking about internally is that the consumer can pattern entropy from gameplay. Please don’t inform me you’ve by no means dragged the mouse or chaotically tortured the keyboard to get hold of “ample” entropy (like TrueCrypt or a current Privacy Pools’ trusted setup ceremony). A hash-based signature nonetheless wants a randomizer – so, you’re welcome.

At the identical time, it shouldn’t be thought-about as a “side-channel countermeasure”. One can think about the additional pockets exercise (rendering the highway, spawning the site visitors, and reacting to panicked customers’ actions) obfuscates the signing and confuses an attacker. But it actually doesn’t – including noise by itself is a weak safety methodology as proven in [10] and [11]. Real side-channel safety often makes use of masking [10, 11, 12] (splitting the key worth into randomized shares to take away the correlation).

While we had been engaged on closing benchmarks and sprucing the weblog, we discovered different lovely examples [13, 14] of what a pockets with a big sufficient show can do!

Conclusion

The concern that present {hardware} wallets can not produce PQ signatures doesn’t maintain up, not less than for hash-based schemes. SLH-DSA indicators in a few minute, and the stateful a part of SHRINCS takes solely seconds, on {hardware} wallets that folks should purchase and use at the moment.

The remaining questions are not about fundamental feasibility. They are engineering questions: optimization, latency, caching, and hash acceleration.

Footnotes

  1. The specification is within the progress and hasn’t been revealed but. ↩
  2. This variant makes use of WOTS+C one-time signature in leaves. Additionally to the lowered signature measurement, this method permits to commerce the signature technology value for the signature verification complexity. ↩
  3. Note that the total SHRINCS key technology process is a mixture of the stateful and stateless KeyGens, so the entire runtime is the sum of the 2. ↩
  4. It requires and extra 20-30KB RAM for the sport search stack. ↩

Similar Posts