一、哈希碰撞是什么?
所谓哈希(hash),就是将不同的输入映射成独一无二的、固定长度的值(又称"哈希值")。它是最常见的软件运算之一。
如果不同的输入得到了同一个哈希值,就发生了"哈希碰撞"(collision)。
举例来说,很多网络服务会使用哈希函数,产生一个 token,标识用户的身份和权限。
AFGG2piXh0ht6dmXUxqv4nA1PU120r0yMAQhuc13i8
上面这个字符串就是一个哈希值。如果两个不同的用户,得到了同样的 token,就发生了哈希碰撞。服务器将把这两个用户视为同一个人,这意味着,用户 B 可以读取和更改用户 A 的信息,这无疑带来了很大的安全隐患。
黑客攻击的一种方法,就是设法制造"哈希碰撞",然后入侵系统,窃取信息。
二、如何防止哈希碰撞?
防止哈希碰撞的最有效方法,就是扩大哈希值的取值空间。
16个二进制位的哈希值,产生碰撞的可能性是 65536 分之一。也就是说,如果有65537个用户,就一定会产生碰撞。哈希值的长度扩大到32个二进制位,碰撞的可能性就会下降到 4,294,967,296 分之一。
更长的哈希值意味着更大的存储空间、更多的计算,将影响性能和成本。开发者必须做出抉择,在安全与成本之间找到平衡。
下面就介绍,如何在满足安全要求的前提下,找出哈希值的最短长度。
三、生日攻击
哈希碰撞的概率取决于两个因素(假设哈希函数是可靠的,每个值的生成概率都相同)。
- 取值空间的大小(即哈希值的长度)
- 整个生命周期中,哈希值的计算次数
这个问题在数学上早有原型,叫做"生日问题"(birthday problem):一个班级需要有多少人,才能保证每个同学的生日都不一样?
答案很出人意料。如果至少两个同学生日相同的概率不超过5%,那么这个班只能有7个人。事实上,一个23人的班级有50%的概率,至少两个同学生日相同;50人班级有97%的概率,70人的班级则是99.9%的概率(计算方法见后文)。
这意味着,如果哈希值的取值空间是365,只要计算23个哈希值,就有50%的可能产生碰撞。也就是说,哈希碰撞的可能性,远比想象的高。实际上,有一个近似的公式。
上面公式可以算出,50% 的哈希碰撞概率所需要的计算次数,N 表示哈希的取值空间。生日问题的 N 就是365,算出来是 23.9。这个公式告诉我们,哈希碰撞所需耗费的计算次数,跟取值空间的平方根是一个数量级。
这种利用哈希空间不足够大,而制造碰撞的攻击方法,就被称为生日攻击(birthday attack)。
四、数学推导
这一节给出生日攻击的数学推导。
至少两个人生日相同的概率,可以先算出所有人生日互不相同的概率,再用 1 减去这个概率。
我们把这个问题设想成,每个人排队依次进入一个房间。第一个进入房间的人,与房间里已有的人(0人),生日都不相同的概率是365/365
;第二个进入房间的人,生日独一无二的概率是364/365
;第三个人是363/365
,以此类推。
因此,所有人的生日都不相同的概率,就是下面的公式。
上面公式的 n 表示进入房间的人数。可以看出,进入房间的人越多,生日互不相同的概率就越小。
这个公式可以推导成下面的形式。
那么,至少有两个人生日相同的概率,就是 1 减去上面的公式。
五、哈希碰撞的公式
上面的公式,可以进一步推导成一般性的、便于计算的形式。
根据泰勒公式,指数函数 ex 可以用多项式展开。
如果 x 是一个极小的值,那么上面的公式近似等于下面的形式。
现在把生日问题的1/365
代入。
因此,生日问题的概率公式,变成下面这样。
假设 d 为取值空间(生日问题里是 365),就得到了一般化公式。
上面就是哈希碰撞概率的公式。
六、应用
上面的公式写成函数。
const calculate = (d, n) => { const exponent = (-n * (n - 1)) / (2 * d) return 1 - Math.E ** exponent; } calculate(365, 23) // 0.5000017521827107 calculate(365, 50) // 0.9651312540863107 calculate(365, 70) // 0.9986618113807388
一般来说,哈希值由大小写字母和阿拉伯数字构成,一共62个字符(10 + 26 + 26)。如果哈希值只有三个字符的长度(比如abc
),取值空间就是 62 ^ 3 = 238,328
,那么10000次计算导致的哈希碰撞概率是100%。
calculate(62 ** 3, 10000) // 1
哈希值的长度增加到5个字符(比如abcde
),碰撞的概率就下降到5.3%。
calculate(62 ** 5, 10000) // 0.05310946204730993
现在有一家公司,它的 API 每秒会收到100万个请求,每个请求都会生成一个哈希值,假定这个 API 会使用10年。那么,大约一共会计算300万亿次哈希。能够接受的哈希碰撞概率是1000亿分之一(即每天发生一次哈希碰撞),请问哈希字符串最少需要多少个字符?
根据上面的公式倒推,就会知道哈希值的最短长度是22个字符(比如BwQ1W6soXkA1PU120r0yMA
),计算过程略。
22个字符的哈希值,就能保证300万亿次计算里面,只有1000亿分之一的概率发生碰撞。常用的 SHA256 哈希函数产生的是64个字符的哈希值,每个字符的取值范围是0~9和a~f,发生碰撞的概率还要低得多。
七、参考链接
- How Long Should I Make My API Key?, by Sam Corcos
- Birthday problem, by Wikipedia
- Birthday attack, by Wikipedia
(完)
tkokof 说:
请教一下书写数学公式的工具,感谢~
2018年9月 5日 22:35 | # | 引用
Timor 说:
无形之中,又复习了一下高数。。
2018年9月 6日 09:25 | # | 引用
Denis 说:
"SHA256 哈希函数产生的是64个字符的哈希值" 这里的字符取取值范围是[0-9A-F], 只有16个值, 跟前文说的62个值的字符不是一回事, 如果用62个字符来表示SHA64的结果, 大约需要log62(2^256) ~= 43个字符.
2018年9月 6日 10:20 | # | 引用
支持阮老师 说:
不明觉厉,因为数学水平太渣 ;)
2018年9月 6日 10:43 | # | 引用
阮一峰 说:
@Denis:
谢谢指出,我忽略了这个问题,已经加了一行说明。
2018年9月 6日 11:31 | # | 引用
sevdot 说:
是时候去补一下高数了
2018年9月 6日 12:50 | # | 引用
as 说:
看了三遍才看懂,,,,
2018年9月 6日 15:13 | # | 引用
Charles 说:
您好博主,SHA256算法得到的哈希值是256位,也就是32字节,通常(ASCII编码或ISO8859-1编码中)一个英文字符对应一个字节,所以应该是32个字符,而不是博主说的64个字符。
2018年9月 6日 15:27 | # | 引用
阮一峰 说:
@Charles: SHA256 确实是256位,但是只使用 0-9 和 a-f 一共16个字符,每个字符只需要4字节,所以是64个字符。
2018年9月 6日 16:26 | # | 引用
禾浅 说:
干货啊……
2018年9月 6日 17:50 | # | 引用
Thinker 说:
office自带就有
2018年9月 6日 18:33 | # | 引用
您的大名 说:
哈哈 我猜 我猜的 可能是看了李永乐老师的视频 才写这篇博文的总结的 我是以小人之心,度君子之腹.
因为李永乐老师有一期视频叫 《手机支付中的数字签名是如何保证信息安全的?李永乐老师讲解生日碰撞和哈希函数》
地址:https://www.youtube.com/watch?v=uS1ZIAsvT5w
2018年9月 6日 19:12 | # | 引用
汪 说:
我不是来找茬的哈。0-9,a-f,区间内的每个字符只需要4个bit,所以总长度64*4=256个bit。
2018年9月 7日 09:50 | # | 引用
InQβ 说:
这里用的应该是 LaTeX 的渲染,codecogs 有一个在线的渲染器,能够输出 gif/png/svg 等多种格式
2018年9月 7日 14:35 | # | 引用
Orange 说:
看完这篇文章我懂得了 一个23人的班级至少两个人生日相同的概率竟然高达50%
2018年9月 7日 19:13 | # | 引用
standin000 说:
请问4节的概率公式怎么到5节的e公式的。
2018年9月 8日 10:10 | # | 引用
John Han 说:
现在体会到了高数的重要性
2018年9月10日 09:34 | # | 引用
v 说:
这里笔误了吧, 每个16进制字符需要4bit,而不是4个字节
2018年9月14日 17:37 | # | 引用
张宏 说:
这么说md5函数的 结果长度达到了32个字符,完全够用咯
2018年9月19日 09:41 | # | 引用
幼儿猿 说:
写的太好了,虽然高数知识跟不上,但是单从哈希碰撞这一方面来说的话,觉得很长知识,如何才能将哈希碰撞降到更低确实是值得去思考的问题。收录转载到我们的公众号,好的东西要让更多人看到。
2018年9月26日 17:24 | # | 引用
WangNianyi2001 说:
2018年10月28日 18:48 | # | 引用
稻香 说:
阮老师什么时候把360浏览器的兼容做一下,文章的一些链接字体看不到
2018年10月30日 15:57 | # | 引用
zhaojufei 说:
那么SHA256碰撞的概率是多少?只要是hash就有碰撞的可能,现在量子计算机还在研究中,一旦研究出来,对这个算法会有什么冲击?我是一直比较担心hash算法的。。。
2019年7月24日 14:52 | # | 引用
LONG 说:
我理解为:在取值空间d下计算n次的碰撞概率
那么这个计算是怎么计算的?是不是我只要计算n次,每次的key值不同就行?
2020年12月24日 17:15 | # | 引用
Lan 说:
这个生日碰撞是在 每个人出生日期概率为均匀分布的条件上的,那么其他的概率分布应该怎样计算呢?或者如何证明 均匀分布时,生日碰撞发生的概率最小?
2021年1月31日 02:45 | # | 引用
waidais 说:
哈希碰撞的结果不会让服务器认为两个值相同只是增加了查询的时间,黑客使用哈希碰撞攻击的目的是让服务器查询哈希表的耗时大幅度增加让服务器瘫痪
2021年8月27日 17:34 | # | 引用
顽石33 说:
又看到了数学公式好亲切的感觉!
2021年12月13日 15:35 | # | 引用
土豆 说:
说的是Hash洪水吗?
2022年12月12日 19:58 | # | 引用