KeyTrap Algorithmic Complexity Attacks Exploit Fundamental Design Flaw in DNSSEC

Researchers from the National Research Center for Applied Cybersecurity ATHENE have uncovered a critical flaw in the design of DNSSEC (DNS Security Extensions) that introduces a vulnerability in all DNSSEC validating DNS resolver implementations.

The team - Elias Heftrig, Haya Schulmann, Niklas Vogel, and Michael Waidner - developed a new class of algorithmic complexity attacks, which they dubbed KeyTrap.

They demonstrated that, with only 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. In fact, the popular Bind9 DNS implementation can be stalled for as long as 16 hours.

These devastating effects prompted major DNS vendors to refer to KeyTrap as “The worst attack on DNS ever discovered.” And the impact of the attack is far reaching. Exploiting KeyTrap, attackers can effectively disable Internet access in any system utilising a DNSSEC-validating DNS resolver.

DNS is critical Internet Infrastructure

DNS is a critical infrastructure for the Internet, underlying a wide range of existing applications and facilitating new and emerging technologies. But this central role has made it a common target of attacks.

To counter such attacks, the IETF standardised DNSSEC, which is aimed at increasing security by requiring that domains should be digitally signed, and the DNS resolvers should use the digital signatures to validate the authenticity of the DNS records in responses.

Challenges in DNSSEC deployment

Although the first specification for DNSSEC was standardised in 1997, its deployment has progressed slowly. 25 years after the initial standard, APNIC measurements indicate that just 31% of the web clients worldwide use DNSSEC-validating DNS resolvers.

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, 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 which 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 top priority on the Internet

The impact of the cryptographic requirements on the availability of DNS was a major concern in the design of DNSSEC [RFC4033-RFC4035, RFC6840]. 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 availability of DNS, aiming at a trade-off between security, performance, and backward-compatibility.

Therefore, the standard requirements for DNSSEC were designed such that the DNS resolvers do not fail on the first cryptographic error, and hence 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 [RFC4035, Section 5.3.1]: 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." The specification also strongly endorses trying all possible signatures [RFC6840].

These DNSSEC requirements follow Postel's Law [RFC1122]: 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 authenticity of the DNS records; e.g., if the keys are misconfigured, incorrect or outdated.

We confirm 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, debugging software.

The DNSSEC specification is flawed

In our research, which was recently made 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 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 [RFC6781]. 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 [RFC4034], emphasising that key-tags are not unique identifiers. We show 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 show 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 identifier, key-tag and all invalid, the resolver must conduct ten signature validations before concluding the signature is invalid. While colliding keys are rare in real-world operation, 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; e.g., 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 combine 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 attacks allow a low-resource adversary to fully DoS a DNS resolver 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, leading to Denial of Service (DoS) 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; e.g., 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 DNS but also any application using it. An unavailability of DNS may not only prevent access to content but risks also disabling security mechanisms, like anti-spam defenses, 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 [RFC2535] from 1999. This requirement was carried over to [RFC4035]. In 2013 the issue was further exacerbated by endorsing the validators also try all the signatures, in the implementation requirements for DNSSEC validation [RFC6840]. 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 a number of requirements, which made it not trivial even for DNS experts to notice. The security community made 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 that we found in 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, which lead to these vulnerabilities, and indeed, all DNS resolvers that follow the RFCs, as well as libraries, and other tools that use 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 November 2, 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.

A complete solution to this fundamental problem in the DNSSEC standard requires to reconsider the underlying design philosophy of DNSSEC; i.e., to revise the DNSSEC standards.

We recommend that everyone installs the patches and updates their DNS software. We recommend to continue using DNSSEC, encourage the domains to get signed, and all the 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.