DJBX33X是一种常见的产生hash的值算法,在PHP、JAVA、ASP.NET、Python等语言中都广泛使用。hash算法理想的情况下算复杂度能达到O(1),但是实际情况下冲突是不可避免的,一旦发生碰撞,时间复杂度就提高了,最坏的情况下算法复杂度会达到O(n^2),那么,这时候,问题就来了,如果执行的操作频繁的发生hash碰撞,那么服务器将会被消耗大量的资源,如果能找出特定的碰撞字符串,那么就能实施DOS攻击。

正常情况下hash算法是不可逆,但是实际上DJBX33X却能在一定程度上可逆,这也使得主动查找碰撞字符变为可能,算法代码如下:

DJBX33X算法思想很简单,就是将hash值*33,然后与字符串进行异或操作。虽然思想简单,但是效率高且难以发生碰撞。Alexander和Julian两位大牛在一场演讲中介绍了对这种算法的暴力破解方法(Efficient Denial of Service Attacks on Web Application Platforms ),具体过程不说了,感兴趣的可以详细看看他们的那场演讲和ppt,这里直接上实践结果:

用中间相遇算法暴力找出了字符串“QCMWaIOvpl”的多个冲突字符串:

hash

观看更多有关 的文章?

*

+
跳转到评论