Internet-Draft ML-DSA-MTL-DNSSEC July 2026
Kaizer, et al. Expires 7 January 2027 [Page]
Workgroup:
DNSOP Working Group
Draft:
draft-kaizer-dnsop-ml-dsa-mtl-dnssec-00
Published:
Intended Status:
Informational
Expires:
Authors:
A. Kaizer
Verisign Labs
J. Harvey
Verisign Labs
B. Kaliski
Verisign Labs
S. Sheth
Verisign Labs

Module-Lattice-Based Signatures with Merkle Tree Ladders (ML-DSA-MTL) for DNSSEC

Abstract

This document describes how to apply the Module-Lattice-Based Digital Signature Algorithm (ML-DSA) and Merkle Tree Ladders (MTL) as a conservative post-quantum cryptographic algorithm for DNS Security Extensions (DNSSEC). This combination is referred to as the ML-DSA-MTL Signature scheme. This document describes how to specify ML-DSA-MTL keys and signatures in DNSSEC, specifically for ML-DSA-44 with SHAKE-128. This document also provides guidance for use of EDNS(0) in signature retrieval.

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/.

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 7 January 2027.

▲

Table of Contents

1. Introduction

The Domain Name System Security Extensions (DNSSEC), which are broadly defined in [RFC4033], [RFC4034] and [RFC4035], use cryptographic keys and digital signatures to provide data origin authentication and data integrity in the DNS.

This document describes the application of Merkle Tree Ladders (MTL) [MTL-MODE] to the Module-Lattice-Based Digital Signature Algorithm (ML-DSA) [FIPS204], referred to generally as ML-DSA-MTL. This document specifically defines the use of ML-DSA-44 with SHAKE-128 as the ML-DSA-44-MTL-SHAKE-128 signature scheme for DNSSEC. Other combinations are possible for MTLs (e.g., SLH-DSA or ML-DSA with SHA256) and may be described in separate documents.

As described herein, a DNSKEY resource record (RR) for an ML-DSA-MTL key contains a ML-DSA key. The ML-DSA key is used for verifying signatures on MTL authentication data. An RRSIG resource record for an ML-DSA-MTL Signature contains a Merkle proof (authentication path) and optional signed MTL. The Merkle proof is verifiable using a MTL. A signed MTL with a Merkle proof can be verified in a single response, similar to how existing DNSSEC algorithms operate today.

This draft focuses on the code-points applicable to DNSKEY and RRSIG formulation and how to retrieve MTL signatures. Later versions may describe DNSSEC protocol and/or operational guidance for zone signing, zone composition, zone updates, zone transfer, name server processing, resolver signature processing, and resolver caching related to MTLs signatures.

1.1. Motivation

This document provides a conservatively designed PQC algorithm for DNSSEC as described in [I-D.sheth-pqc-dnssec-strategy] using MTL [MTL-MODE] and ML-DSA [FIPS204]. The cryptographic operations for applying MTL to ML-DSA in the DNSSEC use case are specified within this document. The reader does not need to be familiar with the more general [MTL-MODE] specification to implement the ML-DSA-MTL signature scheme for DNSSEC.

MTL is designed to reduce the size, memory, and computational impact of PQC signature algorithms. For DNSSEC, the size impact reduction is achieved when signatures provided in RRSIG RRs are primarily comprised of "condensed signatures" (Merkle proofs / authentication paths) and are only occasionally comprised of "full signatures" that contain both a condensed signature and a signed MTL, where the signed MTL includes a signature using the underlying PQC signature algorithm, i.e., ML-DSA. MTL reduces the memory requirements for PQC signatures as the signature data in the zone database or cache is primarily comprised of Merkle proofs and only occasionally of signed MTLs [CTRSAMTL]. It also reduces the computational requirements when many condensed signatures are included under a full signature as only the full signature incurs the signing and/or verification overhead of the underlying algorithm.

ML-DSA was formally published as a standard by NIST in August 2024 [FIPS204]. This document selected ML-DSA as one application of MTL to DNSSEC because lattice-based techniques are well understood and offer a conservative choice for long-term security relative to newer NIST candidate post-quantum signature schemes.

1.2. Definitions

The provided terms in alphabetical order describe concepts utilized in this document.

