单一hash的HashDoS攻击

对于单一hash，如果攻击者获悉了hash算法，就可能构造大量hash值相同的key进行攻击。大量key进入同一个hash slot，让hash table的查询从o(1)退化成o(n)。HashDoS

全域hash

针对HashDoS，一个朴素的思想就是随机选取hash函数，这样构造的攻击key就很大可能失效
具体来看，我们的根本目的是什么？
我们的根本目的是让key均匀分布在hash table的各个slot上

在给定单hash函数的情况下，均匀分布需要达到什么数学条件：
对于n个独立不同的keys，容量为m的hash table，如果满足均匀分布，则每个slot的使用量应当为|n/m|
也就是说，对于特定的key k，从剩余(n-1)个key中随机挑选一个k‘，则(k, k’)落到同一slot的概率为1/m，这样k所在slot的使用量才会满足(n-1) * 1/m = |(n-1)/m| = |n/m|

而我们需要变化的hash函数，那么扩展一下思维，给定一个hash函数=>给定一组hash函数，使用时随机选择一个hash函数，剩下的部分就转换为了上文刚刚讨论的单hash函数情况——
于是，我们需要一个hash函数集合，使得对任意(k, k’) from keys，从哈希函数集中随机选择一个哈希函数，(k, k’) 发生冲突的概率是1/m

于是，我们有全域hash的定义：

A randomized algorithm H for constructing hash functions h : U → {1,… ,M} is universal
if for all (x, y) in U such that x ≠ y, Pr _h∈H [h(x) = h(y)] ≤ 1/M(i.e, The probability of x and y such that h(x) = h(y) is <= 1/M for all possible values of x and y).

• Theorem定理:If H is a set of the universal hash function family, then for any set S ⊆ U of size N, such that x ∈ U and y ∈ S, the expected number of collisions between x and y is at most N/M.
  在全域hash下，与给定x冲突的值的期望个数是N/M

Proof:Each y ∈ S (y ≠ x) has at most a 1/M chance of colliding with x by the definition of “universal”. So,

• Let C_xy = 1 if x and y collide and 0 otherwise.
• Let C_x denote the total number of collisions for x. So, C_x = ∑ _{y∈S, x≠y} C_xy.
• We know E[C_xy] = Pr[ x and y collide ] ≤ 1/M.
• So, by the linearity of expectation, E[C_x] = ∑_y E[C_xy] < N/M.

证明
设Cx是表示与key x冲突的键值数量的随机变量，设Cxy是指示变量
Cxy = 1 if h(x) = h(y) and 0 otherwise
根据定理 E[Cxy]=1/m  
Cx=∑Cxy | y∈T−{x}
=》 E[Cx] = E[ ∑Cxy ]   | y∈T−{x}
          = ∑ E[Cxy] | y∈T−{x}
          = ∑ 1/m | y∈T−{x} 
          = n-1 / m

• 定理2:
  hash函数族将其映射到同一个slot中的概率是|H|/m
  设函数集合大小为|H|，则【从哈希函数集中随机选择一个哈希函数】这个操作会产生1/|H|的概率贡献。而hash集合中的hash函数应当是独立且地位平等的，设p(k_k'_collision_in_hashSet)为：对任意(k, k’) from keys，遍历hash集合中的hash函数输入(k, k’)而产生冲突的概率，有 p(k_k'_collision_in_hashSet) * 1/|H| = 1/m ，从而推得 p(k_k'_collision_in_hashSet) = |H|/m，也就是hash函数族将其映射到同一个slot中的概率是|H| * 1/m = |H|/m