KeyTrap: A 20 Year Old Vulnerability in DNSSEC.

Introduction #

In this blog post, we will be exploring the intricacies of the KeyTrap vulnerability in DNSSEC. This vulnerability is a denial of service (DoS) attack that can be used to disrupt the operation of DNS servers running DNSSEC. We will discuss the details of the vulnerability, its impact, and how it can be mitigated.

This blog post is mainly based on the KeyTrap Paper by Athene and the KeyTrap Athene Website.

What is DNSSEC? #

DNSSEC is an extension of DNS that provides authentication by adding cryptographic signatures to existing DNS records. These signatures are stored in DNS messages alongside other DNS records. By checking the signatures, we can verify that a requested DNS record is not tampered with en-route from the DNS server to the client (IE: Through an attacker).

The DS record is a special type of DNS record that contains the hash of a DNS Key.

As we can see in the diagram above, the DNSSEC validation process involves recursively validating the Public Key of the different name servers using the DS records of the servers above them in the DNS hierarchy.

If there was a malicious actor who manipulates the DNS records, the DNSSEC validation process would be able to detect the tampering and reject the response as the signatures would not match the records.

What is KeyTrap? #

The KeyTrap vulnerability is a flaw in the Internet Standard defining DNSSEC, the security extension for the Domain Name Service (DNS). The standard defines multiple requirements that dictate resolvers to try all available cryptographic material; try all available DNSSEC keys against all available DNSSEC signatures. An attacker can set up a malicious domain with many keys using the same key-tag and many signatures referring to that key-tag. Following the standard, a resolver will attempt to validate ALL keys against ALL signatures, leading to a quadratic effort validating the domain. With a sufficiently large amount of keys and signatures, an attacker can exhaust the CPU resources of the resolver, achieving a Denial-of-Service (DoS).

~ From Athene KeyTrap Page

Factors #

There are some combination of factors that make the KeyTrap attack possible. We will be going through each of them in detail.

1. Key-Tag Collision
2. Multiple Keys
3. Multiple Signatures

Key-Tag Collision #

Key-Tag is a 16-bit value that is used to identify a DNS Key more quickly. The thing to note here is that it is NOT a cryptographic hash of the DNS Key resource associated with the DNS Key record.

As it is a 16-bit value, there are only 65536 possible values for the Key-Tag. The algorithm used to calculate the Key-Tag is specified in RFC4034.

/*
* Assumes that int is at least 16 bits.
* First octet of the key tag is the most significant 8 bits of the
* return value;
* Second octet of the key tag is the least significant 8 bits of the
* return value.
*/

unsigned int keytag (
    unsigned char key[],  /* the RDATA part of the DNSKEY RR */
    unsigned int keysize  /* the RDLENGTH */
) {
    unsigned long ac;     /* assumed to be 32 bits or larger */
    int i;                /* loop index */

    for ( ac = 0, i = 0; i < keysize; ++i )
        ac += (i & 1) ? key[i] : key[i] << 8;
    ac += (ac >> 16) & 0xFFFF;
    return ac & 0xFFFF;
}

The code snippet above is the algorithm used to calculate the Key-Tag as referenced in RFC4034 appendix B.

It should the key by 8 bits and adds the result to the accumulator if the index is even. Otherwise, It just adds the key to the accumulator. After that we shift ac by 16 bits and take the last 16 bits of the result.

For any single key, we can generate a collision by brute-forcing the key until we find a key that has the same Key-Tag as the original key.

By having collisions between keys, the resolver will be force to iterate over all the keys for signature validation.

Multiple Keys #

The DNSSEC specification mandates that a resolver should try ALL colliding keys until it finds the correct key to validate the signature (Or all keys are tried).

This is meant to ensure that the resolver can maintain high availability in the event that there is a key collision (Postel’s Law). However, this also means that there is a trade-off, in this case iterating over all the keys to find the correct one will be CPU intensive.

IE: If there are 1000 keys with the same Key-Tag, the resolver will have to iterate over all 1000 keys to find the correct one. This runs in O(n) to iterate over the keys and calculate the signature.

Multiple Signatures #

Similar to the multiple keys, the resolver will have to iterate over all the signatures to find the correct one. Multiple signatures can be made for the same DNS record (During a key-rollover). The DNS server adds a signature with the new key while retaining the old signature to ensure validity of the DNS record until the old key is propagated across the DNS hierarchy.

The RFC also mandates that in the case of multiple signature, the resolver should try all the signatures until it finds the correct one (or all signatures are tried) (Postel’s Law). This runs in O(n) to iterate over the signatures.

Example Vulnerable Code Snippet #

//loop over all the keys
for(i=0; i<num; i++) {

    /* see if key matches keytag and algo */
    if(algo != dnskey_get_algo(dnskey, i) ||
        tag != dnskey_calc_keytag(dnskey, i)) continue;

    numchecked ++;

    /* see if key verifies */
    sec = dnskey_verify_rrset_sig(env, ve, rrset, dnskey, i, sig_idx);
    if(sec == sec_status_secure)
        return sec;
}
//loop over all the signatures
for(i=0; i<num; i++) {
    sec = dnskeyset_verify_rrset_sig(env, ve, rrset, dnskey, i);
    if(sec == sec_status_secure)
        return sec;
}

The above code is a snippet of the DNSSEC validation process in the Unbound DNS resolver. The resolver loops over all the keys and signatures and tries to validate them. This is the part of the code that is vulnerable to the KeyTrap attack.

It iterates over all the keys and signatures to find the correct one to validate the DNS record.

How the Attack Works #

With the combination of the above mentioned factors, the attacker can set up a malicious domain with many keys using the same key-tag and many signatures referring to that key-tag. As a result, the resolver will attempt to validate ALL keys against ALL signatures, leading to a quadratic effort validating the domain (O(n^2) time complexity).

There is a repository by knqyf263 that demonstrates the KeyTrap attack.

Effects of the Attack #

The KeyTrap attack can be used to exhaust the CPU resources of the resolver, achieving a Denial-of-Service (DoS). The amplification factor of the attack is the number of keys and signatures that the attacker can generate. With the maximum number of keys and signatures in 1 DNS message, the attacker can achieve a 2_000_000 times (increase in CPU instruction counts as a single request) compared to a standard DNSSEC validation process.

Mitigation #

After the CVE is disclosed, the temporary mitigation is to turn off DNSSEC validation in the resolver or to serve stale data.

DNSSEC Validation mitigation #

After some discussion, there were some proposed mitigation to the KeyTrap attack on DNSSEC itself.

Limiting failure signature validation counts #

The resolver can limit the number of times it tries to validate a key or signature. If the resolver reaches the limit, it can return a SERVFAIL response to the client.

However, if the limit is not set strictly, the attacker can still exhaust the CPU resources of the resolver by sending the DNS query with a higher query per second.

Zero failure signature validation #

The resolver can be configured to return a SERVFAIL response to the client if the validation fails. However, if there were many DS records in the DNS message, the resolver will still have to iterate over all the DS Hashes to find the correct one to validate the DNS record.

Limiting Key Collisions #

The resolver can be configured to limit the number of keys collisions. All zones only has 2 colliding keys, the resolver can be configured to only try 2 keys for validation.

However, this mitigation can be overcome by sending multiple DNS messages with the Any query type. Even if the key does not collide, the resolver will still validate all the signatures in the record. Since all the signatures are valid, it does not fail from any validation failures as well.

Limiting all validations #

This is the first effective mitigation that can be implemented. It is somewhat a combination of all of the above mitigation.

1. Limit Key Collisions to 4
2. Limit Cryptographic failures to 16
3. Limit total validations in Any requests to 8.

Resilience of architecture #

There are also some other mitigation that can be implemented to make the DNS resolver more resilient to the KeyTrap attack.

Multi-threading #

The DNS resolver should de-prioritize any requests that cause substantial computational load.

OS Buffer for UDP packets #

The lack of buffer space for UDP packets can cause the resolver to drop the packets. Instead of dropping the packet, the OS can allocate a buffer for teh packet and place pending requests in a dynamic internal buffer.

Threads for cached records #

As many requests can be retrieved from cache, allocating a separate thread to answer queries from cache can reduce the impact of stalling of resolution threads.

Conclusion #

The KeyTrap attack is a denial of service (DoS) attack that can be used to disrupt the operation of DNS servers running DNSSEC.

A design problem with DNSSEC and DNS is the strict application of Postel’s Law which introduced this vulnerability.

Although this does not completely mitigate the attack, it does reduce the impact of the attack. A complete mitigation will require a change/update to the DNSSEC standard.

Useful Links #

1. What is DNSSEC?
2. Github Repo Example
3. DNSSEC Consolidated RFC9364
4. DNSSEC Security Modifications
5. KeyTrap in DNS
6. KeyTrap DoS Paper
7. KeyTrap CVE
8. How DNSSEC Works
9. Google Cloud DNS Keys