[ratelimits] Remarks regarding the Knot DNS 1.2.0 RRL implementation

[Marek Vavruša]

Hi again,

regarding the previous announcement, I also have some remarks I'd like
to share and a few questions open to discussion.

As it's based on the RRL memo, it shares all the common traits - token
bucket algorithm, hashtable for buckets etc., so I'll just name what's
different. We classify responses into a several groups like positive
answers, empty, errors, nxdomain, wildcard, ANY and also
DNSSEC-related (like when the qtype is for RRSIG, DNSKEY etc.). We
also have a class for large answers (if it doesn't fall into any
special class), as the attacker may exploit basically any type in the
zone depending on the contents (TXT for example). I also thought about
the idea of adding some weights to the classes (like "small response"
class could get better rate than a large packet, amplification factor
could be a good metric for this).
But it didn't get implemented, as I wasn't sure whether it would be
worth the extra complexity. Any thoughts?
Rest is probably more/less quite similar.

Second thing is, how are the buckets stored. We chose a fixed-size
hashtable as in the NSD with no chaining, but handle the collisions
differently.
Because, if the seed (for hashing) is known in advance and the
attacker knows a sufficient number of names in the zone, it is
possible to precalculate the colliding packets and constantly reset
the rate in a bucket, avoiding being limited. Neat hashtable size
and a weaker hash function also doesn't help. We introduced a
randomized seed in a hash and also, when a collision occurs,
bucket enters a "slow-start" mode in which it receives a lesser rate
and cannot reset again for a 1 time frame. This is to avoid subsequent
collisions like described. Did anyone experience this? Another
question is whether this is worth bothering, as there are other
inherent and easier weaknesses.
Ugh, sorry for the long post.

Have a nice weekend,
Marek

--
 Marek Vavrusa Knot DNS
 CZ.NIC Labs http://www.knot-dns.cz
 -------------------------------------------
 Americka 23, 120 00 Praha 2, Czech Republic
 WWW: http://labs.nic.cz http://www.nic.cz