版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://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 … }… 继续阅读 哈希碰撞攻击与防范机制