A digital blue tree on a gradient blue background.

Verisign Provides Open Source Implementation of Merkle Tree Ladder Mode

The quantum computing era is coming, and it will change everything about how the world connects online. While quantum computing will yield tremendous benefits, it will also create new risks, so it’s essential that we prepare our critical internet infrastructure for what’s to come. That’s why we’re so pleased to share our latest efforts in this area, including technology that we’re making available as an open source implementation to help internet operators worldwide prepare.

In recent years, the research team here at Verisign has been focused on a future where quantum computing is a reality, and where the general best practices and guidelines of traditional cryptography are re-imagined. As part of that work, we’ve made three further contributions to help the DNS community prepare for these changes:

  • an open source implementation of our Internet-Draft (I-D) on Merkle Tree Ladder (MTL) mode;
  • a new I-D on using MTL mode signatures with DNS Security Extensions (DNSSEC); and
  • an expansion of our previously announced public license terms to include royalty-free terms for implementing and using MTL mode if the I-Ds are published as Experimental, Informational, or Standards Track Requests for Comments (RFCs). (See the MTL mode I-D IPR declaration and the MTL mode for DNSSEC I-D IPR declaration for the official language.)

About MTL Mode

First, a brief refresher on what MTL mode is and what it accomplishes:

MTL mode is a technique developed by Verisign researchers that can reduce the operational impact of a signature scheme when authenticating an evolving series of messages. Rather than signing messages individually, MTL mode signs structures called Merkle tree ladders that are derived from the messages to be authenticated. Individual messages are authenticated relative to a ladder using a Merkle tree authentication path, while ladders are authenticated relative to a public key of an underlying signature scheme using a digital signature. The size and computational cost of the underlying digital signatures can therefore be spread across multiple messages.

The reduction in operational impact achieved by MTL mode can be particularly beneficial when the mode is applied to a signature scheme that has a large signature size or computational cost in specific use cases, such as when post-quantum signature schemes are applied to DNSSEC.

Recently, Verisign Fellow Duane Wessels described how Verisign’s DNSSEC algorithm update — from RSA/SHA-256 (Algorithm 8) to ECDSA Curve P-256 with SHA-256 (Algorithm 13) — increases the security strength of DNSSEC signatures and reduces their size impact. The present update is a logical next step in the evolution of DNSSEC resiliency. In the future, it is possible that DNSSEC may utilize a post-quantum signature scheme. Among the new post-quantum signature schemes currently being standardized, though, there is a shortcoming; if we were to directly apply these schemes to DNSSEC, it would significantly increase the size of the signatures1. With our work on MTL mode, the researchers at Verisign have provided a way to achieve the security benefit of a post-quantum algorithm rollover in a way that mitigates the size impact.

Put simply, this means that in a quantum environment, the MTL mode of operation developed by Verisign will enable internet infrastructure operators to use the longer signatures they will need to protect communications from quantum attacks, while still supporting the speed and space efficiency we’ve come to expect.

For more background information on MTL mode and how it works, see my July 2023 blog post, the MTL mode I-D, or the research paper, “Merkle Tree Ladder Mode: Reducing the Size Impact of NIST PQC Signature Algorithms in Practice.”

Recent Standardization Efforts

In my July 2023 blog post titled “Next Steps in Preparing for Post-Quantum DNSSEC,” I described two recent contributions by Verisign to help the DNS community prepare for a post-quantum world: the MTL mode I-D and a public, royalty-free license to certain intellectual property related to that I-D. These activities set the stage for the latest contributions I’m announcing in this post today.

Our Latest Contributions

  • Open source implementation. Like the I-D we published in July of this year, the open source implementation focuses on applying MTL mode to the SPHINCS+ signature scheme currently being standardized in FIPS 205 as SLH-DSA (Stateless Hash-Based Digital Signature Algorithm) by the National Institute of Standards and Technology (NIST). We chose SPHINCS+ because it is the most conservative of NIST’s post-quantum signature algorithms from a cryptographic perspective, being hash-based and stateless. We remain open to adding other post-quantum signature schemes to the I-D and to the open source implementation.
    We encourage developers to try out the open source implementation of MTL mode, which we introduced at the IETF 118 Hackathon, as the community’s experience will help improve the understanding of MTL mode and its applications, and thereby facilitate its standardization. We are interested in feedback both on whether MTL mode is effective in reducing the size impact of post-quantum signatures on DNSSEC and other use cases, and on the open source implementation itself. We are particularly interested in the community’s input on what language bindings would be useful and on which cryptographic libraries we should support initially. The open source implementation can be found on GitHub at: https://github.com/verisign/MTL
  • MTL mode for DNSSEC I-D. This specification describes how to use MTL mode signatures with DNSSEC, including DNSKEY and RRSIG record formats. The I-D also provides initial guidance for DNSSEC key creation, signature generation, and signature verification in MTL mode. We consider the I-D as an example of the kinds of contributions that can help to address the “Research Agenda for a Post-Quantum DNSSEC,” the subject of another I-D recently co-authored by Verisign. We expect to continue to update this I-D based on community feedback. While our primary focus is on the DNSSEC use case, we are also open to collaborating on other applications of MTL mode.
  • Expanded patent license. Verisign previously announced a public, royalty-free license to certain intellectual property related to the MTL mode I-D that we published in July 2023. With the availability of the open source implementation and the MTL mode for DNSSEC specification, the company has expanded its public license terms to include royalty-free terms for implementing and using MTL mode if the I-D is published as an Experimental, Informational, or Standards Track RFC. In addition, the company has made a similar license grant for the use of MTL mode with DNSSEC. See the MTL mode I-D IPR declaration and the MTL mode for DNSSEC I-D IPR declaration for the official language.

Verisign is grateful for the DNS community’s interest in this area, and we are pleased to serve as stewards of the internet when it comes to developing new technology that can help the internet grow and thrive. Our work on MTL mode is one of the longer-term efforts supporting our mission to enhance the security, stability, and resiliency of the global DNS. We’re encouraged by the progress that has been achieved, and we look forward to further collaborations as we prepare for a post-quantum future.

Footnotes

  1. While it’s possible that other post-quantum algorithms could be standardized that don’t have large signatures, they wouldn’t have been studied for as long. Indeed, our preferred approach for long-term resilience of DNSSEC is to use the most conservative of the post-quantum signature algorithms, which also happens to have the largest signatures. By making that choice practical, we’ll have a solution in place whether or not a post-quantum algorithm with a smaller signature size is eventually available. ↩︎
Share:

Burt Kaliski

Dr. Burt Kaliski Jr., Senior Vice President and Chief Technology Officer, leads Verisign’s long-term research program. Through the program’s innovation initiatives, the CTO organization, in collaboration with business and technology leaders across the company, explores emerging technologies, assesses their impact on the company’s business, prototypes and evaluates new concepts, and recommends new strategies and solutions. Burt is also responsible for... Read More →