Open Air-ban opened 2 months ago
本文简要介绍哈希碰撞以及其中的生日攻击数学模型
所谓哈希(hash),就是将不同的输入映射成独一无二的、固定长度的值(又称"哈希值")。它是最常见的软件运算之一
如果不同的输入得到了同一个哈希值,就发生了"哈希碰撞"(collision)。 举例来说,很多网络服务会使用哈希函数,产生一个 token,标识用户的身份和权限
AFGG2piXh0ht6dmXUxqv4nA1PU120r0yMAQhuc13i8
上面这个字符串就是一个哈希值。如果两个不同的用户,得到了同样的 token,就发生了哈希碰撞。服务器将把这两个用户视为同一个人,这意味着,用户 B 可以读取和更改用户 A 的信息,这无疑带来了很大的安全隐患
黑客攻击的一种方法,就是设法制造"哈希碰撞",然后入侵系统,窃取信息
防止哈希碰撞的最有效方法,就是扩大哈希值的取值空间
16个二进制位的哈希值,产生碰撞的可能性是 65536 分之一。也就是说,如果有65537个用户,就一定会产生碰撞。哈希值的长度扩大到32个二进制位,碰撞的可能性就会下降到 4,294,967,296 分之一
更长的哈希值意味着更大的存储空间、更多的计算,将影响性能和成本。开发者必须做出抉择,在安全与成本之间找到平衡
下面就介绍,如何在满足安全要求的前提下,找出哈希值的最短长度
哈希碰撞的概率取决于以下两个因素(假设哈希函数是可靠的,每个值的生成概率都相同)
这个问题在数学上早有原型,叫做"生日问题":一个班级需要有多少人,才能保证每个同学的生日都不一样?
答案很出人意料。如果至少两个同学生日相同的概率不超过5%,那么这个班只能有7个人。事实上,一个23人的班级有50%的概率,至少两个同学生日相同;50人班级有97%的概率,70人的班级则是99.9%的概率(计算方法见后文)
这意味着,如果哈希值的取值空间是365,只要计算23个哈希值,就有50%的可能产生碰撞。也就是说,哈希碰撞的可能性,远比想象的高。实际上,有一个近似的公式
$$\sqrt{\frac{\pi}{2}N}$$ 上面公式可以算出,50% 的哈希碰撞概率所需要的计算次数,N 表示哈希的取值空间。生日问题的 N 就是365,算出来是 23.9。这个公式告诉我们,哈希碰撞所需耗费的计算次数,跟取值空间的平方根是一个数量级
这种利用哈希空间不足够大,而制造碰撞的攻击方法,就被称为生日攻击
最有意思的来咯
这一节给出生日攻击的数学推导
至少两个人生日相同的概率,可以先算出所有人生日互不相同的概率,再用 1 减去这个概率
我们把这个问题设想成,每个人排队依次进入一个房间。第一个进入房间的人,与房间里已有的人(0人),生日都不相同的概率是365/365;第二个进入房间的人,生日独一无二的概率是364/365;第三个人是363/365,以此类推
365/365
364/365
363/365
因此,所有人的生日都不相同的概率,就是下面的公式
$$\bar{p}(n) = 1 \cdot \left(1 - \frac{1}{365}\right) \cdot \left(1 - \frac{2}{365}\right) \cdots \left(1 - \frac{n-1}{365}\right) $$
上面公式的 n 表示进入房间的人数。可以看出,进入房间的人越多,生日互不相同的概率就越小
这个公式可以推导成下面的形式 $$\frac{365!}{365^n(365-n)!}$$ 那么,至少有两个人生日相同的概率,就是 1 减去上面的公式 $$\bar{p}(n) = 1 - \left(1 - \frac{365!}{365^n(365-n)!}\right)$$
上面的公式,可以进一步推导成一般性的、便于计算的形式
根据泰勒公式,指数函数 ex 可以用多项式展开
$$e^{x} \sum_{k=0}^{\infty} \frac{x^k}{k!} = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!} + \cdots$$
如果 x 是一个极小的值,那么上面的公式近似等于下面的形式
$$e^x\approx 1 + x$$
现在把生日问题的1/365代入
1/365
$$e^{-\frac{1}{365}} \approx 1 - \frac{1}{365}$$
因此,生日问题的概率公式,变成下面这样
这段折腾半天,latex写不出来了,直接贴截图了
假设 d 为取值空间(生日问题里是 365),就得到了一般化公式 $$p(n,d) \approx 1 - e^{-\frac{n(n-1)}{2d}}$$
上面就是哈希碰撞概率的公式
上面的公式写成函数
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亿分之一(即每天发生一次哈希碰撞),请问哈希字符串最少需要多少个字符?
abc
62 ^ 3 = 238,328
calculate(62 ** 3, 10000) // 1
abcde
calculate(62 ** 5, 10000) // 0.05310946204730993
根据上面的公式倒推,就会知道哈希值的最短长度是22个字符(比如BwQ1W6soXkA1PU120r0yMA),计算过程略(真他妈写不动了卧槽)
BwQ1W6soXkA1PU120r0yMA
22个字符的哈希值,就能保证300万亿次计算里面,只有1000亿分之一的概率发生碰撞。常用的 SHA256 哈希函数产生的是64个字符的哈希值,每个字符的取值范围是0~9和a~f,发生碰撞的概率还要低得多
作者:张忠宝(快疯版) 文章参考:
部分数学计算由ChatGPT代劳
内容概览
本文简要介绍哈希碰撞以及其中的生日攻击数学模型
一、哈希碰撞是什么?
所谓哈希(hash),就是将不同的输入映射成独一无二的、固定长度的值(又称"哈希值")。它是最常见的软件运算之一
如果不同的输入得到了同一个哈希值,就发生了"哈希碰撞"(collision)。
举例来说,很多网络服务会使用哈希函数,产生一个 token,标识用户的身份和权限
上面这个字符串就是一个哈希值。如果两个不同的用户,得到了同样的 token,就发生了哈希碰撞。服务器将把这两个用户视为同一个人,这意味着,用户 B 可以读取和更改用户 A 的信息,这无疑带来了很大的安全隐患
黑客攻击的一种方法,就是设法制造"哈希碰撞",然后入侵系统,窃取信息
二、如何防止哈希碰撞?
防止哈希碰撞的最有效方法,就是扩大哈希值的取值空间
16个二进制位的哈希值,产生碰撞的可能性是 65536 分之一。也就是说,如果有65537个用户,就一定会产生碰撞。哈希值的长度扩大到32个二进制位,碰撞的可能性就会下降到 4,294,967,296 分之一
更长的哈希值意味着更大的存储空间、更多的计算,将影响性能和成本。开发者必须做出抉择,在安全与成本之间找到平衡
下面就介绍,如何在满足安全要求的前提下,找出哈希值的最短长度
三、生日攻击
哈希碰撞的概率取决于以下两个因素(假设哈希函数是可靠的,每个值的生成概率都相同)
这个问题在数学上早有原型,叫做"生日问题":一个班级需要有多少人,才能保证每个同学的生日都不一样?
答案很出人意料。如果至少两个同学生日相同的概率不超过5%,那么这个班只能有7个人。事实上,一个23人的班级有50%的概率,至少两个同学生日相同;50人班级有97%的概率,70人的班级则是99.9%的概率(计算方法见后文)
这意味着,如果哈希值的取值空间是365,只要计算23个哈希值,就有50%的可能产生碰撞。也就是说,哈希碰撞的可能性,远比想象的高。实际上,有一个近似的公式
$$\sqrt{\frac{\pi}{2}N}$$ 上面公式可以算出,50% 的哈希碰撞概率所需要的计算次数,N 表示哈希的取值空间。生日问题的 N 就是365,算出来是 23.9。这个公式告诉我们,哈希碰撞所需耗费的计算次数,跟取值空间的平方根是一个数量级
这种利用哈希空间不足够大,而制造碰撞的攻击方法,就被称为生日攻击
四、数学推导
最有意思的来咯
这一节给出生日攻击的数学推导
至少两个人生日相同的概率,可以先算出所有人生日互不相同的概率,再用 1 减去这个概率
我们把这个问题设想成,每个人排队依次进入一个房间。第一个进入房间的人,与房间里已有的人(0人),生日都不相同的概率是
365/365
;第二个进入房间的人,生日独一无二的概率是364/365
;第三个人是363/365
,以此类推因此,所有人的生日都不相同的概率,就是下面的公式
$$\bar{p}(n) = 1 \cdot \left(1 - \frac{1}{365}\right) \cdot \left(1 - \frac{2}{365}\right) \cdots \left(1 - \frac{n-1}{365}\right) $$
上面公式的 n 表示进入房间的人数。可以看出,进入房间的人越多,生日互不相同的概率就越小
这个公式可以推导成下面的形式 $$\frac{365!}{365^n(365-n)!}$$ 那么,至少有两个人生日相同的概率,就是 1 减去上面的公式 $$\bar{p}(n) = 1 - \left(1 - \frac{365!}{365^n(365-n)!}\right)$$
五、哈希碰撞的公式
上面的公式,可以进一步推导成一般性的、便于计算的形式
根据泰勒公式,指数函数 ex 可以用多项式展开
$$e^{x} \sum_{k=0}^{\infty} \frac{x^k}{k!} = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!} + \cdots$$
如果 x 是一个极小的值,那么上面的公式近似等于下面的形式
$$e^x\approx 1 + x$$
现在把生日问题的
1/365
代入$$e^{-\frac{1}{365}} \approx 1 - \frac{1}{365}$$
因此,生日问题的概率公式,变成下面这样
这段折腾半天,latex写不出来了,直接贴截图了
假设 d 为取值空间(生日问题里是 365),就得到了一般化公式 $$p(n,d) \approx 1 - e^{-\frac{n(n-1)}{2d}}$$
上面就是哈希碰撞概率的公式
六、应用
上面的公式写成函数
一般来说,哈希值由大小写字母和阿拉伯数字构成,一共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,发生碰撞的概率还要低得多
相关信息
作者:张忠宝(快疯版) 文章参考:
部分数学计算由ChatGPT代劳