← COMP5565 全部讲次
C01a-2 · 第 2 周

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

MD5 和 SHA-1 被攻破的是哪条性质,比特币的 Hash160 和以太坊的 Keccak 怎么回事,为什么密码要用故意很慢的 bcrypt。

一句话版

哈希函数有很多种。老的 MD5 和 SHA-1 已经被找到碰撞,不能再用;比特币用 SHA-256 加 RIPEMD-160,以太坊用 Keccak。存密码时反过来要挑一个故意很慢的哈希。

上一页 C01a 讲了哈希的三条性质,这一页把它们套到具体的算法上。

先认识这几个词

词 全称 / 读法 一句人话
MD5 Message Digest 5 输出 128 bit 的老哈希,已经被攻破
SHA-1 / SHA-256 Secure Hash Algorithm 美国标准哈希家族,数字常指输出位数
RIPEMD-160 读「瑞普 MD 160」 输出 160 bit 的哈希,比特币用它压短地址
Keccak 读「凯查克」 SHA-3 竞赛的获胜算法,以太坊用的原版
填充规则 padding 把输入补齐到固定块长的规矩,规矩一变结果全变
bcrypt 读「B crypt」 专门存密码用的慢哈希

一个类比:锁匠行里的锁

锁有很多牌子。有的老牌子被人摸出了开法,行里就不再推荐;新牌子还没人打开过,大家照用。

被摸出开法,说的是某一种开法。MD5 和 SHA-1 被攻破,被攻破的是「造两份指纹相同的材料」这一条,倒推原文那条还守得住。

存密码的柜子另有讲究:锁要拧得特别慢。主人每天开一次,多拧几秒无所谓;小偷要试几百万把钥匙,每把都慢几秒,就试不完了。

类比在哪里失效:

  1. 真锁被撬开一把,别的同款锁也就危险了。哈希被找到碰撞,只说明碰撞这一条失守,单向性要另外看。
  2. 真锁慢是因为机械结构。哈希慢是算法故意多转很多圈,可以调。

从零讲起

1. 被攻破的老算法:MD5 和 SHA-1

它解决什么问题

哈希算法会老化。算力在涨,攻击方法也在进步,当年安全的算法后来可能被找到碰撞。

你得知道哪些已经不能再用,以及「被攻破」具体指哪条性质被攻破。

从哪来(补充)

MD5 由 Ronald Rivest 在 1991 年设计,1992 年写进 RFC 1321,输出 128 bit。2004 年 8 月,王小云、冯登国、来学嘉、于红波公布了 MD5 的碰撞。

SHA-1 由美国国家安全局设计,1995 年作为 FIPS PUB 180-1 发布,输出 160 bit。2017 年 2 月 23 日,CWI 和 Google 公布了 SHAttered,第一次实际造出了一对 SHA-1 碰撞文件。

出处:Wikipedia: MD5,Wikipedia: SHA-1

直觉

一个算法在三条性质上各有一道防线。攻击者攻下的是最容易的那道:碰撞。

上一页说过,碰撞攻击里攻击者两个输入都能挑,本来就最容易。MD5 和 SHA-1 都倒在这里。

一步一步看

目标:顺着 MD5 和 SHA-1 的时间线,看出两者被攻破的都是抗碰撞性,单向性至今没有实用的攻破。

  1. 1991 年,MD5 设计出来,输出 128 bit。

  2. 1995 年,SHA-1 成为美国标准,输出 160 bit,结构和 MD5 相似。

  3. 2004 年,王小云等人很快就能找到大量 MD5 碰撞。

  4. 2005 年,王小云等人把 SHA-1 的碰撞成本压到约 2⁶⁹,低于生日攻击的 2⁸⁰。

  5. 2017 年,SHAttered 真的造出了一对 SHA-1 碰撞。

    MD5 和 SHA-1 被攻破的时间线:MD5 在 1991 年由 Rivest 设计,2004 年被找到碰撞;SHA-1 在 1995 年作为 FIPS 180-1 发布,2005 年碰撞成本降到约 2 的 69 次方,2017 年 SHAttered 实际造出碰撞;青绿圆点都是碰撞攻击

  6. 两条线上所有青绿点都是碰撞攻击。单向性都没有实用的攻破。

