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. The majority of domain names today are either signed with RSA/SHA-256 or ECDSA and this is also the case for domain names under .nl, as can be seen in Figure 1.

Figure 1: Algorithms used by domain names under .nl. See stats.sidnlabs.nl for most recent numbers.

These algorithms 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. The 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 more quickly in the future.

Cryptographic signing algorithm

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 deployment of a new algorithm.

Step 3: Getting the algorithm into 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 today deploy Ed25519, if their registrars support the algorithm as well.

How long does all of that take?

After jumping through all those 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 those 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 2 — 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 3 — Share of resolvers able to validate ED25519 and ED448. Support is measured with RIPE Atlas and the most recent numbers can be found here.

Furthermore, most resolvers are not able to validate new algorithms immediately because upgrading also takes time (see Figure 3). The data presented in the graph was 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. And this 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. You can test which algorithms your resolver currently supports with this test at rootcanary.org.

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 to be too difficult by some operators, while others 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?

In view of the observations set out above, 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 hand, DNS operators should strive for optimal security and therefore should keep their systems and domain names up to date. Third, replacing the algorithm used for a domain name with another must be made 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 on quantum-safe algorithms

Currently, the standardisation organisation NIST is assessing new algorithms, which 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 than current algorithms. We still need to understand how we can apply these algorithms in DNSSEC, and we carried out a first analysis in another study. We will further flesh out this work in 2021 through an operational testbed. Learn more about our study in our Internet Measurement Conference 2020 paper. An edited version of this article has also been published at apnic.net and ripe.net..