美文网首页
全域hash 均匀分布 2022-07-18

全域hash 均匀分布 2022-07-18

作者: 9_SooHyun | 来源:发表于2022-07-18 20:30 被阅读0次

    单一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

    相关文章

      网友评论

          本文标题:全域hash 均匀分布 2022-07-18

          本文链接:https://www.haomeiwen.com/subject/idudirtx.html