Merkle Tree Ladder Mode (MTL) Signatures
draft-harvey-cfrg-mtl-mode-02
| Document | Type | Active Internet-Draft (individual) | |
|---|---|---|---|
| Authors | Joe Harvey , Burt Kaliski , Andrew Fregly , Swapneel Sheth | ||
| Last updated | 2023-12-12 | ||
| RFC stream | (None) | ||
| Intended RFC status | (None) | ||
| Formats | |||
| Stream | Stream state | (No stream defined) | |
| Consensus boilerplate | Unknown | ||
| RFC Editor Note | (None) | ||
| IESG | IESG state | I-D Exists | |
| Telechat date | (None) | ||
| Responsible AD | (None) | ||
| Send notices to | (None) |
draft-harvey-cfrg-mtl-mode-02
Network Working Group J. Harvey
Internet-Draft B. Kaliski
Intended status: Informational A. Fregly
Expires: 14 June 2024 S. Sheth
Verisign Labs
12 December 2023
Merkle Tree Ladder Mode (MTL) Signatures
draft-harvey-cfrg-mtl-mode-02
Abstract
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.
Status of This Memo
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/.
Harvey, et al. Expires 14 June 2024 [Page 1]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
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 June 2024.
Copyright Notice
Copyright (c) 2023 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.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1. Conventions Used in This Document . . . . . . . . . . . . 5
2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 5
2.2. Operators . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3. Functions . . . . . . . . . . . . . . . . . . . . . . . . 7
2.4. Algorithm Style . . . . . . . . . . . . . . . . . . . . . 7
3. General Model . . . . . . . . . . . . . . . . . . . . . . . . 8
4. Security Parameters, Cryptographic Functions and Address
Scheme . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.1. Security parameter . . . . . . . . . . . . . . . . . . . 10
4.2. Randomized message digest function (H_msg_mtl) . . . . . 10
4.3. Pseudorandom function (PRF_msg) . . . . . . . . . . . . . 10
4.4. Tweakable hash functions (F and H) . . . . . . . . . . . 11
4.5. Address scheme . . . . . . . . . . . . . . . . . . . . . 11
4.6. Cryptographic separation and message index association for
H_msg_mtl and PRF_msg . . . . . . . . . . . . . . . . . . 13
5. Computing Data Values from Messages . . . . . . . . . . . . . 14
5.1. Signer Operations . . . . . . . . . . . . . . . . . . . . 14
5.2. Verifier Operations . . . . . . . . . . . . . . . . . . . 14
6. MTL Node Sets . . . . . . . . . . . . . . . . . . . . . . . . 15
6.1. Seeds and Series Identifiers . . . . . . . . . . . . . . 15
6.2. Node Sets . . . . . . . . . . . . . . . . . . . . . . . . 15
6.3. Leaf Nodes . . . . . . . . . . . . . . . . . . . . . . . 16
6.4. Internal Nodes . . . . . . . . . . . . . . . . . . . . . 16
Harvey, et al. Expires 14 June 2024 [Page 2]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
6.5. Ladders . . . . . . . . . . . . . . . . . . . . . . . . . 17
6.6. Authentication Paths . . . . . . . . . . . . . . . . . . 19
6.7. Backward Compatibility . . . . . . . . . . . . . . . . . 20
7. Data Structures . . . . . . . . . . . . . . . . . . . . . . . 21
7.1. Ladder . . . . . . . . . . . . . . . . . . . . . . . . . 21
7.2. Rung . . . . . . . . . . . . . . . . . . . . . . . . . . 22
7.3. Authentication Path . . . . . . . . . . . . . . . . . . . 23
8. MTL Node Set Operations . . . . . . . . . . . . . . . . . . . 24
8.1. MTL Node Set Object . . . . . . . . . . . . . . . . . . . 25
8.2. MTL Node Set Hash Operations . . . . . . . . . . . . . . 25
8.2.1. Hashing a Data Value to Produce a Leaf Node Hash Value
(Function: hash_leaf) . . . . . . . . . . . . . . . . 25
8.2.2. Hashing Two Child Nodes to Produce an Internal Node
(Function: hash_int) . . . . . . . . . . . . . . . . 26
8.3. Initializing a MTL Node Set (Function: mtl_initns) . . . 27
8.4. Appending a Data Value to a MTL Node Set (Function:
mtl_append) . . . . . . . . . . . . . . . . . . . . . . . 28
8.5. Computing an Authentication Path (Function:
mtl_authpath) . . . . . . . . . . . . . . . . . . . . . . 29
8.6. Computing the Merkle Tree Ladder for a Node Set (Function:
mtl_ladder) . . . . . . . . . . . . . . . . . . . . . . . 30
8.7. Selecting a Ladder Rung (Function: mtl_rung) . . . . . . 31
8.8. Verifying an Authentication Path (Function:
mtl_verify) . . . . . . . . . . . . . . . . . . . . . . . 32
9. Signing and Verifying Messages in MTL Mode . . . . . . . . . 34
9.1. Signing Messages . . . . . . . . . . . . . . . . . . . . 34
9.2. Verifying Signatures . . . . . . . . . . . . . . . . . . 36
9.3. Ladder identifiers . . . . . . . . . . . . . . . . . . . 37
9.4. Full Signatures . . . . . . . . . . . . . . . . . . . . . 37
9.5. Condensed Signatures . . . . . . . . . . . . . . . . . . 39
10. SPHINCS+ in MTL Mode . . . . . . . . . . . . . . . . . . . . 39
10.1. SHAKE instantiations . . . . . . . . . . . . . . . . . . 42
10.1.1. Randomized message digest function (H_msg_mtl) . . . 42
10.1.2. Pseudorandom function (PRF_msg) . . . . . . . . . . 42
10.1.3. Tweakable hash functions (F and H) . . . . . . . . . 42
10.2. SHA2 instantiations . . . . . . . . . . . . . . . . . . 43
10.2.1. Randomized message digest function (H_msg_mtl) . . . 43
10.2.2. Pseudorandom function (PRF_msg) . . . . . . . . . . 43
10.2.3. Tweakable hash functions (F and H) . . . . . . . . . 44
11. Related Work . . . . . . . . . . . . . . . . . . . . . . . . 44
12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 45
13. Security Considerations . . . . . . . . . . . . . . . . . . . 45
14. References . . . . . . . . . . . . . . . . . . . . . . . . . 46
14.1. Normative References . . . . . . . . . . . . . . . . . . 46
14.2. Informative References . . . . . . . . . . . . . . . . . 47
Appendix A. Example Implementation . . . . . . . . . . . . . . . 48
Appendix B. Test Cases . . . . . . . . . . . . . . . . . . . . . 57
Appendix C. Test Case Sample Output . . . . . . . . . . . . . . 68
Harvey, et al. Expires 14 June 2024 [Page 3]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
Appendix D. Change Log . . . . . . . . . . . . . . . . . . . . . 71
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . 72
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 72
1. Introduction
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.
Harvey, et al. Expires 14 June 2024 [Page 4]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
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+] (and the SLH-DSA subset specified in the
draft [FIPS 205]). 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; and (2) SPHINCS+ has a relatively large signature size and
computational cost, and therefore can benefit significantly from the
reductions offered by MTL mode;(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 specification may support other
signature schemes.
1.1. Conventions Used in This Document
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.
2. Preliminaries
2.1. Definitions
Node Set
A set of nodes, each of which is part of a union of tree
structures either as a leaf node whose value is the hash of a
single data value, or an internal node whose value is the hash of
two child nodes. The node set is acyclic, i.e., every node is
either a leaf node or the ancestor of two or more leaf nodes, and
no node is an ancestor of itself. Every node set has one or more
root nodes, i.e., nodes that have no ancestors.
Rung
A node from a node set that can be used to authenticate one or
more leaf nodes within that node set.
Ladder
A collection of one or more rungs that can be used to verify an
authentication path.
Authentication Path
The set of sibling hash values from a leaf hash value to a rung
Harvey, et al. Expires 14 June 2024 [Page 5]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
Message
A set of bytes that are intended to be signed and later verified.
2.2. Operators
Standard order of operations is assumed throughout this document.
The following mathematical operators are used:
** : a ** b denotes the value of a raised to the power of b
* : a * b denotes the product of a multiplied by b
/ : a / b denotes the quotient of a divided by b
+ : a + b denotes the sum of a and b when a and b are numbers
- : a - b denotes the difference of a and b
= : a = b denotes assigning the value of b to a
The following bitwise operators are used:
& : a & b denotes the bitwise AND of the unsigned integers a and b
| : a | b denotes the bitwise OR of the unsigned integers a and b
~ : ~a denotes the bitwise NOT of the unsigned integer a
>> : a >> i denotes a right bit shift (non-rotating) of a by i bit
positions to the right.
<< : a << i denotes a left bit shift (non-rotating) of a by i bit
positions to the left.
The following comparison operators are used:
== : a == b denotes the comparison between a and b to see if the two
values are equal
<=: a <= b denotes the comparison between a and b to see if a is less
than or equal to b
>=: a >= b denotes the comparison between a and b to see if a is
greater than or equal to b
!=: a != b denotes the comparison between a and b to see if a is not
equal to b
Harvey, et al. Expires 14 June 2024 [Page 6]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
The following array notation is used:
The notation A[i] represents the ith element of array A.
The following byte string notation is used:
+ : a + b denotes the concatenation of values a and b when a and b
are byte strings.
2.3. Functions
Given unsigned integers x and message byte strings a, b, and c 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.
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 |
+---------+----------------+-------+-------+-------------+
2.4. Algorithm Style
The data structures and algorithms defined in this document are
written to be runnable Python 3 code (a full collection of this code
is included in Appendix A). The following styles have been applied
to further make the code easy to read and follow:
* Classes and data structures are written in all uppercase (e.g.
MTLNS)
* Constant values are also written as all uppercase with _
separating words (e.g. MTL_SIG_CONDENSED)
Harvey, et al. Expires 14 June 2024 [Page 7]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
* Variables are written in all lowercase with _ separating words as
needed (e.g. left_hash or tree)
* Functions are written in all lower case and proceeded by a comment
block that highlights the input and output parameters.
3. General Model
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.
1. The signer maintains a dynamic data structure called a Merkle
node set. The leaf nodes of the node set correspond to the
messages that are being "signed" for later authentication and the
internal nodes of the node sets are the hashes of two child
nodes. Similar to a Merkle tree structure, ancestors
authenticate or "cover" their descendants. A Merkle node set is
more general than a Merkle tree in that more than one node can be
a root node (i.e., a node without ancestors). For instance, a
Merkle node set could include multiple trees.
2. As the node set evolves, the signer occasionally selects a set of
nodes from the node set that collectively cover all the leaf
nodes. Such a set is called a "ladder" and each node within the
set is called a "rung." The rungs are selected according to a
"binary rung strategy" where each rung is the root of a perfect
binary tree (see Section 6.5).
3. The signer signs each ladder with the private key of the
underlying signature scheme. The signature on the ladder is the
"MTL mode signature" of the set of messages covered by the
ladder.
4. For each message of interest to a verifier, the signer provides
the verifier a Merkle authentication path from the leaf node
corresponding to the message to a rung in the then-current
ladder. Similar to a Merkle tree structure, the authentication
path includes the sibling hashes on the path from the leaf node
to a rung on the ladder that covers the leaf node.
5. If the verifier has a ladder that is "compatible" with the
authentication path, the verifier verifies the authentication
path on the message relative to the ladder.
6. If not, the verifier requests the ladder that the authentication
path was computed relative to. (Alternatively, the verifier may
request a "full" signature on the message that includes both the
authentication path and the signed ladder that it is computed
relative to, which could be the current ladder. See Section 9.4
for a description of a full signature.)
Harvey, et al. Expires 14 June 2024 [Page 8]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
7. The signer provides the signed ladder together with its
signature. (Or, alternatively, a full signature including the
authentication path together with a signed ladder.)
8. The verifier verifies the signature on the ladder and returns to
Step 5.
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.
4. Security Parameters, Cryptographic Functions and Address Scheme
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+]. This includes
the subset of instantiations that are defined for SLH-DSA in draft
[FIPS 205]. The document also uses an extended version of the
[SPHINCS+] 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.1. The
cryptographic functions are defined in Sections 4.2, 4.3 and 4.4.
The address scheme is defined in Section 4.5.
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 specification.
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.
Harvey, et al. Expires 14 June 2024 [Page 9]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
4.1. Security parameter
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 13).
4.2. Randomized message digest function (H_msg_mtl)
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(R_mtl, PK.seed, PK.root, M) -> md maps a n-byte
randomizer, a n-byte public seed, a n-byte public root and a
variable-length message to a n-byte hash value md.
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:
* R_mtl is the randomizer for the message digest operation
* PK.seed the public seed from the public key
* PK.root is the public root from the public key
* M is the message being processed.
H_msg_mtl is used for computing data values from messages in MTL mode
(see Sections 10.1 and 10.2).
4.3. Pseudorandom function (PRF_msg)
MTL mode also makes use of pseudorandom function PRF_msg defined in
SPHINCS+:
* PRF_msg(SK.prf, OptRand, M) -> R_mtl maps a n-byte secret PRF key,
a n-byte optional random value, and a variable-length message to a
n-byte randomizer R_mtl.
The inputs to PRF_msg have the following meanings:
* SK.prf is the secret PRF key from the private key.
Harvey, et al. Expires 14 June 2024 [Page 10]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
* OptRand depends on whether an implementation wants deterministic
signing. If it does, then OptRand SHOULD be a fixed value, e.g.,
all 0s or PK.seed. (The SPHINCS+ specification suggests both
options in different places for its internal use of OptRand.) If
not, then OptRand MUST be a randomly generated value.
* M is the message being processed.
PRF_msg is used for computing randomizers for hashing messages in MTL
mode (see Section 10.1 and 10.2).
4.4. Tweakable hash functions (F and H)
MTL mode makes use of the tweakable hash functions F and H defined in
SPHINCS+:
* F(PK.seed, ADRS, M_1) -> md maps a n-byte public seed, a 32-byte
address value and a n-byte message value to a n-byte hash value
* H(PK.seed, ADRS, M_1 || M_2) -> md maps a n-byte public seed, a
32-byte address value and the concatenation of two n-byte message
values to a n-byte hash value
The inputs to F and H have the following meanings:
* PK.seed is the public seed from the public key. This value is a
"tweak" to the hash function that separates uses of the function
with different public keys (assuming different public keys have
different public seeds, as they almost always will if the public
seeds are generated at random).
* ADRS is the address associated with the call to the function.
This value is another "tweak" that separates uses of the function
for different purposes.
* M_1 (input to F) is a n-byte value being hashed.
* M_1 || M_2 (input to H) is the concatenation of two n-byte values
being hashed together.
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).
4.5. Address scheme
MTL mode extends the address scheme for function inputs defined in
SPHINCS+, adding four address types.
Harvey, et al. Expires 14 June 2024 [Page 11]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
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-19 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,
MTL_TREE and MTL_LADDER provide a descriptive alternative to the
numbers.
For all four 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.
* MTL Message Hash (type MTL_MSG = 16). This type is used in the
address value that is prepended to a message when calling PRF_msg
to compute a randomizer or when calling H_msg_mtl to compute a
data value from a message. For this type, the sixth and seventh
words MUST be 0 and the eighth word MUST be the message index
(i.e., the leaf index of the corresponding leaf node).
* MTL Data Value (type MTL_DATA = 17). This type is used when
calling F to compute a leaf node hash value from a data value.
For this type, the sixth and seventh words MUST be 0 and the
eighth word MUST be the leaf index.
* MTL Tree (type MTL_TREE = 18). This type is used when calling H
to compute an internal node hash value from two child node hash
values. For this type, the sixth word MUST be 0, the seventh word
MUST be the left index associated with the internal node and the
eighth word MUST be the right index associated with the internal
node.
* MTL Ladder (type MTL_LADDER = 19). This address type is used in
the address value that is prepended to a message when calling the
underlying signature scheme to sign a ladder. For this type, the
sixth, seventh and eighth words MUST be 0.
Harvey, et al. Expires 14 June 2024 [Page 12]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
| 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|
+----------------------+---+---+-----+-----+-----+-----+-----+
| MTL Ladder | 0 | 0 | SID | 19 | 0 | 0 | 0 |
+----------------------+---+---+-----+-----+-----+-----+-----+
Address values are represented with the ADRS class.
4.6. Cryptographic separation and message index association for
H_msg_mtl and PRF_msg
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 specification takes the following approach to achieve
cryptographic separation and message index association for calls to
H_msg and H_msg_mtl:
* When calling H_msg_mtl to compute a data value from a message, an
address value of type MTL_MSG is prepended to the message, where
the value also includes the message index
* When calling the underlying signature scheme to sign a ladder, an
address value of type MTL_LADDER is prepended to the ladder
This specification takes a comparable approach to achieve
cryptographic separation and message index association for calls to
PRF_msg.
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 MTL mode and to H_msg from SPHINCS+ will involve values of M
Harvey, et al. Expires 14 June 2024 [Page 13]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
whose first 32 bytes differ. In such a case, instantiations of
H_msg_mtl and H_msg SHOULD be chosen that support the use of these 32
bytes as a common "tweak" to both H_msg_mtl and H_msg. A comparable
observation applies to calls to PRF_msg, and instantiations of
PRF_msg SHOULD be chosen that support the use of the 32 bytes as a
tweak. Different instantiation choices may be needed for other
underlying signature schemes.
5. Computing Data Values from Messages
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+.)
5.1. Signer Operations
A MTL mode signer starts with a message M and computes a randomizer
R_mtl and a data value with the following steps.
* With deterministic hashing, let OptRand be the public seed PK.seed
* With randomized hashing, let OptRand be a random n-byte value
* Compute a randomizer by applying PRF_msg to the secret PRF key,
the optional random value and the message prepended with an
address value ADRS of type MTL_MSG as described in Section 4.5
R_mtl = PRF_msg(SK.prf, OptRand, ADRS || M)
* Compute the data value by applying H_msg_mtl to the randomizer,
the public seed, the public root and the message prepended with
the same address value
data_value = H_msg_mtl(R_mtl, PK.seed, PK.root, ADRS || M)
5.2. Verifier Operations
A MTL mode verifier starts with a message M and a randomizer R_mtl
and recomputes the data value with the last step above:
Harvey, et al. Expires 14 June 2024 [Page 14]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
* Compute the data value by applying H_msg_mtl to the randomizer,
the public seed, the public root and the message prepended with
the same address value
data_value = H_msg_mtl(R_mtl, PK.seed, PK.root, ADRS || M)
6. MTL Node Sets
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.
6.1. Seeds and Series Identifiers
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.
6.2. Node Sets
A MTL node set has zero or more nodes each of the form <L,R,V> where:
* L is the node's left index, a non-negative integer
* R is the node's right index, a non-negative integer
* V is the node's hash value
Harvey, et al. Expires 14 June 2024 [Page 15]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
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).
6.3. Leaf Nodes
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.
6.4. Internal Nodes
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:
Harvey, et al. Expires 14 June 2024 [Page 16]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
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
6.5. Ladders
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 + ... + 2^v_B
Harvey, et al. Expires 14 June 2024 [Page 17]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
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 (2^v_1,2^v_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 log2(N) rounded up to the next integer.
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.
Harvey, et al. Expires 14 June 2024 [Page 18]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
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
6.6. Authentication Paths
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.
Harvey, et al. Expires 14 June 2024 [Page 19]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
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 log2(N) rounded down to the previous
integer. The actual number is bit_width(R-L) where (L,R) is the
index pair of the rung covering the leaf node.
6.7. Backward Compatibility
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.
Harvey, et al. Expires 14 June 2024 [Page 20]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
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:
* L <= leaf_index <= R, ensuring the leaf index is covered by the
rung
* (L = 0 or degree <= lsb(L)-1) and R-L+1 = 2^degree, where degree =
lsb(R-L+1)-1, ensuring the rung is indeed an apex of a perfect
binary tree in the binary rung strategy
* lsb(R-L+1) is less than or equal to the number of sibling hash
values in the authentication path, ensuring the authentication
path can reach the rung
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.
7. Data Structures
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.
7.1. Ladder
A ladder data structure consists of four base components:
* flags, a 2-byte string providing future extensibility; the initial
value for this field MUST be 0
* sid, the series identifier, a 8-byte string
* rung_count, the number of rungs in the ladder, a positive integer
between 1 and 2^16-1
* rungs, one or more rung data structures
Harvey, et al. Expires 14 June 2024 [Page 21]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
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 //
| |
+-------------------------------+
7.2. Rung
A rung data structure consists of three base components:
* left_index, the left index of the rung, a non-negative integer
* right_index, the right index of the rung, a non-negative integer
* hash, the rung hash value, a n-byte string
The byte representation of the rung is the concatenation of the
binary encodings of the fields using big endian representation of the
integers:
Harvey, et al. Expires 14 June 2024 [Page 22]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
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 //
| |
+-------------------------------+
7.3. Authentication Path
An authentication path data structure consists of seven base
components:
* flags, a 2-byte string providing future extensibility; it MUST be
0 for this version of the specification
* sid, the series identifier, a 8-byte string
* leaf_index, the leaf index of the data value being authenticated,
a non-negative integer
* sibling_hash_count, the number of sibling hash values in the
authentication path, a non-negative integer between 0 and 2^16-1
* sibling_hashes, zero or more sibling hash values, each a n-byte
string
* rung_left, the left index of the target rung, a non-negative
integer
* rung_right, the right index of the target rung, a non-negative
integer
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:
Harvey, et al. Expires 14 June 2024 [Page 23]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
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 Node Count |
+-------------------------------+
| |
// Sibling Hash Values //
| |
+-------------------------------+
8. MTL Node Set Operations
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:
* the public seed MUST be a n-byte string
* the series identifier MUST be a 8-byte string
Harvey, et al. Expires 14 June 2024 [Page 24]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
* the various node indexes (leaf_index, left_index, right_index,
etc.) MUST be non-negative integers between 0 and 2^32-1 (so they
can be represented as 4-byte strings in big endian notation)
* the data value MUST be a n-byte string
* the various hash values (leaf_hash, left_hash, right_hash,
internal_hash, etc.) MUST be a n-byte strings
8.1. MTL Node Set Object
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.
8.2. MTL Node Set Hash Operations
As discussed in Section 6.3 and 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.
8.2.1. Hashing a Data Value to Produce a Leaf Node Hash Value
(Function: hash_leaf)
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.
Harvey, et al. Expires 14 June 2024 [Page 25]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
##################################################################
# 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
8.2.2. Hashing Two Child Nodes to Produce an Internal Node (Function:
hash_int)
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.
Harvey, et al. Expires 14 June 2024 [Page 26]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
##################################################################
# 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
8.3. Initializing a MTL Node Set (Function: mtl_initns)
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
Harvey, et al. Expires 14 June 2024 [Page 27]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
8.4. Appending a Data Value to a MTL Node Set (Function: mtl_append)
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
Harvey, et al. Expires 14 June 2024 [Page 28]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
8.5. Computing an Authentication Path (Function: mtl_authpath)
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.
Harvey, et al. Expires 14 June 2024 [Page 29]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
##################################################################
# 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
8.6. Computing the Merkle Tree Ladder for a Node Set (Function:
mtl_ladder)
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.
Harvey, et al. Expires 14 June 2024 [Page 30]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
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
8.7. Selecting a Ladder Rung (Function: mtl_rung)
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
Harvey, et al. Expires 14 June 2024 [Page 31]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
# 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
8.8. Verifying an Authentication Path (Function: mtl_verify)
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.
Harvey, et al. Expires 14 June 2024 [Page 32]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
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,
Harvey, et al. Expires 14 June 2024 [Page 33]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
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
9. Signing and Verifying Messages in MTL Mode
Descriptions of the signer's and the verifier's operations in a
typical application based on MTL mode are given in Sections 9.1 and
9.2. Section 9.3 discusses how to identify ladders to facilitate
interoperability. Representations of full and condensed MTL mode
signatures are given in Sections 9.4 and 9.5.
9.1. Signing Messages
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:
1. Generate a public / private key pair for an underlying signature
scheme, where the public key includes a public seed and a public root
and the private key includes a public seed, a public root, and a
secret PRF key.
The second step is performed once per series of messages to be
signed:
2. Initialize a node set for the series from a public seed and a
series identifier using mtl_initns.
The third and fourth steps are performed once per message to signed
in a message series:
Harvey, et al. Expires 14 June 2024 [Page 34]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
3. Compute a randomizer from the message using a pseudorandom
function, then compute a data value from the randomizer and the
message using a randomized message digest operation as described in
Section 5.1. Note that as described in Section 4.6, an address value
of type MTL_MSG MUST be prepended to the message prior to calling the
functions in this operation, where the value also includes the
message index the ladder.
4. Append the data value to the node set for the message series
using mtl_append.
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.
5. Compute the current ladder for the node set using mtl_ladder.
6. Sign the ladder using the private key of the underlying signature
scheme. Note that as described in Section 4.6, an address value of
type MTL_LADDER MUST be prepended to the ladder prior to calling the
signature operation.
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.)
7. Provide the signed ladder associated with a specified ladder
identifier.
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.
8. Compute an authentication path for the data value at a specified
message index relative to the current ladder using mtl_authpath.
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.
Harvey, et al. Expires 14 June 2024 [Page 35]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
9. Provide the authentication path and the randomizer associated
with a message to be authenticated. The signer MAY also provide an
explicit ladder identifier for the ladder that the authentication
path was computed relative to - see Section 9.3. Alternatively, the
signer may offer the option of requesting a full signature that
includes the authentication path, the randomizer and a signed ladder.
9.2. Verifying Signatures
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:
1. Obtain the signer's public key for the underlying signature
scheme, where the public key includes a public seed and a public
root.
The second, third, fourth and fifth steps is performed as needed for
each message to be authenticated:
2. Obtain the authentication path and the randomizer associated with
the message to be authenticated. The verifier MAY also obtain an
explicit ladder identifier for the ladder that the authentication
path was computed relative to - see Section 9.3.
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.
4. Re-compute a data value from a message and a randomizer using a
randomized message digest operation as described in Section 5.2.
Note that as described in Section 4.6, an address value of type
MTL_MSG MUST be prepended to the message prior to calling the
functions in this operation, where the value also includes the
message index the ladder.
5. 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.
6. 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.
Harvey, et al. Expires 14 June 2024 [Page 36]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
7. Verify the signature on the signed ladder using the public key of
the underlying signature scheme. Note that as described in
Section 4.6, an address value of type MTL_LADDER MUST be prepended to
the ladder prior to calling the verification operation.
9.3. Ladder identifiers
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:
* Identifying the ladder based on a public key identifier and
information in the authentication path itself, i.e., the series
identifier and the target index pair. This combination is
sufficient to identify the public key, the series of data values
(and thus the MTL node set), and the ladder of interest (given the
target index pair, with the binary rung strategy).
* Identifying the ladder with a URI or other explicit identifier
that refers to a location where the signed ladder is stored or to
the signed ladder itself. This URI can be conveyed together with
the authentication path in an application.
* Specifying interest in a ladder implicitly by setting a flag in
the request for a message and its associated authentication path.
When the flag is not set, the message and authentication path
would be returned (producing a condensed signature - see
Section 9.5). When the flag is set, the message, the signed
ladder is also would be returned (producing a full signature - see
Section 9.4).
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.
9.4. Full Signatures
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.
Harvey, et al. Expires 14 June 2024 [Page 37]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
A full MTL mode signature data structure consists of five base
components:
* R_mtl, the randomizer, a n-byte string
* auth_path, the authentication path
* ladder, the ladder
* sig_len, the length in bytes of the underlying signature on the
ladder, a positive integer between 1 and 2^32-1 (so it can be
represented as 4-byte string in big endian notation)
* sig, the underlying signature on the ladder, a scheme-specific
string
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 //
| |
+-------------------------------+
Harvey, et al. Expires 14 June 2024 [Page 38]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
9.5. Condensed Signatures
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 three base
components:
* R_mtl, the randomizer, a n-byte string
* auth_path, the authentication path
* ladder, the ladder
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 //
| |
+-------------------------------+
10. SPHINCS+ in MTL Mode
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 [FIPS 205].
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:
Harvey, et al. Expires 14 June 2024 [Page 39]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
* SPHINCS+-MTL-{hash}-{bitsec}{opt}-{variant}
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+]. 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+], 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+], 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.
Harvey, et al. Expires 14 June 2024 [Page 40]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
SPHINCS+-MTL Security NIST
Instantiation Parameter n Level
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-128s-simple | 16 | 1 |
| SLH-DSA-MTL-SHAKE-128s | | |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-128s-robust | 16 | 1 |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-128f-simple | 16 | 1 |
| SLH-DSA-MTL-SHAKE-128f | | |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-128f-robust | 16 | 1 |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-192s-simple | 24 | 3 |
| SLH-DSA-MTL-SHAKE-192s | | |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-192s-robust | 24 | 3 |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-192f-simple | 24 | 3 |
| SLH-DSA-MTL-SHAKE-192f | | |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-192f-robust | 24 | 3 |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-256s-simple | 32 | 5 |
| SLH-DSA-MTL-SHAKE-256s | | |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-256s-robust | 32 | 5 |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-256f-simple | 32 | 5 |
| SLH-DSA-MTL-SHAKE-256f | | |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHAKE-256f-robust | 32 | 5 |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-128s-simple | 16 | 1 |
| SLH-DSA-MTL-SHA2-128s | | |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-128s-robust | 16 | 1 |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-128f-simple | 16 | 1 |
| SLH-DSA-MTL-SHA2-128f | | |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-128f-robust | 16 | 1 |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-192s-simple | 24 | 3 |
| SLH-DSA-MTL-SHA2-192s | | |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-192s-robust | 24 | 3 |
+--------------------------------+----------------------+
Harvey, et al. Expires 14 June 2024 [Page 41]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
| SPHINCS+-MTL-SHA2-192f-simple | 24 | 3 |
| SLH-DSA-MTL-SHA2-192f | | |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-192f-robust | 24 | 3 |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-256s-simple | 32 | 5 |
| SLH-DSA-MTL-SHA2-256s | | |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-256s-robust | 32 | 5 |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-256f-simple | 32 | 5 |
| SLH-DSA-MTL-SHA2-256f | | |
+--------------------------------+----------------------+
| SPHINCS+-MTL-SHA2-256f-robust | 32 | 5 |
+--------------------------------+----------------------+
10.1. SHAKE instantiations
The SHAKE instantiations employ the SHAKE256 hash function [FIPS202].
10.1.1. Randomized message digest function (H_msg_mtl)
The randomized message digest function H_msg_mtl (see Section 4.2) 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):
H_msg_mtl(R, PK.seed, PK.root, M) = SHAKE256(R || PK.seed ||
PK.root || M, 8n)
10.1.2. Pseudorandom function (PRF_msg)
The pseudorandom function PRF_msg (see Section 4.3) is defined the
same as in SPHINCS+:
PRF_msg(SK.prf, OptRand, M) = SHAKE256(SK.prf || OptRand || M, 8n)
10.1.3. Tweakable hash functions (F and H)
The tweakable hash functions F and H (see Section 4.4) are defined
the same as in SPHINCS+. In the robust variants, they are defined as:
F(PK.seed, ADRS, M_1) = SHAKE256(PK.seed || ADRS || M_1*, 8n)
H(PK.seed, ADRS, M_1, M_2) = SHAKE256(PK.seed || ADRS ||
(M_1 ||M_2)*, 8n)
with the following notation:
Harvey, et al. Expires 14 June 2024 [Page 42]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
M_1* = M_1 xor SHAKE256(PK.seed, ADRS, 8n)
(M_1 || M_2)* = (M_1 || M_2)* xor SHAKE256(PK.seed, ADRS, 16n)
In the simple variants, they are defined as:
F(PK.seed, ADRS, M_1) = SHAKE256(PK.seed||ADRS||M_1, 8n)
H(PK.seed, ADRS, M_1, M_2) = SHAKE256(PK.seed || ADRS || M_1 || M_2,
8n)
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)*.
10.2. SHA2 instantiations
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.)
10.2.1. Randomized message digest function (H_msg_mtl)
The randomized message digest function H_msg_mtl (see Section 4.2) is
defined the same as the function H_msg in SPHINCS+ except that its
output is n bytes rather than m bytes:
H_msg_mtl(R, PK.seed, PK.root, M) = MGF1-SHA-X(R || PK.seed || SHA-
X(R || PK.seed || PK.root || M), n).
10.2.2. Pseudorandom function (PRF_msg)
The pseudorandom function PRF_msg (see Section 4.3) is defined the
same as in SPHINCS+:
PRF_msg(SK.prf, OptRand, M) = HMAC-SHA-X(SK.prf, OptRand || M)
Harvey, et al. Expires 14 June 2024 [Page 43]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
10.2.3. Tweakable hash functions (F and H)
The tweakable hash functions F and H (see Section 4.4) are defined
the same as in SPHINCS+. In the robust variants, they are defined as:
F(PK.seed, ADRS, M_1) = SHA2-256(BlockPad(PK.seed) || ADRS^c || M_1*)
H(PK.seed, ADRS, M_1, M_2) = SHA-X(BlockPad(PK.seed) || ADRS^c ||
(M_1 ||M_2)*)
with the following notation:
BlockPad(PK.seed) = PK.seed || toByte(0, bl-n) where bl=64 for
SHA2-256 and bl=128 for SHA-512.
ADRS^c is a 22-byte "compressed" version of the address value that
omits bytes 1-3, 5-8 and 21-23. (In MTL mode, the omitted bytes are
all zeros because the address type is one byte long - see
Section 3.4.)
M_1* = M_1 xor MGF1-SHA-X(PK.seed, ADRS, 8n)
(M_1 || M_2)* = (M_1 || M_2)* xor MGF1-SHA-X(PK.seed, ADRS, 16n)
In the simple variants, they are defined as:
F(PK.seed, ADRS, M_1) = SHA2-256(BlockPad(PK.seed) || ADRS^c || M_1)
H(PK.seed, ADRS, M_1, M_2) = SHA-X(BlockPad(PK.seed) || ADRS^c ||
(M_1 ||M_2))
11. Related Work
The binary rung strategy appears under different names in other
cryptographic constructions based on Merkle trees. Champine defines
a binary numeral tree [BIN-NUM-TREES] with similar structure (the
successive perfect binary subtrees are called eigentrees). Other
similarMerkle tree-based constructions include Crosby and Wallach's
history trees [HISTORY-TREE] and Todd's Merkle mountain ranges
[MERKLE_MOUNTAIN],
and Reyzin and Yakoubov's cryptographic accumulator [CRYPTO-ACC],
which achieves an "old-accumulator compatibility" property comparable
to the backward compatibility property described here for the binary
rung strategy.
Harvey, et al. Expires 14 June 2024 [Page 44]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
Certificate transparency logs take advantage of Merkle trees to show
the existence or non-existence of a certificate as published by a
certification authority [RFC9162]. Benjamin, O'Brien, and Westerbaan
[MERKLETREECERTS] propose using authentication paths to a limited
lifetime Merkle tree produced by a certificate transparency service
as certificate signatures. Each Merkle tree is constructed over a
fixed time window in this approach, and the authentication paths are
constructed relative to the single root of the Merkle tree, which is
like a single-rung Merkle tree ladder.
12. IANA Considerations
This document makes no requests of IANA. However, a future version
of this document may request that IANA register flag values for the
ladder and authentication path data structures. A future version may
also request that IANA register the address types MTL_MSG, MTL_DATA,
MTL_TREE and MTL_LADDER. Because the address types use 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.
13. Security Considerations
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 cryptographic separation between interaction
between MTL mode's uses of cryptographic functions and the use of
cryptographic functions by the underlying signature scheme. 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.
Harvey, et al. Expires 14 June 2024 [Page 45]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
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.
14. References
14.1. Normative References
[FIPS180-4] "Secure Hash Standard (SHS)", National Institute of
Standards and Technology, FIPS PUB 180-4, DOI 10.6028/
NIST.FIPS.180-4, August 2015.
[FIPS198-1] " The Keyed-Hash Message Authentication Code (HMAC)",
National Institute of Standards and Technology, FIPS PUB 198-1, DOI
10.6028/NIST.FIPS.198-1, July 2008.
[FIPS186-4] "Digital Signature Standard (DSS)", National Institute of
Standards and Technology, FIPS PUB 186-4, DOI 10.6028/
NIST.FIPS.186-4, July 2013.
[FIPS202] "SHA-3 Standard: Permutation-Based Hash and Extendable-
Output Functions", National Institute of Standards and Technology,
FIPS PUB 202, DOI 10.6028/NIST.FIPS.202, August 2015.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March
1997, ,https://www.rfc-editor.org/info/rfc2119.
[RFC8017] Moriarty, K., Kaliski, B., Jonsson, J., Rusch, A., "PKCS
#1: RSA Cryptography Specifications Version 2.2", RFC 8017, DOI
10.17487/RFC8017, November 2016, https://www.rfc-editor.org/info/
rfc8017.
[RFC4086] Eastlake, D., Schiller, J., Crocker, S., "Randomness
Requirements for Security", BCP 106, RFC 4086, DOI 10.17487/RFC4086,
June 2005, https://www.rfc-editor.org/info/rfc4086.
Harvey, et al. Expires 14 June 2024 [Page 46]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119
Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017,
https://www.rfc-editor.org/info/rfc8174.
14.2. Informative References
[HARAKA] Kolbl, S., Lauridsen, L., Mendel, F., Rechberger, C.,
"Haraka v2 - Efficient Short-Input Hashing for Post-Quantum
Applications", in IACR Transactions on Symmetric Cryptology volume
2016, number 2, pages 1-29, DOI 10.13154/tosc.v2016.i2.1-29, 2017.
[MTL-MODE] Fregly, A., Harvey, J. Kaliski, B., Sheth, S., "Merkle
Tree Ladder Mode: Reducing the Size Impact of NIST PQC Signature
Algorithms in Practice", in Rosulek, M. (editor), Lecture Notes in
Computer Science, volume 13871, CT-RSA 2023 - Cryptographers Track at
the RSA Conference, pages 415-441, DOI 10.1007/978-3-031-30872-7_16,
Springer, 2023. Preliminary version available at
https://eprint.iacr.org/2022/1730.pdf.
[RFC4033] Arends, R., Austein, R., Larson, M., Massey, D., Rose, S.,
"DNS Security Introduction and Requirements", RFC 4033, DOI 10.17487/
RFC4033, March 2005, https://www.rfc-editor.org/info/rfc4033.
[RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S.,
Housley, R., Polk, W., "Internet X.509 Public Key Infrastructure
Certificate and Certificate Revocation List (CRL) Profile", RFC 5280,
DOI 10.17487/RFC5280, May 2008. https://www.rfc-editor.org/info/
rfc5280.
[RFC8446] Rescorla, E., "The Transport Layer Security Protocol
Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018,
https://www.rfc-editor.org/info/rfc8446.
[RFC9162] Laurie, B., Messeri, E., Stradling, R., "Certificate
Transparency Version 2.0", December 2021, RFC 9162, DOI 10.17487/
RFC9162, https://www.rfc-editor.org/info/rfc9162.
[FIPS205] "Stateless Hash-Based Digital Signature Standard Draft",
National Institute of Standards and Technology, FIPS PUB 205, DOI
10.6028/NIST.FIPS.205, August 2023.
[SPHINCS+] Aumasson, J., Bernstein, D., Beullens, W., et al. ,
"SPHINCS+ - Submission to the NIST post-quantum project, v3.1", June
10, 2022, https://sphincs.org/data/sphincs+-r3.1-specification.pdf.
[BIN-NUM-TREES] Champine,L.,"Streaming Merkle Proofs within Binary
Numeral Trees", Cryptology ePrint Archive, Paper 2021/038.
https://eprint.iacr.org/2021/038.
Harvey, et al. Expires 14 June 2024 [Page 47]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
[HISTORY-TREE] Crosby, S., Wallach, D., "Efficient data structures
for tamper-evident logging", Proceedings of the 18th USENIX Security
Symposium, pp. 317-334. USENIX Association (2009).
https://dl.acm.org/doi/abs/10.5555/1855768.1855788.
[MERKLE_MOUNTAIN] Todd, P., "Merkle Mountain Ranges",
https://github.com/opentimestamps/opentimestamps-
server/blob/master/doc/merkle-mountain-range.md.
[CRYPTO-ACC] Reyzin, L., Yakoubov, S., "Efficient asynchronous
accumulators for distributed PKI.", Zikas, V., De Prisco, R. (eds)
Security and Cryptography for Networks, SCN 2016, LNCS, vol. 9841,
pp. 292-309. Springer, Cham, 2016.
https://doi.org/10.1007/978-3-319-44618-9_16.
[MERKLETREECERTS] Benjamin, D., O'Brien, D., and B. Westerbaan,
"Merkle Tree Certificates for TLS", Work in Progress, Internet-Draft,
draft-davidben-tls-merkle-tree-certs-00, 10 March 2023,
https://datatracker.ietf.org/doc/html/draft-davidben-tls-merkle-tree-
certs-00.
Appendix A. Example Implementation
MTL Mode Algorithms Sample Implementation
The algorithms outlined in this document are provided as a complete
Python script. The generic code only stubs out any underlying
signature scheme and the hashing functions are for illustration
purposes only. The outputs from the functions are objects instead of
the defined byte strings to make the code flows easier to read and
experiment with.
-------------------------- mtl.py --------------------------------
"""
This is a collection of the algorithms defined in the Merkle Tree
Ladder Mode (MTL) Signatures specification. Helping functions
(like rand, lsb, msb, bit_width) are also provided to ensure
the algorithms work.
"""
import spx
from math import sqrt
from hashlib import sha256
from secrets import token_bytes
import sys
import hmac
import time
Harvey, et al. Expires 14 June 2024 [Page 48]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
#################################################################
# Definitions of helping functions used in algorithms
#################################################################
# Input: Node Id
# Output: Number of 1 bits in a number
def bit_width(index):
return bin(index).count("1")
# Input: Node Id
# Output: Least significant bit position
def lsb(index):
return int(index & -index).bit_length()
# Input: Node Id
# Output: Most significant bit position
def msb(index):
return index.bit_length()
# Input: Byte string to pad
# Output: Padded string that uses the len value for the pad
def block_pad(value):
block_size=32
padding_size = (block_size - len(value) % block_size)
padding_value = chr(padding_size)
pad = value + bytes((padding_value * padding_size), 'utf-8')
return pad
#################################################################
# MTL Data Structures
#################################################################
################################################################
# Data Structure 1: MTL Ladder Declaration
################################################################
class MTL_LADDER:
def __init__(self, flags, sid, rungs=[]):
self.flags = flags
self.sid = sid
self.rung_count = len(rungs)
self.rungs = rungs
def bytes(self):
buffer = self.flags.to_bytes(2,'big')
buffer += self.sid[:8]
buffer += self.rung_count.to_bytes(2,'big')
for rung in self.rungs:
Harvey, et al. Expires 14 June 2024 [Page 49]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
buffer += rung.bytes()
return buffer
################################################################
# Data Structure 2: MTL Ladder Rung Declaration
################################################################
class RUNG:
def __init__(self, left_index, right_index, hash):
self.left_index = left_index
self.right_index = right_index
self.hash = hash
def bytes(self):
buffer = self.left_index.to_bytes(4,'big')
buffer += self.right_index.to_bytes(4,'big')
buffer += self.hash
return buffer
################################################################
# Data Structure 3: MTL Authentication Path Declaration
################################################################
class MTL_AUTH_PATH:
def __init__(self, flags, leaf_index, sid, sibling_hash,
rung_left, rung_right):
self.flags = flags
self.sid = sid
self.leaf_index = leaf_index
self.rung_left = rung_left
self.rung_right = rung_right
self.sibling_hash_count = len(sibling_hash)
self.sibling_hash = sibling_hash
def bytes(self):
buffer = self.flags.to_bytes(2,'big')
sid_value = self.sid
if(len(sid_value) < 8):
sid_value += b'\x00' * (8 - len(sid_value))
buffer += sid_value[:8]
buffer += self.leaf_index.to_bytes(4,'big')
buffer += self.rung_left.to_bytes(4,'big')
buffer += self.rung_right.to_bytes(4,'big')
buffer += self.sibling_hash_count.to_bytes(2,'big')
buffer += b''.join(self.sibling_hash)
return buffer
Harvey, et al. Expires 14 June 2024 [Page 50]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
##################################################################
# Data Structure 4: MTL Node Set Declaration.
##################################################################
class MTLNS:
def __init__(self, seed, sid):
self.seed = seed
self.sid = sid
self.count = 0
self.hashes = {}
##################################################################
# Data Structure 5: Full MTL Mode Signature Declaration
##################################################################
class MTL_SIG:
def __init__(self, R_mtl, auth, ladder, sig):
self.R_mtl = R_mtl
self.auth = auth
self.ladder = ladder
self.siglen = len(sig)
self.sig = sig
def bytes(self):
buffer = self.R_mtl
buffer += self.auth.bytes()
buffer += self.ladder.bytes()
buffer += self.siglen.to_bytes(4,'big')
buffer += self.sig
return buffer
##################################################################
# Data Structure 6: Condensed MTL Mode Signature Declaration
##################################################################
class MTL_CONDENSED_SIG:
def __init__(self, R_mtl, auth):
self.R_mtl = R_mtl
self.auth = auth
def bytes(self):
buffer = self.R_mtl
buffer += self.auth.bytes()
return buffer
#################################################################
Harvey, et al. Expires 14 June 2024 [Page 51]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
# MTL Algorithms
#################################################################
##################################################################
# Algorithm 1: Hashing a Data Value to Produce a Leaf Node.
##################################################################
# Input: seed, seed value 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
##################################################################
# Algorithm 2: Hashing Two Child Nodes to Produce an Internal Node.
##################################################################
# Input: seed, seed value for the node set (associated with
# public key)
# Input: sid, series identifier for the node set
# Input: left_index, left part of the internal node index pair
# Input: right_index, right part of the internal node index pair
# 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
##################################################################
Harvey, et al. Expires 14 June 2024 [Page 52]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
# Algorithm 3: Initializing a MTL Node Set.
##################################################################
# Input: seed, seed value for this node set (associated with
# public key)
# Input: sid, series identifier for this node set
# Output: node_set, new MTL node set object
def mtl_initns(seed, sid):
node_set = MTLNS(seed, sid)
return node_set
##################################################################
# 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
##################################################################
# 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
Harvey, et al. Expires 14 June 2024 [Page 53]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
# 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
##################################################################
# 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
Harvey, et al. Expires 14 June 2024 [Page 54]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
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 ladder
##################################################################
# 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 auth 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
Harvey, et al. Expires 14 June 2024 [Page 55]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
(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
##################################################################
# 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,
Harvey, et al. Expires 14 June 2024 [Page 56]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
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
Appendix B. Test Cases
These test cases are designed to prove the concepts and give examples
for how things can be done with MTL mode based on the code from
Appendix A.
-------------------------- spx.py --------------------------------
"""
This is a stub implementation of SPHINCS+ underlying
signature functions to demonstrate how MTL mode
with underlying SPHINCS+ signatures would work.
These classes and functions should be replaced
with actual implementations.
"""
from hashlib import sha256
from secrets import token_bytes
import sys
import hmac
import time
# Property that come from the underlying schemes
# Use non-deterministic hashing
RANDOMIZE = False
# Number of bytes in the hashing function
n = 32
# Define this so that the algorithm code is easy to read.
# Since this overrides the default rand, it should be
# replaced in the code for any real experimentation
# to avoid any conflicts
def rand(n):
return token_bytes(n)
##################################################
Harvey, et al. Expires 14 June 2024 [Page 57]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
# SPX Placeholder Functions: Created for the test
# code. To be replaced by actual underlying
# SPHINCS+ or other scheme implementations
##################################################
class SPX_SK:
def __init__(self, seed, prf, pk_seed, pk_root):
self.seed = seed
self.prf = prf
self.pk_seed = pk_seed
self.pk_root = pk_root
class SPX_PK:
def __init__(self, seed, root):
self.seed = seed
self.root = root
# This function doesn't compute the root but uses random data
# TODO: Replace the code in this stub with the actual calls
# to use SPHINCS+
def spx_keygen():
PK = SPX_PK(rand(n),rand(n))
SK = SPX_SK(rand(n),rand(n),PK.seed, PK.root)
return SPXKEY(SK,PK)
# Signing doesn't actually use a SPHINCS+ signature, but instead
# hashes the data for compactness
# TODO: Replace the code in this stub with the actual calls
# to use SPHINCS+
def spx_sign(M, SK):
data_value = sha256()
data_value.update(M)
return data_value.digest()
# Signing doesn't actually verify a SPHINCS+ signature, but instead
# hashes the data for compactness
# TODO: Replace the code in this stub with the actual calls
# to use SPHINCS+
def spx_verify(M, sig, PK):
m = sha256()
m.update(M)
digest = m.digest()
return digest == sig
# Stub for the prf function
# TODO: Replace the code in this stub with the actual calls
# to use SPHINCS+
Harvey, et al. Expires 14 June 2024 [Page 58]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
def prf_msg(prf, opt, message):
m = opt + message
return hmac.new(prf, m, sha256).digest()
# Stub for the F function
# TODO: Replace the code in this stub with the actual calls
# to use SPHINCS+
def F(seed, dataADRS, data_value):
m = sha256()
m.update(block_pad(seed[:32]))
m.update(dataADRS)
m.update(data_value)
return m.digest()
# Stub for the H function
# TODO: Replace the code in this stub with the actual calls
# to use SPHINCS+
def H(seed, mtlnsADRS, left_hash, right_hash):
m = sha256()
m.update(block_pad(seed[:32]))
m.update(mtlnsADRS)
m.update(left_hash)
m.update(right_hash)
return m.digest()
# Stub for the hash message
# TODO: Replace the code in this stub with the actual calls
# to use SPHINCS+
def h_mtl_msg(R, pkseed, pkroot, message):
m = sha256()
m.update(R)
m.update(pkseed)
m.update(pkroot)
m.update(message)
msg = m.digest()
# Should be MGF1-SHA-256 - TODO
h = sha256()
h.update(R)
h.update(pkseed)
h.update(msg)
return h.digest()
class SKMTL:
Harvey, et al. Expires 14 June 2024 [Page 59]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
def __init__(self, sk, mtlns):
self.sk = sk
self.mtlns = mtlns
class SPXKEY:
def __init__(self, sk, pk):
self.sk = sk
self.pk = pk
class SPXMTLLADDER:
def __init__(self, ladder, sig):
self.ladder = ladder
self.sig = sig
def bytes(self):
return self.ladder.bytes() + self.sig
class ADRS:
MTL_MSG = 16
MTL_DATA = 17
MTL_TREE = 18
MTL_LADDER = 19
layer_addr = b'\x00\x00\x00\x00'
tree_addr = b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
addr_type = b'\x00\x00\x00\x00'
addr1 = b'\x00\x00\x00\x00'
addr2 = b'\x00\x00\x00\x00'
addr3 = b'\x00\x00\x00\x00'
def setType(self, atype):
self.addr_type = atype.to_bytes(4, 'big')
def setMessageId(self, msgid):
self.addr3 = msgid.to_bytes(4, 'big')
def setLeafIndex(self, leaf_index):
self.addr2 = leaf_index.to_bytes(4, 'big')
self.addr3 = leaf_index.to_bytes(4, 'big')
def setLeftRightIndexes(self, left_index, right_index):
self.addr2 = left_index.to_bytes(4, 'big')
self.addr3 = right_index.to_bytes(4, 'big')
def setSID(self, sid):
if(len(sid) < 8):
sid += b'\x00' * (8 - len(sid))
self.tree_addr = sid[:8]
Harvey, et al. Expires 14 June 2024 [Page 60]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
def bytes(self):
return b''.join([self.layer_addr,self.tree_addr,
self.addr_type,self.addr1,self.addr2,self.addr3])
# Input: Byte string to pad
# Output: Padded string that uses the len value for the pad
def block_pad(value):
block_size=32
padding_size = (block_size - len(value) % block_size)
padding_value = chr(padding_size)
pad = value + bytes((padding_value * padding_size), 'utf-8')
return pad
------------------------- mtl_test.py -------------------------------
"""
pytest harness for verifying the MTL algorithms with an underlying
SPHINCS+ signature API.
"""
import mtl
import spx
from textwrap import wrap
from secrets import token_bytes
from hashlib import sha256
import hmac
SID = b'0123456789012345'
good_msg = "Test Message".encode('utf-8')
bad_msg = "Invalid Message".encode('utf-8')
# Define this so that the algorithm code is easy to read.
# Since this overrides the default rand, it should be
# replaced in the code for any real experimentation
# to avoid any conflicts
def rand(n):
return token_bytes(n)
#################################################################
# Functions to print data structures to see what is happening
#################################################################
def print_node_set(node_set):
max_width = 0
print("=== MTL Node Set =======================")
for left_index, right_index in node_set.hashes:
if max_width < (right_index-left_index):
max_width = right_index-left_index
for left_index, right_index in node_set.hashes:
Harvey, et al. Expires 14 June 2024 [Page 61]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
print(f"({left_index},{right_index})")
print(f" {node_set.hashes[(left_index, right_index)].hex()}")
def print_ladder(ladder):
print("=== MTL Ladder =======================")
for rung in ladder.rungs:
print(f"({rung.left_index},{rung.right_index})")
print(f" {rung.hash.hex()}")
def print_signature(sig):
print("=== MTL Signature =======================")
for segment in wrap(sig.bytes().hex(), 64):
print(f"{segment}")
#################################################################
# Consolidated functions
#################################################################
##################################################################
# SPHINCS+-MTLi Key Pair Generation
##################################################################
# Output: SPXKEY, a key object with the SPHINCS+ secret key and
# MTL node set along with the SPHINCS+ Public Key
def spx_mtl_keygen():
# Generate SPHINCS+ key pair
spxkey = spx.spx_keygen()
# Form series identifier consisting of all 0s and initialize
# MTL node set with this series identifier
sid = b'\x00' * 8
node_set = mtl.mtl_initns(spxkey.pk.seed, sid)
# Form and return SPHINCS+ key pair
return spx.SPXKEY(spx.SKMTL(spxkey.sk, node_set), spxkey.pk)
#################################################################
# SPHINCS+-MTLi Message Series Append
#################################################################
# Input: M, message to be signed
# Input: SK_mtl, SPHINCS+-MTLi private key that contains a SPHINCS+
# private key SK (including SK.seed, SK.prf, PK.seed, PK.root)
# and a MTL node set node_set (updated in place)
# # Output: MTL record index (mtl_leaf_index, randomizer_mtl)
def spx_mtl_append(M, SK_mtl):
leaf_index = SK_mtl.mtlns.count
mtlADRS = spx.ADRS()
mtlADRS.setType(spx.ADRS.MTL_MSG)
mtlADRS.setSID(SK_mtl.mtlns.sid)
Harvey, et al. Expires 14 June 2024 [Page 62]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
mtlADRS.setMessageId(leaf_index)
# Choose the public seed as input to the randomized message
# digest operation for deterministic hashing, or generate a
# random value for randomized hashing
opt = SK_mtl.sk.pk_seed
if spx.RANDOMIZE:
opt = rand(n)
randomizer_mtl = spx.prf_msg(SK_mtl.sk.prf, opt,
mtlADRS.bytes() + M)
data_value = spx.h_mtl_msg(randomizer_mtl,
SK_mtl.sk.pk_seed,
SK_mtl.sk.pk_root, M)
# Add the M hash to the mtl node set
mtl_leaf_index = mtl.mtl_append(data_value, SK_mtl.mtlns)
return mtl_leaf_index, randomizer_mtl
##################################################################
# SPHINCS+-MTLi Signature Generation
##################################################################
# Input: M, message to be signed
# Input: SK_mtl, SPHINCS+-MTLi private key that contains a SPHINCS+
# private key SK (including SK.seed, SK.prf, PK.seed, PK.root)
# and a MTL node set node_set (updated in place)
# Output: sig_spx_mtl, SPHINCS+-MTL signature = (randomizer_mtl,
# auth_path, ladder, sig_spx)
def spx_mtl_sign(M, SK_mtl):
# Add the message to the MTL node set
mtl_leaf_index, randomizer_mtl = spx_mtl_append(M, SK_mtl)
auth_path = mtl.mtl_authpath(mtl_leaf_index, SK_mtl.mtlns)
ladder = mtl.mtl_ladder(SK_mtl.mtlns)
# Sign the ladder with the MTL tree address
sepADRS = spx.ADRS()
sepADRS.setType(spx.ADRS.MTL_LADDER)
sepADRS.setSID(SK_mtl.mtlns.sid)
signature = spx.spx_sign(sepADRS.bytes() + ladder.bytes(),
SK_mtl.sk)
sig_spx_mtl = mtl.MTL_SIG(randomizer_mtl, auth_path,
ladder, signature)
return sig_spx_mtl
Harvey, et al. Expires 14 June 2024 [Page 63]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
##################################################################
# SPHINCS+-MTL Signature Verification
##################################################################
# Input: M, Message to verify
# Input: signature, Signature to use for verification
# Input: PK that corresponds to the secret key from the signed
# message
# Output: Boolean if signature verifies correctly
def spx_mtl_verify(M, signature, PK):
data_value = spx.h_mtl_msg(signature.R_mtl, PK.seed, PK.root, M)
sepADRS = spx.ADRS()
sepADRS.setSID(signature.auth.sid)
sepADRS.setType(spx.ADRS.MTL_LADDER)
# Verify the SPHINCS+ signature on the ladder
if(spx.spx_verify(sepADRS.bytes() + signature.ladder.bytes(),
signature.sig, PK)):
# Verify the MTL authentication path
ladder_rung = mtl.mtl_rung(signature.auth, signature.ladder)
if(mtl.mtl_verify(PK.seed, data_value, signature.auth,
ladder_rung)):
return True
return False
#################################################################
# Test Functions
#################################################################
##################################################################
# Test 1: Sign and verify a single message
##################################################################
def test_sign_message():
# Generate a key set for MTL plus the stubbed SPHINCS+
spxkey = spx_mtl_keygen()
# Sign the message using MTL and the underyling secret key
sig = spx_mtl_sign(good_msg,spxkey.sk)
# Verify the message signature
assert(spx_mtl_verify(good_msg,sig,spxkey.pk))
# Check that a different message doesn't work
assert(not spx_mtl_verify(bad_msg,sig,spxkey.pk))
# Show the resulting data structures (requires pytest -s)
print(f"\n>>> Message ID {sig.auth.leaf_index}")
print_node_set(spxkey.sk.mtlns)
print_ladder(sig.ladder)
print_signature(sig)
Harvey, et al. Expires 14 June 2024 [Page 64]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
##################################################################
# Test 2: Sign and verify multiple messages, one at a time
##################################################################
def test_sign_messages_incremental():
# Setup how many messages should be tested
test_message_count = 15
# Generate a key set for MTL plus the stubbed SPHINCS+
spxkey = spx_mtl_keygen()
# Test Signing Multiple Messages
for node in range(0,test_message_count):
# Create the message to sign
message = f"Test Message {node}".encode('utf-8')
# Sign the message w/MTL and the underyling secret key
sig = spx_mtl_sign(message,spxkey.sk)
# Verify the message signature
assert(spx_mtl_verify(message,sig,spxkey.pk))
# Check for fail with different message
assert(not spx_mtl_verify(bad_msg,sig,spxkey.pk))
# Show the resulting data structures (requires pytest -s)
print(f"\n>>> Message ID {sig.auth.leaf_index}")
print_node_set(spxkey.sk.mtlns)
print_ladder(sig.ladder)
print_signature(sig)
##################################################################
# Test 3: Sign and verify multiple messages as a batch
# Only performs underlying signature one time
##################################################################
def test_sign_verify_multi_record_batch():
# Setup how many messages should be tested
test_message_count = 1024
# Not using non-deterministic hashing for this test
signatures = {}
mtl_leaf_list = []
# Generate a key set for MTL plus the stubbed SPHINCS+
spxkey = spx_mtl_keygen()
# Initalize a new node set - the node set must be
# kept separately since
node_set = mtl.mtl_initns(SID, spxkey.pk.seed)
# Add messages to the MTL node set
Harvey, et al. Expires 14 June 2024 [Page 65]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
for node in range(0,test_message_count):
# Create the message to sign
message = f"Test Message {node}".encode('utf-8')
# Add the message to the MTL node set
mtl_leaf_list.append(spx_mtl_append(message, spxkey.sk))
# Fetch the ladder that represents all the batch messages
ladder = mtl.mtl_ladder(spxkey.sk.mtlns)
# Sign the ladder with the MTL tree address
sep_addr = spx.ADRS()
sep_addr.setType(spx.ADRS.MTL_LADDER)
sep_addr.setSID(spxkey.sk.mtlns.sid)
signature = spx.spx_sign(sep_addr.bytes() + ladder.bytes(),
spxkey.sk.sk)
# Get the authentication path for each message
for leaf in mtl_leaf_list:
leaf_index, rtml = leaf
message = f"Test Message {leaf_index}".encode('utf-8')
auth_path = mtl.mtl_authpath(leaf_index, spxkey.sk.mtlns)
# Save the signatures for later to be verified
signatures[message] = mtl.MTL_SIG(rtml, auth_path, ladder,
signature)
# Verify the authentication path for each message
for sig_set in signatures:
# Verify the message signature
assert(spx_mtl_verify(sig_set, signatures[sig_set],
spxkey.pk))
# Check for fail with different message
assert(not spx_mtl_verify(bad_msg, signatures[sig_set],
spxkey.pk))
##################################################################
# Test 4: Sign a message set and condense the last signature
##################################################################
def test_condense_incremental_signature():
# Setup how many messages should be tested
test_message_count = 1024
# Generate a key set for MTL plus the stubbed SPHINCS+
spxkey = spx_mtl_keygen()
# Create a set of records
for node in range(0,test_message_count):
# Create the message to sign
Harvey, et al. Expires 14 June 2024 [Page 66]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
message = f"Test Message {node}".encode('utf-8')
# Sign the message w/MTL and the underyling secret key
sig = spx_mtl_sign(message,spxkey.sk)
# Get the condensed signature for the last message
mtl_auth_condensed = mtl.MTL_CONDENSED_SIG(sig.R_mtl, sig.auth)
# Fetch the ladder for the condensed signature
mtl_spx_ladder = spx.SPXMTLLADDER(sig.ladder, sig.sig)
# Print out the resulting signature information and the lengths
print(f"\n ===== Full Signature (len {len(sig.bytes())})" +
f" w/fake underlying signature ============")
for segment in wrap(sig.bytes().hex(), 64):
print(f" {segment}")
print(" Note: Underlying signature is a stub (SHA256 hash).")
print(" Remove 32 bytes and add signature bytes to compare")
print(f"\n ===== Condensed Path " +
f"(len {len(mtl_auth_condensed.bytes())})" +
f" ========================================")
for segment in wrap(mtl_auth_condensed.bytes().hex(), 64):
print(f" {segment}")
print(f"\n ===== Signed Ladder " +
f"(len {len(mtl_spx_ladder.bytes())})" +
f" w/fake underlying signature =============")
for segment in wrap(mtl_spx_ladder.bytes().hex(), 64):
print(f" {segment}")
print(" Note: Underlying signature is a stub (SHA256 hash).")
print(" Remove 32 bytes and add signature bytes to compare")
##################################################################
# Test 5: Sign a message set, condense and then reconstitute
# the last signature
##################################################################
def test_reconstitute_incremental_signature():
# Setup how many messages should be tested
test_message_count = 1024
# Generate a key set for MTL plus the stubbed SPHINCS+
spxkey = spx_mtl_keygen()
# Create a set of records
for node in range(0,test_message_count):
# Create the message to sign
message = f"Test Message {node}".encode('utf-8')
# Sign the message w/MTL and the underyling secret key
Harvey, et al. Expires 14 June 2024 [Page 67]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
sig = spx_mtl_sign(message,spxkey.sk)
# Get the condensed signature for the last message
mtl_auth_condensed = mtl.MTL_CONDENSED_SIG(sig.R_mtl, sig.auth)
# Fetch the ladder for the condensed signature
mtl_spx_ladder = spx.SPXMTLLADDER(sig.ladder, sig.sig)
# Reconstitute the last message with the auth path and ladder
# Note: Assuming the handle points to the condensed ladder.
# In a real scenario the handle should be used to ensure
# an appropriate ladder is used.
reconstituted_sig = mtl.MTL_SIG(mtl_auth_condensed.R_mtl,
mtl_auth_condensed.auth, mtl_spx_ladder.ladder,
mtl_spx_ladder.sig)
# Verify the message signature
assert(spx_mtl_verify(message,reconstituted_sig,spxkey.pk))
# Check for fail with different message
assert(not spx_mtl_verify(bad_msg,reconstituted_sig,spxkey.pk))
print(f"\n ===== Reconstituted Signature (len " +
f"{len(reconstituted_sig.bytes())})" +
f" w/fake underlying signature ====")
for segment in wrap(reconstituted_sig.bytes().hex(), 64):
print(f" {segment}")
print(" Note: Underlying signature is a stub (SHA256 hash).")
print(" Remove 32 bytes and add signature bytes to compare")
Appendix C. Test Case Sample Output
>>> Message ID 0
=== MTL Node Set =======================
(0,0)
af7d4a1bea359d3a578a846ec2bf0e69c34f8833d7332ae32e0b82997baa90b8
=== MTL Ladder =======================
(0,0)
af7d4a1bea359d3a578a846ec2bf0e69c34f8833d7332ae32e0b82997baa90b8
=== MTL Signature =======================
260f918fc224f074761e4c4adeb7d8bdf4b26cd6d6ebc9e500d5a824e338b189
0000000000000000000000000000000000000000000000000000000000000000
000000010000000000000000af7d4a1bea359d3a578a846ec2bf0e69c34f8833
d7332ae32e0b82997baa90b800000020148f0a787c2128f51630c1247acf528a
bc0ad11d9f9976cb7cd2e4e34ac11dd8
>>> Message ID 14
=== MTL Node Set =======================
(0,0)
Harvey, et al. Expires 14 June 2024 [Page 68]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
90885ec41541d80b9d2321a89ba22aaac24bfd83983629e4f6321e6fd73971a8
(1,1)
6bb46cc9a692ec32d85d3056fda670f047dac054278c47fa58a9d85f3a8c3ab6
(0,1)
ab79f7f0b68baef5bd2a88adda4986d37dea0dc623c467052d54bfda15dcdd50
(2,2)
08cc36404c05451bb359c19274f3490cf699fa3821f6fa1d22d2391e781dbc5d
(3,3)
dfa0847ab4f3fe5cf8c90accd345aaa1b39f7a805ef7151ee3f60a2dcb39deb4
(2,3)
ccca3f26e19bfe8ff8ca0ecdd387ad77d4b7550bca47be2c6ce7cf311b14b6bb
(0,3)
b0b956ccdf9376abb65c2de4adb32b2002685a76470d6f837bf9acf3e67a16cf
(4,4)
e9a7f5152c904579d13961f224e5079f750ce5b854cf1864c17c4de19a2fb7f0
(5,5)
c90fff55c43f55087d0509d81a7bf235ed172c49760b3aef0e77723e88277ca8
(4,5)
402b3fd5c8d9f508823b9ae595cfa4fb484b634bff00907e84c836c325618071
(6,6)
e921e204e4859007641025ad493f5155b21a8143aca65a2167c150cf502d5061
(7,7)
a555767ca23936b57a399fe60870118f634b59f72f342f5a926f7e8fb24ed18f
(6,7)
070a5fb7cc11819459cf42cb856083bbb89b1323cdada7c0a1fe6923fd8d2ddd
(4,7)
b1eef8a3a285a5a53ba5c3338839f645407bdd2a199e8db4d5064fc0ab005f38
(0,7)
f6c4315a7824ffc2fdbb2734a701782e4ae4b3cc51bd985cf8e38e6bd6cf1f71
(8,8)
76a4e1eb3a6704f89482edd395a3cb6b518b9c135c0f3e2dd33e15ec03a15195
(9,9)
65dd60329127f06362b8ac19f07973dd672f06cfdca7cd08634e44ee2bfbe12f
(8,9)
38d7fa56eff168a91d358bf4a7b7192ee0f0fe6f77914020b8e876224a73efef
(10,10)
1db3087f33ee86aeaa9458e3b3e85b17e7b08b05ffecac5b5a7ad85d4c902d0f
(11,11)
54c82d5529593ee9bc571d15b47c05e500bfe74be787996115bbf61008f8480d
(10,11)
9bd9256c9053aebd96c69b8b1daaa31a02897ad9457da92572b1c3ffa153a975
(8,11)
ac3d9b008bccd126d1d833dc22091bfc614d376576152b9c7bbb7f53428dc0d5
(12,12)
793669679a28408866d8e8620162510674526fda5a50b2eb3a7e73ee19c6e291
(13,13)
4050397b554c2e555144c01d3e6422e162b4beb5c548cb31225da0830475fec1
(12,13)
Harvey, et al. Expires 14 June 2024 [Page 69]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
377d3e97b80914460eaa1c5b6a5e6d071a5e614dd0e2fd1b88e56f083c699526
(14,14)
ca30a9a18dd8bc1aab3beebd74832299ea9ec1218cefa75c91b70a4c06b05f01
=== MTL Ladder =======================
(0,7)
f6c4315a7824ffc2fdbb2734a701782e4ae4b3cc51bd985cf8e38e6bd6cf1f71
(8,11)
ac3d9b008bccd126d1d833dc22091bfc614d376576152b9c7bbb7f53428dc0d5
(12,13)
377d3e97b80914460eaa1c5b6a5e6d071a5e614dd0e2fd1b88e56f083c699526
(14,14)
ca30a9a18dd8bc1aab3beebd74832299ea9ec1218cefa75c91b70a4c06b05f01
=== MTL Signature =======================
4dc2df90700edb3469b94aa71507fd6b83594354ac5805e076f499d0000d83e2
000000000000000000000000000e0000000e0000000e00000000000000000000
000000040000000000000007f6c4315a7824ffc2fdbb2734a701782e4ae4b3cc
51bd985cf8e38e6bd6cf1f71000000080000000bac3d9b008bccd126d1d833dc
22091bfc614d376576152b9c7bbb7f53428dc0d50000000c0000000d377d3e97
b80914460eaa1c5b6a5e6d071a5e614dd0e2fd1b88e56f083c6995260000000e
0000000eca30a9a18dd8bc1aab3beebd74832299ea9ec1218cefa75c91b70a4c
06b05f01000000204fc750e0d79cf1542e976c7db95989fbf7976c21be19a112
c25d0a547a6046bb
===== Full Signature (len 464) ============
c23e1d84cd9fcb405b961ffc7112f201518a3ea0a385ecacb1e811b4f918481a
00000000000000000000000003ff00000000000003ff000ae18407c19db0027c
8687d7a3fa25aaca51bf9c5c5ae4a44642faaf4f063221ccab1048b35ae4ef70
dac11079f310ead2be2eee39580d98b269df783581af32a17db4ea8c07dd3e07
b9d4d7adf8dcdabbc3578e71730fa7fe472339be0d51db404511dff928b57f6e
08874141978ba02a5ad8b05db062824f61f3d7dd14abd326cdc286ec29664e8d
adf930762a2f15bae0d00fedf6384c3971fa315c96476e4dbbddfb399e9ebade
2cc88c139b6e6fa12284134231ec0e17bb5d661d066a3b07a3f6446b62dd9e52
2268dfd550b80016ea2c50a6b079f823cd71b02dcd41797008f78ed5dcbfcc9f
20d0e0effc903cc5e5f1d47075f86a67c0636757fff963bf83303f05ff5e41b8
4e53d32a078f51632725ccb3ba61b99040e8946761f011aeb3596b7f392e4900
3ce8d007ac703307b1190c3c675599bd854b7c294f41943f0000000000000000
0000000100000000000003ff39e43cfdb78daa9ccc38c7d8342167eb9e8fa968
0a639050c2bc65a07996796900000020cb00605933efc08b05a60970293a609f
440a9b81fd73bdd5e783e3da758a575e
Note: Underlying signature is a stub (SHA256 hash).
Remove 32 bytes and add signature bytes to compare
===== Condensed Path (len 376) =============
c23e1d84cd9fcb405b961ffc7112f201518a3ea0a385ecacb1e811b4f918481a
00000000000000000000000003ff00000000000003ff000ae18407c19db0027c
8687d7a3fa25aaca51bf9c5c5ae4a44642faaf4f063221ccab1048b35ae4ef70
dac11079f310ead2be2eee39580d98b269df783581af32a17db4ea8c07dd3e07
b9d4d7adf8dcdabbc3578e71730fa7fe472339be0d51db404511dff928b57f6e
Harvey, et al. Expires 14 June 2024 [Page 70]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
08874141978ba02a5ad8b05db062824f61f3d7dd14abd326cdc286ec29664e8d
adf930762a2f15bae0d00fedf6384c3971fa315c96476e4dbbddfb399e9ebade
2cc88c139b6e6fa12284134231ec0e17bb5d661d066a3b07a3f6446b62dd9e52
2268dfd550b80016ea2c50a6b079f823cd71b02dcd41797008f78ed5dcbfcc9f
20d0e0effc903cc5e5f1d47075f86a67c0636757fff963bf83303f05ff5e41b8
4e53d32a078f51632725ccb3ba61b99040e8946761f011aeb3596b7f392e4900
3ce8d007ac703307b1190c3c675599bd854b7c294f41943f
===== Signed Ladder (len 84) =============
00000000000000000000000100000000000003ff39e43cfdb78daa9ccc38c7d8
342167eb9e8fa9680a639050c2bc65a079967969cb00605933efc08b05a60970
293a609f440a9b81fd73bdd5e783e3da758a575e
Note: Underlying signature is a stub (SHA256 hash).
Remove 32 bytes and add signature bytes to compare
===== Reconstituted Signature (len 464) ===
e47de2877319c902f73f8bd2a4bd8f168d9b579e48d768c24a3cd2d70d131db4
00000000000000000000000003ff00000000000003ff000a0e482b126bd6318f
677d22a28d366be44cbe6dd8709c1b9a0adcb01c7ad7e02d06e084b109aaccb0
3cdd305c47040c0e299cdcf5f61a4dc28b4aa7ad2b6523e14605d72bcde7afba
f16841b0ac2588204c1a373adfd91bc239fbf3f2219d8775aa67b5bf74f7bb13
e764a8fcc8b4e30eba9da0c8db26d2e06403e8a4d00573ae33c434a3015e60a6
4cce4bbce4d07cfdaf7a3be4198d9635b2f3d4126d2290d9fce69f62d3f10129
269e922de914406276aca04e3f2df949b1f36e14c4a6373a8c137bbd9476dd2e
702c34762e2a105bc260a8842f223dd5c338e01eb013c433139f758cee854e30
07f4b8498a7c528a213c67feeec36cc63101d4d7cb5de3fe8ef774706196437b
12131b105bb39947a03d82895f6908497d9acb797aba2459cd65f27c49f3bd43
a50bbd2b732b1fdd6fbaacd9578c54ba9fe6a1207aaaf4ca0000000000000000
0000000100000000000003ffc54f80e04cbed078c0ca20e89c868cc8f69219ab
d96a8e0ab6fcdb6643df7aac000000204ed3fd35aa080e5e35e8c25f112fc3b7
a4660b8f6d7087a69471d775d5e5c4ef
Note: Underlying signature is a stub (SHA256 hash).
Remove 32 bytes and add signature bytes to compare
Appendix D. Change Log
00: Initial draft of the document.
01: Fixed 10.2.3 Tweakable hash functions definitions. Fixed typo in
section 6.5. Added text to help clarify inputs to the H_msg_mtl and
PRF_msg functions. Added reference to draft FIPS 205.
02: Updated algorithm IDs for alignment with draft FIPS 205. Fixed a
typo in sections 13 and 9.1.
Harvey, et al. Expires 14 June 2024 [Page 71]
Internet-Draft Merkle Tree Ladder Mode (MTL) Signatures December 2023
Acknowledgements
The authors would like to acknowledge the following individuals for
their contributions to this document: Fitzgerald Marcelin.
Authors' Addresses
J. Harvey
Verisign Labs
12061 Bluemont Way
Reston, VA 20190
United States of America
Email: jsharvey@verisign.com
URI: https://www.verisignlabs.com/
B. Kaliski
Verisign Labs
12061 Bluemont Way
Reston, VA 20190
United States of America
Email: bkaliski@verisign.com
URI: https://www.verisignlabs.com/
A. Fregly
Verisign Labs
12061 Bluemont Way
Reston, VA 20190
United States of America
Email: afregly@verisign.com
URI: https://www.verisignlabs.com/
S. Sheth
Verisign Labs
12061 Bluemont Way
Reston, VA 20190
United States of America
Email: ssheth@verisign.com
URI: https://www.verisignlabs.com/
Harvey, et al. Expires 14 June 2024 [Page 72]