  Availability is a major concern in the design of DNSSEC. To ensure
availability, DNSSEC follows Postel's Law [RFC1123]: "Be liberal in what you
accept, and conservative in what you send." Hence, nameservers should send not
just one matching key for a record set, but all the relevant cryptographic
material, e.g., all the keys for all the ciphers that they support and all the
corresponding signatures. This ensures that validation succeeds, and hence
availability, even if some of the DNSSEC keys are misconfigured, incorrect or
correspond to unsupported ciphers.
  We show that this design of DNSSEC is flawed. Exploiting vulnerable
recommendations in the DNSSEC standards, we develop a new class of DNSSEC-based
algorithmic complexity attacks on DNS, we dub KeyTrap attacks. All popular DNS
implementations and services are vulnerable. With just a single DNS packet, the
KeyTrap attacks lead to a 2.000.000x spike in CPU instruction count in
vulnerable DNS resolvers, stalling some for as long as 16 hours. This
devastating effect prompted major DNS vendors to refer to KeyTrap as the worst
attack on DNS ever discovered. Exploiting KeyTrap, an attacker could
effectively disable Internet access in any system utilizing a DNSSEC-validating
resolver.
  We disclosed KeyTrap to vendors and operators on November 2, 2023,
confidentially reporting the vulnerabilities to a closed group of DNS experts,
operators and developers from the industry. Since then we have been working
with all major vendors to mitigate KeyTrap, repeatedly discovering and
assisting in closing weaknesses in proposed patches. Following our disclosure,
the industry-wide umbrella CVE-2023-50387 has been assigned, covering the
DNSSEC protocol vulnerabilities we present in this work.
