The team behind Knot Resolver, the scalable caching DNS resolver, is hard at work developing a complex solution for protecting DNS servers and other participants on the Internet alike against denial-of-service attacks. This effort is a part of the ongoing DNS4EU project, co-funded by the European Union1, which we are a proud part of.
To achieve this goal, we are introducing two new mechanisms:
Firstly, we are implementing rate-limiting of requests originating from the same host and/or network to mitigate attacks, even partially-distributed, using an efficient query-counting mechanism.
Secondly, we are working on a query prioritization mechanism based on measuring CPU time spent on requests, where higher CPU consumption decreases query priority from particular clients in the future, so that demanding clients do not hold back other, less demanding ones.
Most of the code central to this effort is also shared with Knot DNS, the authoritative DNS server, so the users of both projects may enjoy the benefits of this new DoS protection. As usual with projects from CZ.NIC, all of this code is also free and open source under the GPL license, so everyone is free to study and adapt it for their own exciting purposes.
In this article, which is a loose sequel to the Knot Resolver 6.x news article describing the new Manager and its workings, we will first describe basic limiting of individual hosts. Then, we will extend it to whole networks and add multiple methods of restriction. Afterwards, we will move on to query prioritization.
In this first installment, we shall concentrate on a conceptual description from the users’ and/or operators’ point of view, with several intentional (and clearly pointed out) technical inaccuracies. These serve the purpose of simplifying the high-level overview of the whole mechanism. The inaccuracies will then be addressed and corrected in another article, which will serve as a low-level deep dive into the technical solution.
The new features outlined in this article are set to ship this year in an upcoming release of Knot Resolver 6.
Limiting individual hosts, exponential decay, instant vs. rate limit
Let us imagine that for every address in the IPv6 and IPv4 address spaces, we have got a query counter2. For each request, we increment this counter assigned to the source address, unless it would exceed its limit. If we hit this limit, the query is not resolved and is either kept unanswered, or a so-called truncated answer is sent instead. The latter is described in more detail in the section on methods of restriction; first, let us focus on the function of the counters themselves.
Each millisecond, all counters are lowered by a constant fraction of their values. This is called exponential decay3. It resembles the decay of radioactive atoms, which is also described by its half-life – in our case, it is the time by which the counters halve their values.
We describe (and configure) the behavior of a counter using two parameters, the so-called instant and rate limits:
- The instant limit tells us how many queries can be fit into the counter during a single unit of time (in our case the span of a single millisecond) if it was originally zero; e.g. for a new host.
- The rate limit is then used to derive the half-life of the counter. It is the maximum value of queries per second (QPS) that are being sent regularly over an extended period of time. I.e. if the average QPS is higher than the rate limit, the counter is sure to eventually reach the instant limit and requests will be blocked.
In the following figure, we can see the relationship between the instant limit LI, the rate limit LR, and the half-life. The black staircase-like line represents the decreasing value of the counter (the counter’s load) in time after it was filled (and the user was restricted), with no more queries being received after the fill-up. Note that the rate limit LR is given in queries per second, but is always divided by 1000 in the figure, to illustrate its value per millisecond, since that is the granularity of measurement in the program. Also note, that in a real setting the value of LR would be smaller by several orders of magnitude (but such a chart would be unreadable, so we use higher values to better illustrate the behavior).
Let us say we get attacked by a single new host. We first answer their queries up to the instant limit; the counter gets filled up. We then begin refusing to answer until the counter has lowered enough so that another query (or multiple queries) fits there. We answer the little what fits, then keep on refusing again. In this second phase, the average number of queries per second answered is determined by the rate limit. It may be the case that several queries are answered each millisecond, or that a query is answered once per several milliseconds, depending on the rate limit.
This behavior is illustrated by this next figure, which shows how a counter value evolves under an attack with a constant query rate per second QR if the counter was initially zero. The queries sent in the red areas are being restricted. To illustrate this behavior under various conditions, we animate the query rate QR, while both the instant limit LI and the rate limit LR remain the same.
The instant limit is meant to be configured in such a way that a new client gets answers to enough of their queries in a short period of time, according to what is expected to be their normal behavior. The rate limit can then be set to a lower value saying that we accept normal behavior once per several seconds, or to a higher value if we can serve it more frequently. Thus, we set the instant limit according to the expected behavior of clients and the rate limit according to the performance of our server.
One more thing to note is that the set rate limit is reached only if requests are being sent regularly. This comes from the fact that a counter is always decreased by a fraction of its current value, so the decay is at its fastest if it was just below the limit. If a client waits for some time after hitting the limit, their counter is continuously decreasing, but the decrease is continuously slowing down. The strategy of sending a bulk of queries once per several seconds will thus get limited more strictly in a longer run than sending requests one-by-one in regular time intervals.
Limiting networks
Counting queries (only) from individual IP addresses would not work very well, especially for IPv6, where a single attacker can very easily obtain a huge amount of addresses. The usual approach is to simply pick a single address prefix length and limit with a fixed granularity, but that allows a single machine to deplete the whole limit for a prefix (i.e. a larger network, like an ISP). In other words, it would potentially allow a single culprit to easily deny service for a whole network, even if they were attacking only from a single address. Therefore, we choose a more complex hierarchical approach.
We pick several address prefix lengths and, for each of them, a constant that multiplies the chosen rate and instant limits that apply to prefixes of that length. For each request, we then consider all of the (4 or 5, depending on the address family) prefixes of its source address, including the entire address, and increase counters for each of them. If any of the counters were to exceed their limit, none of the counters are incremented and the query is restricted. Shorter prefixes have higher limits as they represent the sum of requests from larger networks. Multiplying both instant and rate limits by the same constant keeps the half-life unchanged, which is a desirable outcome.
Currently, we are considering the following prefixes and multipliers:
| IPv4 prefix | /32 | /24 | /20 | /18 |
|---|---|---|---|---|
| Multiplier | 1 | 32 | 256 | 768 |
| IPv6 prefix | /128 | /64 | /56 | /48 | /32 |
|---|---|---|---|---|---|
| Multiplier | 1 | 2 | 3 | 4 | 64 |
Considerations when choosing the prefixes and their multipliers are as follows: – A single address – regardless of whether it is IPv6 or IPv4 – has the same weight in order to make configuration less confusing. – An end network on IPv6 is typically between /64 and /48 in practice (see the related RIPE policy on prefix assignment for end-users). On IPv4 it’s just /32 or even multiple networks behind a single address via CGNAT. – ISP/LIR level: the minimal routable prefix on IPv4 is /24 and the address space is very dense and fragmented, due to address shortage. On IPv6 the situation is very different, and each RIPE’s LIR gets a /32 or a little shorter if needed (see the related RIPE policy on IPv6 address allocation and assignment).
Here, we would like to give a little shout out to our colleague Maria Matějka from the team developing the routing daemon BIRD for consulting these considerations, especially in the IPv6 space.
Methods of query restriction, multi-level limiting
As mentioned earlier, we can either drop rate-limited requests altogether, or send a minimal, truncated answer, which allows us to verify the client’s authenticity.
Let us first concentrate on UDP requests and truncated answers, which are an existing mechanism in DNS. By default, DNS communication commonly takes place over the fast but unreliable UDP. In a common case, should a complete answer to a query be too long to transfer in a UDP datagram, the answer gets truncated and a so-called TC bit is set in it, prompting the client to switch to the reliable, but at the same time more demanding TCP.
The rationale for sending such truncated answers to clients during rate-limiting is as follows: One of the downsides of DNS over UDP is that it is vulnerable to so-called amplification attacks. Put simply, a UDP client is easily able to spoof their IP address as there is no handshake and/or verification process, meaning that attackers are able to misuse DNS servers to flood victim machines with a relatively large volume of unsolicited UDP datagrams4.
So, an attacker may forge their source address and get our server to amplify the attack to another host. As such, we may get many forged UDP requests and only a few authentic. Dropping almost all of them would resolve the amplification attack, but keep authentic users out of service.
The alternative then is to send only very short UDP responses marked as truncated. Since TCP requires a handshake to establish a connection, the source address gets effectively verified, lessening the effect of amplification, since the UDP response packets sent by the DNS server will be relatively small. It can also be expected that attackers will not bother resending their requests over TCP, as it defeats the purpose of the amplification attack.
This brings us to an important observation: You may have noticed that this sort of shifts the purpose of rate-limiting. Instead of the DNS server using the mechanism to protect itself, it actually protects other actors on the Internet from being flooded by its DNS replies.
To further balance between the two methods of restriction (i.e. sending truncated answers and dropping queries), we can reply only to a fixed fraction of queries with truncated responses, and drop the rest. This approach is being considered for the authoritative Knot DNS.
Another approach is to introduce a lower soft limit for truncating and a higher hard limit for dropping. The soft limit may be set as a percentage of the instant/rate hard limits. This is the approach we are considering for Knot Resolver.
There is another important difference between the soft and hard limits. To keep the hard limit reachable, we need to keep incrementing the counters even when they get over the soft limit. This means that if an attacker keeps sending enough requests to reach the soft limit, but not enough to reach the hard limit, all of their queries will be answered with TC set. On the other hand, once requests are restricted by the hard limit, they do not get counted anymore until the limit is lifted5, and so from time to time there will be a request restricted only by the soft limit again. In other words, the hard limit – perhaps paradoxically – only slows down the response rate, and will always, from time to time, let some requests through; while the soft limit restricts everything until the client has slowed down their request rate enough.
The difference can be seen in the following figure. It is similar to the previous one, but in addition to the hard limits LI and LR, it also contains the soft limits L’I and L’R and soft-limited orange areas.
For requests received over TCP (including the encrypted DNS-over-TLS and DNS-over-HTTPS), using only a hard limit is enough as the source address is always authentic.6 It is also under consideration that Knot Resolver will not apply this rate-limiting mechanism to TCP at all, and will only rely on the prioritization mechanism described in this next section for connected protocols.
Different prices for different queries and prioritization
So far, we have been counting only the number of queries. There is however a significant difference in CPU consumption between different kinds of requests. For example, resolving cached requests received over UDP will be much cheaper than resolving not-yet-cached requests received over TLS.
To account for this, we keep the counting-only rate limiting described above, and add prioritization of requests, which takes CPU time into account. To estimate CPU consumption precisely, we define new counters for respective hosts and networks, much like in the rate-limiting case, but we measure CPU time spent on individual queries and add that to the counters (instead of only incrementing them by one, as is the case of the rate-limiting). Waiting for responses from upstream is excluded from these measurements, as Knot Resolver makes use of asynchronous I/O and can perform other tasks while waiting.
In this mechanism, we don’t use limits for blocking. Instead, we bucket the requests by their originators’ counter values into several priority levels, assigning lower priorities to those hosts/networks, whose CPU consumption was high in the past. Requests with the highest priority are processed immediately, while other requests are pushed to several queues based on their level and deferred to be processed at a later time.
The precise handling of different prefixes and when to drop requests that are too old and have thus probably gone stale is currently a subject of internal discussion and is yet to be decided. We may also decide to drop the lowest-priority queries when the server is overloaded.
Conclusion
This concludes the first part of DoS protection in Knot Resolver 6.
We have described the concept of counting and limiting queries, firstly for individual addresses, then for whole networks. We have then added multiple methods of restriction to the mix, discovering that the rate-limiting mechanism serves to protect from the DNS amplification attack in the process.
In the last section, we moved on to query prioritization using a modification of the mechanism developed for rate-limiting.
In the next article, we shall focus on the low-level implementation of the whole mechanism and correct some inaccuracies left in with the intent to simplify this high-level overview.
- Project number: 101095329 21-EU-DIG-EU-DNS
Project name: DNS4EU and European DNS Shield.
This project is co-funded by the European Union.↩︎ - A big simplification! Such a setup is actually impossible as there would potentially need to be a total of 232 and 2128 counters for IPv4 and IPv6 addresses, respectively. Even if the counters were only byte-sized (which they are not), that would require more memory than is even the theoretical maximum of the address space of 64-bit computers. The actually implemented technical solution to that problem will be described in another article.↩︎
- In an ideal world, exponentially decaying counters would never reach zero, they would only infinitely converge to it in time. That is of course not true in real-life computers, where the counters have a technically imposed precision, so, at some point, they actually will be zeroed out, provided that no matching requests come for a long time, but it is not very practical to consider. For all intents and purposes, the counters are non-zero unless they have just been initialized.↩︎
- A more in-depth description of the DNS amplification attack by CloudFlare: https://www.cloudflare.com/learning/ddos/dns-amplification-ddos-attack/↩︎
- This is actually caused by technical restrictions, which will be described in the low-level deep dive article.↩︎
- TC=1 can only be used on plain UDP anyway. Also, DNS Cookies (RFC 7873) would provide this property for plain UDP, but at the time of writing, only the authoritative Knot DNS implements them, and their adoption rate in the DNS world is very low altogether.↩︎
Authors: Lukáš Ondráček, Vladimír Čunát
Editor: Oto Šťáva