散列表非加密散列函数的种子

Question

如果在调整大小或创建表的过程中将散列表种子设置为随机数，是否可以防止对此类散列表的DDoS攻击，或者，如果知道散列算法，攻击者仍然可以轻松地绕过种子？如果该算法对攻击者未知的随机生成的表使用Pearson散列函数，该怎么办？这样的表散列是否仍然需要种子，或者它是否足够安全？

上下文:我想为我的玩具web服务器的键值数据库使用磁盘上的哈希表，其中的键可能取决于用户输入。

Answer 1

有几种方法可以保护您的散列子系统免受“逆向选择”攻击，其中最流行的是命名为Universal Hashing，其中散列函数或其属性在初始化时随机选择。

在我自己的方法中，我使用了相同的散列函数，其中每个字符都与非线性混合的结果相加，依赖于uint32_t[256]的随机数组。数组是在系统初始化期间创建的，在我的代码中，它是通过读取/dev/urandom在每次启动时创建的。请看我在开源emerSSL程序中的实现。欢迎借用整个哈希表实现，或者仅使用哈希函数。

目前，我的散列函数来自参考来源，为double hashing搜索算法计算两个独立的散列。

有“简化的”哈希函数从源代码，以演示与S块阵列的非线性混合的想法“

uint32_t S_block[0x100]; // Substitute block, random contains

#define NLF(h, c) (S_block[(unsigned char)(c + h)] ^ c)
#define ROL(x, n) (((x) << (n)) | ((x) >> (32 - (n))))

int32_t hash(const char *key) {
  uint32_t h = 0x1F351F35; // Barker code * 2
  char c;
  for(int i = 0; c = key[i]; i++) {
    h  = ROL(h, 5);
    h += NLF(h, c);
  } 
  return h;
}