Recursive DNS Servers (Recursors) are regularly abused by DNS Water Torture attacks to relay malicious traffic.
Water torture attacks (Figure 1) flood Authoritative DNS servers (AuthDNSs) with DNS requests pertaining to Fully Qualified Domain Names (FQDNs) unknown to the AuthDNS. These FQDNs are randomly generated so that a name is never repeated. Thus, DNS caches of Recursors are bypassed and all attack requests are forwarded to the victim.
Mitigating malicious traffic is more efficient the closer it is to the attack origin. Thus, a list of the AuthDNS valid names is required when dealing with such attacks. However, such lists are usually not available since Authoritative Transfer (AXFR) requests are typically restricted for security reasons.
At the recent ACM/IRTF ANRW’20 workshop, we from the NETMODE Laboratory, National Technical University of Athens (NTUA), presented a privacy-aware schema that is suitable for efficiently distributing AuthDNS zone contents to Recursors and/or scrubbing infrastructures.
Our solution enables third parties to retrieve AuthDNS valid FQDNs without inferring zone contents. Zone mapping is time and space efficient; names are compactly stored within AuthDNS zones, low latency filtering of DNS traffic within Recursors is ensured, and bandwidth is conserved when information is exchanged between AuthDNSs and Recursors.
Moreover, our schema relies on standardized DNS requests, for example, AXFR and Incremental Zone Transfer (IXFR), thus being compatible with the existing DNS infrastructure, while zone updates are incorporated incrementally.
Cuckoo Filters: fast, compact and privacy-aware
Our approach leverages on probabilistic data structures as datastores for the valid AuthDNS zone names, specifically Cuckoo Filters (CFs), which are selected for their time, space and privacy-preserving properties.
CFs perform set membership lookups without false negatives (FNs), that is, errors for already inserted elements, while false positives (FPs) occur with a configurable probability. CFs are two dimensional arrays, characterized by the number of available buckets m and entries b per bucket. Elements are inserted in CF entries hashed, as fingerprints of size f bits. Contrary to BloomFilters (BFs), CFs support element deletion, thus enabling rapid name updates for large zones in our DNS use case.
Privacy-aware mapping of DNS names as Cuckoo filter fingerprints
We introduce the HashedDNSZones (HsZns) and the IncrementalDNSZones (IncZns). HsZns hold AuthDNS zone FQDNs hashed and mapped into CFs, whilst IncZns map recent AuthDNS zone changes, therefore facilitating incremental updates on HsZn-retrieved CF fingerprints.
HsZn and IncZn contents are obtained via AXFR- and IXFR-type DNS requests respectively. Moreover, HsZns are regularly renewed to reflect the most recent version of AuthDNS zones.
Listing 1 depicts the HsZn information serialization format. Lines 3 to 7 pertain to CF parameters (m, f and b) and the algorithms used for calculating fingerprints and determining their position within CFs.
Listing 2 includes an example of mapping CF data, that is, FQDN fingerprints (Listing 1, lines 8-9) within HsZns.
In Listing 2, 82 zone FQDNs are mapped to a CF with fingerprints of size f=12 bits and buckets accommodating up to b=4 fingerprints. Mapping complies to the following rules:
- Fingerprints are equally sized and represented using [f / 4] hexadecimal digits. In Listing 2, each fingerprint requires three digits. This size corresponds to an FP probability of 0.3%.
- Fingerprints requiring less than [f / 4] digits are prepended with 0s. In Listing 2, fingerprints that would require one or two digits are prepended with 0s until their size is three digits.
- Fingerprints of multiple buckets are mapped sequentially within a single TXT-type ResourceRecord (RR).
- Buckets with vacant entries are delimited by a dot since their boundaries are not explicit. In Listing 2, the first bucket includes a single fingerprint (c64), thus requires a dot. In contrast, the second bucket is full (four fingerprints), therefore a delimiter is not necessary. The initial fingerprint of each bucket is underlined for clarity.
- Buckets that do not completely fit within an RR are split and the remaining part is inserted in the succeeding RR.
Listing 3 depicts the IncZn information serialization format. The last–serial parameter indicates that name modifications prior to this value are incorporated in the HsZns, thus providing a starting point for Recursors to retrieve recent changes.
The sequence parameter determines if an HsZn is stale and must be downloaded again, for example, when CF parameters are altered. The updates section maps the fingerprints of the modified names, their associated action (addition/deletion) and the CF buckets corresponding to the fingerprints (h1 and h2).
Consumed bandwidth during AXFRs: Cuckoo filters efficiently store large DNS zones
Table 1 depicts the bandwidth consumed by AXFR requests for HsZns, considering zones of various sizes. Diverse data serialization formats are available for mapping zone names into HsZns.
We considered CFs with multiple buckets mapped per RR, CFs with a single bucket mapped per RR and BFs with multiple bytes mapped per RR. FP probability was configured at 0.3%.
| Indicative Zone (Distinct FQDNs) |
Information Serialization Format | CF (Actual Size) |
||
|---|---|---|---|---|
| CF (Multiple Buckets / RR) |
CF (Single Bucket / RR) |
Bloom Filter (Multiple Bytes / RR) |
||
| ntua.gr (8,294) | 26.77 KB | 63.91 KB | 41.86 KB | 13.51 KB |
| su (109,719) | 352.1 KB | 876.1 KB | 553.11 KB | 178.59 KB |
| se (1,387,690) | 4.36 KB | 11.21 MB | 6.86 MB | 2.21 MB |
| ru (5,325,231) | 16.78 MB | 43.76 MB | 26.34 MB | 8.46 MB |
Table 1 — AXFR request consumed bandwidth for Hashed DNS Zones.
CFs assigning multiple buckets per RR outperform the other options and yielded reasonable values for modern network links although their bandwidth consumption is almost twice the actual CF size maintained in-memory.
Privacy-awareness evaluation: Cuckoo filters sustain brute force attacks
Furthermore, we assessed the capabilities of CFs to withstand brute force attacks in the context of DNS.
Table 2 depicts the true positives (TPs) and FPs when looking up all allowed character combinations for FQDNs with first label lengths between three and seven characters. We considered 37 different characters (Latin letters, digits and the hyphen). The mapped zone was ntua.gr and FP probability was 0.3%.
| 1st Label Length (Characters) | TPs (FQDNs) | FPs (FQDNs) | FPs / TPs (Ratio) |
| 3 | 320 | 57 | 0.18 |
| 4 | 640 | 1,789 | 2.80 |
| 5 | 1,178 | 68,296 | 57.98 |
| 6 | 1,183 | 2,532,293 | 2,140.57 |
| 7 | 1,363 | 93,665,989 | 68,720.46 |
Table 2 — Evaluation of CF privacy-awareness.
We observed that FQDNs with first labels longer than five characters are protected with high certainty as they result in a large number of FPs.
Notably, as the first label grows, brute force attacks require exponentially longer time since the total number of hashing operations becomes prohibitively large.
Interested readers may study our paper and use our open sourced code.
Contributors: Dimitris Kalogeras, Vasilis Maglaris
Nikos Kostopoulos is a Ph.D. Student at NTUA. His research focuses on network security tailored to the DNS.
The views expressed by the authors of this blog are their own and do not necessarily reflect the views of APNIC. Please note a Code of Conduct applies to this blog.