| Internet-Draft | Merkle Tree Ladder (MTL) Mode Signatures | June 2024 |
| Harvey, et al. | Expires 14 December 2024 | [Page] |
This document provides an interoperable specification for Merkle tree ladder (MTL) mode, a technique for using an underlying signature scheme to authenticate an evolving series of messages. MTL mode can reduce the signature scheme's operational impact. Rather than signing messages individually, the MTL mode of operation signs structures called "Merkle tree ladders" that are derived from the messages to be authenticated. Individual messages are then authenticated relative to the ladder using a Merkle tree authentication path and the ladder is authenticated using the public key of the underlying signature scheme. The size and computational cost of the underlying signatures are thereby amortized across multiple messages, reducing the scheme's operational impact. The reduction can be particularly beneficial when MTL mode is applied to a post-quantum signature scheme that has a large signature size or computational cost. As an example, the document shows how to use MTL mode with SPHINCS+ (and the SLH-DSA subset specified in the draft FIPS 205), the stateless hash-based signature scheme selected by NIST for standardization. Like other Merkle tree techniques, MTL mode's security is based only on cryptographic hash functions, so the mode is quantum-safe based on the quantum-resistance of its cryptographic hash functions.¶
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶
Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."¶
This Internet-Draft will expire on 14 December 2024.¶
Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved.¶
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License.¶
This document provides an interoperable specification for Merkle tree ladder (MTL) mode [MTL-MODE], a technique for using a signature scheme to authenticate an evolving series of messages that potentially can reduce the operational impact of the signature scheme.¶
MTL mode is a different way of using an underlying signature scheme. Instead of signing individual messages directly, MTL mode signs structures called "Merkle tree ladders" that are derived from the messages to be authenticated. Individual messages are then authenticated relative to the ladder using a Merkle tree authentication path (also called a Merkle proof). The operational impact of the signatures on the ladders is thus amortized across multiple messages. The remaining per-message cost consists of the overhead of computing and using the ladders and authentication paths.¶
The operational benefits of MTL mode are most evident in scenarios where verifiers are interested in a subset of messages among a large, evolving series of messages. Examples include authenticating web Public-Key Infrastructure certificates [RFC5280], Domain Name System Security Extensions (DNSSEC) records [RFC4033] and signed certificate timestamps [RFC9162]. MTL mode is not well suited to scenarios where a verifier is interested in authenticating a single, newly generated message. An example is a Transport Layer Security transcript hash [RFC8446]. In such scenarios, a ladder would need to be signed and verified for every message processed, so the operational impact would not be reduced.¶
The mode is intended primarily for use with post-quantum signature schemes where the reduction of operational impact can be significant given their relatively large signature sizes. As an initial example, this document shows how to use MTL mode with SPHINCS+, a stateless hash-based post-quantum signature scheme selected by NIST for standardization [SPHINCS-PLUS] (and the SLH-DSA subset specified in the draft [FIPS205-IPD]). The design decision is motivated by three considerations: (1) SPHINCS+ also is based on Merkle trees, and thus already has internal functions for computing leaf nodes and internal nodes; (2) SPHINCS+ has a relatively large signature size and computational cost, and therefore can benefit significantly from the reductions offered by MTL mode; and (3) hash-based techniques are well understood and offer a conservative choice for long-term security, alongside newer techniques from other families such as lattice-based cryptography. Future updates to this document may support other signature schemes.¶
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶
Standard order of operations is assumed throughout this document.¶
The following mathematical operators are used:¶
The following bitwise operators are used:¶
The following comparison operators are used:¶
The following array notation is used:¶
The following byte string notation is used:¶
Given an unsigned integer x or a message byte string a, the following functions are defined:¶
lsb(x) returns the position of the least significant bit of x, where bit positions start at 1 and lsb(0) = 0.¶
msb(x) returns the position of the most significant bit of x.¶
bit_width (x) returns the number of 1 value bits in x. This corresponds to the popcnt instruction on Intel/AMD processors and the __builtin_popcount function in gcc.¶
octet(x) returns a single byte with value x (assuming 0 <= x <= 255).¶
OLEN(a) returns the length in bytes of a.¶
Example Function Outputs: +---------+----------------+-------+-------+-------------+ | x | representation | lsb | msb | bit_width | +---------+----------------+-------+-------+-------------+ | 0 | 00000000 + 0 | 0 | 0 | | 1 | 00000001 + 1 | 1 | 1 | | 2 | 00000010 + 2 | 2 | 1 | | 3 | 00000011 + 1 | 2 | 2 | | 4 | 00000100 + 3 | 3 | 1 | | 5 | 00000101 + 1 | 3 | 2 | | 6 | 00000110 + 2 | 3 | 2 | | 7 | 00000111 + 1 | 3 | 3 | +---------+----------------+-------+-------+-------------+¶
The data structures and algorithms defined in this document are written to be runnable Python 3 code. The following styles have been applied to further make the code easy to read and follow:¶
The general model for MTL mode involves the following exchanges between a signer and a verifier. The signer is assumed to have a private key for an underlying signature scheme and the verifier is assumed to have the corresponding public key.¶
The model can reduce the operational impact of the underlying signature scheme in two main ways. First, per Steps 2 and 3, the signer signs ladders only as needed, not necessarily every time a message is added to a message series. The signer thus potentially makes many fewer calls to the underlying signature generation operation and stores fewer signatures than if the messages were signed individually. Second, per Steps 6, 7 and 8, the verifier obtains and verifies signatures on ladders only as needed, not necessarily every time a message is authenticated. The signer thus potentially sends fewer signatures, and the verifier stores and verifies fewer signatures, than if the messages were signed individually.¶
MTL mode signatures are dependent on an underlying signature scheme, requiring proper domain separation and alignment of the security parameters and functions.¶
MTL mode, like pre-hashing, requires domain separation from the underlying signature scheme. Methods for MTL mode domain separation are defined in Section 4.1, following a scheme that is similar to what is specified by NIST in FIPS 204 and FIPS 205.¶
Because SPHINCS+ is the initial recommended underlying signature scheme for MTL mode, this document specifies MTL mode using the SPHINCS+ security parameter and abstract cryptographic functions that are substantially the same as the ones in [SPHINCS-PLUS]. This includes the subset of instantiations that are defined for SLH-DSA in draft [FIPS205-IPD]. The document also uses an extended version of the [SPHINCS-PLUS] address scheme with additional address types. One goal of this approach is to make it easier for developers who already have a SPHINCS+ implementation to build MTL mode operations. Another goal is to makes it easier to ensure that MTL mode operations are cryptographically separated from SPHINCS+'s internal operations.¶
The cryptographic parameter is defined in Section 4.2. Domain separation and pre-hashing as they relate to MTL mode are discussed in Section 4.1. The cryptographic functions are defined in Section 4.3, Section 4.4 and Section 4.5. The address scheme is defined in Section 4.6. Finally, cryptographic separation and message index association are discussed in Section 4.7.¶
In an implementation, the parameter needs to be instantiated with an actual value and the abstract functions need to be instantiated with actual functions. Recommended instantiations when the underlying signature scheme is SPHINCS+ are given in Section 10. Recommended instantiations for other underlying signature schemes may be added in updates to this document.¶
In the following, notation || indicates concatenation of byte strings for consistency with SPHINCS+, in contrast to the + notation used for byte string concatenation elsewhere in the document.¶
[FIPS204-IPD] and [FIPS205-IPD] both propose two ways to use their underlying signature schemes: "pure," where a message is input directly to the underlying signature scheme, and "pre-hash," where a hash of the message is the input. Both also take an optional application-specified context string as input. MTL mode can be modeled as a third "mode of operation," where a ladder derived from one or more messages is the input. Expanding on the April 19, 2024 pre-hashing proposal by NIST [NIST-PREHASH-UPDATE], the input to the underlying signature scheme in this version of the document is formatted as follows:¶
octet(MTL_LADDER_SEP) || octet(OLEN(ctx)) || ctx || OID_MTL || ladder¶
where:¶
The format above separates MTL mode inputs from pure inputs to the underlying signature scheme (which would have a first byte of 0) and from other pre-hash inputs (which would have a first byte of 1). The concatenation of the first four strings in the format (i.e., the strings preceding the ladder) is referred to as the "MTL ladder domain separator."¶
For domain separation between calls made by MTL mode operations and those made by the underlying signature scheme (in the case of SPHINCS+; see Section 4.7), the inputs to H_msg_mtl and PRF_msg in calls made by MTL mode operations are formatted as follows:¶
octet(MTL_MSG_SEP) || octet(OLEN(ctx)) || ctx || value¶
where:¶
The concatenation of the first three strings in the format (i.e., the strings preceding the value) is referred to as the "MTL message domain separator."¶
FOR DISCUSSION: Expanding on the pure and pre-hash domain separator formats is intended to make it easier for implementations of FIPS 204 and FIPS 205 to be extended to support MTL mode in a way that separates MTL mode from the pure and pre-hash modes. However, the approach introduces a new first byte value and new OIDs that implementations might not initially recognize. An alternative is to reuse the proposed pre-hash domain separator format and consider MTL mode itself as a more complex form of pre-hashing. Instead of a new byte, the alternative only introduces new OIDs. However, implementations might only expect OIDs that are associated with NIST-approved hash functions, not MTL mode. Pre-hashing remains an active discussion topic on the NIST PQC mailing list as of this writing, and further updates may be made to this document as is appropriate.¶
MTL mode has one security parameter, the size in bytes of hash values, denoted n. The security parameter SHOULD be at least 16. Typical values of n are 16, 24 and 32 (see Section 10). The security parameter affects the difficulty of breaking MTL mode (see Section 14).¶
MTL mode makes use of a variant of the randomized message digest function (i.e., keyed hash function) H_msg defined in SPHINCS+:¶
H_msg_mtl differs from SPHINCS+'s H_msg in that its output hash value is n bytes long rather than m bytes long (where m is a separate parameter in SPHINCS+). The inputs to H_msg_mtl have the following meanings:¶
H_msg_mtl is used for computing data values from messages in MTL mode (see Section 5.1 and Section 5.2). (Note that when H_msg_mtl is called in these sections, M is the message being signed prepended with a MTL message domain separator - see Section 4.7 for discussion.)¶
MTL mode also makes use of pseudorandom function PRF_msg defined in SPHINCS+:¶
The inputs to PRF_msg have the following meanings:¶
PRF_msg is used for computing randomizers for hashing messages in MTL mode (see Section 5.1 and Section 5.2). (Note that when PRF_msg is called in these sections, M is an ADRS value prepended with a domain separator, optionally followed by the message being signed - see Section 4.7 for discussion.)¶
MTL mode makes use of the tweakable hash functions F and H defined in SPHINCS+:¶
The inputs to F and H have the following meanings:¶
F is used for computing a leaf node from a data value in MTL mode (see Section 8.2.1). H is used for computing an internal node hash value from two child node hash values (see Section 8.2.2).¶
MTL mode extends the address scheme for function inputs defined in SPHINCS+, adding four address types.¶
As in SPHINCS+, the address is an eight-word (32-byte) value. The fifth word (byte positions 17-20) is the address type.¶
This document assigns identifiers 16-18 for new address types. The assignment provides easy visual separation in hexadecimal from the identifiers 0-6 used by SPHINCS+. The constants MTL_MSG, MTL_DATA, and MTL_TREE provide a descriptive alternative to the numbers.¶
For all three types, the first and second words MUST be 0 and the third and fourth words MUST be the series identifier SID associated with the MTL mode operation, padded on the left. The sixth, seventh and eighth words depend on the address type. Index values are represented as 4-byte unsigned integers in big endian notation.¶
| Byte Positions | +----------------------+---+---+-----+-----+-----+-----+-----+ | Address Type |1-4|5-8| 9-16|17-20|21-24|25-28|29-32| +----------------------+---+---+-----+-----+-----+-----+-----+ | MTL Message Hash | 0 | 0 | SID | 16 | 0 | 0 |MsgID| +----------------------+---+---+-----+-----+-----+-----+-----+ | MTL Data Value | 0 | 0 | SID | 17 | 0 | 0 |MsgID| +----------------------+---+---+-----+-----+-----+-----+-----+ | MTL Tree | 0 | 0 | SID | 18 | 0 | Left|Right| +----------------------+---+---+-----+-----+-----+-----+-----+¶
Address values are represented with the ADRS class.¶
The security proof for MTL mode in [MTL-MODE] assumes that calls to the function for computing data values from messages, i.e., to H_msg_mtl here, are cryptographically separated from calls made by SPHINCS+'s internal operations. In addition, the security proof assumes that calls to this function also include the message index as input.¶
For the tweakable hash functions in SPHINCS+, cryptographic separation and message index association are achieved by taking an address value as input. However, H_msg in SPHINCS+ doesn't take an address value as input, and for consistency, neither does H_msg_mtl.¶
This document takes the following approach to achieve cryptographic separation and message index association for calls to H_msg and H_msg_mtl:¶
This document takes a comparable approach to achieve cryptographic separation and message index association for calls to PRF_msg. (Note that calls to PRF_msg from the MTL mode operations only take the domain separator and the address value in the input, not the message.)¶
Assuming that the underlying signature scheme passes the message to be signed directly to H_msg, as SPHINCS+ does, the calls to H_msg_mtl from the MTL mode operations and to H_msg from SPHINCS+ will involve values of M whose first bytes differ, providing cryptographic separation between calls by the MTL mode operations and by SPHINCS+. A comparable observation applies to calls to PRF_msg.¶
In MTL mode, variable-length messages are converted to fixed-length data values that can be processed by the MTL node set operations in the next section.¶
The conversion process involves a randomized message digest operation. The signer computes the randomizer and sends it to the verifier along with other information needed to authenticate the message.¶
The computation of the randomizer varies depending on whether the signer selects deterministic hashing or randomized hashing. (The choice follows a similar approach to SPHINCS+.)¶
A MTL mode signer starts with a message M, a context string ctx, a series identifier SID, and a message index MsgID and computes a randomizer R_mtl and a data value with the following steps.¶
sep = octet(MTL_MSG_SEP) || octet(OLEN(ctx)) || ctx¶
Generate a randomizer R_mtl using a secure random generator [RFC4086]. An implementation MAY use the following steps:¶
R_mtl = PRF_msg(SK.prf, OptRand, sep || ADRS)¶
An implementation MAY either use the same or a different SK.prf value as is used in the underlying signature scheme. In either case, the SK.prf value MUST have been generated using a secure random generator and MUST be kept secret, e.g., as part of the private key. Using the same SK.prf value avoids the need to generate and manage an additional secret. However, using a different SK.prf value can be advantageous if the underlying signature scheme is implemented in a security module and the MTL mode operations are implemented outside the security module and do not have access to the underlying signature schemes SK.prf value.¶
An implementation MAY additionally include the message M in the input to the PRF_msg call by appending it to ADRS, i.e., by passing sep || ADRS || M as the third argument. However, this approach involves an additional pass over the message, which can be disadvantageous if the message is long.¶
data_value = H_msg_mtl(R_mtl, PK.seed, PK.root, sep || ADRS || M)¶
A MTL mode verifier starts with a message M, a randomizer R_mtl, a context string ctx, a series identifier SID and a message index MsgID and recomputes the data value with the following steps.¶
sep = octet(MTL_MSG_SEP) || octet(OLEN(ctx)) || ctx¶
data_value = H_msg_mtl(R_mtl, PK.seed, PK.root, sep || ADRS || M)¶
The core functionality that enables MTL mode is a set of hash-based nodes organized in an expanding tree-like structure. This allows for appending data values to an expanding data series, computing ladders and computing authentication paths from data values to ladder rungs. MTL node set operations provide the building blocks for authenticating messages when a signature scheme is operated in in MTL mode.¶
A MTL node set authenticates a series of data values. Each data value in the series has a unique index, a non-negative integer. In the MTL mode operations in this document, the index starts at 0 and is incremented by 1 after each new data value is appended. A data value is computed from a message to be authenticated via a randomized message digest operation, as described in the previous section.¶
Three data structures supporting MTL node sets are given in Section 7 and six MTL node set operations are given in Section 8. This section provides a general overview of the concepts behind those techniques.¶
The hash operations in the MTL node set operations take a public seed and a series identifier input. The public seed separates the use of the hash operations with different public keys (assuming different public keys have different public seeds). The series identifier separates the use of the hash operations for different series for data values with the same public key.¶
Both the public seed and the series identifier are n-byte values where n is the security parameter.¶
A MTL node set has zero or more nodes each of the form <L,R,V> where:¶
The pair (L,R) is the node's index pair. A node set MUST NOT have more than one node with a given index pair.¶
The node with index pair (L,R) authenticates the data values with indexes between L and R inclusive. If L = R, the node is a leaf node (Section 6.3). If L < R, then it is an internal node (Section 6.4).¶
A leaf node is a node where L = R. It has no child nodes. Its hash value is computed as¶
V = hash_leaf(seed, sid, L, data_value)¶
where hash_leaf is a hash function defined in Section 8.2.1, seed and sid are the public seed and series identifier and data_value is the data value associated with this leaf index.¶
Including the leaf index as an input to hash_leaf separates the use of the hash function for different leaf nodes.¶
A leaf node with a given index authenticates the data value with the corresponding index. It follows that if a node set has a leaf node with a given index, then the data series MUST have a data value with the same index.¶
An internal node is a node where L < R.¶
An internal node has two child nodes, called a left child and a right child. Its hash value is computed as¶
V = hash_int(seed, sid, L, R, left_hash, right_hash)¶
where hash_int is a hash function defined in Section 8.2.2, seed and sid are the public seed and the series identifier, left_hash is the left child's hash value and right_hash is the right child's hash value.¶
Including the left and right indexes as inputs to hash_int separates the use of the hash function for different internal nodes.¶
The left and right children are the nodes with index pairs (L,M-1) and (M,R) respectively where M, the middle index, is the unique integer between L+1 and R that is divisible by the largest power of two. The child index ranges are thus a partition of the internal node's index range. The middle index can be computed as follows:¶
power = msb(R-L)
M = R - mod(R, 2^(power+1))
if(M <= L):
M = R - mod(R, 2^power)
¶
An internal node with index pair (L,R) authenticates the data values with indexes between L and R inclusive. It follows that if a node set has an internal node with an index pair (L,R), then the data series MUST have data values with indexes L through R. In addition, the node set MUST have nodes with index pairs (L,M-1) and (M,R).¶
The following table gives examples of index pairs for internal nodes and their left and right child nodes. In the table, a leaf node is denoted with a single index. For instance, the index 4 is equivalent to the index pair (4,4).¶
Internal Node | Left Child | Right Child
(L,R) | (L,M-1) | (M,R)
-----------------+--------------+---------------
(0,3) | (0,1) | (2,3)
(4,5) | 4 | 5
(0,5) | (0,3) | (4,5)
(0,31) | (0,15) | (16,31)
(0,2) | (0,1) | 2
¶
A ladder is a subset of nodes that is used to authenticate data values. Each node in the ladder is called a rung.¶
In the MTL mode operations in this document, the subset is selected according to what is called the binary rung strategy. In this strategy, the index pairs for the rungs are based on the binary representation of the number of data values in the data series.¶
The rungs in the binary rung strategy are selected as follows. Let N be the number of data values in the data series, let B be the number of 1s bits in the binary representation of N. N can then be represented as the sum of B distinct binary powers.¶
N = 2^v_1 + 2^v_2 + ... + 2v_B¶
where v_1 > v_2 > ... > v_B are the bit positions of the 1s bits in the binary representation. The first rung has index pair (0,2^v_1-1); it is the apex of a perfect binary tree of height v_1 and authenticates the first 2^v_1 data values. The next rung has index pair (2v_1,2v_1+2^v_2-1); it is the apex of a perfect binary tree of height v_2 and authenticates the next 2^v_2 data values. The process continues until the B-th rung, which has index pair (N-2^v_B,N-1) and authenticates the last 2^v_B data values.¶
A rung is said to cover the data values it authenticates, and a ladder is said to cover the data values that its rungs collectively authenticate. The ladder just described thus covers all N data values in the node set.¶
(Another way of visualizing the rungs is to consider the first rung as the apex of the largest perfect binary tree that can be formed from the data values, starting from the left; the second rung as the apex of the largest perfect binary tree than can be formed over the remaining data values; and so on. The sizes of the trees decrease from left to right.)¶
(The binary rung strategy can be contrasted with the typical "single-rung strategy" employed with Merkle trees, where a single rung of a node set is used to authenticate data values, i.e., the root node (0,N-1). When N is a power of 2, the single-rung strategy and the binary-rung strategy are the same.¶
When the N-th data value is added to the node set, v_B+1 new nodes need to be computed to update the ladder: the leaf node with index (N-1,N-1) and the v_B internal nodes leading from the leaf node to the new ladder rung (N-2^v_B,N-1). The first B-1 ladder rungs in the new ladder are the same as in the previous ladder. Because 2^v_B is at most N, the number of new nodes computed is logarithmic in N, similar to ordinary Merkle tree constructions. Moreover, every node computed in the process is the apex of a perfect binary tree.¶
The minimum number of rungs in a ladder computed with the binary rung strategy is 1, in the case that the number of leaf nodes N is a power of 2. The maximum number is the least integer greater than or equal to log2(N), or equivalently ceiling(log2(n)). The actual number is bit_width(N).¶
The following table gives examples of ladders for values of N up to 14. As in the previous table, a leaf node is designated with a single index.¶
Number of Data Values | Ladder Rungs
N |
-------------------------------------------------
1 | 0
2 | (0,1)
3 | (0,1) 2
4 | (0,3)
5 | (0,3) 4
6 | (0,3) (4,5)
7 | (0,3) (4,5) 6
8 | (0,7)
9 | (0,7) 8
10 | (0,7) (8,9)
11 | (0,7) (8,9) 10
12 | (0,7) (8,11)
13 | (0,7) (8,11) 12
14 | (0,7) (8,11) (12,13)
15 | (0,7) (8,11) (12,13) 14
16 | (0,15)
17 | (0,15) 16
18 | (0,15) (16,17)
19 | (0,15) (16,17) 18
¶
The following figure shows a node set with 14 nodes where the rungs are computed according to the binary rung strategy. The internal node hash function is denoted H and the leaf node hash function is not shown. The rungs are marked with asterisks (*).¶
(0,7)*
|
H
/------/ \------\
(0,3) (4,7) (8,11)*
| | |
H H H
/--/ \--\ /--/ \--\ /--/ \--\
(0,1) (2,3) (4,5) (6,7) (8,9) (10,11) (12,13)*
| | | | | | |
H H H H H H H
/ \ / \ / \ / \ / \ / \ / \
0 1 2 3 4 5 6 7 8 9 10 11 12 13
¶
An authentication path is the set of sibling node hash values encountered along the path from a leaf node to a target rung that covers a data value.¶
Target rungs can be any of the successive ancestors of the leaf node in the node set. Because each rung is the apex of a perfect binary tree, the sibling nodes encountered follow the structure of the binary tree.¶
For example, in the figure above, the sibling nodes encountered in the path from leaf node 6 to the rung (0,7) are the nodes with indexes 7, (4,5) and (0,3). The authentication path for the data value with index 6 includes the hash values at those nodes. This data value can be authenticated by recomputing leaf node 6 from the data value using hash_leaf, recomputing internal nodes (6,7), (4,7) and (0,7) from the sibling node hash values and previously computed hash values using hash_int, and then comparing the result to the rung hash value.¶
The minimum number of sibling nodes in an authentication path computed with the binary rung strategy is 0, in the case that the leaf node is the last leaf added and the number of leaf nodes N is odd. The maximum number is the greatest integer less than or equal to log2(N) , or equivalently floor(log2(N)). The actual number is bit_width(R-L) where (L,R) is the index pair of the rung covering the leaf node.¶
An authentication path is initially computed relative to the current ladder in the MTL mode operations in this document. The target rung for the authentication path is thus the unique rung in the ladder that covers the data value to be authenticated. When an authentication path is verified, however, it can be verified relative to any of the successive ancestors of the leaf node corresponding to the data value up to and including the target rung.¶
Continuing the example above, the authentication path for the data value at index 6 can be verified relative to any ladder that includes a rung with index 6, (6,7), (4,7) and/or (0,7). In this case, the ladder covering the first six data values could also be used, because it includes a rung with index 6.¶
More generally, if an authentication path for the data value at leaf_index is computed relative to a ladder that covers the first N data values, the authentication path can also be authenticated relative to any binary rung strategy ladder that covers the first N' data values if the following condition is met:¶
leaf_index <= N' <= N.¶
The first inequality ensures that the ladder covers the data value; the second ensures that the authentication path can reach the ladder.¶
This property of "backward compatibility" with previous ladders is attractive because it provides a way for a verifier to use an old ladder to authenticate a new authentication path, thereby potentially reducing the number of times that the verifier needs to get a new ladder.¶
To facilitate this property, the following "compatibility check" can be applied. Let (L,R) be a rung in a ladder and let leaf_index be the index of the data value. The rung can be used to authenticate the data value if the following conditions hold:¶
If a ladder has a rung that passes this check, then the ladder is compatible with the authentication path. If not, then the verifier needs to get a new ladder.¶
MTL mode operations use three well-defined data structures to represent elements described in the previous section. These structures are byte strings with number values represented in big endian notation. The data structures provide interoperability so that a verifier on one platform can read and verify the data provided by a signer on another platform.¶
A ladder data structure consists of four base components:¶
The rung data structure is described in the next section.¶
The byte representation of the ladder is the concatenation of the binary encodings of the fields using big endian representation of the integers:¶
1 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-------------------------------+
| Flags |
+-------------------------------+
| |
| Series Identifier (SID) |
| |
| |
+-------------------------------+
| Rung Count |
+-------------------------------+
| |
// Rung Data //
| |
+-------------------------------+
¶
A rung data structure consists of three base components:¶
The byte representation of the rung is the concatenation of the binary encodings of the fields using big endian representation of the integers:¶
1 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-------------------------------+
| Left Index |
| |
+-------------------------------+
| Right Index |
| |
+-------------------------------+
| |
// Rung Hash Value //
| |
+-------------------------------+
¶
An authentication path data structure consists of seven base components:¶
The byte representation of the authentication path is the concatenation of the binary encodings of the fields using a 2-byte big endian representation for the node count and 4-byte big endian representations for the indexes:¶
1 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-------------------------------+
| Flags |
+-------------------------------+
| |
| Series Identifier |
| |
| |
+-------------------------------+
| Leaf Index |
| |
+-------------------------------+
| Target Rung Left Index |
| |
+-------------------------------+
| Target Rung Right Index |
| |
+-------------------------------+
| Sibling Hash Count |
+-------------------------------+
| |
// Sibling Hash Values //
| |
+-------------------------------+
¶
This section defines six operations supporting the use of MTL node sets to authenticate messages.¶
The first four, mtl_initns, mtl_append, mtl_ladder and mtl_authpath can be used by a signer to initialize a node set, add data values to it, obtain the current ladder, and obtain an authentication path relative to the current ladder. Each uses a MTL node set object to maintain the state of the node set.¶
The other two, mtl_rung and mtl_verify, can be used by a verifier to select a ladder rung that can be used to authenticate a data value and to authenticate the data value relative to the rung.¶
For the MTL mode operations in this version of the document, the following constraints apply:¶
MTL node set objects consist of four base components: a public seed, a series identifier, a leaf node count and a dynamic array of node hash values.¶
Consistent with the definition of a node set in Section 6.2, the array is indexed by two values. The hash value for the leaf node with index leaf_index is stored at hashes[leaf_index, leaf_index] and the hash value for the internal node with index pair (left_index, right_index) is stored at hashes[left_index, right_index]. The organization of the array is up to the implementation.¶
A new MTLNS node set object initially has a specified public seed and series identifier, a node count of 0 and an empty array of hash values.¶
As discussed in Section 6.3 and Section 6.4, MTL mode node sets are constructed using two hash operations hash_leaf and hash_int. The hash operations are specified in terms of the SPHINCS+ abstract cryptographic functions and the address scheme in Section 4.¶
hash_leaf is a supporting function that hashes a data value to produce a leaf node. The operation takes a public seed, a series identifier, a leaf index and a data value as input and returns a leaf node hash value.¶
The operation uses the MTL_DATA address type and the abstract cryptographic function F.¶
##################################################################
# Algorithm 1: Hashing a Data Value to Produce a Leaf Node.
##################################################################
# Input: seed, public seed for the node set (associated with
# public key)
# Input: sid, series identifier for the node set
# Input: leaf_index of the leaf node hash value
# being computed
# Input: data_value corresponding to the leaf node
# Output: leaf_hash, leaf node hash value
def hash_leaf(seed, sid, leaf_index, data_value):
dataADRS = spx.ADRS()
dataADRS.setType(spx.ADRS.MTL_DATA)
dataADRS.setSID(sid)
dataADRS.setLeafIndex(leaf_index)
leaf_hash = spx.F(seed, dataADRS.bytes(), data_value)
return leaf_hash
¶
hash_int is a supporting function that hashes two child nodes to produce an internal node. The operation takes a public seed, a series identifier, a left index, a right index, a left child hash value and a right child hash value as input and returns an internal node hash value.¶
The operation uses the MTL_TREE address type and the abstract cryptographic function H.¶
##################################################################
# Algorithm 2: Hashing Two Child Nodes to Produce an Internal Node.
##################################################################
# Input: seed, public seed for the node set (associated with
# public key)
# Input: sid, series identifier for the node set
# Input: left_index, left index of the internal node
# Input: right_index, right index of the internal node
# Input: left_hash, left child hash value
# Input: right_hash, right child hash value
# Output: internal_hash, internal node hash value
def hash_int(seed, sid, left_index, right_index, left_hash,
right_hash):
mtlnsADRS = spx.ADRS()
mtlnsADRS.setType(spx.ADRS.MTL_TREE)
mtlnsADRS.setSID(sid)
mtlnsADRS.setLeftRightIndexes(left_index, right_index)
internal_hash = spx.H(seed, mtlnsADRS.bytes(), left_hash,
right_hash)
return internal_hash
¶
mtl_initns initializes a new MTL node set. The operation takes a public seed and a series identifier as input and returns a new MTL node set object.¶
##################################################################
# Algorithm 3: Initializing a MTL Node Set.
##################################################################
# Input: seed, public seed for the node set (associated with
# public key)
# Input: sid, series identifier for the node set
# Output: node_set, new MTL node set object
def mtl_initns(seed, sid):
node_set = MTLNS(seed, sid)
return node_set
¶
mtl_append appends a data value to a MTL node set, adding a leaf node and internal nodes as needed to produce a new ladder covering the expanded series of data values. The operation takes a data value and a MTL node set object as input and returns the new leaf index. The MTL node set object is updated in place.¶
mtl_append maintains the node set in a way that can produce ladders and authentication paths with the binary rung strategy.¶
The operation has two primary steps. First, a new leaf node is computed from the data value and added to the node set. Second, new internal nodes are computed from other nodes (if needed) and added to the node set to produce a new ladder covering the expanded series of data values.¶
##################################################################
# Algorithm 4: Appending a Data Value to a MTL Node Set.
##################################################################
# Input: data_value to append to the node set
# Input: node_set, MTL node set object (updated in place)
# Output: leaf_index assigned to the data value
def mtl_append(data_value, node_set):
leaf_index = node_set.count
node_set.count = leaf_index + 1
seed = node_set.seed
sid = node_set.sid
# Compute and store the leaf node hash value
node_set.hashes[leaf_index,leaf_index] = hash_leaf(seed, sid,
leaf_index, data_value)
# Compute and store additional internal node hash values
for i in range(1,lsb(leaf_index+1)):
left_index = leaf_index - 2**i + 1
mid_index = leaf_index - 2**(i-1) + 1
node_set.hashes[left_index, leaf_index] = hash_int(seed,
sid, left_index, leaf_index,
node_set.hashes[left_index, mid_index - 1],
node_set.hashes[mid_index, leaf_index])
return leaf_index
¶
mtl_authpath computes an authentication path for the data value at a specified leaf index relative to the current ladder for a MTL node set. The operation takes a leaf index and a node set object as input and returns an authentication path from the leaf node to its associated rung in the node set's current ladder.¶
mtl_authpath produces the authentication path with the binary rung strategy.¶
The operation has two primary steps. First, the current ladder rung covering the specified leaf index is selected. Second, the sibling hash values from the leaf node to the rung are concatenated to produce the authentication path.¶
##################################################################
# Algorithm 5: Computing an Authentication Path for a Data Value.
##################################################################
# Input: leaf_index, leaf node index of the data value to
# authenticate
# Input: node_set, MTL node set object encompassing the specified
# leaf node
# Output: auth_path, authentication path from the leaf node to
# the associated rung
def mtl_authpath(leaf_index, node_set):
left_index = 0
sibling_hashes = []
flags = 0
# Check that the leaf is part of this node set
if(leaf_index < 0) or (leaf_index >= node_set.count):
return None # Leaf is outside of node set
# Find the rung index pair covering the leaf index
for i in range(msb(node_set.count),-1,-1):
if node_set.count & (1 << i):
right_index = left_index + 2**i - 1
if leaf_index <= right_index:
break
left_index = right_index + 1
# Concatenate the sibling nodes from the leaf to the rung
for i in range(0, bit_width(right_index-left_index)):
if leaf_index & (1<<i):
sibling_left = (~(2**i-1) & leaf_index) - 2**i
else:
sibling_left = (~(2**i-1) & leaf_index) + 2**i
sibling_right = sibling_left + 2**i -1
sibling_hashes.append(node_set.hashes[sibling_left,
sibling_right])
auth_path = MTL_AUTH_PATH(flags, leaf_index, node_set.sid,
sibling_hashes, left_index, right_index)
return auth_path
¶
mtl_ladder computes the Merkle tree ladder for a node set. It takes a node set object as input and returns the ladder.¶
mtl_ladder produces the ladder with the binary rung strategy.¶
The operation has one primary steps: the current ladder rungs are concatenated to produce the ladder.¶
##################################################################
# Algorithm 6: Computing a Merkle Tree Ladder for a Node Set.
##################################################################
# Input: node_set, MTL node set object
# Output: ladder, Merkle tree ladder for this node set
def mtl_ladder(node_set):
left_index = 0
rungs = []
flags = 0
# Concatenate the rungs in the node set
for i in range(msb(node_set.count),-1,-1):
if node_set.count &(1 << i):
right_index = left_index + 2**i - 1
rungs.append(RUNG(left_index, right_index,
node_set.hashes[left_index,right_index]))
left_index = right_index + 1
ladder = MTL_LADDER(flags, node_set.sid, rungs)
return ladders
¶
mtl_rung selects a ladder rung associated with an authentication path. It takes a ladder and an authentication path as input and returns the associated rung of the lowest degree that can be used to verify the authentication path if the ladder has one, or None if not.¶
mtl_rung supports authentication paths produced with the binary rung strategy.¶
The operation has two primary steps. First, the authentication path is checked to confirm that its target rung index pair is compatible with the binary rung. Second, the ladder rungs are searched for the compatible rung of lowest degree that can be used to verify the authentication path.¶
##################################################################
# Algorithm 7: Selecting a Ladder Rung.
##################################################################
# Input: auth_path, authentication path from the leaf node to
# a rung in the ladder
# Input: ladder, Merkle tree ladder to authenticate relative to
# Output: assoc_rung, the rung in the ladder associated with the
# authentication path or None
def mtl_rung(auth_path, ladder):
# Check that authentication path and ladder have same SID
if(auth_path.sid != ladder.sid):
return None
leaf_index = auth_path.leaf_index
sibling_hash_count = auth_path.sibling_hash_count
# Check that authentication path is a binary rung strategy path
left_index = leaf_index & ~(2**sibling_hash_count-1)
right_index = left_index + (2**sibling_hash_count-1)
if((auth_path.rung_left != left_index) or
(auth_path.rung_right != right_index)):
return None
# Find associated rung with lowest degree, if present
assoc_rung = None
# Minimum degree is updated after first rung is found
min_degree = -1
for rung in ladder.rungs:
# Check if rung index pair would be encountered in
# evaluating authentication path for leaf node
left_index = rung.left_index
right_index = rung.right_index
if((left_index <= leaf_index) and
(right_index >= leaf_index)):
degree = lsb(right_index-left_index+1)-1
if(((degree <= lsb(left_index)-1) or
(lsb(left_index) == 0)) and
(right_index-left_index+1 == 2**degree) and
(degree <= sibling_hash_count)):
if((assoc_rung == None) or
(degree < min_degree)):
assoc_rung = rung
min_degree = degree
return assoc_rung
¶
mtl_verify verifies an authentication path for a data value relative to a rung. It takes a public seed, a data value and a rung as input and returns a Boolean value indicating whether the data value is successfully authenticated.¶
mtl_verify supports authentication paths produced with the binary rung strategy.¶
The operation has two primary steps. First, a leaf node hash value is computed from the data value using hash_leaf. If the leaf node index matches the rung index pair, the leaf node hash value is compared to the rung hash value. Second, internal node hash values are computed as needed from the leaf node hash value and successive sibling hash values in the authentication path using hash_int. Along the way, if the internal node index pair matches the rung index pair, then the internal hash value is compared to the rung hash value.¶
##################################################################
# Algorithm 8: Verifying an Authentication Path.
##################################################################
# Input: seed value for this operation (associated with public key)
# Input: data_value to authenticate
# Input: auth_path, (presumed) authentication path from corresponding
# leaf node to rung of ladder covering leaf node
# Input: assoc_rung, Merkle tree rung to authenticate relative to
# Output: result, a Boolean indicating whether the data value is
# successfully authenticated
def mtl_verify(seed, data_value, auth_path, assoc_rung):
sid = auth_path.sid
leaf_index = auth_path.leaf_index
sibling_hash_count = auth_path.sibling_hash_count
# Recompute leaf node hash value
target_hash = hash_leaf(seed, sid, leaf_index, data_value)
# Compare leaf node hash value to associated rung hash value if
# index pairs match
if ((leaf_index == assoc_rung.left_index) and
(leaf_index == assoc_rung.right_index)):
return target_hash == assoc_rung.hash
# Recompute internal node hash values and compare to
# associated rung hash value if index pairs match
for i in range(1, sibling_hash_count+1):
left_index = leaf_index & ~(2**i-1)
right_index = left_index + 2**i -1
mid_index = left_index + 2**(i-1)
sibling_hash = auth_path.sibling_hash[i-1]
if leaf_index < mid_index:
target_hash = hash_int(seed, sid, left_index,
right_index, target_hash,
sibling_hash)
else:
target_hash = hash_int(seed, sid, left_index,
right_index, sibling_hash,
target_hash)
# Break if associated rung reached
if((left_index == assoc_rung.left_index) and
(right_index == assoc_rung.right_index)):
return target_hash == assoc_rung.hash
return False
¶
Descriptions of the signer's and the verifier's operations in a typical application based on MTL mode are given in Section 9.1 and Section 9.2. Section 9.3 discusses how to identify ladders to facilitate interoperability. Representations of full and condensed MTL mode signatures are given in Section 9.4 and Section 9.5.¶
A signer MUST perform the following or an equivalent set of operations to sign messages in MTL mode.¶
The first step is performed once per key pair:¶
The second step is performed once per series of messages to be signed:¶
The third and fourth steps are performed once per message to be signed in a message series:¶
Compute a randomizer and a data value from the message, the context string, the series identifier and the message index for the message series as described in Section 5.1. Note that a domain separator of type MTL_MSG_SEP is prepended to the inputs to functions in Section 5.1. (See Section 4.7 for further discussion.)¶
Append the data value to the node set for the message series using mtl_append. The message index for the message series is incremented in this step.¶
The fifth and sixth steps are performed whenever the signer wants to produce a new signed ladder for the message series. The signer could do so after each new message is added, or after a new batch of new messages is added.¶
Compute the current ladder for the node set using mtl_ladder.¶
Format a domain separator sep from the context string as follows:¶
sep = octet(MTL_LADDER_SEP) || octet(OLEN(ctx)) || ctx || OID_MTL¶
Sign the ladder prepended with the domain separator using the private key of the underlying signature scheme. (See Section 4.7 for further discussion).¶
The seventh step is performed whenever the signer wants to provide a signed ladder to a requester, e.g., upon request by a verifier. (This step may not be needed if the signer supports the alternative of providing a full signature including the authentication path and a ladder.)¶
The eighth step is performed whenever the signer wants to compute a new authentication path for a message relative to the current ladder for the message series. The signer could do so after each new message is added, after a batch of new messages is added, and/or later, as needed, to update the authentication paths for older messages so that they are relative to the current ladder.¶
The ninth step is performed whenever the signer wants to provide authentication information to a requester, e.g., in conjunction with a message to be authenticated.¶
A verifier MUST perform the following or an equivalent set of operations to verify signatures in MTL mode:¶
The first step is performed once per key pair by each verifier:¶
The second, third, fourth and fifth steps is performed as needed for each message to be authenticated:¶
Obtain the authentication path and the randomizer associated with the message to be authenticated, e.g., in a condensed signature. The verifier MAY also obtain an explicit ladder identifier for the ladder that the authentication path was computed relative to - see Section 9.3.¶
Determine whether any of ladders held by the verifier includes a rung compatible with the authentication path, e.g., using mtl_rung. If not, then proceed to Step 6 and return here.¶
Re-compute a data value from the message, the context string, the series identifier in the authentication path and the message index in the authentication path and the randomizer as described in Section 5.2. Note that a domain separator of type MTL_MSG_SEP is prepended to the message prior to calling the functions in Section 5.2. (See Section 4.7 for further discussion).¶
Verify the authentication path for the data value at a specified message index relative to the compatible rung using mtl_verify.¶
The sixth and seventh steps are performed when the verifier doesn't have a ladder compatible with an authentication path.¶
Obtain the signed ladder associated with a specified ladder identifier. Alternatively, the verifier may request a full signature including an authentication path and the signed ladder that it is computed relative to.¶
Format a domain separator sep from the context string and the MTL mode object identifier as follows:¶
sep = octet(MTL_LADDER_SEP) || octet(OLEN(ctx)) || ctx || OID_MTL¶
Verify the signature on the ladder prepended with the domain separator using the public key of the underlying signature scheme. (See Section 4.7 for further discussion).¶
To facilitate interoperability, an application SHOULD have a way for signers and verifiers to identify a specific signed ladder that a verifier is interested in obtaining.¶
Potential approaches include:¶
The approach MAY be protocol-specific, e.g., the approach used for identifying MTL mode ladders associated with DNSSEC signatures MAY be different than the one used for MTL mode ladders associated with certificates.¶
An application MAY convey a "full" signature - including a randomizer, an authentication path, a ladder and its signature - with the following data structure. A full signature is convenient as a "drop-in" for a conventional signature because it can be verified on its own. However, it includes the overhead of the underlying signature on the ladder.¶
A full MTL mode signature data structure consists of five base components:¶
The byte representation of the full MTL mode signature is the concatenation of the binary encodings of the fields, using a 4-byte big endian representation for the signature length.¶
1 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-------------------------------+
| |
// Randomizer //
| |
+-------------------------------+
| |
// Authentication Path //
| |
+-------------------------------+
| |
// Ladder //
| |
+-------------------------------+
| Underlying Signature Length |
| |
+-------------------------------+
| |
// Underlying Signature //
| |
+-------------------------------+
¶
Note that the last three components are the same as a signed ladder (Section 9.6).¶
An application MAY convey a "condensed" signature - including a randomizer and an authentication path but not a ladder and its signature - with the following data structure. A condensed signature is convenient for reducing the size impact of the ladder signature. However, it requires the verifier to obtain the ladder from a separate source.¶
A condensed MTL mode signature data structure consists of two base components:¶
The byte representation of the condensed MTL mode signature is the concatenation of the binary encodings of the fields.¶
1 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-------------------------------+
| |
// Randomizer //
| |
+-------------------------------+
| |
// Authentication Path //
| |
+-------------------------------+
¶
A signed ladder data structure consists of three base components:¶
The byte representation of the signed ladder is the concatenation of the binary encodings of the fields, using a 4-byte big endian representation for the signature length.¶
1 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-------------------------------+
| |
// Ladder //
| |
+-------------------------------+
| Underlying Signature Length |
| |
+-------------------------------+
| |
// Underlying Signature //
| |
+-------------------------------+
¶
SPHINCS+-MTL applies MTL mode to the underlying signature scheme SPHINCS+. This document supports 24 instantiations corresponding to the 12 instantiations in the SPHINCS+ specification based on the SHAKE hash function [FIPS202] and the 12 instantiations based on the SHA2 hash functions [FIPS180-4]. (In contrast to SPHINCS+, this document does not support instantiations based on the Haraka hash function [HARAKA] - see Note.) This draft also supports the subset of instantiations for SLH-DSA as defined in the draft [FIPS205-IPD]. Note: As FIPS 205 evolves the changes will be tracked and updates may be made to this document as is appropriate.¶
The names of the SPHINCS+-MTL instantiations follow a similar convention to the SPHINCS+ instantiations:¶
The components of the name are as follows:¶
{hash} is the underlying hash function. For this version of the document, it MUST be "SHAKE" or "SHA2", corresponding to the underlying hash function.¶
{bitsec} is the target bit security. It MUST be "128", "192" or "256", corresponding to the "bitsec" value in [SPHINCS-PLUS]. The security parameter n is the target bit security level divided by 8, i.e., 16, 24 or 32. The corresponding NIST security levels for these bit security levels are 1, 3 and 5.¶
{opt} is the optimization goal. It MUST be "s" or "f". As discussed in [SPHINCS-PLUS], the "s" optimization results in smaller signature sizes, while the "f" optimization results in faster signing operations.¶
{variant} is the style of the tweakable hash function. It must be "simple" or "robust". As discussed in [SPHINCS-PLUS], the "simple" style results in faster operations, while the "robust" style results in more conservative security proofs.¶
SPHINCS+-MTL with a given set of components is based on the underlying signature scheme SPHINCS+ with the same components. SPHINCS+-MTL-{hash}-{bitsec}{opt}-{variant} may thus be read as "MTL mode of SPHINCS+-{hash}-{bitsec}{opt}-{variant}".¶
The four components may be chosen independently of one another. Given that there are two choices of {hash}, three choices of {bitsec}, two choices of {opt}, and two choices of {variant}, the total number of instantiations is 2*3*2*2 = 24. The table below lists the names of the 24 supported instantiations, their associated security parameter n, and their NIST security levels.¶
As in SPHINCS+ itself, the instantiations of the abstract cryptographic functions in the MTL mode operations depend on the underlying hash function and the security parameter. The function definitions for each instantiation are given in the following subsections. With the exception of H_msg_mtl, which is new, the instantiations of the functions are the same as in SPHINCS+ and are repeated here for completeness. Recall that the parameters to these functions should be provided as defined in Section 5 of this draft.¶
NOTE: This document does not include Haraka because it is not a NIST-approved hash function and because SPHINCS+ with Haraka only achieves NIST security levels 1 and 2.¶
SPHINCS+-MTL Security NIST
Instantiation Parameter n Level
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-128s-simple | 16 | 1 |
| SLH-DSA-MTL-SHAKE-128s | | |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-128f-simple | 16 | 1 |
| SLH-DSA-MTL-SHAKE-128f | | |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-192s-simple | 24 | 3 |
| SLH-DSA-MTL-SHAKE-192s | | |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-192f-simple | 24 | 3 |
| SLH-DSA-MTL-SHAKE-192f | | |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-256s-simple | 32 | 5 |
| SLH-DSA-MTL-SHAKE-256s | | |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-256f-simple | 32 | 5 |
| SLH-DSA-MTL-SHAKE-256f | | |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-128s-simple | 16 | 1 |
| SLH-DSA-MTL-SHA2-128s | | |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-128f-simple | 16 | 1 |
| SLH-DSA-MTL-SHA2-128f | | |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-192s-simple | 24 | 3 |
| SLH-DSA-MTL-SHA2-192s | | |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-192f-simple | 24 | 3 |
| SLH-DSA-MTL-SHA2-192f | | |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-256s-simple | 32 | 5 |
| SLH-DSA-MTL-SHA2-256s | | |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-256f-simple | 32 | 5 |
| SLH-DSA-MTL-SHA2-256f | | |
+--------------------------------+----------------------+
¶
The SHAKE instantiations employ the SHAKE256 hash function [FIPS202].¶
The randomized message digest function H_msg_mtl (see Section 4.3) is defined the same as the function H_msg in SPHINCS+ except that H_msg_mtl's output is 8n bits (n bytes) rather than 8m bits (m bytes):¶
The pseudorandom function PRF_msg (see Section 4.4) is defined the same as in SPHINCS+:¶
The tweakable hash functions F and H (see Section 4.5) are defined the same as in SPHINCS+. In the robust variants, they are defined as:¶
with the following notation:¶
In the simple variants, they are defined as:¶
NOTE: The definition of H in the robust variant above corrects a typo in the SPHINCS+ specification. In SPHINCS+, the string input to SHAKE256 (in the notation of this document) is PK.seed || ADRS || M_1* || M_2. Following that specification, both M_1 and M_2 would be xored with the same mask value, SHAKE256(PK.seed, ADRS, 8n). The intent in SPHINCS+ is rather that the concatenation (M_1 || M_2) is xored with a longer mask, as is also done in the SHA2 instantiations. This document therefore replaces M_1 || M_2* with (M_1 || M_2)*.¶
The SHA2 instantiations employ the SHA2-256 and/or SHA2-512 hash functions [FIPS186-4], the HMAC-SHA2-256 and/or HMAC-SHA2-512 message authentication codes (pseudorandom functions) [FIPS198-1] and the MGF1-SHA2-256 and/or MGF1-SHA2-512 mask generation functions [RFC8017]. (Here and in the following, SHA-X denotes SHA2-256 when n = 16 and SHA2-512 when n = 24 or 32.)¶
The randomized message digest function H_msg_mtl (see Section 4.3) is defined the same as the function H_msg in SPHINCS+ except that its output is n bytes rather than m bytes:¶
The pseudorandom function PRF_msg (see Section 4.4) is defined the same as in SPHINCS+:¶
The tweakable hash functions F and H (see Section 4.5) are defined the same as in SPHINCS+. In the robust variants, they are defined as:¶
with the following notation:¶
In the simple variants, they are defined as:¶
Parameters required for calculation:¶
Calculations:¶
This document makes no requests of IANA. However, a future version of this document may request that IANA register any or all of the following:¶
Because the domain separator types build on NIST's proposed domain separation scheme, the request for domain separator types may depend on the existence of a registry for domain separation type. Similarly, because the address types build on the SPHINCS+ address scheme, that request may depend on the existence of a registry for SPHINCS+ address types in conjunction with the standardization of SPHINCS+ by the IETF.¶
Implementers MUST use a secure random generator [RFC4086].¶
Implementers MUST select a security parameter consistent with their security requirements.¶
Implementers MUST also select cryptographic functions that are generally accepted for their intended security level and use within MTL mode. Similar to SPHINCS+, the desired properties for the cryptographic functions in MTL mode are that PRF_msg is a pseudorandom function and F and H are multi-target, multi-function second preimage resistant function families. The desired property for H_msg_mtl is that it is an extended target collision resistant function with nonce (where the nonce is provided as the message index in the prepended address value).¶
Because MTL mode is an add-on to an underlying signature scheme, implementers MUST ensure adequate cryptographic separation between MTL mode's uses of cryptographic functions and the use of cryptographic functions by the underlying signature scheme. The operations in Section 5.1, Section 5.2, Section 9.1, and Section 9.2 including the domain separators, and the proposed instantiations in Section 10 were selected taking cryptographic separation between MTL mode and SPHINCS+ into account. Other underlying signature schemes need to be evaluated separately.¶
To avoid unintended interactions between the different instantiations of MTL mode, a given key pair SHOULD only be used with a single instantiation of MTL mode.¶
The signer in MTL mode maintains a Merkle tree node set and is therefore stateful. Implementers SHOULD ensure that the node set is maintained accurately and is not at risk of being reset or repeated, or otherwise the security of MTL mode could be degraded. In particular, as discussed in [MTL-MODE], the reuse of state in MTL mode could provide additional target hash values for an adversary to match in an attack on the hash function, thereby weakening the provable security bounds. In contrast to hash-based signature schemes, however, the reuse of state in MTL mode does not reveal information about a private key that could directly lead to a signature forgery.¶
Similar to SPHINCS+, the security of MTL mode relies on a form of target collision resistance. Target collision resistance assumes that the message is hashed together with a randomizer that is produced with a secure random generator. An advantage of target collision resistance over basic collision resistance (without a randomizer) is that the bit security level associated with security parameter n can be achieved with an n-byte hash value rather than a 2n-byte hash value. This advantage reduces the size of the authentication paths and ladders in MTL mode, in a similar way that it reduces the size of the signatures in SPHINCS+. If the randomizer in the MTL mode operations is not produced securely, however, then the security of the MTL mode operations could be significantly at risk. In particular, if an adversary can predict the randomizer, then an attacker can potentially perform a basic collision attack to find two messages that hash to the same hash value together with the predicted randomizer. Because the hash value is only n bytes, the implementation in this case would only have roughly 4n bits of security rather than the target 8n bits.¶
Section 5.1 suggests one primary approach to secure random generation, namely the use of a pseudorandom function PRF_msg. This is the same approach that SPHINCS+ takes, but the inputs are different for the MTL mode operations.¶
In SPHINCS+, the PRF is applied to an optional external random value and the message being signed. Including the message ensures that the randomizer for one signature operation is cryptographically independent from the randomizer for another signature operation involving a different message, while maintaining the statelessness of SPHINCS+. If same message is signed twice, however, the same randomizer and ultimately the same signature will be generated (deterministic signing). Deterministic signing could increase the risk of side-channel attacks revealing information about the signer's private key if the same computation is run multiple times. Including the optional random value avoids deterministic signing and mitigates this particular risk.¶
In the MTL mode operations, following the suggested example in Section 5.1, the PRF is applied to an optional external random value and an address value. Including the address value ensures that the randomizer for one signature operation is cryptographically independent from another signature operation, regardless of the message being signed. Here, the MTL mode operations are already stateful, and implementations are assumed to be able to maintain a unique address value. If the implementation is not able to maintain a unique address value, however, and uses the same address value more than once, the same randomizer will be generated when the address value is used again, making it predictable. This could lead to a basic collision attack. Including the optional random value avoids this predictability and mitigates the risk. Section 5.1 also suggests the option of including the message in the input in addition to the address value, which is another way to avoid the predictability of the randomizer if the same address value is used more than once (with a different message each time). As noted in Section 5.1, however, including the message involves an additional pass over the message (once for PRF_msg and once for H_msg_mtl), which can be disadvantageous if the message is long. For this reason, including the message is OPTIONAL.¶
This specification uses a domain separator format to distinguish between the use of an underlying signature scheme in MTL mode from its use in pure and pre-hash modes. The domain separator format is beneficial in an application that potentially supports MTL mode in addition to pure or more modes of operation for a given key pair. Other ways to protect against unintended interactions between the use of a key pair in different modes of operation include (a) supporting only a single mode of operation within the application, e.g., only MTL mode, and not allowing key pairs used within the application to be used in other applications; and (b) specifying the mode of operation for a key pair as part of key management information (e.g., via an algorithm identifier or key usage constraints).¶
Considerations for the optional context string are intended to be the same as those for the underlying signature scheme (if it supports one, as FIPS 204 and FIPS 205 are intended to). Section 8.3 of [RFC8032] provides helpful guidance on the use of context strings.)¶
An adversary who learns a set of messages and their MTL mode signatures also learns the leaf nodes of the Merkle node set corresponding to these messages, the authentication paths in the signatures, and the signed ladders in the signatures. Such an adversary can also compute any nodes of the Merkle node set that depends on the nodes it has learned, and form other condensed and full signatures on the messages it has learned (see Section E.2.4 for discussion; the adversary can perform the same steps as an intermediary). Even with the ability to reconstruct the Merkle node set, however, assuming cryptographic security of MTL mode and the underlying signature scheme, an adversary cannot form signatures on messages that have not already been signed by the signer, as it does not have access to the signer's private key.¶
The adversary also cannot form signatures on messages that have already been signed by the signer but that the adversary has not yet learned, because the adversary does not know and cannot predict the randomizers associated with those messages. Moreover, because of the lack of knowledge about the other messages' randomizers, the adversary also cannot determine which messages have been signed based on the reconstructed Merkle node set, other than those whose randomizers it has already learned. Therefore, even though the Merkle tree node set can gradually be reconstructed publicly, the individual messages that have been signed by the signer remain private until the signer publishes them.¶
The authors would like to acknowledge the following individuals for their contributions to this document: Fitzgerald Marcelin.¶