Fork me on GitHub

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

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       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值是不同的。下面我们来验证一下。

3. 实验

test_hash.go

package main

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

直接在goland中打断点

第1次程序启动

image_1d5b36biagha1rbc17kq1ifac4s9.png-2991.9kB

第2次程序启动

image_1d5b37uiq1cobogakvr6a01do8m.png-2718.4kB

结论

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

后记

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

2021年6月21日 事实上,在golang的hashmap中有个hash0参数,
hash0 是哈希的种子,它能为哈希函数的结果引入随机性
以下情况都会重新赋值(随机种子)

1) 创建新的map
2) map被清空

type hmap struct {
...
   hash0     uint32 // hash seed
...
}

参考资料

  1. 哈希碰撞攻击

请我喝瓶饮料

微信支付码

1 对 “哈希碰撞攻击与防范机制”的想法;

  1. 感谢分享!已推荐到《开发者头条》:https://toutiao.io/posts/rdlk9g 欢迎点赞支持!使用开发者头条 App 搜索 334598 即可订阅《萌叔》

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注