Internet-Draft PQC-DNSSEC-RESEARCH-AGENDA September 2023
Fregly, et al. Expires 29 March 2024 [Page]
Network Working Group
Intended Status:
A.M. Fregly
Verisign Labs
R. van Rijswijk-Deij
DACS group, EEMCS, University of Twente
M. Müller
P. Thomassen
C. Schutijser
T. Chung
Virginia Tech

Research Agenda for a Post-Quantum DNSSEC


This document describes a notional research agenda for collaborative multi-stakeholder research related to a future post-quantum DNSSEC ecosystem. It is inspired by the anticipation that adoption of Post-Quantum signature algorithms will have enough operational impact on DNSSEC that either DNS protocol enhancements will be needed, or DNS will move away from UDP as the prevalent DNS transport, or a combination of both will be needed. Some members of the DNS technical community have even suggested evaluating alternatives to DNSSEC and potentially adopting an alternative protocol or practices to assure the integrity of DNS responses. Given the potential impact of such changes on the DNS ecosystem, the authors believe collaborative multi-stakeholder research into the impact of proposed changes should be performed to inform adoption and standardization activities.

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

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 29 March 2024.

1. Conventions Used in This Document

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.

2. Introduction

  • This document supplements concepts described in RFC 7696, "Guidelines for Cryptographic Algorithm Agility and Selecting Mandatory-to-Implement Algorithms" [RFC7696], by defining a research agenda to support both algorithm selection and selection of operational and infrastructure changes related to the adoption of Post-Quantum Cryptographic (PQC) signature algorithms for DNSSEC.
  • DNSSEC needs cryptographic agility and resiliency that addresses the long lead time to roll out new algorithms.
  • NIST’s currently chosen PQC signature algorithms may have significant size impact on DNSSEC, transport, memory, and processing.
  • There are multiple approaches for addressing the issues PQC algorithms present to DNSSEC with significant pros and cons for these approaches.
  • Collaborative multi-stakeholder involvement in research and modeling is desirable to inform the DNSSEC PQC standardization and transition agenda.
  • The IETF and industry processes for introducing new algorithms into DNSSEC and deprecating them involve the following steps. First, zone signers need to implement the new signature algorithm. Next, validation software needs to implement the corresponding signature verification algorithm. When these are pervasive, then the IETF can make that algorithm a DNSSEC mandatory-to-implement algorithm. As an algorithm ages, the parameters for the algorithm may be adjusted to keep pace with advances in computing capabilities. Eventually, the IETF may stop recommending the algorithm and consequently the algorithm is deprecated and eventually removed from zone signing software and validation software used by zone signers and validators.
  • Given these drivers and considerations, the authors of this agenda are submitting this document with the intention that it be considered relative to research and modeling to inform standards activities related to adoption of post-quantum digital signature algorithms into DNSSEC.

3. Issues Post-Quantum Signature Algorithms Present to DNSSEC

The currently selected NIST PQC digital signature algorithms have characteristics that will present challenges for adoption into DNSSEC. These challenges seem likely to inspire changes to DNS and DNSSEC related protocols, network infrastructure, hardware capacities, and operational practices due to:

  • Size of cryptographic materials in transport
  • Processing time for cryptographic operations
  • Memory footprint for cryptographic operations

Of these challenges, signature size is perhaps the most challenging. In DNSSEC, signatures typically comprise by far the majority of DNSSEC related response data and consequently their size has a larger impact than public key sizes. Large signatures are an issue due to UDP being the prevalent transport for DNS and relative to DNS response sizes, especially over IPv6. Per [DNSFLAG2020], "An EDNS buffer size of 1232 bytes will avoid fragmentation on nearly all current networks. This is based on an MTU of 1280, which is required by the IPv6 specification, minus 48 bytes for the IPv6 and UDP headers and the aforementioned research." Signed NSEC and NSEC3 responses containing two or three signatures respectively and signed with the NIST selected algorithm with the smallest signature size, FALCON 512 (at 666 bytes per signature), would result in packets whose size exceeds the required minimum MTU for IPv6, resulting in fragmented or truncated responses for networks that support no more than the minimum.

There are methods of dealing with responses that are too big, such as sending fragmented responses or having a DNS query retried over TCP. Research has shown that these methods, designed for "slightly oversized" messages, increase latency, are prone to failure, lack universal support, and their suitability for responses that are (possibly) O(10^2) times a classical DNS message is unclear. Besides, there are other potential transport options such as TLS and QUIC. However, given the massive footprint of DNS and need for transport support across that footprint, a move away from plain UDP as the prevalent transport should be carefully considered due to a number of factors including an expected extended transition period, operational considerations and costs.

