C01a-4 哈希的边界:能核对完整性,不保密,也证明不了来源
BitTorrent 怎么靠哈希核对分片,石头剪刀布为什么一公布哈希就露馅、加随机 nonce 怎么修,以及数据和哈希被一起换掉时为什么核对照样通过。
一句话版
哈希能告诉你数据有没有被改,这就是它在 BitTorrent 里的用法。它有两件事做不到:藏不住内容,也说不清是谁发的。
前三页讲了哈希的性质、算法和存密码,见 C01a 到 C01a-3。这一页是这一讲的转折点:哈希做不到的那部分,正是后面数字签名要补的。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 完整性 | integrity | 数据没被改过 |
| 机密性 | confidentiality | 别人看不到内容 |
| 来源真实性 | authenticity | 确实是他发的 |
| 不可否认性 | non-repudiation | 他事后赖不掉 |
| 承诺-揭示 | commit-reveal | 先公布一个锁定值,之后再亮出原文 |
| nonce | 读「诺斯」 | 只用一次的随机数 |
| MAC | Message Authentication Code | 用双方共享密钥算的校验码 |
一个类比:封条
快递箱上贴一张印着编号的封条。收件时编号对得上、封条没破,说明箱子路上没被拆过。
可封条是透明的。箱子里只可能是三样东西之一时,别人隔着封条掂一掂就猜出来了。
封条谁都能买。半路有人把箱子连同封条一起换掉,换成他自己的箱子和他自己的封条,你核对编号照样对得上。
类比在哪里失效:
- 真封条靠「没破」证明没拆过。哈希靠重算比对,数据改一个字节,算出来的值就全变。
- 真封条的编号和箱子里的东西无关。哈希值由内容算出来,内容可猜时,哈希值等于把内容写在外面。
从零讲起
1. 哈希能做到的:核对完整性
它解决什么问题
从陌生节点下载一个大文件,怎么知道收到的每一块都没坏、也确实属于这个文件?
哈希能回答这个问题。数据改一点,哈希就全变,拿手里的数据重算一遍,和登记的哈希比就行。
从哪来(补充)
BitTorrent 由 Bram Cohen 在 2001 年设计,同年 7 月发布第一版。文件切成固定大小的分片,每片的哈希写在 torrent 文件里,v1 规范用的是 SHA-1。
直觉
找文件有两种思路:按「在哪台机器上」找,或者按「内容的哈希是什么」找。
后一种叫内容寻址(content addressed)。只要哈希对得上,从谁那里拿到的都一样。
一步一步看
目标:走一遍分片下载的核对,看自己重算的哈希和登记值一比,就能判断陌生节点给的片能不能用。
-
发布者把大文件切成很多片,片 1、片 2、片 3、片 4……
-
每片各算一个哈希 h1、h2、h3、h4,登记在种子文件里。
-
你从一个陌生节点收到片 3。
-
你自己算一遍片 3 的哈希,得到 h。
-
h 和登记的 h3 一样,说明这片没坏,确实属于这个文件。
-
不一样就丢掉,换个节点再要。
怎么判断
完整性检查成立,要先满足一个前提:你手里那份参照哈希是可信的。
意思是:比对的两边,一边是你自己算的,另一边必须来自可靠的地方。BitTorrent 里那份参照就是种子文件里登记的哈希。
常见误解
以为哈希对得上,就说明分片是可信的人发来的
哈希只回答「这片对不对」。是谁发来的,它回答不了。BitTorrent 不在乎这一点,因为它只关心内容对不对。
以为内容寻址只在 BitTorrent 里用
这是分布式系统里很基础的设计模式,后面在 IPFS 和以太坊的状态存储里还会遇到。
试一下
你收到片 3,算出的哈希和登记的 h3 差了一位。可能是什么原因?你该怎么做?
片 3 在传输中坏了,或者对方故意给了假数据。不管哪种,都丢掉这片,换个节点再要。哈希只要差一点,就说明内容不同。
攻击者能不能造一份假的片 3,让它的哈希刚好等于 h3?
这要找第二原像。h3 和真片 3 是定死的,攻击者只能自己造假数据去凑,对安全的哈希做不到。
2. 哈希不保密:石头剪刀布
它解决什么问题
网上玩石头剪刀布,后出招的人能看到先出招的,就会作弊。
一个想法是承诺-揭示:双方先公布自己出招的哈希,等都公布了,再揭晓原文。课件问:这个协议有没有问题?
从哪来(补充)
这种「先锁定、后揭晓」的做法叫承诺方案(commitment scheme)。它要满足两条:揭晓前对方读不出值,叫隐藏;揭晓时自己改不了值,叫绑定。
概念最早来自 Manuel Blum 1981 年的论文《Coin Flipping by Telephone》,1988 年由 Brassard、Chaum、Crépeau 形式化。
出处:Wikipedia: Commitment scheme
直觉
出招只有三种。对手根本不用反推哈希,正着把三种都算一遍,看哪个对得上就行。
课件的原话是:对手不需要解开哈希,就能知道你出了什么。
一步一步看
目标:看 Bob 把三种出招逐个算哈希就认出 Alice 的承诺,再看拼上随机 nonce 后这招为什么失效。
-
Alice 出剪刀,公布 H(scissors),值是 0x389a2d4e 开头的那串。
-
Bob 拿到这串,自己用 Keccak-256 算 H(rock),得到 0x10977e4d 开头,对不上。
-
再算 H(paper),得到 0xea923ca2 开头,对不上。
-
再算 H(scissors),得到 0x389a2d4e 开头,一样。
-
Bob 知道 Alice 出了剪刀,就出石头。
-
修法:承诺时拼一个随机的 nonce,公布 H(choice ‖ nonce)。nonce 是随机 32 字节。
-
揭晓时,Alice 把 choice 和 nonce 一起公布。Bob 自己重算,和她之前公布的承诺比对。
怎么算
修好后的承诺:
commit = H(choice ‖ nonce)
意思是:把出招和一段随机数拼起来再哈希。‖ 读「拼接」。
原像空间从 3 变成:
3 × 2²⁵⁶
Bob 要正着枚举,得把每种出招配上每一种 nonce 都试一遍,试不完。
这一招和上一页的盐是同一个手法。盐防字典,nonce 防枚举,都是往原像里加随机字节,不让别人按上下文去猜。
常见误解
以为 nonce 和盐一样,可以公开放着
揭晓前 nonce 必须保密。Bob 提前拿到 nonce,又可以把三种出招配上它算一遍,枚举回来了。密码的盐公开,是因为它的作用只是让每个用户的哈希不同。两者的保密要求不一样。
以为换一个更强的哈希就能修好
换成什么哈希都一样,三种出招就是三种。问题出在原像空间太小,和用哪个哈希无关。
试一下
拼了 nonce 以后,Alice 还能在揭晓时改口吗?
不能。她要改口,就得找到另一组 (choice’, nonce’),让哈希等于她之前公布的值,这是找第二原像。哈希的抗碰撞和抗第二原像让她改不了,这就是承诺的绑定。
一个投票系统公布每个人选票的哈希 H(候选人名字),候选人只有 5 位。安全吗?
不安全。候选人只有 5 种,把 5 个名字各算一遍哈希就能查出每个人投了谁。要拼上每人各自的随机 nonce。
3. 哈希证明不了来源
它解决什么问题
上一个概念讲了完整性检查的前提:参照哈希必须可信。如果数据和哈希走同一条路过来,攻击者半路一起换掉,会怎样?
直觉
任何人都能算哈希。攻击者换掉文件后,顺手把假文件的哈希也算好附上。
你核对的是「这两样东西互相匹配」。它们确实互相匹配,只是两样都是假的。
一步一步看
目标:看攻击者把文件和哈希一起换掉后收件人的核对照样通过,明白哈希证明不了数据来自谁。
-
发送者发出文件 D,附上 H(D)。
-
攻击者半路截下,换成假文件 D’。
-
攻击者自己算 H(D’),替换掉附带的 H(D)。
-
收件人收到 D’ 和 H(D’)。他自己算 H(D’),和附带的比。
-
一样,核对通过。收件人不知道文件已经被换过。
怎么判断
遇到「哈希 / MAC / 签名能提供哪些保证」的题,对着这张表判:
| 保证 | 哈希 | MAC | 数字签名 |
|---|---|---|---|
| 完整性(数据没被改) | 要有可信参照摘要 | 有 | 有,要有可信公钥 |
| 来源真实性(确实是他发的) | 没有 | 有 | 有 |
| 不可否认性(他赖不掉) | 没有 | 没有 | 有 |
| 机密性(别人看不到) | 没有 | 没有 | 没有 |
MAC 一栏是课件之外的补充。MAC 用一把双方共享的对称密钥,所以能证明「是有钥匙的人发的」。可钥匙两边都有,谁都可能是发的那个,事后说不清,所以没有不可否认性。
区块链要的是「这笔交易确实是这个地址签的,他赖不掉」,所以必须用签名。
常见误解
以为下载页旁边贴了哈希,就能保证文件没被篡改
只有哈希来源比文件更可信时才成立。攻击者能改下载页,就能把文件和哈希一起换掉。
以为 MAC 和签名作用一样,只是换了个算法
MAC 的钥匙两边共享,签名的私钥只在签名者一人手里。差别落在不可否认性上:签名能证明是他签的,MAC 只能证明是两人中的一个。
试一下
Alice 用 MAC 给 Bob 发了一条「转给 Bob 10 元」的消息。之后 Alice 说「这条是 Bob 自己造的」。Bob 能拿 MAC 向第三方证明吗?
不能。Bob 也有那把共享密钥,他自己就能算出同样的 MAC。第三方分不清是谁算的。要让 Alice 赖不掉,得用她的私钥签名。
怎么改,才能让上面换文件的攻击失效?
参照哈希要走一条攻击者改不了的路:比如提前通过可信渠道拿到,或者由发送者用私钥签名。签名要用到攻击者没有的私钥,他伪造不出来。
把它们串起来
哈希能做的是完整性检查。BitTorrent 每个分片带哈希,收到就重算比对,前提是参照哈希可信。
它做不到两件事。第一件是保密:原像空间小时,对手正着枚举就能还原,修法是往原像里拼随机 nonce,和存密码时加盐是同一个手法。第二件是证明来源:谁都能算哈希,数据和哈希可以被一起换掉。
第二个洞要靠数字签名来补。签名之前,先看哈希还能搭成什么数据结构,下一页 C01b 讲哈希链。
课件里的坑
- [算法混用] p.25 的三个哈希值用的是 Keccak-256,前面存密码那几页用的是 SHA-256,课件没有说明换了算法(p.18–21、p.25)
- [修法未给] 课件只问出了问题,没给修法;修法要和 p.5 那句「往原像里加随机字节防猜」以及 p.21–23 的盐串起来看(p.5、p.25)
- [保密要求] nonce 和盐是同一个手法,但揭晓前 nonce 要保密,盐是公开的,答题别混用(p.22、p.25)
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写哈希、MAC、签名对四种保证的那张表;再把石头剪刀布的问题和修法完整说一遍;最后回查两个最容易错的地方:哈希对得上不代表来源可信,nonce 揭晓前要保密。
必背
- 哈希能做的是完整性检查:数据一改哈希就变;BitTorrent 每个分片带哈希,按内容寻址(content addressed)
- 哈希不提供机密性:原像空间小(三种出招、常见密码)时正着枚举就能还原,对手不用反推哈希
- 修法是在原像里拼随机 nonce:commit = H(choice ‖ nonce),原像空间从 3 变成 3 × 2²⁵⁶;揭晓前 nonce 要保密
- 哈希不提供来源真实性:任何人都能算哈希,数据和哈希可以被一起替换,完整性检查要先有可信的参照摘要
- 哈希 / MAC / 签名:MAC 有完整性和来源真实性但没有不可否认性,不可否认性只有签名有
课件例题
例 1(课件 p.24–25):用哈希承诺玩石头剪刀布,有什么问题
见下方完整例题。
完整例题
题面(课件 p.24–25):Alice 和 Bob 在网上玩石头剪刀布。为了防止后出招的人偷看,双方先各自公布自己出招的哈希,然后再揭晓原文。课件给出三个值:
| 明文 | 哈希值 |
|---|---|
| rock | 0x10977e4d68108d418408bc9310b60fc6d0a750c63ccef42cfb0ead23ab73d102 |
| paper | 0xea923ca2cdda6b54f4fb2bf6a063e5a59a6369ca4c4ae2c4ce02a147b3036a21 |
| scissors | 0x389a2d4e358d901bfdf22245f32b4b0a401cc16a4b92155a2ee5da98273dad9a |
(1) 这个协议有什么问题?(2) 只改一处,怎么修好?(3) 这说明哈希缺了哪种保证?
约定:哈希用课件这几个值对应的 Keccak-256。
解法:
- 出招只有三种,原像空间是 3。
- Bob 拿到 Alice 公布的哈希,把 rock、paper、scissors 各算一遍 Keccak-256,对照这张表就知道 Alice 出了什么。
- 他不需要「破解」哈希,单向性在这里形同虚设,因为它的前提是输入空间够大。
- 修法:承诺时拼一个随机 nonce,公布 commit = H(choice ‖ nonce),nonce 取随机 32 字节。
- 原像空间变成 3 × 2²⁵⁶,正着枚举试不完。
- 揭晓时把 choice 和 nonce 一起公布,对方重算比对。揭晓前 nonce 要保密。
- 结论:哈希不提供机密性。它保护的是「数据没变」,低熵输入下的哈希等于明文。
要点:这一招和存密码时的盐同源,都是往原像里加随机字节。
答题格式:先写问题(原像只有三种,正着枚举),再写修法(拼 nonce 的式子),最后一句点明「哈希不提供机密性」。
变式题(先自己做)
(1) 一份竞标方案,各家先公布 H(报价) 再揭晓。报价都是 1 到 100 万之间的整数元。安全吗? (2) 某软件官网同一页面上给出下载链接和 SHA-256 值。攻击者控制了这个页面。用户校验哈希能发现问题吗? (3) 用一句话说明 MAC 为什么做不到不可否认。
提示
(1) 原像空间有多大?攻击者正着算要多久?(2) 参照哈希和文件走的是不是同一条路?(3) 那把钥匙在谁手里?
判分点与答案(非官方评分标准)
判分点:① 第 (1) 问指出原像空间小、可枚举,并给出 nonce 修法;② 第 (2) 问指出数据和哈希可被一起替换;③ 第 (3) 问指出密钥双方共享。
(1) 不安全。原像空间只有约 10⁶ 种,现代电脑一下就能全部算完,对照就能查出每家报价。每家要拼上自己的随机 nonce 再哈希。
(2) 发现不了。攻击者能改页面,就能把文件和哈希一起换掉,用户核对的两样都是假的。参照哈希要来自攻击者改不了的渠道,或者由发布者签名。
(3) MAC 的密钥收发双方都有,任何一方都能算出同样的 MAC,第三方分不清是谁发的。
闪卡自测
1. BitTorrent 怎么用哈希?什么叫 content addressed?
文件切成分片,每片带一个哈希,收到分片后重算比对,就知道这片没坏、确实属于这个文件。按内容的哈希找数据,叫内容寻址(p.27)。
2. 用哈希承诺玩石头剪刀布,问题出在哪?
原像只有三种,对手把三种出招各算一遍哈希对照就知道你出了什么,不需要反推哈希(p.24、p.25)。
3. 怎么修好石头剪刀布的承诺?
公布 H(choice ‖ nonce),nonce 是随机 32 字节,原像空间变成 3 × 2²⁵⁶。揭晓时 choice 和 nonce 一起公布(p.25 补充)。
4. 为什么说哈希不提供来源真实性?
任何人都能算哈希,攻击者可以把数据和哈希一起换掉,核对照样通过。完整性检查要先有可信的参照摘要(p.26)。
5. 哈希、MAC、签名谁有不可否认性?
只有签名有。MAC 的密钥双方共享,谁都可能是发的那个;哈希谁都能算(p.26 补充)。
6. nonce 和盐都是加随机字节,保密要求一样吗?
不一样。nonce 揭晓前要保密,否则对手配上它又能枚举;盐公开存放(p.22、p.25)。
下一讲
C01b 哈希链:改一块,后面全要重算:把哈希装进一串数据块里,看篡改为什么藏不住。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。