A single packet can exhaust the processing capacity of a vulnerable DNS server, effectively disabling the machine, by exploiting a 20-plus-year-old design flaw in the DNSSEC specification.
That would make it trivial to take down, say, a public DNSSEC-validating DNS resolver that has yet to be patched, upsetting all the clients relying on that service.
The academics who found this flaw – associated with the German National Research Center for Applied Cybersecurity (ATHENE) in Darmstadt – claimed DNS server software makers briefed about the vulnerability described it as “the worst attack on DNS ever discovered.”
Identified by Professor Haya Schulmann and Niklas Vogel of the Goethe University Frankfurt; Elias Heftrig of Fraunhofer SIT; and Professor Michael Waidner at the Technical University of Darmstadt and Fraunhofer SIT, the security hole has been named KeyTrap, designated CVE-2023-50387, and assigned a CVSS severity rating of 7.5 out of 10.
As of December 2023, approximately 31 percent of web clients worldwide used DNSSEC-validating DNS resolvers and, like other applications relying on those systems, would feel the effects of a KeyTrap attack: With those DNS servers taken down by the flaw, clients relying on them would be unable to resolve domain and host names to IP addresses to use, resulting in a loss of connectivity.
With KeyTrap, an attacker could completely disable large parts of the worldwide Internet
The researchers said lone DNS packets exploiting KeyTrap could stall public DNSSEC-validated DNS services, such as those provided by Google and Cloudflare, by making them do calculations that overtax server CPU cores.
This disruption of DNS could not only deny people’s access to content but could also interfere with other systems, including spam defenses, cryptographic defenses (PKI), and inter-domain routing security (RPKI), the researchers assert.
“Exploitation of this attack would have severe consequences for any application using the Internet including unavailability of technologies such as web-browsing, e-mail, and instant messaging,” they claimed. “With KeyTrap, an attacker could completely disable large parts of the worldwide internet.”
A non-public technical paper on the vulnerability provided to The Register, titled, “The KeyTrap Denial-of-Service Algorithmic Complexity Attacks on DNS,” describes how an assault would be carried out.
“To initiate the attacks our adversary causes the victim resolver to look up a record in its malicious domain,” the due-to-be-published paper states. “The attacker’s nameserver responds to the DNS queries with a malicious record set (RRset), according to the specific attack vector and zone configuration.”
The attack works, the paper explains, because the DNSSEC spec follows Postel’s Law: “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 requirement, to ensure availability, means DNSSEC-validating DNS resolvers can be forced to do a lot of work if presented with colliding key-tags and colliding keys that must be validated.
“Our complexity attacks are triggered by feeding the DNS resolvers with specially crafted DNSSEC records, which are constructed in a way that exploits validation vulnerabilities in cryptographic validation logic,” the paper explains. “When the DNS resolvers attempt to validate the DNSSEC records they receive from our nameserver, they get stalled. Our attacks are extremely stealthy, being able to stall resolvers between 170 seconds and 16 hours (depending on the resolver software) with a single DNS response packet.”
The ATHENE boffins said they worked with all relevant vendors and major public DNS providers prior to privately disclose the vulnerability so a coordinated patch release would be possible. The last patch was finished today.
“We are aware of this vulnerability and rolled out a fix in coordination with the reporting researchers,” a Google spokesperson told The Register. “There is no evidence of exploitation and no action required by users at this time.”
Network research lab NLnet Labs published a patch for its Unbound DNS software, addressing two vulnerabilities, one of which is KeyTrap. The other bug fixed, CVE-2023-50868, referred to as the NSEC3 vulnerability, also allows denial of service through CPU exhaustion.
“The KeyTrap vulnerability works by using a combination of keys (also colliding keys), signatures and number of RRSETs on a malicious zone,” NLnet Labs wrote. “Answers from that zone can force a DNSSEC validator down a very CPU intensive and time costly validation path.”
PowerDNS, meanwhile, has an update here to thwart KeyTrap exploitation.
“An attacker can publish a zone that contains crafted DNSSEC related records. While validating results from queries to that zone using the RFC mandated algorithms, the Recursor’s resource usage can become so high that processing of other queries is impacted, resulting in a denial of service,” the team wrote. “Note that any resolver following the RFCs can be impacted, this is not a problem of this particular implementation.”
The fix for CVE-2023-50387 is just one of six vulnerabilities addressed in Internet Systems Consortium’s BIND 9 DNS software. The others include:
- CVE-2023-4408: Parsing large DNS messages may cause excessive CPU load;
- CVE-2023-5517: Querying RFC 1918 reverse zones may cause an assertion failure when “nxdomain-redirect” is enabled;
- CVE-2023-5679: Enabling both DNS64 and serve-stale may cause an assertion failure during recursive resolution;
- CVE-2023-6516: Specific recursive query patterns may lead to an out-of-memory condition;
- CVE-2023-50868: Preparing an NSEC3 closest encloser proof can exhaust CPU resources.
The requirements for the KeyTrap vulnerability date all the way back to 1999 from the now obsolete RFC 2535, according to the research team that identified it. And by 2012, these elements appeared in RFC 6781 and RFC 6840, the implementation requirements for DNSSEC validation.
One packet suffices. You don’t have to do more than that to disconnect an entire network
Since at least August 2000 – more than 23 years ago – KeyTrap has been present in the BIND 9 DNS resolver, and it surfaced seven years later in the Unbound DNS resolver.
Dr Haya Shulman, a professor of computer science and one of the academics behind the KeyTrap research, told The Register in a phone interview the attack is simple and can be carried out by encoding it in a zone file.
“The vulnerability is actually something that’s recommended in the DNSSEC standard,” Prof Shulman explained. “One packet suffices. You don’t have to do more than that to disconnect an entire network.”
Prof Shulman said the patches that have been issued by various vendors break the standard. “The problem is this attack is not easy to solve,” she said. “If we launch it against a patched resolver, we still get 100 percent CPU usage but it can still respond.”
The ATHENE team observed that while the flaw remained undetected for decades, its obscurity isn’t surprising because DNSSEC validation requirements are so complicated. So too is mitigating the vulnerability and completely eliminating it will require a revision of the DNSSEC standard. ®