[ratelimits] Remarks regarding the Knot DNS 1.2.0 RRL implementation

[Marek Vavruša]

On 5 March 2013 09:25, Paul Vixie <paul at redbarn.org> wrote:
> can i ask, as before, that we all implement the same idea for now, just to
> give our deployers a chance to have all of their servers work the same way?
> if there's a flaw in the rrl spec, let's discuss it immediately. if there
> are better ideas, let's discuss those less immediately.
>
> in particular, any rrl attempt that uses simple buckets rather than bucket
> chains, is going to alias many tuples into one set of counters, and thus be
> incorrect per the current spec. the spec does not call for hashing at all,
> but what it does say is that the set of counters shall be denoted by a
> certain tuple. if you're denoting by a shorter tuple, you're not
> implementing rrl.

I agree more less. BIND RRL also aliases many tuples into one set of
counters, it's just less
probable. I don't feel like this is too much important, RRL is not a
silver bullet and I take it as a very clever yet simple way to combat
a problem nowadays, not as as thing that's meant to last.
And if there's a possibility that two flows will share a same limit
(unpredictably and time limited)?
I would be okay with that, if it works reasonably well otherwise.
But I also understand if anyone disagrees.

> bands, classifiers, separate limits for large responses, are all ideas worth
> considering... later, after we've got feature parity.
>
> paul

This is just about "how to identify flows", but it sounds reasonable.
Let's see what the deployers think first.

Kind regards,
Marek

>
> re:
>
>
> Marek Vavruša wrote:
>
> Hi Matthijs,
>
> at first, I was thinking of having multiple bands instead of just
> "positive" response.
> Similar to a traffic shaping problem where you prioritize smaller packets.
> I currently use 1k as a threshold for large packets.
> The original idea was - the "smaller" class yields larger portion of
> the rate and vice versa.
> Thinking about it, it seems quite reasonable and trivial to classify.
>
> Marek
>
> On 4 March 2013 13:50, Matthijs Mekking <matthijs at nlnetlabs.nl> wrote:
>
> Hi Marek,
>
> I like the idea of having a classification of large responses. It seems
> that the current RRL algorithm does not perform well if an attack is
> able to trigger various positive responses[1]. I agree that such
> performing such an attack is more complex than an ANY or NXDOMAIN
> attack, but it is certainly feasible (especially with NSEC).
>
> What do you consider large?
>
> Adding weight to the classes is a direction that we should definitely
> can look into. I guess the "penalty points" used in the Dampening
> proposal can form a good base for that.
>
> [1]
> http://www.nlnetlabs.nl/downloads/publications/report-rrl-dekoning-rozekrans.pdf
>
> Best regards,
>   Matthijs
>
>
> On 03/01/2013 06:11 PM, Marek Vavruša wrote:
>
> 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
> _______________________________________________
> ratelimits mailing list
> ratelimits at lists.redbarn.org
> http://lists.redbarn.org/mailman/listinfo/ratelimits
>
> _______________________________________________
> ratelimits mailing list
> ratelimits at lists.redbarn.org
> http://lists.redbarn.org/mailman/listinfo/ratelimits