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 signatures¹. 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. ↩︎

The post Verisign Provides Open Source Implementation of Merkle Tree Ladder Mode appeared first on Verisign Blog.

The Domain Name System (DNS) root zone will soon be getting a new record type, called ZONEMD, to further ensure the security, stability, and resiliency of the global DNS in the face of emerging new approaches to DNS operation. While this change will be unnoticeable for the vast majority of DNS operators (such as registrars, internet service providers, and organizations), it provides a valuable additional layer of cryptographic security to ensure the reliability of root zone data.

In this blog, we’ll discuss these new proposals, as well as ZONEMD. We’ll share deployment plans, how they may affect certain users, and what DNS operators need to be aware of beforehand to ensure little-to-no disruptions.

The Root Server System

The DNS root zone is the starting point for most domain name lookups on the internet. The root zone contains delegations to nearly 1,500 top-level domains, such as .com, .net, .org, and many others. Since its inception in 1984, various organizations known collectively as the Root Server Operators have provided the service for what we now call the Root Server System (RSS). In this system, a myriad of servers respond to approximately 80 billion root zone queries each day.

While the RSS continues to perform this function with a high degree of dependability, there are recent proposals to use the root zone in a slightly different way. These proposals create some efficiencies for DNS operators, but they also introduce new challenges.

New Proposals

In 2020, the Internet Engineering Task Force (IETF) published RFC 8806, titled “Running a Root Server Local to a Resolver.” Along the same lines, in 2021 the Internet Corporation for Assigned Names and Numbers (ICANN) Office of the Chief Technology Officer published OCTO-027, titled “Hyperlocal Root Zone Technical Analysis.” Both proposals share the idea that recursive name servers can receive and load the entire root zone locally and respond to root zone queries directly.

But in a scenario where the entire root zone is made available to millions of recursive name servers, a new question arises: how can consumers of zone data verify that zone content has not been modified before reaching their systems?

One might imagine that DNS Security Extensions (DNSSEC) could help. However, while the root zone is indeed signed with DNSSEC, most of the records in the zone are considered non-authoritative (i.e., all the NS and glue records) and therefore do not have signatures. What about something like a Pretty Good Privacy (PGP) signature on the root zone file? That comes with its own challenge: in PGP, the detached signature is easily separated from the data. For example, there is no way to include a PGP signature over DNS zone transfer, and there is no easy way to know which version of the zone goes with the signature.

Introducing ZONEMD

A solution to this problem comes from RFC 8976. Led by Verisign and titled “Message Digest for DNS Zones” (known colloquially as ZONEMD), this protocol calls for a cryptographic digest of the zone data to be embedded into the zone itself. This ZONEMD record can then be signed and verified by consumers of the zone data. Here’s how it works:

Each time a zone is updated, the publisher calculates the ZONEMD record by sorting and canonicalizing all the records in the zone and providing them as input to a message digest function. Sorting and canonicalization are the same as for DNSSEC. In fact, the ZONEMD calculation can be performed at the same time the zone is signed. Digest calculation necessarily excludes the ZONEMD record itself, so the final step is to update the ZONEMD record and its signatures.

A recipient of a zone that includes a ZONEMD record repeats the same calculation and compares its calculated digest value with the published digest. If the zone is signed, then the recipient can also validate the correctness of the published digest. In this way, recipients can verify the authenticity of zone data before using it.

A number of open-source DNS software products now, or soon will, include support for ZONEMD verification. These include Unbound (version 1.13.2), NSD (version 4.3.4), Knot DNS (version 3.1.0), PowerDNS Recursor (version 4.7.0) and BIND (version 9.19).

Who Is Affected?

Verisign, ICANN, and the Root Server Operators are taking steps to ensure that the addition of the ZONEMD record in no way impacts the ability of the root server system to receive zone updates and to respond to queries. As a result, most internet users are not affected by this change.

Anyone using RFC 8806, or a similar technique to load root zone data into their local resolver, is unlikely to be affected as well. Software products that implement those features should be able to fully process a zone that includes the new record type, especially for reasons described below. Once the record has been added, users can take advantage of ZONEMD verification to ensure root zone data is authentic.

Users most likely to be affected are those that receive root zone data from the internic.net servers (or some other source) and use custom software to parse the zone file. Depending on how such custom software is designed, there is a possibility that it will treat the new ZONEMD record as unexpected and lead to an error condition. Key objectives of this blog post are to raise awareness of this change, provide ample time to address software issues, and minimize the likelihood of disruptions for such users.

