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