Zacard's Notes

Hash碰撞

发表于 | 分类于 | | 阅读次数

Hash定义

摘自百度百科：

Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

为什么会产生Hash碰撞

…通过散列算法，变换成固定长度的输出，该输出就是散列值…

既然是根据输入值，变换成固定长度的输出，那就必然会存在不同的输入产生相同的输出。

如何解决Hash碰撞

开放地址法

这种方法就是在计算一个key的哈希的时候，发现目标地址已经有值了，即发生冲突了，这个时候通过相应的函数在此地址后面的地址去找，直到没有冲突为止。这个方法常用的有线性探测，二次探测，再哈希。这种解决方法有个不好的地方就是，当发生冲突之后，会在之后的地址空间中找一个放进去，这样就有可能后来出现一个key哈希出来的结果也正好是它放进去的这个地址空间，这样就会出现非同义词的两个key发生冲突。

拉链法

拉链法是通过数组+链表的形式组合而成的。当发送碰撞后，只需将其追加到对应的链表中即可。如下图所示：

java中的HashMap也是采用这种方法解决Hash冲突的。

与开放地址法相比，拉链法有如下优点：

  • 拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短
  • 由于链接法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况
  • 开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而链接法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间
  • 用链接法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填入散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点

拉链法的缺点：

  • 链表指针需要额外空间
  • 以HashMap为例，如果每次插入都产生碰撞，HashMap将退化为一个链表而导致查询的时间复杂度从O(1)变成了O(n)。我们称之为HashMap退化。

P.S. 这里说明下，在jdk8下，HashMap有个改进。当链表的长度大于8时，将转化为一棵红黑树存储。这样即使在最差情况下，查找速度也将在O(lgn)

Hash碰撞攻击

由于存在Hash碰撞，攻击者只要制造大量碰撞的Hash输入。将会造成大量Hash堆积，轻则查询速度缓慢，拖累网站服务。重则内存溢出，网站服务崩溃。

如何进行Hash碰撞攻击

Hash碰撞攻击其实就是寻找Hash碰撞的过程。

目前寻找Hash碰撞的方式有以下4中：

  • 相等子串法：针对某些Hash函数具有相同的字符串组合在上下文中相同位置的Hash值都相同的特性来构造碰撞的。比如f（“string1”）=f（“string2”），那么字符串“aaastring1bbb”与字符串“aaastring2bbb”中，“string1”与“string2”具有相同的Hash值。针对这个特性我们可以构造任意多的碰撞，比如“Ly”和“nz”的Hash值相同，那么“LyLy”、“nznz”、“Lynz”、“nzLy”的Hash值都相同。
  • 生日攻击法：生日攻击方法没有利用Hash函数的结构和任何代数弱性质，它只依赖于消息摘要的长度，即Hash值的长度。这种攻击对Hash函数提出了一个必要的安全条件，即消息摘要必须足够长。生日攻击(传送门)这个术语来自于所谓的生日悖论（传送门）：在一个教室中最少应有多少学生才使得至少有两个学生的生日在同一天的概率不小于1/2？这个问题的答案为23。
  • 中间相遇法：生日攻击的一种变形，它不比较Hash值，而是比较链中的中间变量。这种攻击主要适用于攻击具有分组链结构的Hash方案。中间相遇攻击的基本原理为：将消息分成两部分，对伪造消息的第一部分从初试值开始逐步向中间阶段产生r1个变量；对伪造消息的第二部分从Hash结果开始逐步退回中间阶段产生r2个变量。在中间阶段有一个匹配的概率与生日攻击成功的概率一样。
  • 模差分法：比较高效。应该是目前效率最好的一种方法。传送门

如何抵御Hash碰撞攻击

这时候就需要一个算法良好的Hash函数，使最终的Hash值尽量的分布均匀。

目前主流的是time33算法及其变种。

time33算法代码示例：

1
2
3
4
5
6
7
8
public int time33(char[] str) {
    int hash = 0;
    for (char c : str) {
        hash = hash * 33 + c;
    }
    return hash;
}

为什么要用33这个倍数因子呢？

因为1到256之间的所有奇数，都能达到一个可接受的哈希分布，平均分布大概是86%。而其中33，17，31，63，127，129这几个数在面对大量的哈希运算时有一个更大的优势，就是这些数字能将乘法用位运算配合加减法替换，这样运算速度会更高。并不是所有基于time33的算法都使用33作为倍数，如Ngix使用的是time31，Tokyo Cabinet使用的是time37。

P.S. jdk的String.hashCode使用的是time31.而common-lang3中的HashCodeBuilder默认使用的是time37.

String.hashCode代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Returns a hash code for this string. The hash code for a
 * {@code String} object is computed as
 * <blockquote><pre>
 * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
 * </pre></blockquote>
 * using {@code int} arithmetic, where {@code s[i]} is the
 * <i>i</i>th character of the string, {@code n} is the length of
 * the string, and {@code ^} indicates exponentiation.
 * (The hash value of the empty string is zero.)
 *
 * @return  a hash code value for this object.
 */
public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}
坚持原创技术分享，您的支持将鼓励我继续创作！

热评文章