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

[Peter Cawley <lua@...>]

On Thu, Dec 29, 2011 at 5:37 PM, fredrik danerklint
<fredan-lua@fredan.se> wrote:
> Hi!
>
> I've would like to know if Lua is vulnerably to this hash collision that was
> presented at CCC yesterday.
>
> Slashdot articel
> http://developers.slashdot.org/story/11/12/29/1352219/microsoft-issuing-unusual-out-of-band-security-update
>
> The presentation on youtube:
> http://www.youtube.com/watch?v=R2Cq3CLI6H8
>
> And the information about this:
> http://packetstormsecurity.org/files/108209/n.runs-SA-2011.004.txt
>
> Overview:
>
> Hash tables are a commonly used data structure in most programming
> languages. Web application servers or platforms commonly parse
> attacker-controlled POST form data into hash tables automatically, so
> that they can be accessed by application developers.
>
> If the language does not provide a randomized hash function or the
> application server does not recognize attacks using multi-collisions, an
> attacker can degenerate the hash table by sending lots of colliding
> keys. The algorithmic complexity of inserting n elements into the table
> then goes to O(n**2), making it possible to exhaust hours of CPU time
> using a single HTTP request.
>
>
> They did mention that Lua could be vulnerably to this kind of an attack at
> the end of the presentation, so I would like to know if it is or not.
>
> --
> //fredan
>

The fundamental messages here are:
1) Inserting N elements into a hash table insertion is O(N^2) worst
case (regardless of what particular hash table implementation is being
used).
2) If non-randomised hash functions are being used, then inputs which
hit this worst case can be calculated (regardless of the particular
hash function).
3) If running a network service, any user-supplied input to a hash
table might be this worst case, leading to a DoS attack.

In terms of Lua:
1) Hash table insertion occurs when Lua code puts anything into a
table. Furthermore, hash table insertion occurs whenever a string is
created (as the string interning process uses a hash table).
2) Lua's hash function is non-randomised. Furthermore, for strings at
least 32 characters long, only at most 31 characters of the string are
used for the hash, so collisions are trivial to calculate. This also
means that randomising the hash function would also have to involve an
algorithm for choosing 31 characters at random, rather than the
current approach of doing so deterministically.
3) I have no idea how popular Lua is for network services.