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

[Miles Bader <miles@...>]

"Ashwin Hirschi" <lua-l@reflexis.com> writes:
>> This sort of attack is only an issue in a very narrow range of
>> applications, and the people developing those applications need to be
>> aware of the issue.
>
> 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).

You think a majority of Lua-using apps "interact with/across the
internet"?!

Wacky...

> 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.

Shrug.  They are different languages, with different user communities
and applications.  Obviously languages like Ruby _do_ seem to be
overwhelmingly used in "across the internet" applications, so maybe
such a default makes sense for it.  But Lua is not Ruby.

> 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.

An "all characters" hash is not free, especially for _very_ long
strings (I regularly handle 500MB strings), and the benefit of such a
change needs to be weighed against the costs, weighted by the
likelihood of each case.  [This is especially true on less performant
hardware, and I think Lua is much more frequently used on such
platforms compared to more bloated/weighty languages like Python,
Ruby, etc.]

The Lua maintainers specifically used the partial string hash for
performance reasons:

    The hash function does not look at all bytes of the string if the
    string is too long. This allows fast hashing of long strings.
    Avoiding loss of performance when handling long strings is
    important because they are common in Lua. For instance, it is
    usual to process files in Lua by reading them completely into
    memory into a single long string.

[From "The Implementation of Lua 5.0"]

-Miles

-- 
Back, n. That part of your friend which it is your privilege to contemplate in
your adversity.