Deployment Plan

In 2020, Verisign asked the Root Zone Evolution Review Committee (RZERC) to consider a proposal for adding data protections to the root zone using ZONEMD. In 2021, the RZERC published its recommendations in RZERC003. One of those recommendations was for Verisign and ICANN to develop a deployment plan and make the community aware of the plan’s details. That plan is summarized in the remainder of this blog post.

Phased Rollout

One attribute of a ZONEMD record is the choice of a hash algorithm used to create the digest. RFC 8976 defines two standard hash algorithms – SHA-384 and SHA-512 – and a range of “private-use” algorithms.

Initially, the root zone’s ZONEMD record will have a private-use hash algorithm. This allows us to first include the record in the zone without anyone worrying about the validity of the digest values. Since the hash algorithm is from the private-use range, a consumer of the zone data will not know how to calculate the digest value. A similar technique, known as the “Deliberately Unvalidatable Root Zone,” was utilized when DNSSEC was added to the root zone in 2010.

After a period of more than two months, the ZONEMD record will transition to a standard hash algorithm.

Hash Algorithm

SHA-384 has been selected for the initial implementation for compatibility reasons.

The developers of BIND implemented the ZONEMD protocol based on an early Internet-Draft, some time before it was published as an RFC. Unfortunately, the initial BIND implementation only accepts ZONEMD records with a digest length of 48 bytes (i.e., the SHA-384 length). Since the versions of BIND with this behavior are in widespread use today, use of the SHA-512 hash algorithm would likely lead to problems for many BIND installations, possibly including some Root Server Operators.

Presentation Format

Distribution of the zone between the Root Zone Maintainer and Root Server Operators primarily takes place via the DNS zone transfer protocol. In this protocol, zone data is transmitted in “wire format.”

The root zone is also stored and served as a file on the internic.net FTP and web servers. Here, the zone data is in “presentation format.” The ZONEMD record will appear in these files using its native presentation format. For example:

. 86400 IN ZONEMD 2021101902 1 1 ( 7d016e7badfd8b9edbfb515deebe7a866bf972104fa06fec
e85402cc4ce9b69bd0cbd652cec4956a0f206998bfb34483 )

Some users of zone data received from the FTP and web servers might currently be using software that does not recognize the ZONEMD presentation format. These users might experience some problems when the ZONEMD record first appears. We did consider using a generic record format; however, in consultation with ICANN, we believe that the native format is a better long-term solution.

Schedule

Currently, we are targeting the initial deployment of ZONEMD in the root zone for September 13, 2023. As previously stated, the ZONEMD record will be published first with a private-use hash algorithm number. We are targeting December 6, 2023, as the date to begin using the SHA-384 hash algorithm, at which point the root zone ZONEMD record will become verifiable.

Conclusion

Deploying ZONEMD in the root zone helps to increase the security, stability, and resiliency of the DNS. Soon, recursive name servers that choose to serve root zone data locally will have stronger assurances as to the zone’s validity.

If you’re interested in following the ZONEMD deployment progress, please look for our announcements on the DNS Operations mailing list.

The post Adding ZONEMD Protections to the Root Zone appeared first on Verisign Blog.

This is the final in a multi-part series on cryptography and the Domain Name System (DNS).

In previous posts in this series, I’ve discussed a number of applications of cryptography to the DNS, many of them related to the Domain Name System Security Extensions (DNSSEC).

In this final blog post, I’ll turn attention to another application that may appear at first to be the most natural, though as it turns out, may not always be the most necessary: DNS encryption. (I’ve also written about DNS encryption as well as minimization in a separate post on DNS information protection.)

DNS Encryption

In 2014, the Internet Engineering Task Force (IETF) chartered the DNS PRIVate Exchange (dprive) working group to start work on encrypting DNS queries and responses exchanged between clients and resolvers.

That work resulted in RFC 7858, published in 2016, which describes how to run the DNS protocol over the Transport Layer Security (TLS) protocol, also known as DNS over TLS, or DoT.

DNS encryption between clients and resolvers has since gained further momentum, with multiple browsers and resolvers supporting DNS over Hypertext Transport Protocol Security (HTTPS), or DoH, with the formation of the Encrypted DNS Deployment Initiative, and with further enhancements such as oblivious DoH.

