NIST public full text Public Domain

NIST FIPS 205: Stateless Hash-Based Digital Signature Standard

National Institute of Standards and Technology · National Institute of Standards and Technology (NIST)

NIST · Standards · License: Public Domain

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

FIPS 205 Federal Information Processing Standards Publication

Stateless Hash-Based Digital Signature Standard Category: Computer Security

Subcategory: Cryptography

Information Technology Laboratory National Institute of Standards and Technology Gaithersburg, MD 20899-8900 This publication is available free of charge from: https://doi.org/10.6028/NIST.FIPS.205 Published: August 13, 2024

U.S. Department of Commerce Gina M. Raimondo, Secretary National Institute of Standards and Technology Laurie E. Locascio, NIST Director and Under Secretary of Commerce for Standards and Technology

Foreword The Federal Information Processing Standards Publication (FIPS) series of the National Institute of Standards and Technology (NIST) is the official series of publications relating to standards and guidelines developed under 15 U.S.C. 278g-3, and issued by the Secretary of Commerce under 40 U.S.C. 11331. Comments concerning this Federal Information Processing Standard publication are welcomed and should be submitted using the contact information in the “Inquiries and comments” clause of the announcement section. Kevin M. Stine, Director Information Technology Laboratory

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

Abstract This standard specifies the stateless hash-based digital signature algorithm (SLH-DSA). Digital signatures are used to detect unauthorized modifications to data and to authenticate the identity of the signatory. In addition, the recipient of signed data can use a digital signature as evidence in demonstrating to a third party that the signature was, in fact, generated by the claimed signatory. This is known as non-repudiation since the signatory cannot easily repudiate the signature at a later time. SLH-DSA is based on SPHINCS+ , which was selected for standardization as part of the NIST Post-Quantum Cryptography Standardization process. Keywords: computer security; cryptography; digital signatures; Federal Information Processing Standards; hash-based signatures; post-quantum; public-key cryptography.

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

Federal Information Processing Standards Publication 205 Published: August 13, 2024 Effective: August 13, 2024

Announcing the

Stateless Hash-Based Digital Signature Standard Federal Information Processing Standards (FIPS) publications are developed by the National Institute of Standards and Technology (NIST) under 15 U.S.C. 278g-3 and issued by the Secretary of Commerce under 40 U.S.C. 11331. 1. Name of Standard. Stateless Hash-Based Digital Signature Standard (FIPS 205). 2. Category of Standard. Computer Security. Subcategory. Cryptography. 3. Explanation. This standard specifies a stateless hash-based digital signature scheme (SLHDSA) for applications that require a digital signature rather than a written signature. Additional digital signature schemes are specified and approved in other NIST Special Publications and FIPS publications (e.g., FIPS 186-5 [1]). A digital signature is represented in a computer as a string of bits and computed using a set of rules and parameters that allow the identity of the signatory and the integrity of the data to be verified. Digital signatures may be generated on both stored and transmitted data. Signature generation uses a private key to generate a digital signature. Signature verification uses a public key that corresponds to but is not the same as the private key. Each signatory possesses a private and public key pair. Public keys may be known by the public, but private keys must be kept secret. Anyone can verify the signature by employing the signatory’s public key. Only the user who possesses the private key can perform signature generation. The digital signature is provided to the intended verifier along with the signed data. The verifying entity verifies the signature by using the claimed signatory’s public key. Similar procedures may be used to generate and verify signatures for both stored and transmitted data. This standard specifies several parameter sets for SLH-DSA that are approved for use. Additional parameter sets may be specified and approved in future NIST Special Publications. 4. Approving Authority. Secretary of Commerce. 5. Maintenance Agency. Department of Commerce, National Institute of Standards and Technology, Information Technology Laboratory (ITL). 6. Applicability. This standard is applicable to all federal departments and agencies for the protection of sensitive unclassified information that is not subject to section 2315 of Title 10, United States Code, or section 3502 (2) of Title 44, United States Code. Either this standard, FIPS 204, FIPS 186-5, or NIST Special Publication 800-208 shall be used in designing and implementing public-key-based signature systems that federal departments and agencies operate or that are operated for them under contract. In the future, additional digital signature i

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

schemes may be specified and approved in FIPS publications or NIST Special Publications. The adoption and use of this standard are available to private and commercial organizations. 7. Applications. A digital signature algorithm allows an entity to authenticate the integrity of signed data and the identity of the signatory. The recipient of a signed message can use a digital signature as evidence in demonstrating to a third party that the signature was, in fact, generated by the claimed signatory. This is known as non-repudiation since the signatory cannot easily repudiate the signature at a later time. A digital signature algorithm is intended for use in electronic mail, electronic funds transfer, electronic data interchange, software distribution, data storage, and other applications that require data integrity assurance and data origin authentication. 8. Implementations. A digital signature algorithm may be implemented in software, firmware, hardware, or any combination thereof. NIST will develop a validation program to test implementations for conformance to the algorithms in this standard. For every computational procedure that is specified in this standard, a conforming implementation may replace the given set of steps with any mathematically equivalent process. In other words, different procedures that produce the correct output for every input are permitted. Information about validation programs is available at https://csrc.nist.gov/projects/cmvp. Examples for digital signature algorithms are available at https://csrc.nist.gov/projects/cryptographic-standardsand-guidelines/example-values. Agencies are advised that digital signature key pairs shall not be used for other purposes. 9. Other Approved Security Functions. Digital signature implementations that comply with this standard shall employ cryptographic algorithms that have been approved for protecting Federal Government-sensitive information. Approved cryptographic algorithms and techniques include those that are either: a. Specified in a Federal Information Processing Standard (FIPS) publication, b. Adopted in a FIPS or NIST recommendation, or c. Specified in the list of approved security functions in SP 800-140C. 10. Export Control. Certain cryptographic devices and technical data regarding them are subject to federal export controls. Exports of cryptographic modules that implement this standard and technical data regarding them must comply with these federal regulations and be licensed by the Bureau of Industry and Security of the U.S. Department of Commerce. Information about export regulations is available at https://www.bis.doc.gov. 11. Patents. The algorithm in this standard may be covered by U.S. or foreign patents. 12. Implementation Schedule. This standard becomes effective immediately upon final publication. 13. Specifications. Federal Information Processing Standard (FIPS) 205, Stateless Hash-Based Digital Signature Standard (affixed).

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

14. Qualifications. The security of a digital signature system depends on the secrecy of the signatory’s private keys. Signatories shall, therefore, guard against the disclosure of their private keys. While it is the intent of this standard to specify general security requirements for generating digital signatures, conformance to this standard does not ensure that a particular implementation is secure. It is the responsibility of an implementer to ensure that any module that implements a digital signature capability is designed and built in a secure manner. Similarly, the use of a product containing an implementation that conforms to this standard does not guarantee the security of the overall system in which the product is used. The responsible authority in each agency or department shall ensure that an overall implementation provides an acceptable level of security. Since a standard of this nature must be flexible enough to adapt to advancements and innovations in science and technology, this standard will be reviewed every five years in order to assess its adequacy. 15. Waiver Procedure. The Federal Information Security Management Act (FISMA) does not allow for waivers to Federal Information Processing Standards (FIPS) that are made mandatory by the Secretary of Commerce. 16. Where to Obtain Copies of the Standard. This publication is available by accessing https: //csrc.nist.gov/publications. Other computer security publications are available at the same website. 17. How to Cite This Publication. NIST has assigned NIST FIPS 205 as the publication identifier for this FIPS, per the NIST Technical Series Publication Identifier Syntax. NIST recommends that it be cited as follows: National Institute of Standards and Technology (2024) Stateless Hash-Based Digital Signature Standard. (Department of Commerce, Washington, D.C.), Federal Information Processing Standards Publication (FIPS) NIST FIPS 205. https: //doi.org/10.6028/NIST.FIPS.205 18. Inquiries and Comments. Inquiries and comments about this FIPS may be submitted to fips-205-comments@nist.gov.

iii

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

Federal Information Processing Standards Publication 205 Specification for the

Stateless Hash-Based Digital Signature Standard Table of Contents 1 Introduction

1.1

Purpose and Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2

Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Glossary of Terms, Acronyms, and Symbols

2.1 Terms and Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3

Mathematical Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Overview of the SLH-DSA Signature Scheme

3.1 Additional Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2

Implementation Considerations . . . . . . . . . . . . . . . . . . . . . . . . .

4 Functions and Addressing 4.1

Hash Functions and Pseudorandom Functions . . . . . . . . . . . . . . . . .

4.2 Addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3

Member Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.4 Arrays, Byte Strings, and Integers . . . . . . . . . . . . . . . . . . . . . . . .

5 Winternitz One-Time Signature Plus Scheme

5.1 WOTS+ Public-Key Generation . . . . . . . . . . . . . . . . . . . . . . . . . .

5.2 WOTS+ Signature Generation . . . . . . . . . . . . . . . . . . . . . . . . . .

Computing a WOTS+ Public Key From a Signature . . . . . . . . . . . . . . .

5.3

6 eXtended Merkle Signature Scheme (XMSS)

6.1

Generating a Merkle Hash Tree . . . . . . . . . . . . . . . . . . . . . . . . .

6.2

Generating an XMSS Signature . . . . . . . . . . . . . . . . . . . . . . . . . .

6.3

Computing an XMSS Public Key From a Signature . . . . . . . . . . . . . . . .

7 The SLH-DSA Hypertree

26 iv

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

7.1

Hypertree Signature Generation . . . . . . . . . . . . . . . . . . . . . . . . .

7.2

Hypertree Signature Verification . . . . . . . . . . . . . . . . . . . . . . . . .

8 Forest of Random Subsets (FORS)

8.1

Generating FORS Secret Values . . . . . . . . . . . . . . . . . . . . . . . . . .

8.2

Generating a Merkle Hash Tree . . . . . . . . . . . . . . . . . . . . . . . . .

8.3

Generating a FORS Signature . . . . . . . . . . . . . . . . . . . . . . . . . . .

8.4

Computing a FORS Public Key From a Signature . . . . . . . . . . . . . . . . .

9 SLH-DSA Internal Functions

9.1

SLH-DSA Key Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9.2

SLH-DSA Signature Generation . . . . . . . . . . . . . . . . . . . . . . . . . .

9.3

SLH-DSA Signature Verification . . . . . . . . . . . . . . . . . . . . . . . . . .

10 SLH-DSA External Functions

10.1 SLH-DSA Key Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10.2 SLH-DSA Signature Generation . . . . . . . . . . . . . . . . . . . . . . . . . . 10.2.1 Pure SLH-DSA Signature Generation . . . . . . . . . . . . . . . . . . . 10.2.2 HashSLH-DSA Signature Generation . . . . . . . . . . . . . . . . . . . 10.3 SLH-DSA Signature Verification . . . . . . . . . . . . . . . . . . . . . . . . . .

37 38 39 41

11 Parameter Sets

11.1 SLH-DSA Using SHAKE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11.2 SLH-DSA Using SHA2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2.1 SLH-DSA Using SHA2 for Security Category 1 . . . . . . . . . . . . . . . 11.2.2 SLH-DSA Using SHA2 for Security Categories 3 and 5 . . . . . . . . . .

44 45 46

References

Appendix A — Differences From the SPHINCS+ Submission

A.1 Changes From FIPS 205 Initial Public Draft . . . . . . . . . . . . . . . . . . . .

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

List of Tables Table 1 Table 2 Table 3

Member functions for addresses . . . . . . . . . . . . . . . . . . . . . . SLH-DSA parameter sets . . . . . . . . . . . . . . . . . . . . . . . . . . Member functions for compressed addresses . . . . . . . . . . . . . . .

14 43 45

List of Figures Figure 1 Figure 2 Figure 3 Figure 4 Figure 5 Figure 6 Figure 7 Figure 8 Figure 9 Figure 10 Figure 11 Figure 12 Figure 13 Figure 14 Figure 15 Figure 16 Figure 17 Figure 18

An SLH-DSA signature . . . . . . . . . . . . . . . . . . . . . . . . . . . Address (ADRS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . WOTS+ hash address . . . . . . . . . . . . . . . . . . . . . . . . . . . WOTS+ public-key compression address . . . . . . . . . . . . . . . . . Hash tree address . . . . . . . . . . . . . . . . . . . . . . . . . . . . . FORS tree address . . . . . . . . . . . . . . . . . . . . . . . . . . . . . FORS tree roots compression address . . . . . . . . . . . . . . . . . . . WOTS+ key generation address . . . . . . . . . . . . . . . . . . . . . . FORS key generation address . . . . . . . . . . . . . . . . . . . . . . . WOTS+ signature data format . . . . . . . . . . . . . . . . . . . . . . . XMSS signature data format . . . . . . . . . . . . . . . . . . . . . . . . Merkle hash tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HT signature data format . . . . . . . . . . . . . . . . . . . . . . . . . FORS signature data format . . . . . . . . . . . . . . . . . . . . . . . . SLH-DSA private key . . . . . . . . . . . . . . . . . . . . . . . . . . . . SLH-DSA public key . . . . . . . . . . . . . . . . . . . . . . . . . . . . . SLH-DSA signature data format . . . . . . . . . . . . . . . . . . . . . . Compressed address (ADRS𝑐 ) . . . . . . . . . . . . . . . . . . . . . .

8 12 12 12 13 13 13 14 14 19 22 24 26 29 33 33 34 45

List of Algorithms Algorithm 1 Algorithm 2 Algorithm 3 Algorithm 4 Algorithm 5 Algorithm 6 Algorithm 7 Algorithm 8 Algorithm 9 Algorithm 10 Algorithm 11 Algorithm 12 Algorithm 13 Algorithm 14

gen_len2 (𝑛, 𝑙𝑔𝑤 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . toInt(𝑋, 𝑛) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . toByte(𝑥, 𝑛) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . base_2b (𝑋, 𝑏, 𝑜𝑢𝑡_𝑙𝑒𝑛) . . . . . . . . . . . . . . . . . . . . . . . . chain(𝑋, 𝑖, 𝑠, PK.seed, ADRS) . . . . . . . . . . . . . . . . . . . wots_pkGen(SK.seed, PK.seed, ADRS) . . . . . . . . . . . . . . wots_sign(𝑀, SK.seed, PK.seed, ADRS) . . . . . . . . . . . . . wots_pkFromSig(𝑠𝑖𝑔, 𝑀, PK.seed, ADRS) . . . . . . . . . . . . . xmss_node(SK.seed, 𝑖, 𝑧, PK.seed, ADRS) . . . . . . . . . . . . xmss_sign(𝑀, SK.seed, 𝑖𝑑𝑥, PK.seed, ADRS) . . . . . . . . . . . xmss_pkFromSig(𝑖𝑑𝑥, SIG𝑋𝑀𝑆𝑆 , 𝑀, PK.seed, ADRS) . . . . . . . ht_sign(𝑀, SK.seed, PK.seed, 𝑖𝑑𝑥𝑡𝑟𝑒𝑒 , 𝑖𝑑𝑥𝑙𝑒𝑎𝑓 ) . . . . . . . . . . ht_verify(𝑀, SIG𝐻𝑇 , PK.seed, 𝑖𝑑𝑥𝑡𝑟𝑒𝑒 , 𝑖𝑑𝑥𝑙𝑒𝑎𝑓 , PK.root) . . . . . . fors_skGen(SK.seed, PK.seed, ADRS, 𝑖𝑑𝑥) . . . . . . . . . . . . vi

10 15 15 16 18 18 20 21 23 24 25 27 28 29

FIPS 205

Algorithm 15 Algorithm 16 Algorithm 17 Algorithm 18 Algorithm 19 Algorithm 20 Algorithm 21 Algorithm 22 Algorithm 23 Algorithm 24 Algorithm 25

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

fors_node(SK.seed, 𝑖, 𝑧, PK.seed, ADRS) . . . . . . . . . . . . . fors_sign(𝑚𝑑, SK.seed, PK.seed, ADRS) . . . . . . . . . . . . . fors_pkFromSig(SIG𝐹 𝑂𝑅𝑆 , 𝑚𝑑, PK.seed, ADRS) . . . . . . . . . . slh_keygen_internal(SK.seed, SK.prf, PK.seed) . . . . . . . . . . slh_sign_internal(𝑀, SK, 𝑎𝑑𝑑𝑟𝑛𝑑) . . . . . . . . . . . . . . . . . . . slh_verify_internal(𝑀, SIG, PK) . . . . . . . . . . . . . . . . . . . . slh_keygen() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slh_sign(𝑀, 𝑐𝑡𝑥, SK) . . . . . . . . . . . . . . . . . . . . . . . . . . hash_slh_sign(𝑀, 𝑐𝑡𝑥, PH, SK) . . . . . . . . . . . . . . . . . . . . . slh_verify(𝑀, SIG, 𝑐𝑡𝑥, PK) . . . . . . . . . . . . . . . . . . . . . . . hash_slh_verify(𝑀, SIG, 𝑐𝑡𝑥, PH, PK) . . . . . . . . . . . . . . . . .

vii

30 31 32 34 35 36 37 39 40 41 42

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

Introduction

1.1 Purpose and Scope This standard defines a method for digital signature generation that can be used for the protection of binary data (commonly called a message) and for the verification and validation of those digital signatures.1 The security of the stateless hash-based digital signature algorithm (SLH-DSA) relies on the presumed difficulty of finding preimages for hash functions as well as several related properties of the same hash functions. Unlike the algorithms specified in FIPS 186-5 [1], SLH-DSA is designed to provide resistance against attacks from a large-scale quantum computer. This standard specifies the mathematical steps that need to be performed for key generation, signature generation, and signature verification. Additional assurances are required for digital signatures to be valid (e.g., the assurance of identity and private key possession). SP 800-89, Recommendation for Obtaining Assurances for Digital Signature Applications [3], specifies the required assurances and the methods for obtaining these assurances.

1.2 Context Over the past several years, there has been steady progress toward building quantum computers. The security of many commonly used public-key cryptosystems will be at risk if large-scale quantum computers are ever realized. This would include key-establishment schemes and digital signatures that are based on integer factorization and discrete logarithms (both over finite fields and elliptic curves). As a result, in 2016, NIST initiated a public Post-Quantum Cryptography (PQC) Standardization process to select quantum-resistant public-key cryptographic algorithms for standardization. A total of 82 candidate algorithms were submitted to NIST for consideration. After three rounds of evaluation and analysis, NIST selected the first four algorithms for standardization. These algorithms are intended to protect sensitive U.S. Government information well into the foreseeable future, including after the advent of cryptographically relevant quantum computers. This standard includes the specification for one of the algorithms selected: SPHINCS+ , a stateless hash-based digital signature scheme. This standard contains several minor modifications compared to Version 3 [4], which was submitted at the beginning of round three of the NIST PQC Standardization process. The changes are described in Appendix A. Throughout this standard, SPHINCS+ will be referred to as SLH-DSA for stateless hash-based digital signature algorithm.

NIST Special Publication (SP) 800-175B [2], Guideline for Using Cryptographic Standards in the Federal Government: Cryptographic Mechanisms, includes a general discussion of digital signatures.

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

Glossary of Terms, Acronyms, and Symbols

2.1 Terms and Definitions approved

FIPS-approved and/or NIST-recommended. An algorithm or technique that is either 1) specified in a FIPS or NIST recommendation, 2) adopted in a FIPS or NIST recommendation, or 3) specified in a list of NIST-approved security functions. [1]

