NIST SP 800-208 日本語訳

NIST Special Publication 800-208

David A. Cooper Daniel C. Apon Quynh H. Dang Michael S. Davidson Morris J. Dworkin Carl A. Miller

This publication is available free of charge from: https://doi.org/10.6028/NIST.SP.800-208

NIST Special Publication 800-208

David A. Cooper Daniel C. Apon Quynh H. Dang Michael S. Davidson Morris J. Dworkin Carl A. Miller

Computer Security Division Information Technology Laboratory

This publication is available free of charge from: https://doi.org/10.6028/NIST.SP.800-208

October 2020

U.S. Department of Commerce Wilbur L. Ross, Jr., Secretary

National Institute of Standards and Technology

Walter Copan, NIST Director and Under Secretary of Commerce for Standards and Technology

Authority

This publication has been developed by NIST in accordance with its statutory responsibilities under the Federal Information Security Modernization Act (FISMA) of 2014, 44 U.S.C. § 3551 et seq., Public Law (P.L.) 113-283. NIST is responsible for developing information security standards and guidelines, including minimum requirements for federal information systems, but such standards and guidelines shall not apply to national security systems without the express approval of appropriate federal officials exercising policy authority over such systems. This guideline is consistent with the requirements of the Office of Management and Budget (OMB) Circular A-130.

Nothing in this publication should be taken to contradict the standards and guidelines made mandatory and binding on federal agencies by the Secretary of Commerce under statutory authority. Nor should these guidelines be interpreted as altering or superseding the existing authorities of the Secretary of Commerce, Director of the OMB, or any other federal official. This publication may be used by nongovernmental organizations on a voluntary basis and is not subject to copyright in the United States. Attribution would, however, be appreciated by NIST.

National Institute of Standards and Technology Special Publication 800-208 Natl. Inst. Stand. Technol. Spec. Publ. 800-208, 59 pages (October 2020) CODEN: NSPUE2

This publication is available free of charge from: https://doi.org/10.6028/NIST.SP.800-208

Certain commercial entities, equipment, or materials may be identified in this document in order to describe an experimental procedure or concept adequately. Such identification is not intended to imply recommendation or endorsement by NIST, nor is it intended to imply that the entities, materials, or equipment are necessarily the best available for the purpose.

原本PDFの抜粋画像

There may be references in this publication to other publications currently under development by NIST in accordance with its assigned statutory responsibilities. The information in this publication, including concepts and methodologies, may be used by federal agencies even before the completion of such companion publications. Thus, until each publication is completed, current requirements, guidelines, and procedures, where they exist, remain operative. For planning and transition purposes, federal agencies may wish to closely follow the development of these new publications by NIST.

Organizations are encouraged to review all draft publications during public comment periods and provide feedback to NIST. Many NIST cybersecurity publications, other than the ones noted above, are available at https://csrc.nist.gov/publications.

Comments on this publication may be submitted to: National Institute of Standards and Technology Attn: Computer Security Division, Information Technology Laboratory 100 Bureau Drive (Mail Stop 8930) Gaithersburg, MD 20899-8930 Email: pqc-comments@nist.gov

All comments are subject to release under the Freedom of Information Act (FOIA).

The Information Technology Laboratory (ITL) at the National Institute of Standards and Technology (NIST) promotes the U.S. economy and public welfare by providing technical leadership for the Nation’s measurement and standards infrastructure. ITL develops tests, test methods, reference data, proof of concept implementations, and technical analyses to advance the development and productive use of information technology. ITL’s responsibilities include the development of management, administrative, technical, and physical standards and guidelines for the cost-effective security and privacy of other than national security-related information in federal information systems. The Special Publication 800-series reports on ITL’s research, guidelines, and outreach efforts in information system security, and its collaborative activities with industry, government, and academic organizations.

cryptography; digital signatures; hash-based signatures; public-key cryptography.

Document Conventions

The terms “shall” and “shall not” indicate requirements to be followed strictly in order to conform to the publication and from which no deviation is permitted.

The terms “should” and “should not” indicate that, among several possibilities, one is recommended as particularly suitable without mentioning or excluding others, that a certain course of action is preferred but not necessarily required, or that (in the negative form) a certain possibility or course of action is discouraged but not prohibited.

The terms “may” and “need not” indicate a course of action permissible within the limits of the publication.

The terms “can” and “cannot” indicate a possibility and capability, whether material, physical, or causal.

Conformance Testing

Conformance testing for implementations of the functions that are specified in this publication will be conducted within the framework of the Cryptographic Algorithm Validation Program (CAVP) and the Cryptographic Module Validation Program (CMVP). The requirements that apply to these implementations are indicated by the word “shall.” Some of these requirements may be out-of-scope for CAVP or CMVP validation testing and, thus, are the responsibility of entities using, implementing, installing, or configuring applications that incorporate this Recommendation.

Patent Disclosure Notice

NOTICE: The Information Technology Laboratory (ITL) has requested that holders of patent claims whose use may be required for compliance with the guidance or requirements of this publication disclose such patent claims to ITL. However, holders of patents are not obligated to respond to ITL calls for patents and ITL has not undertaken a patent search in order to identify which, if any, patents may apply to this publication.

As of the date of publication and following call(s) for the identification of patent claims whose use may be required for compliance with the guidance or requirements of this publication, no such patent claims have been identified to ITL.

No representation is made or implied by ITL that licenses are not required to avoid patent infringement in the use of this publication.

NIST is in the process of developing standards for post-quantum secure digital signature schemes [7] that can be used as replacements for the schemes that are specified in [4]. Stateful HBS schemes are not suitable for general use because they require careful state management that is often difficult to assure, as summarized in Section 1.2 and described in detail in [8].

Instead, stateful HBS schemes are primarily intended for applications with the following characteristics: 1) it is necessary to implement a digital signature scheme in the near future; 2) the implementation will have a long lifetime; and 3) it would not be practical to transition to a different digital signature scheme once the implementation has been deployed.

An application that may fit this profile is the authentication of firmware updates for constrained devices. Some constrained devices that will be deployed in the near future will be in use for decades. These devices will need to have a secure mechanism for receiving firmware updates, and it may not be practical to change the code for verifying signatures on updates once the devices have been deployed.

