Rate limiting DNS – Tony Finch

We have a problem that our authoritative name servers are being used in a traffic amplification attack, along the lines of this SANS ISC report, except we have been sustaining 1000 - 3000 queries per second for nearly a week.

We need a proper solution to DNS amplification attacks. It is not enough to focus on the surface features of the current attack (recursion desired, QTYPE=*) because they are easy for attackers to change. For instance, an ANY query for cam.ac.uk returns 2KB of data, and an MX query (with DO DNSSEC) returns 1.5KB - not much less.

Some kind of per-client rate limit seems to be in order: legit recursive DNS servers should not be making high volumes of queries to our authoritative servers. Here is an outline of a rate limiting scheme thought up by Ian Jackson, Mark Wooding, and me. It uses integer arithmetic, requires a fixed amount of memory, and has a small per-query overhead.

Set up a Bloom filter, sized to give a suitable false positive rate. (There are about ten million recursive DNS servers on the Internet.) Each bucket contains an integer (rather than a bit) large enough to hold a reasonable per-interval packet count.

When a query arrives, hash its source network (/24 for IPv4, /64 for IPv6) with some random data which you obtained at startup. The hash function should be optimised for speed rather than strength. You need two independent hash values, h1 and h2. Increment buckets in the Bloom filter with indexes h1 + i*h2 for 0 <= i <= n. The client's rate is the minimum of the counts in these buckets. If this rate is too large, refuse the query.

Periodically, scan the Bloom filter and multiply each bucket by some number less than one. This ages out old data. (Or should it be a subtraction for leaky-bucket rate limiting?).

That's it. This has probably been invented before, but I haven't searched the literature yet. If anyone has any pointers I'd be grateful :-)

Edit: Paul Vixie and Vernon Schryver have produced a response rate limiting patch for BIND which deals with this problem rather sooner and more thoroughly :-)