Elias Heftrig, Niklas Vogel, and Michael Waidner contributed to this work.
My fellow researchers and I from the National Research Center for Applied Cybersecurity ATHENE have uncovered a critical flaw in the design of DNSSEC, which introduced a vulnerability in all DNSSEC-validating DNS resolver implementations. We developed a new class of algorithmic complexity attacks, dubbed ‘KeyTrap’.
In the technical report, we demonstrate that just with a single DNS packet the attack can exhaust the CPU and stall all widely-used DNS implementations and public DNS providers, such as Google Public DNS and Cloudflare. The impact of KeyTrap attacks is far-reaching. Exploiting KeyTrap, attackers can effectively disable Internet access in any system utilizing a DNSSEC-validating DNS resolver.
DNS is a critical Internet infrastructure
The DNS has evolved into a critical infrastructure of the Internet; it underlies a wide range of applications and facilitates new and emerging technologies. The central role of the DNS has also made it a common target of attacks. To prevent attacks against the DNS, the IETF standardized security extensions for DNS in DNSSEC. To gain security benefits, domains should be digitally signed, and the DNS resolvers should use digital signatures to validate the authenticity of the DNS records in responses.
Challenges towards DNSSEC deployment
Although the first specification for DNSSEC was standardized in 1997, its deployment progressed slowly. Now, 25 years after the initial standard, APNIC measurements indicate that 31% of web clients worldwide use DNSSEC-validating DNS resolvers (Figure 1).
One of the factors causing slow adoption is fear of harming or even losing connectivity due to failures or load introduced by the computation of cryptographic operations or transmission of cryptographic material.
In addition, the deployment of new mechanisms may result in misconfigurations and errors. For instance, keys may be expired, or not correctly configured, or the resolvers may not support some of the cryptographic ciphers that the domain owner used to sign its zone records. Failed DNSSEC validation leads to connectivity problems of the corresponding affected service to the applications and clients using DNS.
Availability is a top priority in the Internet
The impact of the cryptographic requirements on the availability of the DNS was a major concern in the design of DNSSEC (RFC 4033, RFC 4035, RFC 6840). Strict DNSSEC validation rules could impact DNS availability, hence, the DNSSEC standard opted to limit strict requirements to the necessary minimum that suffices to ensure cryptographic security while maintaining the availability of DNS, aiming at a tradeoff between security, performance, and backward compatibility.
Therefore, the standard requirements for DNSSEC were designed so that the DNS resolvers do not fail on the first cryptographic error, and therefore, as long as a resolver can verify the provided information with any available DNSSEC material, the validation should succeed. Consequently, the core DNSSEC specification mandates the DNS resolvers to try all possible keys when validating a resource record set. the validator…
”MUST try each matching DNSKEY RR until either the signature is validated or the validator has run out of matching public keys to try.”
RFC 4035, Section 5.3.1
The specification also strongly endorses trying all possible signatures [RFC 6840].
These DNSSEC requirements follow Postel’s Law (RFC 1122). The nameservers should send all the available cryptographic material, and the resolvers should use any of the cryptographic material they receive until the validation is successful. This ensures availability even if some of the DNSSEC material cannot correctly validate the authenticity of the DNS records, for example, if the keys are misconfigured, incorrect or outdated.
We confirmed experimentally and through code analysis that these DNSSEC protocol requirements are supported by all major DNS resolver implementations, but also tools that use DNS and software that provide DNS functionality, such as libraries, zone checkers, and debugging software.
DNSSEC specification is flawed
In our research, which is now public, we discovered that the design philosophy of DNSSEC is flawed. We demonstrated that the flaws in the DNSSEC standard could be exploited for cyberattacks by developing the first DNSSEC-based algorithmic complexity attacks against the DNS. We exploited the following flawed requirements:
Key-tag collisions: First, DNSSEC allows for multiple keys in a given DNS zone, for example during key rollover or for multi-algorithm support (RFC 6781). Consequently, when validating DNSSEC, DNS resolvers are required to identify a suitable cryptographic key to use for signature verification.
DNSSEC uses key tag values to differentiate between the keys. The key tag values are not necessarily unique and multiple different DNS keys can have identical key tag values. This is explicitly stated in (RFC 4034), emphasizing that key tags are not unique identifiers. We showed colliding key tags can be exploited to cause a resolver to be unable to identify a suitable key efficiently but to have to perform validations with all the available keys, inflicting computational effort during signature validation.
Multiple keys: The DNSSEC specification mandates that a resolver must try all colliding keys until it finds a key that successfully validates the signature, or all keys have been tried. This requirement is meant to ensure availability. We showed this ‘eager validation’ can be exploited to create a heavy computational effort for the validating resolver since the number of validations grows linearly with the amount of colliding keys. For example, if a signature has ten colliding keys, all with identical algorithm identifiers and key tags, and are all invalid, the resolver must conduct ten signature validations before concluding the signature is invalid. While colliding keys are rare in real-world operations, we show that records with multiple colliding keys can be efficiently crafted by an adversary, imposing heavy computation on a victim resolver.
Multiple signatures: The philosophy of trying all the cryptographic material available to ensure that the validation succeeds also applies to the validation of signatures. Creating multiple signatures for a given DNS record can happen, for example, during a key rollover. The DNS server adds a signature with the new key while retaining the old signature to ensure the signature remains valid for all resolvers until the new key has propagated. Thus, parallel to the case of colliding keys, the RFCs specify that in the case of multiple signatures on the same record, a resolver should try all the signatures it received until it finds a valid signature or until all signatures have been tried.
We combined these requirements for the eager validation of signatures and of keys, along with the colliding key tags to develop powerful DNSSEC-based algorithmic complexity attacks on validating DNS resolvers. Our methods show a low-resource adversary can fully attack a DNS resolver with a Denial-of-Service (DoS) for up to 16 hours with a single DNS request. Members from the 31-participant task force of major operators, vendors, and developers of DNS/DNSSEC, to which we disclosed our research, dubbed our attack ‘the most devastating vulnerability ever found in DNSSEC’.
We demonstrated, experimentally, that our attacks are detrimental to the availability of the affected DNS resolvers, and allow DoS attacks on basic DNS functionalities, such as providing cached responses, or processing inbound or pending DNS packets.
We showed, experimentally, that an adversary using a single DNSSEC-signed DNS response can DoS resolvers leading to a spike of 2,000,000x in CPU instruction count. The stalling period of the victim resolver depends on the resolver implementation, for example, the popular Bind9 resolver can be stalled for 16 hours. We find that all DNSSEC-validating DNS software, DNS libraries and public DNS services on our dataset are vulnerable to our attacks.
The KeyTrap attacks affect not only the DNS but also any application using it. The unavailability of the DNS may not only prevent access to content but risks also disabling security mechanisms, like anti-spam defences, Public Key Infrastructure (PKI), or even inter-domain routing security like RPKI.
Complex vulnerabilities are challenging to find
The flaws have been around for quite some time. The vulnerable requirement to try all keys was present already in the obsoleted (RFC 2535) from 1999. This requirement was carried over to RFC 4035.
In 2013, the issue was further exacerbated by endorsing that the validators also try all the signatures in the implementation requirements for DNSSEC validation (RFC 6840). Using code analysis, the team could trace the vulnerabilities to the early versions of Bind9 in 2000 and Unbound in 2007, which indicates that the vulnerabilities were introduced in the wild from the beginning with the deployment of DNSSEC.
Although the vulnerabilities the team found have existed in the standard for about 25 years and in the wild for 24 years, they have not been noticed by the community. This is not surprising since the complexity of the DNSSEC validation requirements made it challenging to identify the flaws. The exploit requires a combination of several requirements, which made it not trivial even for DNS experts to notice. The security community had similar experiences with much simpler vulnerabilities, such as Heartbleed or Log4j, which were there but no one could see them, and they took years to notice and fix.
KeyTrap vulnerabilities are fundamental
Unfortunately, in contrast to software bugs, like HeartBleed, the vulnerabilities found during our research are fundamental and are not simple to resolve, since they are rooted in the design philosophy of DNSSEC. The DNSSEC specification from its early drafts explicitly includes the flawed requirements, that lead to these vulnerabilities, and indeed, all DNS resolvers that follow the RFCs, as well as libraries and other tools that use the DNS or provide DNS functionality, like zone-checkers and debugging tools, were found to be vulnerable.
Early responsible disclosure and support of the vendors
Since the initial disclosure of the vulnerabilities on 2 November 2023, we have been working with all major vendors on mitigating the problems in their implementations. Development of patches was challenging and non-trivial and required multiple iterations. We describe the process of patch development along with the failures in the technical report.
Final patches mitigate the flaws, but all resolvers that deploy them currently break the DNSSEC standard recommendations. Since the flaw is rooted in mandatory standard requirements, not in vendor-specific implementation choices, this is necessarily the case. The challenge that the patches face is the need to strike a balance between security and availability.
The current patches shift the balance between security and availability towards security, but on the other hand risk sacrificing availability in corner cases. Or, alternatively, if they shift the balance towards availability, they do not completely prevent the attacks, as we saw in the case of patched Bind9, where a variation of KeyTrap attack still could cause high CPU load, albeit without inflicting packet loss.
We recommend that everyone installs the patches and updates their DNS software. We recommend the ongoing use of DNSSEC, urge domains to implement signing and encourage all resolvers to enforce DNSSEC validation. DNSSEC is the only practical measure to block DNS cache poisoning attacks.
Details of the evaluations, the development of the patches and the attacks can be found in the technical report.
Dr. Haya Shulman is a Professor of computer science at Goethe-Universität Frankfurt, department director at the Fraunhofer-Institute for Secure Information Technology SIT and a head of the research area Analytics-based Cybersecurity in the national research centre ATHENE.
The views expressed by the authors of this blog are their own and do not necessarily reflect the views of APNIC. Please note a Code of Conduct applies to this blog.