In a stateful HBS scheme, an HBS private key consists of a large set of one-time signature (OTS) private keys. The signer needs to ensure that no individual OTS key is ever used to sign more than one message. If an attacker were able to obtain digital signatures for two different messages that were created using the same OTS key, then it would become computationally feasible for that attacker to forge signatures on arbitrary messages [13]. Therefore, as described in [8], when a stateful HBS scheme is implemented, extreme care needs to be taken in order to ensure that no OTS key is ever reused.

In order to obtain assurance that OTS keys are not reused, the signing process should be performed in a highly controlled environment. As described in [8], there are many ways in which seemingly routine operations could lead to the risk of one-time key reuse. The conformance requirements imposed in Section 8.1 on cryptographic modules that implement stateful HBS schemes are intended to help prevent one-time key reuse.

The remainder of this document is divided into the following sections and appendices:

approved — FIPS-approved or NIST-recommended. An algorithm or technique that is either 1) specified in a FIPS or NIST Recommendation or 2) adopted in a FIPS or NIST Recommendation and specified either (a) in an appendix to the FIPS or NIST Recommendation or (b) in a document referenced by the FIPS or NIST Recommendation.

Selected acronyms and abbreviations used in this publication are defined below.

EEPROM — Electronically erasable programmable read-only memory

EUF-CMA — Existential unforgeability under adaptive chosen message attacks

FIPS — Federal Information Processing Standard

HBS — Hash-based signature

HSS — Hierarchical Signature Scheme

IRTF — Internet Research Task Force

LM-OTS — Leighton-Micali One-Time Signature

LMS — Leighton-Micali signature

NIST — National Institute of Standards and Technology

OTS — One-time signature

QROM — Quantum random oracle model

RAM — Random access memory

RFC — Request for Comments

ROM — Random oracle model

SHA — Secure Hash Algorithm

SHAKE — Secure Hash Algorithm KECCAK

SP — Special Publication

VM — Virtual machine

\(WOTS^{+}\) — Winternitz One-Time Signature Plus

XDR — External Data Representation

XMSS — eXtended Merkle Signature Scheme

\(XMSS^{MT}\) — Multi-tree XMSS

At a high level, XMSS and LMS are very similar. They each consist of two components—a one-time signature (OTS) scheme and a method for creating a single, long-term public key from a large set of OTS public keys. A brief explanation of OTS schemes and the method for creating a long-term public key from a large set of OTS public keys can be found in Sections 3 and 4 of [14].

Figure 2: A sample Winternitz signature generation and verification

As noted in [14], simply signing the individual digits of the digest is not sufficient because an attacker would be able to generate valid signatures for other message digests. For example, given \(s_k = H(x_k)\), as in Figure 2, an attacker would be able to generate a signature for a message digest with a \(k\)th digit of 2 by applying \(H\) to \(s_k\) once or to a message digest with a \(k\)th digit of 3 by applying \(H\) to \(s_k\) twice. An attacker could not, however, generate a signature for a message digest with a \(k\)th digit of 0 as this would require finding some value \(y\) such that \(H(y) = s_k\), which would not be feasible as long as \(H\) is preimage-resistant.

Figure 3: A sample Winternitz signature

While a single, long-term public key could be created from a large set of OTS public keys by simply concatenating the keys together, the resulting public key would be unacceptably large. XMSS and LMS instead use Merkle hash trees [18], which allow for the long-term public key to be very short in exchange for requiring a small amount of additional information to be provided with each OTS key. To create a hash tree, the OTS public keys are hashed once to form the leaves of the tree, and these hashes are then hashed together in pairs to form the next level up. Those hash values are then hashed together in pairs, the resulting hash values are hashed together, and so on until all of the public keys have been used to generate a single hash value (the root of the tree), which will be used as the long-term public key.

Figure 4: A Merkle Hash Tree

Both [1] and [2] define single tree and multi-tree variants of their signature schemes. In an instance that involves two levels of trees, as shown in Figure 5, the OTS keys that form the leaves of the top-level tree sign the roots of the trees at the bottom level, and the OTS keys that form the leaves of the bottom-level trees are used to sign the messages. The root of the top-level tree is the long-term public key for the signature scheme.³

As described in Section 7, the use of two levels of trees can make it easier to distribute OTS keys across multiple cryptographic modules in order to protect against private key loss. A set of OTS keys can be created in one cryptographic module, and the root of the Merkle tree formed from these keys can be published as the public key for the signature scheme. OTS keys can then be created on multiple other cryptographic modules with a separate Merkle tree created for the OTS keys of each of the other cryptographic modules, and a different OTS key from the first cryptographic module can be used to sign each of the roots of the other cryptographic modules.

root a

ka,0 ka,1 ka,2 ka,3

rootb,1

rootb,3

rootb,0

rootb,2

kb,0 kb,1 kb,2 kb,3 kb,4 kb,5 kb,6 kb,7 kb,8 kb,9 kb,10 kb,11 kb,12 kb,13 kb,14 kb,15

Figure 5: A two-Level Merkle tree

XMSS generates its prefixes in a similar way. The information described above is used to form an address, which uniquely identifies where a particular hash invocation occurs within the scheme. This address is then hashed along with a unique identifier (SEED) for the long-term public key to create the prefix.

Figure 6: XMSS hash computation with prefix and bitmask

The LMS and HSS algorithms are described in RFC 8554 [2]. This Special Publication approves the use of LMS and HSS with four different hash functions: SHA-256, SHA-256/192, SHAKE256/256, and SHAKE256/192 (see Section 2.3). The parameter sets that use SHA-256 are defined in RFC 8554 [2]. The parameter sets that use SHA-256/192, SHAKE256/256, and SHAKE256/192 are defined in this publication.

When generating a key pair for an HSS instance, the requirements specified in the previous paragraph apply to each LMS tree in the instance. If the HSS instance has more than one level, then the hash function used for the tree at level 0 shall be used for every LMS tree at every other level. For each level, the same LMS and LM-OTS parameter sets shall be used for every LMS tree at that level. Different LMS and LM-OTS parameter sets may be used at different levels, as long as all chosen parameter sets use the same hash function.

