hash << 5是一个简单的移位操作，可以换算成hash *32，该算法可以理解为 hash= hash* 33 + *arKey++ 同时如果提交的key超过7位，需要逐位进行运算。 构造冲突的key 为了方便计算，我们预期构造的两个key均设置为8位。从zend_inline_hash_func函数 来分析，进行unrolled操作的时候，如果两个key的前面6位相同，是不影响结果的，只需要 考虑碰撞后面两位字母。我们预期构造的两个key如下： Key1： xa[1]a[2] Key2： xb[1]b[2] 其中x是一个随机的6位的字符串。 根据算法hash= hash* 33 + *arKey++，如果需要计算出来的hash相同，我们需要满足如下 的条件： (5381*33+ Ascii(a[1]))*33+ Ascii(a[2])=(5381*33+ Ascii(b[1])*33+ Ascii(b[2]) 展开运算，得到如下结果 Ascii(a[1])*33+ Ascii(a[2])= Ascii(b[1])*33+ Ascii(b[2]) 剩下的工作就很简单了，查下Ascii表可以找出来很多组合，一组简单的结果如下： a[1]=2 b[1]=1 a[2]=2 b[2]=S 通过以下的demo代码可以进行验证 -----------------code------------------------- # include <stdio.h> # include <stdlib.h> # include <string.h> unsigned long zend_inline_hash_func(char *arKey, int nKeyLength) { unsigned long hash = 5381; for (; nKeyLength >= 8; nKeyLength -= 8) { hash = ((hash << 5) + hash) + *arKey++; hash = ((hash << 5) + hash) + *arKey++; hash = ((hash << 5) + hash) + *arKey++; hash = ((hash << 5) + hash) + *arKey++; hash = ((hash << 5) + hash) + *arKey++; hash = ((hash << 5) + hash) + *arKey++; hash = ((hash << 5) + hash) + *arKey++; hash = ((hash << 5) + hash) + *arKey++; } switch (nKeyLength) { case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ case 1: hash = ((hash << 5) + hash) + *arKey++; break; case 0: break; } return hash; } int main() { unsigned long hasha ; unsigned long hashb ; char *a = "abcdef22"; char *b = "abcdef1S"; printf ( "PHP Hashtable collisions Demo\r\nAuthor: Flyh4t\r\n\r\n " ); hasha = zend_inline_hash_func(a, strlen (a) + 1 ); printf ("[+]String: %s\r\n PHP5 HASHA: %ld\r\n " , a , hasha); hashb = zend_inline_hash_func(b, strlen (b) + 1 ); printf ("[+]String: %s\r\n PHP5 HASHB: %ld\r\n " , b , hashb); return 0 ; } ----------------------------------------------------- 结算结果如下： PHP Hashtable collisions Demo Author: Flyh4t [+]String: abcdef22 PHP5 HASHA: 1004317790 [+]String: abcdef1S PHP5 HASHB: 1004317790 达到了预期的效果。 |
