最近哈希表碰撞攻击(
Hashtable collisions as DOS attack)的话题不断被提起,各种语言纷
纷中招。本文结合
PHP 内核源码,聊一聊这种攻击的原理及实现。
哈希表碰撞攻击的基本原理
哈希表是一种查找效率极高的数据结构,很多语言都在内部实现了哈希表。
PHP 中的哈希表
是一种极为重要的数据结构,不但用于表示
Array 数据类型,还在 Zend 虚拟机内部用于存
储上下文环境信息(执行上下文的变量及函数均使用哈希表结构存储)。
理想情况下哈希表插入和查找操作的时间复杂度均为
O(1),任何一个数据项可以在一个与
哈希表长度无关的时间内计算出一个哈希值(
key),然后在常量时间内定位到一个桶(术
语
bucket,表示哈希表中的一个位置)。当然这是理想情况下,因为任何哈希表的长度都是
有限的,所以一定存在不同的数据项具有相同哈希值的情况,此时不同数据项被定为到同
一个桶,称为碰撞(
collision)。哈希表的实现需要解决碰撞问题,碰撞解决大体有两种思
路,第一种是根据某种原则将被碰撞数据定为到其它桶,例如线性探测
——如果数据在插
入时发生了碰撞,则顺序查找这个桶后面的桶,将其放入第一个没有被使用的桶;第二种
策略是每个桶不是一个只能容纳单个数据项的位置,而是一个可容纳多个数据的数据结构
(例如链表或红黑树),所有碰撞的数据以某种数据结构的形式组织起来。
不论使用了哪种碰撞解决策略,都导致插入和查找操作的时间复杂度不再是
O(1)。以查找
为例,不能通过
key 定位到桶就结束,必须还要比较原始 key(即未做哈希之前的 key)是
否相等,如果不相等,则要使用与插入相同的算法继续查找,直到找到匹配的值或确认数
据不在哈希表中。
PHP 是使用单链表存储碰撞的数据,因此实际上 PHP 哈希表的平均查找复杂度为 O(L),其
中
L 为桶链表的平均长度;而最坏复杂度为 O(N),此时所有数据全部碰撞,哈希表退化成
单链表。下图
PHP 中正常哈希表和退化哈希表的示意图。