1.引子
哈希表的原理是用数组来保存键值对，键值对存放的位置（下标）由键的哈希值决定，键的哈希值可以在参数时间内计算出来，这样哈希表插入、查找和删除的时间复杂度为O(1)，但是这是理想的情况下，真实的情况是，键的哈希值存在冲突碰撞，也就是不同的键的哈希值可能相等，一个好的哈希函数应该是尽可能的减少碰撞。解决冲突碰撞的方法有分为两种：开放地址法和 链接法，这里不具体展开。哈希表一般都采用链接法来解决冲突碰撞，也就是用一个链表来将分配到同一个桶（键的哈希值一样）的键值对保存起来。
所谓的哈希碰撞攻击就是，针对哈希函数的特性，精心构造数据，使所有数据的哈希值相同，当这些数据保存到哈希表中，哈希表就会退化为单链表，哈希表的各种操作的时间复杂度提升一个数量级，因此会消耗大量CPU资源，导致系统无法快速响应请求，从而达到拒绝服务攻击（Dos）的目的。
绝大多数语言中map的默认实现都是HashMap，比如Golang、Python，Java有2种HashMap和TreeMap
2.攻击方法与防范机制
通过构造哈希值完全相同的字符串
比如 hash(str1) == hash(str2)
找到大量的哈希值相同的str1、str2、str3 …
这种攻击方法依赖的前提是hash函数本身是不变的。
那么如果hash函数是变化的，那么就会大大增加构造哈希值完全相同的字符串的难度。 由此衍生出方案1。
2.1 方案1 加salt
哈希值的计算变为 hash(salt + str)
salt为特殊的字符串，一般都是固定值
由于salt是不对外暴露的，所以黑客构造哈希值完全相同的字符串的难度就增大了
2.2 方案2 可变的hash函数
如果hash函数本身就是可变的，那么黑客几乎无法构造哈希值完全相同的字符串。
我们来看Golang是怎么做的
type _type struct {...kind uint8alg *typeAlg...
}
每个类型都有其对应的typeAlg
// typeAlg is also copied/used in reflect/type.go.
// keep them in sync.
type typeAlg struct {// function for hashing objects of this type// (ptr to object, seed) -> hashhash func(unsafe.Pointer, uintptr) uintptr// function for comparing objects of this type// (ptr to object A, ptr to object B) -> ==?equal func(unsafe.Pointer, unsafe.Pointer) bool
}
var algarray = [alg_max]typeAlg{...alg_STRING: {strhash, strequal},alg_INTER: {interhash, interequal},alg_FLOAT32: {f32hash, f32equal},alg_FLOAT64: {f64hash, f64equal},alg_CPLX64: {c64hash, c64equal},...
}
func strhash(a unsafe.Pointer, h uintptr) uintptr {x := (*stringStruct)(a)return memhash(x.str, h, uintptr(x.len))
}
最终我们可以看到
func memhash(p unsafe.Pointer, seed, s uintptr) uintptr {...
}
这里的种子是个每次程序启动都会变化的随机数。 也就是说每次程序启动，同一个字符串的hash值是不同的。下面我们来验证一下。
3. 实验
test_hash.go
package mainfunc main() {var a = make(map[string]int, 5)a["helloworld"] = 1println(a["helloworld"])
}
直接在goland中打断点
第1次程序启动
第2次程序启动
结论
第1次hash值和第2次hash显然不同，由于seed的存在，对于每次程序的启动，可以理解为hash函数都是不同的。
后记
由于笔者不是安全领域的专家，本文必定有所疏漏，欢迎批评指出
