[ratelimits] Remarks regarding the Knot DNS 1.2.0 RRL implementation

Matthijs Mekking matthijs at nlnetlabs.nl
Tue Mar 5 09:12:51 UTC 2013


I think we are implementing the same idea right now. I disagree just
because we don't use bucket chains, we don't implement rrl.

We have implemented randomized seed so that collisions are not
predictable. Current implementation does not see many collisions occur.
If we would see more collisions, we could implement bucket chains or
some other collision avoid mechanism in NSD. The slow-start mode also
sounds as a neat idea and that might be also something to consider in
our implementation to avoid subsequent collisions.

Ideas can be exchanged now, I don't see any harm in discussing them now.
Better come prepared when more sophisticated attacks are going to happen.

Best regards,
  Matthijs

On 03/05/2013 09:25 AM, Paul Vixie 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.
> 
> bands, classifiers, separate limits for large responses, are all ideas
> worth considering... later, after we've got feature parity.
> 
> paul
> 
> 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


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 553 bytes
Desc: OpenPGP digital signature
URL: <http://lists.redbarn.org/pipermail/ratelimits/attachments/20130305/7e0d2912/attachment-0001.pgp>


More information about the ratelimits mailing list