Login
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:
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.”
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.
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.
︎
The post Verisign Provides Open Source Implementation of Merkle Tree Ladder Mode appeared first on Verisign Blog.
In 2021, we discussed a potential future shift from established public-key algorithms to so-called “post-quantum” algorithms, which may help protect sensitive information after the advent of quantum computers. We also shared some of our initial research on how to apply these algorithms to the Domain Name System Security Extensions, or DNSSEC. In the time since that blog post, we’ve continued to explore ways to address the potential operational impact of post-quantum algorithms on DNSSEC, while also closely tracking industry research and advances in this area.
Now, significant activities are underway that are setting the timeline for the availability and adoption of post-quantum algorithms. Since DNS participants – including registries and registrars – use public key-cryptography in a number of their systems, these systems may all eventually need to be updated to use the new post-quantum algorithms. We also announce two major contributions that Verisign has made in support of standardizing this technology: an Internet-Draft as well as a public, royalty-free license to certain intellectual property related to that Internet-Draft.
In this blog post, we review the changes that are on the horizon and what they mean for the DNS ecosystem, and one way we are proposing to ease the implementation of post-quantum signatures – Merkle Tree Ladder mode.
By taking these actions, we aim to be better prepared (while also helping others prepare) for a future where cryptanalytically relevant quantum computing and post-quantum cryptography become a reality.
In July 2022, the National Institute of Standards and Technology (NIST) selected one post-quantum encryption algorithm and three post-quantum signature algorithms for standardization, with standards for these algorithms arriving as early as 2024. In line with this work, the Internet Engineering Task Force (IETF) has also started standards development activities on applying post-quantum algorithms to internet protocols in various working groups, including the newly formed Post-Quantum Use in Protocols (PQUIP) working group. And finally, the National Security Agency (NSA) recently announced that National Security Systems are expected to transition to post-quantum algorithms by 2035.
Collectively, these announcements and activities indicate that many organizations are envisioning a (post-)quantum future, across many protocols. Verisign’s main concern continues to be how post-quantum cryptography impacts the DNS, and in particular, how post-quantum signature algorithms impact DNSSEC.
The standards being developed in the next few years are likely to be the ones deployed when the post-quantum transition eventually takes place, so now is the time to take operational requirements for specific protocols into account.
For DNSSEC, the operational concerns are twofold.
First, the large signature sizes of current post-quantum signatures selected by NIST would result in DNSSEC responses that exceed the size limits of the User Datagram Protocol, which is broadly deployed in the DNS ecosystem. While the Transmission Control Protocol and other transports are available, the additional overhead of having large post-quantum signatures on every response — which can be one to two orders of magnitude as long as traditional signatures —introduces operational risk to the DNS ecosystem that would be preferable to avoid.
Second, the large signatures would significantly increase memory requirements for resolvers using in-memory caches and authoritative nameservers using in-memory databases.
Figure 1, from Andy Fregly’s recent presentation at OARC 40, shows the impact on a fully signed DNS zone where, on average, there are 2.2 digital signatures per resource record set (covering both existence and non-existence proofs). The horizontal bars show the percentage of the zone file that would be comprised of signature data for the two prevalent current algorithms, RSA and ECDSA, and for the smallest and largest of the NIST PQC algorithms. At the low and high end of these examples, signatures with ECDSA would take up 40% of the zone and SPHINCS+ signatures would take up over 99% of the zone. The vertical bars give the percentage size increase of the zone file due to signatures. Again, comparing the low and high end, a zone fully signed with SPHINCS+ would be about 50 times the size of a zone fully signed with ECDSA.
In his 1988 article, “The First Ten Years of Public-Key Cryptography,” Whitfield Diffie, co-discoverer of public-key cryptography, commented on the lack of progress in finding public-key encryption algorithms that were as fast as the symmetric-key algorithms of the day: “Theorems or not, it seemed silly to expect that adding a major new criterion to the requirements of a cryptographic system could fail to slow it down.”
Diffie’s counsel also appears relevant to the search for post-quantum algorithms: It would similarly be surprising if adding the “major new criterion” of post-quantum security to the requirements of a digital signature algorithm didn’t impact performance in some way. Signature size may well be the tradeoff for post-quantum security, at least for now.
With this tradeoff in mind, Verisign’s post-quantum research team has explored ways to address the size impact, particularly to DNSSEC, arriving at a construction we call a Merkle Tree Ladder (MTL), a generalization of a single-rooted Merkle tree (see Figure 2). We have also defined a technique that we call the Merkle Tree Ladder mode of operation for using the construction with an underlying signature algorithm.
Similar to current deployments of public-key cryptography, MTL mode combines processes with complementary properties to balance performance and other criteria (see Table 1). In particular, in MTL mode, rather than signing individual messages with a post-quantum signature algorithm, ladders comprised of one or more Merkle tree nodes are signed using the post-quantum algorithm. Individual messages are then authenticated relative to the ladders using Merkle authentication paths.
| Criterion to Achieve | Initial Design with a Single Process | Improved Design Combining Complementary Processes | Benefit |
| Public-Key Property for Encryption | – Encrypt Individual Messages with Public-Key Algorithm | – Establish Symmetric Keys Using Public-Key Algorithm – Encrypt Multiple Messages Using Each Symmetric Key |
– Amortize Cost of Public-Key Operations Across Multiple Messages |
| Post-Quantum Property for Signatures | – Sign Individual Messages with Post-Quantum Algorithm | – Sign Merkle Tree Ladders using Post-Quantum Algorithm – Authenticate Multiple Messages Relative to Each Signed Ladder |
– Amortize Size of Post-Quantum Signature Across Multiple Messages |
Although the signatures on the ladders might be relatively large, the ladders and their signatures are sent infrequently. In contrast, the Merkle authentication paths that are sent for each message are relatively short. The combination of the two processes maintains the post-quantum property while amortizing the size impact of the signatures across multiple messages. (Merkle tree constructions, being based on hash functions, are naturally post-quantum.)
The two-part approach for public-key algorithms has worked well in practice. In Transport Layer Security, symmetric keys are established in occasional handshake operations, which may be more expensive. The symmetric keys are then used to encrypt multiple messages within a session without further overhead for key establishment. (They can also be used to start a new session).
We expect that a two-part approach for post-quantum signatures can similarly work well in an application like DNSSEC where verifiers are interested in authenticating a subset of messages from a large, evolving message series (e.g., DNS records).
In such applications, signed Merkle Tree Ladders covering a range of messages in the evolving series can be provided to a verifier occasionally. Verifiers can then authenticate messages relative to the ladders, given just a short Merkle authentication path.
Importantly, due to a property of Merkle authentication paths called backward compatibility, all verifiers can be given the same authentication path relative to the signer’s current ladder. This also helps with deployment in applications such as DNSSEC, since the authentication path can be published in place of a traditional signature. An individual verifier may verify the authentication path as long as the verifier has a previously signed ladder covering the message of interest. If not, then the verifier just needs to get the current ladder.
As reported in our presentation on MTL mode at the RSA Conference Cryptographers’ Track in April 2023, our initial evaluation of the expected frequency of requests for MTL mode signed ladders in DNSSEC is promising, suggesting that a significant reduction in effective signature size impact can be achieved.
To facilitate more public evaluation of MTL mode, Verisign’s post-quantum research team last week published the Internet-Draft “Merkle Tree Ladder Mode (MTL) Signatures.” The draft provides the first detailed, interoperable specification for applying MTL mode to a signature scheme, with SPHINCS+ as an initial example.
We chose SPHINCS+ because it is the most conservative of the NIST PQC algorithms from a cryptographic perspective, being hash-based and stateless. It is arguably most suited to be one of the algorithms in a long-term deployment of a critical infrastructure service like DNSSEC. With this focus, the specification has a “SPHINCS+-friendly” style. Implementers familiar with SPHINCS+ will find similar notation and constructions as well as common hash function instantiations. We are open to adding other post-quantum signature schemes to the draft or other drafts in the future.
Publishing the Internet-Draft is a first step toward the goal of standardizing a mode of operation that can reduce the size impact of post-quantum signature algorithms.
In support of this goal, Verisign also announced this week a public, royalty-free license to certain intellectual property related to the Internet-Draft published last week. Similar to other intellectual property rights declarations the company has made, we have announced a “Standards Development Grant” which provides the listed intellectual property under royalty-free terms for the purpose of facilitating standardization of the Internet-Draft we published on July 10, 2023. (The IPR declaration gives the official language.)
We expect to release an open-source implementation of the Internet-Draft soon, and, later this year, to publish an Internet-Draft on using MTL mode signatures in DNSSEC.
With these contributions, we invite implementers to take part in the next step toward standardization: evaluating initial versions of MTL mode to confirm whether they indeed provide practical advantages in specific use cases.
DNSSEC continues to be an important part of the internet’s infrastructure, providing cryptographic verification of information associated with the unique, stable identifiers in this ubiquitous namespace. That is why preparing for an eventual transition to post-quantum algorithms for DNSSEC has been and continues to be a key research and development activity at Verisign, as evidenced by our work on MTL mode and post-quantum DNSSEC more generally.
Our goal is that with a technique like MTL mode in place, protocols like DNSSEC can preserve the security characteristics of a pre-quantum environment while minimizing the operational impact of larger signatures in a post-quantum world.
In a later blog post, we’ll share more details on some upcoming changes to DNSSEC, and how these changes will provide both security and operational benefits to DNSSEC in the near term.
Verisign plans to continue to invest in research and standards development in this area, as we help prepare for a post-quantum future.
The post Next Steps in Preparing for Post-Quantum DNSSEC appeared first on Verisign Blog.
FreshRSS 