seeding may not be an effective defense against hash flooding

[Josh Haberman <jhaberman@...>]

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