DNSSEC: The Long and Bumpy Road of Algorithm Deployment

DNS Security Extensions (DNSSEC) support a range of cryptographic signing algorithms, from modern Edwards curve-based algorithms such as Ed25519, to DSA/SHA1 from the 1990s.

These algorithms are at the heart of DNSSEC, but need to be replaced occasionally. For example, improved cryptoanalysis could render an algorithm insecure. Even worse, a quantum computer, applying Shor’s algorithm, could break all algorithms standardised for DNSSEC within polynomial time.

This replacement process can take a long time, first as it goes through the standardisation process in the IETF, then the support process in DNS software, registries and registrars. In this post, my co-authors and I from SIDN Labs, NLnet Labs, and Virginia Tech, take a look at this long journey to understand the barriers and how to transition to more secure algorithms faster in the future.

Cryptographic Signing Algorithms

Step 1: Standardising a new algorithm

Before an algorithm can be used in DNSSEC, it needs to be standardised in the IETF as an RFC (for example, RFC 8080 for Ed25519).

In the past, standardising new algorithms took between one and four years. Studying the mailing list archives of the IETF, we found that, in general, algorithms have a higher chance of getting standardised if they bring some improvement. This could be better security, better performance or smaller signatures.

Step 2: Getting the algorithm into software

Ultimately, DNS software needs to be able to use a new algorithm for signing (for example, OpenDNSSEC), while resolvers (for example, Unbound or Knot) need to be able to validate the signatures.

DNS software relies on libraries to perform these cryptographic functions; OpenSSL and GnuTLS are the most common ones. Only if these libraries support a new algorithm will DNS software be able to work with them. These libraries can thus become a roadblock to deploy a new algorithm.

Step 3: Getting the algorithm in operation

Unfortunately, they are not the only roadblocks. DNS operators, registrars and registries need to support the new algorithm: all of them need to publish the public key or a hash of the key in order to enable resolvers to validate the signature.

In the case of the most recent addition to the DNSSEC algorithm family, Ed25519 and Ed448, this support has lagged substantially. More than three years after their standardisation, they are available through the most popular crypto libraries, but are still not supported by many of the most popular DNS operators and registrars, including registries responsible for Top-Level-Domains (TLDs). This means their customers cannot upgrade to Ed25519 or Ed448, even though it is expected that Ed25519 will become the recommend default algorithm.

Owners of .nl domain names can already deploy Ed25519 today, if their registrar supports the algorithm as well.

How Long Does All of That Take?

After jumping through all these hoops, the next question is how long it takes until domains are actually using a new algorithm and how long until resolvers are able to validate it?

To answer these questions, we had a look at the number of domain names signed with ECDSAP256 under the TLDs .com, .net, .org, .nl and .se. To do so, we used data collected by the measurement platform OpenINTEL. In Figure 1 you can see that it took more than 4½ years after its standardisation in 2012 until the first 100,000 domain names were signed with this algorithm.

Figure 1 — Number of domain names signed with ECDSAP256, since work started on its draft in 2011. 

The big drivers were large DNS operators that started signing all their domain names with ECDSAP256, resulting in jumps in adoption, even though the early adopters of this algorithm were small providers.

Figure 2 — Share of resolvers able to validate Ed25519 and Ed448. Support is measured with RIPE Atlas and you can find the most recent numbers here.

Furthermore, most resolvers are not able to validate new algorithms immediately because upgrading also takes time (see Figure 2). This data is collected with more than 10,000 RIPE Atlas probes. For Ed25519, 72% of validating resolvers in our dataset support this new algorithm, 3½ years after its standardisation in April 2017. This is despite the fact that all major DNS resolver vendors have supported this algorithm at least since the beginning of 2018.

Domain name operators interested in deploying Ed25519, therefore, might want to wait a bit longer until resolver support is closer to 100%. Otherwise, their domain names will not be optimally protected. Test which algorithms your resolver currently supports via the Root Canary Project. 

Rolling Signing Algorithms

In general, we found evidence that transitioning from one algorithm to another is still perceived as a barrier by domain operators. These so called ‘algorithm rollovers’ can cause outages when not carried out carefully. For example, we saw domain names first turning off DNSSEC signing altogether before signing with ECDSAP256.

Some domain names are still signed with algorithms that rely on SHA-1, which has been considered insecure for quite some time now. We believe that rolling to a different algorithm is perceived as too big of a barrier, but also that some operators still lack the incentive to move towards more secure algorithms. Most resolvers still consider these algorithms secure, but this might change in the near future.

How to Get a New Algorithm Deployed

Keeping these observations in mind, what are the main success factors for getting an algorithm deployed?

First, the Internet community should trust the new algorithm. For example, it helps if an algorithm is already used in other protocols like TLS, which increases the chance that the standardisation of DNSSEC goes through smoothly.

Second, DNS operators, registrars and registries should be encouraged by the community to support the new algorithm as well. If they see that there is demand, the chance that they will add support becomes higher. On the other side, DNS operators should strive for optimal security and, therefore, should keep their systems and domain names up to date.

Third, replacing an algorithm with another at a domain name must become as easy as possible. Luckily, as DNS software has become more advanced it can now automate most parts of an algorithm rollover. Mechanisms like CDS/CDNSKEY could simplify this process further but are not yet as well supported.

Implications of Quantum-safe Algorithms

Currently, the standardisation organisation NIST is assessing new algorithms that can neither be broken by current computers nor by quantum computers.

All our findings hold for these, so called, quantum-safe algorithms as well, with one additional caveat: the quantum-safe algorithms that currently have the highest chance of getting standardised by NIST have significantly larger keys, signatures or both, compared to the algorithms. We still need to understand how we can apply these algorithms in DNSSEC, and carried out a first analysis in another study.

We will flesh out this work further in 2021 through an operational testbed. Learn more about our study in our Internet Measurement Conference 2020 paper.