Extensions to the XDR syntax in Section 3.3 of [2] needed to support the parameter sets defined in Sections 4.2 through 4.4 of this document are specified in Appendix A. The numeric identifiers for these parameter sets are marked as “TBD” since they had not yet been assigned at the time this document was published. Once they are assigned, the numeric identifiers may be found at https://www.iana.org/assignments/leighton-micali-signatures/leighton-micali-signatures.xhtml.

When generating LMS or HSS key pairs using SHA-256, the LMS and LM-OTS parameter sets shall be selected from the following two tables, which come from Sections 4 and 5 of [2].

Table 1: LM-OTS parameter sets for SHA-256

Table 2: LMS parameter sets for SHA-256

When generating LMS or HSS key pairs using SHA-256/192, the LMS and LM-OTS parameter sets shall be selected from the following two tables.

Table 3: LM-OTS parameter sets for SHA-256/192

Table 4: LMS parameter sets for SHA-256/192

When generating LMS or HSS key pairs using SHAKE256/256, the LMS and LM-OTS parameter sets shall be selected from the following two tables.

Table 5: LM-OTS parameter sets for SHAKE256/256

Table 6: LMS parameter sets for SHAKE256/256

When generating LMS or HSS key pairs using SHAKE256/192, the LMS and LM-OTS parameter sets shall be selected from the following two tables.

Table 7: LM-OTS parameter sets for SHAKE256/192

Table 8: LMS parameter sets for SHAKE256/192

Extensions to the XDR syntax in Appendices A, B, and C of [1] needed to support the parameter sets defined in Sections 5.2 through 5.4 of this document are specified in Appendix B.

Table 10: XMSS parameter sets for SHA-256

Table 12: XMSS parameter sets for SHA-256/192

Table 14: XMSS parameter sets for SHAKE256/256

Table 16: XMSS parameter sets for SHAKE256/192

Note: Variables and notations used in this section are defined in the relevant documents mentioned above.

If a digital signature key will be used to generate signatures over a long period of time and replacing the public key would be difficult, then it will be necessary to prepare for the possibility that a cryptographic module holding the private key may fail during the key’s lifetime. In the case of most digital signature schemes, a common solution is to make copies of the private key. However, in the case of stateful HBS schemes, simply copying the private key would create a risk of OTS key reuse.

While it would be possible to have one cryptographic module generate all of the OTS keys and then distribute different OTS keys to each of the other cryptographic modules, doing so is not an option for cryptographic modules that conform to this recommendation: due to the risks associated with copying OTS keys, this recommendation prohibits exporting private keying material (Section 8).

One option would be to create multiple stateful HBS keys on different cryptographic modules and then configure clients to accept signatures created using any of these keys. These keys could be distributed to clients all at once or using a mechanism such as the Hash Of Root Key certificate extension [23], which provides a mechanism for distributing new public keys over time.

When working with distributed multi-tree hash-based signatures, the cryptographic module that holds the top-level tree is a potential single point of failure. Once this cryptographic module fails, it is no longer possible to sign additional bottom-level key pairs. Consequently, all of the bottom-level keys should be generated up front as part of the initial key generation ceremony. Once the top-level key has been used to sign all of the bottom-level keys, the top-level key is no longer needed, as copies of the signatures created using OTS keys of the top-level key pair may be stored outside of the cryptographic module.

In order to avoid the top-level key being a single point of failure, the two options described above could be combined to create multiple distributed multi-tree HBS keys. Multiple top-level keys pairs would initially be created, each on a different cryptographic module, and clients would be configured to accept signatures created using any of these keys. Then, whenever a new bottom-level key needed to be created, it could be signed by any one of the top-level keys. This would allow for new bottom-level keys to be created as long as at least one of the cryptographic modules that contains a top-level key remained operational. Of course, the same level of care should be used when signing a bottom-level key as would be used during the initial key generation ceremony (or as would be used in making a copy of an RSA or ECDSA private key).

In the case of HSS, the distributed multi-tree scheme described above can be implemented using multiple cryptographic modules that individually implement LMS without modifications. The top-level LMS public key can be converted to an HSS public key by an external, non-cryptographic device. This device can also submit the public keys of the bottom-level LMS keys for signature by the top-level LMS key. In HSS, the operation for signing the root of a lower-level tree is the same as the operation for signing an ordinary message. Finally, this external device can submit ordinary messages to cryptographic modules that hold the bottom-level LMS keys for signing and then combine the resulting LMS signatures with the top-level key’s signature on the bottom-level LMS public key in order to create the HSS signature for the ordinary messages (see Algorithm 7 and Algorithm 8 in [2]).

Section 7.2.2 describes the steps that an external, non-cryptographic device needs to perform in order to implement XMSSMT key and signature generation using a set of cryptographic modules that implement the algorithms in Section 7.2.1. While Algorithms 10' and 12' in Section 7.2.1 have been designed to work with XMSSMT instances that have more than two layers, the algorithms in Section 7.2.2 assume that an XMSSMT instance with exactly two layers is being created.

sk[j] = \(PRF_{keygen}\)(S_XMSS, SEED || ADRS); } // Set the secret key for OTS key i to the array of len // private key values generated for that key. wots_sk[i] = sk; } setWOTS_SK(SK, wots_sk);

if ( L > 0 ) { // M must be the n-byte root from an XMSS public key byte[n] r = 0; // n-byte string of zeros byte[n] M' = M; } else { byte[n] r = PRF(getSK_PRF(SK), toByte(idx_sig, 32)); byte[n] M' = H_msg(r || getRoot(SK) || (toByte(idx_sig, n)), M); } idx_leaf = idx_sig - t * 2^(h / d); Sig = idx_sig || r || treeSig(M', SK, idx_leaf, ADRS); return Sig;

Input: No input

}

