[ratelimits] Remarks regarding the Knot DNS 1.2.0 RRL implementation

[Marek Vavruša]

Hi, my apologies for the delay, I was out on the weekend. Thanks for
the very good questions!

On 1 March 2013 18:31, Vernon Schryver <vjs at rhyolite.com> wrote:
>> From: =?UTF-8?Q?Marek_Vavru=C5=A1a?= <marek.vavrusa at nic.cz>
>
>> Second thing is, how are the buckets stored. We chose a fixed-size
>> hashtable as in the NSD with no chaining,
>
> It's good to hear about another implementation, but I do have a
> question.  What led to not using chaining in this implementation?
> Was it onlyh it the significantly simpler code?
>
> I obviously think the costs of chaining are worth the benefit of no
> false positives.  I have the impression that chaining might be added
> to the NSD code in a future version after private discussions about
> the Birthday Paradox and the probability of false positives due to
> hash collisions.
>
> Please understand that I'm not trying to attack anyone or anything,
> but discover if I'm wrong.

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.
So it is more of a question of whether it's better to have a smaller hash tables
and overfill them or have a large hash table with no overfilling.
Neither is best or worst, but I feel
the former isn't worth the effort here as it adds complexity of
maintaining a table size,
allocating per new buckets, by the way, is there any finite limit as
to how many buckets will it allocate?
Not sure, just asking.

Also, about the the efficiency of such an attack. There are about 8
classes, only positive responses
and different netblocks can complement to the variability significantly.
So one would have to collect a large number of names in a zone and
sweep with different spoofed source addresses
and check reliably (that's a problem) whether a collision occured,
this is not trivial nor time efficient and from my point of view, not
worth the effort. Or am I missing something?

>
>
>>                                               We introduced a
>> randomized seed in a hash
>
> That's a good idea, but I would change the seed occassionally to
> thwart attacks by bad guys, unless except when using a cryptographic
> hash function, which sounds too expensive.
> Changing the hash function should only leak a small burst, which
> shouldn't matter if it happens only no more than once per 10s or
> 100s of minutes.

Fully agree, this is a good idea.

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

Cheers,
Marek