Re: seeding may not be an effective defense against hash flooding

[Daurnimator <quae@...>]

On 4 October 2012 at 08:26, Josh Haberman <jhaberman@gmail.com> wrote:
> Previously there was a lot of discussion about possible hash flooding
> vulnerabilities in the Lua interpreter (where an attacker deliberately
> triggers O(n) worst-case hash table performance), and I see that Lua
> 5.2.1 includes code to seed its hash function with a random number to
> prevent this.
>
> I just came across this page that includes algorithms for producing
> hash collisions that are independent of seed for several popular hash
> algorithms:
>
> https://www.131002.net/siphash/
>
> This code is specific to CityHash and MurmurHash, but as these are
> both significantly more complicated that Lua's hash function, it seems
> likely that seed-independent collisions could be produced for Lua's
> hash function also.
>
> If this is true, the hash seeding in Lua 5.2.1 may not be effective as
> a defense against hash flooding.  I'm not an expert in the math
> involved so I hesitate to say anything authoritative-sounding, but it
> appears as though hash seeding may be a less valuable technique than
> previously thought for avoiding hash flooding.
>
> Josh


Today I read https://kate.io/blog/simple-hash-collisions-in-lua/ and I
think this issue might be worth bringing up again.

There are many situations where lua developers are using untrusted
input strings as table keys.

I'm curious what the performance hit is in the general case for
swapping to siphash.
Does anyone have suggestions for useful benchmarks?