Hash Dos

lua-users home
wiki

The string hashing algorithms used in Lua 5.1, Lua 5.2.0 and LuaJit 2.0.0-beta9 are vulnerable to hashing DoS(denial-of-service) attack (See thread [1] on Lua mailing list).

Hashing attack benchmark

In the benchmarks below all strings have the same length, "Good" strings have very few hash collision, "Bad" strings all have the same hash value. A string length of 32 bytes is used since it is easy to attack the hashing algorithms used in all the tested VM implementations (except Lua 5.2.1-work1, since it will hash the full string). LuaJIT 2.0.0-beta9 is vulnerable to hashing DoS with strings of length 15.

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

[Download second hash fix patch for Lua 5.1]

Features

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

RecentChanges · preferences
edit · history
Last edited May 1, 2012 10:01 am GMT (diff)