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 a DNSSEC-validating DNS resolver that has yet to be patched, upsetting all the clients relying on that service and make it seem as though websites and apps were offline.

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 out 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.

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. It basically involves asking a vulnerable DNSSEC-validating DNS resolver to look up an address that causes the server to contact a malicious nameserver that sends a reply that causes the resolver to consume most or all of its own CPU resources.

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 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.