Hash Dos

wiki

哈希攻击基准测试

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

哈希算法分析

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

攻击者只需要 3 个哈希函数中未使用的字节，就可以生成超过 1600 万个具有相同哈希值的字符串（所有字符串需要相同长度）。对于 Lua 5.1 和 5.2.0，所需的最小字符串长度为 32 字节，对于 LuaJit 2.0，则只需要 17 字节的最小长度。

Lua 5.1 的第二次哈希修复

特性

• 每个 Lua 状态的随机种子回溯移植。
• 当需要时，使用 [FNV1 哈希函数] 作为第二个哈希。

工作原理

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