Re: Hash Table Collisions (n.runs-SA-2011.004)

[Leo Razoumov <slonik.az@...>]

On Sun, Jan 1, 2012 at 12:48, Vladimir Protasov <eoranged@ya.ru> wrote:
> To avoid the problem we just should generate random salt at lua startup, then use it during hash generation. It will prevent attacker to guess which values will be placed in the same bucket.
> Also, check out Jenkins One-at-a-time hash, for example, here: http://en.wikibooks.org/wiki/Algorithm_implementation/Hashing
> If you'll initialize variable hash with a random number generated at startup time, like
>
>    uint32 joaat_hash(uchar *key, size_t key_len) {
>        uint32 hash = LUA_GENERATED_ON_STARTUP_SEED;
>        ...
>
> the attacker will not be able to guess which values will have the same hash, so It will not be easy to exploit this.
>

Salt would not help if one keeps ignoring characters the way Lua does.
Two strings that differ only in those characters that are ignored by
the hash function still hash to the same value.

--Leo--