哈希函数详解

当你下载软件并核对校验和、用密码登录、签署文件或向 比特币 添加一个区块时,都有哈希函数在起作用。它把任意数量的数据变成一个固定长度的简短指纹,即哈希值(也称摘要),而且这个过程无法逆转,也无法伪造。这个想法很简单,但对好的哈希函数的要求却很严格,而使用最广泛的两种哈希函数 MD5 和 SHA-1 没能经受住考验。

两条只差一个字母的消息进入哈希函数,输出两个完全不同的 SHA-256 哈希值,翻转的位在网格中标出
两条只差一个字母的消息进入哈希函数,输出两个完全不同的 SHA-256 哈希值,翻转的位在网格中标出

数据的指纹

哈希函数接收任意长度的输入,返回固定长度的哈希值:SHA-256 的哈希值为 256 位,写成 64 个十六进制数字。同样的输入总是给出同样的哈希值,因此哈希值可以代表数据。如果两个文件的 SHA-256 哈希值相同,就可以确定它们完全一样;如果下载的文件有一位损坏,它的哈希值就不再与发布者列出的一致。由于可能的输入远多于可能的哈希值,必然有许多输入共享同一个哈希值;好的哈希函数只是让人无法找到其中任何一个。

三项承诺

密码学哈希函数做出三项承诺。抗原像性:给定一个哈希值,无法找到能产生它的输入。抗第二原像性:给定一个输入,无法找到哈希值相同的另一个输入。抗碰撞性:无法找到任何两个哈希值相同的输入。对于 n 位的理想哈希函数,最好的攻击就是猜:找原像大约需要 2ⁿ 次尝试,找碰撞大约需要 2ⁿᐟ² 次。如果有人找到了比这快得多的方法,这个哈希函数就被称为已被攻破。

雪崩效应

输入改变一位,哈希值的每一位都应以一半的概率翻转,且彼此独立。这样,消息的微小改动就会产生一个看起来毫不相干的哈希值,而哈希值也不会透露输入的哪一部分发生了变化。SHA-256 通过 64 轮运算来实现这一点,每一轮都对它的八个 32 位字进行循环移位、相加和组合,因此几轮之内每个输入位都已影响到每一个字。相比之下,简单的字节和改变的量恰好等于输入改变的量,因此它会泄露一切。

SHA-256 的内部

SHA-256 首先填充消息:在末尾追加一个 1 位、若干个 0 以及消息的长度,使总长度成为 512 位的整数倍。然后它每次处理 512 位。每个分组被扩展成 64 个字,再混入由八个 32 位字组成的状态;状态的初始值是固定的,取自前八个素数的平方根。处理完最后一个分组后的状态就是哈希值。这种链式结构以 Ralph Merkle 和 Ivan Damgård 的名字命名,MD5、SHA-1 和 SHA-512 也都采用它;2015 年标准化的较新的 SHA-3 则使用一种称为海绵结构的不同构造。

拉尔夫·默克尔在2007年奇点峰会上。SHA-256 所用的链式结构以他和伊万·达姆加德的名字命名。
拉尔夫·默克尔在2007年奇点峰会上。SHA-256 所用的链式结构以他和伊万·达姆加德的名字命名。

生日攻击

在 23 人的群体中,有两人生日相同的概率略高于一半,尽管一年有 365 天,因为关键在于配对的数量,而配对数随人数的平方增长。哈希函数中的碰撞遵循同样的规律。在 2ᵏ 种可能的哈希值中,预计大约经过 √(π/2 · 2ᵏ) 个随机输入就会出现一次碰撞。对于 32 位,这大约是 8.2 万个输入,转眼就能完成;对于 128 位,这大约是 2⁶⁴,大型计算项目已经可以做到。这就是为什么 MD5 的 128 位从来都不算宽裕,也是为什么 SHA-256 把长度加倍,以提供 128 位的安全强度。

MD5 和 SHA-1:已被攻破

Ron Rivest 于 1991 年设计了 MD5,而 SHA-1 由 NSA 设计,于 1995 年发布。2004 年,王小云 和她的同事展示了如何快速制造 MD5 碰撞;2008 年,研究人员利用这种碰撞伪造了一张受网页浏览器信任的证书。2012 年的间谍软件 Flame 利用 MD5 碰撞伪装成 Microsoft 的更新。SHA-1 在 2017 年失守:Google 和 CWI Amsterdam 在进行了大约 2⁶³ 次计算后,公布了两个 SHA-1 哈希值相同的不同 PDF 文件。两者仍可用于发现意外错误,但不能用于任何可能遭到攻击者针对的场合。

哈希的用途

数字签名签的是文件的哈希值,而不是文件本身。Git 用哈希值为每个文件和每次提交命名,比特币 矿工则寻找经两次 SHA-256 哈希后以一长串 0 开头的区块头。网站绝不应存储密码本身,只应存储密码的哈希值;但由于人们常选短密码,这个哈希必须是慢速且加盐的,例如使用 bcrypt、scrypt 或 Argon2,让猜测变得代价高昂。ZIP 文件、PNG 图像和 Ethernet 中使用的 CRC-32 等校验和也是哈希,只不过它们是为了发现噪声而不是抵御攻击者而设计的。

亲自探索

打开哈希函数实验室,用 SHA-256、SHA-512、SHA-1、MD5、CRC-32 和玩具字节和计算你自己的文本的哈希值。按“改动一个字符”并数一数翻转的位;按“运行测试”在一千次单比特改动上进行雪崩测试,看看围绕哈希值一半位数的钟形曲线;按“寻找碰撞”在哈希值的前 8 到 32 位上找到真正的碰撞,观看生日攻击的实际过程。

常见问题

哈希和加密是一回事吗?

不是。加密是为了让持有密钥的人能够解开;哈希没有密钥,任何人都无法逆转。加密让消息保密,而哈希只提供一个指纹,让你核对手中已有的消息。

找到一次 SHA-256 碰撞需要多长时间?

用生日攻击,大约需要计算 2¹²⁸ 次哈希,这是一个 39 位数。即使地球上的每台计算机都只做这一件事,所需时间也远远超过宇宙的年龄。目前还不知道有任何捷径。

为什么同一段文本的两次哈希结果从不会不同?

哈希函数是确定性的:它没有随机性,也没有密钥,所以同样的字节总是给出同样的哈希值。但你看不见的细微差别,比如末尾多一个空格、不同的换行符,或带重音字母的另一种 Unicode 形式,确实会产生不同的哈希值。

什么是盐?

盐是一个与密码哈希存放在一起并混入其中的随机值。这样,密码相同的两个用户会得到不同的哈希值,攻击者也无法用同一张预先计算好的常见密码表来对付每个账户。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

打开哈希函数实验室