hash-table 非加密哈希函数的种子

Question

如果在调整大小或 table 创建期间将哈希 table 种子设置为随机数，是否可以防止对此类哈希的 DDoS 攻击 table 或者，了解哈希算法，攻击者仍会轻松绕过种子？如果算法使用 Pearson 哈希函数和随机生成的 tables，攻击者不知道怎么办？这样的 table 哈希还需要种子还是足够安全？

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

Answer 1

有几种方法可以保护您的 hash-subsystem 免受“逆向选择”攻击，其中最流行的是 Universal Hashing，其中 hash-function 或属性在初始化时随机选择。

在我自己的方法中，我使用相同的散列函数，其中每个字符添加到 non-linear 混合的结果，uint32_t[256] 的随机数组的依赖项。数组是在系统初始化期间创建的，在我的代码中，它发生在每次启动时，通过读取 /dev/urandom。请参阅我在开源 emerSSL 程序中的实现。欢迎您借用整个 hash-table 实现，或仅借用 hash-function。

目前，我的 hash-function 来自参考来源为 double hashing 搜索算法计算两个独立的哈希值。

源代码中有“简化的”hash-function，以展示 non-linear 与 S-block 数组混合的想法

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

hash-table 非加密哈希函数的种子

Seed for hash-table non cryptographic hash functions

hash

hashmap

hashtable

hashset

hashcode