[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: seeding may not be an effective defense against hash flooding
- From: Javier Guerra Giraldez <javier@...>
- Date: Mon, 18 Dec 2017 22:17:12 +0000
On 18 December 2017 at 18:26, Pierre-Yves Gérardy <firstname.lastname@example.org> wrote:
> What about string interning (which AFAIK uses a hash table
> internally)? Do you limit the string length before passing them to
> Lua? Or is it irrelevant for LuaJIT?
I'm afraid I don't understand what you mean. What I described was
about comparing the string interning process (which is the only time a
string's hash is computed) with different hashing algorithms.
As for string length, the current algorithm is O(1), that is, it takes
the same time no matter the string size. But in any case right after
calculating the hash (and comparing with existing string hashes), it
will be either copied or fully compared, both of these operations are
O(n). But this speed advantage is also what makes so trivial to
generate hash collisions.