Authentication Path
The set of sibling hash values from a leaf hash value to a rung.
Index
An integer value I that identifies a leaf node in a node set. Indexes start at 0 and are consecutively assigned.
Index Pair
A pair of integer values (L,R) that together identify a node in a node set based on the lowest and highest indexes of the consecutively-indexed leaf nodes that the node authenticates. For a leaf node, the index pair is (I,I) which is used interchangeably with the leaf index I.
Internal Node
A node in a node set whose value is the hash of two child nodes.
Ladder/Merkle Tree Ladder (MTL)
A collection of one or more rungs that can be used to verify an authentication path.
Leaf Node
A node in a node set whose value is the hash of a single message.
Message
A set of bytes that are intended to be signed and later verified.
Node Set
An evolving set of hash nodes, each of which is part of a union of tree structures either as a leaf node or an internal node. A 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.
Root Node
A node in a node set that has no ancestors.
Series Identifier (SID)
A cryptographically unique value associated with an instance of a MTL node set.
Rung
A node from a node set that can be used to authenticate one or more leaf nodes within that node set. A rung may be a root node.

1.3. Binary Rung Strategy

In the MTL operations in this document, the ladder is selected according to what is called the binary rung strategy. In this strategy, the index pairs for the rungs are based on the binary representation of the number of messages in the message series. More specifically, the first rung is the apex of the largest perfect binary tree that can be formed from the leaf nodes corresponding to the messages, starting from the left; the second rung is the apex of the largest perfect binary tree that can be formed from the remaining leaf nodes; and so on. The sizes of the trees decrease from left to right.

The following figure shows a node set with 14 leaf nodes based on this 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

Merkle tree authentication paths in binary rung strategy are constructed from the perfect binary tree that a given rung covers. For example, the authentication path for leaf 9 would include the hash of leaf 8 and (10,11) which is sufficient to re-create rung (8,11) which covers leaf 9.

The following table gives examples of ladders for values of N up to 19 to showcase how the rungs evolve as new messages are appended to a given node set.

          Number of Messages    |      Ladder Rungs
                    N           |
        -------------------------------------------------
                    1           | (0,0)
                    2           | (0,1)
                    3           | (0,1) (2,2)
                    4           | (0,3)
                    5           | (0,3) (4,4)
                    6           | (0,3) (4,5)
                    7           | (0,3) (4,5) (6,6)
                    8           | (0,7)
                    9           | (0,7) (8,8)
                   10           | (0,7) (8,9)
                   11           | (0,7) (8,9) (10,10)
                   12           | (0,7) (8,11)
                   13           | (0,7) (8,11) (12,12)
                   14           | (0,7) (8,11) (12,13)
                   15           | (0,7) (8,11) (12,13) (14,14)
                   16           | (0,15)
                   17           | (0,15) (16,16)
                   18           | (0,15) (16,17)
                   19           | (0,15) (16,17) (18,18)

Different rung strategies may result in rungs and authentication paths that differ from the above. This document does not limit to any specific rung strategy, although for interoperability in constructing/evaluating authentication paths the current draft assumes each rung is a perfect binary tree. Additional rung strategies may be defined in updates to this draft or in future drafts.

2. 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.

The single pipe character, "|", is used to denote concatenation as is done in [RFC4034].

All numeric DNSKEY elements and RRSIG elements specified in this document are unsigned integers in network byte order (big endian order).

3. DNSKEY Resource Records

ML-DSA-44 public keys are stored in the Public Key field of a DNSKEY resource record as the fixed-length, 1312-octet output of the ML-DSA-44 public key, as specified in [FIPS204] Algorithm 22. The Algorithm field of the DNSKEY RR MUST be set to the value allocated for ML-DSA-44 (see Section 9).

4. RRSIG Resource Records

The value of the signature field in the RRSIG RR consists of a variable-length value starting with one-octet MTL-Type and followed by MTL Authentication Data:

                     1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   MTL-Type    |                                               |
+-+-+-+-+-+-+-+-+                                               |
|                    MTL Authentication Data                    |
/                                                               /
/                                                               /
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The MTL-Type octet is one of condensed (0) or full (1). The MTL Authentication Data includes the signature information of the specified type. Condensed signatures are described in Section 5.1.1 and full signatures are described in Section 5.1.2. How these signatures can be leveraged for dynamic signing is described in Section 8.2.

