[ratelimits] Remarks regarding the Knot DNS 1.2.0 RRL implementation

[Marek Vavruša]

On 4 March 2013 15:40, Vernon Schryver <vjs at rhyolite.com> wrote:
>> From: =?UTF-8?Q?Marek_Vavru=C5=A1a?= <marek.vavrusa at nic.cz>
>
>> I believe you store qname hash in the buckets (+other data of course),
>> so it's still
>> possible to have a collision, it's just that you use more bits
>> (qtype,rtype etc. stored separately)
>> and allow buckets with different netblocks under a same hash.
>
> Of course the BIND9 RRL hash function has collisions; collisions are
> fundamental to hashing.  What can differ is what happens when there
> is a collision.  What the BIND9 RRL code does not have is collisions
> between different client IP addresses on the same bucket of counters,
> timers, etc.  In the BIND9 RRL code, the hash function is used to find
> a chain of buckets of counters, timers, etc.  That chain is searched
> for the bucket with the right (QTYPE,QNAME,client IP).  I understand
> your code and the NSD code to have a single bucket of counters, timers,
> etc. for all (QTYPE,QNAME,client IP) tuples with a given hash value.

No, we use class instead of qtype, which is calculated from response
characteristics,
qtype is part of it. By the way, did you evaluate properties of BIND9
chosen hash function?
Just curious, because of what it looks like.

> I think the cost of chaining to prevent collisions on counters, timers,
> etc. is necessary, because the number of legitimate clients at which
> the probability that at least 2 clients at different IP addresses will
> collide on the same bucket of counters, timers, etc. without chaining
> is approximately the square root of the number of buckets.  If you
> have 1,000,000 buckets, then the probability is more than 0.5 that at
> least 2 clients among 1000 IP addresses making the same request will
> use the same bucket.  See https://www.google.com/search?q=birthday+paradox
>
> At authoritative servers where RRL makes sense, different clients
> are very likely to request the same (QTYPE,QNAME).

Ok, then 2 hashes among sqrt(num_buckets) will collide at p~0.5.
That is not the same, as the hash is calculated from the (IP,class,qname,seed),
you can't just narrow it down to "different IPs", just that at least 1
thing from the tuple changed.
IF that happens and two different IPs with the same (qtype,qname) will
hit the same bucket,
they take two tokens from it. If they issue the same request over and
over, well then, they should be rate limited. But we're playing nice
and if second IP will cause the collision -> part of the tokens will
be restored (but not multiple times per window), so it will still get
some kind of service.
IF they exhaust all the tokens together, then there's SLIP. I don't
see a point of exploiting this, if you want to deny most of the
service to victim, then you just spoof the address and that's it.
It may happen with a legitimate traffic yes, but will it make a
difference? Not much.

> I understand that the NSD RRL code deals with those collisions on
> counters by recommended very much larger thresholds for dropping
> responses than the thresholds of 10 or even lower recommended for
> the BIND9 code.  As long as the bad guys do not distribute
> reflection attacks, thresholds of 100 or 1000 are ok.

This worries me a lot. RRL will work "ok", but only until the bad guys realize,
that they can use multiple servers at once for the attack.
And it's not something we could fix at this level.

>
>
>>                                         is there any finite limit as
>> to how many buckets will it allocate?
>
> There are both a minimum or initial number of buckets and a maximum
> number of buckets.  When the maximum would be exceeded, the oldest
> bucket is recycled.  Unless the number of attacking IP addresses is
> larger than the number of buckets, it is safe to recycle the oldest
> bucket.

OK, sounds reasonable, thanks for clearing it up.

>> this is not trivial nor time efficient and from my point of view, not
>> worth the effort. Or am I missing something?
>
> I'm not sure if we're talking about collisions.  If so, I think you
> are missing the effects of the Birthday Paradox that make the
> probability of collision between legitimate clients high.
>
> You might notice that I wrote about collisions between clients instead
> of collisions between requests.  That is because each bucket of counters,
> timers, etc. in the BIND9 RRL code has a key consisting of
> (IP,class,QTYPE,hash(QNAME),ok/NXDOMAIN/ERROR)
> Using a 4 byte hash of the QNAME instead of variable space or a fixed
> space of 255 bytes for the QNAME lets the buckets be a fixed, modest
> size.  As long as a single DNS client fewer than than several thousand
> requests/second, it is unlikely to suffer a false positive.  Besides,
> a client making 1000s of requests/second for different QNAMEs probably
> should be rate limited.

Ok, that clears up the bit from the previous part when you talked
about clients, maybe I misunderstood.
At least for our implementation, you would need to estimate prob. of
collision of a request
and a probability that these two requests are from different IPs,
which could be estimated from the number of netblocks.

>
>
> Vernon Schryver    vjs at rhyolite.com
> _______________________________________________
> ratelimits mailing list
> ratelimits at lists.redbarn.org
> http://lists.redbarn.org/mailman/listinfo/ratelimits