By Alexander Truskovsky, Senior Product Manager, ISARA Corporation
Published on Mar. 27, 2018
With the latest release of the ISARA Radiate™ Security Solution Suite, we’ve added stateful hash-based signatures, specifically eXtended Merkle Signature Scheme (XMSS), to the cryptographic library. With this addition, we now offer complete stateful hash-based signature algorithm support. Also, using a unique optimization approach, we’ve successfully overcome the recognized challenges associated with implementing stateful hash-based signatures to create an HSM-based implementation successfully tested with Utimaco Inc.’s SecurityServer. Stateful hash-based signature algorithms are particularly valuable in “roots of trust” applications for durable products like automobiles that are being designed today but will be in use well into the quantum era.
LMS and XMSS are two algorithms that stand out from the rest of quantum-safe candidates. They’re based on a mature area of mathematics that’s over 40 years old and are well understood and trusted to be used today. Stateful hash-based signature scheme is really a collection of one-time hash-based signing and verification key pairs. In order to make these algorithms practical, the verification keys are combined using a binary tree into a single public key. This makes them easy to deploy in systems that perform signature verification. On the signature generation side, however, they are a little difficult to use because the signer needs to ensure that each signing key is only used once. Having to maintain private key state makes it a little impractical for protocols, like TLS. However, they work very well for code signing and that is what NIST is going to approve stateful hash-based signatures for.
While both LMS and XMSS generally perform better than elliptic curve cryptography (ECC), they have one drawback – a large stateful private key. We’ve solved the private key state management problem in our HSM implementation, making these schemes ready for quantum-safe code and certificate signing today. In our HSM-implementation we were able to use a tree height of 20 allowing for over one million possible signatures, making the number of possible signatures virtually unlimited. By using our unique tree reduction technique and state management, we were able to create an implementation that performs on par with classical digital signature implementations.
NIST received 69 post-quantum algorithms for potential standardization. NIST intends to standardize multiple options for different use cases plus speed and performance trade-offs, so that over the next five to seven years that list will be reduced to several options. Stateful hash-based digital signature schemes such as LMS and XMSS are not part of this process and will be approved for certain types of use cases, like code-signing, soon. The Internet Engineering Task Force (IETF) has both LMS and XMSS in the final stages of the specification which will then be standardized by NIST for low-frequency operations like code-signing. NIST directly addresses their plans for stateful-hash based signatures on their Post-Quantum Cryptography FAQ page stating:
“NIST plans to coordinate with other standards organizations, such as the IETF, to develop standards for stateful hash-based signatures. As stateful hash-based signatures do not meet the API requested for signatures, this standardization effort will be a separate process from the one outlined in the call for proposals. It is expected that NIST will only approve a stateful hash-based signature standard for use in a limited range of signature applications, such as code signing, where most implementations will be able to securely deal with the requirement to keep state.”
The urgency to migrate to quantum-safe roots of trust is directly related to the lifetime of the critical asset. Durable assets that are expected to be in-field ten or more years are at a greater risk to the quantum threat since there’s a higher chance that what’s designed today will still be used during the quantum era.
For example, smartphones have a relatively quick development cycle and are usually enjoyed for a few years before they’re replaced with the latest and greatest version. A new smartphone with quantum-safe roots of trust can be developed, sold and then replaced within 3-4 years.
On the other hand, critical infrastructure and fully-connected cars typically have lifespans greater than 10 years and development and production cycles of several years. A car designed today will be on the road well beyond 2026 – the earliest predicted date a large-scale quantum computer is expected to exist. The addition of XMSS to our toolkit give automotive manufacturers complete choice of stateful hash-based signature options to begin embedding quantum-safe roots of trust today to maintain the safety of the vehicle, as well as protect the investment in over-the-air software update capabilities and reduce upgrade/recall costs in the future.
With ISARA Radiate™ 1.4, quantum-safe roots of trust are now ready for the most security-conscious governments and organizations, such as automotive manufacturers, to begin their quantum-safe migration today.