5. MTL Implementation Details

This section describes the data structures for each MTL-Type in Section 5.1, how to instantiate the hashing algorithms in Section 5.2, and summarizes what data is included for each MTL-Type in Section 5.3. Taken together, it allows a signer or verifier to sign and verify MTL DNSSEC signatures in a consistent, interoperable manner. Appendix B and Appendix C include high-level steps a signer or verifier could take to implement these concepts.

The octets required in this section are based on the values for ML-DSA-44 as specified in [FIPS204] and could be different if other underlying signature algorithms were supported.

5.1. MTL Data Structures

This section describes the format of the MTL Authentication Data referred to in Section 4.

5.1.1. Condensed Signatures

An application MAY convey a "condensed" signature comprised of a Merkle tree proof only, which is convenient for reducing the size impact compared to a full signature. However, it requires the verifier to obtain the rest of the full signature, i.e., the signed ladder, from a separate source, e.g., with a separate query.

A condensed MTL signature consists of:

                         1 1 1 1 1 1
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
    +-------------------------------+
    |             Flags             |
    +-------------------------------+
    |                               |
    //             SID             //
    |          (32-octets)          |
    +-------------------------------+
    |                               |
    //          Randomizer         //
    |          (16-octets)          |
    +-------------------------------+
    |                               |
    |          Leaf Index           |
    |          (8-octets)           |
    |                               |
    +-------------------------------+
    |                               |
    |     Target Rung Left Index    |
    |          (8-octets)           |
    |                               |
    +-------------------------------+
    |                               |
    |    Target Rung Right Index    |
    |          (8-octets)           |
    |                               |
    +-------------------------------+
    |      Sibling Hash Count       |
    +-------------------------------+
    |                               |
    //     Sibling Hash Values     //
    |    (16-octets per sibling)    |
    +-------------------------------+

Where:

  • flags, string providing future extensibility; it MUST be 0 for this version of the document
  • SID, series identifier of the node set
  • randomizer, randomizer value associated with leaf_index
  • leaf_index, the leaf index of the message being authenticated, a non-negative integer between 0 and 2^64-1
  • rung_left, the left index of the target rung, a non-negative integer between 0 and 2^64-1
  • rung_right, the right index of the target rung, a non-negative integer between 0 and 2^64-1
  • 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

The SID is RECOMMENDED to be generated from an approved Random Bit Generator [RFC4086] and the randomizer MUST be generated from an approved Random Bit Generator.

5.1.2. Full Signatures

An application MAY convey a "full" signature which can be verified on its own. However, it includes the overhead of the ladder and the underlying signature on the ladder.

A full MTL signature consists of two base components:

                         1 1 1 1 1 1
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
    +-------------------------------+
    |                               |
    //     Condensed Signature     //
    |       (variable octets)       |
    +-------------------------------+
    |                               |
    //        Signed Ladder        //
    |       (variable octets)       |
    +-------------------------------+

Where:

5.1.2.1. Signed Ladder

A signed ladder data structure consists of:

                         1 1 1 1 1 1
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
    +-------------------------------+
    |             Flags             |
    +-------------------------------+
    |                               |
    //             SID             //
    |          (32-octets)          |
    +-------------------------------+
    |          Rung Count           |
    +-------------------------------+
    |                               |
    //          Rung Data          //
    |      (32-octets per rung)     |
    +-------------------------------+
    |  Underlying Signature Length  |
    |          (4-octets)           |
    +-------------------------------+
    |                               |
    //    Underlying Signature     //
    |         (2420-octets)         |
    +-------------------------------+

Where:

  • flags, string providing future extensibility; the initial value for this field MUST be 0
  • SID, same value as defined in Section 5.1.1
  • 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
  • sig_len, the length in octets of the underlying signature on the ladder, a positive integer between 1 and 2^32-1
  • sig, the underlying signature on the ladder (i.e., flags, SID, rung_count, and rungs)

Each Rung Data consists of:

                         1 1 1 1 1 1
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
    +-------------------------------+
    |                               |
    |          Left Index           |
    |          (8-octets)           |
    |                               |
    +-------------------------------+
    |                               |
    |          Right Index          |
    |          (8-octets)           |
    |                               |
    +-------------------------------+
    |                               |
    //       Rung Hash Value       //
    |          (16-octets)          |
    +-------------------------------+

