最近同学阿里面试的时候被问到什么是哈希碰撞攻击，然后今天巧合下看到这篇文章: PHP哈希表碰撞攻击原理，就决定做一下简单的记录
基本原理
哈希表的原理是用数组来保存键值对，键值对存放的位置（下标）由键的哈希值决定，键的哈希值可以在参数时间内计算出来，这样哈希表插入、查找和删除的时间复杂度为O(1)，但是这是理想的情况下，真实的情况是，键的哈希值存在冲突碰撞，也就是不同的键的哈希值可能相等，一个好的哈希函数应该是尽可能的减少碰撞。解决冲突碰撞的方法有分为两种：开放地址法和 链接法，这里不具体展开。哈希表一般都采用链接法来解决冲突碰撞，也就是用一个链表来将分配到同一个桶（键的哈希值一样）的键值对保存起来。
所谓的哈希碰撞攻击就是，针对哈希函数的特性，精心构造数据，使所有数据的哈希值相同，当这些数据保存到哈希表中，哈希表就会退化为单链表，哈希表的各种操作的时间复杂度提升一个数量级，因此会消耗大量CPU资源，导致系统无法快速响应请求，从而达到拒绝服务攻击（Dos）的目的。
制造哈希碰撞的方法
PHP哈希表碰撞攻击原理中提到了一种比较简单的制造哈希碰撞的方法，这个方法利用了PHP中哈希表的两个特性：
- php中如果键值是数字，则直接将其作为哈希值
- 在对哈希值取余获取下标位置时，采用hash&tableMask(array.size-1)（用位运算代替%运算优化计算速度，这个的原理我在JAVA集合框架总结中也提到过）
利用这两个特性，可以按照以下的方法制造哈希碰撞：假设容量为2^16的哈希表，tableMask=0 1111 1111 1111 1111，接下来，可以以0为初始值，以2^16为步长，制造足够多的数据
0000 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0
0001 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0
0010 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0
0011 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0
0100 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0
……
概况来说只要保证后16位均为0，则与掩码位于后得到的哈希值全部碰撞在位置0。
Hash碰撞与拒绝服务攻击 中还提到四种制造哈希碰撞的方法
- 相等子串法
相等子串法是针对某些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分析方法，具有较高的执行效率。模差分的算法请参考http://wenku.baidu.com/view/f0bf451414791711cc7917b5.html?from=related。
攻击方式
HashTable在所有的Web应用框架上都有应用，我们对Web应用每次发起请求所提交的参数，服务器端都会将其存储在HashTable中供后台代码调用，所以哈希碰撞攻击的攻击方式一般都是通过发送包含大量碰撞键值的参数的post请求，来达到攻击的目的。
防护方式
- 限制POST请求的参数个数
- 限制冲突链表的长度
备注
Hash碰撞与拒绝服务攻击 中还提到PHP5的HashTable使用的函数是DJBX33A，Java（没有说是那个版本的jdk，有待考察） 的Hash函数是对DJBX33A的改造（使用的31而不是33，另外初始值为0而不是5381），两种哈希函数都可以使用相等子串法来获取该Hash函数的碰撞