In addition to transport impact, larger signature sizes will have significant impact on in-memory caches of resolvers and in-memory databases used by authoritative nameservers for large zones. In an example using a fully signed TLD with the following characteristics:

  • NS RRs comprise nearly 100% of non-DNSSEC-related RRs
  • NS RRsets have an average of 2.4 NS RRs and an average record length of 53 bytes
  • For each domain, there is one RR for both DS and NSEC3 and one RRset for each
  • There is one RRSIG for each DS and NSEC3 RRset

In this example, if the zone was signed with SPHINCS+ 128s, signatures would comprise over 99% of the size of the zone file. This would increase the zone file size by a factor of 67 relative to a zone signed with ECDSA-256 and by a factor of 37 relative to a zone signed with RSA 1280.

CPU processing requirements may also increase significantly for some PQC algorithms though this issue is of less concern than the issues presented by signature sizes. For example, in DNSSEC signatures are not typically generated "on the fly", but rather are generated in batches by a provisioning system. It can be anticipated that by the time PQC algorithms have been deployed, advances in CPUs, GPUs, and specialized processors should address the performance impacts of PQC algorithms. In some cases such as for verification on legacy low-powered devices with limited CPU capacity, CPU processing may be a consideration.

Taking into consideration the above factors, addressing the impact on DNSSEC of PQC signature sizes on DNSSEC should be a primary focus for algorithm research, impact analysis, transition planning, and standardization activities.