Where:

  • left_index, the left index of the rung, a non-negative integer between 0 and 2^64-1
  • right_index, the right index of the rung, a non-negative integer between left_index and 2^64-1
  • hash, the rung hash value

5.2. MTL Hash Function Instantiation

This document specifies the use of cSHAKE128 as the hash function for use in MTL as defined in NIST SP 800-185 [CSHAKE]. For MTL the hash algorithm is utilized to generate the Merkle tree(s) that comprise a node set where the inputs to the hash function depend on whether the node is a leaf node or internal node.

For a leaf node, LEAF = (SID | Randomizer | leaf_index | len(ctx_msg) | ctx_msg | msg) where:

  • SID, a 32-octet value as described in Section 5.1.1
  • leaf_index, an 8-octet value denoting the leaf node's index
  • Randomizer, a 16-octet value as described in Section 5.1.1
  • len(ctx_msg), a 4-octet value of the length of the included message-specific context string; MUST be 0
  • ctx_msg, variable length byte array; MUST be null in this draft
  • msg, variable length byte array containing the message corresponding to the leaf node, i.e., RRSIG_RDATA | RR(1) | RR(2)...

The inclusion of ctx_msg is provided for future extensibility and consistency with other recent specifications that support per-message context strings.

For an internal node, INTERNAL = (SID | left_index | right_index | hash_left | hash_right) where:

  • SID, a 32-octet value
  • left_index, an 8-octet value denoting the internal node's left index
  • right_index, an 8-octet value denoting the internal node's right index
  • hash_left, a 16-octet value denoting the left child hash
  • hash_right, a 16-octet value denoting the right child hash

This is then applied to cSHAKE as follows to produce a cSHAKE128 output:

  • H_leaf = cSHAKE(LEAF, 128, "", HASH_CUSTOMIZATION_STRING_LEAF)
  • H_int = cSHAKE(INTERNAL, 128, "", HASH_CUSTOMIZATION_STRING_INT)

where HASH_CUSTOMIZATION_STRING_LEAF is the user customization string input allowed by cSHAKE and MUST be an octet string represented by "{'M','T','L','L','E','A','F'}" and HASH_CUSTOMIZATION_STRING_INT MUST be an octet string represented by "{'M','T','L','I','N','T'}".

5.3. MTL Signature Coverage

Full and condensed signatures protect the same DNS RRset responses as non-MTL DNSSEC responses because the leaf nodes correspond to the same RRSIG_RDATA | RR(1) | RR(2)... observed in 3.1.8.1 of [RFC4034]. The primary difference between full and condensed responses is what is covered by the signature related data as described next.

A full signature signs a ladder rather than individual DNS RRsets, i.e., signature = sign(FLAGS | SID | RUNG_COUNT | RUNG_DATA). Meanwhile, the msg input to the leaf node hash operation contains the [RFC4034] data. This enables one signature on a signed ladder to authenticate every RRset included in the given Merkle tree node set rather than signing each RRset individually.

A condensed signature does not provide a signature using sign(...) but provides enough information to prove inclusion in a Merkle tree node set covered by a signed ladder. The association with a full signature that has sign(...) data covers the condensed signature.

6. Algorithm Numbers for DS, DNSKEY, and RRSIG Resource Records

The algorithm number associated with the use of MLDSA44MTLSHAKE128 in DS, DNSKEY, and RRSIG resource records is TBD. This registration is fully defined in the IANA Considerations section.

7. The mtl-full EDNS(0) Option

To receive full signatures, a MTL-aware client MUST request that signatures be returned in the full format by providing the mtl-full EDNS(0) option in the OPT meta-RR of its query [RFC6891].

7.1. Option Format

The mtl-full option is encoded as follows:

0                       8                      16
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|                  OPTION-CODE                  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|                 OPTION-LENGTH                 |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

Where:

OPTION-CODE
The EDNS0 option code assigned to mtl-full, TBD.
OPTION-LENGTH
Always zero.

7.2. Use by DNS Servers

When a query includes the mtl-full option, the response MUST include one or more full and optionally zero or more condensed signatures. Each condensed signature in the response MUST be covered by at least one full signature in the response which enables a full response to be self-contained.

