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

[Matthew Wild <mwild1@...>]

On 2 January 2012 14:54, David Kolf <kolf@gmx.de> wrote:
> Leo Razoumov wrote:
>>
>> 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.
>>
>>
>> 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.
>
>
> I considered picking the 16 to 32 characters which aren't ignored at random,
> too. But then I noticed that an attacker only needs to pick 2 or 3
> characters that aren't used for the hash in order to generate enough
> collisions to cause trouble -- the probability for hitting ignored chars at
> random is way too high.
>
> And Lua has to skip chars or else the operation file:read("*a") would be a
> problem for big files.
>
> So I am afraid that Lua still needs to raise an error when there is an
> extreme number of collisions. (As Mark suggested it).

Or handle collisions more efficiently.

Consider that throwing an error is still an effective
denial-of-service attack against Lua network services. DoS is about
one or more users impairing quality of service for other users of the
service. The original post achieves this through hogging CPU time.
This proposed solution would basically allow an attacker to prevent
certain sets of strings from being sent by other users of the service,
probably leaving the server with little choice but to close their
connections.

For example, a theoretical attack against a Lua HTTP server would be
to make requests with lots of headers that collide with standard HTTP
header names/values. For example I could make requests to the server
containing user-agent strings that match Chrome's user-agent string,
*except* for the skipped characters. When a legitimate Chrome user
hits the server, an error would be thrown by not being able to store
the user-agent string for a perfectly valid request.

I'm not saying that throwing isn't a satisfactory solution in some or
even many cases, but in certain applications it can be almost as bad
as the original problem.

Regards,
Matthew