Cryptographic modules that implement signature generation for a parameter set shall also implement key generation for that parameter set. Implementations of the key generation and signature algorithms in this document shall only be validated for use within hardware cryptographic modules. The cryptographic modules shall be validated to provide FIPS 140-2 or FIPS 140-3 [19] Level 3 or higher physical security, and the operational environment shall be non-modifiable or limited.⁸ In addition, a cryptographic module that implements the key generation or signature algorithms shall only operate in an approved mode of operation and shall not implement a bypass mode. The cryptographic module shall not allow for the export of private keying material. The entropy source for any approved random bit generator [6] used in the implementation shall be located inside the cryptographic module’s physical boundary.

Cryptographic modules that implement LMS key and signature generation shall support at least one of the LM-OTS parameter sets in Section 4. For each LM-OTS parameter set supported by a cryptographic module, the cryptographic module shall support at least one LMS parameter set from Section 4 that uses the same hash function as the LM-OTS parameter set. Cryptographic modules that implement LMS key and signature generation shall generate random data in accordance with Section 6.1.

Cryptographic modules that implement LMS signature verification shall support at least one of the LM-OTS parameter sets in Section 4. For each LM-OTS parameter set supported by a cryptographic module, the cryptographic module shall support at least one LMS parameter set from Section 4 that uses the same hash function as the LM-OTS parameter set.

Both LMS and XMSS are stateful signature schemes. If an attacker were able to obtain signatures for two different messages created using the same one-time signature (OTS) key, then it would become computationally feasible for that attacker to create forgeries [13]. As noted in [8], extreme care needs to be taken in order to avoid the risk that an OTS key will be reused accidentally. While the conformance requirements in Section 8.1 prevent many of the actions that could result in accidental OTS key reuse, cryptographic modules still need to be carefully designed to ensure that unexpected behavior cannot result in an OTS key being reused.

In order to avoid reuse of an OTS key, the state of the private key must be updated each time a signature is generated. If the private key is stored in non-volatile memory, then the state of the key must be updated in the nonvolatile memory to mark an OTS key as unavailable before the corresponding signature that was generated using the OTS key is exported. Depending on the environment, this can be nontrivial to implement. With many operating systems, simply writing the update to a file is not sufficient because the write operation will be cached with the actual write to non-volatile memory occurring later. If the cryptographic module loses power or crashes before the write to non-volatile memory occurs, then the state update will be lost. If a signature were exported after the write operation was issued, but before the update was written to non-volatile memory, there would be a risk that the OTS key would be used again after the cryptographic module restarts.

Some hardware cryptographic modules implement monotonic counters, which are guaranteed to increment each time the counter’s value is read. When available, using the current value of a monotonic counter to determine which OTS key to use for a signature may be very helpful in avoiding unintentional reuse of an OTS key.

For LMS and XMSS, as for the other approved digital signature schemes [4], the signature generation algorithm is not applied directly to the message but to a message digest generated by the underlying hash function. The security of any signature scheme depends on the inability of an attacker to find distinct messages with the same message digest.

There are two ways that an attacker might find these distinct messages. The attacker could look for a message that has the same message digest as a message that has already been signed (a second preimage), or the attacker could look for any two messages that have the same message digest (a generic collision) and then try to get the private key holder (i.e., signer) to sign one of them [21]. Finding a second preimage is much more difficult than finding a generic collision, and it would be infeasible for an attacker to find a second preimage with any of the hash functions allowed by this recommendation.

LMS and XMSS both use randomized hashing. When a message is presented to be signed, a random value is created and prepended to the message, and the hash function is applied to this expanded message to produce the message digest. Prepending the random value makes it infeasible for anyone other than the signer to find a generic collision because finding a collision would require predicting the randomizing value. The randomized hashing process does not, however, impact the ability of a signer to create a generic collision since the signer, knowing the private key, can choose the random value to prepend to the message.

Consequently, one trade-off for the use of 192-bit hash functions in LMS and XMSS is the weakening of the verifier’s assurance that the signer will not be able to change the message once the signature is revealed. This possibility does not affect the formal security properties of the schemes because it remains the case that only the signer could produce a valid signature on a message.

Although procedures for the revocation of a compromised key are outside the scope of this publication, the implementation of any signature scheme, in principle, should include such a procedure [22]. For implementations of stateful hash-based signature schemes, which would be vulnerable in the event of OTS key reuse, revocation procedures would arguably be even more important.

In practice, however, procedures for revocation that are timely, efficient, and robust are often difficult to implement. For applications with the characteristics described in Section 1.1, the difficulties would likely be magnified.

Barker EB, Kelsey JM (2015) Recommendation for Random Number Generation Using Deterministic Random Bit Generators. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-90A, Rev. 1. https://doi.org/10.6028/NIST.SP.800-90Ar1

Sönmez Turan M, Barker EB, Kelsey JM, McKay KA, Baish ML, Boyle M (2018) Recommendation for the Entropy Sources Used for Random Bit Generation. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-90B. https://doi.org/10.6028/NIST.SP.800-90B

Barker EB, Kelsey JM (2016) Recommendation for Random Bit Generator (RBG) Constructions. (National Institute of Standards and Technology, Gaithersburg, MD), (Second Draft) NIST Special Publication (SP) 800-90C. Available at https://csrc.nist.gov/publications/detail/sp/800-90c/draft

[8]

McGrew D, Kampanakis P, Fluhrer S, Gazdag S, Butin D, Buchmann J (2016) State Management for Hash-Based Signatures. Cryptology ePrint Archive, Report 2016/357. https://eprint.iacr.org/2016/357.pdf

[9]

Genêt A, Kannwischer MJ, Pelletier H, McLauchlan A (2018) Practical Fault Injection Attacks on SPHINCS. Cryptology ePrint Archive, Report 2018/674. https://eprint.iacr.org/2018/674

[10]

Castelnovi L, Martinelli A, Prest T (2018) Grafting trees: A fault attack against the SPHINCS framework. Post-Quantum Cryptography - 9th International Conference (PQCrypto 2018), Lecture Notes in Computer Science 10786, pp 165–184. https://doi.org/10.1007/978-3-319-79063-3_8

[11]

Fluhrer S (2017) Further Analysis of a Proposed Hash-Based Signature Standard. Cryptology ePrint Archive, Report 2017/553. https://eprint.iacr.org/2017/553.pdf

