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

[Javier Guerra Giraldez <javier@...>]

On Tue, Jan 3, 2012 at 4:30 PM, Ashwin Hirschi <lua-l@reflexis.com> wrote:
> Please check your calendar. We're writing 2012 and software that somehow
> interacts with/across the Internet is not considered to be in a "narrow
> range" (by any stretch of the imagination).

check your horizons.  Lua is used in far more environments besides
network-connected computers with RAM to spare.

Even then, most of my networked processes don't keep user-supplied
arbitrary strings long enough to let them accumulate.  Almost the only
exception to this is HTTP processing, and then i always put nginx in
front of it.  This hypothetical attack is just another reason to do
that.  it needs to be solved, but crippling the language in the
process wouldn't be wise.


> Scripting languages like Python, Ruby, Javascript and Perl are dealing (or
> have already dealt) with this hash collision issue by making the necessary
> changes to their hash implementations.

these languages already used the naïve 'all characters' hash proposed
by Vladimir, and still were vulnerable. their solution was to add some
randomization to the hash.  we were discussing here if that solution
still held with the current 'sparse' hash used by Lua.  it's not so
easy, but i think a clever use of random sampling would do the trick.


> I believe Lua needs to do the same. If it does not, it risks being deemed
> not suitable for writing software for the web. I don't know about you, but I
> for one would not like to see that happen.

i concur that a solution is needed, the sooner the better; but "doing
the same" won't work, since Lua uses hashtables in a very different
way than those languages.  one family of proposals is changing the
sampling, another is a better fallback on the degenerate case (so it's
not so degenerated), i'm sure the high powers of Lua can imagine a few
more.

but simply devolving to the far slower and memory hungry hashtables of
other languages is not a good strategy.


-- 
Javier