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. 被攻破的老算法: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 的时间线,看出两者被攻破的都是抗碰撞性,单向性至今没有实用的攻破。
-
1991 年,MD5 设计出来,输出 128 bit。
-
1995 年,SHA-1 成为美国标准,输出 160 bit,结构和 MD5 相似。
-
2004 年,王小云等人很快就能找到大量 MD5 碰撞。
-
2005 年,王小云等人把 SHA-1 的碰撞成本压到约 2⁶⁹,低于生日攻击的 2⁸⁰。
-
2017 年,SHAttered 真的造出了一对 SHA-1 碰撞。
-
两条线上所有青绿点都是碰撞攻击。单向性都没有实用的攻破。
怎么判断
说「某算法被攻破」时,要补一句:破的是哪条性质。
| 算法 | 输出 | 碰撞 | 单向性 | 课件结论 |
|---|---|---|---|---|
| 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:
-
拿到公钥 x。
-
先算 SHA-256,得到 256 bit。
-
再把这 256 bit 交给 RIPEMD-160,得到 160 bit。
-
这 160 bit 是比特币地址的一部分。
再看以太坊:
-
输入 rock,用原版 Keccak-256 算,得到 0x10977e4d 开头的值。课件后面石头剪刀布那道题里的值就是这样算出来的。
-
同一个 rock,用 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 加密算法。它自带盐,还能调迭代次数,硬件变快了就把次数调高。
直觉
合法用户登录只算一次,多等几十毫秒感觉不到。
攻击者要试几百万、几亿次。每次都慢一点,乘上次数就是天文数字。慢哈希把同一份慢,分给了算得少的一方和算得多的一方,后者吃亏大得多。
一步一步看
目标:比较同一块 GPU 上 SHA-256 和 bcrypt 的速度,看出慢六个数量级拖住了攻击者,合法用户却几乎无感。
-
同一块 GPU,每秒能算约 10¹⁰ 次 SHA-256。
-
换成 bcrypt,每秒只能跑约 10⁴ 次。
-
两者差 6 个数量级。
-
SHA-256 跑 1 秒的量,bcrypt 要跑 10⁶ 秒,约 11.6 天。
-
合法用户这边,一次登录多花的时间只有几十毫秒。
怎么判断
看到「哈希应该快」和「哈希应该慢」同时出现,先分场景:
| 场景 | 要快还是要慢 | 原因 |
|---|---|---|
| 区块链:区块哈希、挖矿、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。
必背
- MD5 和 SHA-1 被攻破的是碰撞性质,不是单向性;课件建议迁移到 SHA-256 / SHA-512
- Bitcoin = SHA2-256 + RIPEMD-160,Ethereum = Keccak
- Keccak 与标准 SHA3 填充规则不同,同一输入结果不同;以太坊和 Solidity 的 keccak256() 用的是原版 Keccak
- Hash160 = RIPEMD160(SHA256(x)),输出 160 bit,用于比特币地址
- BCRYPT 故意设计得慢是为了拖垮密码爆破:对合法用户多几十毫秒无感,对攻击者是几个数量级的成本
- 哈希要快(区块链)和要慢(密码存储)是两个场景,不矛盾
课件例题
例 1(课件 p.11–12):为什么有人想要一个故意很慢的哈希函数
题面:有些哈希函数被故意设计得很慢,例如 BCRYPT。区块链里的哈希越快越好,为什么还会有人想要一个慢的?
提示
想想谁会大量地算哈希:是登录的用户,还是偷到数据库的攻击者?
解答
- 慢哈希用在密码存储上。攻击者偷到数据库后,要把字典里的词逐个哈希再比对,每算一次都要花时间。
- 哈希越慢,攻击者跑完一本字典的时间越长,暴力破解就被拖垮。
- 合法用户只在登录时算一次,多花几十毫秒察觉不到。
- 所以慢本身是一种防御,它把攻防双方的成本拉开。区块链要快、密码存储要慢,是两个场景,不矛盾。
完整例题
题面(自编,依据课件 p.8–12):一个团队在设计一个系统,有三处要用哈希:(a) 给区块算哈希并挖矿;(b) 把用户公钥变成比特币风格的地址;(c) 存用户登录密码。另外有人提议用 MD5 来做 (a)。请为三处各选一种哈希,并评价 MD5 的提议。
约定:每处写出算法名,并用一句话说明理由。
解法:
- (a) 区块哈希和挖矿要快,选 SHA-256。比特币就是这样用的,挖矿实际是双重 SHA-256。
- (b) 公钥变地址,选 Hash160 = RIPEMD160(SHA256(x))。
- 先算 SHA-256 得到 256 bit,再算 RIPEMD-160 压到 160 bit,地址够短。
- (c) 存密码要慢,选 bcrypt。它每秒只能算约 10⁴ 次,同一块 GPU 跑 SHA-256 约 10¹⁰ 次,差 6 个数量级。
- MD5 的提议不行。MD5 的碰撞早在 2004 年就被找到了。
- 区块哈希要防的正是有人造出两份哈希相同的内容来替换,碰撞失守就等于这道防线失守。
- 课件的建议是迁移到 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 密码怎么存:哈希与加盐:从明文存储讲起,看攻击者怎么用字典攻击,以及加盐为什么能把批量攻击打回逐个攻击。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。