Post-quantum cryptography

[d3zd3z]

MCUboot supports 2 general types of signature algorithms, those based on RSA, and those based on elliptic curves. There is some research suggesting that Shor's algorithm may be implementable on a quantum annealing computer rather than needing a general purpose quantum computer. Since these devices are already available in configurations with thousands of bits, it is not unreasonable to assume that at least RSA, and possible EC-based cryptographic algorithms will be broken in a timeframe of possible 10s of years.

The IETF SUIT working group, as well as the Mbed TLS project are both considering implementations of signature algorithms that will not be susceptible to breaks by advances in quantum computing. SUIT is even considering making implementation of a quantum-safe signature algorithm (likely HSS-LMS) to be mandatory, meaning any SUIT compliant implementation must support this signature algorithm, in addition to any other algorithms it supports. Fortunately, the signature verification aspect of HSS-LMS is a fairly small amount of code, and mostly consists of multiple invocations of an underlying hash function (which we already need).

I wanted to place this discussion here as a placeholder for us to discuss the impact of these algorithms on MCUboot. It would be possible to implement HSS-LMS in MCUboot (it would be a fairly small amount of boot code, and a little more substantial code in imgtool and the sim).

Aside from some differences in terms of signature sizes (there is a tradeoff between signature size and verification time), the most significant difference with HSS-LMS is that the private key must keep track of state. A given private key is only able to sign a fixed number of images. Most importantly, if a given state is used to sign more than one image, all security is lost, and an attacker would be able to then sign arbitrary images.

[0Grit]

@bremoran @vitprajzler @mniestroj

[bremoran]

Some relevant background & references:
https://www.nature.com/articles/s41598-018-36058-z
https://ui.adsabs.harvard.edu/abs/2019SCPMA..6260311P/abstract

[fkromer]

wolfBoot supports LMS/HSS and XMSS/XMSS^MT. Could be a helpful reference.

[ralienpp]

The challenge of state management only affects the infrastructure that produces and signs the firmware, whereas the logic running on the embedded system only needs to be able to verify that signature - this is a simpler task.

Therefore implementing this feature would enable others to build and try prototypes. As long as they can figure out a way for secure state-handling on the server side, this could enable them to produce quantum-safe systems that rely on "old and tried" cryptographic primitives, rather than rely on newer types of algorithms that haven't been tested by time yet (e.g., ML-DSA).