[12]

Buchmann J, Dahmen E, Hulsing A (2011) XMSS – A Practical Forward Secure Signature Scheme based on Minimal Security Assumptions. Cryptology ePrint Archive, Report 2011/484. https://eprint.iacr.org/2011/484.pdf

[13]

Bruinderink LG, Hülsing A (2016) “Oops, I did it again” – Security of One-Time Signatures under Two-Message Attacks. Cryptology ePrint Archive, Report 2016/1042. https://eprint.iacr.org/2016/1042.pdf

[14]

Perlner R, Cooper D (2009) Quantum Resistant Public Key Cryptography: A Survey. 8th Symposium on Identity and Trust on the Internet (IDtrust 2009), pp 85-93. https://doi.org/10.1145/1527017.1527028

[15]

Eaton E (2017) Leighton-Micali Hash-Based Signatures in the Quantum Random-Oracle Model. Cryptology ePrint Archive, Report 2017/607. https://eprint.iacr.org/2017/607

[16]

Bernstein DJ, Hülsing A, Kölbl S, Niederhagen R, Rijneveld J, Schwabe P (2019) The SPHINCS+ Signature Framework. Cryptology ePrint Archive, Report 2019/1086. https://eprint.iacr.org/2019/1086.pdf

[17]

Malkin T, Micciancio D, Miner S (2002) Efficient generic forward-secure signatures with an unbounded number of time periods. Advances in Cryptology — EUROCRYPT 2002, Lecture Notes in Computer Science 2332, pp 400–417. https://doi.org/10.1007/3-540-46035-7_27

[18]

Merkle RC (1979) Security, Authentication, and Public Key Systems. PhD thesis, Stanford University, June 1979. Available at https://www.merkle.com/papers/Thesis1979.pdf

[19]

National Institute of Standards and Technology (2001) Security Requirements for Cryptographic Modules. (U.S. Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) 140-2, Change Notice 2 December 03, 2002. https://doi.org/10.6028/NIST.FIPS.140-2

National Institute of Standards and Technology (2019) Security Requirements for Cryptographic Modules. (U.S. Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) 140-3. https://doi.org/10.6028/NIST.FIPS.140-3

[20]

Chen L, Jordan S, Liu Y-K, Moody D, Peralta R, Perlner RA, Smith-Tone D (2016) Report on Post-Quantum Cryptography. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) 8105. https://doi.org/10.6028/NIST.IR.8105

[21]

Sotirov A, Stevens M, Appelbaum J, Lenstra A, Molnar D, Osvik DA, de Weger B (2008) MD5 considered harmful today: Creating a rogue CA certificate. Available at https://www.win.tue.nl/hashclash/rogue-ca

[22]

Special Publication 800-57 series:

Barker EB (2020) Recommendation for Key Management, Part 1: General. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-57 Part 1, Rev. 5. https://doi.org/10.6028/NIST.SP.800-57pt1r5

Barker EB, Barker WC (2019) Recommendation for Key Management: Part 2 – Best Practices for Key Management Organizations. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-57 Part 2, Rev. 1. https://doi.org/10.6028/NIST.SP.800-57pt2r1

Barker EB, Dang QH (2015) Recommendation for Key Management, Part 3: Application-Specific Key Management Guidance. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-57 Part 3, Rev. 1. https://doi.org/10.6028/NIST.SP.800-57pt3r1

[23]

Housley R (2019) Hash Of Root Key Certificate Extension. (Internet Engineering Task Force (IETF)), IETF Request for Comments (RFC) 8649. https://doi.org/10.17487/RFC8649

In order to support the LM-OTS and LMS parameter sets defined in Sections 4.2 through 4.4, the XDR syntax in Section 3.3 of [2] is extended as follows. For data structures of type enum or union below, the values or case statements specified in this appendix are to be added to the ones specified in Section 3.3 of [2].

The numeric identifiers for the parameter sets defined in Sections 4.2 through 4.4 are marked as “TBD,” as they had not yet been assigned at the time this document was published. Once they are assigned, the numeric identifiers may be found at https://www.iana.org/assignments/leighton-micali-signatures/leighton-micali-signatures.xhtml.

/* one-time signatures */

enum lmots_algorithm_type { lmots_sha256_n24_w1 = TBD, lmots_sha256_n24_w2 = TBD, lmots_sha256_n24_w4 = TBD, lmots_sha256_n24_w8 = TBD, lmots_shake_n32_w1 = TBD, lmots_shake_n32_w2 = TBD, lmots_shake_n32_w4 = TBD, lmots_shake_n32_w8 = TBD, lmots_shake_n24_w1 = TBD, lmots_shake_n24_w2 = TBD, lmots_shake_n24_w4 = TBD, lmots_shake_n24_w8 = TBD };

typedef opaque bytestring24[24];

struct lmots_signature_n24_p200 { bytestring24 C; bytestring24 y[200]; };

struct lmots_signature_n24_p101 { bytestring24 C; bytestring24 y[101]; };

struct lmots_signature_n24_p51 { bytestring24 C; bytestring24 y[51]; };

struct lmots_signature_n24_p26 { bytestring24 C; bytestring24 y[26]; };

union lmots_signature switch (lmots_algorithm_type type) { case lmots_sha256_n24_w1: lmots_signature_n24_p200 sig_n24_p200; case lmots_sha256_n24_w2: lmots_signature_n24_p101 sig_n24_p101; case lmots_sha256_n24_w4: lmots_signature_n24_p51 sig_n24_p51; case lmots_sha256_n24_w8: lmots_signature_n24_p26 sig_n24_p26; case lmots_shake_n32_w1: lmots_signature_n32_p265 sig_n32_p265; case lmots_shake_n32_w2: lmots_signature_n32_p133 sig_n32_p133; case lmots_shake_n32_w4: lmots_signature_n32_p67 sig_n32_p67; case lmots_shake_n32_w8: lmots_signature_n32_p34 sig_n32_p34; case lmots_shake_n24_w1: lmots_signature_n24_p200 sig_n24_p200; case lmots_shake_n24_w2: lmots_signature_n24_p101 sig_n24_p101; case lmots_shake_n24_w4: lmots_signature_n24_p51 sig_n24_p51; case lmots_shake_n24_w8: lmots_signature_n24_p26 sig_n24_p26; };

