Summary

NIST is requesting public comments on the intended approval of LMS and XMSS as stateful hash-based signature (HBS) schemes. Questions for consideration and instructions for providing comments by April 1, 2019 are included at the bottom of this notice.

Details

In December 2016 NIST issued a Call for Proposals soliciting public-key cryptosystems that are capable of protecting sensitive information, even after the advent of quantum computers. The corresponding FAQ noted that NIST plans to have a separate standardization process for stateful hash-based signatures, which would be coordinated with other standards organizations, such as the Internet Engineering Task Force (IETF).

The IETF has been developing specifications for two stateful hash-based digital signature schemes, XMSS and LMS. XMSS was published as Request for Comments (RFC) 8391 in May 2018. LMS is still in draft but is nearly complete. On June 21, 2018, NIST requested input from the public on its plans to standardize stateful hash-based signatures, asking whether NIST should move forward with XMSS now or wait for LMS to be finished. The general consensus was that both should be standardized.

Stateful hash-based signature schemes, such as XMSS and LMS, are prone to misuse. In these schemes, the signer has a set of key pairs for a one-time signature scheme. If any given private key is used to generate signatures on two or more distinct “messages” (i.e, the data to be signed), then it would be straightforward for an attacker with access to the signatures to generate forgeries (additional “valid” signatures) on other messages.

While the precise security level depends on parameters of the one-time signature scheme, the security of stateful hash-based signatures should be considered to be compromised in the event of key reuse. With typical parameter values, the security would be reduced to a level that is orders of magnitude weaker than that of single-key DES, which was publicly broken in the late 1990s. In some cases, signature forgeries could be generated by a few minutes of computations on a consumer-grade laptop; see [Bruinderink and Hülsing] for a detailed analysis.  Consequently, implementations of XMSS or LMS must maintain state to keep track of the one-time private keys that have been used to generate signatures, in order to prevent their reuse.

These considerations motivated the following statement in the FAQ and the June announcement: 

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.

In practice, however, it is difficult for NIST to limit the applications for cryptographic techniques, even for implementations that are certified under the auspices of the Cryptographic Module Validation Program (CMVP). For example, when a software library of cryptographic techniques is validated under the program, its vendor will not necessarily have any information about the signature applications for which the vendor’s customers might choose to deploy the techniques.

Moreover, the CMVP and Cryptographic Algorithm Validation Program (CAVP) are designed to provide assurance that individual modules correctly implement the cryptographic techniques. Experience has shown that it can be very difficult to enforce requirements on the larger system in which the modules are deployed.

NIST's Computer Security Division would like your feedback.

NIST currently intends to approve both LMS and XMSS. Because stateful hash-based signatures are prone to misuse, NIST seeks input on the following questions: 

• How should NIST’s specification characterize the applications for which such signatures are, or are not, appropriate?
• What requirements and guidance for protecting against misuse should NIST include beyond what is provided in the IETF specifications?

Comments may be sent to pqc-comments@nist.gov with the subject line “stateful HBS comments” by April 1, 2019.