Quantum-resistant signatures: an update

Quantum-resistant crypto

Recently there has been great media attention on Quantum Computers (QC) and their potential impact on current cryptography standards. We blogged about it in 2015.   All of this attention has drawn out critical efforts from many in academia and industry to solve problems with today’s cryptography that would break in a post quantum computer world.  However, much of that work has lacked focus on an area which is fundamental- cryptographic signatures.

Why are quantum-resistant signatures important

A quantum computer could break essentially all of the public key cryptography standards in use today: ECC, RSA, DSA and DH. Thus, if practical QCs became a reality, they would pose a threat to PKI-based signatures. For example, someone with a QC at some time in the future could perform a man-in-the-middle attack for a captured TLS negotiation, meaning the encryption within TLS protecting the confidentiality of the data would be broken. Signatures are often used to ensure software is legitimate and from a known entity.  In another scenario, if a signature used to validate software integrity is embedded in a piece of software or ‘burned into a piece of hardware’, a QC could, at some time in the future, forge a signature and manage to load an arbitrary otherwise malicious image. For those reasons, at Cisco, among other things, we have been investigating quantum-secure signatures.

HBS schemes

A well-understood quantum-secure signature technique is Hash-Based Signatures (HBS). Hash-Based signatures are tree structures that have signatures of messages as their leaves and the root and the path to the root of the tree becomes the public key for the messages signed in the tree. Due to their well-understood and analyzed primitives, HBS schemes are widely accepted as good candidates for quantum-secure signatures. XMSS is one such scheme that has been going through iterations for standardization in IETF’s CFRG WorkGroup (WG). Similarly, LMS is another HBS scheme by Cisco’s David McGrew driven in IETF. Both of these schemes are stateful, which means that a private key should only be used once to sign a message and a reused private key compromises the security of all the signatures in the tree. On the other hand, purely stateless schemes like SPHINCS eliminate the state management challenges, but have significantly high signature sizes.

As we’ve seen in a number of other encryption schemes, while the requirement of avoiding key reuse in a stateful signature schemes seems simple, it conflicts with a baseline goal of ensuring crypto is as easy as possible to implement and needs to be addressed. There are techniques that can be applied to protect against such concerns.  Cisco has been working with a set of world class researchers to mature these schemes and offer them for broader consideration via our paper here.  In this paper, we analyze state management in hash-based signature schemes, and categorize the security issues that can occur and ultimately we consider a hybrid stateless/stateful approach. Compared to a completely stateless scheme, the hybrid approach realizes the essential benefits, with smaller signatures and faster signing. We believe that by leveraging these techniques, stateful schemes can be practical in more environments since the complexity and very high signature size of stateless schemes are often limiting factors for their deployment.

Future

A properly deployed and implemented HBS schemes has multiple applications in a post-quantum world. Some use cases include

• Firmware or software image signing
• Certificate authentication (TLS, IKEv2 and more). Standardization of the HBS scheme in the widely used in the industry Cryptographic Message Syntax (CMS) would be required as the LMS in CMS draft attempts to do for LMS.
• Software package signing
• File signing

We believe both stateful and stateless schemes are useful for certain use cases. Tradeoffs between signature size, performance and implementation concerns will be important when deciding which scheme is used where. For example, a stateless 41KB SPHINCS signature can be impractical for a certificate in certain environments, whereas in modern networks it might not be an issue. Similarly, state management can be challenging for certain memory technologies, which can deem them impractical in some cases.

We expect that some HBS schemes will be standardized which will make the eligible to be used in crypto protocol and for certain use cases. We are working to ensure HBS schemes will be considered in many standards efforts going on around the world.

At Cisco, we will keep focusing on signatures that stand up to the existence of quantum computers and we believe HBS is the right place to focus. Our goal is to work with the industry and promote standardization of commonly accepted schemes and adoption in crypto standards like CMS. Our vision and thoughts will be presented in the 4th ETSI/IQC Workshop on Quantum-Safe Cryptography in September. For more information on our view of engineering postquantum security and recent developments, stay tuned for an upcoming blog.