← COMP5565 全部讲次
C01a · 第 2 周

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 数量翻一倍

一个类比:档案室的指纹册

档案室给每份进来的材料按一枚指纹,另册登记。材料可以是一张便条,也可以是一整箱卷宗,按出来的指纹大小都一样。

按材料取指纹很快。拿着一枚指纹,却造不出那份材料,这叫单向。

两份不同的材料按出了同一枚指纹,叫碰撞。指定一份材料、去造另一份指纹相同的,比随便造两份指纹相同的难得多。这一页的三条性质就是在说这三件事。

类比在哪里失效:

  1. 真指纹几乎天然唯一。哈希的输出长度固定,输入却无穷多,碰撞一定存在,只是找不到。
  2. 指纹册不保密。材料只有三种可能时,看一眼指纹就知道是哪份,这一点留到 C01a-4 讲。

从零讲起

1. 哈希函数是什么

它解决什么问题

数据可能很大,一部电影几 GB。想核对两份数据是否一样,逐字节比太慢,传过来再比又太费带宽。

要是每份数据都有一个很短、长度固定的代表,比这个代表就够了。哈希函数负责算出这个代表。

从哪来(补充)

「哈希」这个思路最早出现在 IBM 的 Hans Peter Luhn 写于 1953 年 1 月的一份内部备忘录里。当时是为了给数据快速分桶查找。

这个词正式印进文献,又过了十几年。密码学里用的哈希多加了几条安全要求,下一个概念就讲。

出处:Wikipedia: Hash function

直觉

把哈希想成一台绞肉机。什么东西都能放进去,出来的都是一样大小的一团。

同样的东西放进去,出来的永远一样。换一个字节,出来的就面目全非。出来的那一团,没法还原成原来的样子。

一步一步看

目标:拿 SHA-256 逐条对照三条功能要求和确定性,看出哈希值为什么能当任意数据的短代表。

课件给了三条功能要求,这里拿同一个函数 SHA-256 走一遍。

  1. 输入长度任意:6 个字节的 qwerty、5 个字节的 hello、几 GB 的一部电影,都能放进去算。

  2. 输出长度固定:三份输入算出来的都是 64 个十六进制字符,也就是 256 bit。

  3. 正向计算容易:算一次哈希很快,电脑每秒能算很多次。

    长短不一的三份输入 qwerty、hello 和一部几 GB 的电影,经过同一个 SHA-256,各自得到一串 64 个十六进制字符、256 bit 的输出;右边青绿括号标出输出长度永远一样

  4. 再验一下「确定性」:明天再算一次 qwerty,得到的还是 65e84be3 开头的那一串。

怎么判断

拿到一个函数,按三条要求逐条问:

  • 能不能吃下任意长度的输入?
  • 不管输入多长,输出是不是一样长?
  • 正着算是不是很便宜?

三条都满足,它才算一个哈希函数。注意第三条:区块链里的哈希每秒要算海量次,必须快。

后面 C01a-2 会讲一个「故意很慢」的哈希。那是密码存储这个特殊场景,两者不矛盾。

常见误解

以为哈希就是加密

加密有一把钥匙,持钥匙的人能把密文解回明文。哈希没有钥匙,谁都解不回去,也不打算解回去。它的用途是核对,不是藏东西。

以为输出长度固定,所以输入长度也有上限

输入长度没有上限,输出长度固定。正因为这样,不同输入撞上同一个输出是必然存在的,这就是下一个概念要处理的碰撞。

试一下

SHA-256 的输出是 256 bit。写成十六进制要几个字符?

一个十六进制字符表示 4 bit,256 ÷ 4 = 64,所以是 64 个字符。

一个函数把任何输入都映射成它的第一个字节。它满足三条功能要求吗?好用吗?

三条功能要求都满足:吃任意输入、输出固定 1 字节、算得快。可它完全不安全,开头相同的两份数据就会撞在一起。功能要求只保证能用,安全要靠下一个概念的三条性质。

2. 三条安全性质

它解决什么问题

功能要求只说了「能算」。要拿哈希来防篡改、存密码,还得保证攻击者造不出想要的结果。

课件用三条性质把「安全」说清楚,三条的区别是这一讲最常考的点。

直觉

想象攻击者在玩三种游戏,难度依次降低:

  • 单向:给他一枚指纹,让他造一份能按出这枚指纹的材料。
  • 第二原像:给他一份具体的材料,让他造另一份指纹相同的。
  • 强抗碰撞:什么都不给,让他随便造两份指纹相同的材料。