A server MUST NOT return a full signature unless mtl-full is provided. If a server does not have a full signature and one is requested, it MUST return SERVFAIL with a TBD EDE code.

7.3. Use by DNS Clients

A client SHOULD first query a server without the mtl-full option, and then, if needed, re-issue the query with the mtl-full option. Since responses to queries with the mtl-full option are expected to be large, it is RECOMMENDED that queries with the mtl-full option be issued over transports (e.g., TCP, TLS, QUIC) that support large responses without truncation and/or fragmentation.

Clients that request a full signature but receive only condensed signatures MUST return SERVFAIL with a TBD EDE code. If a client does not use the mtl-full option and receives one or more full signatures, it MUST return SERVFAIL with TBD EDE code.

7.4. Summary of Expected Outcomes

This section summarizes the expected behavior a server and a client follow when encountering a MTL response depending on if mtl-full was used.

7.4.1. Authoritative Server

Table 1: Expected authoritative behavior
mtl-full Have Full Return
Y Y One or more full + covered condensed
Y N SERVFAIL + EDE
N - One or more condensed

7.4.2. Client

Table 2: Expected client behavior
mtl-full Response Action
Y At least one full Use
Y No full SERVFAIL + EDE
N One or more full SERVFAIL + EDE
N Condensed Use or request full

8. Implementation Considerations

8.1. Batch Signing

Signing RRsets in batches, i.e., as multiple additions to a node set, rather than as individual additions or as messages can leverage MTL to reduce the number of signature and verification operations performed with the underlying signature algorithm. This results in reducing the average computational overhead per message signed/verified. This practice can also reduce the load on a hardware security module. Batches also benefit the verifier by reducing the number of full signatures required for validation because multiple RRSIGs can be verified by the signed ladder covering a batch. The appropriate batch size will depend on the properties of the zone and the requirements of the zone operator. Batch size needs to be considered carefully to ensure that new signatures are available in a timely manner while still gaining the benefits of batch signing [MTL-ENDURANCE].

8.2. Online Signing

MTL can accommodate online signing, also known as dynamic signing, where responses are generated dynamically at query time. How exactly this is achieved is dependent on the operator's requirements. One example, but not limiting, is to generate a new MTL node set for each query response. Implementors should be aware that online signing may limit the amortization benefits of MTL to only data within the same query.

9. IANA Considerations

This document updates the IANA registry for DNSSEC "Domain Name System Security (DNSSEC) Algorithm Numbers" located at https://www.iana.org/assignments/dns-sec-alg-numbers/dns-sec-alg-numbers.xhtml. The following entries are requested to be added to the registry subject to the Number update:

ML-DSA-44-MTL-SHAKE-128
+--------------+--------------------------------+
| Number       | TBD                            |
| Description  | ML-DSA-44-MTL-SHAKE-128        |
| Mnemonic     | MLDSA44MTLSHAKE128             |
| Zone Signing | Y                              |
| Trans. Sec.  | *                              |
| Reference    | This specification             |
+--------------+--------------------------------+

10. Implementation Status

NOTE: Please remove this section and the reference to RFC 7942 prior to publication as an RFC.

This section records the status of known implementations of the protocol defined by this specification at the time of posting of this Internet-Draft, and is based on a proposal described in RFC 7942. The description of implementations in this section is intended to assist the IETF in its decision processes in progressing drafts to RFCs. Please note that the listing of any individual implementation here does not imply endorsement by the IETF. Furthermore, no effort has been spent to verify the information presented here that was supplied by IETF contributors. This is not intended as, and must not be construed to be, a catalog of available implementations or their features. Readers are advised to note that other implementations may exist.

According to RFC 7942, "this will allow reviewers and working groups to assign due consideration to documents that have the benefit of running code, which may serve as evidence of valuable experimentation and feedback that have made the implemented protocols more mature. It is up to the individual working groups to use this information as they see fit".

For testing purposes, ML-DSA-44-MTL-SHAKE-128 has been implemented in the following DNS open-source applications:

These implementations depend on the reference implementation of MTL which is available in C. The MTL library can be found at https://github.com/Verisign/MTL.

11. Security Considerations

