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

[Sam Roberts <vieuxtech@...>]

OK, so quoting the report:

   ruby could be caused to take 6 hours of i7 CPU time to parse a 2 MB
post request

That seems ripe for exploit.

Whereas I rearranged your code to run standalone, and what I'm seeing
for 8MB of input to lua is it goes from about 2 seconds with random
data to about 44 seconds with crafted data. And I have an i3 CPU, not
i7, for what its worth.

That's not blowing me away.

% lua TestHeader.lua not-so-random.txt
not-so-random.txt       size    8388668 seconds to process      44.06
% lua TestHeader.lua random.txt
random.txt      size    8388668 seconds to process      1.89


Did I damage your code? Is lua's hash algorithm just so much faster
that it isn't as exploitable as other languages?

Note that the original report took pains to look at whether POST data
sizes had any particular limitations, and 2-8MB seemed to be common
limitations on how big a POST would be accepted, so while really huge
100MB or 1000MB crafted data might do bad things to lua, you can't
deliver that kind of attack payload unless a server is willing to
accept that much user-generated data.

Attached is my version of your code, will usage instructions on top.

--[[
call like

lua TestHeader.lua
lua random.txt
lua not-so-random.txt

By Petite Abeille, and made to run stand-alone by Sam Roberts
]]

if not arg[1] then
    print"Preparing data files, might take a while"

    local function Random()
        local aBuffer = {}

        for anIndex = 1, 32 do
            aBuffer[ anIndex ] = string.char( math.random( 59, 126 ) )
        end

        return table.concat( aBuffer )
    end

    local function NotSoRandom()
        local aChar = string.char( math.random( 59, 126 ) )

        return ( '%s%s%s%s%s' ):format( ( aChar ):rep( 28 ),
        string.char( math.random( 59, 126 ) ),
        aChar,
        string.char( math.random( 59, 126 ) ),
        aChar )
    end

    local function prepare(random, filename)
        local f = assert(io.open(filename, "wb"))

        repeat
            f:write( ( '%s: %s\n' ):format( random(), random() ) )
        until f:seek() > (8 * 1024 * 1024)

        print("file", filename, "size", f:seek())

        f:close()
    end

    prepare(Random, "random.txt")
    prepare(NotSoRandom, "not-so-random.txt")
    return
end


local function Trim( aValue )
    return ( aValue:gsub( '^[%c%s]+', '' ):gsub( '[%s%c]+$', '' ) )
end

local function ReadHeader( aReader )
    local aHeader = {}
    
    for aLine in aReader:lines() do
        local aKey, aValue = Trim( aLine ):match( '(%S-): (.*)' )
    
        if aKey then
            local aKey = Trim( aKey ):lower()
            local aPreviousValue = aHeader[ aKey ]
            
            aValue = Trim( aValue )
            
            if aPreviousValue then
                --aValue = aPreviousValue .. ',' .. aValue
            end
    
            aHeader[ aKey ] = aValue
        else
            break
        end
    end
    
    return aHeader
end

print("processing", arg[1])

local aTime = os.clock()

headers = assert(io.open( arg[1], 'rb' ))
ReadHeader( headers )

local bTime = os.clock()

print( arg[1], "size", headers:seek(), "seconds to process", bTime - aTime )