最后一种他能自由挑两份,回旋余地最大,所以最容易得手。

一步一步看

目标:把三条安全性质并排比,看每一条里哪些输入是题目给定的、哪些由攻击者自己挑。

  1. 单向性(one-way):题目给定一个哈希值 h。攻击者要找任何一个 x,让 H(x) = h。他手上只有 h。

  2. 第二原像抗性(weak collision-resistant):题目给定一个 x。攻击者要找另一个 y,让 H(y) = H(x)。x 是定死的,他只能挑 y。

  3. 强抗碰撞(strong collision-resistant):题目什么都不给。攻击者自己挑 x 和 y,只要不同、哈希相等就算赢。

  4. 三格并排看,虚线框是攻击者自己挑的,实线框是题目给定的。从左到右,攻击者能控制的输入越来越多。

    三格并排对比三条哈希性质:单向是给定 h 去找任何一个 x,第二原像是给定 x 去找另一个 y,强抗碰撞是 x 和 y 两个输入都由攻击者自由挑;虚线框表示攻击者自己挑,实线框表示题目给定

  5. 「难以找到」指计算上做不到,要算的次数多到不现实。数学上这样的输入是存在的。

怎么判断

碰到一个攻击场景,先圈出题目给了什么:

题目给定 攻击者挑 对应性质
哈希值 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。

  1. 暴力找原像:最坏要试遍 2¹⁶⁰ 种可能。

  2. 生日攻击找碰撞:试约 2^(160/2) = 2⁸⁰ 次,就有约一半的把握撞出一对。

  3. 2005 年王小云等人用差分攻击,把找碰撞的成本压到约 2⁶⁹。

  4. 2017 年 SHAttered 实际造出了一对碰撞文件,用了约 2⁶³ 次计算。

    四根横条按 2 的指数画出 SHA-1 上几种找法的计算量:暴力找原像 2 的 160 次方;生日攻击找碰撞 2 的 80 次方,用青绿标出;2005 年王小云等约 2 的 69 次方;2017 年 SHAttered 约 2 的 63 次方

  5. 这几根条按指数画。指数砍一半,次数就开平方,差距大得惊人。

怎么算

记两个式子:

  • 找原像:约 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¹⁶⁰ 的平方根。

必背

  1. 哈希函数的三条功能要求:输入长度任意、输出长度固定、正向计算容易
  2. 三条性质:单向(给 h 找不出 x)、弱抗碰撞即第二原像(给定 x 找不出另一个 y)、强抗碰撞(任意一对 x,y)
  3. 区分三条性质的判据是攻击者控制几个输入:第二原像只控制一个,碰撞两个都控制
  4. 强抗碰撞蕴含弱抗碰撞,反之不成立;强弱说的是性质的强度,强性质防的是更容易的那种攻击
  5. 输出 n bit 时暴力找原像要 2ⁿ 次,找碰撞只要约 2^(n/2) 次(生日攻击)
  6. 单向性的前提是输入空间足够大,低熵输入可以被正向枚举

课件例题

本讲课件没有例题针对这一页的内容。p.2–7 是定义页,下面的完整例题和变式题按课件的定义自编,用来练三条性质的区分。

完整例题

题面(自编,依据课件 p.6、p.7、p.9):

(1) 攻击者手里有一份已签名的合同和它的哈希,想造一份内容不同、哈希相同的假合同。他在攻击哪条性质?如果他可以自由挑两份文件呢? (2) SHA-1 输出 160 bit,为什么 2005 年的攻击成本是 2⁶⁹,而不是 2¹⁶⁰?

约定:「攻击哪条性质」答性质的中英文名,并说出判据。

解法:

  1. 先圈题目给定的东西:合同是已经签好的,定死了。
  2. 攻击者只控制假合同这一个输入,要让它和给定合同的哈希相同,所以是第二原像攻击,对应弱抗碰撞(second-preimage resistance)。
  3. 两份文件都由他挑时,他只要凑出任意一对哈希相同的文件,变成碰撞攻击,对应强抗碰撞。
  4. 碰撞攻击更容易得手,因为他能控制两个输入。
  5. 第 (2) 问:2¹⁶⁰ 是暴力找原像的次数。
  6. 找碰撞有生日攻击,只要约 2^(160/2) = 2⁸⁰ 次,这是抗碰撞的理论上限。
  7. 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 怎么被攻破,比特币和以太坊各选了什么哈希,以及为什么有人故意要一个慢的哈希。

下一讲 →
C01a-2 C01a-2 常见哈希函数与慢哈希:哪些还能用,链上选了谁

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。