[dns-operations] DNS RRL light?

Vernon Schryver vjs at rhyolite.com
Sat Sep 15 01:07:13 UTC 2012

> From: Mohamed Lrhazi <ml623 at georgetown.edu>

> I am counting query_type+query_name, implemented as:
> set qhash [b64encode [md5 "$q_type:$q_name"]]
> I guess that's my "state blob". Is that good?

If possible, I'd use a bit hash function with lower CPU costs, although
speed might matter.  However, it sounds as this is all done as in shell
scripts, and so it's not expected to handle many queries per second.

Any good 128-bit hash will have no more collisions than a 128-bit
cryptographic hash function and might have fewer.  Contrary to ancient
superstition, cryptographic hashes have no fewer or better distributed
collisions than any other good hash function.  Cryptographic hashes
are only supposed to be hard to reverse and their collisions are
supposed to be hard to predict.  Those characteristics and their mundane
collision characteristics are based only hope and a trivial number
(compared to 2**128)of tests instead of mathematics like that behind
other hash functions such as cyclic redundancy checks.

If the IP address is handled elsewhere, any reasonable (not necessarily
'good') 32-bit hash such as `sum` or `cksum` should also have no
collisions that matter, be a lot faster, and need fewer bits.
The size of the state blob matters if you want to handle lots of
queries/second and so need to store window size blobs;
(10 seconds)*(100K blobs/second)=1M blobs.

The key for each BIND9 RRL state blob consists of
   - 129 bits of IP address.  Perhaps embedded IPv4 addresses would
      work, but this time I chose a separate IPv4/IPv6 bit.
   - qtype
   - simplistic 32-bit hash of qname to avoid a fixed size 256 byte
       buffer or worse, malloc
   - DNS class compressed to one bit for now
   - whether the response is an error, NXDOMAIN, or normal
   - whether TCP was used.
Most of the BIND9 RRL blob consists of other stuff including links,
counters, and timers.

> I am also dropping everything, during the drop window, as I did not
> want to keep the query info for too long, but since I will lower the
> window, it might be feasible.

Dropping everything increases the likelihood of dropping legitimate
requests, and so is another reason to make your window as short as

Vernon Schryver    vjs at rhyolite.com

More information about the dns-operations mailing list