写给开发人员的实用密码学 - Hash算法

说到Hash（哈希），开发人员应该不陌生，比如Hash表是一种非常常用的数据结构，通过Hash表能够根据键值快速找到数据。哈希函数将文本（或其他数据）映射为整数，从而能够提高检索效率。

密码学中的Hash算法和普通的Hash算法不是同一个概念，从安全的角度考虑，密码学中的Hash算法除了有普通Hash算法的特性之外，还有其他的一些特性。

密码学Hash算法也通常称作摘要算法，是密码学中的基础算法，是现代密码学中的核心组成部分。2004年山东大学王小云教授发表论文，指出了MD5和SHA-1两种Hash算法的漏洞，引起了业界的恐慌，足以说明Hash算法的重要性。密码学中有很多密码学Hash算法，比如MD5、SHA-1、SHA128、SHA256、SHA512等，国家商用密码中也有一个Hash算法SM3。我们不用理解Hash算法的内部实现原理，更应该关注其特性、用途以及使用中需要注意的点。

在密码学中，Hash函数将任意大小（例如文本消息）的输入数据转换为固定大小（例如256位）的结果，这称为哈希值（或哈希码、消息摘要）。比如SHA-256和SHA3-256，可将任意输入转换为256位输出。

哈希算法

密码学Hash算法示例

我们可以借助 OpenSSL 附带的命令行工具计算字符串"hello"的SHA256算法哈希值：

$ echo -n "hello" | openssl sha256
(stdin)= 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

也可以借助开源国密算法库 GmSSL 的命令行工具，计算 SM3 算法的哈希值：

$ echo -n "hello" | gmssl dgst -sm3
(stdin)= becbbfaae6548b8bf0cfcad5a27183cd1be6093b1cceccc303d9c61d0a645268

密码学Hash算法的特点

设计一个Hash算法并不难，但要设计一个能用于密码学上的Hash算法非常难，需要有非常深厚的数学和密码学功底。一个设计良好的密码学Hash算法需要具有如下特点：

1. 确定性：相同的消息总是能得到同样的摘要值，特定的Hash算法，不管消息长度是多少，最终的摘要值长度是相同的。
2. 快速：计算任何给定消息的哈希值应该很快。
3. 难以分析：对输入消息的微小修改将完全改变输出哈希值。
4. 不可逆：通过摘要值很难逆向计算出原始消息，Hash算法具备单向性，摘要值是不可逆的，这也是非常重要的特性。为了逆向计算出原始消息，唯一的方法就是采用暴力攻击、字典攻击、彩虹表
5. 没有碰撞：找到两个具有相同哈希值的不同消息非常困难（或几乎不可能）。

注意第5点，没有冲突是一种理想情况，考虑到最后生成的摘要值只有固定的有限位，必然存在不同消息具有相同哈希值的情况，但这里强调的是找到它们非常困难。后面谈到 MD5 的破解将会谈到。

密码学Hash算法的用途

密码学哈希算法用途很广，下面看看最常见的几个用途：

• 文档/消息完整性

验证文件/文档/消息的完整性。比如我们在网站下载文件时，网站通常会给出文件的 MD5 值或 SHA256 值。

OpenSSL源码Hash值

通过对比哈希值，我们可以确保自己下载的文件和服务器上是一致的。

• 存储密码

这个开发人员应该很熟悉，当然也有菜鸟程序员直接往数据库中存储明文密码（从曝光的拖库攻击事件中，发现这么做的公司还不少）。开发人员通常不将纯文本密码保存在数据库中，而保存密码散列值或从密码派生的更复杂的值（例如，Scrypt派生的值）。

/etc/shadow文件

上面的示例来自现代 Linux 系统中的 /etc/shadow 文件，里面的密码存储为带盐的多轮SHA-512哈希值。

采用这种解决方案，即使数据库或数据文件泄露，攻击者也无法通过口令的摘要值计算出原始口令，攻击者很难伪造用户进行攻击。

系统具体如何校验用户密码呢？大概的步骤如下：

• 用户输入用户名和口令登录。
• 系统使用Hash算法计算出口令的摘要值。
• 系统使用用户名和摘要值在数据库表中进行检索，一旦匹配到就说明该用户输入的口令是正确的。
• 生成唯一ID

生成特定文档/消息的（几乎）唯一ID。密码散列函数几乎根据文档的内容唯一地标识文档。当然从理论上讲，任何哈希函数都可能发生碰撞，但是这种碰撞不太可能发生，因此大多数系统（如Git）都假定它们使用的哈希函数不存在碰撞。

这样的示例有 git 版本管理系统，其每一个提交通过一个哈希值标记。

git通过哈希值标记一个提交

这个特性还可以用来比较大文件，通过计算两个文件的Hash值，比较Hash值就可以判断两个文件是否相同。

• 伪随机数生成

