KeyTrap Explained
On Valentine's Day 2024, the DNS community faced a double whammy: CVE-2023-50387 and CVE-2023-50868. Both vulnerabilities, classified as high severity by ISC (https://kb.isc.org/docs/cve-2023-50387 and https://kb.isc.org/docs/cve-2023-50868), were discovered in late 2023. After responsible disclosure to major DNS vendors, patches were released alongside the public announcement. But what's the real deal with the first vulnerability, dubbed KeyTrap? How does it work, and should you have canceled your Valentine's Day plans to address it? Let's dive in.
DNSSEC Basics and Key Tag
To understand KeyTrap, we need to revisit a DNSSEC concept: Key Tags (or Key IDs). Remember, DNSSEC adds signatures (RRSIG) to responses for authentication. But what if there are multiple signing keys in a zone? How does a validating resolver know which one to use? That's where Key Tags come in.
Think of a Key Tag as a 16-bit number (like 27566) that helps resolvers quickly pick the right key. It's a shortcut, but importantly, these IDs aren't totally unique (this is important for the exploit, we’ll come back to this later).
Let’s look at a quick example. When we query for a record in a zone signed with DNSSEC, it comes back with at least one signature, or RRSIG. In the example below, the RRSIG was signed by the key with the ID 27566.
% dig www.isc.org. A +dnssec +multi
...
;; ANSWER SECTION:
www.isc.org. 300 IN CNAME isc.map.fastlydns.net.
isc.map.fastlydns.net. 300 IN A 151.101.18.217
www.isc.org. 300 IN RRSIG CNAME 13 3 300 (
20240325063719 20240311063510 27566 isc.org.
4Zq30VUle4eLxC2ZJJ//jx4PJdls0KwxGDEpc0P5WU+q
m/PtzIIv7hdC4WWEyEXiJlSAmxQOetZ77zRKQbnzhA== )
...Knowing that the key we are looking for has the ID 27566 makes it easy when we need to choose which of the following available DNSKEY to use to validate the signature:
% dig isc.org. DNSKEY +dnssec +multi
...
;; ANSWER SECTION:
isc.org. 2966 IN DNSKEY 257 3 13 (
zEoOfseNFDM+E8spu7RR2Ar/GzFqAehe4yapWLiv6McI
UF6xmI5GcIQ3+uLAizS2cNWHt6EArVj8ogjtrRXwfw==
) ; KSK; alg = ECDSAP256SHA256 ; key id = 7250
isc.org. 2966 IN DNSKEY 256 3 13 (
1CS+VQcRn4lGTK+b3wDjVO0hFDx4DV7s3Q1Fwxuq9ahd
255FRny4f4vdZOMMMxpbRH5Zhwoh/706IV0v9JwjlA==
) ; ZSK; alg = ECDSAP256SHA256 ; key id = 27566
isc.org. 2966 IN RRSIG DNSKEY 13 2 3600 (
20240319233000 20240305223417 7250 isc.org.
JvzQKYR/Pfu9sNoeWdp4B3xNnwQt19gfuplZTPYpD9pP
S9yW2Jn5sF/ATrhyShPurasno5TczFaLzs4xDodTHg== )
...Understanding Key Tag Design
It's important to remember that the 16-bit Key Tag is auto-generated, not manually set. You'll find the calculation method in RFC 4034 Appendix B. Here is a summary of how the design works:
Efficiency: A 16-bit integer (or up to 5 digits) allows validating resolvers to quickly locate the right key, even when a zone has multiple keys.
Practical Limits: While a 16-bit field can't guarantee uniqueness for every key ever created, it's highly unlikely that two keys within the same zone will have the same auto-generated Key Tag.
Handling the Rare Collision: In the unusual case where a zone does have keys with identical Key Tags, validating resolvers have a built-in safety net: they must try each matching key to find the correct one.
As we will see, KeyTrap exploits the handling of rare collision as a key part of its attack.
Exploiting the Key Tag Design
The research team behind the KeyTrap attack asked a very basic question: what if you purposely listed keys with the same Key Tag (or Key ID)? How will that affect the validating resolvers? The published paper actually listed 4 separate techniques:
SigJam (One Key x Many Signatures): This technique involves creating many invalid signatures all pointing to the same key, The research team was able to fit 340 signatures into one single DNS response (sent over TCP), causing 340 validation attempts only to end in SERVFAIL.
LockCram (Many Keys x One Signature): This technique forges many keys with identical Key Tag, forcing the validating resolver to attempt validation with all of the keys listed.
KeySigTrap (Many Keys x Many Signatures): This technique combines the previous two techniques, that leads to a quadratic increase of validations (that is, M*N rather than just N).
HashTrap (Many Keys x Many Hashes): This technique does not directly abuse the Key Tag field, but forces the validating resolver to perform many hashing calculations. This technique is used more extensively in CVE-2023-50868, which I will discuss in a future post.
The research team behind KeyTrap devised a clever sequence of steps to exploit the vulnerabilities in DNSSEC validation. Here's how it unfolds:
The attacker sends a query to a DNSSEC-aware resolver (validating resolver).
The validating resolver queries the authoritative server controlled by the attacker.
The attacker sends back a large response containing many crafted signatures.
The validating resolver queries the authoritative server again to retrieve the corresponding keys as listed by the signatures.
The attacker sends back another large response, this time containing many keys.
This causes the validating resolver into a computational frenzy, only to end in a validation failure (SERVFAIL).
The research team picked the most impactful algorithm combinations to ensure the validating resolver has to perform the maximum amount of work. In the paper, an attacker could fit up to 519 signatures in a single packet (#3), and 589 DNS keys (#5). This triggers 589*519=305691 signature validations!
What makes this worse, is that some implementations such as BIND and Unbound will retry after a failure, further exacerbating the resource-consumption problem.
Should I Panic?
This all sounds pretty scary. But how bad is it, really? Let’s recap what is required for this attack to work well, and I will tackle each point one by one:
Your DNS recursive resolver is DNSSEC-enabled i.e. is a validating resolver.
The attacker is able to reach the validating resolver.
The large packets from attacker-controlled domain can reach your validating resolver.
Not Many DNSSEC-Enabled Resolvers
Unfortunately, and somewhat surprisingly, DNSSEC-enabled resolvers are still in the minority. While Geoff Huston's 2023 study showed roughly 30% of internet DNS traffic attempting DNSSEC validation, that's by volume, not by individual resolvers. Remember, some resolvers handle much more traffic than others.
A closer look, also by Huston, reveals a less encouraging picture: only about 4% of DNS resolvers actually perform DNSSEC validation. This means a staggering 96% of resolvers worldwide aren't vulnerable to KeyTrap simply because they don't yet support DNSSEC. There's a good chance your DNS resolver falls into this majority.
It’s Hard for Attacker to Reach Internal Resolvers
If you're among the few who've deployed DNSSEC, chances are, your validating resolvers sit behind firewalls, NAT, and other protective measures. This makes a KeyTrap attack much less appealing for two reasons:
Barriers to Entry: Could a determined attacker breach all those layers? Maybe, but it'd be a lot of effort for just crashing your DNS.
Bigger Targets: If they've bypassed your security, they have access to far more valuable assets than just your DNS resolver.
In short, if your DNS validating resolver is well-protected within your network, attackers likely won't waste their time on a KeyTrap attack. There are simply easier and more rewarding targets out there.
We Still Struggle with TCP (Especially with DNS)
To make KeyTrap truly devastating, an attacker needs to cram hundreds of signatures and keys into as few packets as possible. Sending smaller packets over time won't do the trick – a resolver might be overwhelmed too quickly to process later malicious data.
So what’s the big deal with sending large packets? It’s 2024, surely that’s not a problem? But DNS is a special case.
Although the original DNS specs (RFC 1035) clearly state TCP is required, many vendors and operators wrongly assume DNS works fine over just UDP. Despite efforts like DNS Flag Day to raise awareness, research shows a lot of DNS servers still struggle with TCP or large messages.
Ironically, this means if an attacker tries to use KeyTrap, the attack might fail simply because network operators or DNS admins haven't configured their systems to handle large DNS messages properly!
Conclusion
KeyTrap is definitely a clever exploit. Should you patch? Absolutely – security updates are always important. But should you have ditched your Valentine's Day plans for this? Probably not. Unless you're an ISP with a DNSSEC validation service (and even then, there are workarounds like RPZ), this patch can likely wait.
It's a good reminder to stay on top of updates, but hey, sometimes a romantic dinner is worth more than scrambling to fix every single vulnerability the moment it's announced.