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

C01a-4 哈希的边界:能核对完整性,不保密,也证明不了来源

BitTorrent 怎么靠哈希核对分片,石头剪刀布为什么一公布哈希就露馅、加随机 nonce 怎么修,以及数据和哈希被一起换掉时为什么核对照样通过。

一句话版

哈希能告诉你数据有没有被改,这就是它在 BitTorrent 里的用法。它有两件事做不到:藏不住内容,也说不清是谁发的。

前三页讲了哈希的性质、算法和存密码,见 C01a 到 C01a-3。这一页是这一讲的转折点:哈希做不到的那部分,正是后面数字签名要补的。

先认识这几个词

词 全称 / 读法 一句人话
完整性 integrity 数据没被改过
机密性 confidentiality 别人看不到内容
来源真实性 authenticity 确实是他发的
不可否认性 non-repudiation 他事后赖不掉
承诺-揭示 commit-reveal 先公布一个锁定值,之后再亮出原文
nonce 读「诺斯」 只用一次的随机数
MAC Message Authentication Code 用双方共享密钥算的校验码

一个类比:封条

快递箱上贴一张印着编号的封条。收件时编号对得上、封条没破,说明箱子路上没被拆过。

可封条是透明的。箱子里只可能是三样东西之一时,别人隔着封条掂一掂就猜出来了。

封条谁都能买。半路有人把箱子连同封条一起换掉,换成他自己的箱子和他自己的封条,你核对编号照样对得上。

类比在哪里失效:

  1. 真封条靠「没破」证明没拆过。哈希靠重算比对,数据改一个字节,算出来的值就全变。
  2. 真封条的编号和箱子里的东西无关。哈希值由内容算出来,内容可猜时,哈希值等于把内容写在外面。

从零讲起

1. 哈希能做到的:核对完整性

它解决什么问题

从陌生节点下载一个大文件,怎么知道收到的每一块都没坏、也确实属于这个文件?

哈希能回答这个问题。数据改一点,哈希就全变,拿手里的数据重算一遍,和登记的哈希比就行。

从哪来(补充)

BitTorrent 由 Bram Cohen 在 2001 年设计,同年 7 月发布第一版。文件切成固定大小的分片,每片的哈希写在 torrent 文件里,v1 规范用的是 SHA-1。

出处:Wikipedia: BitTorrent

直觉

找文件有两种思路:按「在哪台机器上」找,或者按「内容的哈希是什么」找。

后一种叫内容寻址(content addressed)。只要哈希对得上,从谁那里拿到的都一样。

一步一步看

目标:走一遍分片下载的核对,看自己重算的哈希和登记值一比,就能判断陌生节点给的片能不能用。

  1. 发布者把大文件切成很多片,片 1、片 2、片 3、片 4……

  2. 每片各算一个哈希 h1、h2、h3、h4,登记在种子文件里。

  3. 你从一个陌生节点收到片 3。

  4. 你自己算一遍片 3 的哈希,得到 h。

    BitTorrent 的内容寻址:大文件切成片 1 到片 4,每片的哈希 h1 到 h4 登记在种子文件里;从陌生节点收到片 3 后自己算哈希得到 h,和登记的 h3 比,一样就说明没坏、确实属于这个文件,不一样就丢掉换个节点再要;底部提示这只回答这片对不对,是谁发来的哈希回答不了

  5. h 和登记的 h3 一样,说明这片没坏,确实属于这个文件。

  6. 不一样就丢掉,换个节点再要。

怎么判断

完整性检查成立,要先满足一个前提:你手里那份参照哈希是可信的。

意思是:比对的两边,一边是你自己算的,另一边必须来自可靠的地方。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 后这招为什么失效。

  1. Alice 出剪刀,公布 H(scissors),值是 0x389a2d4e 开头的那串。

  2. Bob 拿到这串,自己用 Keccak-256 算 H(rock),得到 0x10977e4d 开头,对不上。

  3. 再算 H(paper),得到 0xea923ca2 开头,对不上。

  4. 再算 H(scissors),得到 0x389a2d4e 开头,一样。

    对手不用反推哈希:Alice 公布的承诺是 0x389a2d4e 开头的值,Bob 自己用 Keccak-256 把 rock、paper、scissors 各算一遍,得到 0x10977e4d、0xea923ca2、0x389a2d4e 开头的值,scissors 那一个对上了;原像只有三种可能,哈希值和明文没区别

  5. Bob 知道 Alice 出了剪刀,就出石头。

  6. 修法:承诺时拼一个随机的 nonce,公布 H(choice ‖ nonce)。nonce 是随机 32 字节。

    拼一个随机 nonce 前后对比:H(choice) 的原像空间只有 3 种;H(choice ‖ nonce) 中 nonce 随机 32 字节,原像空间变成 3 × 2 的 256 次方种,多到枚举不完;揭晓时把 choice 和 nonce 一起公布,对方自己重算核对;揭晓前 nonce 要保密,密码的盐是公开的

  7. 揭晓时,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. 哈希证明不了来源