/* hash-based signatures (hbs) */

enum lms_algorithm_type { lms_sha256_n24_h5 = TBD, lms_sha256_n24_h10 = TBD, lms_sha256_n24_h15 = TBD, lms_sha256_n24_h20 = TBD, lms_sha256_n24_h25 = TBD, lms_shake_n32_h5 = TBD, lms_shake_n32_h10 = TBD, lms_shake_n32_h15 = TBD, lms_shake_n32_h20 = TBD, lms_shake_n32_h25 = TBD, lms_shake_n24_h5 = TBD, lms_shake_n24_h10 = TBD, lms_shake_n24_h15 = TBD, lms_shake_n24_h20 = TBD, lms_shake_n24_h25 = TBD };

/* leighton-micali signatures (lms) */

union lms_path switch (lms_algorithm_type type) { case lms_sha256_n24_h5: case lms_shake_n24_h5: bytestring24 path_n24_h5[5]; case lms_sha256_n24_h10: case lms_shake_n24_h10: bytestring24 path_n24_h10[10]; case lms_sha256_n24_h15: case lms_shake_n24_h15: bytestring24 path_n24_h15[15]; case lms_sha256_n24_h20: case lms_shake_n24_h20: bytestring24 path_n24_h20[20]; case lms_sha256_n24_h25: case lms_shake_n24_h25: bytestring24 path_n24_h25[25];

case lms_shake_n32_h5: bytestring32 path_n32_h5[5]; case lms_shake_n32_h10: bytestring32 path_n32_h10[10]; case lms_shake_n32_h15: bytestring32 path_n32_h15[15]; case lms_shake_n32_h20: bytestring32 path_n32_h20[20]; case lms_shake_n32_h25: bytestring32 path_n32_h25[25]; };

struct lms_key_n24 { lmots_algorithm_type ots_alg_type; opaque I[16]; opaque K[24]; };

union lms_public_key switch (lms_algorithm_type type) { case lms_sha256_n24_h5: case lms_sha256_n24_h10: case lms_sha256_n24_h15: case lms_sha256_n24_h20: case lms_sha256_n24_h25: case lms_shake_n24_h5: case lms_shake_n24_h10: case lms_shake_n24_h15: case lms_shake_n24_h20: case lms_shake_n24_h25: lms_key_n24 z_n24;

case lms_shake_n32_h5: case lms_shake_n32_h10: case lms_shake_n32_h15: case lms_shake_n32_h20: case lms_shake_n32_h25: lms_key_n32 z_n32; };

In order to support the XMSS parameter sets defined in Sections 5.2 through 5.4, the XDR syntax in Appendices A, B, and C of [1] is extended as follows. For data structures of type enum or union below, the values or case statements specified in this appendix are to be added to the ones specified in Appendices A, B, and C of [1].

/* ots_algorithm_type identifies a particular signature algorithm */

enum ots_algorithm_type { wotsp-sha2_192 = 0x00000005, wotsp-shake256_256 = 0x00000006, wotsp-shake256_192 = 0x00000007, };

/* Byte strings */

typedef opaque bytestring24[24];

union ots_signature switch (ots_algorithm_type type) {

case wotsp-sha2_192: case wotsp-shake256_192: bytestring24 ots_sig_n24_len51[51];

case wotsp-shake256_256: bytestring32 ots_sig_n32_len67[67]; };

union ots_pubkey switch (ots_algorithm_type type) { case wotsp-sha2_192: case wotsp-shake256_192: bytestring24 ots_pubk_n24_len51[51];

case wotsp-shake256_256: bytestring32 ots_pubk_n32_len67[67]; };

/* Definition of parameter sets */

enum xmss_algorithm_type { xmss-sha2_10_192 = 0x0000000D, xmss-sha2_16_192 = 0x0000000E, xmss-sha2_20_192 = 0x0000000F,

xmss-shake256_10_256 = 0x00000010, xmss-shake256_16_256 = 0x00000011, xmss-shake256_20_256 = 0x00000012,

xmss-shake256_10_192 = 0x00000013, xmss-shake256_16_192 = 0x00000014, xmss-shake256_20_192 = 0x00000015, };

/* Authentication path types */

union xmss_path switch (xmss_algorithm_type type) { case xmss-sha2_10_192: case xmss-shake256_10_192:

bytestring24 path_n24_t10[10];

case xmss-shake256_10_256: bytestring32 path_n32_t10[10];

case xmss-sha2_16_192: case xmss-shake256_16_192: bytestring24 path_n24_t16[16];

case xmss-shake256_16_256: bytestring32 path_n32_t16[16];

case xmss-sha2_20_192: case xmss-shake256_20_192: bytestring24 path_n24_t20[20];

case xmss-shake256_20_256: bytestring32 path_n32_t20[20]; };

/* Types for XMSS random strings */

union random_string_xmss switch (xmss_algorithm_type type) { case xmss-sha2_10_192: case xmss-sha2_16_192: case xmss-sha2_20_192: case xmss-shake256_10_192: case xmss-shake256_16_192: case xmss-shake256_20_192:

bytestring24 rand_n24; case xmss-shake256_10_256: case xmss-shake256_16_256: case xmss-shake256_20_256: bytestring32 rand_n32; };

/* Corresponding WOTS+ type for given XMSS type */

union xmss_ots_signature switch (xmss_algorithm_type type) { case xmss-sha2_10_192: case xmss-sha2_16_192: case xmss-sha2_20_192:

wotsp-sha2_192;

case xmss-shake256_10_256: case xmss-shake256_16_256: case xmss-shake256_20_256: wotsp-shake256_256;

case xmss-shake256_10_192: case xmss-shake256_16_192: case xmss-shake256_20_192: wotsp-shake256_192; };

/* Types for bitmask seed */