怎么判断

说「某算法被攻破」时,要补一句:破的是哪条性质。

算法 输出 碰撞 单向性 课件结论
MD5 128 bit 已破 没有实用攻击 不再用
SHA-1 160 bit 已破 没有实用攻击 不再用
SHA-256 / SHA-512 256 / 512 bit 安全 安全 迁移到这里

判断题看到「MD5 被攻破,所以能从 MD5 值反推出原文」,答错。碰撞被攻破,不等于能倒推。

常见误解

以为用 MD5 存密码危险,是因为它的碰撞被找到了

存密码怕的是被倒推和被字典猜中。MD5 存密码危险,主要因为它太快,攻击者每秒能试极多次。碰撞是另一回事,下一个概念讲慢哈希时会看到。

以为 SHA-2 是和 SHA-1 完全无关的新设计

课件说 SHA-2 系列(256/384/512)基于 SHA-1 的思路,只是输出更长。输出变长,生日攻击的成本就跟着涨。

试一下

SHA-1 输出 160 bit,生日攻击的理论成本是多少?2005 年的攻击比它便宜多少倍?

2^(160/2) = 2⁸⁰。2⁸⁰ ÷ 2⁶⁹ = 2¹¹ = 2048,便宜了约两千倍。

一份旧系统用 MD5 校验下载文件。攻击者能不能拿到 MD5 值后反推出原文件?

不能。MD5 被攻破的是碰撞,单向性没有实用攻击。真正的风险在于攻击者可以事先准备一对碰撞文件,一份正常、一份带毒,两份 MD5 相同。

2. 链上的选型:Hash160 和 Keccak

它解决什么问题

比特币和以太坊都离不开哈希,但选的算法不一样。考试会考对应关系,也会考两个细节:比特币为什么套两层,以太坊的「SHA3」为什么不是 SHA3。

从哪来(补充)

RIPEMD-160 发表于 1996 年,作者是 KU Leuven 的 Dobbertin、Bosselaers、Preneel,比特币用了它。

Keccak 由 Bertoni、Daemen、Peeters、Van Assche 设计,2012 年被 NIST 选为 SHA-3。2015 年 8 月 5 日 FIPS 202 批准时改了填充规则,以太坊用的是改之前的版本。

出处:Wikipedia: RIPEMD,Wikipedia: SHA-3

直觉

Hash160 像寄信要过两道分拣:先用 SHA-256 把公钥压成一段,再用 RIPEMD-160 压得更短。

Keccak 和 SHA3 像同一份菜谱的两个版本。主料一样,只改了收尾的一步,端出来的菜味道就全变了。

一步一步看

目标:分别走一遍比特币 Hash160 的两层哈希和以太坊的 Keccak,看出以太坊的「SHA3」和 NIST 版算出的值不一样。

先看比特币的 Hash160:

  1. 拿到公钥 x。

  2. 先算 SHA-256,得到 256 bit。

  3. 再把这 256 bit 交给 RIPEMD-160,得到 160 bit。

  4. 这 160 bit 是比特币地址的一部分。

    比特币的 Hash160 两层哈希:公钥先过 SHA-256 得到 256 bit,再过 RIPEMD-160 得到 160 bit,青绿标出的 160 bit 是比特币地址的一部分,下方写着公式 Hash160 = RIPEMD160(SHA256(x))

再看以太坊:

  1. 输入 rock,用原版 Keccak-256 算,得到 0x10977e4d 开头的值。课件后面石头剪刀布那道题里的值就是这样算出来的。

  2. 同一个 rock,用 NIST 标准版 SHA3-256 算,得到另一串完全不同的值。

    输入 rock 分两路:经过原版 Keccak-256 得到 0x10977e4d 开头的值,这是以太坊在用的;经过 NIST 改过填充规则的 SHA3-256 得到另一串完全不同的值;中间青绿说明差在填充规则

怎么算

Hash160 的式子是:

Hash160(x) = RIPEMD160(SHA256(x))