伪随机数生成和密钥派生。生成随机序列的一种简单方法是这样的：从随机种子开始（例如键盘单击或鼠标移动）。附加“1”并计算散列以获得第一个随机数，然后附加“2”并计算散列获得第二个随机数，以此类推。

• 工作量证明算法

主要用在比特币，也就是俗称的挖矿。大多数工作量证明算法计算的哈希值大于特定值（称为挖掘难度）。为了找到此哈希值，矿工计算了数十亿个不同的哈希，并采用其中的最大哈希值，因为哈希数是不可预测的。例如，工作证明问题的定义如下：找到一个数字p，以使hash（x + p）的开头保留10个零位。

Hash算法一览

在过去，软件开发人员设计了许多密码哈希算法。其中有些已证明不安全（例如 MD5 和 SHA1 ），有些仍被认为是安全的（例如 SHA-2 、SHA-3 和 BLAKE2 ）。下面让我们了解一下目前广泛使用的加密哈希算法。

• MD5

MD5是一种比较常用的Hash算法，摘要值长度固定是 128 比特， MD5 算法目前被证明已经不安全了，不建议使用。

• SHA-1

SHA-1算法类似于MD5算法，输出的长度固定是160比特。SHA-1算法在严谨的加密学中已经被证明是不安全的，但在实际中仍然有使用，因为在现实世界中要构造出碰撞还是非常困难的，需要经过大量的运算。当然在新的应用中要避免使用。

• SHA-2

SHA-2是一系列强大的密码哈希函数：SHA-256（256位哈希）、SHA-384（384位哈希）、SHA-512（512位哈希）等。SHA-2算法是目前建议使用的Hash算法，在美国作为官方加密标准发布。

从设计上讲，哈希输出的位数越多，一般而言具有更高的安全性和更高的抗冲突性。通常，128位哈希函数要比256位哈希函数要弱，而256位哈希函数要比512位哈希函数弱。因此，SHA-512比SHA-256更强大。

• SHA-3

SHA-3算法并不是为了取代SHA-2算法，而是一种在设计上和SHA-2完全不同的算法，主要有四种算法，分别是SHA3-256、SHA3-512、SHA3-224、SHA3-384，输出的长度分别是256比特、512比特、224比特、384比特。

在相同的哈希长度下，SHA-3比SHA-2更安全。例如，SHA3-256比SHA-256提供更多的加密强度。

SHA-3被认为是高度安全的，在美国作为官方推荐的加密标准发布。

• SM3

SM3是国密密码杂凑算法标准，由国家密码管理局于2010年12月公布。SM3的输出杂凑值长度为256比特(32字节)，与国际标准SHA-256等长。SM3设计安全性为128比特，安全性与256比特椭圆曲线/SM2、SM4/SMS4、AES-128等同。

小知识：王小云院士真的破解了 MD5 吗？

2004年8月，在美国加州圣巴巴拉召开的国际密码大会上，王小云宣读了自己和研究团队对于MD4、MD5、HAVAL-128和RIPEMD四个国际著名密码算法的破译结果。

这被认为是2004年密码学界最具突破性的结果，堪称学术界的一场强烈地震。当年国际密码大会总结报告上写道：我们该怎么办？MD5被重创了，它即将从应用中淘汰。

2005年，美国《新科学家》杂志在一篇文章中，用了颇具震撼力的标题——《崩溃！密码学的危机》，报道了王小云团队花10年时间取得的学术成果。

所谓的“破解”其实误导了很多人，并不是说扔给王小云一个 MD5 散列值，然后她马上就能算出一个原文来。从密文推算出明文理论上是不可能的，所以王小云的研究成果并不能通过 MD5 的散列值逆向推算出明文。即给定 Hash 值，王小云不能逆向计算出 M。

MD5(M)=Hash

其中 M 指密码的明文，Hash 表示密码散列后的密文。

实际上，王小云的研究成果如下：

MD5(M1)=MD5(M2)

即给定消息 M1，能够计算获取 M2，使得 M2 产生的散列值与 M1 产生的散列值相同。如此，MD5 的抗碰撞性就已经不满足了，使得 MD5 不再是安全的散列算法。这样一来，MD5 用于数字签名将存在严重问题，因为可以篡改原始消息，而生成相同的 Hash 值。

这里，简单地用王教授的碰撞法给大家举个简单的例子。假如用户 A 给 B 写了个 Email 内容为 Hello，然后通过王教授的碰撞法，可能得到 Fuck 这个字符串的摘要信息和 Hello 这个字符串产生的摘要信息是一样的。如果 B 收到的 Email 内容为 Fuck，经过 MD5 计算后的，B 也将认为 Email 并没有被修改！但事实并非如此。

王小云院士的研究报告表明，MD4，MD5，HAVAL-128，RIPEMD 和 SHA-1 均已被证实存在上面的漏洞，即给定消息 M1，能够找到不同消息 M2 产生相同的散列值，即产生 Hash 碰撞。