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

[Vladimir Protasov <eoranged@...>]

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.

01.01.2012, 20:08, "Mark Hamburg" <mark@grubmah.com>:
> On Dec 31, 2011, at 7:33 PM, Tom N Harris wrote:
>
>>  On 12/31/2011 09:27 PM, Mark Hamburg wrote:
>>>  I am increasingly convinced that the best defense is to fail string interning when the buckets get too long. This obviously could reject some non-malicious cases, but those shouldn't be that common.
>>  What are the disadvantages to this approach? The VM would not be able to assume inequality if two pointers are different. Another option is to have a slower but more robust algorithm that is activated when the faster hash is insufficient. That would add a test to every table lookup and require a flag bit. Or store the hash function as a pointer which adds 4~8 bytes to the table.
>>
>>  In my oversimplified experiments with this, I found that the excess strings will eventually be removed by the GC. Aggressive collection makes it difficult to fill the string table with collisions. Though that still incurs a performance penalty, and doesn't help if the strings are being kept alive somehow. If the strings are keys in a regular table, such as decoded POST form fields, then you still have a problem on that table, even if you drop them from the internal string table.
>
> In my version of this, at some point string interning failures would start behaving like memory allocation failures — i.e., we simply would fail to generate the new string and would fail the operation attempting to generate it. So, pointer equality would still work for testing string equality.
>
> Mark

-- 
Best regards,
Vladimir Protasov.