On February 13, 2024, a team of researchers disclosed that a single DNS packet — about a hundred bytes — could stall a DNSSEC-validating resolver for as long as sixteen hours. Not crash it. Stall it: peg a CPU core and stop answering everyone else’s queries while it ground through a calculation an attacker had handed it. They called it KeyTrap.
The uncomfortable part isn’t the severity, though the severity was real: every major validating resolver was affected, and public giants like Google Public DNS and Cloudflare were in scope. The uncomfortable part is where the flaw lived. KeyTrap wasn’t a buffer overflow someone fat-fingered in 2019. It was a requirement — a “MUST” — sitting in the DNSSEC specification, in plain sight, since roughly the year 2000. The researchers at ATHENE (Elias Heftrig, Haya Schulmann, Niklas Vogel, and Michael Waidner) didn’t find a mistake in the code. They found that the code was doing exactly what the standard told it to.
The rule that seemed obviously correct
DNSSEC signs DNS records so a resolver can verify they weren’t tampered with in transit. To check a signature, the resolver needs the matching public key. The problem is that “matching” isn’t always one-to-one.
Each signature (an RRSIG record) carries a key tag: a 16-bit value, essentially a checksum over the key, used as a quick hint for “try this key.” A resolver picks the DNSKEY records whose key tag, algorithm, and signer name line up with the signature, and tries them. Here’s the catch that RFC 4035 §5.3.1 spells out: the resolver “MUST try each matching DNSKEY RR until either the signature is validated or the validator has run out of matching public keys to try.” In 2013, RFC 6840 extended the same generosity to signatures — try all of them, too.
Read in daylight, that’s the obviously right behavior. Key tags are only a hint, not an identifier; two different keys can share one. During a key rollover a zone legitimately publishes several keys at once. If a resolver gave up after the first key that looked right but didn’t verify, it would wrongly reject perfectly valid, signed domains every time a tag collided. So the spec says: be forgiving. Don’t give up. Try every key against every signature until one works. Never let a real signature fail because you were lazy.
That instinct — when in doubt, try harder — is what got weaponized.
Quadratic effort from a hundred bytes
A key tag collision is cheap to manufacture. You control your own zone; you can generate keys until a batch of them share a tag, and publish signatures that all point at that tag. Now imagine a zone with a few hundred colliding keys and a few hundred signatures, all referencing each other.
A resolver that obeys the spec has to try every key against every signature. That’s not linear work; it’s the product. n keys times m signatures is quadratic, and every single attempt is a full public-key cryptographic operation — the expensive kind. All of them fail, because the attacker designed them to, so the resolver never gets to short-circuit on success. It just keeps trying, faithfully, to the last combination.
The attacker doesn’t even need to flood anything. They register a domain, stand up this malicious signed zone, and get the victim resolver to look up one name inside it. The resolver fetches the answer and, to validate it, walks into the trap. One query. One response. The researchers measured stalls ranging from a couple of minutes to sixteen hours depending on the implementation — long enough that a shared resolver stops serving every other user behind it. This is the textbook shape of an algorithmic complexity attack: small input, catastrophic work, and the victim volunteering the CPU.
And because close to a third of internet users sit behind DNSSEC-validating resolvers, “one resolver stops answering” is not a small blast radius.
The fix is everyone agreeing to break the rule
Here’s the tell that KeyTrap was a design problem and not a bug. You cannot patch it by fixing a line of code, because there was no wrong line. The behavior was correct per the RFC. So what did the vendors actually do?
They capped the work. BIND, Unbound, Knot, PowerDNS — each added a budget: a limit on how much validation effort a single answer is allowed to consume. Cross the budget and the resolver stops, returns SERVFAIL, and moves on. In other words, every implementation independently decided to stop obeying “MUST try each matching DNSKEY RR until … the validator has run out of matching public keys to try.” The standard said be maximally forgiving. The fix is to be deliberately unforgiving past a threshold, and to accept that on some pathological-but-technically-valid zone, you will now refuse to validate something you’re strictly required to.
That’s the right call. It’s also an admission. The specification’s notion of “correct” — never wrongly reject a signed record — turned out to be unaffordable in the presence of an adversary, and the industry quietly redefined correct to mean “give up before you hurt yourself.”
What KeyTrap should teach
The lesson isn’t “DNSSEC is uniquely broken,” though it’s fair to note this is the same protocol that took twenty years to reach minority adoption and still trips people with expired signatures and botched rollovers. The lesson is more general, and it applies to anything you build that parses untrusted input.
Any time a spec says try every combination until one works, and the combinations are attacker-controlled, you have a complexity bomb with a delay fuse. The failure mode is invisible in every test you’ll run, because your test data is benign — a handful of keys, a couple of signatures, everything resolving in microseconds. It only detonates when someone constructs the input on purpose. “Be lenient in what you accept” is good advice for interoperability and a loaded gun for availability, and the two halves of that trade-off don’t show up in the same room until an adversary walks in.
KeyTrap sat in the standard for over two decades, implemented faithfully by every DNSSEC resolver on the planet, reviewed by exactly the kind of careful people who write RFCs. Nobody spotted it, because it wasn’t hiding. It read like the responsible thing to do. That’s the part worth keeping: the most dangerous flaws aren’t the ones that look like mistakes. They’re the ones that look like diligence.