The security considerations of [FIPS204] are inherited in the usage of ML-DSA-MTL in DNSSEC.

ML-DSA-44-MTL-SHAKE-128 is intended to operate at around the 128-bit security level against classical attacks and the 64-bit level against quantum attacks, consistent with NIST's security level I and comparable to non-PQC DNSSEC algorithms such as ECDSAP256SHA256 (algorithm 13). Future documents may describe ML-DSA-65 or ML-DSA-87 if stronger security levels are needed.

A private key used for a DNSSEC zone MUST NOT be used for any other purpose than for that zone. Otherwise, cross-protocol or cross-application attacks are possible.

Implementers MUST NOT use the same SID for multiple MTL instantiations, e.g., the MTL instantiation for a KSK node set and the MTL instantiation for a ZSK node set MUST use different SIDs.

Post-quantum algorithms in DNSSEC may introduce larger keys, signatures, and/or signing/verifying effort which may lead to differences in resource capacity compared to existing DNS operational profiles. Accounting for such factors will help mitigate potential resource exhaustion attacks. The following highlights such factors as it relates to ML-DSA in MTL:

12. Acknowledgements

This I-D has drawn from helpful examples of document structure and specification text from various DNSSEC algorithm RFCs. The authors express their gratitude to the authors of those RFCs for their contributions.

13. References

13.1. Normative References

[FIPS204]
National Institute of Standards and Technology (NIST), "Module-Lattice-Based Digital Signature Standard", FIPS PUB 204, DOI 10.6028/NIST.FIPS.204, , <https://doi.org/10.6028/NIST.FIPS.204>.
[RFC2119]
Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, , <https://www.rfc-editor.org/info/rfc2119>.
[RFC4033]
Arends, R., Austein, R., Larson, M., Massey, D., and S. Rose, "DNS Security Introduction and Requirements", RFC 4033, DOI 10.17487/RFC4033, , <https://www.rfc-editor.org/info/rfc4033>.
[RFC4035]
Arends, R., Austein, R., Larson, M., Massey, D., and S. Rose, "Protocol Modifications for the DNS Security Extensions", RFC 4035, DOI 10.17487/RFC4035, , <https://www.rfc-editor.org/info/rfc4035>.
[RFC6891]
Damas, J., Graff, M., and P. Vixie, "Extension Mechanisms for DNS (EDNS(0))", STD 75, RFC 6891, DOI 10.17487/RFC6891, , <https://www.rfc-editor.org/info/rfc6891>.
[RFC8174]
Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, , <https://www.rfc-editor.org/info/rfc8174>.

13.2. Informative References

[BIN-NUM-TREES]
Champine, L., "Streaming Merkle Proofs within Binary Numeral Trees", Cryptology ePrint Archive Paper 2021/038, , <https://eprint.iacr.org/2021/038>.
[CRYPTO-ACC]
Reyzin, L. and S. Yakoubov, "Efficient data structures for tamper-evident logging", Zikas, V., De Prisco, R. (eds) Security and Cryptography for Networks SCN 2016, LNCS, vol. 9841, pp. 292-309. Springer, Cham, , <https://doi.org/10.1007/978-3-319-44618-9_16>.
[CSHAKE]
National Institute of Standards and Technology (NIST), "DSHA-3 Derived Functions: cSHAKE, KMAC, TupleHash and ParallelHash", FIPS SP 800-185, DOI 10.6028/NIST.SP.800-185, , <https://doi.org/10.6028/NIST.SP.800-185>.
[CTRSAMTL]
Kaliski, B., Fregly, A.M., Harvey, J., and S. Sheth, "Merkle Tree Ladder Mode: Reducing the Size Impact of NIST PQC Signature Algorithms in Practice", .
[HISTORY-TREE]
Crosby, S. and D. Wallach, "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>.
[I-D.sheth-pqc-dnssec-strategy]
Sheth, S., Chung, T., and B. Overeinder, "Post-Quantum Cryptography Strategy for DNSSEC", Work in Progress, Internet-Draft, draft-sheth-pqc-dnssec-strategy-00, , <https://datatracker.ietf.org/doc/html/draft-sheth-pqc-dnssec-strategy-00>.
[MERKLE_MOUNTAIN]
Todd, P., "Merkle Mountain Ranges", <https://github.com/opentimestamps/opentimestamps-server/blob/master/doc/merkle-mountain-range.md>.
[MTL-ENDURANCE]
Tran, M. and T. Chung, "Randomized Evaluation of SLH-DSA-MTL's Impact on Reducing PQ-DNSSEC Signature Sizes", , <https://github.com/IQTF/pq-dnssec-materials/raw/refs/heads/main/IETF122/Tran_Randomized_evaluation_of_SLH-DSA-MTL's_impact_on_reducing_PQ-DNSSEC_signature_sizes.pdf>.
[MTL-MODE]
Fregly, A., Harvey, J., Kaliski, B., and S. Sheth, "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, , <https://eprint.iacr.org/2022/1730.pdf>.
[RFC4034]
Arends, R., Austein, R., Larson, M., Massey, D., and S. Rose, "Resource Records for the DNS Security Extensions", RFC 4034, DOI 10.17487/RFC4034, , <https://www.rfc-editor.org/info/rfc4034>.
[RFC4086]
Eastlake 3rd, D., Schiller, J., and S. Crocker, "Randomness Requirements for Security", BCP 106, RFC 4086, DOI 10.17487/RFC4086, , <https://www.rfc-editor.org/info/rfc4086>.

