| Internet-Draft | Merkle Tree Ladder (MTL) Mode Signatures | October 2025 |
| Harvey, et al. | Expires 19 April 2026 | [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 ML-DSA as defined in FIPS204 and SLH-DSA as defined in FIPS205. 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 19 April 2026.¶
Copyright (c) 2025 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. Two drafts on applying MTL mode to applications are not available as of this writing. [I-D.harvey-cfrg-mtl-mode-considerations] provides design considerations for application designers on how to add Merkle Tree Ladder (MTL) Mode signatures into their applications. [I-D.fregly-dnsop-slh-dsa-mtl-dnssec] describes how to apply MTL Mode to DNSSEC. Additionally [I-D.sheth-pqc-dnssec-strategy] discusses the utility of MTL mode to developing a resilient PQC DNSSEC strategy. More drafts may be developed for other applications.¶
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 ML-DSA [FIPS204] and SLH-DSA [FIPS205], the first signature algorithms selected by NIST for standardization as part of its post-quantum cryptography project. The design decision is motivated by three considerations: (1) SLH-DSA also is based on Merkle trees, and thus MTL Mode does not introduce any additional cryptographic assumptions; (2) both algorithms have 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.¶
The cryptographic parameter is defined in Section 4.1. The cryptographic functions are defined in Section 11 and Section 5. The address scheme is defined in Section 6.2.¶
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 SLH-DSA or ML-DSA are given in Section 10. Recommended instantiations for other underlying signature schemes may be added in updates to this document.¶
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 16).¶
MTL mode makes use of the following tweakable hash functions:¶
The inputs to H_leaf and H_int have the following meanings:¶
H_leaf is used for computing a leaf node from a message in MTL mode (see Section 8.2.1). H_int is used for computing an internal node hash value from two child node hash values (see Section 8.2.2).¶
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 messages to an expanding message series, computing ladders and computing authentication paths from messages 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 messages. Each message in the series is stored in 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 message is appended.¶
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.¶
Each instance of MTL mode is associated with a unique series identifier (SID). Each series identifier uniquely identifies a node set. Signers MUST NOT sign multiple distinct node sets under the same series identifier. It is RECOMMENDED that signers generate series identifiers using an approved Random Bit Generator [RFC4086].¶
The series identifier is a 2n-byte value, where n is the security parameter.¶
Each message in an MTL node set is assigned a 64-bit index. To maintain the security of the underlying hash functions, signers MUST NOT re-use any index after they have been used for signing.¶
For each node in the node set we assign a unique tweak ADRS based on its position within the hash tree. The first 64 bits of ADRS is the minimum index included in the subtree covered by the node, and the remaining 64 bits of ADRS is the maximum index in the subtree; both are in big-endian notation.¶
We use ADRS(L,R) to denote the tweak value computed from these indices.¶
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 messages with indexes between L and R inclusive. If L = R, the node is a leaf node (Section 6.4). If L < R, then it is an internal node (Section 6.5).¶
A leaf node is a node where L = R. It has no child nodes. Its hash value is computed as¶
V = H_leaf(SID, ADRS(L,R), Rand, ctx_msg, msg)¶
where H_leaf is a hash function defined in Section 8.2.1, SID is the series identifier for the node set, Rand is the randomizer associated with leaf index L, ctx_msg is the context string associated with msg, and msg is the message stored in leaf index L.¶
When initially signing msg, Rand MUST be sampled such that it is indistinguishable from uniform random sampling. Rand values MAY be sampled in advance, in which case they MUST be kept private until they are used in a signature.¶
The MTL addressing scheme defines a maximum index of 2^(64)-1. Thus a single node set may authenticate a maximum of 2^64 messages.¶
A leaf node with a given index authenticates the message stored in the corresponding index. It follows that if a node set has a leaf node with a given index, then the message series MUST have a message signed 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 = H_int(SID, ADRS(L,R), H_L, H_R)¶
where H_int is a hash function defined in Section 8.2.2, SID is the series identifier, H_L is the left child's hash value and H_R is the right child's hash value.¶
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 messages stored in 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 message series MUST have messages 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,4) | (5,5)
(0,5) | (0,3) | (4,5)
(0,31) | (0,15) | (16,31)
(0,2) | (0,1) | (0,2)
(7,13) | (7,10) | (11,13)
¶
A ladder is a subset of nodes that is used to authenticate messages. 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 messages in the message series.¶
The rungs in the binary rung strategy are selected as follows. Let N be the number of messages in the message 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 messages. 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 messages. 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 messages.¶
A rung is said to cover the messages it authenticates, and a ladder is said to cover the messages that its rungs collectively authenticate. The ladder just described thus covers all N messages 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 messages, starting from the left; the second rung as the apex of the largest perfect binary tree than can be formed over the remaining messages; 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 messages, 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 message 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 Messages | Ladder Rungs
N |
-------------------------------------------------
1 | (0,0)
2 | (0,1)
3 | (0,1) (2,2)
4 | (0,3)
5 | (0,3) (4,4)
6 | (0,3) (4,5)
7 | (0,3) (4,5) (6,6)
8 | (0,7)
9 | (0,7) (8,8)
10 | (0,7) (8,9)
11 | (0,7) (8,9) (10,10)
12 | (0,7) (8,11)
13 | (0,7) (8,11) (12,12)
14 | (0,7) (8,11) (12,13)
15 | (0,7) (8,11) (12,13) (14,14)
16 | (0,15)
17 | (0,15) (16,16)
18 | (0,15) (16,17)
19 | (0,15) (16,17) (18,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 message.¶
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,6) to the rung (0,7) are the nodes with indexes (7,7), (4,5) and (0,3). The authentication path for the message with index 6 includes the hash values at those nodes. This message can be authenticated by recomputing leaf node 6 from the message using H_leaf, recomputing internal nodes (6,7), (4,7) and (0,7) from the sibling node hash values and previously computed hash values using H_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 message 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 message up to and including the target rung.¶
Continuing the example above, the authentication path for the message stored at index 6 can be verified relative to any ladder that includes a rung with index (6,6), (6,7), (4,7) and/or (0,7). In this case, the ladder covering the first six messages could also be used, because it includes a rung with index 6.¶
More generally, if an authentication path for the message stored at leaf_index is computed relative to a ladder that covers the first N messages, the authentication path can also be authenticated relative to any binary rung strategy ladder that covers the first N' messages if the following condition is met:¶
leaf_index <= N' <= N.¶
The first inequality ensures that the ladder covers the message; 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 message. The rung can be used to authenticate the message 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 8-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 |
+-------------------------------+
| |
// Randomizer //
| |
+-------------------------------+
| |
| 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 messages 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 message and to authenticate the message 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 series identifier, a leaf node count, and a dynamic array of node hash values and randomizers.¶
Consistent with the definition of a node set in Section 6.3, 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 series identifier, a node count of 0 and an empty array of hash values.¶
As discussed in Section 6.4 and Section 6.5, MTL mode node sets are constructed using two hash operations hash_leaf and hash_int. The hash operations are specified in terms of the abstract cryptographic functions H_leaf and H_int, and the address scheme in Section 4.¶
hash_leaf is a supporting function that hashes a message to produce a leaf node. The operation takes a message, a series identifier, a leaf index, and a randomizer as input and returns a leaf node hash value.¶
The operation uses the abstract cryptographic function H_leaf.¶
##########################################################
# Algorithm 1: Hashing a Message to Produce a Leaf Node.
##########################################################
# Input: sid, series identifier for the node set
# Input: leaf_index of the leaf node hash value
# being computed
# Input: randomizer associated with leaf_index
# Input: message, the message to be authenticated and
# stored in index leaf_index
# Input: ctx_msg, context string to associate with the
# message
# Output: leaf_hash, leaf node hash value
def hash_leaf(sid, leaf_index, randomizer, message, ctx_msg):
mtlnsADRS = ADRS()
mtlnsADRS.setLeftRightIndexes(leaf_index, leaf_index)
leaf_hash = H_leaf(sid, mtlnsADRS, randomizer, ctx_msg, message)
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 abstract cryptographic function H_int.¶
##################################################################
# Algorithm 2: Hashing Two Child Nodes to Produce an Internal Node.
##################################################################
# 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(sid, left_index, right_index, left_hash, right_hash):
mtlnsADRS = ADRS()
mtlnsADRS.setLeftRightIndexes(left_index, right_index)
internal_hash = H_int(sid, mtlnsADRS, left_hash, right_hash)
return internal_hash
¶
mtl_initns initializes a new MTL node set. The operation takes a series identifier as input and returns a new MTL node set object.¶
##################################################################
# Algorithm 3: Initializing a MTL Node Set.
##################################################################
# Input: sid, series identifier for the node set
# Output: node_set, new MTL node set object
def mtl_initns(sid):
node_set = MTLNS(sid)
return node_set
¶
mtl_append appends a message to a MTL node set, adding a leaf node and internal nodes as needed to produce a new ladder covering the expanded series of messages. The operation takes a message 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 message 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 messages.¶
##################################################################
# Algorithm 4: Appending a Message to a MTL Node Set.
##################################################################
# Input: msg, message to append to the node set
# Input: ctx_msg, context string associated with msg
# Input: node_set, MTL node set object (updated in place)
# Output: leaf_index where msg has been stored in the node_set
def mtl_append(msg, ctx_msg, node_set):
leaf_index = node_set.count
node_set.count = leaf_index + 1
sid = node_set.sid
# Compute and store the leaf node hash value
rand = urandom(n)
node_set.randomizers[leaf_index] = rand
node_set.hashes[leaf_index,leaf_index] = hash_leaf(sid,
leaf_index, rand, msg, ctx_msg)
# 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(
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 message stored 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 Message.
##################################################################
# Input: leaf_index, leaf node index of the message 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,
node_set.randomizers[leaf_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 step: 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 message relative to a rung. It takes a message, a context string, and a rung as input and returns a Boolean value indicating whether the message 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 message and authentication path 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: msg, message to authenticate
# Input: ctx_msg, context string associated with msg
# 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 message
# is successfully authenticated
def mtl_verify(msg, ctx_msg, 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(sid, leaf_index,
auth_path.randomizer,
msg, ctx_msg)
# 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(sid, left_index,
right_index, target_hash,
sibling_hash)
else:
target_hash = hash_int(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.4 and Section 9.5. Section 9.6 discusses how to identify ladders to facilitate interoperability. Representations of full and condensed MTL mode signatures are given in Section 9.1 and Section 9.2.¶
An application MAY convey a "full" signature - 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¶
1 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-------------------------------+
| |
// SID //
| |
+-------------------------------+
| |
// Authentication Path //
| |
+-------------------------------+
| |
// Signed Ladder //
| |
+-------------------------------+
¶
An application MAY convey a "condensed" signature - including a SID 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
+-------------------------------+
| |
// SID //
| |
+-------------------------------+
| |
// 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 //
| |
+-------------------------------+
¶
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:¶
Sample a randomizer and compute the leaf hash for the message series as described in Section 6.4.¶
Append the leaf hash 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.¶
Sign the ladder using the private key of the underlying signature scheme and OID_MTL as the context string.¶
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.¶
The algorithms below describe MTL mode signatures using the traditional interface for cryptographic signature schemes. In order to serve as a drop-in replacement, the signing algorithm always produces full signatures. Condensed signatures are handled in Section 9.5¶
The algorithms make use of an underlying signature scheme sig_scheme=(gen, sign, vrfy).¶
##########################################################
# Algorithm 9: MTL Key Generation
##########################################################
# Input: n, the target byte security level
# Output: (pk, sk, node_set), a new public key, secret key,
# and empty node set
def mtl_gen(n):
(sig_pk, sig_sk) = sig_scheme.gen(n)
sid = urandom(2 * n)
pk = (sid, sig_pk)
sk = (sid, sig_sk)
return (pk, sk)
¶
##########################################################
# Algorithm 10: MTL Signing
##########################################################
# Input: sk, an MTL secret key
# Input: msg, the message to be authenticated
# Input: ctx_msg, the context string to be associated
# with msg
# Input: node_set, MTL node set object (updated in place)
# Output: full_sig, a full signature on m
def mtl_sign(sk, msg, ctx_msg, node_set):
sid = sk.sid
leaf_index = mtl_append(msg, ctx_msg, node_set)
auth_path = mtl_authpath(leaf_index, node_set)
ladder = mtl_ladder(node_set)
ladder_signature = sig_scheme.sign(sk.sig_sk, ladder,
OID_MTL)
signed_ladder = MTL_SIGNED_LADDER(ladder,
len(ladder_signature,
ladder_signature))
full_sig = MTL_FULL_SIGNATURE(sid, auth_path,
signed_ladder)
return full_sig
¶
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, fifth and sixth steps is performed as needed for each message to be authenticated:¶
Obtain the authentication path and the series identifier 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.6.¶
Determine whether any of ladders held by the verifier includes a rung compatible with the authentication path, e.g., using mtl_rung. If so, skip to step 5.¶
The fourth step is 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.¶
Re-compute a leaf hash from the message, the context string, the series identifier in the authentication path and the message index in the authentication path and the series identifier as described in Section 6.4.¶
Verify the authentication path for the message at a specified message index relative to the compatible rung using mtl_verify.¶
The algorithms below describe verifying an mtl signature. mtl_vrfy describes how to verify a full signature. mtl_reconstitute describes how to transform a condensed signature and a previously-saved full signature on the same node set into a new full signature.¶
##########################################################
# Algorithm 11: MTL Verification
##########################################################
# Input: pk, an mtl public key
# Input: msg, the message to verify
# Input: ctx_msg, the context string associated with msg
# Input: full_sig, a full signature on msg
# Output: a boolean value indicating whether or not the
# signature is accepted
def mtl_vrfy(pk, msg, ctx_msg, full_sig):
if sig.vrfy(pk, full_sig.ladder, MTL_OID,
full_sig.underlying_signature) != True:
return False
assoc_rung = mtl_rung(full_sig.auth_oath, full_sig.ladder)
if mtl_verify_authpath(msg, ctx_msg, full_sig.auth_path,
assoc_rung) != True:
return False
return True
¶
##########################################################
# Algorithm 12: MTL Reconstitution
##########################################################
# Input: pk, an mtl public key
# Input: msg, the message to verify
# Input: ctx_msg, the context string associated with msg
# Input: condensed_sig, a condensed signature on msg to
# be verified
# Input: full_sig, a previously-verified full signature for
# some message
# Output: new_full_sig, a full signature for msg
def mtl_vrfy(pk, msg, ctx_msg, condensed_sig, full_sig):
if condensed_sig.sid != full_sig.sid:
return None
sid = condensed_sig.sid
new_full_sig = MTL_FULL_SIGNATURE(sid, condensed_sid.authpath,
full_sig.signed_ladder)
return new_full_sig
¶
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.¶
The names of the MTL instantiations follow a similar convention to the SLH-DSA instantiations:¶
The components of the name are as follows:¶
{signature} is the underlying signature scheme. This document defines support for ML-DSA [FIPS204] and SLH-DSA in pure mode [FIPS205]. We expect to support additional post-quantum signature algorithms as they become standardized.¶
{hash} is the underlying hash function group used for the MTL node set. For this version of the document, it MUST be "SHAKE" or "SHA2". If the choice of {signature} includes a choice of hash function, it is RECOMMENDED that {hash} use the same hash as the signature scheme. This document only defines instantiations which follow this recommendation.¶
{bitsec} is the target bit security level. It MUST be "128", "192" or "256". The target bit security level is the security parameter n times by 8. The corresponding NIST security strength categories for these bit security levels are 1, 3 and 5. For parameter sets where {bitsec} and the bit security level of {signature} do not match, the security strength achieved by the construction is the lesser of the two.¶
{variant} is reserved for future use. If not used, the leading hyphen is omitted from the name. This document does not define any values for {variant}.¶
The first three components may be chosen independently of one another. However, this document follows the recommendations for {signature} and {bitsec}, hence the choice of {signature} fully determines the remaining parameters. The table below lists the names of the 17 supported instantiations, their associated security parameter n, and their NIST security categories.¶
MTL Security NIST
Instantiation Parameter n Category
+------------------------------------+--------------+---------+
| SLH-DSA-SHAKE-128s-MTL-SHAKE-128 | 16 | 1 |
+------------------------------------+--------------+---------+
| SLH-DSA-SHAKE-128f-MTL-SHAKE-128 | 16 | 1 |
+------------------------------------+--------------+---------+
| SLH-DSA-SHAKE-192s-MTL-SHAKE-192 | 24 | 3 |
+------------------------------------+--------------+---------+
| SLH-DSA-SHAKE-192f-MTL-SHAKE-192 | 24 | 3 |
+------------------------------------+--------------+---------+
| SLH-DSA-SHAKE-256s-MTL-SHAKE-256 | 32 | 5 |
+------------------------------------+--------------+---------+
| SLH-DSA-SHAKE-256f-MTL-SHAKE-256 | 32 | 5 |
+------------------------------------+--------------+---------+
| SLH-DSA-SHA2-128s-MTL-SHA2-128 | 16 | 1 |
+------------------------------------+--------------+---------+
| SLH-DSA-SHA2-128f-MTL-SHA2-128 | 16 | 1 |
+------------------------------------+--------------+---------+
| SLH-DSA-SHA2-192s-MTL-SHA2-192 | 24 | 3 |
+------------------------------------+--------------+---------+
| SLH-DSA-SHA2-192f-MTL-SHA2-192 | 24 | 3 |
+------------------------------------+--------------+---------+
| SLH-DSA-SHA2-256s-MTL-SHA2-256 | 32 | 5 |
+------------------------------------+--------------+---------+
| SLH-DSA-SHA2-256f-MTL-SHA2-256 | 32 | 5 |
+------------------------------------+--------------+---------+
| ML-DSA-44-MTL-SHAKE-128 | 16 | 1 |
+------------------------------------+--------------+---------+
| ML-DSA-65-MTL-SHAKE-192 | 24 | 3 |
+------------------------------------+--------------+---------+
| ML-DSA-87-MTL-SHAKE-256 | 32 | 5 |
+------------------------------------+--------------+---------+
¶
Throughout this section we make use of the functions encode_string() and bytepad() defined by [CSHAKE]. We define a variable BLOCKSIZE which matches the block size in bytes of the hash function in use: 64 for SHA2-256; 128 for SHA2-512; 168 for SHAKE128; 136 for SHAKE256.¶
Note that even though both H_leaf and H_int may use the same underlying hash function, the signer MUST NOT call H_leaf using an internal ADRS (i.e. L != R) nor H_int with a leaf ADRS (i.e. L == R). This is due to the security of tweakable hash functions relying on the signer never using the same ADRS twice for different purposes.¶
The SHAKE instantiations employ the customized SHAKE variants cSHAKE128 and cSHAKE256 [CSHAKE]. (Here and in the following, cSHAKE denotes cSHAKE128 when n = 16 and cSHAKE256 when n = 24 or 32.) The tweakable hash functions H_leaf and H_int (see Section 5) are defined as follows:¶
The SHA2 instantiations employ the SHA2-256 and/or SHA2-512 hash functions [FIPS186-4]. (Here and in the following, SHA-X denotes SHA2-256 when n = 16 and SHA2-512 when n = 24 or 32.)¶
Following the design philosophy of cSHAKE, we define functions cSHA-X to incorporate the customization string into the hash function. To achieve the desired output lengths, we then truncate the hash to the first L bits.¶
The tweakable hash functions H_leaf and H_int (see Section 5) are defined as follows:¶
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:¶
For testing purposes, a reference implementation of MTL mode is available in C. The MTL library can be found at https://github.com/verisign/MTL and includes example tools for key generation, signing, and verifying messages with an MTL message series.¶
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 strength category and use within MTL mode. Similar to SLH-DSA, the desired properties for the cryptographic functions in MTL mode are that H_leaf and H_int are multi-target, multi-function second preimage resistant function families.¶
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.¶
Signers MUST NOT use the same series identifier for multiple node sets. Implementers SHOULD sample SIDs from an approved random bit generator.¶
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 SLH-DSA, 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 SLH-DSA. 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.¶
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 205 does). 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 MTL 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 MTL node set that depend 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 MTL 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 MTL 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 data structures and algorithms have changed significantly since prior versions of this document. We expect they will be updated again in future revisions. The authors welcome any and all feedback.¶
The authors would like to acknowledge the following individuals for their contributions to this document: Fitzgerald Marcelin.¶