意思是:先对 x 做 SHA-256,再对结果做 RIPEMD-160,最后输出 160 bit。括号从里往外读,里面的先算。

补充:套两层的理由课件没说,中本聪也没公开解释过。能查到的说法有两条:Hash160 的用途是把公钥压短,再拿去做地址(learnmeabitcoin);比特币核心开发者 Pieter Wuille 推测,套两层是出于对某些攻击的顾虑,这种顾虑多半是多余的(bitcoin.stackexchange)。

对应关系记一张表:

链 用的哈希 用在哪
比特币 SHA2-256 区块哈希、交易 ID、挖矿
比特币 RIPEMD160(SHA256(x)) 公钥变地址
以太坊 Keccak-256 Solidity 的 keccak256() 等

常见误解

以为 Keccak-256 就是 SHA3-256

Keccak 是 SHA-3 竞赛的获胜者,NIST 标准化时改了填充规则。同一个输入,两者给出完全不同的结果。以太坊在 SHA3 定稿前上线,一直用原版 Keccak。

把 Hash160 的两层顺序写反

先 SHA-256,后 RIPEMD-160。写成 SHA256(RIPEMD160(x)) 输出会是 256 bit,和「Hash160」这个名字对不上。用输出长度倒推顺序最不容易错。

试一下

Hash160 的输出写成十六进制是几个字符?

160 ÷ 4 = 40,是 40 个十六进制字符。

一个同学在 Python 里用 hashlib.sha3_256 算 rock,得到的值和课件的 0x10977e4d 对不上。为什么?

hashlib.sha3_256 是 NIST 标准版 SHA3-256。课件那个值是用以太坊的 Keccak-256 算的,两者填充规则不同,结果对不上是正常的。

3. 故意很慢的哈希:bcrypt

它解决什么问题

哈希的第三条功能要求是「算得快」。可存密码时,快反而帮了攻击者:他偷到数据库后,要把字典里的词一个个算哈希去比,算得越快,猜得越快。

所以存密码要用一种故意很慢的哈希,课件举的例子是 BCRYPT。

从哪来(补充)

bcrypt 由 Niels Provos 和 David Mazières 设计,1999 年在 USENIX 发表,基于 Blowfish 加密算法。它自带盐,还能调迭代次数,硬件变快了就把次数调高。

出处:Wikipedia: bcrypt

直觉

合法用户登录只算一次,多等几十毫秒感觉不到。

攻击者要试几百万、几亿次。每次都慢一点,乘上次数就是天文数字。慢哈希把同一份慢,分给了算得少的一方和算得多的一方,后者吃亏大得多。

一步一步看

目标:比较同一块 GPU 上 SHA-256 和 bcrypt 的速度,看出慢六个数量级拖住了攻击者,合法用户却几乎无感。

  1. 同一块 GPU,每秒能算约 10¹⁰ 次 SHA-256。

  2. 换成 bcrypt,每秒只能跑约 10⁴ 次。

  3. 两者差 6 个数量级。

    两根横条按 10 的指数画出同一块 GPU 每秒能算的次数:SHA-256 约 10 的 10 次方次,bcrypt 约 10 的 4 次方次,用青绿标出;底下说明差 6 个数量级

  4. SHA-256 跑 1 秒的量,bcrypt 要跑 10⁶ 秒,约 11.6 天。

  5. 合法用户这边,一次登录多花的时间只有几十毫秒。

怎么判断

看到「哈希应该快」和「哈希应该慢」同时出现,先分场景:

场景 要快还是要慢 原因
区块链:区块哈希、挖矿、Merkle 树 要快 全网每秒要算海量次
密码存储 要慢 每个用户只在登录时算一次,慢只拖累攻击者

意思是:慢本身是一种防御,它把攻防双方的成本拉开。区块链要快、密码要慢,两者不矛盾。

课件讲存密码的那几页直接用单轮 SHA-256,那是在讲原理。真要存密码,用 bcrypt 这类慢哈希。

常见误解

以为慢哈希会让网站卡顿

一次登录只算一次,几十毫秒用户察觉不到。真正受影响的是要算几亿次的攻击者。