The dprive working group turned its attention to the resolver-to-authoritative exchange during its rechartering in 2018. And in October of last year, ICANN’s Office of the CTO published its strategy recommendations for the ICANN-managed Root Server (IMRS, i.e., the L-Root Server), an effort motivated in part by concern about potential “confidentiality attacks” on the resolver-to-root connection.

From a cryptographer’s perspective the prospect of adding encryption to the DNS protocol is naturally quite interesting. But this perspective isn’t the only one that matters, as I’ve observed numerous times in previous posts.

Balancing Cryptographic and Operational Considerations

A common theme in this series on cryptography and the DNS has been the question of whether the benefits of a technology are sufficient to justify its cost and complexity.

This question came up not only in my review of two newer cryptographic advances, but also in my remarks on the motivation for two established tools for providing evidence that a domain name doesn’t exist.

Recall that the two tools — the Next Secure (NSEC) and Next Secure 3 (NSEC3) records — were developed because a simpler approach didn’t have an acceptable risk / benefit tradeoff. In the simpler approach, to provide a relying party assurance that a domain name doesn’t exist, a name server would return a response, signed with its private key, “<name> doesn’t exist.”

From a cryptographic perspective, the simpler approach would meet its goal: a relying party could then validate the response with the corresponding public key. However, the approach would introduce new operational risks, because the name server would now have to perform online cryptographic operations.

The name server would not only have to protect its private key from compromise, but would also have to protect the cryptographic operations from overuse by attackers. That could open another avenue for denial-of-service attacks that could prevent the name server from responding to legitimate requests.

The designers of DNSSEC mitigated these operational risks by developing NSEC and NSEC3, which gave the option of moving the private key and the cryptographic operations offline, into the name server’s provisioning system. Cryptography and operations were balanced by this better solution. The theme is now returning to view through the recent efforts around DNS encryption.

Like the simpler initial approach for authentication, DNS encryption may meet its goal from a cryptographic perspective. But the operational perspective is important as well. As designers again consider where and how to deploy private keys and cryptographic operations across the DNS ecosystem, alternatives with a better balance are a desirable goal.

Minimization Techniques

In addition to encryption, there has been research into other, possibly lower-risk alternatives that can be used in place of or in addition to encryption at various levels of the DNS.

We call these techniques collectively minimization techniques.

Qname Minimization

In “textbook” DNS resolution, a resolver sends the same full domain name to a root server, a top-level domain (TLD) server, a second-level domain (SLD) server, and any other server in the chain of referrals, until it ultimately receives an authoritative answer to a DNS query.

This is the way that DNS resolution has been practiced for decades, and it’s also one of the reasons for the recent interest in protecting information on the resolver-to-authoritative exchange: The full domain name is more information than all but the last name server needs to know.

One such minimization technique, known as qname minimization, was identified by Verisign researchers in 2011 and documented in RFC 7816 in 2016. (In 2015, Verisign announced a royalty-free license to its qname minimization patents.)

With qname minimization, instead of sending the full domain name to each name server, the resolver sends only as much as the name server needs either to answer the query or to refer the resolver to a name server at the next level. This follows the principle of minimum disclosure: the resolver sends only as much information as the name server needs to “do its job.” As Matt Thomas described in his recent blog post on the topic, nearly half of all .com and .net queries received by Verisign’s .com TLD servers were in a minimized form as of August 2020.

Additional Minimization Techniques

Other techniques that are part of this new chapter in DNS protocol evolution include NXDOMAIN cut processing [RFC 8020] and aggressive DNSSEC caching [RFC 8198]. Both leverage information present in the DNS to reduce the amount and sensitivity of DNS information exchanged with authoritative name servers. In aggressive DNSSEC caching, for example, the resolver analyzes NSEC and NSEC3 range proofs obtained in response to previous queries to determine on its own whether a domain name doesn’t exist. This means that the resolver doesn’t always have to ask the authoritative server system about a domain name it hasn’t seen before.

All of these techniques, as well as additional minimization alternatives I haven’t mentioned, have one important common characteristic: they only change how the resolver operates during the resolver-authoritative exchange. They have no impact on the authoritative name server or on other parties during the exchange itself. They thereby mitigate disclosure risk while also minimizing operational risk.

