[ratelimits] Remarks regarding the Knot DNS 1.2.0 RRL implementation

[Vernon Schryver]

> From: =?UTF-8?Q?Marek_Vavru=C5=A1a?= <marek.vavrusa at nic.cz>


> > For estimating collision rates, the seed, class, and qtype have a
> > total of less than 3 bits of entropy, and so must be ignored along
> > with the constants in the hash function.  At authoritative servers,
> > the qname also limited entropy.  At a server authoritative for 1000
> > domains, the entropy of the qname is only 10 bits.
>
> That is a good point - how much does it affect the resulting hash?
> I'm not familiar with the "3 bit" threshold for ignoring it, but it is
> a good point - I'm worried
> about class information content mostly. I'll do some measurements later on.

"Entropy" is a way of talking about the size of the range or number
of outputs of a hash function.  To a good approximation, at any given
time, there are fewer than 8 different combinations of seed, class,
and QTYPE.  My point is that almost all of the entropy is in the IP
address.


> No, maybe I explained it wrong. Let's say the bucket is assigned to 192.168.0.1,
> it has a remaining rate X for this time window. Now a 10.2.3.4 hits
> the same bucket,
> collision is detected, bucket is reassigned and marked and an extra
> portion of the rate is given to a bucket.

How do you detect the collision?  Do you do what the NSD code does?
I understand that to be:
   - save the IP address in bucket
   - during lookup, compare the IP address of the request with the
      IP address in the bucket.
     + If they differ, reset the counters and timers and save the 
          IP address in the bucket.
     + If they are the same, update the counters and timers and
         possibly drop the response.

The problem with that mechanism is not false positives or dropping
good responses.  False positives do not happen between separate IP
addresses although they can for a single IP address at about 1000 
qnames/second (birthday paradox).
Instead, the problem is false negatives or failing to block attacks
during collisions between legitimate requests and attack requests.

Perhaps someone else will compute the probability of failing to
block some of at least 1 attack stream among A attack streams while
handling N legitimate responses/second when both A and N are uniformly
distributed among B buckets.  When I tried that estimate last year,
the result was not fatal but I thought not good.


Vernon Schryver    vjs at rhyolite.com