以为用了慢哈希,弱密码就安全了

慢哈希只把每次猜测变贵。abandon、qwerty 这种字典前排的词,攻击者照样很快猜到。慢哈希防的是大规模暴力搜索。

试一下

一本字典 10⁸ 个词。用 SHA-256 和 bcrypt 各要跑多久?按上面两个速度算。

SHA-256:10⁸ ÷ 10¹⁰ = 0.01 秒。bcrypt:10⁸ ÷ 10⁴ = 10⁴ 秒,约 2.8 小时。这只是跑一个用户;下一页会讲,加盐之后每个用户都要单独跑一遍。

挖矿要不要用慢哈希?

不要。挖矿是全网不停地算哈希找符合条件的值,验证别人的块也要算,哈希必须快。慢哈希只适合「合法方算得少、攻击方算得多」的场景。

把它们串起来

上一页给了三条性质,这一页拿真实算法对号入座。MD5 和 SHA-1 都倒在碰撞这一条,所以要换到 SHA-256 这类输出更长的算法。

链上选型各有来历。比特币用 SHA-256 做主力,再套一层 RIPEMD-160 把公钥压成 160 bit 的地址。以太坊用的是原版 Keccak,它和后来的标准 SHA3 填充不同,结果也不同。

最后一个概念把「要快」翻了过来。存密码时故意选慢哈希,让攻击者每次猜测都更贵。密码到底怎么存、慢哈希之外还要加什么,下一页 C01a-3 一步步讲。

课件里的坑

  • [上标丢失] p.9 文字层里的「269」是上标丢了,实际是 2⁶⁹(p.9)
  • [同名不同物] p.8 把 SHA3 和 Keccak 分成两行列出,以太坊标在 Keccak 那行。它们对同一输入结果不同,答题别写成「以太坊用 SHA3」(p.8)
  • [示意与工程] p.18–20 的图用单轮 SHA-256 存密码,只是在演示原理;p.11–12 才给出工程上该用慢哈希(p.11、p.12、p.18–20)

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先默写算法和链的对应表,再写出 Hash160 的式子和输出长度;然后把课件例题和完整例题各做一遍;最后回查两个最容易错的地方:MD5 破的是碰撞,Keccak 不等于 SHA3。

必背

  1. MD5 和 SHA-1 被攻破的是碰撞性质,不是单向性;课件建议迁移到 SHA-256 / SHA-512
  2. Bitcoin = SHA2-256 + RIPEMD-160,Ethereum = Keccak
  3. Keccak 与标准 SHA3 填充规则不同,同一输入结果不同;以太坊和 Solidity 的 keccak256() 用的是原版 Keccak
  4. Hash160 = RIPEMD160(SHA256(x)),输出 160 bit,用于比特币地址
  5. BCRYPT 故意设计得慢是为了拖垮密码爆破:对合法用户多几十毫秒无感,对攻击者是几个数量级的成本
  6. 哈希要快(区块链)和要慢(密码存储)是两个场景,不矛盾

课件例题

例 1(课件 p.11–12):为什么有人想要一个故意很慢的哈希函数

题面:有些哈希函数被故意设计得很慢,例如 BCRYPT。区块链里的哈希越快越好,为什么还会有人想要一个慢的?

提示

想想谁会大量地算哈希:是登录的用户,还是偷到数据库的攻击者?

解答
  1. 慢哈希用在密码存储上。攻击者偷到数据库后,要把字典里的词逐个哈希再比对,每算一次都要花时间。
  2. 哈希越慢,攻击者跑完一本字典的时间越长,暴力破解就被拖垮。
  3. 合法用户只在登录时算一次,多花几十毫秒察觉不到。
  4. 所以慢本身是一种防御,它把攻防双方的成本拉开。区块链要快、密码存储要慢,是两个场景,不矛盾。

完整例题

题面(自编,依据课件 p.8–12):一个团队在设计一个系统,有三处要用哈希:(a) 给区块算哈希并挖矿;(b) 把用户公钥变成比特币风格的地址;(c) 存用户登录密码。另外有人提议用 MD5 来做 (a)。请为三处各选一种哈希,并评价 MD5 的提议。

