哈希碰撞攻击与防范机制

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | http://vearne.cc

哈希表的原理是用数组来保存键值对，键值对存放的位置（下标）由键的哈希值决定，键的哈希值可以在参数时间内计算出来，这样哈希表插入、查找和删除的时间复杂度为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       uint8
    alg        *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) -> hash
    hash 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值是不同的。下面我们来验证一下。

test_hash.go

package main

func main() {
    var a = make(map[string]int, 5)
    a["helloworld"] = 1
    println(a["helloworld"])
}

直接在goland中打断点

第1次程序启动

第2次程序启动

第1次hash值和第2次hash显然不同，由于seed的存在，对于每次程序的启动，可以理解为hash函数都是不同的。

由于笔者不是安全领域的专家，本文必定有所疏漏，欢迎批评指出

1. 哈希碰撞攻击

如果我的文章对你有帮助，你可以给我打赏以促使我拿出更多的时间和精力来分享我的经验和思考总结。