big-endian

The property of a byte string having its bytes positioned in order of decreasing significance. In particular, the leftmost (first) byte is the most significant, and the rightmost (last) byte is the least significant. The term “big-endian” may also be applied in the same manner to bit strings. [5, adapted]

byte string

An array of integers in which each integer is in the set {0, … , 255}.

claimed signatory

From the verifier’s perspective, the claimed signatory is the entity that purportedly generated a digital signature. [1]

destroy

An action applied to a key or a piece of secret data. After a key or a piece of secret data is destroyed, no information about its value can be recovered. [1]

digital signature

The result of a cryptographic transformation of data that, when properly implemented, provides a mechanism for verifying origin authentication, data integrity, and signatory non-repudiation. [1]

entity

An individual (person), organization, device, or process. Used interchangeably with party. [1]

equivalent process

Two processes are equivalent if the same output is produced when the same values are input to each process (either as input parameters, as values made available during the process, or both). [1]

extendable-output function

A function on bit strings in which the output can be extended to any desired length. Approved XOFs (such as those specified in FIPS 202 [6]) are designed to satisfy the following properties as long as the specified output length is sufficiently long to prevent trivial attacks: 1. (One-way) It is computationally infeasible to find any input that maps to any new pre-specified output. 2. (Collision-resistant) It is computationally infeasible to find any two distinct inputs that map to the same output. [7, adapted]

fresh random value

A previously unused output of a random bit generator.

hash function

A function on bit strings in which the length of the output is fixed. Approved hash functions (such as those specified in FIPS 180 [8] and FIPS 202 [6]) are designed to satisfy the following properties:

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

1. (One-way) It is computationally infeasible to find any input that maps to any new pre-specified output 2. (Collision-resistant) It is computationally infeasible to find any two distinct inputs that map to the same output. [1] hash value

See message digest.

key

A parameter used in conjunction with a cryptographic algorithm that determines its operation. Examples applicable to this standard include: 1. The computation of a digital signature from data, and 2. The verification of a digital signature. [1]

key pair

A public key and its corresponding private key. [1]

message

The data that is signed. Also known as signed data during the signature verification and validation process. [1]

message digest

The result of applying a hash function to a message. Also known as a hash value. [1]

non-repudiation

A service that is used to provide assurance of the integrity and origin of data in such a way that the integrity and origin can be verified and validated by a third party as having originated from a specific entity in possession of the private key (i.e., the signatory). [1]

owner

A key pair owner is the entity authorized to use the private key of a key pair. [1]

party

An individual (person), organization, device, or process. Used interchangeably with entity. [1]

private key

A cryptographic key that is used with an asymmetric (public-key) cryptographic algorithm. The private key is uniquely associated with the owner and is not made public. The private key is used to compute a digital signature that may be verified using the corresponding public key. [1]

pseudorandom

A process or data produced by a process is said to be pseudorandom when the outcome is deterministic yet also effectively random as long as the internal action of the process is hidden from observation. For cryptographic purposes, “effectively random” means “computationally indistinguishable from random within the limits of the intended security strength.” [1]

public key

A cryptographic key that is used with an asymmetric (public-key) cryptographic algorithm and is associated with a private key. The public key is associated with an owner and may be made public. In the case of digital signatures, the public key is used to verify a digital signature that was generated using the corresponding private key. [1]

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

security category

A number associated with the security strength of a post-quantum cryptographic algorithm, as specified by NIST (see [9, Sect. 5.6]).

security strength

A number associated with the amount of work (i.e., the number of operations) that is required to break a cryptographic algorithm or system. [1]

shall

Used to indicate a requirement of this standard. [1]

should

Used to indicate a strong recommendation but not a requirement of this standard. Ignoring the recommendation could result in undesirable results. [1]

signatory

The entity that generates a digital signature on data using a private key. [1]

signature generation The process of using a digital signature algorithm and a private key to generate a digital signature on data. [1] signature validation

The (mathematical) verification of the digital signature and obtaining the appropriate assurances (e.g., public-key validity, private-key possession, etc.). [1]

signature verification The process of using a digital signature algorithm and a public key to verify a digital signature on data. [1] signed data

The data or message upon which a digital signature has been computed. Also see message. [1]

verifier

The entity that verifies the authenticity of a digital signature using the public key. [1]

2.2 Acronyms ADRS

Address

ADRSc

Compressed Address

AES

Advanced Encryption Standard

DER

Distinguished Encoding Rules

FIPS

Federal Information Processing Standard

FORS

Forest of Random Subsets

ITL

Information Technology Laboratory

MGF

Mask Generation Function

NIST

National Institute of Standards and Technology

OID

Object Identifier

PQC

Post-Quantum Cryptography

PRF

Pseudorandom Function 4

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

SHA

Secure Hash Algorithm

SHAKE

Secure Hash Algorithm KECCAK

Special Publication

RFC

Request for Comments

WOTS+

Winternitz One-Time Signature Plus

XMSS

eXtended Merkle Signature Scheme

XOF

eXtendable-Output Function

2.3 Mathematical Symbols 𝑋∥𝑌

