Preparing DNSSEC for Quantum Computing

This blog post is based on a peer-reviewed article, which will be published in Computer Communication Review. You can find our authors-version on this website.

Why are quantum computers relevant to DNSSEC?

Quantum computers work differently from current computers. Instead of calculating with bits, which can take the state of one or zero, quantum computers use qubits, which can be in multiple states at the same time. As a result, quantum computers can solve some computational problems more efficiently than current computers. Such computational problems serve as the foundations for cryptographic algorithms, like Elliptic Curve or RSA, that we use to sign DNS messages today. Use of such algorithms in DNSSEC enables anyone on the internet to verify that an incoming DNS message is the original message and that it has not been tampered with in transit. Instead of hundreds of years, quantum computers have the potential to break such cryptographic algorithms within hours or days using Shor’s algorithm. For DNSSEC, that means an attacker could carry out a man-in-the-middle attack: they could intercept a DNSSEC-signed response (e.g. carrying the IP address of a site like www.rivm.nl), modify the IP address in the DNS response, and then resign it. The victim, then, would not be able to tell the difference between the signature on the original message and the signature that the attacker has attached to the manipulated message. As a result, the victim (e.g. a visitor to www.rivm.nl) could be redirected to malicious content. Luckily, computational problems exist that are not easy to resolve, either for current computers or for quantum computers. As such, they are useful for cryptographic algorithms, such as those needed for DNSSEC. The standardisation organisation National Institute of Standards and Technology (NIST) is currently running a competition with the goal of standardising ‘quantum-safe’ algorithms, i.e. algorithms that will still be secure in the age of quantum computers.

Algorithm requirements for DNSSEC

Together with researchers from TNO, NLnet Labs and the University of Twente, we have assessed whether the signing algorithms entered in the NIST competition are suitable for DNSSEC use. To structure the exercise, we first defined four requirements that quantum-safe algorithms need to fulfil in order to be suitable for DNSSEC. In order of priority (most important first), they are:

Signature size

Given that a DNSSEC signature is transmitted with every signed DNS message, our first requirement is: quantum-safe algorithms should generate signatures that are smaller than 1,232 bytes. The DNS mainly uses UDP for transporting messages between resolvers and authoritative name servers. DNS messages therefore need to fit into one UDP datagram. If not, we run the risk that the message will not be transmitted successfully as a result of fragmentation. In the DNS, that works as follows: when a recursive resolver sends a query to an authoritative name server, it indicates what the maximum supported response size is. If the response is larger, the authoritative name server asks the resolver to retry using TCP instead of UDP. The process is sensitive to errors, however. For example, the resolver or the authoritative name server might not support TCP, or a middlebox might allow DNS messages to be transmitted only using UDP. Also, even if the resolver indicates that it supports a certain datagram size, the underlying network layer might not. In that case, the network layer will cut the response into smaller fragments, which have a higher chance of not being received successfully, for instance due to firewalls dropping fragmented packets. After some time, the resolver would retry via TCP, but, as mentioned above, that is often not successful either. It is therefore best if DNS messages are not fragmented. Measurements have shown that DNS messages larger than 1,232 bytes, have a higher chance of not being transmitted successfully.

Validation speed

Resolvers should be able to validate quantum-safe algorithms as efficiently as current algorithms. Since a signature is transmitted with every DNS response, a resolver also needs to validate the signature on every message it receives from an authoritative. As a result, busy resolvers (e.g. those operated by an ISP or by a service like Google Public DNS) need to validate thousands of responses per second. Moreover, we expect that number to grow in the future, because DNSSEC adoption is still growing.

Signing speed

The speed at which records are signed should also be on a par with current algorithms. In DNSSEC, zone operators only need to sign records when zone content has changed. For example, for .nl we need to create around 11,000 new signatures every half an hour on average. In some cases, records need to be signed on-the-fly and then higher signing speeds might be required.

Public key size

Public keys may be larger than 1,232 bytes. With DNSSEC, public keys are only occasionally transmitted to validate the signatures on individual responses. For example, a resolver will typically request the public keys for its million most popular domain names only once an hour. We therefore take the view that public keys could be larger than 1,232 bytes. Later in this article, we explain how larger keys could be transferred reliably.

Assessing quantum-safe algorithms

So, do the algorithms entered in the NIST competition fulfil our requirements? Of the quantum-safe algorithms that provide comparable security to current algorithms, three create signatures smaller than 1,232 bytes: Falcon-512, Rainbow-Ia, and RedGeMSS128. The table below lists the algorithms, together with their other relevant attributes. For easier comparison, we also list two algorithms often used in DNSSEC today at the bottom.

Table 1. Measuring quantum-safe algorithms. For each algorithm, we tested the performance of the optimised implementations in our test bed. There, we signed a random 86-byte message, validated the signature and measured how long both steps took. We then repeated the process a couple of thousand times and calculated the median processing times. Based on the measurements, we conclude that all three algorithms are probably efficient enough to be used in DNSSEC for most use cases. For example, they all allow a sufficiently high resolver validation speed, sometimes even faster than traditional DNSSEC signing algorithms (rightmost column). The size of the keys and signatures, however, give more reason for concern. Even though Falcon-512 creates signatures smaller than 1,232 bytes, problems could occur if a record is signed with two keys. That is often the case during key rollovers, and it increases the risk of packet loss. Rainbow-Ia, and RedGeMSS128, on the other hand, create very small signatures, but their public keys are too big to fit into a DNS message.

Our proposal: transmitting public keys out of band

Table 1 shows that none of the algorithms are a perfect fit for DNSSEC. Falcon-512 theoretically meets all our requirements, but it could cause problems when used in practice. That problem might be addressed by sending all DNS messages using TCP, but that is likely to be impractical, since the name servers for large TLDs or busy resolvers might not be able to handle large numbers of TCP connections efficiently because of the many connection states involved. We believe that Rainbow-Ia, and RedGeMSS128 are more suitable for DNSSEC, but only if we find another way of transmitting public keys reliably. Since their public keys do not fit into a DNS message, we could split them into chunks and publish each chunk under a separate domain name label. That would necessitate the addition of further information to the messages that carry the chunks, so that a resolver can re-assemble them into one key. That approach has the advantage that the key can still be transmitted in-band but has the disadvantage that it would require the resolver to send multiple queries to get the key, which increases the chance of packet loss. We therefore propose transmitting the public keys out-of-band. Resolvers would then not receive the key itself but only a URL and would subsequently use a different protocol, such as HTTP, to fetch the key. The approach comes with some caveats, though. For example, the resolver would need to support HTTP in order to retrieve the key, and name server operators would need to provide additional key hosting services.

Conclusions and next steps

So, can DNSSEC be adapted to cope with quantum computing? Our research suggests that it can. At least two of the algorithms currently being assessed in the NIST competition seem suitable. However, additional research will be required to “bolt” such algorithms onto DNSSEC. Such research will need to address questions such as how to handle the larger public keys used by the new algorithms. Also, the algorithms that seem favourable are both still under evaluation. As yet unknown security vulnerabilities might therefore be found in the future. It is also worth noting that the widespread deployment of previous signing algorithms took almost a decade. It is therefore important that we start planning the transition to quantum-safe algorithms as soon as possible. Together with our research partners, we intend to assess our proposals in more detail and perhaps bring them to the IETF for further discussion. Our research paper contains a more detailed analysis and some background on the quantum-safe algorithms whose suitability for DNSSEC we assessed.