The resolver’s exchanges with authoritative name servers, prior to minimization, were already relatively less sensitive because they represented aggregate interests of the resolver’s many clients¹. Minimization techniques lower the sensitivity even further at the root and TLD levels: the resolver sends only its aggregate interests in TLDs to root servers, and only its interests in SLDs to TLD servers. The resolver still sends the aggregate interests in full domain names at the SLD level and below², and may also include certain client-related information at these levels, such as the client-subnet extension. The lower levels therefore may have different protection objectives than the upper levels.

Conclusion

Minimization techniques and encryption together give DNS designers additional tools for protecting DNS information — tools that when deployed carefully can balance between cryptographic and operational perspectives.

These tools complement those I’ve described in previous posts in this series. Some have already been deployed at scale, such as a DNSSEC with its NSEC and NSEC3 non-existence proofs. Others are at various earlier stages, like NSEC5 and tokenized queries, and still others contemplate “post-quantum” scenarios and how to address them. (And there are yet other tools that I haven’t covered in this series, such as authenticated resolution and adaptive resolution.)

Modern cryptography is just about as old as the DNS. Both have matured since their introduction in the late 1970s and early 1980s respectively. Both bring fundamental capabilities to our connected world. Both continue to evolve to support new applications and to meet new security objectives. While they’ve often moved forward separately, as this blog series has shown, there are also opportunities for them to advance together. I look forward to sharing more insights from Verisign’s research in future blog posts.

Read the complete six blog series:

1. The Domain Name System: A Cryptographer’s Perspective
2. Cryptographic Tools for Non-Existence in the Domain Name System: NSEC and NSEC3
3. Newer Cryptographic Advances for the Domain Name System: NSEC5 and Tokenized Queries
4. Securing the DNS in a Post-Quantum World: New DNSSEC Algorithms on the Horizon
5. Securing the DNS in a Post-Quantum World: Hash-Based Signatures and Synthesized Zone Signing Keys
6. Information Protection for the Domain Name System: Encryption and Minimization

---

^{1. This argument obviously holds more weight for large resolvers than for small ones — and doesn’t apply for the less common case of individual clients running their own resolvers. However, small resolvers and individual clients seeking additional protection retain the option of sending sensitive queries through a large, trusted resolver, or through a privacy-enhancing proxy. The focus in our discussion is primarily on large resolvers.}

^{2. In namespaces where domain names are registered at the SLD level, i.e., under an effective TLD, the statements in this note about “root and TLD” and “SLD level and below” should be “root through effective TLD” and “below effective TLD level.” For simplicity, I’ve placed the “zone cut” between TLD and SLD in this note.}

Minimization et al. techniques and encryption together give DNS designers additional tools for protecting DNS information — tools that when deployed carefully can balance between cryptographic and operational perspectives.

The post Information Protection for the Domain Name System: Encryption and Minimization appeared first on Verisign Blog.

This is the fifth in a multi-part series on cryptography and the Domain Name System (DNS).

In my last article, I described efforts underway to standardize new cryptographic algorithms that are designed to be less vulnerable to potential future advances in quantum computing. I also reviewed operational challenges to be considered when adding new algorithms to the DNS Security Extensions (DNSSEC).

In this post, I’ll look at hash-based signatures, a family of post-quantum algorithms that could be a good match for DNSSEC from the perspective of infrastructure stability.

I’ll also describe Verisign Labs research into a new concept called synthesized zone signing keys that could mitigate the impact of the large signature size for hash-based signatures, while still maintaining this family’s protections against quantum computing.

(Caveat: The concepts reviewed in this post are part of Verisign’s long-term research program and do not necessarily represent Verisign’s plans or positions on new products or services. Concepts developed in our research program may be subject to U.S. and/or international patents and/or patent applications.)

A Stable Algorithm Rollover

The DNS community’s root key signing key (KSK) rollover illustrates how complicated a change to DNSSEC infrastructure can be. Although successfully accomplished, this change was delayed by ICANN to ensure that enough resolvers had the public key required to validate signatures generated with the new root KSK private key.

Now imagine the complications if the DNS community also had to ensure that enough resolvers not only had a new key but also had a brand-new algorithm.

Imagine further what might happen if a weakness in this new algorithm were to be found after it was deployed. While there are procedures for emergency key rollovers, emergency algorithm rollovers would be more complicated, and perhaps controversial as well if a clear successor algorithm were not available.

