Lua string hash 算法

JSHash

Posted by qmsheng on January 26, 2018

我在前一篇文章介绍过下面这 3 个字符串拥有相同的 hash,会导致 Hash Dos 问题:

"0000000000000000000000000000000000"
"f0l0l0w0m0e0n0t0w0i0t0t0e0r0?0:0)0"
"x0x0x0x0x0x0x0x0x0x0x0x0x0x0x0x0x0"

但是 Lua 并没有将自己的 string hash 算法暴露出来,那应该怎么验证呢?其实翻看 Lua 5.1.4 源码,lstring.c 中关于 string hash 是这么定义的:

TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
  GCObject *o;
  unsigned int h = cast(unsigned int, l);  /* seed */
  size_t step = (l>>5)+1;  /* if string is too long, don't hash all its chars */
  size_t l1;
  for (l1=l; l1>=step; l1-=step)  /* compute hash */
    h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1]));
  for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)];
       o != NULL;
       o = o->gch.next) {
    TString *ts = rawgco2ts(o);
    if (ts->tsv.len == l && (memcmp(str, getstr(ts), l) == 0)) {
      /* string may be dead */
      if (isdead(G(L), o)) changewhite(o);
      return ts;
    }
  }
  return newlstr(L, str, l, h);  /* not found */
}

其实这个算法叫 JSHash,这里我用 LuaJIT 的 bit 来实现个:

local bit = require "bit"

local lshift = bit.lshift
local rshift = bit.rshift
local bxor = bit.bxor

local byte = string.byte
local sub = string.sub
local len = string.len

local function JSHash(str)
    local l = len(str)
    local h = l
    local step = rshift(l, 5) + 1

    for i=l,step,-step do
        h = bxor(h, (lshift(h, 5) + byte(sub(str, i, i)) + rshift(h, 2)))
    end

    return h
end

print(JSHash("0000000000000000000000000000000000"))
print(JSHash("f0l0l0w0m0e0n0t0w0i0t0t0e0r0?0:0)0"))
print(JSHash("x0x0x0x0x0x0x0x0x0x0x0x0x0x0x0x0x0"))

-- output:
-- 1777619995
-- 1777619995
-- 1777619995

可以看到上面 3 个字符串的 hash 都是:1777619995,必然会触发 hash 冲突。

另外需要注意的是 LuaJIT 的 hash 算法和 Lua 是不同的,其是一个 lookup3 的变种。

lookup3 也被暴雪公司使用于解析其各游戏的 MPQ 文件

有关字符串 hash 算法的对比,可以参考下面这两篇文章,写的都比我好: