[ANN] Patch to fix hash DoS attack for Lua 5.1

["Robert G. Jakabosky" <bobby@...>]

I have created a patch for Lua 5.1 to strengthen it against hash DoS attacks 
(See previous thread [1] back in January).

Download the patch from [2].  The patch uses the FNV-1 [3] hash function when 
it detects a hash attack.  Under normal usage no strings will be hashed a 
second time.  When under attack only strings with the same hash value as the 
attack strings will be re-hashed with FNV.  For details on how the patch works 
see the pseudo code on the HashDos [4] wiki page on lua-users.org.

The patch also backports (from Lua 5.2.1-work1) the per Lua state random seed 
value that is used to seed the standard Lua hash function.

For testing the slowdown from a hash DoS attack I created a benchmark that can 
create strings that will have the same hash value.  If there are no objections 
I will release the benchmark code.

--------- Simulated HTTP POST attack
-- 40000 unique Strings, length 32, estimated POST data length 1.328Mbytes
                                   Good strings,       Bad strings
Lua 5.1                              0.430 secs          29.753 secs
Lua 5.1 (second hash fix)    0.452 secs           0.515 secs
Lua 5.2.0                           0.450 secs          29.850 secs
Lua 5.2.1-work1                 0.450 secs           0.380 secs
LuaJit 2.0.0-beta9              0.086 secs          11.988 secs

If the above table is hard to read view it on the wiki page [4].  There is 
also some more analysis of the hash algorithms used in Lua & LuaJIT.

1. http://lua-users.org/lists/lua-l/2012-01/msg00497.html
2. http://lua-
users.org/files/wiki_insecure/power_patches/5.1/lua_5.1_second_hash_fix.patch
3. http://www.isthe.com/chongo/tech/comp/fnv/index.html
4. http://lua-users.org/wiki/HashDos

-- 
Robert G. Jakabosky