I’m not suggesting that any of the post-quantum algorithms that might be standardized by NIST will be found to have a weakness. But confidence in cryptographic algorithms can be gained and lost over many years, sometimes decades.

From the perspective of infrastructure stability, therefore, it may make sense for DNSSEC to have a backup post-quantum algorithm built in from the start — one for which cryptographers already have significant confidence and experience. This algorithm might not be as efficient as other candidates, but there is less of a chance that it would ever need to be changed. This means that the more efficient candidates could be deployed in DNSSEC with the confidence that they have a stable fallback. It’s also important to keep in mind that the prospect of quantum computing is not the only reason system developers need to be considering new algorithms from time to time. As public-key cryptography pioneer Martin Hellman wisely cautioned, new classical (non-quantum) attacks could also emerge, whether or not a quantum computer is realized.

Hash-Based Signatures

The 1970s were a foundational time for public-key cryptography, producing not only the RSA algorithm and the Diffie-Hellman algorithm (which also provided the basic model for elliptic curve cryptography), but also hash-based signatures, invented in 1979 by another public-key cryptography founder, Ralph Merkle.

Hash-based signatures are interesting because their security depends only on the security of an underlying hash function.

It turns out that hash functions, as a concept, hold up very well against quantum computing advances — much better than currently established public-key algorithms do.

This means that Merkle’s hash-based signatures, now more than 40 years old, can rightly be considered the oldest post-quantum digital signature algorithm.

If it turns out that an individual hash function doesn’t hold up — whether against a quantum computer or a classical computer — then the hash function itself can be replaced, as cryptographers have been doing for years. That will likely be easier than changing to an entirely different post-quantum algorithm, especially one that involves very different concepts.

The conceptual stability of hash-based signatures is a reason that interoperable specifications are already being developed for variants of Merkle’s original algorithm. Two approaches are described in RFC 8391, “XMSS: eXtended Merkle Signature Scheme” and RFC 8554, “Leighton-Micali Hash-Based Signatures.” Another approach, SPHINCS+, is an alternate in NIST’s post-quantum project.

Hash-based signatures can potentially be applied to any part of the DNSSEC trust chain. For example, in Figure 1, the DNS record sets can be signed with a zone signing key (ZSK) that employs a hash-based signature algorithm.

The main challenge with hash-based signatures is that the signature size is large, on the order of tens or even hundreds of thousands of bits. This is perhaps why they haven’t seen significant adoption in security protocols over the past four decades.

Synthesizing ZSKs with Merkle Trees

Verisign Labs has been exploring how to mitigate the size impact of hash-based signatures on DNSSEC, while still basing security on hash functions only in the interest of stable post-quantum protections.

One of the ideas we’ve come up with uses another of Merkle’s foundational contributions: Merkle trees.

Merkle trees authenticate multiple records by hashing them together in a tree structure. The records are the “leaves” of the tree. Pairs of leaves are hashed together to form a branch, then pairs of branches are hashed together to form a larger branch, and so on. The hash of the largest branches is the tree’s “root.” (This is a data-structure root, unrelated to the DNS root.)

Each individual leaf of a Merkle tree can be authenticated by retracing the “path” from the leaf to the root. The path consists of the hashes of each of the adjacent branches encountered along the way.

Authentication paths can be much shorter than typical hash-based signatures. For instance, with a tree depth of 20 and a 256-bit hash value, the authentication path for a leaf would only be 5,120 bits long, yet a single tree could authenticate more than a million leaves.

Returning to the example above, suppose that instead of signing each DNS record set with a hash-based signature, each record set were considered a leaf of a Merkle tree. Suppose further that the root of this tree were to be published as the ZSK public key (see Figure 2). The authentication path to the leaf could then serve as the record set’s signature.

The validation logic at a resolver would be the same as in ordinary DNSSEC:

• The resolver would obtain the ZSK public key from a DNSKEY record set signed by the KSK.
• The resolver would then validate the signature on the record set of interest with the ZSK public key.

The only difference on the resolver’s side would be that signature validation would involve retracing the authentication path to the ZSK public key, rather than a conventional signature validation operation.

The ZSK public key produced by the Merkle tree approach would be a “synthesized” public key, in that it is obtained from the records being signed. This is noteworthy from a cryptographer’s perspective, because the public key wouldn’t have a corresponding private key, yet the DNS records would still, in effect, be “signed by the ZSK!”

