Hash Dos

wiki

Hashing attack benchmark

--------- 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

Hash algorithm analysis

-- number of bytes not used in hash function

==============================================================

String length                  < 15,  15-20 ,  20-32 , 32-64  

--------------------------------------------------------------

Lua 5.1                        0   ,    0   ,    0   , len/2

Lua 5.2.0                      0   ,    0   ,    0   , len/2

LuaJit 2.0.0-beta9             0-1 ,   2-4  , len-16 , len-16

An attacker only needs 3 bytes that are not used in the hash function to be able to generate over 16 million strings with the same hash value (all string need to be the same length). For Lua 5.1 & 5.2.0 the minimum string length needed is 32 bytes, for LuaJit 2.0 a min. length of only 17 bytes is needed.

Second Hash fix for Lua 5.1

Features

• Backport per Lua state random seed.
• Use [FNV1 hash function] as second hash when needed.

How it works

-- pseudo code, This is not true Lua code



function NewStringMarker(state, hash)

  local marker = {len = 0, is_marker = true, hash = hash, refcount = 0}



  local bucket = GetBucketHead(state, hash) -- get bucket

  Append(bucket, marker)

  return marker

end



function NewString(state, str, len, hash, has_marker)

  local elem = { len = len, has_marker = has_marker, hash = hash, str = str }



  local bucket = GetBucketHead(state, hash) -- get bucket

  Append(bucket, elem)

  return elem

end



function ReleaseStringMarker(state, str, len)

  -- rehash string with first hash function to find marker.

  local hash1 = FirstHashFunc(str, len, state.seed)

  local bucket = GetBucketHead(state, hash1)

  foreach(elem in bucket) do

    -- check if hash matches

    if (elem.hash == hash) then

      -- check if this is a marker

      if (elem.is_marker) then

        if (--(elem.refcount) == 0) then

          -- free unused marker and remove from bucket

          Remove(bucket, elem)

          return -- done

        end

      end

    end

  end

end



-- called by GC

function FreeString(state, elem)

  if (elem.has_marker) then

    -- find marker using first hash function

    ReleaseStringMarker(state, elem.str, elem.len)

  end

  assert(not elem.is_marker)

  -- free string element.

end



function LuaNewInternString(state, str, len)

  local first_hash = true

  local depth = 0

  local marker = nil

  local has_marker = false

  local hash1 = 0

  local hash = 0 -- current hash

  local bucket = nil



  hash1 = FirstHashFunc(str, len, state.seed)

  hash = hash1

rehashed:

  bucket = GetBucketHead(state, hash) -- get bucket using current hash value.



  foreach(elem in bucket) do

    -- check if hash matches

    if (elem.hash == hash) then

      -- check if this is a marker

      if (elem.is_marker) then

        marker = elem

      else

        -- check if this is the string we are looking for.

        if (elem.len == len and elem.str == str) then

          -- found string

          return elem

        end

      end

    end

    depth++

  end

  -- string not found

  if (first_hash) then

    -- check if there is already a marker for the first hash

    if (marker) then

      -- we need to search for the string using second hash function.

      has_marker = true

      hash = SecondHashFunc(str, len, hash1) -- seed second hash with first hash value

      depth = 0

      first_hash = false

      goto rehashed

    end

    -- if bucket is over limit

    if (depth > DEPTH_LIMIT) then

      hash = SecondHashFunc(str, len, hash1) -- seed second hash with first hash value

      -- create marker

      marker = NewStringMarker(state, hash1)

      marker.refcount++

      has_marker = true

    end

  else

    -- second hash function was used, inc. reference counter of marker.

    marker.refcount++

  end

  -- create new string

  return NewString(state, str, len, hash, has_marker)

end