The concatenation of two arrays 𝑋 and 𝑌. If 𝑋 is an array of length ℓ𝑥 , and 𝑌 is an array of length ℓ𝑦 , then 𝑍 = 𝑋 ∥ 𝑌 is an array of length ℓ𝑥 + ℓ𝑦 such that 𝑍[𝑖] = {

𝑋[𝑖] if 0 ≤ 𝑖 < ℓ𝑥 𝑌 [𝑖 − ℓ𝑥 ] if ℓ𝑥 ≤ 𝑖 < ℓ𝑥 + ℓ𝑦 .

𝑋[𝑖 ∶ 𝑗]

A subarray of 𝑋. If 𝑋 is an array of length ℓ𝑥 , 0 ≤ 𝑖 < 𝑗 ≤ ℓ𝑥 , and 𝑌 = 𝑋[𝑖 ∶ 𝑗], then 𝑌 is an array of length 𝑗 − 𝑖 such that 𝑌 [𝑘] = 𝑋[𝑖 + 𝑘] for 0 ≤ 𝑘 < 𝑗 − 𝑖.

Truncℓ (𝑋)

A truncation function that outputs the leftmost ℓ bytes of the input byte string 𝑋. If 𝑌 = Truncℓ (𝑋), then 𝑌 is a byte string (array) of length ℓ such that 𝑌 [𝑖] = 𝑋[𝑖] for 0 ≤ 𝑖 < ℓ (i.e., 𝑌 = 𝑋[0 ∶ ℓ]).

|𝑋|

The length (in bytes) of byte string 𝑋.

⌈𝑎⌉

The ceiling of 𝑎; the smallest integer that is greater than or equal to 𝑎. For example, ⌈5⌉ = 5, ⌈5.3⌉ = 6, and ⌈−2.1⌉ = −2. [1]

⌊𝑎⌋

The floor of 𝑎; the largest integer that is less than or equal to 𝑎. For example, ⌊5⌋ = 5, ⌊5.3⌋ = 5, and ⌊−2.1⌋ = −3. [1]

𝑎 mod 𝑛

The unique remainder 𝑟, 0 ≤ 𝑟 ≤ (𝑛 − 1), when integer 𝑎 is divided by the positive integer 𝑛. For example, 23 mod 7 = 2. [1]

𝑎⋅𝑏

The product of 𝑎 and 𝑏. For example, 3 ⋅ 5 = 15.

𝑎𝑏

𝑎 raised to the power 𝑏. For example, 25 = 32.

log2 𝑥

The base 2 logarithm of 𝑥. For example, log2 (16) = 4.

The prefix to a number that is represented in binary.

The prefix to a number that is represented in hexadecimal. [1, adapted]

𝑎≫𝑏

The logical right shift of 𝑎 by 𝑏 positions (i.e., 𝑎 ≫ 𝑏 = ⌊𝑎/2𝑏 ⌋). For example, 0x73 ≫ 4 = 7. [10, adapted] 5

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

𝑎≪𝑏

The logical left shift of 𝑎 by 𝑏 positions (i.e., 𝑎 ≪ 𝑏 = 𝑎 ⋅ 2𝑏 ). For example, 0x73 ≪ 4 = 0x730. [10, adapted]

𝑎⊕𝑏

The bitwise exclusive-or of 𝑎 and 𝑏. For example, 115 ⊕ 1 = 114 (115 ⊕ 1 = 0b01110011 ⊕ 0b00000001 = 0b01110010 = 114).

𝑠←𝑥

In pseudocode, this notation means that the variable 𝑠 is set to the value of the expression 𝑥.

𝑠 ←− 𝔹𝑛

In pseudocode, this notation means that the variable 𝑠 is set to a byte string of length 𝑛 chosen at random. A fresh random value is generated for each time this step is performed.

⊥

A symbol indicating failure or the lack of output from an algorithm.

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

Overview of the SLH-DSA Signature Scheme

SLH-DSA is a stateless hash-based signature scheme that is constructed using other hash-based signature schemes as components: (1) a few-time signature scheme, forest of random subsets (FORS), and (2) a multi-time signature scheme, the eXtended Merkle Signature Scheme (XMSS). XMSS is constructed using the hash-based one-time signature scheme Winternitz One-Time Signature Plus (WOTS+ ) as a component.2 Conceptually, an SLH-DSA key pair consists of a very large set of FORS key pairs.3 The few-time signature scheme FORS allows each key pair to safely sign a small number of messages. An SLH-DSA signature is created by computing a randomized hash of the message, using part of the resulting message digest to pseudorandomly select a FORS key, and signing the remaining part of the message digest with that key. An SLH-DSA signature consists of the FORS signature and the information that authenticates the FORS public key. The authentication information is created using XMSS signatures. XMSS is a multi-time signature scheme that is created using a combination of WOTS+ one-time ′ signatures and Merkle hash trees [13]. An XMSS key consists of 2ℎ WOTS+ keys and can sign ′ 2ℎ messages. The WOTS+ public keys are formed into a Merkle hash tree, and the root of the tree is the XMSS public key. (The Merkle hash tree formed from the WOTS+ keys is also referred to as an XMSS tree.) An XMSS signature consists of a WOTS+ signature and an authentication path within the Merkle hash tree for the WOTS+ public key. In Figure 1, triangles represent XMSS trees, squares represent the WOTS+ public keys, and circles represent the interior nodes of the hash tree. Within an XMSS tree, the square and circles that are filled in represent the authentication path for the WOTS+ public key needed to verify the signature. The authentication information for a FORS public key is a hypertree signature. A hypertree is a tree of XMSS trees, as depicted in Figure 1. The tree consists of 𝑑 layers4 in which the top layer ′ (layer 𝑑 − 1) consists of a single XMSS tree, the next layer down (layer 𝑑 − 2) consists of 2ℎ ′ XMSS trees, and the lowest layer (layer 0) consists of 2(𝑑−1)ℎ XMSS trees. The public key of each XMSS key at layers 0 through 𝑑 − 2 is signed by an XMSS key at the next higher layer. The XMSS ′ keys at layer 0 collectively have 2𝑑ℎ = 2ℎ WOTS+ keys, which are used to sign the 2ℎ FORS public keys in the SLH-DSA key pair. The sequence of 𝑑 XMSS signatures needed to authenticate a FORS public key when starting with the public key of the XMSS key at layer 𝑑 − 1 is a hypertree signature. An SLH-DSA signature consists of a FORS signature along with a hypertree signature. An SLH-DSA public key (Figure 16) contains two 𝑛-byte components: (1) PK.root, which is the public key of the XMSS key at layer 𝑑 − 1, and (2) PK.seed, which is used to provide domain separation between different SLH-DSA key pairs. An SLH-DSA private key (Figure 15) consists of an 𝑛-byte seed SK.seed that is used to pseudorandomly generate all of the secret values for the WOTS+ and FORS keys and an 𝑛-byte key SK.prf that is used in the generation of the randomized hash of the message. An SLH-DSA private key also includes copies of PK.root and PK.seed, as these values are needed during both signature generation and signature verification. The WOTS+ and XMSS schemes that are used as components of SLH-DSA are not the same as the WOTS+ and XMSS schemes in RFC 8391 [11] and SP 800-208 [12]. 3 For the parameter sets in this standard, an SLH-DSA key pair contains 263 , 264 , 266 , or 268 FORS keys, which are pseudorandomly generated from a single seed. 4 For the parameter sets in this standard, 𝑑 is 7, 8, 17, or 22. 2

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

PK.root layer 𝑑 − 1 = 2

WOTS+ signature layer 1

Merkle tree node +

WOTS signature

WOTS+ public key FORS public key

layer 0

WOTS+ signature

FORS signature Message Figure 1. An SLH-DSA signature The WOTS+ one-time signature scheme is specified in Section 5, and the XMSS multi-time signature scheme is specified in Section 6. Section 7 specifies the generation and verification of hypertree signatures. The FORS few-time signature scheme is specified in Section 8. Finally, Section 9 specifies the SLH-DSA key generation, signature, and verification functions. As the WOTS+ , XMSS, hypertree, and FORS schemes described in this standard are not intended for use as stand-alone signature schemes, only the components of the schemes necessary to implement SLH-DSA are described. In particular, these sections do not include functions for key pair generation, and a signature verification function is only specified for hypertree signatures. When used in this standard, WOTS+ , XMSS, and FORS signatures are implicitly verified using functions to generate public keys from messages and signatures (see Sections 5.3, 6.3, and 8.4). When verifying an SLH-DSA signature, the randomized hash of the message and the FORS signature are used to compute a candidate FORS public key. The candidate FORS public key and the WOTS+ signature from the layer 0 XMSS key are used to compute a candidate WOTS+ public key, which is then used in conjunction with the corresponding authentication path to compute a candidate XMSS public key. The candidate layer 0 XMSS public key is used along with the layer 1 8

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

XMSS signature to compute a candidate layer 1 XMSS public key. This process is repeated until a candidate layer 𝑑 − 1 public key has been computed. SLH-DSA signature verification succeeds if the computed candidate layer 𝑑 − 1 XMSS public key is the same as the SLH-DSA public key root PK.root.

3.1 Additional Requirements This section specifies requirements for cryptographic modules that implement SLH-DSA. Section 3.2 discusses issues that implementers of cryptographic modules should take into consideration but that are not requirements. SP 800-89, Recommendation for Obtaining Assurances for Digital Signature Applications [3], specifies requirements that apply to the use of digital signature schemes. Randomness generation. SLH-DSA key generation (Algorithm 21) requires the generation of three random 𝑛-byte values: PK.seed, SK.seed, and SK.prf, where 𝑛 is 16, 24, or 32, depending on the parameter set. For each invocation of key generation, each of these values shall be a fresh (i.e., not previously used) random value generated using an approved random bit generator (RBG), as prescribed in SP 800-90A, SP 800-90B, and SP 800-90C [14, 15, 16]. Moreover, the RBG used shall have a security strength of at least 8𝑛 bits. See Table 2 for the value of 𝑛 for each parameter set. Destruction of sensitive data. Data used internally by key generation and signing algorithms in intermediate computation steps could be used by an adversary to gain information about the private key and thereby compromise security. The data used internally by verification algorithms is similarly sensitive for some applications, including the verification of signatures that are used as bearer tokens (i.e., authentication secrets) or signatures on plaintext messages that are intended to be confidential. Intermediate values of the verification algorithm may reveal information about its inputs (i.e., the message, signature, and public key), and in some applications, security or privacy requires one or more of these inputs to be confidential. Therefore, implementations of SLH-DSA shall ensure that any local copies of the inputs and any potentially sensitive intermediate data are destroyed as soon as they are no longer needed. Key checks. SP 800-89 imposes requirements for the assurance of public-key validity and privatekey possession. In the case of SLH-DSA, where public-key validation is required, implementations shall verify that the public key is 2𝑛 bytes in length. When the assurance of private key possession is obtained via regeneration, the owner of the private key shall check that the private key is 4𝑛 bytes in length and shall use SK.seed and PK.seed to recompute PK.root and compare the newly generated value with the value in the private key currently held. Floating-point arithmetic. Implementations of SLH-DSA shall not use floating-point arithmetic, as rounding errors in floating point operations may lead to incorrect results in some cases. In all pseudocode in this standard in which division is performed (e.g., 𝑥/𝑦) and 𝑦 may not divide 𝑥, either ⌊𝑥/𝑦⌋ or ⌈𝑥/𝑦⌉ is used. Both of these can be computed without floating-point arithmetic, as ordinary integer division 𝑥/𝑦 computes ⌊𝑥/𝑦⌋, and ⌈𝑥/𝑦⌉ = ⌊(𝑥 + 𝑦 − 1)/𝑦⌋ for non-negative integers 𝑥 and positive integers 𝑦.

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

While the value of 𝑙𝑒𝑛2 (see Equation 5.3) may be computed without using floating-point arithmetic (see Algorithm 1), it is recommended that this value be precomputed. For all parameter sets in this standard, 𝑙𝑒𝑛2 is 3. Algorithm 1 gen_len2 (𝑛, 𝑙𝑔𝑤 ) Computes 𝑙𝑒𝑛2 (Equation 5.3). Input: Security parameter 𝑛, bits per hash chain 𝑙𝑔𝑤 . Output: 𝑙𝑒𝑛2 . 1: 𝑤 ← 2𝑙𝑔𝑤 8⋅𝑛+𝑙𝑔𝑤 −1 2: 𝑙𝑒𝑛1 ← ⌊ ⌋ 𝑙𝑔𝑤 3: 𝑚𝑎𝑥_𝑐ℎ𝑒𝑐𝑘𝑠𝑢𝑚 = 𝑙𝑒𝑛1 ⋅ (𝑤 − 1) 4: 𝑙𝑒𝑛2 ← 1 5: 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦 ← 𝑤 6: while 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦 ≤ 𝑚𝑎𝑥_𝑐ℎ𝑒𝑐𝑘𝑠𝑢𝑚 do 7: 𝑙𝑒𝑛2 ← 𝑙𝑒𝑛2 + 1 8: 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦 ← 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦 ⋅ 𝑤 9: end while 10: return 𝑙𝑒𝑛2

▷ Equation 5.1 ▷ Equation 5.2 ▷ maximum possible checksum value

▷ maximum value that may be signed using ▷ 𝑙𝑒𝑛2 hash chains is 𝑤𝑙𝑒𝑛2 − 1 = 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦 − 1

3.2 Implementation Considerations This section discusses some implementation considerations for SLH-DSA. Do not support component use. As WOTS+ , XMSS, FORS, and hypertree signature schemes are not approved for use as stand-alone signature schemes, cryptographic modules should not make interfaces to these components available to applications. SP 800-208 [12] specifies approved stateful hash-based signature schemes. Side-channel and fault attacks. For signature schemes, the secrecy of the private key is critical. Care must be taken to protect implementations against attacks, such as side-channel attacks or fault attacks [17, 18, 19, 20, 21]. A cryptographic device may leak critical information with side-channel analysis or attacks that allow internal data or keying material to be extracted without breaking the cryptographic primitives.

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

Functions and Addressing

4.1 Hash Functions and Pseudorandom Functions The specification of SLH-DSA makes use of six functions — PRF𝑚𝑠𝑔 , H𝑚𝑠𝑔 , PRF, Tℓ , H, and F — that are all implemented using hash functions or XOFs with fixed output lengths. The inputs and output of each function are byte strings. In the following definitions, 𝔹 = {0, … , 255} denotes the set of all bytes, 𝔹𝑛 denotes the set of byte strings of length 𝑛 bytes, and 𝔹∗ denotes the set of all byte strings. The ADRS input is described in Section 4.2. • PRF𝑚𝑠𝑔 (SK.prf, 𝑜𝑝𝑡_𝑟𝑎𝑛𝑑, 𝑀 ) (𝔹𝑛 × 𝔹𝑛 × 𝔹∗ → 𝔹𝑛 ) is a pseudorandom function (PRF) that generates the randomizer (𝑅) for the randomized hashing of the message to be signed. • H𝑚𝑠𝑔 (𝑅, PK.seed, PK.root, 𝑀 ) (𝔹𝑛 × 𝔹𝑛 × 𝔹𝑛 × 𝔹∗ → 𝔹𝑚 ) is used to generate the digest of the message to be signed. • PRF(PK.seed, SK.seed, ADRS) (𝔹𝑛 × 𝔹𝑛 × 𝔹32 → 𝔹𝑛 ) is a PRF that is used to generate the secret values in WOTS+ and FORS private keys. • Tℓ (PK.seed, ADRS, 𝑀ℓ ) (𝔹𝑛 × 𝔹32 × 𝔹ℓ𝑛 → 𝔹𝑛 ) is a hash function that maps an ℓ𝑛-byte message to an 𝑛-byte message. • H(PK.seed, ADRS, 𝑀2 ) (𝔹𝑛 × 𝔹32 × 𝔹2𝑛 → 𝔹𝑛 ) is a special case of Tℓ that takes a 2𝑛-byte message as input. • F(PK.seed, ADRS, 𝑀1 ) (𝔹𝑛 × 𝔹32 × 𝔹𝑛 → 𝔹𝑛 ) is a hash function that takes an 𝑛-byte message as input and produces an 𝑛-byte output. The specific instantiations for these functions differ for different parameter sets and are specified in Section 11.

4.2 Addresses Four of the functions described in Section 4.1 take a 32-byte address (i.e., ADRS) as input. An ADRS consists of public values that indicate the position of the value being computed by the function. A different ADRS value is used for each call to each function. In the case of PRF, this is used to generate a large number of different secret values from a single seed. In the case of Tℓ , H, and F, it is used to mitigate multi-target attacks. In the pseudocode, where addresses are passed as parameters, they may be passed either by reference or by value. The structure of an ADRS conforms to word boundaries, with each word being 4 bytes long and values encoded as unsigned integers in big-endian byte order (see Figure 2). The first word of ADRS specifies the layer address, which is the height of an XMSS tree within the hypertree. Trees on the bottom layer have a height of zero, and the single XMSS tree at the top has a height of 𝑑 − 1 (see Figure 1). The next three words of ADRS specify the tree address, which is the position of an XMSS tree within a layer of the hypertree. The leftmost XMSS tree in a layer has a ′ tree address of zero, and the rightmost XMSS tree in layer 𝐿 has a tree address of 2(𝑑−1−𝐿)ℎ − 1. The next word is used to specify the type of the address, which differs depending on the use case. 11

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

There are seven different types of address used in SLH-DSA, as described below.5 The address type determines how the final 12 bytes of the address are to be interpreted. The algorithms in this standard are written based on the assumption that whenever the type in an ADRS is changed, the final 12 bytes of the address are initialized to zero.

layer address

4 bytes

tree address

12 bytes

𝑡𝑦𝑝𝑒

4 bytes 12 bytes

Figure 2. Address (ADRS) The type is set to WOTS_HASH (i.e., 𝑡𝑦𝑝𝑒 = 0) for a WOTS+ hash address (see Figure 3), which is used when computing hash chains in WOTS+ . When type is WOTS_HASH, the next word encodes the key pair address, which is the index of the WOTS+ key pair within the XMSS tree specified by the layer and tree addresses, with the leftmost WOTS+ key having an index of zero and the ′ rightmost WOTS+ key having an index of 2ℎ − 1. Next is the chain address, which encodes the index of the chain within WOTS+ , followed by the hash address, which encodes the address of the hash function within the chain. layer address

layer address

tree address

𝑡𝑦𝑝𝑒 = 0 (WOTS_HASH) key pair address chain address hash address

4 bytes 4 bytes 4 bytes

Figure 3. WOTS+ hash address

𝑡𝑦𝑝𝑒 = 1 (WOTS_PK) key pair address

4 bytes

𝑝𝑎𝑑𝑑𝑖𝑛𝑔 = 0

8 bytes

Figure 4. WOTS+ public-key compression address

The type is set to WOTS_PK (i.e., 𝑡𝑦𝑝𝑒 = 1) when compressing WOTS+ public keys (see Figure 4). As when the type is WOTS_HASH, the next word encodes the index of the WOTS+ key pair within the XMSS tree specified by the layer and tree addresses. The remaining two words of ADRS are not needed and are set to zero. The type is set to TREE (i.e., 𝑡𝑦𝑝𝑒 = 2) when computing the hashes within the XMSS tree (see Figure 5). For this type of address, the next word is always set to zero. The following word 5

The type word will have a value of 0, 1, 2, 3, 4, 5, or 6. In order to improve readability, these values will be referred to in this standard by the constants WOTS_HASH, WOTS_PK, TREE, FORS_TREE, FORS_ROOTS, WOTS_PRF, and FORS_PRF, respectively.

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

encodes the height of the node within the tree that is being computed, and the final word encodes the index of the node at that height. layer address tree address 𝑡𝑦𝑝𝑒 = 2 (TREE) 𝑝𝑎𝑑𝑑𝑖𝑛𝑔 = 0 tree height tree index

4 bytes 4 bytes 4 bytes

Figure 5. Hash tree address The type is set to FORS_TREE (i.e., 𝑡𝑦𝑝𝑒 = 3) when computing hashes within the FORS tree (see Figure 6). The next word is the key pair address, which encodes the FORS key that is used. The value is the same as the key pair address for the WOTS+ key used to sign the FORS key (see Figure 3 and Figure 4). The next two words — the tree height and tree index — encode the node within the FORS tree that is being computed. The tree height starts with zero for the leaf nodes. The tree index is counted continuously across the 𝑘 different FORS trees. The leftmost node in the leftmost tree has an index of zero, and the rightmost node in the rightmost tree at level 𝑗 has an index of 𝑘 ⋅ 2(𝑎−𝑗) − 1, where 𝑎 is the height of the tree. layer address = 0

layer address = 0

tree address

𝑡𝑦𝑝𝑒 = 3 (FORS_TREE) key pair address tree height tree index

𝑡𝑦𝑝𝑒 = 4 (FORS_ROOTS) key pair address

4 bytes

𝑝𝑎𝑑𝑑𝑖𝑛𝑔 = 0

8 bytes

4 bytes 4 bytes 4 bytes

Figure 6. FORS tree address

Figure 7. FORS tree roots compression address

The type is set to FORS_ROOTS (i.e., 𝑡𝑦𝑝𝑒 = 4) when compressing the 𝑘 FORS tree roots (see Figure 7). The next word is the key pair address, which has the same meaning as it does in the FORS_TREE address. The remaining two words of ADRS are not needed and are set to zero. The type is set to WOTS_PRF (i.e., 𝑡𝑦𝑝𝑒 = 5) when generating secret values for WOTS+ keys (see Figure 8). The values for the other words in the address are set to the same values as for the WOTS_HASH address (Figure 3) used for the chain. The hash address is always set to zero.

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

layer address

layer address = 0

tree address

𝑡𝑦𝑝𝑒 = 5 (WOTS_PRF) key pair address chain address hash address = 0

𝑡𝑦𝑝𝑒 = 6 (FORS_PRF) key pair address tree height = 0 tree index

4 bytes 4 bytes 4 bytes

Figure 8. WOTS+ key generation address

4 bytes 4 bytes 4 bytes

Figure 9. FORS key generation address

The type is set to FORS_PRF (i.e., 𝑡𝑦𝑝𝑒 = 6) when generating secret values for FORS keys (see Figure 9). The values for the other words in the address are set to the same values as for the FORS_TREE address (Figure 6) used for the same leaf node.

4.3 Member Functions The algorithms in this standard make use of member functions. If a complex data structure (e.g., an ADRS) contains a component 𝑋, then ADRS.getX() returns the value of 𝑋, and ADRS.setX(𝑌) sets the component 𝑋 in ADRS to the value held by 𝑌. If a data structure 𝑠 contains multiple instances of 𝑋, then 𝑠.getX(𝑖) returns the value of the 𝑖th instance of 𝑋 in 𝑠. For example, if 𝑠 is a FORS signature (Figure 14), then 𝑠.getAUTH(𝑖) returns the authentication path for the 𝑖th tree. Whenever the type in an address changes, the final 12 bytes of the address are initialized to zero. The member function ADRS.setTypeAndClear(𝑌) for addresses sets the 𝑡𝑦𝑝𝑒 of the ADRS to 𝑌 and sets the final 12 bytes of the ADRS to zero.6 Table 1 shows alternative notation for each of the member functions that operates on addresses. Table 1. Member functions for addresses Member function ADRS.setLayerAddress(𝑙) ADRS.setTreeAddress(𝑡) ADRS.setTypeAndClear(𝑌) ADRS.setKeyPairAddress(𝑖) ADRS.setChainAddress(𝑖) ADRS.setTreeHeight(𝑖) ADRS.setHashAddress(𝑖) ADRS.setTreeIndex(𝑖) 𝑖 ← ADRS.getKeyPairAddress() 𝑖 ← ADRS.getTreeIndex() 6

Expanded notation ADRS ← toByte(𝑙, 4) ∥ ADRS[4 ∶ 32] ADRS ← ADRS[0 ∶ 4] ∥ toByte(𝑡, 12) ∥ ADRS[16 ∶ 32] ADRS ← ADRS[0 ∶ 16] ∥ toByte(𝑌 , 4) ∥ toByte(0, 12) ADRS ← ADRS[0 ∶ 20] ∥ toByte(𝑖, 4) ∥ ADRS[24 ∶ 32] ADRS ← ADRS[0 ∶ 24] ∥ toByte(𝑖, 4) ∥ ADRS[28 ∶ 32] ADRS ← ADRS[0 ∶ 28] ∥ toByte(𝑖, 4) 𝑖 ← toInt(ADRS[20 ∶ 24], 4) 𝑖 ← toInt(ADRS[28 ∶ 32], 4)

As noted in Section 4.2, the type (𝑌) is an integer. However, in the pseudocode, the constants WOTS_HASH, WOTS_PK, TREE, FORS_TREE, FORS_ROOTS, WOTS_PRF, and FORS_PRF are used in order to improve readability.

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

4.4 Arrays, Byte Strings, and Integers If 𝑋 is a byte string of length 𝑛, then 𝑋[𝑖] for 𝑖 ∈ {0, … , 𝑛 − 1} will refer to the 𝑖th element in the string 𝑋. If 𝑋 is an array of 𝑚 𝑛-byte strings, then 𝑋[𝑖] for 𝑖 ∈ {0, … , 𝑚 − 1} will refer to the 𝑖th 𝑛-byte string in 𝑋, and 𝑋 will refer to the 𝑚 ⋅ 𝑛-byte string 𝑋[0] ∥ 𝑋[1] ∥ … 𝑋[𝑚 − 1]. A byte string may be interpreted as the big-endian representation of an integer. In such cases, a byte string 𝑋 of length 𝑛 is converted to the integer 𝑋[0] ⋅ 256𝑛−1 + 𝑋[1] ⋅ 256𝑛−2 + … 𝑋[𝑛 − 2] ⋅ 256 + 𝑋[𝑛 − 1]. Similarly, an integer 𝑥 may be converted to a byte string of length 𝑛 by finding coefficients 𝑥0 , 𝑥1 , … 𝑥𝑛−2 , 𝑥𝑛−1 ∈ {0, … , 255} such that 𝑥 = 𝑥0 ⋅ 256𝑛−1 + 𝑥1 ⋅ 256𝑛−2 + … 𝑥𝑛−2 ⋅ 256 + 𝑥𝑛−1 and then setting the byte string to be 𝑥0 𝑥1 … 𝑥𝑛−2 𝑥𝑛−1 . Algorithm 2 is a function that converts a byte string 𝑋 of length 𝑛 to an integer, and Algorithm 3 is a function that converts an integer 𝑥 to a byte string of length 𝑛. Algorithm 2 toInt(𝑋, 𝑛) Converts a byte string to an integer. Input: 𝑛-byte string 𝑋. Output: Integer value of 𝑋. 1: 𝑡𝑜𝑡𝑎𝑙 ← 0 2: for 𝑖 from 0 to 𝑛 − 1 do 3: 𝑡𝑜𝑡𝑎𝑙 ← 256 ⋅ 𝑡𝑜𝑡𝑎𝑙 + 𝑋[𝑖] 4: end for 5: return 𝑡𝑜𝑡𝑎𝑙

Algorithm 3 toByte(𝑥, 𝑛) Converts an integer to a byte string. Input: Integer 𝑥, string length 𝑛. Output: Byte string of length 𝑛 containing binary representation of 𝑥 in big-endian byte-order. 1: 𝑡𝑜𝑡𝑎𝑙 ← 𝑥 2: for 𝑖 from 0 to 𝑛 − 1 do 3: 𝑆[𝑛 − 1 − 𝑖] ← 𝑡𝑜𝑡𝑎𝑙 mod 256 𝑡𝑜𝑡𝑎𝑙 ← 𝑡𝑜𝑡𝑎𝑙 ≫ 8 4: 5: end for 6: return 𝑆

▷ least significant 8 bits of 𝑡𝑜𝑡𝑎𝑙

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

For the WOTS+ and FORS schemes, the messages to be signed need to be split into a sequence of 𝑏-bit strings, where each 𝑏-bit string is interpreted as an integer between 0 and 2𝑏 − 1.7 This is the equivalent of creating the base-2𝑏 representation of the message. The base_2b function (Algorithm 4) takes a byte string 𝑋, a bit string length 𝑏, and an output length 𝑜𝑢𝑡_𝑙𝑒𝑛 as input and returns an array of base-2𝑏 integers that represent the first 𝑜𝑢𝑡_𝑙𝑒𝑛 ⋅ 𝑏 bits of 𝑋 if the individual bytes in 𝑋 are encoded as 8-bit strings in big-endian bit order. 𝑋 must be at least ⌈𝑜𝑢𝑡_𝑙𝑒𝑛 ⋅ 𝑏/8⌉ bytes in length. As the value of 𝑏𝑖𝑡𝑠 will never exceed 𝑏 + 7, a 𝑏 + 7-bit unsigned integer is sufficient to store 𝑡𝑜𝑡𝑎𝑙 (i.e., 𝑡𝑜𝑡𝑎𝑙 may be stored as a 32-bit unsigned integer). Algorithm 4 base_2b (𝑋, 𝑏, 𝑜𝑢𝑡_𝑙𝑒𝑛) Computes the base 2𝑏 representation of 𝑋. Input: Byte string 𝑋 of length at least ⌈ 𝑜𝑢𝑡_8𝑙𝑒𝑛⋅𝑏 ⌉, integer 𝑏, output length 𝑜𝑢𝑡_𝑙𝑒𝑛. Output: Array of 𝑜𝑢𝑡_𝑙𝑒𝑛 integers in the range [0, … , 2𝑏 − 1]. 1: 𝑖𝑛 ← 0 2: 𝑏𝑖𝑡𝑠 ← 0 3: 𝑡𝑜𝑡𝑎𝑙 ← 0 4: for 𝑜𝑢𝑡 from 0 to 𝑜𝑢𝑡_𝑙𝑒𝑛 − 1 do 5: while 𝑏𝑖𝑡𝑠 < 𝑏 do 6: 𝑡𝑜𝑡𝑎𝑙 ← (𝑡𝑜𝑡𝑎𝑙 ≪ 8) + 𝑋[𝑖𝑛] 7: 𝑖𝑛 ← 𝑖𝑛 + 1 8: 𝑏𝑖𝑡𝑠 ← 𝑏𝑖𝑡𝑠 + 8 9: end while 10: 𝑏𝑖𝑡𝑠 ← 𝑏𝑖𝑡𝑠 − 𝑏 11: 𝑏𝑎𝑠𝑒𝑏[𝑜𝑢𝑡] ← (𝑡𝑜𝑡𝑎𝑙 ≫ 𝑏𝑖𝑡𝑠) mod 2𝑏 12: end for 13: return 𝑏𝑎𝑠𝑒𝑏

𝑏 will be the value of 𝑙𝑔𝑤 when the base_2b function is used in WOTS+ , and 𝑏 will be the value of 𝑎 when the base_2b function is used in FORS. For the parameter sets in this standard, 𝑙𝑔𝑤 is 4, and 𝑎 is 6, 8, 9, 12, or 14.

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

Winternitz One-Time Signature Plus Scheme

This section describes the WOTS+ one-time signature scheme that is a component of SLH-DSA. WOTS+ uses two parameters. The security parameter 𝑛 is the length in bytes of the messages that may be signed as well as the length of the private key elements, public key elements, and signature elements. For the parameter sets specified in this standard, 𝑛 may be 16, 24, or 32 (see Table 2). The second parameter 𝑙𝑔𝑤 indicates the number of bits that are encoded by each hash chain that is used.8 𝑙𝑔𝑤 is 4 for all parameter sets in this standard. These parameters are used to compute four additional values: 𝑤 = 2𝑙𝑔𝑤

(5.1)

8𝑛 ⌉ 𝑙𝑔𝑤

(5.2)

log2 (𝑙𝑒𝑛1 ⋅ (𝑤 − 1)) ⌋+1 𝑙𝑔𝑤

(5.3)

𝑙𝑒𝑛 = 𝑙𝑒𝑛1 + 𝑙𝑒𝑛2

(5.4)

𝑙𝑒𝑛1 = ⌈ 𝑙𝑒𝑛2 = ⌊

When 𝑙𝑔𝑤 = 4, 𝑤 = 16, 𝑙𝑒𝑛1 = 2𝑛, 𝑙𝑒𝑛2 = 3, and 𝑙𝑒𝑛 = 2𝑛 + 3. A WOTS+ private key consists of 𝑙𝑒𝑛 secret values of length 𝑛. In SLH-DSA, these are all generated from an 𝑛-byte seed SK.seed using a PRF. Chains of length 𝑤 are then created from the secret values using a chaining function, and the end values from each of the chains are public values. The WOTS+ public key is computed as the hash of these public values. In order to create a signature, the 8𝑛-bit message is first converted into an array of 𝑙𝑒𝑛1 base-𝑤 integers. A checksum is then computed for this string, and the checksum is converted into an array of 𝑙𝑒𝑛2 base-𝑤 integers. The signature consists of the appropriate entries from the chains for each of the integers in the message and checksum arrays. The WOTS+ functions make use of two helper functions: base_2b and chain. The base_2b function (Section 4.4) is used to break the message to be signed and the checksum value into arrays of base-𝑤 integers. The chain function (Algorithm 5) is used to compute the hash chains. The chain function takes an 𝑛-byte string 𝑋 and integers 𝑠 and 𝑖 (where 𝑖 + 𝑠 < 𝑤) as input and returns the result of iterating a hash function F on the input 𝑠 times, starting from an index of 𝑖.9 The chain function also requires as input PK.seed, which is part of the SLH-DSA public key, and an address ADRS. The type in ADRS must be set to WOTS_HASH, and the layer address, tree address, key pair address, and chain address must be set to the address of the chain being computed. The chain function updates the hash address in ADRS with each iteration to specify the current position in the chain prior to ADRS’s use in F.

In [10], the Winternitz parameter 𝑤 is used as the second WOTS+ parameter, where 𝑤 indicates the length of the hash chains that are used. This standard uses the parameter 𝑙𝑔𝑤 = log2 (𝑤) to simplify notation. 9 A start index of 0 indicates the beginning of the chain. 8

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

Algorithm 5 chain(𝑋, 𝑖, 𝑠, PK.seed, ADRS) Chaining function used in WOTS+ . Input: Input string 𝑋, start index 𝑖, number of steps 𝑠, public seed PK.seed, address ADRS. Output: Value of F iterated 𝑠 times on 𝑋. 1: 𝑡𝑚𝑝 ← 𝑋 2: for 𝑗 from 𝑖 to 𝑖 + 𝑠 − 1 do 3: ADRS.setHashAddress(𝑗) 4: 𝑡𝑚𝑝 ← F(PK.seed, ADRS, 𝑡𝑚𝑝) 5: end for 6: return 𝑡𝑚𝑝

5.1 WOTS+ Public-Key Generation The wots_pkGen function (Algorithm 6) generates WOTS+ public keys. It takes SK.seed and PK.seed from the SLH-DSA private key and an address as input. The type in the address ADRS must be set to WOTS_HASH, and the layer address, tree address, and key pair address must encode the address of the WOTS+ public key to be generated. Lines 4 through 9 in Algorithm 6 generate the public values, as described in Section 5. For each of the 𝑙𝑒𝑛 public values, the corresponding secret value is generated in lines 5 and 6, and the chain function is called to compute the end value of the chain of length 𝑤. Once the 𝑙𝑒𝑛 public values are computed, they are compressed into a single 𝑛-byte value in lines 10 through 13. Algorithm 6 wots_pkGen(SK.seed, PK.seed, ADRS) Generates a WOTS+ public key. Input: Secret seed SK.seed, public seed PK.seed, address ADRS. Output: WOTS+ public key 𝑝𝑘. 1: skADRS ← ADRS ▷ copy address to create key generation key address 2: skADRS.setTypeAndClear(WOTS_PRF) 3: skADRS.setKeyPairAddress(ADRS.getKeyPairAddress()) 4: for 𝑖 from 0 to 𝑙𝑒𝑛 − 1 do 5: skADRS.setChainAddress(𝑖) 6: 𝑠𝑘 ← PRF(PK.seed, SK.seed, skADRS) ▷ compute secret value for chain 𝑖 7: ADRS.setChainAddress(𝑖) 8: 𝑡𝑚𝑝[𝑖] ← chain(𝑠𝑘, 0, 𝑤 − 1, PK.seed, ADRS) ▷ compute public value for chain 𝑖 9: end for 10: wotspkADRS ← ADRS ▷ copy address to create WOTS+ public key address 11: wotspkADRS.setTypeAndClear(WOTS_PK) 12: wotspkADRS.setKeyPairAddress(ADRS.getKeyPairAddress()) 13: 𝑝𝑘 ← T𝑙𝑒𝑛 (PK.seed, wotspkADRS, 𝑡𝑚𝑝) ▷ compress public key 14: return 𝑝𝑘

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

5.2 WOTS+ Signature Generation A WOTS+ signature is an array of 𝑙𝑒𝑛 byte strings of length 𝑛, as shown in Figure 10. The wots_sign function (Algorithm 7) generates the signature by converting the 𝑛-byte message 𝑀10 into an array of 𝑙𝑒𝑛1 base-𝑤 integers (line 2). A checksum is computed over 𝑀 (lines 3 through 5). The checksum is converted to a byte string, which is then converted into an array of 𝑙𝑒𝑛2 base-𝑤 integers (lines 6 and 7). The 𝑙𝑒𝑛2 integers that represent the checksum are appended to the 𝑙𝑒𝑛1 integers that represent the message (line 7).11 For each of the 𝑙𝑒𝑛 base-𝑤 integers, the signature consists of the corresponding node in one of the hash chains. For each of these integers, lines 12 and 13 compute the secret value for the hash chain, and lines 14 and 15 compute the node in the hash chain that corresponds to the integer. The selected nodes are concatenated to form the WOTS+ signature. sigots [0] ⋯ sigots [𝑙𝑒𝑛 − 1]

𝑛 bytes 𝑛 bytes

Figure 10. WOTS+ signature data format In addition to the 𝑛-byte message to be signed, wots_sign takes SK.seed and PK.seed from the SLH-DSA private key and an address as input. The type in the address ADRS must be set to WOTS_HASH, and the layer address, tree address, and key pair address must encode the address of the WOTS+ key that is used to sign the message.

10 11

In SLH-DSA, the message 𝑀 that is signed using WOTS+ is either an XMSS public key or a FORS public key. In the case that 𝑙𝑔𝑤 = 4, the 𝑛-byte message is converted into an array of 2𝑛 base-16 integers (i.e., hexadecimal digits). The checksum is encoded as two bytes with the least significant four bits being zeros, and the most significant 12 bits are appended to the message as an array of three base-16 integers.

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

Algorithm 7 wots_sign(𝑀, SK.seed, PK.seed, ADRS) Generates a WOTS+ signature on an 𝑛-byte message. Input: Message 𝑀, secret seed SK.seed, public seed PK.seed, address ADRS. Output: WOTS+ signature 𝑠𝑖𝑔. 1: 𝑐𝑠𝑢𝑚 ← 0 2: 𝑚𝑠𝑔 ← base_2b (𝑀 , 𝑙𝑔𝑤 , 𝑙𝑒𝑛1 )

▷ convert message to base 𝑤

3: for 𝑖 from 0 to 𝑙𝑒𝑛1 − 1 do 4: 𝑐𝑠𝑢𝑚 ← 𝑐𝑠𝑢𝑚 + 𝑤 − 1 − 𝑚𝑠𝑔[𝑖] 5: end for

▷ compute checksum

6: 𝑐𝑠𝑢𝑚 ← 𝑐𝑠𝑢𝑚 ≪ ((8 − ((𝑙𝑒𝑛2 ⋅ 𝑙𝑔𝑤 ) mod 8)) mod 8) b

7: 𝑚𝑠𝑔 ← 𝑚𝑠𝑔 ∥ base_2

▷ for 𝑙𝑔𝑤 = 4, left shift by 4 ▷ convert to base 𝑤

(toByte (𝑐𝑠𝑢𝑚, ⌈ 𝑙𝑒𝑛28⋅𝑙𝑔𝑤 ⌉) , 𝑙𝑔𝑤 , 𝑙𝑒𝑛2 )

8: skADRS ← ADRS ▷ copy address to create key generation key address 9: skADRS.setTypeAndClear(WOTS_PRF) 10: skADRS.setKeyPairAddress(ADRS.getKeyPairAddress()) 11: for 𝑖 from 0 to 𝑙𝑒𝑛 − 1 do 12: skADRS.setChainAddress(𝑖) 13: 𝑠𝑘 ← PRF(PK.seed, SK.seed, skADRS) ▷ compute chain 𝑖 secret value 14: ADRS.setChainAddress(𝑖) 15: 𝑠𝑖𝑔[𝑖] ← chain(𝑠𝑘, 0, 𝑚𝑠𝑔[𝑖], PK.seed, ADRS) ▷ compute chain 𝑖 signature value 16: end for 17: return 𝑠𝑖𝑔

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

5.3 Computing a WOTS+ Public Key From a Signature Verifying a WOTS+ signature involves computing a public-key value from a message and signature value. Verification succeeds if the correct public-key value is computed, which is determined by using the computed public-key value along with other information to compute a candidate PK.root value and then comparing that value to the known value of PK.root from the SLH-DSA public key. This section describes wots_pkFromSig (Algorithm 8), a function that computes a candidate WOTS+ public key from a WOTS+ signature and corresponding message. In addition to an 𝑛-byte message 𝑀 and a 𝑙𝑒𝑛 ⋅ 𝑛-byte signature 𝑠𝑖𝑔, which is interpreted as an array of 𝑙𝑒𝑛 𝑛-byte strings, the wots_pkFromSig function takes PK.seed from the SLH-DSA public key and an address as input. The type of the address ADRS must be set to WOTS_HASH, and the layer address, tree address, and key pair address must encode the address of the WOTS+ key that was used to sign the message. Lines 1 through 7 of wots_pkFromSig are the same as lines 1 through 7 of wots_sign (Algorithm 7). Lines 8 through 11 of wots_pkFromSig compute the end nodes for each of the chains using the signature value as the starting point and the message value to determine the number of iterations that need to be performed to get to the end node. Finally, as with lines 10 through 13 of Algorithm 6, the computed public-key values are compressed in lines 12 through 15. Algorithm 8 wots_pkFromSig(𝑠𝑖𝑔, 𝑀, PK.seed, ADRS) Computes a WOTS+ public key from a message and its signature. Input: WOTS+ signature 𝑠𝑖𝑔, message 𝑀, public seed PK.seed, address ADRS. Output: WOTS+ public key 𝑝𝑘𝑠𝑖𝑔 derived from 𝑠𝑖𝑔. 1: 𝑐𝑠𝑢𝑚 ← 0 2: 𝑚𝑠𝑔 ← base_2b (𝑀 , 𝑙𝑔𝑤 , 𝑙𝑒𝑛1 )

▷ convert message to base 𝑤

3: for 𝑖 from 0 to 𝑙𝑒𝑛1 − 1 do 4: 𝑐𝑠𝑢𝑚 ← 𝑐𝑠𝑢𝑚 + 𝑤 − 1 − 𝑚𝑠𝑔[𝑖] 5: end for

▷ compute checksum

6: 𝑐𝑠𝑢𝑚 ← 𝑐𝑠𝑢𝑚 ≪ ((8 − ((𝑙𝑒𝑛2 ⋅ 𝑙𝑔𝑤 ) mod 8)) mod 8) 7: 𝑚𝑠𝑔 ← 𝑚𝑠𝑔 ∥ base_2b (toByte (𝑐𝑠𝑢𝑚, ⌈

▷ for 𝑙𝑔𝑤 = 4, left shift by 4 ▷ convert to base 𝑤

𝑙𝑒𝑛2 ⋅𝑙𝑔𝑤 ⌉) , 𝑙𝑔𝑤 , 𝑙𝑒𝑛2 ) 8

8: for 𝑖 from 0 to 𝑙𝑒𝑛 − 1 do 9: ADRS.setChainAddress(𝑖) 10: 𝑡𝑚𝑝[𝑖] ← chain(𝑠𝑖𝑔[𝑖], 𝑚𝑠𝑔[𝑖], 𝑤 − 1 − 𝑚𝑠𝑔[𝑖], PK.seed, ADRS) 11: end for 12: wotspkADRS ← ADRS ▷ copy address to create WOTS+ public key address 13: wotspkADRS.setTypeAndClear(WOTS_PK) 14: wotspkADRS.setKeyPairAddress(ADRS.getKeyPairAddress()) 15: 𝑝𝑘𝑠𝑖𝑔 ← T𝑙𝑒𝑛 (PK.seed, wotspkADRS, 𝑡𝑚𝑝) 16: return 𝑝𝑘𝑠𝑖𝑔

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

eXtended Merkle Signature Scheme (XMSS)

XMSS extends the WOTS+ signature scheme into one that can sign multiple messages. A Merkle ′ tree [13] of height ℎ′ is used to allow 2ℎ WOTS+ public keys to be authenticated using a single 𝑛-byte XMSS public key, which is the root of the Merkle tree.12 As each WOTS+ key may be used ′ to sign one message, the XMSS key may be used to sign 2ℎ messages. An XMSS signature is (ℎ′ + 𝑙𝑒𝑛) ⋅ 𝑛 bytes in length and consists of a WOTS+ signature and an authentication path (see Figure 11). The authentication path is an array of nodes from the Merkle tree — one from each level of the tree, except for the root — that allows the verifier to compute the root of the tree when used in conjunction with the WOTS+ public key that can be computed from the WOTS+ signature. SIGWOTS+ AUTH[0] ⋯ AUTH[ℎ′ − 1]

𝑙𝑒𝑛 ⋅ 𝑛 bytes 𝑛 bytes 𝑛 bytes

Figure 11. XMSS signature data format

6.1 Generating a Merkle Hash Tree The xmss_node function (Algorithm 9) computes the nodes of an XMSS tree. The xmss_node function takes as input SK.seed and PK.seed from the SLH-DSA private key; a target node index 𝑖, which is the index of the node being computed; a target node height 𝑧, which is the height within the Merkle tree of the node being computed; and an address. The address ADRS must have the layer address and tree address set to the XMSS tree within which the node is being ′ computed. The target node height and index must satisfy 𝑧 ≤ ℎ′ and 𝑖 < 2(ℎ −𝑧) . Each node in an XMSS tree is the root of a subtree, and Algorithm 9 computes the root of the subtree recursively. If the subtree consists of a single leaf node, then the function simply returns the value of the node’s WOTS+ public key (lines 2 through 4). Otherwise, the function computes the roots of the left subtree (line 6) and right subtree (line 7) and hashes them together (lines 8 through 11).

′

The Merkle tree formed from the 2ℎ WOTS+ keys of an XMSS key is referred to in this standard as an XMSS tree.

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

Algorithm 9 xmss_node(SK.seed, 𝑖, 𝑧, PK.seed, ADRS) Computes the root of a Merkle subtree of WOTS+ public keys. Input: Secret seed SK.seed, target node index 𝑖, target node height 𝑧, public seed PK.seed, address ADRS. Output: 𝑛-byte root 𝑛𝑜𝑑𝑒. 1: if 𝑧 = 0 then 2: ADRS.setTypeAndClear(WOTS_HASH) 3: ADRS.setKeyPairAddress(𝑖) 4: 𝑛𝑜𝑑𝑒 ← wots_pkGen(SK.seed, PK.seed, ADRS) 5: else 6: 𝑙𝑛𝑜𝑑𝑒 ← xmss_node(SK.seed, 2𝑖, 𝑧 − 1, PK.seed, ADRS) 7: 𝑟𝑛𝑜𝑑𝑒 ← xmss_node(SK.seed, 2𝑖 + 1, 𝑧 − 1, PK.seed, ADRS) 8: ADRS.setTypeAndClear(TREE) 9: ADRS.setTreeHeight(𝑧) 10: ADRS.setTreeIndex(𝑖) 11: 𝑛𝑜𝑑𝑒 ← H(PK.seed, ADRS, 𝑙𝑛𝑜𝑑𝑒 ∥ 𝑟𝑛𝑜𝑑𝑒) 12: end if 13: return 𝑛𝑜𝑑𝑒

6.2 Generating an XMSS Signature The xmss_sign function (Algorithm 10) creates an XMSS signature on an 𝑛-byte message 𝑀13 by creating an authentication path (lines 1 through 4) and signing 𝑀 with the appropriate WOTS+ key (lines 5 through 7). In addition to 𝑀, xmss_sign takes SK.seed and PK.seed from the SLH-DSA private key, an address, and an index as input. The address ADRS must have the layer address and tree address set to the XMSS key that is being used to sign the message, and the index 𝑖𝑑𝑥 must be the index of the WOTS+ key within the XMSS tree that will be used to sign the message. The authentication path consists of the sibling nodes of each node that is on the path from the WOTS+ key used to the root. For example, in Figure 12, if the message is signed with 𝐾2 , then 𝐾2 , 𝑛1,1 , and 𝑛2,0 are the on path nodes, and the authentication path consists of 𝐾3 , 𝑛1,0 , and 𝑛2,1 . In line 2 of Algorithm 10, ⌊𝑖𝑑𝑥/2𝑗 ⌋ is the on path node, and ⌊𝑖𝑑𝑥/2𝑗 ⌋ ⊕ 1 is the authentication path node. Line 3 computes the value of the authentication path node.

In SLH-DSA, the message 𝑀 that is signed using XMSS is either an XMSS public key or a FORS public key.

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

Algorithm 10 xmss_sign(𝑀, SK.seed, 𝑖𝑑𝑥, PK.seed, ADRS) Generates an XMSS signature. Input: 𝑛-byte message 𝑀, secret seed SK.seed, index 𝑖𝑑𝑥, public seed PK.seed, address ADRS. Output: XMSS signature SIG𝑋𝑀𝑆𝑆 = (𝑠𝑖𝑔 ∥ AUTH). 1: for 𝑗 from 0 to ℎ′ − 1 do ▷ build authentication path 𝑗 2: 𝑘 ← ⌊𝑖𝑑𝑥/2 ⌋ ⊕ 1 3: AUTH[𝑗] ← xmss_node(SK.seed, 𝑘, 𝑗, PK.seed, ADRS) 4: end for 5: ADRS.setTypeAndClear(WOTS_HASH) 6: ADRS.setKeyPairAddress(𝑖𝑑𝑥) 7: 𝑠𝑖𝑔 ← wots_sign(𝑀 , SK.seed, PK.seed, ADRS) 8: SIG𝑋𝑀𝑆𝑆 ← 𝑠𝑖𝑔 ∥ AUTH 9: return SIG𝑋𝑀𝑆𝑆

𝑛3,0 = H(𝑛2,0 ∥ 𝑛2,1 )

P P

𝑛2,0 = H(𝑛1,0 ∥ 𝑛1,1 )

𝑛2,1 = H(𝑛1,2 ∥ 𝑛1,3 )

� �

@ @

𝑛1,0 = H(𝐾0 ∥ 𝐾1 ) 𝑛1,1 = H(𝐾2 ∥ 𝐾3 ) 𝑛1,2 = H(𝐾4 ∥ 𝐾5 ) 𝑛1,3 = H(𝐾6 ∥ 𝐾7 ) � �

𝐾0

@ @

𝐾1

� �

𝐾2

@ @

� �

𝐾3

@ @

𝐾4

Figure 12. Merkle hash tree

𝐾5

� �

𝐾6

@ @

𝐾7

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

6.3 Computing an XMSS Public Key From a Signature Verifying an XMSS signature involves computing a public-key value from a message and a signature value. Verification succeeds if the correct public-key value is computed, which is determined by using the computed public-key value along with other information to compute a candidate PK.root value and then comparing that value to the known value of PK.root from the SLH-DSA public key. This section describes xmss_pkFromSig (Algorithm 11), a function that computes a candidate XMSS public key from an XMSS signature and corresponding message. In addition to an 𝑛-byte message 𝑀 and an (𝑙𝑒𝑛+ℎ′ )⋅𝑛-byte signature SIG𝑋𝑀𝑆𝑆 , xmss_pkFromSig takes PK.seed from the SLH-DSA public key, an address, and an index as input. The address ADRS must be set to the layer address and tree address of the XMSS key that was used to sign the message, and the index 𝑖𝑑𝑥 must be the index of the WOTS+ key within the XMSS tree that was used to sign the message. Algorithm 11 begins by computing the WOTS+ public key in lines 1 through 5. The root is then computed in lines 6 through 18. Starting with the leaf node (i.e., the WOTS+ public key), a node at each level of the tree is computed by hashing together the node computed in the previous iteration with the corresponding authentication path node. In lines 12 and 15, AUTH is interpreted as an array of ℎ′ 𝑛-byte strings. Algorithm 11 xmss_pkFromSig(𝑖𝑑𝑥, SIG𝑋𝑀𝑆𝑆 , 𝑀, PK.seed, ADRS) Computes an XMSS public key from an XMSS signature. Input: Index 𝑖𝑑𝑥, XMSS signature SIG𝑋𝑀𝑆𝑆 = (𝑠𝑖𝑔 ∥ AUTH), 𝑛-byte message 𝑀, public seed PK.seed, address ADRS. Output: 𝑛-byte root value 𝑛𝑜𝑑𝑒[0]. 1: ADRS.setTypeAndClear(WOTS_HASH) ▷ compute WOTS+ pk from WOTS+ 𝑠𝑖𝑔 2: ADRS.setKeyPairAddress(𝑖𝑑𝑥) 3: 𝑠𝑖𝑔 ← SIG𝑋𝑀𝑆𝑆 .getWOTSSig() ▷ SIG𝑋𝑀𝑆𝑆 [0 ∶ 𝑙𝑒𝑛 ⋅ 𝑛] 4: AUTH ← SIG𝑋𝑀𝑆𝑆 .getXMSSAUTH() ▷ SIG𝑋𝑀𝑆𝑆 [𝑙𝑒𝑛 ⋅ 𝑛 ∶ (𝑙𝑒𝑛 + ℎ′ ) ⋅ 𝑛] 5: 𝑛𝑜𝑑𝑒[0] ← wots_pkFromSig(𝑠𝑖𝑔, 𝑀 , PK.seed, ADRS) 6: ADRS.setTypeAndClear(TREE) ▷ compute root from WOTS+ pk and AUTH 7: ADRS.setTreeIndex(𝑖𝑑𝑥) 8: for 𝑘 from 0 to ℎ′ − 1 do 9: ADRS.setTreeHeight(𝑘 + 1) 10: if ⌊𝑖𝑑𝑥/2𝑘 ⌋ is even then 11: ADRS.setTreeIndex(ADRS.getTreeIndex()/2) 12: 𝑛𝑜𝑑𝑒[1] ← H(PK.seed, ADRS, 𝑛𝑜𝑑𝑒[0] ∥ AUTH[𝑘]) 13: else 14: ADRS.setTreeIndex((ADRS.getTreeIndex() − 1)/2) 15: 𝑛𝑜𝑑𝑒[1] ← H(PK.seed, ADRS, AUTH[𝑘] ∥ 𝑛𝑜𝑑𝑒[0]) 16: end if 17: 𝑛𝑜𝑑𝑒[0] ← 𝑛𝑜𝑑𝑒[1] 18: end for 19: return 𝑛𝑜𝑑𝑒[0]

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

The SLH-DSA Hypertree

SLH-DSA requires a very large number of WOTS+ keys to sign FORS public keys. As it would not be feasible for the parameter sets in this standard to have a single XMSS key with so many WOTS+ keys, SLH-DSA uses a hypertree to sign the FORS keys. As depicted in Figure 1, a hypertree is a tree of XMSS trees. The XMSS keys at the lowest layer are used to sign FORS public keys (Section 8), and the XMSS keys at every other layer are used to sign the XMSS public keys at the layer below. The hypertree has 𝑑 layers of XMSS trees with each XMSS tree being a Merkle tree of height ℎ′ , so the total height of the hypertree is ℎ = 𝑑 ⋅ ℎ′ (see Table 2). The top layer (layer 𝑑 − 1) is a single XMSS tree, and the public key of this XMSS key pair (i.e., the root of the Merkle tree) is the ′ public key of the hypertree (PK.root). The next layer down has 2ℎ XMSS trees, and the public ′ key of each of these XMSS keys is signed by one of the 2ℎ WOTS+ keys that is part of the top ′ layer’s XMSS key. The lowest layer has 2ℎ−ℎ XMSS trees, providing 2ℎ WOTS+ keys to sign FORS keys.

7.1 Hypertree Signature Generation A hypertree signature is (ℎ + 𝑑 ⋅ 𝑙𝑒𝑛) ⋅ 𝑛 bytes in length and consists of a sequence of 𝑑 XMSS signatures, starting with a signature generated using an XMSS key at the lowest layer and ending with a signature generated using the XMSS key at the top layer (see Figure 13). XMSS signature SIGXMSS (layer 0) XMSS signature SIGXMSS (layer 1) ⋯ XMSS signature SIGXMSS (layer 𝑑 − 1)

(ℎ′ + 𝑙𝑒𝑛) ⋅ 𝑛 bytes (ℎ′ + 𝑙𝑒𝑛) ⋅ 𝑛 bytes (ℎ′ + 𝑙𝑒𝑛) ⋅ 𝑛 bytes

Figure 13. HT signature data format In addition to the 𝑛-byte message 𝑀,14 the ht_sign function (Algorithm 12) takes as input SK.seed and PK.seed from the SLH-DSA private key, the index of the XMSS tree at the lowest layer that will sign the message 𝑖𝑑𝑥𝑡𝑟𝑒𝑒 , and the index of the WOTS+ key within the XMSS tree that will sign the message 𝑖𝑑𝑥𝑙𝑒𝑎𝑓 . Algorithm 12 begins in lines 1 through 3 by signing 𝑀 with the specified XMSS key using the WOTS+ key within that XMSS key specified by 𝑖𝑑𝑥𝑙𝑒𝑎𝑓 . The XMSS public key is obtained (line 5 or 14) for each successive layer and signed by the appropriate key at the next higher level (lines 7 through 11).

In SLH-DSA, the message 𝑀 that is provided to ht_sign is a FORS public key.

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

Algorithm 12 ht_sign(𝑀, SK.seed, PK.seed, 𝑖𝑑𝑥𝑡𝑟𝑒𝑒 , 𝑖𝑑𝑥𝑙𝑒𝑎𝑓 ) Generates a hypertree signature. Input: Message 𝑀, private seed SK.seed, public seed PK.seed, tree index 𝑖𝑑𝑥𝑡𝑟𝑒𝑒 , leaf index 𝑖𝑑𝑥𝑙𝑒𝑎𝑓 . Output: HT signature SIG𝐻𝑇 . 1: ADRS ← toByte(0, 32) 2: ADRS.setTreeAddress(𝑖𝑑𝑥𝑡𝑟𝑒𝑒 ) 3: SIG𝑡𝑚𝑝 ← xmss_sign(𝑀 , SK.seed, 𝑖𝑑𝑥𝑙𝑒𝑎𝑓 , PK.seed, ADRS) 4: SIG𝐻𝑇 ← SIG𝑡𝑚𝑝 5: 𝑟𝑜𝑜𝑡 ← xmss_pkFromSig(𝑖𝑑𝑥𝑙𝑒𝑎𝑓 , SIG𝑡𝑚𝑝 , 𝑀 , PK.seed, ADRS) 6: for 𝑗 from 1 to 𝑑 − 1 do ′ 7: 𝑖𝑑𝑥𝑙𝑒𝑎𝑓 ← 𝑖𝑑𝑥𝑡𝑟𝑒𝑒 mod 2ℎ ▷ ℎ′ least significant bits of 𝑖𝑑𝑥𝑡𝑟𝑒𝑒 ′ 8: 𝑖𝑑𝑥𝑡𝑟𝑒𝑒 ← 𝑖𝑑𝑥𝑡𝑟𝑒𝑒 ≫ ℎ ▷ remove least significant ℎ′ bits from 𝑖𝑑𝑥𝑡𝑟𝑒𝑒 9: ADRS.setLayerAddress(𝑗) 10: ADRS.setTreeAddress(𝑖𝑑𝑥𝑡𝑟𝑒𝑒 ) 11: SIG𝑡𝑚𝑝 ← xmss_sign(𝑟𝑜𝑜𝑡, SK.seed, 𝑖𝑑𝑥𝑙𝑒𝑎𝑓 , PK.seed, ADRS) 12: SIG𝐻𝑇 ← SIG𝐻𝑇 ∥ SIG𝑡𝑚𝑝 13: if 𝑗 < 𝑑 − 1 then 14: 𝑟𝑜𝑜𝑡 ← xmss_pkFromSig(𝑖𝑑𝑥𝑙𝑒𝑎𝑓 , SIG𝑡𝑚𝑝 , 𝑟𝑜𝑜𝑡, PK.seed, ADRS) 15: end if 16: end for 17: return SIG𝐻𝑇

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

7.2 Hypertree Signature Verification Hypertree signature verification works by making 𝑑 calls to xmss_pkFromSig (Algorithm 11) and comparing the result to the public key of the hypertree. In addition to the 𝑛-byte message 𝑀 and the (ℎ + 𝑑 ⋅ 𝑙𝑒𝑛) ⋅ 𝑛-byte signature SIG𝐻𝑇 , ht_verify (Algorithm 13) takes as input PK.seed and PK.root from the SLH-DSA public key, the index of the XMSS tree at the lowest layer that signed the message 𝑖𝑑𝑥𝑡𝑟𝑒𝑒 , and the index of the WOTS+ key within the XMSS tree that signed the message 𝑖𝑑𝑥𝑙𝑒𝑎𝑓 . At each layer, either the message 𝑀 or the computed public key of the XMSS key at the lower layer is provided along with the appropriate XMSS signature to xmss_pkFromSig in order to obtain the layer’s computed XMSS public key. If the computed XMSS public key of the top layer tree is the same as the known hypertree public key, PK.root, then verification succeeds. Algorithm 13 ht_verify(𝑀, SIG𝐻𝑇 , PK.seed, 𝑖𝑑𝑥𝑡𝑟𝑒𝑒 , 𝑖𝑑𝑥𝑙𝑒𝑎𝑓 , PK.root) Verifies a hypertree signature. Input: Message 𝑀, signature SIG𝐻𝑇 , public seed PK.seed, tree index 𝑖𝑑𝑥𝑡𝑟𝑒𝑒 , leaf index 𝑖𝑑𝑥𝑙𝑒𝑎𝑓 , HT public key PK.root. Output: Boolean. 1: ADRS ← toByte(0, 32) 2: ADRS.setTreeAddress(𝑖𝑑𝑥𝑡𝑟𝑒𝑒 ) 3: SIG𝑡𝑚𝑝 ← SIG𝐻𝑇 .getXMSSSignature(0) ▷ SIG𝐻𝑇 [0 ∶ (ℎ′ + 𝑙𝑒𝑛) ⋅ 𝑛] 4: 𝑛𝑜𝑑𝑒 ← xmss_pkFromSig(𝑖𝑑𝑥𝑙𝑒𝑎𝑓 , SIG𝑡𝑚𝑝 , 𝑀 , PK.seed, ADRS) 5: for 𝑗 from 1 to 𝑑 − 1 do ′ 6: 𝑖𝑑𝑥𝑙𝑒𝑎𝑓 ← 𝑖𝑑𝑥𝑡𝑟𝑒𝑒 mod 2ℎ ▷ ℎ′ least significant bits of 𝑖𝑑𝑥𝑡𝑟𝑒𝑒 7: 𝑖𝑑𝑥𝑡𝑟𝑒𝑒 ← 𝑖𝑑𝑥𝑡𝑟𝑒𝑒 ≫ ℎ′ ▷ remove least significant ℎ′ bits from 𝑖𝑑𝑥𝑡𝑟𝑒𝑒 8: ADRS.setLayerAddress(𝑗) 9: ADRS.setTreeAddress(𝑖𝑑𝑥𝑡𝑟𝑒𝑒 ) 10: SIG𝑡𝑚𝑝 ← SIG𝐻𝑇 .getXMSSSignature(𝑗) ▷ SIG𝐻𝑇 [𝑗 ⋅ (ℎ′ + 𝑙𝑒𝑛) ⋅ 𝑛 ∶ (𝑗 + 1)(ℎ′ + 𝑙𝑒𝑛) ⋅ 𝑛] 11: 𝑛𝑜𝑑𝑒 ← xmss_pkFromSig(𝑖𝑑𝑥𝑙𝑒𝑎𝑓 , SIG𝑡𝑚𝑝 , 𝑛𝑜𝑑𝑒, PK.seed, ADRS) 12: end for 13: if 𝑛𝑜𝑑𝑒 = PK.root then 14: return true 15: else 16: return false 17: end if

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

Forest of Random Subsets (FORS)

FORS is a few-time signature scheme that is used to sign the digests of the actual messages. Unlike WOTS+ , for which forgeries become feasible if a key is used twice [22], the security of a FORS key degrades gradually as the number of signatures increases. FORS uses two parameters: 𝑘 and 𝑡 = 2𝑎 (see Table 2). A FORS private key consists of 𝑘 sets of 𝑡 𝑛-byte strings, all of which are pseudorandomly generated from the seed SK.seed. Each of the 𝑘 sets is formed into a Merkle tree, and the roots of the trees are hashed together to form the FORS public key. A signature on a 𝑘 ⋅ 𝑎-bit message digest consists of 𝑘 elements from the private key, one from each set selected using 𝑎 bits of the message digest, along with the authentication paths for each of these elements (see Figure 14). private key value (tree 0)

𝑛 bytes

AUTH (tree 0)

𝑎 ⋅ 𝑛 bytes

⋯ private key value (tree 𝑘 − 1)

𝑛 bytes

AUTH (tree 𝑘 − 1)

𝑎 ⋅ 𝑛 bytes

Figure 14. FORS signature data format

8.1 Generating FORS Secret Values The fors_skGen function (Algorithm 14) generates the 𝑛-byte strings of the FORS private key. The function takes SK.seed and PK.seed from the SLH-DSA private key, an address, and an index as input. The 𝑡𝑦𝑝𝑒 in the address ADRS must be set to FORS_TREE, and the tree address and key pair address must be set to the index of the WOTS+ key within the XMSS tree that signs the FORS key. The layer address must be set to zero. The index 𝑖𝑑𝑥 is the index of the FORS secret value within the sets of FORS trees. Algorithm 14 fors_skGen(SK.seed, PK.seed, ADRS, 𝑖𝑑𝑥) Generates a FORS private-key value. Input: Secret seed SK.seed, public seed PK.seed, address ADRS, secret key index 𝑖𝑑𝑥. Output: 𝑛-byte FORS private-key value. 1: skADRS ← ADRS ▷ copy address to create key generation address 2: skADRS.setTypeAndClear(FORS_PRF) 3: skADRS.setKeyPairAddress(ADRS.getKeyPairAddress()) 4: skADRS.setTreeIndex(𝑖𝑑𝑥) 5: return PRF(PK.seed, SK.seed, skADRS)

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

8.2 Generating a Merkle Hash Tree The fors_node function (Algorithm 15) computes the nodes of a Merkle tree. It is the same as xmss_node, except that the leaf nodes are the hashes of the FORS secret values instead of WOTS+ public keys. The fors_node function takes as input SK.seed and PK.seed from the SLH-DSA private key; a target node index 𝑖, which is the index of the node being computed; a target node height 𝑧, which is the height within the Merkle tree of the node being computed; and an address. The address ADRS must have the layer address set to zero (since the XMSS tree that signs a FORS key is always at layer 0), the tree address set to the XMSS tree that signs the FORS key, the 𝑡𝑦𝑝𝑒 set to FORS_TREE, and the key pair address set to the index of the WOTS+ key within the XMSS tree that signs the FORS key. The target node height and index must satisfy 𝑧 ≤ 𝑎 and 𝑖 < 𝑘 ⋅ 2(𝑎−𝑧) . Each node in the Merkle tree is the root of a subtree, and Algorithm 15 computes the root of a subtree recursively. If the subtree consists of a single leaf node, then the function simply returns a hash of the node’s private 𝑛-byte string (lines 2 through 5). Otherwise, the function computes the roots of the left subtree (line 7) and right subtree (line 8) and hashes them together (lines 9 through 11). Algorithm 15 fors_node(SK.seed, 𝑖, 𝑧, PK.seed, ADRS) Computes the root of a Merkle subtree of FORS public values. Input: Secret seed SK.seed, target node index 𝑖, target node height 𝑧, public seed PK.seed, address ADRS. Output: 𝑛-byte root 𝑛𝑜𝑑𝑒. 1: if 𝑧 = 0 then 2: 𝑠𝑘 ← fors_skGen(SK.seed, PK.seed, ADRS, 𝑖) 3: ADRS.setTreeHeight(0) 4: ADRS.setTreeIndex(𝑖) 5: 𝑛𝑜𝑑𝑒 ← F(PK.seed, ADRS, 𝑠𝑘) 6: else 7: 𝑙𝑛𝑜𝑑𝑒 ← fors_node(SK.seed, 2𝑖, 𝑧 − 1, PK.seed, ADRS) 8: 𝑟𝑛𝑜𝑑𝑒 ← fors_node(SK.seed, 2𝑖 + 1, 𝑧 − 1, PK.seed, ADRS) 9: ADRS.setTreeHeight(𝑧) 10: ADRS.setTreeIndex(𝑖) 11: 𝑛𝑜𝑑𝑒 ← H(PK.seed, ADRS, 𝑙𝑛𝑜𝑑𝑒 ∥ 𝑟𝑛𝑜𝑑𝑒) 12: end if 13: return 𝑛𝑜𝑑𝑒

8.3 Generating a FORS Signature The fors_sign function (Algorithm 16) signs a 𝑘 ⋅ 𝑎-bit message digest 𝑚𝑑.15 In addition to the message digest, fors_sign takes SK.seed and PK.seed from the SLH-DSA private key and an address as input. The address ADRS must have the layer address set to zero (since the XMSS 15

For convenience, fors_sign takes a ⌈ 𝑘⋅𝑎 8 ⌉ byte message digest as input and extracts 𝑘 ⋅ 𝑎 bits to sign.

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

tree that signs a FORS key is always at layer 0), the tree address set to the XMSS tree that signs the FORS key, the 𝑡𝑦𝑝𝑒 set to FORS_TREE, and the key pair address set to the index of the WOTS+ key within the XMSS tree that signs the FORS key. The fors_sign function splits 𝑘⋅𝑎 bits of 𝑚𝑑 into 𝑘 𝑎-bit strings (line 2), each of which is interpreted as an integer between 0 and 𝑡 − 1. Each of these integers is used to select a secret value from one of the 𝑘 sets (line 4). For each secret value selected, an authentication path is computed and added to the signature (lines 5 through 9). Algorithm 16 fors_sign(𝑚𝑑, SK.seed, PK.seed, ADRS) Generates a FORS signature. Input: Message digest 𝑚𝑑, secret seed SK.seed, address ADRS, public seed PK.seed. Output: FORS signature SIG𝐹 𝑂𝑅𝑆 . 1: SIG𝐹 𝑂𝑅𝑆 = NULL ▷ initialize SIG𝐹 𝑂𝑅𝑆 as a zero-length byte string 2: 𝑖𝑛𝑑𝑖𝑐𝑒𝑠 ← base_2b (𝑚𝑑, 𝑎, 𝑘) 3: for 𝑖 from 0 to 𝑘 − 1 do ▷ compute signature elements 4: SIG𝐹 𝑂𝑅𝑆 ← SIG𝐹 𝑂𝑅𝑆 ∥ fors_skGen(SK.seed, PK.seed, ADRS, 𝑖 ⋅ 2𝑎 + 𝑖𝑛𝑑𝑖𝑐𝑒𝑠[𝑖]) 5: for 𝑗 from 0 to 𝑎 − 1 do ▷ compute auth path 6: 𝑠 ← ⌊𝑖𝑛𝑑𝑖𝑐𝑒𝑠[𝑖]/2𝑗 ⌋ ⊕ 1 7: AUTH[𝑗] ← fors_node(SK.seed, 𝑖 ⋅ 2𝑎−𝑗 + 𝑠, 𝑗, PK.seed, ADRS) 8: end for 9: SIG𝐹 𝑂𝑅𝑆 ← SIG𝐹 𝑂𝑅𝑆 ∥ AUTH 10: end for 11: return SIG𝐹 𝑂𝑅𝑆

8.4 Computing a FORS Public Key From a Signature Verifying a FORS signature involves computing a public-key value from a message digest and a signature value. Verification succeeds if the correct public-key value is computed, which is determined by verifying the hypertree signature on the computed public-key value using the SLHDSA public key. This section describes fors_pkFromSig (Algorithm 17), a function that computes a candidate FORS public key from a FORS signature and corresponding message digest. In addition to a message digest 𝑚𝑑 and a 𝑘 ⋅ (𝑎 + 1) ⋅ 𝑛-byte signature SIG𝐹 𝑂𝑅𝑆 , fors_pkFromSig takes PK.seed from the SLH-DSA public key and an address as input.16 The address ADRS must have the layer address set to zero (since the XMSS tree that signs a FORS key is always at layer 0), the tree address set to the XMSS tree that signs the FORS key, the 𝑡𝑦𝑝𝑒 set to FORS_TREE, and the key pair address set to the index of the WOTS+ key within the XMSS tree that signs the FORS key. The fors_pkFromSig function begins by computing the roots of each of the 𝑘 Merkle trees (lines 2 through 20). As in fors_sign, 𝑘 ⋅ 𝑎 bits of the message digest are split into 𝑘 𝑎-bit strings (line 1), each of which is interpreted as an integer between 0 and 𝑡 − 1. The integers are used to determine the locations in the Merkle trees of the secret values from the signature (lines 3 16

As with fors_sign, fors_pkFromSig takes a ⌈ 𝑘⋅𝑎 8 ⌉ byte message digest as input and extracts 𝑘 ⋅ 𝑎 bits.

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

through 5). The hashes of the secret values are computed (line 6), and the hash values are used along with the corresponding authentication paths from the signature to compute the Merkle tree roots (lines 7 through 19). Once all of the Merkle tree roots have been computed, they are hashed together to compute the FORS public key (lines 21 through 24). Algorithm 17 fors_pkFromSig(SIG𝐹 𝑂𝑅𝑆 , 𝑚𝑑, PK.seed, ADRS) Computes a FORS public key from a FORS signature. Input: FORS signature SIG𝐹 𝑂𝑅𝑆 , message digest 𝑚𝑑, public seed PK.seed, address ADRS. Output: FORS public key. 1: 𝑖𝑛𝑑𝑖𝑐𝑒𝑠 ← base_2b (𝑚𝑑, 𝑎, 𝑘) 2: for 𝑖 from 0 to 𝑘 − 1 do 3: 𝑠𝑘 ← SIG𝐹 𝑂𝑅𝑆 .getSK(𝑖) ▷ SIG𝐹 𝑂𝑅𝑆 [𝑖 ⋅ (𝑎 + 1) ⋅ 𝑛 ∶ (𝑖 ⋅ (𝑎 + 1) + 1) ⋅ 𝑛] 4: ADRS.setTreeHeight(0) ▷ compute leaf 5: ADRS.setTreeIndex(𝑖 ⋅ 2𝑎 + 𝑖𝑛𝑑𝑖𝑐𝑒𝑠[𝑖]) 6: 𝑛𝑜𝑑𝑒[0] ← F(PK.seed, ADRS, 𝑠𝑘) 7: 𝑎𝑢𝑡ℎ ← SIG𝐹 𝑂𝑅𝑆 .getAUTH(𝑖) ▷ SIG𝐹 𝑂𝑅𝑆 [(𝑖 ⋅ (𝑎 + 1) + 1) ⋅ 𝑛 ∶ (𝑖 + 1) ⋅ (𝑎 + 1) ⋅ 𝑛] 8: for 𝑗 from 0 to 𝑎 − 1 do ▷ compute root from leaf and AUTH 9: ADRS.setTreeHeight(𝑗 + 1) 10: if ⌊𝑖𝑛𝑑𝑖𝑐𝑒𝑠[𝑖]/2𝑗 ⌋ is even then 11: ADRS.setTreeIndex(ADRS.getTreeIndex()/2) 12: 𝑛𝑜𝑑𝑒[1] ← H(PK.seed, ADRS, 𝑛𝑜𝑑𝑒[0] ∥ 𝑎𝑢𝑡ℎ[𝑗]) 13: else 14: ADRS.setTreeIndex((ADRS.getTreeIndex() − 1)/2) 15: 𝑛𝑜𝑑𝑒[1] ← H(PK.seed, ADRS, 𝑎𝑢𝑡ℎ[𝑗] ∥ 𝑛𝑜𝑑𝑒[0]) 16: end if 17: 𝑛𝑜𝑑𝑒[0] ← 𝑛𝑜𝑑𝑒[1] 18: end for 19: 𝑟𝑜𝑜𝑡[𝑖] ← 𝑛𝑜𝑑𝑒[0] 20: end for 21: forspkADRS ← ADRS ▷ copy address to create a FORS public-key address 22: forspkADRS.setTypeAndClear(FORS_ROOTS) 23: forspkADRS.setKeyPairAddress(ADRS.getKeyPairAddress()) 24: 𝑝𝑘 ← T𝑘 (PK.seed, forspkADRS, 𝑟𝑜𝑜𝑡) ▷ compute the FORS public key 25: return 𝑝𝑘

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

SLH-DSA Internal Functions

SLH-DSA uses the hypertree and the FORS keys to create a stateless hash-based signature scheme. The SLH-DSA private key contains a secret seed value and a secret PRF key. The public key consists of a key identifier PK.seed and the root of the hypertree. A signature is created by hashing the message, using part of the message digest to select a FORS key, signing other bits from the message digest with the FORS key, and generating a hypertree signature for the FORS key. The parameters for SLH-DSA are those specified previously for WOTS+ , XMSS, the SLH-DSA hypertree, and FORS (see Table 2). SLH-DSA uses one additional parameter 𝑚, which is the length in bytes of the message digest. It is computed as: 𝑚=⌈

ℎ′ 𝑘⋅𝑎 ℎ − ℎ′ ⌉+⌈ ⌉+⌈ ⌉ 8 8 8

SLH-DSA uses ℎ bits of the message digest to select a FORS key: ℎ − ℎ′ bits to select an XMSS tree at the lowest layer and ℎ′ bits to select a WOTS+ key and corresponding FORS key from that tree. 𝑘 ⋅ 𝑎 bits of the digest are signed by the selected FORS key. While only ℎ + 𝑘 ⋅ 𝑎 bits of the message digest are used, implementation is simplified by extracting the necessary bits from a slightly larger digest. This section describes the functions for SLH-DSA key generation, signature generation, and signature verification. In the functions in this section, where randomness is required, the random values are provided as inputs to the functions. The interfaces specified in this section will be used when testing of SLH-DSA implementations is performed through the Cryptographic Algorithm Validation Program (CAVP). The key generation function in this section may also be used to obtain the assurance of private key possession via regeneration, as described in Section 3.1. Other than for testing purposes, the interfaces for key generation and signature generation specified in this section should not be made available to applications, as any random values required for key generation and signature generation shall be generated by the cryptographic module. Section 10 provides guidance on the interfaces to be made available to applications.

9.1 SLH-DSA Key Generation SLH-DSA public keys contain two elements (see Figure 16). The first is an 𝑛-byte public seed PK.seed, which is used in many hash function calls to provide domain separation between different SLH-DSA key pairs. The second value is the hypertree public key (i.e., the root of the top layer XMSS tree). PK.seed shall be generated using an approved random bit generator (see SK.seed SK.prf PK.seed PK.root

𝑛 bytes 𝑛 bytes 𝑛 bytes 𝑛 bytes

PK.seed PK.root

𝑛 bytes 𝑛 bytes

Figure 16. SLH-DSA public key

Figure 15. SLH-DSA private key 33

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

[14, 15, 16]), where the instantiation of the random bit generator supports at least 8𝑛 bits of security strength. The SLH-DSA private key contains two random, secret 𝑛-byte values (see Figure 15). SK.seed is used to generate all of the WOTS+ and FORS private key elements. SK.prf is used to generate a randomization value for the randomized hashing of the message in SLH-DSA. The private key also includes a copy of the public key. Both SK.seed and SK.prf shall be generated using an approved random bit generator, where the instantiation of the random bit generator supports at least 8𝑛 bits of security strength. Algorithm 18 generates an SLH-DSA key pair. Lines 1 through 3 compute the root of the top layer XMSS tree. Line 4 bundles the three inputs and the computed PK.seed into the private and public keys. SLH-DSA signing has two variants — “hedged” and deterministic (see Section 9.2) — whose keys should only be used for the generation and verification of hedged and deterministic SLH-DSA digital signatures, respectively. Algorithm 18 slh_keygen_internal(SK.seed, SK.prf, PK.seed) Generates an SLH-DSA key pair. Input: Secret seed SK.seed, PRF key SK.prf, public seed PK.seed Output: SLH-DSA key pair (SK, PK). 1: ADRS ← toByte(0, 32) ▷ generate the public key for the top-level XMSS tree 2: ADRS.setLayerAddress(𝑑 − 1) 3: PK.root ← xmss_node(SK.seed, 0, ℎ′ , PK.seed, ADRS) 4: return ( (SK.seed, SK.prf, PK.seed, PK.root), (PK.seed, PK.root) )

9.2 SLH-DSA Signature Generation An SLH-DSA signature consists of a randomization string, a FORS signature, and a hypertree signature, as shown in Figure 17. Generating an SLH-DSA signature (Algorithm 19) begins by creating an 𝑚-byte message digest (lines 2 through 5). A PRF is used to create a message randomizer (line 3), and it is hashed along with the message to create the digest (line 5). Bits are then extracted from the message digest to be signed by the FORS key (line 6), to select an XMSS tree (lines 7 and 9), and to select a WOTS+ key and corresponding FORS key within that XMSS tree (lines 8 and 10). Next, the FORS signature is computed (lines 11 through 14), and the corresponding FORS public key is obtained (line 16). Finally, the FORS public key is signed (line 17). Randomness R FORS signature SIGFORS HT signature SIGHT

𝑛 bytes 𝑘(1 + 𝑎) ⋅ 𝑛 bytes (ℎ + 𝑑 ⋅ 𝑙𝑒𝑛) ⋅ 𝑛 bytes

Figure 17. SLH-DSA signature data format 34

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

Algorithm 19 slh_sign_internal(𝑀, SK, 𝑎𝑑𝑑𝑟𝑛𝑑) Generates an SLH-DSA signature. Input: Message 𝑀, private key SK = (SK.seed, SK.prf, PK.seed, PK.root), (optional) additional randomness 𝑎𝑑𝑑𝑟𝑛𝑑. Output: SLH-DSA signature SIG. 1: ADRS ← toByte(0, 32) 2: 𝑜𝑝𝑡_𝑟𝑎𝑛𝑑 ← 𝑎𝑑𝑑𝑟𝑛𝑑 ▷ substitute 𝑜𝑝𝑡_𝑟𝑎𝑛𝑑 ← PK.seed for the deterministic variant 3: 𝑅 ← PRF𝑚𝑠𝑔 (SK.prf, 𝑜𝑝𝑡_𝑟𝑎𝑛𝑑, 𝑀 ) ▷ generate randomizer 4: SIG ← 𝑅 5: 𝑑𝑖𝑔𝑒𝑠𝑡 ← H𝑚𝑠𝑔 (𝑅, PK.seed, PK.root, 𝑀 ) 6: 𝑚𝑑 ← 𝑑𝑖𝑔𝑒𝑠𝑡 [0 ∶ ⌈ 𝑘⋅𝑎 8 ⌉]

▷ compute message digest ▷ first ⌈ 𝑘⋅𝑎 8 ⌉ bytes ℎ−ℎ/𝑑 ▷ next ⌈ 8 ⌉ bytes

ℎ−ℎ/𝑑 8 ⌉] ℎ−ℎ/𝑑 ℎ−ℎ/𝑑 𝑘⋅𝑎 ℎ 8: 𝑡𝑚𝑝_𝑖𝑑𝑥𝑙𝑒𝑎𝑓 ← 𝑑𝑖𝑔𝑒𝑠𝑡 [⌈ 𝑘⋅𝑎 8 ⌉ + ⌈ 8 ⌉ ∶ ⌈ 8 ⌉ + ⌈ 8 ⌉ + ⌈ 8𝑑 ⌉] 𝑘⋅𝑎 7: 𝑡𝑚𝑝_𝑖𝑑𝑥𝑡𝑟𝑒𝑒 ← 𝑑𝑖𝑔𝑒𝑠𝑡 [⌈ 𝑘⋅𝑎 8 ⌉∶⌈ 8 ⌉+⌈

ℎ ▷ next ⌈ 8𝑑 ⌉ bytes

9: 𝑖𝑑𝑥𝑡𝑟𝑒𝑒 ← toInt (𝑡𝑚𝑝_𝑖𝑑𝑥𝑡𝑟𝑒𝑒 , ⌈

ℎ−ℎ/𝑑 ℎ−ℎ/𝑑 8 ⌉) mod 2 ℎ 10: 𝑖𝑑𝑥𝑙𝑒𝑎𝑓 ← toInt (𝑡𝑚𝑝_𝑖𝑑𝑥𝑙𝑒𝑎𝑓 , ⌈ 8𝑑 ⌉) mod 2ℎ/𝑑

11: ADRS.setTreeAddress(𝑖𝑑𝑥𝑡𝑟𝑒𝑒 ) 12: ADRS.setTypeAndClear(FORS_TREE) 13: ADRS.setKeyPairAddress(𝑖𝑑𝑥𝑙𝑒𝑎𝑓 ) 14: SIG𝐹 𝑂𝑅𝑆 ← fors_sign(𝑚𝑑, SK.seed, PK.seed, ADRS) 15: SIG ← SIG ∥ SIG𝐹 𝑂𝑅𝑆 16: PK𝐹 𝑂𝑅𝑆 ← fors_pkFromSig(SIG𝐹 𝑂𝑅𝑆 , 𝑚𝑑, PK.seed, ADRS) 17: SIG𝐻𝑇 ← ht_sign(PK𝐹 𝑂𝑅𝑆 , SK.seed, PK.seed, 𝑖𝑑𝑥𝑡𝑟𝑒𝑒 , 𝑖𝑑𝑥𝑙𝑒𝑎𝑓 ) 18: SIG ← SIG ∥ SIG𝐻𝑇 19: return SIG

▷ get FORS key

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

The message randomizer may be set in either a non-deterministic or deterministic way, depending on whether 𝑎𝑑𝑑𝑟𝑛𝑑 is provided as an input. For the “hedged” variant, 𝑎𝑑𝑑𝑟𝑛𝑑 is provided as an input, and 𝑜𝑝𝑡_𝑟𝑎𝑛𝑑 is set to 𝑎𝑑𝑑𝑟𝑛𝑑. The hedged variant is the default and should be used on platforms where side-channel attacks are a concern. When using the hedged version, 𝑎𝑑𝑑𝑟𝑛𝑑 shall be an 𝑛-byte random value. While 𝑎𝑑𝑑𝑟𝑛𝑑 should ideally be generated by an approved random bit generator, other methods for generating fresh random values may be used. For the deterministic variant, 𝑎𝑑𝑑𝑟𝑛𝑑 is not provided as an input, and 𝑜𝑝𝑡_𝑟𝑎𝑛𝑑 is set to PK.seed, which results in signing being deterministic (i.e., signing the same message twice will result in the same signature). The deterministic variant is available for platforms where a random bit generator is not available.

9.3 SLH-DSA Signature Verification As with signature generation, SLH-DSA signature verification (Algorithm 20) begins by computing a message digest (line 8) and then extracting 𝑚𝑑 (line 9), 𝑖𝑑𝑥𝑡𝑟𝑒𝑒 (lines 10 and 12), and 𝑖𝑑𝑥𝑙𝑒𝑎𝑓 (lines 11 and 13) from the digest. A candidate FORS public key is then computed (line 17), and the signature on the FORS key is verified (line 18). If this signature verification succeeds, then the correct FORS public key was computed, and the signature SIG on message 𝑀 is valid. Algorithm 20 slh_verify_internal(𝑀, SIG, PK) Verifies an SLH-DSA signature. Input: Message 𝑀, signature SIG, public key PK = (PK.seed, PK.root). Output: Boolean. 1: if |SIG| ≠ (1 + 𝑘(1 + 𝑎) + ℎ + 𝑑 ⋅ 𝑙𝑒𝑛) ⋅ 𝑛 then 2: return false 3: end if 4: ADRS ← toByte(0, 32) 5: 𝑅 ← SIG.getR() ▷ SIG[0 ∶ 𝑛] 6: SIG𝐹 𝑂𝑅𝑆 ← SIG.getSIG_FORS() ▷ SIG[𝑛 ∶ (1 + 𝑘(1 + 𝑎)) ⋅ 𝑛] 7: SIG𝐻𝑇 ← SIG.getSIG_HT() ▷ SIG[(1 + 𝑘(1 + 𝑎)) ⋅ 𝑛 ∶ (1 + 𝑘(1 + 𝑎) + ℎ + 𝑑 ⋅ 𝑙𝑒𝑛) ⋅ 𝑛] 8: 𝑑𝑖𝑔𝑒𝑠𝑡 ← H𝑚𝑠𝑔 (𝑅, PK.seed, PK.root, 𝑀 ) 9: 𝑚𝑑 ← 𝑑𝑖𝑔𝑒𝑠𝑡 [0 ∶ ⌈ 𝑘⋅𝑎 8 ⌉]

▷ compute message digest ▷ first ⌈ 𝑘⋅𝑎 8 ⌉ bytes ℎ−ℎ/𝑑 ▷ next ⌈ 8 ⌉ bytes

ℎ−ℎ/𝑑 8 ⌉] ℎ−ℎ/𝑑 ℎ−ℎ/𝑑 ℎ 𝑘⋅𝑎 11: 𝑡𝑚𝑝_𝑖𝑑𝑥𝑙𝑒𝑎𝑓 ← 𝑑𝑖𝑔𝑒𝑠𝑡 [⌈ 𝑘⋅𝑎 8 ⌉ + ⌈ 8 ⌉ ∶ ⌈ 8 ⌉ + ⌈ 8 ⌉ + ⌈ 8𝑑 ⌉] 𝑘⋅𝑎 10: 𝑡𝑚𝑝_𝑖𝑑𝑥𝑡𝑟𝑒𝑒 ← 𝑑𝑖𝑔𝑒𝑠𝑡 [⌈ 𝑘⋅𝑎 8 ⌉∶⌈ 8 ⌉+⌈

ℎ ▷ next ⌈ 8𝑑 ⌉ bytes

12: 𝑖𝑑𝑥𝑡𝑟𝑒𝑒 ← toInt (𝑡𝑚𝑝_𝑖𝑑𝑥𝑡𝑟𝑒𝑒 , ⌈

ℎ−ℎ/𝑑 ℎ−ℎ/𝑑 8 ⌉) mod 2 ℎ 13: 𝑖𝑑𝑥𝑙𝑒𝑎𝑓 ← toInt (𝑡𝑚𝑝_𝑖𝑑𝑥𝑙𝑒𝑎𝑓 , ⌈ 8𝑑 ⌉) mod 2ℎ/𝑑

▷ compute FORS public key

14: ADRS.setTreeAddress(𝑖𝑑𝑥𝑡𝑟𝑒𝑒 ) 15: ADRS.setTypeAndClear(FORS_TREE) 16: ADRS.setKeyPairAddress(𝑖𝑑𝑥𝑙𝑒𝑎𝑓 )

17: PK𝐹 𝑂𝑅𝑆 ← fors_pkFromSig(SIG𝐹 𝑂𝑅𝑆 , 𝑚𝑑, PK.seed, ADRS) 18: return ht_verify(PK𝐹 𝑂𝑅𝑆 , SIG𝐻𝑇 , PK.seed, 𝑖𝑑𝑥𝑡𝑟𝑒𝑒 , 𝑖𝑑𝑥𝑙𝑒𝑎𝑓 , PK.root)

FIPS 205

10.

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

SLH-DSA External Functions

This section provides guidance on the key generation, signature generation, and signature verification functions that should be provided for use by applications. The functions in this section use the functions in Section 9 to implement the underlying SLH-DSA scheme.

10.1 SLH-DSA Key Generation Algorithm 21 generates an SLH-DSA key pair. Lines 1 through 3 generate the random values for the private and public keys, and line 7 calls slh_keygen_internal to compute PK.root and return the private and public key. PK.seed, SK.seed, and SK.prf shall be generated using an approved random bit generator (see [14, 15, 16]), where the instantiation of the random bit generator supports at least 8𝑛 bits of security strength. Algorithm 21 slh_keygen() Generates an SLH-DSA key pair. Input: (none) Output: SLH-DSA key pair (SK, PK). $

1: SK.seed ← − 𝔹𝑛 $

2: SK.prf ← −𝔹

𝑛

▷ set SK.seed, SK.prf, and PK.seed to random 𝑛-byte ▷ strings using an approved random bit generator

3: PK.seed ← − 𝔹𝑛 4: if SK.seed = NULL or SK.prf = NULL or PK.seed = NULL then 5: return ⊥ ▷ return an error indication if random bit generation failed 6: end if 7: return slh_keygen_internal(SK.seed, SK.prf, PK.seed)

10.2 SLH-DSA Signature Generation This section presents two versions of SLH-DSA signature generation: a “pure” version (slh_sign) and a “pre-hash” version (hash_slh_sign). Both versions use slh_sign_internal, but they differ in how the message input to slh_sign_internal is created from the content to be signed. In the pure version, the content is signed by slh_sign_internal along with some domain separation information. In the pre-hash version, a hash of the content is signed by slh_sign_internal along with some domain separation information. Both versions take the content to be signed, the private key, and a context as input. The pre-hash version also takes as input a hash function or XOF that is to be used to pre-hash the content to be signed. The context string has a maximum length of 255 bytes. By default, the context is the empty string. However, applications may specify the use of a non-empty context string. The identifier for a signature (e.g., the object identifier [OID]) should indicate whether the signature is a pure signature or a pre-hash signature. In the case of pre-hash signatures, the identifier should also indicate the hash function or XOF used to compute the pre-hash.17 While 17

In the case of a XOF, this would also include the length of the output from the XOF.

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

a single key pair may be used for both pure and pre-hash signatures, it is recommended that each key pair only be used for one version or the other. If a non-empty context string is to be used, this should either be indicated by the signature’s identifier or the application with which the signature is being used. If the default hedged variant of slh_sign_internal is used, the 𝑛-byte random value 𝑎𝑑𝑑𝑟𝑛𝑑 shall be generated by the cryptographic module that runs slh_sign_internal. However, 𝑀 ′ in Algorithms 22 and 23 may be constructed outside of the crytographic module. In the case of hash_slh_sign, the hash or XOF of the content to be signed must be computed within a FIPS 140-validated cryptographic module, but it may be a different cryptographic module than the one that runs slh_sign_internal. In general, the pure version is preferred. However, for some cryptographic modules that generate SLH-DSA signatures, performing lines 3 and 5 of Algorithm 19 may be infeasible if the message 𝑀 is large. This may, for example, be the result of the module having limited memory to store the message to be signed. Similarly, for some cryptographic modules that verify SLH-DSA signatures, performing line 8 of Algorithm 20 may be infeasible if the message 𝑀 is large. For some use cases, these issues may be addressed by signing a digest of the content rather than signing the content directly. In many cases where the content to be signed is large, hashing of the content is performed at the application level. For example, in the Cryptographic Message Syntax [23], a digest of the content may be computed, and that digest is signed along with other attributes. In cases in which the content is not hashed at the application level, the pre-hash version of SLH-DSA signing (Section 10.2.2) may be used. To maintain the same level of security strength when the content is hashed at the application level or when using the pre-hash version of SLH-DSA, the digest that is signed needs to be generated using an approved hash function or XOF (e.g., from FIPS 180-4 [8] or FIPS 202 [6]) that provides at least 8𝑛 bits of classical security strength against both collision and second preimage attacks [6, Table 4].18 Verification of a signature created in this way will require the verify function to generate a digest from the message in the same way for input to the verification function. Even if it is feasible to compute collisions on the hash functions or XOF used to instantiate H𝑚𝑠𝑔 , PRF, PRF𝑚𝑠𝑔 , F, H, and T𝑙 , there is believed to be no adverse effect on the security of SLH-DSA.19 However, if the input to the signing function is a digest of the content, then collisions on the function used to compute the digest can result in forged messages. 10.2.1 Pure SLH-DSA Signature Generation In the pure version, the content to be signed is prepended with a one-byte domain separator, one byte that indicates the length of the context string, and the context string. The domain separator, which has a value of zero for pure signing, is included to prevent pre-hash signatures from verifying as pure signatures and vice versa. In the default case in which the context string 18

Obtaining at least 8𝑛 bits of classical security strength against collision attacks requires that the digest to be signed is at least 2𝑛 bytes in length. 19 As noted in Section 11, applications that require message-bound signatures may be adversely affected if it is feasible to compute collisions on H𝑚𝑠𝑔 .

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

is empty, pure signing simply involves prepending two zero bytes to the content to be signed and passing the result to slh_sign_internal along with the private key and, in the case of hedged signing, an 𝑛-byte random value. Algorithm 22 slh_sign(𝑀, 𝑐𝑡𝑥, SK) Generates a pure SLH-DSA signature. Input: Message 𝑀, context string 𝑐𝑡𝑥, private key SK. Output: SLH-DSA signature SIG. 1: if |𝑐𝑡𝑥| > 255 then return ⊥ ▷ return an error indication if the context string is too long 2: 3: end if $

4: 𝑎𝑑𝑑𝑟𝑛𝑑 ← − 𝔹𝑛 5: if 𝑎𝑑𝑑𝑟𝑛𝑑 = NULL then 6: return ⊥ 7: end if

▷ skip lines 4 through 7 for the deterministic variant ▷ return an error indication if random bit generation failed

8: 𝑀 ′ ← toByte(0, 1) ∥ toByte(|𝑐𝑡𝑥|, 1) ∥ 𝑐𝑡𝑥 ∥ 𝑀 ▷ omit 𝑎𝑑𝑑𝑟𝑛𝑑 for the deterministic variant 9: SIG ← slh_sign_internal(𝑀 ′ , SK, 𝑎𝑑𝑑𝑟𝑛𝑑) 10: return SIG

10.2.2 HashSLH-DSA Signature Generation In the pre-hash version, the message input to slh_sign_internal is the result of applying either a hash function or a XOF to the content to be signed. The output of the hash function or XOF is prepended by a one-byte domain separator, one byte that indicates the length of the context string, the context string, and the distinguished encoding rules (DER) encoding of the hash function or XOF’s OID. The domain separator has a value of one for pre-hash signing. The DER encoding of the OID includes the tag and length. Algorithm 23 shows the DER encodings of the OIDs for SHA-256, SHA-512, SHAKE128, and SHAKE256. However, hash_slh_sign may be used with other hash functions or XOFs. SHA-256 and SHAKE128 are only appropriate for use with SLH-DSA parameter sets that are claimed to be in security category 1 (see Section 11).

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

Algorithm 23 hash_slh_sign(𝑀, 𝑐𝑡𝑥, PH, SK) Generates a pre-hash SLH-DSA signature. Input: Message 𝑀, context string 𝑐𝑡𝑥, pre-hash function PH, private key SK. Output: SLH-DSA signature SIG. 1: if |𝑐𝑡𝑥| > 255 then 2: return ⊥ ▷ return an error indication if the context string is too long 3: end if $

4: 𝑎𝑑𝑑𝑟𝑛𝑑 ← − 𝔹𝑛 5: if 𝑎𝑑𝑑𝑟𝑛𝑑 = NULL then 6: return ⊥ 7: end if

▷ skip lines 4 through 7 for the deterministic variant ▷ return an error indication if random bit generation failed

8: switch PH do 9: case SHA-256: 10: OID ← toByte(0x0609608648016503040201, 11) 11: PH𝑀 ← SHA-256(𝑀 )

▷ 2.16.840.1.101.3.4.2.1

case SHA-512: OID ← toByte(0x0609608648016503040203, 11) ▷ 2.16.840.1.101.3.4.2.3 PH𝑀 ← SHA-512(𝑀 ) 15: case SHAKE128: 16: OID ← toByte(0x060960864801650304020B, 11) ▷ 2.16.840.1.101.3.4.2.11 17: PH𝑀 ← SHAKE128(𝑀 , 256) 18: case SHAKE256: 19: OID ← toByte(0x060960864801650304020C, 11) ▷ 2.16.840.1.101.3.4.2.12 20: PH𝑀 ← SHAKE256(𝑀 , 512) 21: case … ▷ other approved hash functions or XOFs 22: … 23: end switch 24: 𝑀 ′ ← toByte(1, 1) ∥ toByte(|𝑐𝑡𝑥|, 1) ∥ 𝑐𝑡𝑥 ∥ OID ∥ PH𝑀 25: SIG ← slh_sign_internal(𝑀 ′ , SK, 𝑎𝑑𝑑𝑟𝑛𝑑) ▷ omit 𝑎𝑑𝑑𝑟𝑛𝑑 for the deterministic variant 26: return SIG 12: 13: 14:

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

10.3 SLH-DSA Signature Verification Algorithms 24 and 25 present the pure and pre-hash versions of SLH-DSA signature verification that correspond to the pure and pre-hash versions of SLH-DSA signature generation in Section 10.2. These functions construct 𝑀 ′ in the same way as Algorithms 22 and 23, respectively, and pass the resulting 𝑀 ′ to slh_verify_internal for verification. As with signature generation, 𝑀 ′ may be constructed outside of the cryptographic module that performs slh_verify_internal. However, in the case of hash_slh_verify, the hash or XOF of the content must be computed within a FIPS 140-validated cryptographic module, which may be a different cryptographic module than the one that performs slh_verify_internal. The identifier associated with the signature should indicate whether the pure or pre-hash version of signature verification should be used, and in the pre-hash case, the hash function or XOF to use to compute the pre-hash. A non-empty context string should be used in verification if one is specified in the signature’s identifier or by the application with which the signature is being used. Algorithm 24 slh_verify(𝑀, SIG, 𝑐𝑡𝑥, PK) Verifies a pure SLH-DSA signature. Input: Message 𝑀, signature SIG, context string 𝑐𝑡𝑥, public key PK. Output: Boolean. 1: if |𝑐𝑡𝑥| > 255 then 2: return false 3: end if 4: 𝑀 ′ ← toByte(0, 1) ∥ toByte(|𝑐𝑡𝑥|, 1) ∥ 𝑐𝑡𝑥 ∥ 𝑀 5: return slh_verify_internal(𝑀 ′ , SIG, PK)

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

Algorithm 25 hash_slh_verify(𝑀, SIG, 𝑐𝑡𝑥, PH, PK) Verifies a pre-hash SLH-DSA signature. Input: Message 𝑀, signature SIG, context string 𝑐𝑡𝑥, pre-hash function PH, public key PK. Output: Boolean. 1: if |𝑐𝑡𝑥| > 255 then 2: return false 3: end if 4: switch PH do 5: case SHA-256: 6: OID ← toByte(0x0609608648016503040201, 11) 7: PH𝑀 ← SHA-256(𝑀 )

▷ 2.16.840.1.101.3.4.2.1

case SHA-512: OID ← toByte(0x0609608648016503040203, 11) ▷ 2.16.840.1.101.3.4.2.3 PH𝑀 ← SHA-512(𝑀 ) 11: case SHAKE128: 12: OID ← toByte(0x060960864801650304020B, 11) ▷ 2.16.840.1.101.3.4.2.11 13: PH𝑀 ← SHAKE128(𝑀 , 256) 14: case SHAKE256: 15: OID ← toByte(0x060960864801650304020C, 11) ▷ 2.16.840.1.101.3.4.2.12 16: PH𝑀 ← SHAKE256(𝑀 , 512) 17: case … ▷ other approved hash functions or XOFs 18: … 19: end switch 20: 𝑀 ′ ← toByte(1, 1) ∥ toByte(|𝑐𝑡𝑥|, 1) ∥ 𝑐𝑡𝑥 ∥ OID ∥ PH𝑀 21: return slh_verify_internal(𝑀 ′ , SIG, PK) 8: 9: 10:

FIPS 205

11.

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

Parameter Sets

This standard approves 12 parameter sets for use with SLH-DSA. A parameter set consists of parameters for WOTS+ (𝑛 and 𝑙𝑔𝑤 ), XMSS and the SLH-DSA hypertree (ℎ and 𝑑), and FORS (𝑘 and 𝑎), as well as instantiations for the functions H𝑚𝑠𝑔 , PRF, PRF𝑚𝑠𝑔 , F, H, and Tℓ . Table 2 lists the parameter sets that are approved for use.20 Each parameter set name indicates the hash function family (SHA2 or SHAKE) that is used to instantiate the hash functions, the length in bits of the security parameter 𝑛, and whether the parameter set was designed to create relatively small signatures (‘s’) or to have relatively fast signature generation (‘f’). There are six sets of values for 𝑛, 𝑙𝑔𝑤 , ℎ, 𝑑, 𝑘, and 𝑎 that are approved for use.21 For each of the six sets of values, the functions H𝑚𝑠𝑔 , PRF, PRF𝑚𝑠𝑔 , F, H, and Tℓ may be instantiated using either SHAKE [6] or SHA-2 [8]. For the SHAKE parameter sets, the functions shall be instantiated as specified in Section 11.1. For the SHA2 parameter sets, the functions shall be instantiated as specified in Section 11.2.1 if 𝑛 = 16 and shall be instantiated as specified in Section 11.2.2 if 𝑛 = 24 or 𝑛 = 32. Table 2. SLH-DSA parameter sets

SLH-DSA-SHA2-128s SLH-DSA-SHAKE-128s SLH-DSA-SHA2-128f SLH-DSA-SHAKE-128f SLH-DSA-SHA2-192s SLH-DSA-SHAKE-192s SLH-DSA-SHA2-192f SLH-DSA-SHAKE-192f SLH-DSA-SHA2-256s SLH-DSA-SHAKE-256s SLH-DSA-SHA2-256f SLH-DSA-SHAKE-256f

pk bytes

sig bytes

𝑛

ℎ

𝑑

ℎ

𝑎

𝑘

𝑙𝑔𝑤

𝑚

security category

7 856

17 088

16 224

35 664

29 792

49 856

′

The 12 parameter sets included in Table 2 were designed to meet certain security strength categories defined by NIST in its original Call for Proposals [25] with respect to existential unforgeability under chosen message attack (EUF-CMA) when each key pair is used to sign at most 264 messages.22 These security strength categories are explained further in SP 800-57, Part 1 [9]. 20

SP 800-230 [24] specifies additional parameter sets that are approved for use. While key pairs generated for the parameter sets specified in this standard may be used to sign up to 264 messages, key pairs generated for the parameter sets in SP 800-230 are more limited in the number of signatures that may be generated. 21 In addition to 𝑛, 𝑙𝑔𝑤 , ℎ, 𝑑, 𝑘, and 𝑎, Table 2 also lists values for parameters that may be computed from these values (ℎ′ , 𝑚, public-key size(pk bytes), and signature size(sig bytes)). The security category is the security category in which the parameter set is claimed to be [10]. 22 If a key pair were used to sign 10 billion (1010 ) messages per second, it would take over 58 years to sign 264 messages.

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

Using this approach, security strength is not described by a single number, such as “128 bits of security.” Instead, each parameter set is claimed to be at least as secure as a generic block cipher with a prescribed key size. More precisely, it is claimed that the computational resources needed to break SLH-DSA are greater than or equal to the computational resources needed to break the block cipher when these computational resources are estimated using any realistic model of computation. Different models of computation can be more or less realistic and, accordingly, lead to more or less accurate estimates of security strength. Some commonly studied models are discussed in [26]. Concretely, the parameter sets with 𝑛 = 16 are claimed to be in security category 1, the parameter sets with 𝑛 = 24 are claimed to be in security category 3, and the parameter sets with 𝑛 = 32 are claimed to be in security category 5 [10]. For additional discussion of the security strength of SLH-DSA, see [10, 27]. Some applications require a property known as message-bound signatures [28, 29], which intuitively requires that it be infeasible for anyone to create a public key and a signature that are valid for two different messages. Signature schemes are not required to have this property under the EUF-CMA security definition used in assigning security categories. In the case of SLH-DSA, the key pair owner could create two messages with the same signature by finding a collision on H𝑚𝑠𝑔 . Due to the length of the output of H𝑚𝑠𝑔 , finding such a collision would be expected to require fewer computational resources than specified for the parameter sets’ claimed security categories in all cases except SLH-DSA-SHA2-128f and SLH-DSA-SHAKE-128f.23 Therefore, applications that require message-bound signatures should either take the expected cost of finding collisions on H𝑚𝑠𝑔 into account when choosing an appropriate parameter set or apply a technique (e.g., the BUFF transformation [29]) to obtain the message-bound signatures property.

11.1 SLH-DSA Using SHAKE H𝑚𝑠𝑔 , PRF, PRF𝑚𝑠𝑔 , F, H, and Tℓ shall be instantiated as follows for the SLH-DSA-SHAKE128s, SLH-DSA-SHAKE-128f, SLH-DSA-SHAKE-192s, SLH-DSA-SHAKE-192f, SLH-DSA-SHAKE-256s, and SLH-DSA-SHAKE-256f parameter sets: H𝑚𝑠𝑔 (𝑅, PK.seed, PK.root, 𝑀 ) = SHAKE256(𝑅 ∥ PK.seed ∥ PK.root ∥ 𝑀 , 8𝑚) PRF(PK.seed, SK.seed, ADRS) = SHAKE256(PK.seed ∥ ADRS ∥ SK.seed, 8𝑛) PRF𝑚𝑠𝑔 (SK.prf, 𝑜𝑝𝑡_𝑟𝑎𝑛𝑑, 𝑀 ) = SHAKE256(SK.prf ∥ 𝑜𝑝𝑡_𝑟𝑎𝑛𝑑 ∥ 𝑀 , 8𝑛) F(PK.seed, ADRS, 𝑀1 ) = SHAKE256(PK.seed ∥ ADRS ∥ 𝑀1 , 8𝑛) H(PK.seed, ADRS, 𝑀2 ) = SHAKE256(PK.seed ∥ ADRS ∥ 𝑀2 , 8𝑛) Tℓ (PK.seed, ADRS, 𝑀ℓ ) = SHAKE256(PK.seed ∥ ADRS ∥ 𝑀ℓ , 8𝑛)

11.2 SLH-DSA Using SHA2 In Sections 11.2.1 and 11.2.2, the functions MGF1-SHA-256 and MGF1-SHA-512 are MGF1 from Appendix B.2.1 of RFC 8017 [30], where Hash is SHA-256 or SHA-512, respectively. The functions

Finding a collision would be expected to require computing H𝑚𝑠𝑔 for approximately 2(ℎ+𝑘⋅𝑎)/2 different messages.

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

HMAC-SHA-256 and HMAC-SHA-512 are the HMAC function from FIPS 198-1 [31, 32], where 𝐻 is SHA-256 or SHA-512, respectively. The functions in Sections 11.2.1 and 11.2.2 make use of a compressed version of ADRS (see Figure 18). A compressed address (ADRS𝑐 ) is a 22-byte string that is the same as an ADRS with the exceptions that the encodings of the layer address and type are reduced to one byte each and the encoding of the tree address is reduced to eight bytes (i.e., ADRS𝑐 = ADRS[3] ∥ ADRS[8 ∶ 16] ∥ ADRS[19] ∥ ADRS[20 ∶ 32]). For implementations of the SHA2 parameter sets that store addresses in compressed form (i.e., 22 bytes), the member functions (Section 4.3) are as shown in Table 3 rather than Table 1.

layer address

1 byte

tree address

8 bytes

𝑡𝑦𝑝𝑒

1 byte 12 bytes

Figure 18. Compressed address (ADRS𝑐 )

Table 3. Member functions for compressed addresses Member function ADRS.setLayerAddress(𝑙) ADRS.setTreeAddress(𝑡) ADRS.setTypeAndClear(𝑌) ADRS.setKeyPairAddress(𝑖) ADRS.setChainAddress(𝑖) ADRS.setTreeHeight(𝑖) ADRS.setHashAddress(𝑖) ADRS.setTreeIndex(𝑖) 𝑖 ← ADRS.getKeyPairAddress() 𝑖 ← ADRS.getTreeIndex() 11.2.1

Expanded notation ADRS ← toByte(𝑙, 1) ∥ ADRS[1 ∶ 22] ADRS ← ADRS[0 ∶ 1] ∥ toByte(𝑡, 8) ∥ ADRS[9 ∶ 22] ADRS ← ADRS[0 ∶ 9] ∥ toByte(𝑌 , 1) ∥ toByte(0, 12) ADRS ← ADRS[0 ∶ 10] ∥ toByte(𝑖, 4) ∥ ADRS[14 ∶ 22] ADRS ← ADRS[0 ∶ 14] ∥ toByte(𝑖, 4) ∥ ADRS[18 ∶ 22] ADRS ← ADRS[0 ∶ 18] ∥ toByte(𝑖, 4) 𝑖 ← toInt(ADRS[10 ∶ 14], 4) 𝑖 ← toInt(ADRS[18 ∶ 22], 4)

SLH-DSA Using SHA2 for Security Category 1

H𝑚𝑠𝑔 , PRF, PRF𝑚𝑠𝑔 , F, H, and Tℓ shall be instantiated as follows for the SLH-DSA-SHA2-128s and SLH-DSA-SHA2-128f parameter sets: H𝑚𝑠𝑔 (𝑅, PK.seed, PK.root, 𝑀 ) = MGF1-SHA-256(𝑅 ∥ PK.seed ∥ SHA-256(𝑅 ∥ PK.seed ∥ PK.root ∥ 𝑀 ), 𝑚) 45

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

PRF(PK.seed, SK.seed, ADRS) = Trunc𝑛 (SHA-256(PK.seed ∥ toByte(0, 64 − 𝑛) ∥ ADRS𝑐 ∥ SK.seed)) PRF𝑚𝑠𝑔 (SK.prf, 𝑜𝑝𝑡_𝑟𝑎𝑛𝑑, 𝑀 ) = Trunc𝑛 (HMAC-SHA-256(SK.prf, 𝑜𝑝𝑡_𝑟𝑎𝑛𝑑 ∥ 𝑀 )) F(PK.seed, ADRS, 𝑀1 ) = Trunc𝑛 (SHA-256(PK.seed ∥ toByte(0, 64 − 𝑛) ∥ ADRS𝑐 ∥ 𝑀1 )) H(PK.seed, ADRS, 𝑀2 ) = Trunc𝑛 (SHA-256(PK.seed ∥ toByte(0, 64 − 𝑛) ∥ ADRS𝑐 ∥ 𝑀2 )) Tℓ (PK.seed, ADRS, 𝑀ℓ ) = Trunc𝑛 (SHA-256(PK.seed ∥ toByte(0, 64 − 𝑛) ∥ ADRS𝑐 ∥ 𝑀ℓ )) 11.2.2 SLH-DSA Using SHA2 for Security Categories 3 and 5 H𝑚𝑠𝑔 , PRF, PRF𝑚𝑠𝑔 , F, H, and Tℓ shall be instantiated as follows for the SLH-DSA-SHA2-192s, SLH-DSA-SHA2-192f, SLH-DSA-SHA2-256s, and SLH-DSA-SHA2-256f parameter sets: H𝑚𝑠𝑔 (𝑅, PK.seed, PK.root, 𝑀 ) = MGF1-SHA-512(𝑅 ∥ PK.seed ∥ SHA-512(𝑅 ∥ PK.seed ∥ PK.root ∥ 𝑀 ), 𝑚) PRF(PK.seed, SK.seed, ADRS) = Trunc𝑛 (SHA-256(PK.seed ∥ toByte(0, 64 − 𝑛) ∥ ADRS𝑐 ∥ SK.seed)) PRF𝑚𝑠𝑔 (SK.prf, 𝑜𝑝𝑡_𝑟𝑎𝑛𝑑, 𝑀 ) = Trunc𝑛 (HMAC-SHA-512(SK.prf, 𝑜𝑝𝑡_𝑟𝑎𝑛𝑑 ∥ 𝑀 )) F(PK.seed, ADRS, 𝑀1 ) = Trunc𝑛 (SHA-256(PK.seed ∥ toByte(0, 64 − 𝑛) ∥ ADRS𝑐 ∥ 𝑀1 )) H(PK.seed, ADRS, 𝑀2 ) = Trunc𝑛 (SHA-512(PK.seed ∥ toByte(0, 128 − 𝑛) ∥ ADRS𝑐 ∥ 𝑀2 )) Tℓ (PK.seed, ADRS, 𝑀ℓ ) = Trunc𝑛 (SHA-512(PK.seed ∥ toByte(0, 128 − 𝑛) ∥ ADRS𝑐 ∥ 𝑀ℓ ))

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

References [1] National Institute of Standards and Technology (2023) Digital Signature Standard (DSS). (Department of Commerce, Washington, D.C.), Federal Information Processing Standards Publications (FIPS) NIST FIPS 186-5. https://doi.org/10.6028/NIST.FIPS.186-5. [2] National Institute of Standards and Technology (2024) Guideline for Using Cryptographic Standards in the Federal Government: Cryptographic Mechanisms. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-175B, Rev. 2. [Forthcoming: will be available at https://csrc.nist.gov/publications]. [3] National Institute of Standards and Technology (2024) Recommendation for Obtaining Assurances for Digital Signature Applications. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-89, Rev. 1. [Forthcoming: will be available at https://csrc.nist.gov/publications]. [4] Aumasson JP, Bernstein DJ, Beullens W, Dobraunig C, Eichlseder M, Fluhrer S, Gazdag SL, Hülsing A, Kampanakis P, Kölbl S, Lange T, Lauridsen MM, Mendel F, Niederhagen R, Rechberger C, Rijneveld J, Schwabe P, Westerbaan B (2020) SPHINCS+ – Submission to the NIST post-quantum project, v.3. [5] Barker EB, Chen L, Roginsky AL, Vassilev A, Davis R, Simon S (2019) Recommendation for Pair-Wise Key-Establishment Using Integer Factorization Cryptography. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-56B, Rev. 2. https://doi.org/10.6028/NIST.SP.800-56Br2. [6] National Institute of Standards and Technology (2015) SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. (Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) NIST FIPS 202. https://doi.org/ 10.6028/NIST.FIPS.202. [7] Kelsey JM, Chang SjH, Perlner RA (2016) SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash and ParallelHash. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-185. https://doi.org/10.6028/NIST.SP.800-185. [8] National Institute of Standards and Technology (2015) Secure Hash Standard (SHS). (Department of Commerce, Washington, D.C.), Federal Information Processing Standards Publication (FIPS) NIST FIPS 180-4. https://doi.org/10.6028/NIST.FIPS.180-4. [9] National Institute of Standards and Technology (2024) Recommendation for Key Management: Part 1 – General. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-57 Part 1, Rev 6. [Forthcoming: will be available at https://csrc.nist.gov/publications]. [10] Aumasson JP, Bernstein DJ, Beullens W, Dobraunig C, Eichlseder M, Fluhrer S, Gazdag SL, Hülsing A, Kampanakis P, Kölbl S, Lange T, Lauridsen MM, Mendel F, Niederhagen R, Rechberger C, Rijneveld J, Schwabe P, Westerbaan B (2022) SPHINCS+ – Submission to the NIST post-quantum project, v.3.1. Available at https://sphincs.org/data/sphincs+-r3.1specification.pdf.

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

[11] Hülsing A, Butin D, Gazdag SL, Rijneveld J, Mohaisen A (2018) XMSS: eXtended Merkle Signature Scheme. (Internet Research Task Force (IRTF)), IRTF Request for Comments (RFC) 8391. https://doi.org/10.17487/RFC8391. [12] Cooper DA, Apon D, Dang QH, Davidson MS, Dworkin MJ, Miller CA (2020) Recommendation for Stateful Hash-Based Signature Schemes. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-208. https://doi.org/10.6028/NIST.SP. 800-208. [13] Merkle RC (1979) Secrecy, Authentication, and Public Key Systems. Ph.D. thesis. Stanford university, . [14] 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. [15] 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. [16] Barker EB, Kelsey JM, McKay KA, Roginsky AL, Sönmez Turan M (2022) Recommendation for Random Bit Generator (RBG) Constructions. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-90C 4pd. https://doi.org/10.6028/ NIST.SP.800-90C.4pd. [17] Kannwischer MJ, Genêt A, Butin D, Krämer J, Buchmann J (2018) Differential Power Analysis of XMSS and SPHINCS. Constructive Side-Channel Analysis and Secure Design, eds Fan J, Gierlichs B (Springer International Publishing, Cham), pp 168–188. https://doi.org/10.1007/ 978-3-319-89641-0_10. [18] Castelnovi L, Martinelli A, Prest T (2018) Grafting Trees: A Fault Attack Against the SPHINCS Framework. Post-Quantum Cryptography, eds Lange T, Steinwandt R (Springer International Publishing, Cham), pp 165–184. https://doi.org/10.1007/978-3-319-79063-3_8. [19] Genêt A, Kannwischer MJ, Pelletier H, McLauchlan A (2018) Practical Fault Injection Attacks on SPHINCS, Cryptology ePrint Archive preprint. https://ia.cr/2018/674. [20] Amiet D, Leuenberger L, Curiger A, Zbinden P (2020) FPGA-based SPHINCS+ Implementations: Mind the Glitch. 2020 23rd Euromicro Conference on Digital System Design (DSD), pp 229–237. https://doi.org/10.1109/DSD51259.2020.00046. [21] Genêt A (2023) On Protecting SPHINCS+ Against Fault Attacks. IACR Transactions on Cryptographic Hardware and Embedded Systems 2023(2):80–114. https://doi.org/10.46586/ tches.v2023.i2.80-114. [22] Groot Bruinderink L, Hülsing A (2018) “Oops, I Did It Again” – Security of One-Time Signatures Under Two-Message Attacks. Selected Areas in Cryptography – SAC 2017, eds Adams C, Camenisch J (Springer International Publishing, Cham), pp 299–322. https://doi.org/10. 1007/978-3-319-72565-9_15. 48

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

[23] Housley R (2009) Cryptographic Message Syntax (CMS). (Internet Engineering Task Force (IETF)), IETF Request for Comments (RFC) 5652. https://doi.org/10.17487/RFC5652. [24] National Institute of Standards and Technology (2024) Recommendation for Additional Stateless Hash-Based Digital Signature Parameter Sets. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-230. [Forthcoming: will be available at https://csrc.nist.gov/publications]. [25] National Institute of Standards and Technology (2016) Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process. Available at https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/ call-for-proposals-final-dec-2016.pdf. [26] Alagic G, Apon D, Cooper DA, Dang QH, Dang T, Kelsey JM, Lichtinger J, Liu YK, Miller CA, Moody D, Peralta R, Perlner RA, Robinson A, Smith-Tone D (2022) Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) NIST IR 8413-upd1, includes updates as of September 26, 2022. https://doi.org/ 10.6028/NIST.IR.8413-upd1. [27] Hülsing A, Kudinov M (2022) Recovering the Tight Security Proof of SPHINCS+ . Advances in Cryptology – ASIACRYPT 2022, eds Agrawal S, Lin D (Springer Nature Switzerland, Cham), pp 3–33. https://doi.org/10.1007/978-3-031-22972-5_1. [28] Stern J, Pointcheval D, Malone-Lee J, Smart NP (2002) Flaws in Applying Proof Methodologies to Signature Schemes. Advances in Cryptology — CRYPTO 2002, ed Yung M (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 93–110. https://doi.org/10.1007/3-540-45708-9_7. [29] Cremers C, Düzlü S, Fiedler R, Janson C, Fischlin M (2021) BUFFing Signature Schemes Beyond Unforgeability and the Case of Post-Quantum Signatures. 2021 IEEE Symposium on Security and Privacy (SP) (IEEE Computer Society, Los Alamitos, CA, USA), pp 1696–1714. https://doi.org/10.1109/SP40001.2021.00093. [30] Moriarty K, Kaliski B, Jonsson J, Rusch A (2016) PKCS #1: RSA Cryptography Specifications Version 2.2. (Internet Engineering Task Force (IETF)), IETF request for comments (RFC) 8017. https://doi.org/10.17487/RFC8017. [31] National Institute of Standards and Technology (2008) The Keyed-Hash Message Authentication Code (HMAC). (Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) NIST FIPS 198-1. https://doi.org/10.6028/NIST.FIPS.1981. [32] Krawczyk H, Bellare M, Canetti R (1997) HMAC: Keyed-Hashing for Message Authentication. (Internet Engineering Task Force (IETF)), IETF request for comments (RFC) 2104. https: //doi.org/10.17487/RFC2104. [33] Stern M (2021) Re: Diversity of signature schemes. Available at https://groups.google.com/ a/list.nist.gov/g/pqc-forum/c/2LEoSpskELs/m/LkUdQ5mKAwAJ. [34] Antonov S (2022) ROUND 3 OFFICIAL COMMENT: SPHINCS+. Available at https://groups. google.com/a/list.nist.gov/g/pqc-forum/c/FVItvyRea28/m/mGaRi5iZBwAJ. 49

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

[35] Perlner R, Kelsey J, Cooper D (2022) Breaking Category Five SPHINCS+ with SHA-256. PostQuantum Cryptography, eds Cheon JH, Johansson T (Springer International Publishing, Cham), pp 501–522. https://doi.org/10.1007/978-3-031-17234-2_23.

FIPS 205

STATELESS HASH-BASED DIGITAL SIGNATURE STANDARD

Appendix A — Differences From the SPHINCS+ Submission This standard is based on Version 3.1 of the SPHINCS+ specification [10] and contains several minor modifications compared to Version 3 [4], which was submitted at the beginning of round three of the NIST PQC Standardization process: • Two new address types — WOTS_PRF and FORS_PRF — were defined for WOTS+ and FORS secret key value generation. • PK.seed was added as an input to PRF in order to mitigate multi-key attacks. • For the category 3 and 5 SHA2 parameter sets, SHA-256 was replaced by SHA-512 in H𝑚𝑠𝑔 , PRF𝑚𝑠𝑔 , H, and Tℓ based on weaknesses that were discovered when using SHA-256 to obtain category 5 security [33, 34, 35]. • 𝑅 and PK.seed were added as inputs to MGF1 when computing H𝑚𝑠𝑔 for the SHA2 parameter sets in order to mitigate multi-target long-message second preimage attacks. This standard also differs from the Version 3 specification in its method for extracting bits from the message digest to select a FORS key. This change was made in order to align with the reference implementation that was submitted along with the round three specification. The description of the method for extracting indices for FORS signature generation and verification from the message digest was also changed due to ambiguity in the submitted specification. The method described in this standard is not compatible with the method used in the reference implementation that was submitted along with the round three specification. Additionally, line 6 in both wots_sign and wots_pkFromSig were changed to match the reference implementation, as the pseudocode in [10, 4] will sometimes shift 𝑐𝑠𝑢𝑚 by the incorrect amount when 𝑙𝑔𝑤 is not 4. This standard approves the use of only 12 of the 36 parameter sets defined in [10, 4]. As specified in Section 11, only the ‘simple’ instances of the SHA2 and SHAKE parameter sets are approved.

A.1

Changes From FIPS 205 Initial Public Draft

The differences from Version 3 of the SPHINCS+ specification described in Appendix A were included in the draft version of this standard (FIPS 205 ipd) that was posted on August 24, 2023. Based on comments that were submitted on FIPS 205 ipd, the SLH-DSA signature generation and verification functions were modified to include domain separation cases in which the message is signed directly and in which a digest of the message is signed. The changes were made by modifying the inputs to the signing and verification functions (see Algorithms 22, 23, 24, and 25).

NIST FIPS 205: Stateless Hash-Based Digital Signature Standard

Analyze & explore related research in Conceptio

Related documents