Additional Design Considerations

In this type of DNSSEC implementation, the Merkle tree approach only applies to the ZSK level. Hash-based signatures would still be applied at the KSK level, although their overhead would now be “amortized” across all records in the zone.

In addition, each new ZSK would need to be signed “on demand,” rather than in advance, as in current operational practice.

This leads to tradeoffs, such as how many changes to accumulate before constructing and publishing a new tree. Fewer changes and the tree will be available sooner. More changes and the tree will be larger, so the per-record overhead of the signatures at the KSK level will be lower.

Conclusion

My last few posts have discussed cryptographic techniques that could potentially be applied to the DNS in the long term — or that might not even be applied at all. In my next post, I’ll return to more conventional subjects, and explain how Verisign sees cryptography fitting into the DNS today, as well as some important non-cryptographic techniques that are part of our vision for a secure, stable and resilient DNS.

Read the complete six blog series:

1. The Domain Name System: A Cryptographer’s Perspective
2. Cryptographic Tools for Non-Existence in the Domain Name System: NSEC and NSEC3
3. Newer Cryptographic Advances for the Domain Name System: NSEC5 and Tokenized Queries
4. Securing the DNS in a Post-Quantum World: New DNSSEC Algorithms on the Horizon
5. Securing the DNS in a Post-Quantum World: Hash-Based Signatures and Synthesized Zone Signing Keys
6. Information Protection for the Domain Name System: Encryption and Minimization

Research into concepts such as hash-based signatures and synthesized zone signing keys indicates that these techniques have the potential to keep the Domain Name System (DNS) secure for the long term if added into the Domain Name System Security Extensions (DNSSEC).

The post Securing the DNS in a Post-Quantum World: Hash-Based Signatures and Synthesized Zone Signing Keys appeared first on Verisign Blog.

This is the third in a multi-part blog series on cryptography and the Domain Name System (DNS).

In my last post, I looked at what happens when a DNS query renders a “negative” response – i.e., when a domain name doesn’t exist. I then examined two cryptographic approaches to handling negative responses: NSEC and NSEC3. In this post, I will examine a third approach, NSEC5, and a related concept that protects client information, tokenized queries.

The concepts I discuss below are topics we’ve studied in our long-term research program as we evaluate new technologies. They do not necessarily represent Verisign’s plans or position on a new product or service. Concepts developed in our research program may be subject to U.S. and international patents and patent applications.

NSEC5

NSEC5 is a result of research by cryptographers at Boston University and the Weizmann Institute. In this approach, which is still in an experimental stage, the endpoints are the outputs of a verifiable random function (VRF), a cryptographic primitive that has been gaining interest in recent years. NSEC5 is documented in an Internet Draft (currently expired) and in several research papers.

A VRF is like a hash function but with two important differences:

1. In addition to a message input, a VRF has a second input, a private key. (As in public-key cryptography, there’s also a corresponding public key.) No one can compute the outputs without the private key, hence the “random.”
2. A VRF has two outputs: a token and a proof. (I’ve adopted the term “token” for alignment with the research that I describe next. NSEC5 itself simply uses “hash.”) Anyone can check that the token is correct given the proof and the public key, hence the “verifiable.”

So, it’s not only hard for an adversary to reverse the VRF – which is also a property the hash function has – but it’s also hard for the adversary to compute the VRF in the forward direction, thus preventing dictionary attacks. And yet a relying party can still confirm that the VRF output for a given input is correct, because of the proof.

How does this work in practice? As in NSEC and NSEC3, range statements are prepared in advance and signed with the zone signing key (ZSK). With NSEC5, however, the range endpoints are two consecutive tokens.

When a domain name doesn’t exist, the name server applies the VRF to the domain name to obtain a token and a proof. The name sever then returns a range statement where the token falls within the range, as well as the proof, as shown in the figure below. Note that the token values are for illustration only.

Because the range statement reveals only tokenized versions of other domain names in a zone, an adversary who doesn’t know the private key doesn’t learn any new existing domain names from the response. Indeed, to find out which domain name corresponds to one of the tokenized endpoints, the adversary would need access to the VRF itself to see if a candidate domain name has a matching hash value, which would involve an online dictionary attack. This significantly reduces disclosure risk.

