RFC 8391
XMSS: eXtended Merkle Signature Scheme
5. Parameter Sets
This section provides basic parameter sets that are assumed to cover most relevant applications. Parameter sets for two classical security levels are defined. Parameters with n = 32 provide a classical security level of 256 bits. Parameters with n = 64 provide a classical security level of 512 bits. Considering quantum- computer-aided attacks, these output sizes yield post-quantum security of 128 and 256 bits, respectively.
While this document specifies several parameter sets, an implementation is only REQUIRED to provide support for verification of all REQUIRED parameter sets. The REQUIRED parameter sets all use SHA2-256 to instantiate all functions. The REQUIRED parameter sets are only distinguished by the tree height parameter h (which determines the number of signatures that can be done with a single key pair) and the number of layers d (which defines a trade-off between speed and signature size). An implementation MAY provide support for signature generation using any of the proposed parameter sets. For convenience, this document defines a default option for XMSS (XMSS_SHA2_20_256) and XMSS^MT (XMSSMT-SHA2_60/3_256). These are supposed to match the most generic requirements.5.1. Implementing the Functions
For the n = 32 setting, we give parameters that use SHA2-256 as defined in [FIPS180] and other parameters that use the SHA3/Keccak- based extendable-output function SHAKE-128 as defined in [FIPS202]. For the n = 64 setting, we give parameters that use SHA2-512 as defined in [FIPS180] and other parameters that use the SHA3/Keccak- based extendable-output functions SHAKE-256 as defined in [FIPS202]. The parameter sets using SHA2-256 are mandatory for deployment and therefore MUST be provided by any implementation. The remaining parameter sets specified in this document are OPTIONAL. SHA2 does not provide a keyed-mode itself. To implement the keyed hash functions, the following is used for SHA2 with n = 32: F: SHA2-256(toByte(0, 32) || KEY || M), H: SHA2-256(toByte(1, 32) || KEY || M), H_msg: SHA2-256(toByte(2, 32) || KEY || M), and PRF: SHA2-256(toByte(3, 32) || KEY || M). Accordingly, for SHA2 with n = 64 we use: F: SHA2-512(toByte(0, 64) || KEY || M), H: SHA2-512(toByte(1, 64) || KEY || M), H_msg: SHA2-512(toByte(2, 64) || KEY || M), and PRF: SHA2-512(toByte(3, 64) || KEY || M).
The n-byte padding is used for two reasons. First, it is necessary
that the internal compression function takes 2n-byte blocks, but keys
are n and 3n bytes long. Second, the padding is used to achieve
independence of the different function families. Finally, for the
PRF, no full-fledged Hash-Based Message Authentication Code (HMAC) is
needed as the message length is fixed, meaning that standard length
extension attacks are not a concern here. For that reason, the
simpler construction above suffices.
Similar constructions are used with SHA3. To implement the keyed
hash functions, the following is used for SHA3 with n = 32:
F: SHAKE128(toByte(0, 32) || KEY || M, 256),
H: SHAKE128(toByte(1, 32) || KEY || M, 256),
H_msg: SHAKE128(toByte(2, 32) || KEY || M, 256),
PRF: SHAKE128(toByte(3, 32) || KEY || M, 256).
Accordingly, for SHA3 with n = 64, we use:
F: SHAKE256(toByte(0, 64) || KEY || M, 512),
H: SHAKE256(toByte(1, 64) || KEY || M, 512),
H_msg: SHAKE256(toByte(2, 64) || KEY || M, 512),
PRF: SHAKE256(toByte(3, 64) || KEY || M, 512).
As for SHA2, an initial n-byte identifier is used to achieve
independence of the different function families. While a shorter
identifier could be used in case of SHA3, we use n bytes for
consistency with the SHA2 implementations.
5.2. WOTS+ Parameters
To fully describe a WOTS+ signature method, the parameters n and w, as well as the functions F and PRF, MUST be specified. The following table defines several WOTS+ signature systems, each of which is identified by a name. Naming follows this convention: WOTSP-[Hashfamily]_[n in bits]. Naming does not include w as all parameter sets in this document use w=16. Values for len are provided for convenience. +-----------------+----------+----+----+-----+ | Name | F / PRF | n | w | len | +-----------------+----------+----+----+-----+ | REQUIRED: | | | | | | | | | | | | WOTSP-SHA2_256 | SHA2-256 | 32 | 16 | 67 | | | | | | | | OPTIONAL: | | | | | | | | | | | | WOTSP-SHA2_512 | SHA2-512 | 64 | 16 | 131 | | | | | | | | WOTSP-SHAKE_256 | SHAKE128 | 32 | 16 | 67 | | | | | | | | WOTSP-SHAKE_512 | SHAKE256 | 64 | 16 | 131 | +-----------------+----------+----+----+-----+ Table 1 The implementation of the single functions is done as described above. External Data Representation (XDR) formats for WOTS+ are listed in Appendix A.5.3. XMSS Parameters
To fully describe an XMSS signature method, the parameters n, w, and h, as well as the functions F, H, H_msg, and PRF, MUST be specified. The following table defines different XMSS signature systems, each of which is identified by a name. Naming follows this convention: XMSS-[Hashfamily]_[h]_[n in bits]. Naming does not include w as all parameter sets in this document use w=16.
+-------------------+-----------+----+----+-----+----+ | Name | Functions | n | w | len | h | +-------------------+-----------+----+----+-----+----+ | REQUIRED: | | | | | | | | | | | | | | XMSS-SHA2_10_256 | SHA2-256 | 32 | 16 | 67 | 10 | | | | | | | | | XMSS-SHA2_16_256 | SHA2-256 | 32 | 16 | 67 | 16 | | | | | | | | | XMSS-SHA2_20_256 | SHA2-256 | 32 | 16 | 67 | 20 | | | | | | | | | OPTIONAL: | | | | | | | | | | | | | | XMSS-SHA2_10_512 | SHA2-512 | 64 | 16 | 131 | 10 | | | | | | | | | XMSS-SHA2_16_512 | SHA2-512 | 64 | 16 | 131 | 16 | | | | | | | | | XMSS-SHA2_20_512 | SHA2-512 | 64 | 16 | 131 | 20 | | | | | | | | | XMSS-SHAKE_10_256 | SHAKE128 | 32 | 16 | 67 | 10 | | | | | | | | | XMSS-SHAKE_16_256 | SHAKE128 | 32 | 16 | 67 | 16 | | | | | | | | | XMSS-SHAKE_20_256 | SHAKE128 | 32 | 16 | 67 | 20 | | | | | | | | | XMSS-SHAKE_10_512 | SHAKE256 | 64 | 16 | 131 | 10 | | | | | | | | | XMSS-SHAKE_16_512 | SHAKE256 | 64 | 16 | 131 | 16 | | | | | | | | | XMSS-SHAKE_20_512 | SHAKE256 | 64 | 16 | 131 | 20 | +-------------------+-----------+----+----+-----+----+ Table 2 The XDR formats for XMSS are listed in Appendix B.5.3.1. Parameter Guide
In contrast to traditional signature schemes like RSA or Digital Signature Algorithm (DSA), XMSS has a tree height parameter h that determines the number of messages that can be signed with one key pair. Increasing the height allows using a key pair for more signatures, but it also increases the signature size and slows down key generation, signing, and verification. To demonstrate the impact of different values of h, the following table shows signature size and runtimes. Runtimes are given as the number of calls to F and H when the BDS algorithm is used to compute authentication paths for
the worst case. The last column shows the number of messages that can be signed with one key pair. The numbers are the same for the XMSS-SHAKE instances with same parameters h and n. +------------------+-------+------------+--------+--------+-------+ | Name | |Sig| | KeyGen | Sign | Verify | #Sigs | +------------------+-------+------------+--------+--------+-------+ | REQUIRED: | | | | | | | | | | | | | | XMSS-SHA2_10_256 | 2,500 | 1,238,016 | 5,725 | 1,149 | 2^10 | | | | | | | | | XMSS-SHA2_16_256 | 2,692 | 79*10^6 | 9,163 | 1,155 | 2^16 | | | | | | | | | XMSS-SHA2_20_256 | 2,820 | 1,268*10^6 | 11,455 | 1,159 | 2^20 | | | | | | | | | OPTIONAL: | | | | | | | | | | | | | | XMSS-SHA2_10_512 | 9,092 | 2,417,664 | 11,165 | 2,237 | 2^10 | | | | | | | | | XMSS-SHA2_16_512 | 9,476 | 155*10^6 | 17,867 | 2,243 | 2^16 | | | | | | | | | XMSS-SHA2_20_512 | 9,732 | 2,476*10^6 | 22,335 | 2,247 | 2^20 | +------------------+-------+------------+--------+--------+-------+ Table 3 As a default, users without special requirements should use option XMSS-SHA2_20_256, which allows signing of 2^20 messages with one key pair and provides reasonable speed and signature size. Users that require more signatures per key pair or faster key generation should consider XMSS^MT.5.4. XMSS^MT Parameters
To fully describe an XMSS^MT signature method, the parameters n, w, h, and d, as well as the functions F, H, H_msg, and PRF, MUST be specified. The following table defines different XMSS^MT signature systems, each of which is identified by a name. Naming follows this convention: XMSSMT-[Hashfamily]_[h]/[d]_[n in bits]. Naming does not include w as all parameter sets in this document use w=16.
+------------------------+-----------+----+----+-----+----+----+
| Name | Functions | n | w | len | h | d |
+------------------------+-----------+----+----+-----+----+----+
| REQUIRED: | | | | | | |
| | | | | | | |
| XMSSMT-SHA2_20/2_256 | SHA2-256 | 32 | 16 | 67 | 20 | 2 |
| | | | | | | |
| XMSSMT-SHA2_20/4_256 | SHA2-256 | 32 | 16 | 67 | 20 | 4 |
| | | | | | | |
| XMSSMT-SHA2_40/2_256 | SHA2-256 | 32 | 16 | 67 | 40 | 2 |
| | | | | | | |
| XMSSMT-SHA2_40/4_256 | SHA2-256 | 32 | 16 | 67 | 40 | 4 |
| | | | | | | |
| XMSSMT-SHA2_40/8_256 | SHA2-256 | 32 | 16 | 67 | 40 | 8 |
| | | | | | | |
| XMSSMT-SHA2_60/3_256 | SHA2-256 | 32 | 16 | 67 | 60 | 3 |
| | | | | | | |
| XMSSMT-SHA2_60/6_256 | SHA2-256 | 32 | 16 | 67 | 60 | 6 |
| | | | | | | |
| XMSSMT-SHA2_60/12_256 | SHA2-256 | 32 | 16 | 67 | 60 | 12 |
| | | | | | | |
| OPTIONAL: | | | | | | |
| | | | | | | |
| XMSSMT-SHA2_20/2_512 | SHA2-512 | 64 | 16 | 131 | 20 | 2 |
| | | | | | | |
| XMSSMT-SHA2_20/4_512 | SHA2-512 | 64 | 16 | 131 | 20 | 4 |
| | | | | | | |
| XMSSMT-SHA2_40/2_512 | SHA2-512 | 64 | 16 | 131 | 40 | 2 |
| | | | | | | |
| XMSSMT-SHA2_40/4_512 | SHA2-512 | 64 | 16 | 131 | 40 | 4 |
| | | | | | | |
| XMSSMT-SHA2_40/8_512 | SHA2-512 | 64 | 16 | 131 | 40 | 8 |
| | | | | | | |
| XMSSMT-SHA2_60/3_512 | SHA2-512 | 64 | 16 | 131 | 60 | 3 |
| | | | | | | |
| XMSSMT-SHA2_60/6_512 | SHA2-512 | 64 | 16 | 131 | 60 | 6 |
| | | | | | | |
| XMSSMT-SHA2_60/12_512 | SHA2-512 | 64 | 16 | 131 | 60 | 12 |
| | | | | | | |
| XMSSMT-SHAKE_20/2_256 | SHAKE128 | 32 | 16 | 67 | 20 | 2 |
| | | | | | | |
| XMSSMT-SHAKE_20/4_256 | SHAKE128 | 32 | 16 | 67 | 20 | 4 |
| | | | | | | |
| XMSSMT-SHAKE_40/2_256 | SHAKE128 | 32 | 16 | 67 | 40 | 2 |
| | | | | | | |
| XMSSMT-SHAKE_40/4_256 | SHAKE128 | 32 | 16 | 67 | 40 | 4 |
| | | | | | | |
| XMSSMT-SHAKE_40/8_256 | SHAKE128 | 32 | 16 | 67 | 40 | 8 |
| | | | | | | | | XMSSMT-SHAKE_60/3_256 | SHAKE128 | 32 | 16 | 67 | 60 | 3 | | | | | | | | | | XMSSMT-SHAKE_60/6_256 | SHAKE128 | 32 | 16 | 67 | 60 | 6 | | | | | | | | | | XMSSMT-SHAKE_60/12_256 | SHAKE128 | 32 | 16 | 67 | 60 | 12 | | | | | | | | | | XMSSMT-SHAKE_20/2_512 | SHAKE256 | 64 | 16 | 131 | 20 | 2 | | | | | | | | | | XMSSMT-SHAKE_20/4_512 | SHAKE256 | 64 | 16 | 131 | 20 | 4 | | | | | | | | | | XMSSMT-SHAKE_40/2_512 | SHAKE256 | 64 | 16 | 131 | 40 | 2 | | | | | | | | | | XMSSMT-SHAKE_40/4_512 | SHAKE256 | 64 | 16 | 131 | 40 | 4 | | | | | | | | | | XMSSMT-SHAKE_40/8_512 | SHAKE256 | 64 | 16 | 131 | 40 | 8 | | | | | | | | | | XMSSMT-SHAKE_60/3_512 | SHAKE256 | 64 | 16 | 131 | 60 | 3 | | | | | | | | | | XMSSMT-SHAKE_60/6_512 | SHAKE256 | 64 | 16 | 131 | 60 | 6 | | | | | | | | | | XMSSMT-SHAKE_60/12_512 | SHAKE256 | 64 | 16 | 131 | 60 | 12 | +------------------------+-----------+----+----+-----+----+----+ Table 4 XDR formats for XMSS^MT are listed in Appendix C.5.4.1. Parameter Guide
In addition to the tree height parameter already used for XMSS, XMSS^MT has the parameter d that determines the number of tree layers. XMSS can be understood as XMSS^MT with a single layer, i.e., d=1. Hence, the choice of h has the same effect as for XMSS. The number of tree layers provides a trade-off between signature size on the one side and key generation and signing speed on the other side. Increasing the number of layers reduces key generation time exponentially and signing time linearly at the cost of increasing the signature size linearly. Essentially, an XMSS^MT signature contains one WOTSP signature per layer. Speed roughly corresponds to d-times the speed for XMSS with trees of height h/d. To demonstrate the impact of different values of h and d, the following table shows signature size and runtimes. Runtimes are given as the number of calls to F and H when the BDS algorithm and distributed signature generation are used. Timings are worst-case times. The last column shows the number of messages that can be signed with one key pair. The numbers are the same for the XMSS-
SHAKE instances with same parameters h and n. Due to formatting limitations, only the parameter part of the parameter set names are given, omitting the name "XMSSMT". +----------------+---------+------------+--------+--------+-------+ | Name | |Sig| | KeyGen | Sign | Verify | #Sigs | +----------------+---------+------------+--------+--------+-------+ | REQUIRED: | | | | | | | | | | | | | | SHA2_20/2_256 | 4,963 | 2,476,032 | 7,227 | 2,298 | 2^20 | | | | | | | | | SHA2_20/4_256 | 9,251 | 154,752 | 4,170 | 4,576 | 2^20 | | | | | | | | | SHA2_40/2_256 | 5,605 | 2,535*10^6 | 13,417 | 2,318 | 2^40 | | | | | | | | | SHA2_40/4_256 | 9,893 | 4,952,064 | 7,227 | 4,596 | 2^40 | | | | | | | | | SHA2_40/8_256 | 18,469 | 309,504 | 4,170 | 9,152 | 2^40 | | | | | | | | | SHA2_60/3_256 | 8,392 | 3,803*10^6 | 13,417 | 3,477 | 2^60 | | | | | | | | | SHA2_60/6_256 | 14,824 | 7,428,096 | 7,227 | 6,894 | 2^60 | | | | | | | | | SHA2_60/12_256 | 27,688 | 464,256 | 4,170 | 13,728 | 2^60 | | | | | | | | | OPTIONAL: | | | | | | | | | | | | | | SHA2_20/2_512 | 18,115 | 4,835,328 | 14,075 | 4,474 | 2^20 | | | | | | | | | SHA2_20/4_512 | 34,883 | 302,208 | 8,138 | 8,928 | 2^20 | | | | | | | | | SHA2_40/2_512 | 19,397 | 4,951*10^6 | 26,025 | 4,494 | 2^40 | | | | | | | | | SHA2_40/4_512 | 36,165 | 9,670,656 | 14,075 | 8,948 | 2^40 | | | | | | | | | SHA2_40/8_512 | 69,701 | 604,416 | 8,138 | 17,856 | 2^40 | | | | | | | | | SHA2_60/3_512 | 29,064 | 7,427*10^6 | 26,025 | 6,741 | 2^60 | | | | | | | | | SHA2_60/6_512 | 54,216 | 14,505,984 | 14,075 | 13,422 | 2^60 | | | | | | | | | SHA2_60/12_512 | 104,520 | 906,624 | 8,138 | 26,784 | 2^60 | +----------------+---------+------------+--------+--------+-------+ Table 5
As a default, users without special requirements should use option XMSSMT-SHA2_60/3_256, which allows signing of 2^60 messages with one key pair (this is a virtually unbounded number of signatures). At the same time, signature size and speed are well balanced.6. Rationale
The goal of this note is to describe the WOTS+, XMSS, and XMSS^MT algorithms based on the scientific literature. The description is done in a modular way that allows basing a description of stateless hash-based signature algorithms like SPHINCS [BHH15] on it. This note slightly deviates from the scientific literature by using a tweak that prevents multi-user and multi-target attacks against H_msg. To this end, the public key as well as the index of the used one-time key pair become part of the hash function key. Thereby, we achieve a domain separation that forces an attacker to decide which hash value to attack. For the generation of the randomness used for randomized message hashing, we apply a PRF, keyed with a secret value, to the index of the used one-time key pair instead of the message. The reason is that this requires processing the message only once instead of twice. For long messages, this improves speed and simplifies implementations on resource-constrained devices that cannot hold the entire message in storage. We give one mandatory set of parameters using SHA2-256. The reasons are twofold. On the one hand, SHA2-256 is part of most cryptographic libraries. On the other hand, a 256-bit hash function leads to parameters that provide 128 bits of security even against quantum- computer-aided attacks. A post-quantum security level of 256 bits seems overly conservative. However, to prepare for possible cryptanalytic breakthroughs, we also provide OPTIONAL parameter sets using the less widely supported SHA2-512, SHAKE-256, and SHAKE-512 functions. We suggest the value w = 16 for the Winternitz parameter. No bigger values are included since the decrease in signature size then becomes less significant. Furthermore, the value w = 16 considerably simplifies the implementations of some of the algorithms. Please note that we do allow w = 4 but limit the specified parameter sets to w = 16 for efficiency reasons.
The signature and public key formats are designed so that they are easy to parse. Each format starts with a 32-bit enumeration value that indicates all of the details of the signature algorithm and hence defines all of the information that is needed in order to parse the format.7. Reference Code
For testing purposes, a reference implementation in C is available. The code contains a basic implementation that closely follows the pseudocode in this document and an optimized implementation that uses the BDS algorithm [BDS08] to compute authentication paths and distributed signature generation as described in [HRB13] for XMSS^MT. The code is permanently available at <https://github.com/joostrijneveld/xmss-reference>.8. IANA Considerations
The Internet Assigned Numbers Authority (IANA) has created three registries: one for WOTS+ signatures (as defined in Section 3), one for XMSS signatures (as defined in Section 4), and one for XMSS^MT signatures (as defined in Section 4). For the sake of clarity and convenience, the first collection of WOTS+, XMSS, and XMSS^MT parameter sets is defined in Section 5. Additions to these registries require that a specification be documented in an RFC or another permanent and readily available reference in sufficient detail as defined by the "Specification Required" policy described in [RFC8126] to make interoperability between independent implementations possible. Each entry in these registries contains the following elements: o a short name, such as "XMSS_SHA2_20_256", o a positive number, and o a reference to a specification that completely defines the signature method test cases or provides a reference implementation that can be used to verify the correctness of an implementation (or a reference to such an implementation). Requests to add an entry to these registries MUST include the name and the reference. The number is assigned by IANA. These number assignments SHOULD use the smallest available positive number. Submitters MUST have their requests reviewed and approved. Designated Experts for this task as requested by the "Specification Required" policy defined by [RFC8126] will be assigned by the
Internet Engineering Steering Group (IESG). The IESG can be contacted at iesg@ietf.org. Interested applicants that are unfamiliar with IANA processes should visit <http://www.iana.org>. The number 0x00000000 (decimal 0) is Reserved. The numbers between 0xDDDDDDDD (decimal 3,722,304,989) and 0xFFFFFFFF (decimal 4,294,967,295) inclusive will not be assigned by IANA and are Reserved for Private Use; no attempt will be made to prevent multiple sites from using the same value in different (and incompatible) ways [RFC8126]. The "WOTS+ Signatures" registry is as follows. +--------------------+-----------------+-------------+ | Numeric Identifier | Name | Reference | +--------------------+-----------------+-------------+ | 0x00000000 | Reserved | this RFC | | | | | | 0x00000001 | WOTSP-SHA2_256 | Section 5.2 | | | | | | 0x00000002 | WOTSP-SHA2_512 | Section 5.2 | | | | | | 0x00000003 | WOTSP-SHAKE_256 | Section 5.2 | | | | | | 0x00000004 | WOTSP-SHAKE_512 | Section 5.2 | +--------------------+-----------------+-------------+ Table 6
The "XMSS Signatures" registry is as follows. +--------------------+-------------------+-------------+ | Numeric Identifier | Name | Reference | +--------------------+-------------------+-------------+ | 0x00000000 | Reserved | this RFC | | | | | | 0x00000001 | XMSS-SHA2_10_256 | Section 5.3 | | | | | | 0x00000002 | XMSS-SHA2_16_256 | Section 5.3 | | | | | | 0x00000003 | XMSS-SHA2_20_256 | Section 5.3 | | | | | | 0x00000004 | XMSS-SHA2_10_512 | Section 5.3 | | | | | | 0x00000005 | XMSS-SHA2_16_512 | Section 5.3 | | | | | | 0x00000006 | XMSS-SHA2_20_512 | Section 5.3 | | | | | | 0x00000007 | XMSS-SHAKE_10_256 | Section 5.3 | | | | | | 0x00000008 | XMSS-SHAKE_16_256 | Section 5.3 | | | | | | 0x00000009 | XMSS-SHAKE_20_256 | Section 5.3 | | | | | | 0x0000000A | XMSS-SHAKE_10_512 | Section 5.3 | | | | | | 0x0000000B | XMSS-SHAKE_16_512 | Section 5.3 | | | | | | 0x0000000C | XMSS-SHAKE_20_512 | Section 5.3 | +--------------------+-------------------+-------------+ Table 7
The "XMSS^MT Signatures" registry is as follows.
+--------------------+------------------------+-------------+
| Numeric Identifier | Name | Reference |
+--------------------+------------------------+-------------+
| 0x00000000 | Reserved | this RFC |
| | | |
| 0x00000001 | XMSSMT-SHA2_20/2_256 | Section 5.4 |
| | | |
| 0x00000002 | XMSSMT-SHA2_20/4_256 | Section 5.4 |
| | | |
| 0x00000003 | XMSSMT-SHA2_40/2_256 | Section 5.4 |
| | | |
| 0x00000004 | XMSSMT-SHA2_40/4_256 | Section 5.4 |
| | | |
| 0x00000005 | XMSSMT-SHA2_40/8_256 | Section 5.4 |
| | | |
| 0x00000006 | XMSSMT-SHA2_60/3_256 | Section 5.4 |
| | | |
| 0x00000007 | XMSSMT-SHA2_60/6_256 | Section 5.4 |
| | | |
| 0x00000008 | XMSSMT-SHA2_60/12_256 | Section 5.4 |
| | | |
| 0x00000009 | XMSSMT-SHA2_20/2_512 | Section 5.4 |
| | | |
| 0x0000000A | XMSSMT-SHA2_20/4_512 | Section 5.4 |
| | | |
| 0x0000000B | XMSSMT-SHA2_40/2_512 | Section 5.4 |
| | | |
| 0x0000000C | XMSSMT-SHA2_40/4_512 | Section 5.4 |
| | | |
| 0x0000000D | XMSSMT-SHA2_40/8_512 | Section 5.4 |
| | | |
| 0x0000000E | XMSSMT-SHA2_60/3_512 | Section 5.4 |
| | | |
| 0x0000000F | XMSSMT-SHA2_60/6_512 | Section 5.4 |
| | | |
| 0x00000010 | XMSSMT-SHA2_60/12_512 | Section 5.4 |
| | | |
| 0x00000011 | XMSSMT-SHAKE_20/2_256 | Section 5.4 |
| | | |
| 0x00000012 | XMSSMT-SHAKE_20/4_256 | Section 5.4 |
| | | |
| 0x00000013 | XMSSMT-SHAKE_40/2_256 | Section 5.4 |
| | | |
| 0x00000014 | XMSSMT-SHAKE_40/4_256 | Section 5.4 |
| | | |
| 0x00000015 | XMSSMT-SHAKE_40/8_256 | Section 5.4 |
| | | | | 0x00000016 | XMSSMT-SHAKE_60/3_256 | Section 5.4 | | | | | | 0x00000017 | XMSSMT-SHAKE_60/6_256 | Section 5.4 | | | | | | 0x00000018 | XMSSMT-SHAKE_60/12_256 | Section 5.4 | | | | | | 0x00000019 | XMSSMT-SHAKE_20/2_512 | Section 5.4 | | | | | | 0x0000001A | XMSSMT-SHAKE_20/4_512 | Section 5.4 | | | | | | 0x0000001B | XMSSMT-SHAKE_40/2_512 | Section 5.4 | | | | | | 0x0000001C | XMSSMT-SHAKE_40/4_512 | Section 5.4 | | | | | | 0x0000001D | XMSSMT-SHAKE_40/8_512 | Section 5.4 | | | | | | 0x0000001E | XMSSMT-SHAKE_60/3_512 | Section 5.4 | | | | | | 0x0000001F | XMSSMT-SHAKE_60/6_512 | Section 5.4 | | | | | | 0x00000020 | XMSSMT-SHAKE_60/12_512 | Section 5.4 | +--------------------+------------------------+-------------+ Table 8 An IANA registration of a signature system does not constitute an endorsement of that system or its security.9. Security Considerations
A signature system is considered secure if it prevents an attacker from forging a valid signature. More specifically, consider a setting in which an attacker gets a public key and can learn signatures on arbitrary messages of its choice. A signature system is secure if, even in this setting, the attacker cannot produce a new message/signature pair of his choosing such that the verification algorithm accepts. Preventing an attacker from mounting an attack means that the attack is computationally too expensive to be carried out. There are various estimates for when a computation is too expensive to be done. For that reason, this note only describes how expensive it is for an attacker to generate a forgery. Parameters are accompanied by a bit security value. The meaning of bit security is as follows. A parameter set grants b bits of security if the best attack takes at least 2^(b - 1) bit operations to achieve a success probability of
1/2. Hence, to mount a successful attack, an attacker needs to perform 2^b bit operations on average. The given values for bit security were estimated according to [HRS16].9.1. Security Proofs
A full security proof for all schemes described in this document can be found in [HRS16]. This proof shows that an attacker has to break at least one out of certain security properties of the used hash functions and PRFs to forge a signature in any of the described schemes. The proof in [HRS16] considers an initial message compression different from the randomized hashing used here. We comment on this below. For the original schemes, these proofs show that an attacker has to break certain minimal security properties. In particular, it is not sufficient to break the collision resistance of the hash functions to generate a forgery. More specifically, the requirements on the used functions are that F and H are post-quantum multi-function multi-target second-preimage resistant keyed functions, F fulfills an additional statistical requirement that roughly says that most images have at least two preimages, PRF is a post-quantum pseudorandom function, and H_msg is a post-quantum multi-target extended target collision-resistant keyed hash function. For detailed definitions of these properties see [HRS16]. To give some intuition: multi-function multi-target second- preimage resistance is an extension of second-preimage resistance to keyed hash functions, covering the case where an adversary succeeds if it finds a second preimage for one out of many values. The same holds for multi-target extended target collision resistance, which just lacks the multi-function identifier as target collision resistance already considers keyed hash functions. The proof in [HRS16] splits PRF into two functions. When PRF is used for pseudorandom key generation or generation of randomness for randomized message hashing, it is still considered a pseudorandom function. Whenever PRF is used to generate bitmasks and hash function keys, it is modeled as a random oracle. This is due to technical reasons in the proof, and an implementation using a pseudorandom function is secure. The proof in [HRS16] considers classical randomized hashing for the initial message compression, i.e., H(r, M) instead of H(r || getRoot(PK) || index, M). This classical randomized hashing allows getting a security reduction from extended target collision resistance [HRS16], a property that is conjectured to be strictly weaker than collision resistance. However, it turns out that in this case, an attacker could still launch a multi-target attack even against multiple users at the same time. The reason is that the adversary attacking u users at the same time learns u * 2^h
randomized hashes H(r_i_j || M_i_j) with signature index i in [0, 2^h - 1] and user index j in [0, u]. It suffices to find a single pair (r*, M*) such that H(r* || M*) = H(r_i_u || M_i_u) for one out of the u * 2^h learned hashes. Hence, an attacker can do a brute-force search in time 2^n / u * 2^h instead of 2^n. The indexed randomized hashing H(r || getRoot(PK) || toByte(idx, n), M) used in this work makes the hash function calls position- and user-dependent. This thwarts the above attack because each hash function evaluation during an attack can only target one of the learned randomized hash values. More specifically, an attacker now has to decide which index idx and which root value to use for each query. If one assumes that the used hash function is a random function, it can be shown that a multi-user existential forgery attack that targets this message compression has a complexity of 2^n hash function calls. The given bit security values were estimated based on the complexity of the best-known generic attacks against the required security properties of the used hash and pseudorandom functions, assuming conventional and quantum adversaries. At the time of writing, generic attacks are the best-known attacks for the parameters suggested in the classical setting. Also, in the quantum setting, there are no dedicated attacks known that perform better than generic attacks. Nevertheless, the topic of quantum cryptanalysis of hash functions is not as well understood as in the classical setting.9.2. Minimal Security Assumptions
The assumptions one has to make to prove security of the described schemes are minimal in the following sense. Any signature algorithm that allows arbitrary size messages relies on the security of a cryptographic hash function, either on collision resistance or on extended target collision resistance if randomized hashing is used for message compression. For the schemes described here, this is already sufficient to be secure. In contrast, common signature schemes like RSA, DSA, and Elliptic Curve Digital Signature Algorithm (ECDSA) additionally rely on the conjectured hardness of certain mathematical problems.9.3. Post-Quantum Security
A post-quantum cryptosystem is a system that is secure against attackers with access to a reasonably sized quantum computer. At the time of writing this note, whether or not it is feasible to build such a machine is an open conjecture. However, significant progress was made over the last few years in this regard. Hence, we consider it a matter of risk assessment to prepare for this case.
In contrast to RSA, DSA, and ECDSA, the described signature systems are post-quantum-secure if they are used with an appropriate cryptographic hash function. In particular, for post-quantum security, the size of n must be twice the size required for classical security. This is in order to protect against quantum square-root attacks due to Grover's algorithm. [HRS16] shows that variants of Grover's algorithm are the optimal generic attacks against the security properties of hash functions required for the described schemes. As stated above, we only consider generic attacks here, as cryptographic hash functions should be deprecated as soon as dedicated attacks that perform significantly better exist. This also applies to the quantum setting. As soon as dedicated quantum attacks against the used hash function that can perform significantly better than the described generic attacks exist, these hash functions should not be used anymore for the described schemes, or the computation of the security level has to be redone.10. References
10.1. Normative References
[FIPS180] National Institute of Standards and Technology, "Secure Hash Standard (SHS)", FIPS PUB 180-4, DOI 10.6028/NIST.FIPS.180-4, August 2015. [FIPS202] National Institute of Standards and Technology, "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions", FIPS PUB 202, DOI 10.6028/NIST.FIPS.202, August 2015. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/info/rfc2119>. [RFC4506] Eisler, M., Ed., "XDR: External Data Representation Standard", STD 67, RFC 4506, DOI 10.17487/RFC4506, May 2006, <https://www.rfc-editor.org/info/rfc4506>. [RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 8126, DOI 10.17487/RFC8126, June 2017, <https://www.rfc-editor.org/info/rfc8126>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, <https://www.rfc-editor.org/info/rfc8174>.10.2. Informative References
[BDH11] Buchmann, J., Dahmen, E., and A. Huelsing, "XMSS - A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions", Lecture Notes in Computer Science, Volume 7071, Post-Quantum Cryptography, DOI 10.1007/978-3-642-25405-5_8, 2011. [BDS08] Buchmann, J., Dahmen, E., and M. Schneider, "Merkle Tree Traversal Revisited", Lecture Notes in Computer Science, Volume 5299, Post-Quantum Cryptography, DOI 10.1007/978-3-540-88403-3_5, 2008. [BDS09] Buchmann, J., Dahmen, E., and M. Szydlo, "Hash-based Digital Signature Schemes", Book chapter, Post-Quantum Cryptography, DOI 10.1007/978-3-540-88702-7_3, 2009. [BHH15] Bernstein, D., Hopwood, D., Huelsing, A., Lange, T., Niederhagen, R., Papachristodoulou, L., Schneider, M., Schwabe, P., and Z. Wilcox-O'Hearn, "SPHINCS: Practical Stateless Hash-Based Signatures", Lecture Notes in Computer Science, Volume 9056, Advances in Cryptology - EUROCRYPT, DOI 10.1007/978-3-662-46800-5_15, 2015. [HRB13] Huelsing, A., Rausch, L., and J. Buchmann, "Optimal Parameters for XMSS^MT", Lecture Notes in Computer Science, Volume 8128, CD-ARES, DOI 10.1007/978-3-642-40588-4_14, 2013. [HRS16] Huelsing, A., Rijneveld, J., and F. Song, "Mitigating Multi-Target Attacks in Hash-based Signatures", Lecture Notes in Computer Science, Volume 9614, Public-Key Cryptography - PKC, DOI 10.1007/978-3-662-49384-7_15, 2016. [Huelsing13] Huelsing, A., "W-OTS+ - Shorter Signatures for Hash-Based Signature Schemes", Lecture Notes in Computer Science, Volume 7918, Progress in Cryptology - AFRICACRYPT, DOI 10.1007/978-3-642-38553-7_10, 2013.
[Huelsing13a] Huelsing, A., "Practical Forward Secure Signatures using Minimal Security Assumptions", PhD thesis TU Darmstadt, 2013, <http://tuprints.ulb.tu-darmstadt.de/3651/1/Thesis.pdf>. [KMN14] Knecht, M., Meier, W., and C. Nicola, "A space- and time- efficient Implementation of the Merkle Tree Traversal Algorithm", Computing Research Repository (CoRR), arXiv:1409.4081, 2014. [MCF18] McGrew, D., Curcio, M., and S. Fluhrer, "Hash-Based Signatures", Work in Progress, draft-mcgrew-hash-sigs-11, April 2018. [Merkle83] Merkle, R., "Secrecy, Authentication, and Public Key Systems", Computer Science Series, UMI Research Press, ISBN: 9780835713849, 1983.
(next page on part 4)