4. Notional Changes to DNSSEC to Address the Impact of Post-Quantum Algorithms

  • Smaller: This approach seeks to find ways to lower the size of PQC signatures. While there is some chance that NIST may in the future select a PQC signature algorithm that has small signatures and reasonable processing requirements, the algorithm would likely need a long period of evaluation and implementation prior to broad adoption. An alternative approach would be to define methods that minimize the size impact of the current NIST PQC signature schemes by using them in a different way [MTLMODEID].
  • Selective - Algorithm Negotiation based on concepts described in [NEGOTIATION]. This approach provides a mechanism for reducing response sizes when a zone has multiple DNSSEC keys of different algorithms, as is likely during the transition to PQC. When this occurs, the DNSSEC responses would become even larger due to including both traditional and PQC signatures (and possibly multiple PQC signature algorithms if there isn't yet a common choice supported by all verifiers). Algorithm Negotiation gives the flexibility for the verifier to specify which algorithms it supports and receiving back signatures selected based on those choices.
  • Shift - This approach seeks to shift the transport of keys and signatures to out-of-band processing. This could include approaches like pushing DNSSEC data to widely distributed servers or using session-based transports to interact with servers that are optimized for delivering DNSSEC data over session-based transports.
  • Skip - This approach seeks to minimize the need to retrieve DNSSEC data interactively. Resolvers might do this by performing proactive caching of DNSSEC data. For instance, a resolver might proactively request DNSSEC data who's TTL has expired based on prior history showing this data is highly likely to be requested. Another approach might be for a resolver to indicate what DNSSEC data it is holding and then only receive DNSSEC data if the data held by the resolver is not current.
  • Split - This approach splits DNSSEC data across multiple RRs, each of which can then be retrieved separately [FRAG].
  • Sessions - This approach would involve moving away from UDP as the prevalent transport for DNS and moving to a session-based protocol such as TCP, TLS or QUIC.
  • Supplant - This approach would involve replacing DNSSEC with some other mechanism that authenticates DNS responses.

5. Proposed Research Activities

The described notional approaches plus others that may come to light could have significant impact on: devices; DNSSEC-related protocols; software used in devices; software used in resolvers; software used in authoritative nameservers; network considerations; performance; transition planning; operational considerations; resources needed for DNSSEC-related processing. It would be prudent to gain a detailed understanding of these impacts prior to creating and adopting standards or beginning a transition to a PQC DNSSEC. This understanding could be gained by means of a collaborative multi-stakeholder research agenda. This agenda might be comprised of:

  • Deployment Analytics: device types and characteristics; roles (stub, resolver, authoritative nameserver); algorithms; environmental constraints such as network limitations; software used for resolution and nameserver operations; resolver in-memory cache sizes; authoritative nameserver in-memory database sizes; zone sizes relative to memory impact; zone composition; supportable transports
  • UDP Networking Path MTU Analytics: stub to resolver; resolver to resolver; resolver to authoritative
  • Analyze DNS/DNSSEC Query and Response Traffic: stub to resolver; resolver to resolver; resolver to authoritative nameserver:

    • Query and Response Analytics: composition, size, and response times of DNS queries and responses including details for overall traffic and DNSSEC-related traffic; transport protocols
    • Caching: caching algorithms, cache composition, effectiveness
    • Truncation and Fragmentation Analysis: overall traffic; DNSSEC related traffic; failures; retries. This analysis is pertinent to understanding and modeling the impact failures and retries would have on DNS performance. For instance, retries over TCP result in a DNS query / response cycle requiring extra round trips with consequent increase in DNS resolution time.
    • DNS response time impact for common use cases (browsing, web services, mobile, IoT,...). It will likely take some creative approaches to broadly assess this so that results are reflective of “real” user experience.
    • Session Based Protocols: percentage of traffic; response times; session setup and teardown metrics; failures; session state/resource management including as a potential denial of service vector.
  • Analyze Zones Based on Domain Level (root, TLD, lower levels)

    • DNSSEC related RRs
    • signature algorithms
    • frequency of updates
    • zone signing metrics.

6. Research Questions

The research is designed to provide the data needed to answer questions such as the following:

  • What is the footprint of resolver software across the DNS ecosystem - metrics on what software and versions are deployed?
  • How can resolvers be categorized and identified according to how likely and quickly they might be updated to handle protocol changes? What are the factors that impact this: cost, administrative limitations, firmware limitations, device limitations?
  • What is the footprint of crypto libraries across the DNS ecosystem?
  • How can we categorize and identify DNS software across the DNS ecosystem relative to how it may be updated to handle protocol changes? What are the factors that impact this: cost, administrative limitations, firmware limitations, devices limitations?
  • What is the split between traffic sent to resolvers versus traffic sent to authoritative nameservers?
  • What is the footprint of forwarding resolver to resolver traffic?
  • Where are the network devices that constrain UDP MTUs - network borders, Internet routing infrastructure, resolvers, authoritative servers?
  • What would be the impact to legacy DNS components for various transition strategies (IoT/embedded devices, locations with a history of being slow to upgrade, locations where change control policies slow implementation of updates, resource constrained locations; locations with a lack of expertise,...)?
  • What are the networks that cannot be upgraded or for which network upgrades would be hard: embedded, IoT, wireless? What are the characteristics for how devices on these networks interact with resolvers?

7. Research Driven Modeling

This described research agenda would provide answers to the research questions and lead to a baseline understanding of the overall DNSSEC ecosystem that would be impacted by DNSSEC-related standards and technology changes to support PQC algorithm adoption. This understanding could then enable modeling of the impacts of various approaches for a PQC DNSSEC. Desirable modeling might include:

  • Projecting impacts: to processing, network requirements, costs, and dependencies
  • Impact of PQC algorithms
  • Impact of proposed protocol changes
  • Snapshot projections for future points in time
  • Baseline timeline for DNS ecosystem components

8. IANA Considerations

This document does not specify any instructions for IANA

10. References

10.1. Normative References

Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, , <>.
Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, , <>.

10.2. Informative References

dns-violations, "DNS Flag Day 2020", , <>.
Goertzen, J. and D. Stebila, "Post-Quantum Signatures in DNSSEC via Request-Based Fragmentation", , <>.
Harvey, J., Kaliski, B., Fregly, A.M., and S. Sheth, "Merkle Tree Ladder Mode (MTL) Signatures", , <>.
Huque, S., Kerr, S., and H. Shulman, "Algorithm Negotiation in DNSSEC", , <>.
Housley, R., "Guidelines for Cryptographic Algorithm Agility and Selecting Mandatory-to-Implement Algorithms", BCP 201, RFC 7696, DOI 10.17487/RFC7696, , <>.

Appendix A. Acknowledgements

The authors would like to acknowledge the following individuals for their contributions to the development of this document: Sofía Celi, Paul Hoffman, Scott Hollenbeck, Russ Housley, Geoff Huston, Burt Kaliski, Sean Turner, Duane Wessels

Appendix B. Change Log

Initial draft

Authors' Addresses

Andrew Fregly
Verisign Labs
12061 Bluemont Way
Reston, VA 20190
United States of America
Roland Martijn van Rijswijk-Deij
DACS group, EEMCS, University of Twente
Moritz Müller
Meander 501
6825 MD Arnhem
Peter Thomassen
Kyffhäuserstraße 5
10781 Berlin
Caspar Schutijser
Meander 501
6825 MD Arnhem
Taejoong Chung
Virginia Tech
2228 KnowledgeWorks II
Blacksburg, Virginia 24061
United States of America