约定:每处写出算法名,并用一句话说明理由。

解法:

  1. (a) 区块哈希和挖矿要快,选 SHA-256。比特币就是这样用的,挖矿实际是双重 SHA-256。
  2. (b) 公钥变地址,选 Hash160 = RIPEMD160(SHA256(x))。
  3. 先算 SHA-256 得到 256 bit,再算 RIPEMD-160 压到 160 bit,地址够短。
  4. (c) 存密码要慢,选 bcrypt。它每秒只能算约 10⁴ 次,同一块 GPU 跑 SHA-256 约 10¹⁰ 次,差 6 个数量级。
  5. MD5 的提议不行。MD5 的碰撞早在 2004 年就被找到了。
  6. 区块哈希要防的正是有人造出两份哈希相同的内容来替换,碰撞失守就等于这道防线失守。
  7. 课件的建议是迁移到 SHA-256 / SHA-512。

要点:先分场景定快慢,再看算法有没有被攻破,最后核对输出长度。

答题格式:三行写三处选型,每行「算法 + 理由」;最后一段单独评价 MD5,点明它破的是碰撞。

变式题(先自己做)

(1) 一个 Solidity 合约要和链下的 Python 程序算同一个哈希。Python 那边该用 hashlib.sha3_256 吗? (2) 判断对错:「SHA-1 被攻破了,所以用 SHA-1 存的密码可以直接被还原。」 (3) Hash160 的输出比 SHA-256 短,会不会更不安全?从生日攻击的角度说说。

提示

(1) Solidity 的 keccak256() 用的是原版还是标准版?(2) 被攻破的是哪条性质?(3) 160 bit 输出时,找碰撞的成本是 2 的多少次方?

判分点与答案(非官方评分标准)

判分点:① 第 (1) 问指出 Keccak 与 SHA3 填充不同;② 第 (2) 问指出被攻破的是碰撞;③ 第 (3) 问写出 2⁸⁰。

(1) 不该。hashlib.sha3_256 是标准 SHA3-256,和 Solidity 的 keccak256() 填充规则不同,结果对不上。要用原版 Keccak-256 的实现。

(2) 错。SHA-1 被攻破的是碰撞,单向性没有实用攻击,不能从哈希还原密码。只是 SHA-1 太快,不适合存密码,字典攻击照样很快。

(3) 160 bit 输出时,生日攻击找碰撞约 2^(160/2) = 2⁸⁰ 次,比 SHA-256 的 2¹²⁸ 低。代价是抗碰撞的余量小一些,好处是地址更短。

闪卡自测

1. MD5 和 SHA-1 被攻破的是哪条性质?

被攻破的是碰撞性质,单向性没破(p.9)。

2. 比特币和以太坊各用什么哈希?

比特币用 SHA2-256 和 RIPEMD-160,以太坊用 Keccak(p.8)。

3. Keccak 和 SHA3 是一回事吗?

不是。Keccak 是 SHA-3 竞赛的获胜算法,NIST 标准化时改了填充规则,所以标准 SHA3-256 和以太坊用的 Keccak-256 对同一输入给出完全不同的结果(p.8)。

4. Hash160 怎么算?输出多长?

Hash160 = RIPEMD160(SHA256(x)),先 SHA-256 再 RIPEMD-160,输出 160 bit,用于比特币地址(p.10)。

5. 为什么有人要一个「故意很慢」的哈希函数?

密码哈希场景下慢能拖垮暴力破解。合法用户登录时多花几十毫秒无感,攻击者跑整本字典的成本却被拉开几个数量级(p.11、p.12)。

6. 课件对 MD5 和 SHA-1 的建议是什么?

迁移到 SHA-256 / SHA-512(p.9)。

下一讲

C01a-3 密码怎么存:哈希与加盐:从明文存储讲起,看攻击者怎么用字典攻击,以及加盐为什么能把批量攻击打回逐个攻击。

下一讲 →
C01a-3 C01a-3 密码怎么存:哈希、字典攻击与加盐

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