union seed switch (xmss_algorithm_type type) { case xmss-sha2_10_192: case xmss-sha2_16_192: case xmss-sha2_20_192: case xmss-shake256_10_192: case xmss-shake256_16_192: case xmss-shake256_20_192:

bytestring24 seed_n24;

case xmss-shake256_10_256: case xmss-shake256_16_256: case xmss-shake256_20_256: bytestring32 seed_n32; };

/* Types for XMSS root node */

union xmss_root switch (xmss_algorithm_type type) { case xmss-sha2_10_192: case xmss-sha2_16_192: case xmss-sha2_20_192: case xmss-shake256_10_192: case xmss-shake256_16_192: case xmss-shake256_20_192: bytestring24 root_n24;

case xmss-shake256_10_256: case xmss-shake256_16_256: case xmss-shake256_20_256: bytestring32 root_n32; };

/* Definition of parameter sets */

enum xmssmt_algorithm_type {

xmssmt-sha2_20/2_192 = 0x00000021, xmssmt-sha2_20/4_192 = 0x00000022, xmssmt-sha2_40/2_192 = 0x00000023, xmssmt-sha2_40/4_192 = 0x00000024, xmssmt-sha2_40/8_192 = 0x00000025, xmssmt-sha2_60/3_192 = 0x00000026, xmssmt-sha2_60/6_192 = 0x00000027, xmssmt-sha2_60/12_192 = 0x00000028,

xmssmt-shake256_20/2_256 = 0x00000029, xmssmt-shake256_20/4_256 = 0x0000002A, xmssmt-shake256_40/2_256 = 0x0000002B, xmssmt-shake256_40/4_256 = 0x0000002C, xmssmt-shake256_40/8_256 = 0x0000002D, xmssmt-shake256_60/3_256 = 0x0000002E, xmssmt-shake256_60/6_256 = 0x0000002F, xmssmt-shake256_60/12_256 = 0x00000030,

xmssmt-shake256_20/2_192 = 0x00000031, xmssmt-shake256_20/4_192 = 0x00000032, xmssmt-shake256_40/2_192 = 0x00000033, xmssmt-shake256_40/4_192 = 0x00000034, xmssmt-shake256_40/8_192 = 0x00000035, xmssmt-shake256_60/3_192 = 0x00000036, xmssmt-shake256_60/6_192 = 0x00000037, xmssmt-shake256_60/12_192 = 0x00000038, };

/* Type for XMSS^MT key pair index */

/* Depends solely on h */

union idx_sig_xmssmt switch (xmss_algorithm_type type) { case xmssmt-sha2_20/2_192: case xmssmt-sha2_20/4_192: case xmssmt-shake256_20/2_256: case xmssmt-shake256_20/4_256: case xmssmt-shake256_20/2_192: case xmssmt-shake256_20/4_192:

bytestring3 idx3;

case xmssmt-sha2_40/2_192: case xmssmt-sha2_40/4_192: case xmssmt-sha2_40/8_192: case xmssmt-shake256_40/2_256: case xmssmt-shake256_40/4_256: case xmssmt-shake256_40/8_256: case xmssmt-shake256_40/2_192: case xmssmt-shake256_40/4_192: case xmssmt-shake256_40/8_192: bytestring5 idx5;

case xmssmt-sha2_60/3_192: case xmssmt-sha2_60/6_192: case xmssmt-sha2_60/12_192: case xmssmt-shake256_60/3_256: case xmssmt-shake256_60/6_256: case xmssmt-shake256_60/12_256: case xmssmt-shake256_60/3_192: case xmssmt-shake256_60/6_192: case xmssmt-shake256_60/12_192: bytestring8 idx8; };

union random_string_xmssmt switch (xmssmt_algorithm_type type) { case xmssmt-sha2_20/2_192: case xmssmt-sha2_20/4_192: case xmssmt-sha2_40/2_192: case xmssmt-sha2_40/4_192: case xmssmt-sha2_40/8_192: case xmssmt-sha2_60/3_192: case xmssmt-sha2_60/6_192: case xmssmt-sha2_60/12_192: case xmssmt-shake256_20/2_192: case xmssmt-shake256_20/4_192: case xmssmt-shake256_40/2_192: case xmssmt-shake256_40/4_192: case xmssmt-shake256_40/8_192: case xmssmt-shake256_60/3_192: case xmssmt-shake256_60/6_192: case xmssmt-shake256_60/12_192: bytestring24 rand_n24;

case xmssmt-shake256_20/2_256: case xmssmt-shake256_20/4_256: case xmssmt-shake256_40/2_256: case xmssmt-shake256_40/4_256: case xmssmt-shake256_40/8_256: case xmssmt-shake256_60/3_256: case xmssmt-shake256_60/6_256: case xmssmt-shake256_60/12_256: bytestring32 rand_n32; };

/* Type for reduced XMSS signatures */

union xmss_reduced (xmss_algorithm_type type) { case xmssmt-sha2_20/2_192: case xmssmt-sha2_40/4_192: case xmssmt-sha2_60/6_192: case xmssmt-shake256_20/2_192: case xmssmt-shake256_40/4_192: case xmssmt-shake256_60/6_192: bytestring24 xmss_reduced_n24_t61[61];

case xmssmt-sha2_20/4_192: case xmssmt-sha2_40/8_192: case xmssmt-sha2_60/12_192: case xmssmt-shake256_20/4_192: case xmssmt-shake256_40/8_192: case xmssmt-shake256_60/12_192: bytestring24 xmss_reduced_n24_t56[56];

case xmssmt-sha2_40/2_192: case xmssmt-sha2_60/3_192: case xmssmt-shake256_40/2_192: case xmssmt-shake256_60/3_192: bytestring24 xmss_reduced_n24_t71[71];

case xmssmt-shake256_20/2_256: case xmssmt-shake256_40/4_256: case xmssmt-shake256_60/6_256: bytestring32 xmss_reduced_n32_t77[77]; case xmssmt-shake256_20/4_256: case xmssmt-shake256_40/8_256: case xmssmt-shake256_60/12_256: bytestring32 xmss_reduced_n32_t72[72];

case xmssmt-shake256_40/2_256: case xmssmt-shake256_60/3_256: bytestring32 xmss_reduced_n32_t87[87]; };

