单一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 Cxy = 1 if x and y collide and 0 otherwise.
- Let Cx denote the total number of collisions for x. So, Cx = ∑ y∈S, x≠y Cxy.
- We know E[Cxy] = Pr[ x and y collide ] ≤ 1/M.
- So, by the linearity of expectation, E[Cx] = ∑y E[Cxy] < 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
网友评论