Appendix A. Change Log

Appendix B. Signer Steps

A signer, e.g., an authoritative server, performs the following set of operations to sign messages in MTL.

The first step is performed once per key pair:

  1. Generate a public / private key pair for ML-DSA-44, e.g., for use as a KSK or ZSK.

The second step is performed once per node set to be signed:

  1. Generate a series identifier for the node set and initialize a node set for the series. The message index of the node set is set to 0 in this step.

The third and fourth steps are performed once per message to be signed in a node set:

  1. Sample a randomizer and compute the leaf hash for the message.

  2. Append the leaf hash to the node set. The message index is incremented in this step.

The fifth and sixth steps are performed whenever the signer wants to produce a new signed ladder. The signer could do so after each new message is added, or after a new batch of new messages is added.

  1. Compute the current ladder for the node set using one or more rungs that collectively authenticate all the nodes in the node set.

  2. Sign the ladder using the ML-DSA-44 private key generated in (1).

The seventh step is performed whenever the signer wants to provide a full signature to a requester, e.g., upon receiving an mtl-full EDNS(0) option.

  1. Provide the full signature as described in Section 5.1.2.

The eighth step is performed whenever the signer wants to compute a new authentication path for a message relative to the current ladder. 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.

  1. Compute an authentication path for the message at a specified message index relative to the current ladder.

The ninth step is performed whenever the signer wants to provide authentication information to a requester, e.g., as part of a condensed signature in a response.

  1. Provide the condensed signature(s) as described in Section 5.1.1.

Appendix C. Verifier Steps

A verifier, e.g., a DNSSEC-aware resolver, performs the following to verify signatures in MTL:

  1. Obtain the signer's public key, e.g., from appropriate DNSKEY records.

The second, third, fifth and sixth steps are performed as needed for each message to be authenticated:

  1. From a condensed signature in a DNS response, obtain the authentication path (i.e., sibling hash values) and the SID.

  2. Determine whether any of ladders held by the verifier includes a rung compatible with the authentication path. If so, skip to step 5.

The fourth step is performed when the verifier doesn't have a compatible ladder.

  1. Re-try the DNS request with mtl-full EDNS(0) option to fetch a full signature which includes a signed ladder with an included condensed signature that is covered by that ladder. Validate the included signed ladder signature against the public key in (1).

  2. Compute a leaf hash from the message as described in Section 5.2.

  3. Verify the authentication path and leaf hash relative to the compatible rung.

Authors' Addresses

A. Kaizer
Verisign Labs
12061 Bluemont Way
Reston, VA 20190
United States of America
URI: https://www.verisignlabs.com/
J. Harvey
Verisign Labs
12061 Bluemont Way
Reston, VA 20190
United States of America
URI: https://www.verisignlabs.com/
B. Kaliski
Verisign Labs
12061 Bluemont Way
Reston, VA 20190
United States of America
URI: https://www.verisignlabs.com/
S. Sheth
Verisign Labs
12061 Bluemont Way
Reston, VA 20190
United States of America
URI: https://www.verisignlabs.com/