C01a 哈希函数与三条安全性质:给数据按一枚指纹
从零讲哈希函数是什么、三条功能要求、三条安全性质怎么区分,以及为什么找碰撞只要 2^(n/2) 次。
一句话版
哈希函数把任意长的数据算成一串定长的「指纹」。正着算很快,倒着推不回去,两份不同的数据也很难撞上同一枚指纹。
这一讲从哈希讲到签名,分七页。这一页只讲哈希函数本身:它是什么,在什么意义上算安全。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 哈希 H(x) | hash function,读「H of x」 | 把任意长的数据算成定长指纹的函数 |
| 摘要 / 哈希值 | digest | 哈希算出来的那串定长结果 |
| 原像 | preimage | 被哈希之前的那份原始输入 x |
| 碰撞 | collision | 两份不同的输入算出了同一个哈希值 |
| bit | 比特,二进制的一位 | n bit 的输出一共有 2ⁿ 种可能 |
| 2ⁿ | 读「2 的 n 次方」 | 2 连乘 n 次,n 每加 1 数量翻一倍 |
一个类比:档案室的指纹册
档案室给每份进来的材料按一枚指纹,另册登记。材料可以是一张便条,也可以是一整箱卷宗,按出来的指纹大小都一样。
按材料取指纹很快。拿着一枚指纹,却造不出那份材料,这叫单向。
两份不同的材料按出了同一枚指纹,叫碰撞。指定一份材料、去造另一份指纹相同的,比随便造两份指纹相同的难得多。这一页的三条性质就是在说这三件事。
类比在哪里失效:
- 真指纹几乎天然唯一。哈希的输出长度固定,输入却无穷多,碰撞一定存在,只是找不到。
- 指纹册不保密。材料只有三种可能时,看一眼指纹就知道是哪份,这一点留到 C01a-4 讲。
从零讲起
1. 哈希函数是什么
它解决什么问题
数据可能很大,一部电影几 GB。想核对两份数据是否一样,逐字节比太慢,传过来再比又太费带宽。
要是每份数据都有一个很短、长度固定的代表,比这个代表就够了。哈希函数负责算出这个代表。
从哪来(补充)
「哈希」这个思路最早出现在 IBM 的 Hans Peter Luhn 写于 1953 年 1 月的一份内部备忘录里。当时是为了给数据快速分桶查找。
这个词正式印进文献,又过了十几年。密码学里用的哈希多加了几条安全要求,下一个概念就讲。
直觉
把哈希想成一台绞肉机。什么东西都能放进去,出来的都是一样大小的一团。
同样的东西放进去,出来的永远一样。换一个字节,出来的就面目全非。出来的那一团,没法还原成原来的样子。
一步一步看
目标:拿 SHA-256 逐条对照三条功能要求和确定性,看出哈希值为什么能当任意数据的短代表。
课件给了三条功能要求,这里拿同一个函数 SHA-256 走一遍。
-
输入长度任意:6 个字节的 qwerty、5 个字节的 hello、几 GB 的一部电影,都能放进去算。
-
输出长度固定:三份输入算出来的都是 64 个十六进制字符,也就是 256 bit。
-
正向计算容易:算一次哈希很快,电脑每秒能算很多次。
-
再验一下「确定性」:明天再算一次 qwerty,得到的还是 65e84be3 开头的那一串。
怎么判断
拿到一个函数,按三条要求逐条问:
- 能不能吃下任意长度的输入?
- 不管输入多长,输出是不是一样长?
- 正着算是不是很便宜?
三条都满足,它才算一个哈希函数。注意第三条:区块链里的哈希每秒要算海量次,必须快。
后面 C01a-2 会讲一个「故意很慢」的哈希。那是密码存储这个特殊场景,两者不矛盾。
常见误解
以为哈希就是加密
加密有一把钥匙,持钥匙的人能把密文解回明文。哈希没有钥匙,谁都解不回去,也不打算解回去。它的用途是核对,不是藏东西。
以为输出长度固定,所以输入长度也有上限
输入长度没有上限,输出长度固定。正因为这样,不同输入撞上同一个输出是必然存在的,这就是下一个概念要处理的碰撞。
试一下
SHA-256 的输出是 256 bit。写成十六进制要几个字符?
一个十六进制字符表示 4 bit,256 ÷ 4 = 64,所以是 64 个字符。
一个函数把任何输入都映射成它的第一个字节。它满足三条功能要求吗?好用吗?
三条功能要求都满足:吃任意输入、输出固定 1 字节、算得快。可它完全不安全,开头相同的两份数据就会撞在一起。功能要求只保证能用,安全要靠下一个概念的三条性质。
2. 三条安全性质
它解决什么问题
功能要求只说了「能算」。要拿哈希来防篡改、存密码,还得保证攻击者造不出想要的结果。
课件用三条性质把「安全」说清楚,三条的区别是这一讲最常考的点。
直觉
想象攻击者在玩三种游戏,难度依次降低:
- 单向:给他一枚指纹,让他造一份能按出这枚指纹的材料。
- 第二原像:给他一份具体的材料,让他造另一份指纹相同的。
- 强抗碰撞:什么都不给,让他随便造两份指纹相同的材料。
最后一种他能自由挑两份,回旋余地最大,所以最容易得手。
一步一步看
目标:把三条安全性质并排比,看每一条里哪些输入是题目给定的、哪些由攻击者自己挑。
-
单向性(one-way):题目给定一个哈希值 h。攻击者要找任何一个 x,让 H(x) = h。他手上只有 h。
-
第二原像抗性(weak collision-resistant):题目给定一个 x。攻击者要找另一个 y,让 H(y) = H(x)。x 是定死的,他只能挑 y。
-
强抗碰撞(strong collision-resistant):题目什么都不给。攻击者自己挑 x 和 y,只要不同、哈希相等就算赢。
-
三格并排看,虚线框是攻击者自己挑的,实线框是题目给定的。从左到右,攻击者能控制的输入越来越多。
-
「难以找到」指计算上做不到,要算的次数多到不现实。数学上这样的输入是存在的。
怎么判断
碰到一个攻击场景,先圈出题目给了什么:
| 题目给定 | 攻击者挑 | 对应性质 |
|---|---|---|
| 哈希值 h | 一个 x | 单向性 |
| 一个具体输入 x | 另一个 y | 第二原像抗性(弱抗碰撞) |
| 什么都不给 | x 和 y 两个 | 强抗碰撞 |
再记一条逻辑关系:强抗碰撞 ⇒ 弱抗碰撞,⇒ 读「推出」。
意思是:一个函数连「随便挑两份」都防得住,「指定一份再找另一份」这种更受限的情形自然也防得住。反过来不成立,防住受限的情形不代表防得住更宽松的。
常见误解
以为「强」说的是攻击更强
强和弱说的是性质的强度。强性质要防的反而是更容易的那种攻击,因为攻击者两个输入都能挑。所以满足强性质的函数一定满足弱性质。
以为单向性在任何输入上都成立
单向性的前提是输入空间足够大。输入只有三种可能时,攻击者不用倒推,把三种各算一遍对照就行。课件在这里埋了一句:有时要给原像加随机字节,防止别人根据上下文猜出来。
试一下
攻击者手里有一份签好的合同,想造一份内容不同、哈希相同的假合同。他在攻击哪条性质?
合同是给定的,他只能挑假合同这一个输入,所以攻击的是第二原像抗性(弱抗碰撞)。
如果攻击者能自由起草两份合同,一份给对方签,一份留着替换,攻击的是哪条?
两份都由他挑,变成碰撞攻击,对应强抗碰撞。这种攻击更容易得手,所以强抗碰撞是更高的要求。
3. 生日攻击:为什么碰撞比原像好找(补充)
它解决什么问题
输出 n bit 时,一共有 2ⁿ 种可能的哈希值。直觉上,找什么都要试 2ⁿ 次。
可是课件说 SHA-1 被攻破时的成本是 2⁶⁹,比 2¹⁶⁰ 小得多。这个差距一部分就来自生日攻击:找碰撞的成本天然只有找原像的平方根。
从哪来(补充)
名字来自「生日问题」:一屋子 23 个人,就有超过一半的概率有两人同一天生日,70 个人时概率到 99.9%。
23 远小于一年的天数,因为要比的是「任意两人」,两两配对的数目涨得飞快。
出处:Wikipedia: Birthday problem,Wikipedia: Birthday attack
直觉
找原像,是拿一枚指定的指纹去撞,每试一次只有一次机会。
找碰撞,是随便造一堆材料,看其中任意两份有没有撞上。造了 k 份,就有大约 k²/2 对可以比。配对数随 k 的平方增长,所以 k 不用很大就能凑出一对。
一步一步看
目标:拿 SHA-1 比较暴力找原像、生日攻击和实际攻击的成本,看出找碰撞为什么比找原像便宜得多。
拿 SHA-1 来算,它的输出是 160 bit。
-
暴力找原像:最坏要试遍 2¹⁶⁰ 种可能。
-
生日攻击找碰撞:试约 2^(160/2) = 2⁸⁰ 次,就有约一半的把握撞出一对。
-
2005 年王小云等人用差分攻击,把找碰撞的成本压到约 2⁶⁹。
-
2017 年 SHAttered 实际造出了一对碰撞文件,用了约 2⁶³ 次计算。
-
这几根条按指数画。指数砍一半,次数就开平方,差距大得惊人。
怎么算
记两个式子:
- 找原像:约 2ⁿ 次
- 找碰撞:约 2^(n/2) 次
意思是:输出位数砍一半,再算 2 的那么多次方,就是找碰撞的大致成本。
代一个数:n = 160 时,2^(160/2) = 2⁸⁰。这是 SHA-1 抗碰撞的理论上限,任何攻击压到这以下,就算攻破了抗碰撞。
所以想要 128 bit 的抗碰撞安全,输出至少要 256 bit,这也是课件建议迁移到 SHA-256 的一个原因。
常见误解
以为 2⁸⁰ 只是 2¹⁶⁰ 的一半
2⁸⁰ 是 2¹⁶⁰ 的平方根。2¹⁶⁰ ÷ 2⁸⁰ = 2⁸⁰,差了 2⁸⁰ 倍,远不止一半。
以为生日攻击能用来找原像
生日攻击靠的是「任意两个撞上就行」。找原像要撞一个指定的值,没有配对的便宜可占,还是 2ⁿ 量级。
试一下
一个哈希输出 64 bit。找碰撞大约要试多少次?
2^(64/2) = 2³²,大约 43 亿次,一台普通电脑就能跑完。所以 64 bit 的哈希在抗碰撞上不够用。
MD5 输出 128 bit。生日攻击的理论成本是多少?
2^(128/2) = 2⁶⁴。实际攻击比这还便宜得多,下一页讲。
把它们串起来
哈希函数先要满足三条功能要求:吃任意长的输入,吐定长的输出,正着算得快。这只说明它能用。
能不能用来防人,看三条安全性质。区分它们只问一句:攻击者能自己挑几个输入。挑得越多,攻击越容易,对应的性质要求就越高,所以强抗碰撞推得出弱抗碰撞。
生日攻击给碰撞定了一个价:2^(n/2)。拿这个数去衡量真实算法,就能看出 MD5 和 SHA-1 为什么被判出局。下一页 C01a-2 讲这些具体的算法。
课件里的坑
- [页面漏项] p.4 只列了单向性和强抗碰撞两条,中间那条第二原像要到 p.6 才出现。三条性质要把 p.4、p.6、p.7 拼起来看,只背 p.4 会漏一条(p.4、p.6、p.7)
- [强弱反直觉] p.7 的「强」「弱」说的是性质强度。强性质防的是更容易得手的攻击,选择题最常在这里设陷阱(p.7)
- [数字来源] p.9 写 SHA-1 的碰撞成本降到 2⁶⁹,课件没交代基准。比较对象是生日攻击给出的 2⁸⁰,不是 2¹⁶⁰(p.9)
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写三条功能要求和三条安全性质,每条写清「题目给什么、攻击者挑什么」;再把完整例题从头做一遍;最后回查两个最容易错的地方:强抗碰撞说的不是攻击强度,2⁸⁰ 是 2¹⁶⁰ 的平方根。
必背
- 哈希函数的三条功能要求:输入长度任意、输出长度固定、正向计算容易
- 三条性质:单向(给 h 找不出 x)、弱抗碰撞即第二原像(给定 x 找不出另一个 y)、强抗碰撞(任意一对 x,y)
- 区分三条性质的判据是攻击者控制几个输入:第二原像只控制一个,碰撞两个都控制
- 强抗碰撞蕴含弱抗碰撞,反之不成立;强弱说的是性质的强度,强性质防的是更容易的那种攻击
- 输出 n bit 时暴力找原像要 2ⁿ 次,找碰撞只要约 2^(n/2) 次(生日攻击)
- 单向性的前提是输入空间足够大,低熵输入可以被正向枚举
课件例题
本讲课件没有例题针对这一页的内容。p.2–7 是定义页,下面的完整例题和变式题按课件的定义自编,用来练三条性质的区分。
完整例题
题面(自编,依据课件 p.6、p.7、p.9):
(1) 攻击者手里有一份已签名的合同和它的哈希,想造一份内容不同、哈希相同的假合同。他在攻击哪条性质?如果他可以自由挑两份文件呢? (2) SHA-1 输出 160 bit,为什么 2005 年的攻击成本是 2⁶⁹,而不是 2¹⁶⁰?
约定:「攻击哪条性质」答性质的中英文名,并说出判据。
解法:
- 先圈题目给定的东西:合同是已经签好的,定死了。
- 攻击者只控制假合同这一个输入,要让它和给定合同的哈希相同,所以是第二原像攻击,对应弱抗碰撞(second-preimage resistance)。
- 两份文件都由他挑时,他只要凑出任意一对哈希相同的文件,变成碰撞攻击,对应强抗碰撞。
- 碰撞攻击更容易得手,因为他能控制两个输入。
- 第 (2) 问:2¹⁶⁰ 是暴力找原像的次数。
- 找碰撞有生日攻击,只要约 2^(160/2) = 2⁸⁰ 次,这是抗碰撞的理论上限。
- 2005 年 Wang 等人用差分攻击,把碰撞成本压到约 2⁶⁹,低于 2⁸⁰,所以算攻破了 SHA-1 的抗碰撞。
要点:先数攻击者控制几个输入,再谈难度。比较碰撞成本时,基准是 2^(n/2)。
答题格式:第一句写性质名,第二句写「攻击者控制 1 个 / 2 个输入」,第三句写对应的难度比较。
变式题(先自己做)
(1) 一个下载站公布了安装包的 SHA-256。攻击者想做一个带病毒的安装包,让它的 SHA-256 等于公布的那个值。他在攻击哪条性质? (2) 一个哈希输出 200 bit。按生日攻击,找碰撞大约要多少次?找原像呢? (3) 判断对错:「一个函数满足第二原像抗性,就一定满足强抗碰撞。」
提示
(1) 公布的是哈希值,还是一个具体文件?攻击者需要和谁的哈希相同?(2) 碰撞看 n/2,原像看 n。(3) 回想「强 ⇒ 弱」的方向。
判分点与答案(非官方评分标准)
判分点:① 第 (1) 问指出原始安装包是给定的;② 写出 2^(n/2) 和 2ⁿ 两个式子;③ 第 (3) 问说清推出方向。
(1) 原始安装包是给定的,它的哈希也公开了,攻击者只控制假安装包一个输入,要撞上给定文件的哈希,所以是第二原像攻击。只拿哈希值、不知道原文件时,就退化成单向性的问题;这里原文件公开下载,所以按第二原像答。
(2) 找碰撞约 2^(200/2) = 2¹⁰⁰ 次,找原像约 2²⁰⁰ 次。
(3) 错。方向反了:强抗碰撞 ⇒ 弱抗碰撞。满足弱性质的函数不一定满足强性质,MD5 和 SHA-1 的碰撞被找到了,第二原像至今没有实用攻击。
闪卡自测
1. 哈希函数的三条功能要求是什么?
接受任意长度的输入,输出固定长度,正向计算要容易(p.3)。
2. 第二原像攻击和碰撞攻击,哪个更难?为什么?
第二原像更难。判据是攻击者控制几个输入:第二原像里攻击者只控制一个,另一个是给定的;碰撞攻击里两个都由他自由挑(p.6、p.7)。
3. 为什么说「强抗碰撞蕴含弱抗碰撞」,反过来不成立?
能防住「自由挑两个」的函数,自然也防住「指定一个再找另一个」这种更受限的情形。反向不成立,防住受限情形不代表能防住更宽松的情形(p.7)。
4. 输出 n bit 时,找原像和找碰撞各要多少次?
找原像约 2ⁿ 次,找碰撞约 2^(n/2) 次,后者叫生日攻击(p.7 补充)。
5. SHA-1 的 2⁶⁹ 是跟什么比的?
跟生日攻击的上限 2⁸⁰ 比。SHA-1 输出 160 bit,2^(160/2) = 2⁸⁰,压到 2⁶⁹ 就算攻破了抗碰撞(p.9)。
6. 单向性什么时候形同虚设?
输入空间很小的时候。攻击者不用倒推,把所有可能各算一遍对照就行,所以有时要给原像加随机字节(p.5)。
下一讲
C01a-2 常见哈希函数与慢哈希:MD5、SHA-1 怎么被攻破,比特币和以太坊各选了什么哈希,以及为什么有人故意要一个慢的哈希。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。