这篇文章讨论了哈希函数的安全问题和python的哈希实现

Hash DOS

所谓Hash DOS即利用hash碰撞增加服务器负担、使其无法响应正常用户的请求的情况，以下说明为什么可以利用哈希碰撞发起DOS攻击

哈希碰撞不可避免

哈希是一种摘要算法而非加密算法，它将任意长度的比特序列映射成一个固定长度的比特序列，根据抽屉原理/鸽笼原理：“n+1个苹果放到n个抽屉中，至少有一个抽屉里放了两个及两个以上的苹果”，哈希函数将具有无穷种情况的任意长度比特序列映射到有穷种情况的固定长度比特序列，所以必定存在一些比特序列，他们经过哈希运算后得到的值相等，即哈希碰撞

哈希碰撞容易发生

假设哈希表中有365个桶，那么往其中插入23个随机的数据，发生哈希碰撞的概率有多少?

实际上，概率高达50% ！将随机数据换成每个人的生日，这就是生日悖论

这说明，哈希碰撞发生的概率远超我们的预期

hash DOS的原理

以上说明了哈希碰撞容易发生，但这并不能解释为什么哈希碰撞能用于发起DOS攻击
哈希表在理想状况下，插入、查找、删除都是在常数时间内完成（时间复杂度O(1)），在最坏的情况下，时间复杂度是O(n)。大部分时候我们都认为哈希表的时间复杂度就是O(1)， 因此将哈希表用于系统关键处用于提高性能，然而由于哈希碰撞的不可预测性，哈希表的时间复杂度实际上是在O(1) ~ O(n)中摇摆，这就为系统关键处带来了不确定性。
设想现在系统关键处的哈希表由于发生了大量哈希碰撞，性能急剧下降，那么整个系统的性能也会急剧下降
假设有一个服务器维护一个哈希表，键是用户名字符串，值是用户的各种信息组成的对象，这个哈希表有一百万个桶，攻击者如果想要通过蛮力使哈希表性能恶化，鉴于一百万的量级，可能需要发起非常多操作才能达到预期。然而假设攻击者知道了服务器使用的哈希函数，例如服务器使用了一个不安全的哈希函数

long hash(char* username){
    long hash = 0;
    for (int i = 0; username[i] != '\0'; i++) {
        hash += username[i];
    }
    return hash;
}

这样的哈希函数可以轻松构造出哈希值相同的不同字符串，例如"zhansan"和"zhansbl"。于是攻击者精心构造了一千个这样的字符串然后发起了一百次操作，每次操作服务器就会遇到这一千个发生碰撞的键值对，逐个比较时间复杂度为O(n)，n为碰撞规模，精心构造的字符串极大地放大了每次操作的效果