DNS Response Rate Limiting as implemented in NSD

By Wouter Wijngaards

(Note 10 Oct 2012: Rate limiting is worked on at this time, and is being tested, it is not available in NSD production code yet).

(Update 10 Dec 2012 : changed title to indicate it is based on Vixie and Schryver’s work)

Rate Limits

Rate limiting is seen as a way to combat reflection attacks, where spoofed UDP packets are bounced off DNS servers to attack a target, and rate limits stop these high volume query streams. BCP38 (source IP checks on originating networks, bcp38) is the real fix, but has not seen sufficient deployment. We would not want to complicate our software needlessly; the rate limiting must not become a target itself. But the knowledge that the DNS server has, makes rate limiting easier to implement. We chose an implementation that should be easy to separate from the DNS server, if desired. Our approach is based on RRL by Vixie and Schryver (RRL) and Tony Finch’s analysis (fanf).

The RRL (response rate limiting) is implemented in the NSD server, for convenience. This makes server operations easier and implementation faster, and it saves time classifying the response. This code is enabled with the — enable-ratelimit option for configure. We plan to implement RRL for NSD4 and NSD3. There is a whitelist option available for allowing higher traffic for some parts.

The approach is meant to be different from others, for code diversity goals, thus we do not use the code from Vixie and Schryver, but we use similar false positive prevention mechanisms. The NSD RRL code uses a fixed-size hashtable, and smoothed averaged qps rates per bucket. If two different source netblocks (/24 ip4, /64 ip6) hash to the same bucket, it is reinitialized, causing a potential false positive to turn into a false negative. Additionally, the SLIP mechanism from Vixie and Schryver is used to give TCP fallback in case of a false positive.

Usage

Use the configure script option — enable-ratelimit to compile NSD. There are a couple options in the nsd.conf file.

In the server section you have

rrl-size: <numbuckets> # This option gives the size of the hashtable. Default 1000000. More buckets use more memory, and reduce the chance of hash collisions.

rrl-ratelimit: <qps> # The max qps allowed (from one query source). Default 200 qps.

rrl-whitelist-ratelimit: <qps> # The max qps for query sorts for a source, which have been whitelisted. Default 2000 qps. The rrl-whitelist option causes queries to be whitelisted.

If you set the ratelimits to 0 then you disable ratelimiting.

For zones (and patterns in NSD4) you have

rrl-whitelist: <rrltype> # This option causes queries of this rrltype to be whitelisted, for this zone. They receive the whitelist-ratelimit. You can give multiple lines, each enables a new rrltype to be whitelisted for the zone. Default has none whitelisted. The rrltype is the query classification that the NSD RRL employs to make different types not interfere with one another.

Query classification

Ratelimits are applied for a specific combination of a query source, query classification type and a domain name. This is so that queries from a different source netblock do not impact queries from other netblocks. In case of a reflection attack, the netblock represents the target of the attack. Queries with a different rrltype classification do not hamper queries with another classification, so that an attack of one type does not stop legitimate queries of another type. The domain name is chosen to match the type of query, and makes the RRL more specific, e.g. the zone name for name-error responses (nxdomain), the query name for normal answers (positive), the zonecut for delegations (referral), …

The different classification types employed are:

• nxdomain
• error
• referral
• any
• wildcard
• nodata
• dnskey
• positive
• all

The all rrltype is a shortcut to whitelist all types with the rrl-whitelist configuration setting.

Setting the Rate Limit

The goal for setting the rate limit is to allow normal ‘heavy usage’, but resolvers are assumed to cache. False positives have to be avoided, this is where a legitimate query is rate limited. False negatives are considered acceptable, this is where an attack is not correctly noticed, and is not ratelimited. Unless you have unlimited memory, you cannot have perfection, you have to accept false positives or false negatives. We want to avoid false positives, and keep the false negatives low. The RRL has a performance impact of about 4% on NSD, but because it uses a hashtable this should not be affected by different configuration settings.

The number of hashbuckets has to be sufficient to classify traffic, which originates from DNS resolvers. But also the hashbuckets use up memory, about 20 bytes per entry in NSD. The default is set at one million. A value of millions is appropriate, because there are millions of resolvers, and also because 20Mb extra memory (with the defaults) is acceptable. If you have extra memory, more buckets means less hash collisions.

For some number of attacks we have to be able to keep track of the query rates for the attacks, in a way that does not hamper legitimate queries. This means that a separate hashbucket is needed for each attack and for the legitimate queries. If you have x attacks ongoing at one time, and y is the ratelimit, and z is the max qps that the server can do, then x ≈ z/y is the number of attacks that the server could keep track of without getting overloaded itself. And the number of hashbuckets must be a lot larger than x to avoid hash collisions.

Assume a server that can do 200k qps as its maximum performance, which is configured with a ratelimit of 200 qps. This server would be able to deal with 200.000/200 = 1000 ongoing reflection attacks of 200 qps without becoming overloaded itself. The 1M hashbuckets then gives 1.000.000/1000 = 1000 buckets per attack, for the attack itself one bucket and 999 separate buckets for legitimate queries. If the hash was random, this would be a 1/1000 chance of a hash collision between an attack and a legitimate query. Realistically, attacks may be much larger than 200 qps, and that would reduce the number of ongoing attacks the server can handle without getting overloaded itself, but less attacks means more buckets for legitimate queries, and thus a lower chance of a hash collision.

A hash collision is a problem, but need not necessarily lead to a false positive or false negative. The RRL in NSD checks if the source is the same, and if not reinitializes the rate counter, so that false positives should not happen by a collision. The zero counter allows another 200 queries of the attack to be let through after a collision, until the ratelimit is hit again, and this is the false negative. If such collisions are sporadic, then the queries let through should be relatively small. If such collisions happen too often, then the attacks may not be stopped properly. For this reason the hash employs a server-chosen secret to make it unpredictable so that collisions cannot be forced.

If this fails to avoid false positives, there is SLIP (from Vixie and Schryver) which causes TCP fallback to stop the false positive. In our implementation, we reply to half the queries with the TC flag set (and the packet is empty, only the query name), and half the queries are randomly dropped. This should give an amplification of less than 1.