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

[Sean Conner <sean@...>]

It was thus said that the Great Sam Roberts once stated:
> I've been following along, and while I've seen credible claims that
> lua is susceptible to:
> 
> http://packetstormsecurity.org/files/108209/n.runs-SA-2011.004.txt
> 
> I haven't seen any lua code that proves it.
> 
> There isn't a standard POST parser in lua, but it should be possible
> for someone who believes this is a significant issue to write a small
> lua program that parses a 2 MB string of key/value pairs into a hash
> table and takes many hours to do so (for example, before it was
> modified, ruby could be caused to take 6 hours of i7 CPU time to parse
> a 2 MB post request).
> 
> Without such code, its a bit hard to see this problem as anything
> other than theoretical, and impossible to know whether any proposed
> changes actually are effective.

  Okay, I have a proof-of-concept.  The following Lua code:

	require "badhash"

	start = os.clock()
	good = {}
	bad  = {}

	for i = 1 , 2000000 do
	  local x = goodhash()
	  good[x] = true 
	end

	stop = os.clock() 
	print("good",stop - start)

	start = os.clock()
	for i = 1 , 20000 do
	  local x = badhash()
	  bad[x] = true  
	end

	stop = os.clock()
	print("bad",stop - start)

outputs the following:

good    8.36
bad     6.32

Note:  this on a quad-core 2.8GHz Pentium system.  Also note that the "good
hash" covers 2,000,000 distinct strings, while the "bad hash" covers only
20,000 (one hundred times less strings).  The "good hash" function generates
a random, 1024 byte string (not strictly text---it's 1024 bytes of random
data).  The "bad hash" function generates a similarly random 1024 bytes, but
the bytes that comprise the hash (from lstring.c:80) are identical from
string to string.  One last note:  This was coded for Lua 5.1.

  I'm currently hesitant to push the actual code to badhash() but will do so
if people think it's for the best.

  -spc (hmm ... dropping the number of calls of goodhash() to 200,000 (1/10
	the original calls) on requires 0.77 ... )