Re: So I had this weird idea to solve the indexing problem

Of course, I chose the extreme; but combining a few simple Knuth's modular hashes, whose multiplers are different primes (which can even be also randomly selected from a known set of primes when creating the hashmap, or when reindeing it), is genrally enough to resist most attacks without much cost.

I said SHA* are fast by experience with today's implementations (may be they are slow in the current Lua-only libraries, but Lua should provide a set of secure hashes by default because it has many usages.

And if your Lua table is indexed by keys that are critical data which have to be secured for privacy reasons (notably against response time-based side channels), you have to think about secure hashes.

If your hash function is still using a single basic Knuth multiplier with a small prime (like 17 or 21), your table is easily attackable and it is better to choose a large enough prime (at least 15 bits).

Le lun. 10 juin 2019 à 19:50, Gé Weijers <ge@weijers.org> a écrit :

On Mon, Jun 10, 2019 at 3:58 AM Philippe Verdy <verdy_p@wanadoo.fr> wrote:
However the nasty unbalanced hash trees only occur if you have not used a good enough hashing function; the implementation, above some table size, could arrange to use a stronger cryptographic function (e.g. SHA512, but still SHA1 is still very resistant) which will ensure a really flattened distribution, instead of a simple modular arithmetic function with the multiplication by known static prime (like the simple Knut's hashing function).

SHA-512 is not very fast when hashing small values. SHA-512 pads the value to at least 1024 bits, and then evaluate an 80 round function to complete the hash, which takes over 1000 cycles on Intel Skylake for instance. Hashing random integers, floats and short strings will be very slow because you always have to hash at least 128 bytes, which is mostly padding and a length field.

Some newer Intel and AMD processors have specialized instructions to speed up SHA-256, but even then you have to process at least 512bits over 64 rounds.

Almost-universal hash families are a better candidate for this kind of thing if your threat model includes hash collision DOS attacks. You do not need most of the properties of hash functions like SHA-512 to build a DOS attack resistant hashmap.

See: https://en.wikipedia.org/wiki/Universal_hashing

Gé