The name server needs a copy of the zone’s NSEC5 private key so that it can generate proofs for non-existent domain names. The ZSK itself can stay in the provisioning system. As the designers of NSEC5 have pointed out, if the NSEC5 private key does happen to be compromised, this only makes it possible to do a dictionary attack offline— not to generate signatures on new range statements, or on new positive responses.

NSEC5 is interesting from a cryptographer’s perspective because it uses a less common cryptographic technique, a VRF, to achieve a design goal that was at best partially met by previous approaches. As with other new technologies, DNS operators will need to consider whether NSEC5’s benefits are sufficient to justify its cost and complexity. Verisign doesn’t have any plans to implement NSEC5, as we consider NSEC and NSEC3 adequate for the name servers we currently operate. However, we will continue to track NSEC5 and related developments as part of our long-term research program.

Tokenized Queries

A few years before NSEC5 was published, Verisign Labs had started some research on an opposite application of tokenization to the DNS, to protect a client’s information from disclosure.

In our approach, instead of asking the resolver “What is <name>’s IP address,” the client would ask “What is token 3141…’s IP address,” where 3141… is the tokenization of <name>.

(More precisely, the client would specify both the token and the parent zone that the token relates to, e.g., the TLD of the domain name. Only the portion of the domain name below the parent would be obscured, just as in NSEC5. I’ve omitted the zone information for simplicity in this discussion.)

Suppose now that the domain name corresponding to token 3141… does exist. Then the resolver would respond with the domain name’s IP address as usual, as shown in the next figure.

In this case, the resolver would know that the domain name associated with the token does exist, because it would have a mapping between the token and the DNS record, i.e., the IP address. Thus, the resolver would effectively “know” the domain name as well for practical purposes. (We’ve developed another approach that can protect both the domain name and the DNS record from disclosure to the resolver in this case, but that’s perhaps a topic for another post.)

Now, consider a domain name that doesn’t exist and suppose that its token is 2718… .

In this case, the resolver would respond that the domain name doesn’t exist, as usual, as shown below.

But because the domain name is tokenized and no other information about the domain name is returned, the resolver would only learn the token 2718… (and the parent zone), not the actual domain name that the client is interested in.

The resolver could potentially know that the name doesn’t exist via a range statement from the parent zone, as in NSEC5.

How does the client tokenize the domain name, if it doesn’t have the private key for the VRF? The name server would offer a public interface to the tokenization function. This can be done in what cryptographers call an “oblivious” VRF protocol, where the name server doesn’t see the actual domain name during the protocol, yet the client still gets the token.

To keep the resolver itself from using this interface to do an online dictionary attack that matches candidate domain names with tokens, the name server could rate-limit access, or restrict it only to authorized requesters.

Additional details on this technology may be found in U.S. Patent 9,202,079B2, entitled “Privacy preserving data querying,” and related patents.

It’s interesting from a cryptographer’s perspective that there’s a way for a client to find out whether a DNS record exists, without necessarily revealing the domain name of interest. However, as before, the benefits of this new technology will be weighed against its operational cost and complexity and compared to other approaches. Because this technique focuses on client-to-resolver interactions, it’s already one step removed from the name servers that Verisign currently operates, so it is not as relevant to our business today in a way it might have been when we started the research. This one will stay under our long-term tracking as well.

Conclusion

The examples I’ve shared in these last two blog posts make it clear that cryptography has the potential to bring interesting new capabilities to the DNS. While the particular examples I’ve shared here do not meet the criteria for our product roadmap, researching advances in cryptography and other techniques remains important because new events can sometimes change the calculus. That point will become even more evident in my next post, where I’ll consider the kinds of cryptography that may be needed in the event that one or more of today’s algorithms is compromised, possibly through the introduction of a quantum computer.

Read the complete six blog series:

1. The Domain Name System: A Cryptographer’s Perspective
2. Cryptographic Tools for Non-Existence in the Domain Name System: NSEC and NSEC3
3. Newer Cryptographic Advances for the Domain Name System: NSEC5 and Tokenized Queries
4. Securing the DNS in a Post-Quantum World: New DNSSEC Algorithms on the Horizon
5. Securing the DNS in a Post-Quantum World: Hash-Based Signatures and Synthesized Zone Signing Keys
6. Information Protection for the Domain Name System: Encryption and Minimization

The post Newer Cryptographic Advances for the Domain Name System: NSEC5 and Tokenized Queries appeared first on Verisign Blog.