/* xmss_reduced_array depends on d */

union xmss_reduced_array (xmss_algorithm_type type) { case xmssmt-sha2_20/2_192: case xmssmt-sha2_40/2_192: case xmssmt-shake256_20/2_256: case xmssmt-shake256_40/2_256: case xmssmt-shake256_20/2_192: case xmssmt-shake256_40/2_192:

xmss_reduced xmss_red_arr_d2[2];

case xmssmt-sha2_60/3_192: case xmssmt-shake256_60/3_256: case xmssmt-shake256_60/3_192: xmss_reduced xmss_red_arr_d3[3];

case xmssmt-sha2_20/4_192: case xmssmt-sha2_40/4_192: case xmssmt-shake256_20/4_256: case xmssmt-shake256_40/4_256: case xmssmt-shake256_20/4_192: case xmssmt-shake256_40/4_192: xmss_reduced xmss_red_arr_d4[4];

case xmssmt-sha2_60/6_192: case xmssmt-shake256_60/6_256: case xmssmt-shake256_60/6_192: xmss_reduced xmss_red_arr_d6[6];

case xmssmt-sha2_40/8_192: case xmssmt-shake256_40/8_256: case xmssmt-shake256_40/8_192: xmss_reduced xmss_red_arr_d8[8];

case xmssmt-sha2_60/12_192: case xmssmt-shake256_60/12_256: case xmssmt-shake256_60/12_192: xmss_reduced xmss_red_arr_d12[12];

};

/* Types for bitmask seed */

union seed switch (xmssmt_algorithm_type type) { case xmssmt-sha2_20/2_192: case xmssmt-sha2_20/4_192: case xmssmt-sha2_40/2_192: case xmssmt-sha2_40/4_192: case xmssmt-sha2_40/8_192: case xmssmt-sha2_60/3_192: case xmssmt-sha2_60/6_192: case xmssmt-sha2_60/12_192: case xmssmt-shake256_20/2_192: case xmssmt-shake256_20/4_192: case xmssmt-shake256_40/2_192: case xmssmt-shake256_40/4_192: case xmssmt-shake256_40/8_192: case xmssmt-shake256_60/3_192: case xmssmt-shake256_60/6_192: case xmssmt-shake256_60/12_192:

bytestring24 seed_n24;

case xmssmt-shake256_20/2_256: case xmssmt-shake256_20/4_256: case xmssmt-shake256_40/2_256: case xmssmt-shake256_40/4_256: case xmssmt-shake256_40/8_256: case xmssmt-shake256_60/3_256: case xmssmt-shake256_60/6_256: case xmssmt-shake256_60/12_256: bytestring32 seed_n32;

};

/* Types for XMSS^MT root node */

union xmssmt_root switch (xmssmt_algorithm_type type) { case xmssmt-sha2_20/2_192: case xmssmt-sha2_20/4_192: case xmssmt-sha2_40/2_192: case xmssmt-sha2_40/4_192: case xmssmt-sha2_40/8_192: case xmssmt-sha2_60/3_192: case xmssmt-sha2_60/6_192: case xmssmt-sha2_60/12_192: case xmssmt-shake256_20/2_192: case xmssmt-shake256_20/4_192: case xmssmt-shake256_40/2_192: case xmssmt-shake256_40/4_192: case xmssmt-shake256_40/8_192: case xmssmt-shake256_60/3_192: case xmssmt-shake256_60/6_192: case xmssmt-shake256_60/12_192: bytestring24 root_n24;

case xmssmt-shake256_20/2_256: case xmssmt-shake256_20/4_256: case xmssmt-shake256_40/2_256: case xmssmt-shake256_40/4_256: case xmssmt-shake256_40/8_256: case xmssmt-shake256_60/3_256: case xmssmt-shake256_60/6_256: case xmssmt-shake256_60/12_256: bytestring32 root_n32; };

This appendix briefly summarizes the formal security model and proofs of security of the LMS and XMSS signature schemes and provides a short discussion comparing these models and proofs.

It is therefore desirable to have a cryptographic security proof that avoids using the random oracle model. However, this often leads to less efficient cryptographic systems, or it is not yet known how to perform a proof without appealing to the random oracle model, or both. So, as a matter of real-world pragmatism, the ROM is commonly used.

C.3 LMS Security Proof

In [11], the author considers a particular experiment in the random oracle model in which the adversary is given a series of strings with prefixes (in a randomly chosen but structured manner) and hash targets. The attacker’s goal is to find one more string that has the same prefix and hash target as any of its input strings. The author proves an upper bound on the adversary’s ability to compute first or second preimages from these strings (by querying the compression function modeled as a random oracle).

Then, the author reduces the problem of forging a signature in LMS to this stated experiment, concluding that the same upper bounds apply to the problem of producing forgeries against LMS. This random oracle model proof critically depends on the randomness of the prefixes used in LMS, which means that LMS in the real world critically depends on the pseudorandomness of the prefixes.

Further, in [15], the same proof is carried out in the QROM.

C.4 XMSS Security Proof

In [12], a security analysis for the original (academic publication) version of XMSS is given under the following assumptions:

The proof in [12] asserts that if both of these assumptions are true, then XMSS is existentially unforgeable under adaptive chosen message attacks (EUF-CMA) in the standard model.

In a little more detail, the current version of XMSS uses two types of assumptions:

C.5 Comparison of the Security Models and Proofs of LMS and XMSS

Generally speaking, both LMS and XMSS are supported by sound security proofs under commonly used cryptographic hardness assumptions. That is, if these cryptographic assumptions are true, then both schemes are provably shown to be existentially unforgeable under chosen message attack, even against an adversary that has access to a large-scale quantum computer for use in its forgery attack.

Therefore, the cryptographic hardness assumptions made by LMS and XMSS in order to achieve existential unforgeability under chosen message attack (EUF-CMA) may be viewed as substantially similar and worthy of essentially equal confidence. As such, the practitioner’s decision to deploy one scheme or the other should primarily depend on other factors, such as the efficiency demands for a given deployment environment or the other security considerations enumerated earlier in this document.