Two years ago, we had our first guest blog post, about FALCON-512 in PowerDNS. We are happy to now present a followup guest post on Post-Quantum Cryptography in DNSSEC.
Authors: Jason Goertzen, David Joseph, Peter Thomassen
The DNS protocol is the internet’s phonebook. Send off a domain name, and receive an IP address, to which all further communications can be sent. Validating the authenticity of that IP address requires cryptography, however, and this is where DNSSEC comes in. But the cryptography used to sign domain name/IP address pairs – known as records – will be vulnerable to quantum computers once they are available, and thus faces the same complex transition to post-quantum cryptography (PQC) as the rest of the internet.
Even if estimates for Q-day (potentially within a decade or two) might seem optimistic, rolling out new DNSSEC signing schemes is a complex and lengthy process. The PQC algorithms themselves are on the cusp of being standardized by NIST, after an 8-year process, and folks around IETF are just now starting to research how to ready DNSSEC for the quantum threat. These new PQC algorithms have much larger signatures and keys which could cause delivery issues if the DNS protocol is not adapted for these needs. Clearly we need to investigate …
In a continuation of earlier experiments with Falcon-512 in PowerDNS, deSEC and SandboxAQ have been evaluating for the past year how PQC would behave if it were slotted in with no additional protocol changes. This involved deploying zones – portions of the DNS namespace managed by a specific organization – signed with Falcon, Dilithium, SPHINCS+, as well as the stateful hash-based signature scheme XMSS. In order to deploy these zones, we modified BIND 9 and PowerDNS to support all of these algorithms. In this post we’ll look at PowerDNS, noting that the modifications to both implementations are rather similar.
In order to add support for the PQC algorithms, we took advantage of the open source project Open Quantum Safe. Open Quantum Safe provides a library called liboqs which contains the PQC algorithms selected by NIST for standardization. The project also offers an OpenSSL 3 provider (“oqs-provider”) which exposes those algorithms via the OpenSSL API. We ultimately used oqs-provider as the other DNSSEC algorithms were already using the OpenSSL API. Once one of the algorithms was added, supporting others was easy. We've published the source code on GitHub.
Stateful hash-based signatures are a special type of PQC, already standardized. In contrast to the other signing schemes we tested, signers have to carefully track a “state” (in essence, a counter), whose value must change with every invocation so as to not break security. In principle, they’ll work well for some applications, including DNSSEC, but the complexities of tracking state make them impractical for use cases like load balancers signing TLS transcripts. In order to test these types of signatures, we concentrated on the performance impact, and did not worry too much about managing this state correctly. (In other words, we allowed ourselves to insecurely reuse state, and the signatures implemented this way do not provide authenticity; however, they are perfectly suitable for investigating protocol-related performance aspects like deliverability.)
Liboqs is also in the process of adding support for stateful hash-based signatures. This study is the first project that is utilizing the new stateful signatures API. However, since this API is so new, oqs-provider does not support stateful signatures. This means that we had to use the low level API provided by liboqs instead. The API worked as expected, so it wasn’t too much effort to add XMSS and XMSSMT directly to the software.
Key generation did require special treatment, however, so we made a small change. Stateful hash-based signature schemes can generate a limited number of signatures, and zone operators would likely want to be able to pick the appropriate parameter set for their zone size. Both for XMSS and XMSSMT there are a plethora of parameter sets. The more signatures you wish to allow, the larger they become. In practice, it’s likely that operators of smaller zones would prefer to use parameter sets that support fewer signatures and benefit from smaller signature sizes. However, if a parameter set was standardized and the number of signatures it generated was too small, it would prevent operators of large zones from deploying XMSS or XMSSMT.
It would not be reasonable to have a DNSSEC algorithm number standardized for each parameter set (12 sets for XMSS and 16 for XMSSMT). Therefore, we took a similar approach to RSA modulus sizes: “Support all of the parameter sets of XMSS and XMSSMT, or you aren’t compliant”. Our implementation differentiates between parameter sets based on information stored within the DNSKEY. The nice thing is that liboqs does this for us by hiding an internal OID into both the secret and public keys, requiring only the introduction of the corresponding mappings to translate between the XMSS/XMSSMT parameter sets and DNSSEC algorithm numbers without losing the specific parameter details.
We added a custom function to PowerDNS’s DNSSECKeeper. This function takes the specified algorithm name, and if it is a type of XMSS or XMSSMT, converts the algorithm name to the generic XMSS or XMSSMT name and returns the internal OID associated with the target parameter set. This OID is then passed to the key generation function to specify the specific parameter set requested.
In order to evaluate how these quantum-resistant signature algorithms perform in real world DNS, we deployed several zones, each one signed by one classical or quantum-resistant algorithm. The PowerDNS-operated test zones were set up with a CSK scheme with dynamic signing (in contrast to the BIND zones which used a KSK/ZSK presigned setup).
We then deployed experiments across the RIPE ATLAS network. This is a network of roughly 10,000 small nodes distributed across the globe, which researchers can use to run various kinds of network-related measurements.
To run DNSSEC experiments, the PowerDNS nameserver was located in Finland, and clients from across the RIPE ATLAS network submitted DNS requests using their locally configured resolver(s), receiving PQC-enabled responses. We then looked into how many responses arrived and what their properties were, depending on algorithm, transport and the like.
We find that in general, measurement results are quite noisy. We therefore applied pre-filtering, ignoring individual results from probe-resolver combinations that answered incorrectly for the zone signed with algorithm 8 (RSASHA256). (A correct response required the expected A record, or NXDOMAIN, depending on the case.) The pre-filter did not include a requirement for the AD bit, i.e., resolvers not performing validation were acceptable as long as the response appeared correct in terms of return code and record content.
The following two figures show results from PowerDNS-operated zones for an existing name (Fig. 1) and a non-existing name (Fig. 2), with the aforementioned pre-filter applied. The two quadrants at the top are for probes querying their resolver via UDP, and the ones at the bottom via TCP. Only for queries on the right, the DO bit was set.
Figure 1: Results for an existing name.
Figure 2: Results for a non-existing name. NSEC3 is indicated by a “3” suffix; otherwise NSEC is used.
As can be seen, nearly all resolvers appear to be compatible with algorithms 8, 13, and 15, independently of transport and DO bit, for both NSEC and NSEC3 setups. This is no surprise for algorithm 8 (due to the pre-selection), and also expected for algorithm 13 (which some TLDs have deployed, presumably after verifying interoperability). For algorithm 15, we were less certain ahead of time, but it’s good to see that it does not appear to cause problems. (For numbers on actual validation support, see Fig. 4 below.)
Regarding PQC, it can be clearly seen that response delivery rates go down significantly as response sizes increase. This most prominently applies along the algorithm dimension, where the largest packet involved in a resolution happens to correlate with the algorithm numbers we chose – as a result, SERVFAIL responses become more frequent for SPHINCS+ and XMSS-type algorithms than for Dilithium2. Falcon, having the smallest signatures, appears to have the fewest issues.
It appears that many resolvers don’t obtain DNSSEC records by default (perhaps because validation is turned off, or because the zone’s DS record already indicates an unsupported algorithm). Only when setting the DO bit to request the resolver to obtain these records do larger packets occur, and deliverability problems might get worse. Whether that really is the case depends on whether the increase in packet size is such that a particular deliverability barrier (such as MTU) is exceeded. It appears that this mostly affects TCP scenarios for SPHINCS+ and XMSS (and somewhat Dilithium2), nullifying the benefit that those algorithms otherwise enjoy from using this transport when the DO bit is absent.
Similar considerations apply to NSEC vs. NSEC3, where transmission boundaries may be crossed depending on the case. In the scenarios we evaluated, this does not appear to have significant effects, except in the case of XMSS, where the SERVFAIL rate in the worst case goes from 19.9% to 51.6% when using NSEC3 (TCP, no DO bit).
Taking a slightly different perspective, Fig. 3 shows the frequency of correct (0) vs. incorrect (1) responses (for an existing name). While correct fractions for conventional algorithms are very close to 100% in all cases, PQC algorithms again show dependency on packet sizes as mediated by the choice of transport and DO bit, and in line with expectations. In particular, when the DO bit is not set, going from UDP to TCP increases success rates for SPHINCS+ and XMSS from around 80% to around 90%, with Dilithium2 going from 89.1% to 93.2% and Falcon from 97.4% to 98.5%. A similar trend is observed when the DO bit is present, except that overall numbers are lower, going from 50% to around 80–90% when going from UDP to TCP. The exception is again Falcon, performing better (around 90%).
Figure 3: Fraction of correct responses (for an existing name).
A surprising result was the AD bit distribution in responses (Fig. 4). First, it can be seen that between 32% and 48% of probe–resolver pairs claim DNSSEC validation for conventional algorithms. This is in line with what’s expected from DNSSEC validation deployment studies.
More interestingly, we are pretty certain that no probe was connected to a resolver that is able to validate signatures from our PQC implementations. Still, when the DO bit was set, responses from about 8.5% of probe–resolver pairs indicated for the Falcon algorithm that signatures had been validated. This appears to be clearly broken, and perhaps deserves a deeper look into what resolver software produces such responses. Curiously, the problem goes away when using TCP.
Figure 4: AD bit (for a non-existing name).
If you’d like to play around with our test zones, you can do so using our test bench at https://pq-dnssec.dedyn.io/.
In addition to our signing implementation for PowerDNS authoritative nameserver (available at pdns.pq-dnssec.dedyn.io:53), we have also implemented validation in PowerDNS Recursor (running on port 5302).
You can query this PQC-enabled PowerDNS resolver directly from the above page (using a DoH proxy), and also test interoperation by selecting BIND resolver to validate PowerDNS signatures or vice versa. As BIND uses a different setup (KSK/ZSK presigned, instead of CSK with dynamic NSEC3), results may vary slightly across scenarios.
In case you want to use the command line, the page also has information on which exactly are the zones to query, accompanied by links to source code and additional measurement results.
This project was funded by NLnet Foundation and supported by SSE.