它解决什么问题

上一个概念讲了完整性检查的前提:参照哈希必须可信。如果数据和哈希走同一条路过来,攻击者半路一起换掉,会怎样?

直觉

任何人都能算哈希。攻击者换掉文件后,顺手把假文件的哈希也算好附上。

你核对的是「这两样东西互相匹配」。它们确实互相匹配,只是两样都是假的。

一步一步看

目标:看攻击者把文件和哈希一起换掉后收件人的核对照样通过,明白哈希证明不了数据来自谁。

  1. 发送者发出文件 D,附上 H(D)。

  2. 攻击者半路截下,换成假文件 D’。

  3. 攻击者自己算 H(D’),替换掉附带的 H(D)。

  4. 收件人收到 D’ 和 H(D’)。他自己算 H(D’),和附带的比。

    数据和哈希被一起换掉,核对照样通过:原本发出的是文件 D 和 H(D),攻击者半路换成假文件 D’ 和 H(D’);收件人自己算 H(D’) 和附带的 H(D’) 比,一样,于是通过;任何人都能算哈希,对得上只说明两样东西互相匹配,要先有可信的参照摘要或签名才谈得上核对来源

  5. 一样,核对通过。收件人不知道文件已经被换过。

怎么判断

遇到「哈希 / 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 揭晓前要保密。

必背

  1. 哈希能做的是完整性检查:数据一改哈希就变;BitTorrent 每个分片带哈希,按内容寻址(content addressed)
  2. 哈希不提供机密性:原像空间小(三种出招、常见密码)时正着枚举就能还原,对手不用反推哈希
  3. 修法是在原像里拼随机 nonce:commit = H(choice ‖ nonce),原像空间从 3 变成 3 × 2²⁵⁶;揭晓前 nonce 要保密
  4. 哈希不提供来源真实性:任何人都能算哈希,数据和哈希可以被一起替换,完整性检查要先有可信的参照摘要
  5. 哈希 / MAC / 签名:MAC 有完整性和来源真实性但没有不可否认性,不可否认性只有签名有

课件例题

例 1(课件 p.24–25):用哈希承诺玩石头剪刀布,有什么问题

见下方完整例题。

完整例题

题面(课件 p.24–25):Alice 和 Bob 在网上玩石头剪刀布。为了防止后出招的人偷看,双方先各自公布自己出招的哈希,然后再揭晓原文。课件给出三个值:

明文 哈希值
rock 0x10977e4d68108d418408bc9310b60fc6d0a750c63ccef42cfb0ead23ab73d102
paper 0xea923ca2cdda6b54f4fb2bf6a063e5a59a6369ca4c4ae2c4ce02a147b3036a21
scissors 0x389a2d4e358d901bfdf22245f32b4b0a401cc16a4b92155a2ee5da98273dad9a

(1) 这个协议有什么问题?(2) 只改一处,怎么修好?(3) 这说明哈希缺了哪种保证?

约定:哈希用课件这几个值对应的 Keccak-256。

解法:

  1. 出招只有三种,原像空间是 3。
  2. Bob 拿到 Alice 公布的哈希,把 rock、paper、scissors 各算一遍 Keccak-256,对照这张表就知道 Alice 出了什么。
  3. 他不需要「破解」哈希,单向性在这里形同虚设,因为它的前提是输入空间够大。
  4. 修法:承诺时拼一个随机 nonce,公布 commit = H(choice ‖ nonce),nonce 取随机 32 字节。
  5. 原像空间变成 3 × 2²⁵⁶,正着枚举试不完。
  6. 揭晓时把 choice 和 nonce 一起公布,对方重算比对。揭晓前 nonce 要保密。
  7. 结论:哈希不提供机密性。它保护的是「数据没变」,低熵输入下的哈希等于明文。

要点:这一招和存密码时的盐同源,都是往原像里加随机字节。

答题格式:先写问题(原像只有三种,正着枚举),再写修法(拼 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 哈希链:改一块,后面全要重算:把哈希装进一串数据块里,看篡改为什么藏不住。

下一讲 →
C01b C01b 哈希链:改一块,后面全要重算

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