10.1 概述

hash函数：输入不定长，输出是固定的长度，输出通常被称为摘要。

hash函数有很多应用。例如hash表。hash函数需要保证一件事情：对于两个相同的输入，产生相同的输出。这里需要强调，并不能保证两个相同的输出对应的是相同的输入。因为这是不可能做到的：因为固定了长度，摘要是有限个数的，而输入的可能性是无限的。另外一个好的hash函数需要可以快速地计算。

由于本书是一本密码学相关书籍，仅介绍密码学的hash函数。密码学中的hash函数可以用来构建消息认证算法，签名验签算法，和另外很多工具例如随机数生成器。本书之后的章节会对这些进行介绍。

密码学中的hash函数需要较一般的hash函数拥有更加强大的特点。对于密码学的hash函数，需要以下几点是不可能的（impossible hard）：

• 修改一条消息但是不改变它的hash
• 生成一条给定hash的原消息
• 对于同样的hash找出两条不同的消息

第一条特点对于密码学的hash函数可以说是“雪崩性的影响”。修改哪怕只是一位，将很使得整个摘要发生天翻地覆的变化：摘要的每一位有50%的概率会发生翻转，这并不意味着每一个修改都会引起接近一半的位反正翻转。更重要的是不可能找到碰撞或者近似碰撞。

第二条特点，说明给定摘要h，想要找出原文m是非常难的，这也被称为抗预映射（pre-image resistance）。这也使得hash函数应该是一个单向的函数，给定消息计算hash很容易，但是给定hash计算原消息非常难。

第三条特点，找到一条拥有同样hash的消息，有两重含义。首先：给定消息m，要找到另一条消息m‘和m拥有相同的hash要非常难，这也被称为第二抗预映射（second pre-image resistance）。其次，要找出两条消息m和m‘拥有相同的hash要非常的难。这被称为抗碰撞（collision resistance）。由于抗碰撞比抗第二预映射是更强的形式，它们有的时候也被称为弱抗碰撞（weak collision resistance）和强抗碰撞（strong collision resistance）。

这些概念通常来源于一些攻击，而不是抗攻击。例如，碰撞攻击就是一种尝试产生hash碰撞的攻击，而第二预映射的攻击就是尝试给定消息和摘要后，尝试找出第二个和其摘要相同的消息。

10.2 MD5

MD5是由Ronald Rivest在1991年在MD4基础上发明的。这个hash函数产生的输出是128位。过去这些年里，密码学协会已经揭示出MD5的一些弱点。在1993年Bert den Boer和Antoon Bosselaers发表了一篇关于MD5的“伪碰撞”的文章。Dobbertin扩展了这项研究使其可以产生碰撞。在2004年，在Dobbertin工装的基础之上，王小云，冯登国，来学嘉等发布了针对MD5的真正的碰撞攻击。同时王等使用碰撞的x509证书，然后给出了针对HMAC-MD5的辨别攻击。

目前已经不推荐使用MD5来产生数字签名，HMAC-MD5依然是安全的消息认证，然而不要在新的密码系统中使用它。

计算消息的MD5摘要需要以下5步。

• 添加扩展。先在末尾添加一位1，然后添加0直到长度达到448（模512）。
• 使用消息的原始长度模64的值，填充余下的64位，这个时候整个消息就是512的倍数了。
• 初始化4个32位的字，A，B，C和D。将其赋值为特定的4个常量。
• 首先定义4个非线性函数F、G、H、I，对输入的报文运算以512位数据段为单位进行处理。对每个数据段都要进行4轮的逻辑处理，在4轮中分别使用4个不同的函数F、G、H、I。每一轮以ABCD和当前的512位的块为输入，处理后送入ABCD(128位) [8] 。
• 之后A||B||C||D就是输出的摘要。

这个填充的模式使得MD5会遭受一些长度扩展的攻击。

在python中产生MD5摘要的方法如下：

import hashlib
hashlib.md5(b"crypto101").hexdigest()

10.3 SHA-1

SHA-1是NSA提出的hash函数，其也继承了MD4的一些设计，SHA-1产生的摘要长度是160位。和MD5一样，SHA-1也被认为用作数字签名是不安全的。许多软件公司和浏览器，包括Google Chrome已经全面替换掉了SHA-1算法。在2017年的2月23日来自CWI Amsterdam和Google的研究人员宣告他们创建了两个内容不同但SHA-1摘要值相同的文件。SHA-1被正式攻破。在这之前一些针对SHA-1缩减版本的破解方法，包括王小云提出的。“The SHAppending”着重于容许攻击者决定部分原消息的条件之下找到SHA-1的碰撞，容许攻击者决定部分原消息同城被认为可以挑选压缩函数的初始化向量。

在python中产生SHA-1摘要的方法如下：

import hashlib
hashlib.sha1(b"crypto101").hexdigest()

10.4 SHA-2

SHA-2是一个hash函数家族包括SHA-224，SHA-256，SHA-384，SHA-512，SHA-512/224和SHA-512-256，它们的摘要长度分别为224，256，384，512，224和256位。这些hash函数是基于Merkle-Damgard构造，可以被用于数字签名，消息认证和随机数生成。SHA-2不仅效率比SHA-1要高，其安全性也更好，因为其增强了抗碰撞性。

SHA-224与SHA-256是为32位处理器设计的，而SHA-384，SHA-512是为64位的处理器设计的。32位的在32位的CPU上运行的更快，64位的在64位的CPU上运行的更快。SHA-512/224和SHA-512/256是SHA-512的截断的版本，允许使用64位的字产生和32位一样的输出。（这样就可以有224或者256的摘要长度，并且在64位的CPU上有更好的性能）

SHA-2家族一览表

可以在python中调用这些函数，然后比较一下它们摘要的长度

>>> import hashlib
>>> len(hashlib.sha224(b"").digest())
28
>>> len(hashlib.sha256(b"").digest())
32
>>> len(hashlib.sha384(b"").digest())
48
>>> len(hashlib.sha512(b"").digest())
64

针对SHA-2的攻击

目前已证明有一些针对SHA-256和SHA-512的减轮版本的碰撞攻击和预映射攻击。例如Somitra Kumar Sanadhya 和Palash Sarkar已经可以破解SHA-256的24轮次版本（一共64轮，减少了后40轮）。在此强调针对减轮次的攻击目前并没有击破整个算法。

10.5 Keccak和SHA-3

Keccak是由Guido Bertoni, Joan Daemen, Gilles Van Assche, 和Michael Peeters发明的一个海绵过滤函数家族。Keccak已经在SHA3-224，SHA3-256，SHA3-384，SHA3-512的hash函数中标准化了。

尽管SHA-3听起来像是来自于SHA-2家族，但是两者的设计非常的不同。SHA-3在硬件上效率非常高，但是在软件上与SHA-2相比会慢一些。后面部分会介绍一些有关SHA-3的安全性，例如避免长度扩展攻击。

sha3在python3.6之后可以使用

import hashlib
hashlib.sha3_224(b"crypto101").hexdigest()
hashlib.sha3_256(b"crypto101").hexdigest()
hashlib.sha3_384(b"crypto101").hexdigest()
hashlib.sha3_512(b"crypto101").hexdigest()

10.6 密码存储

密码学中的摘要的最主要很不幸也是被破环地最完整的用例是密码存储。

假设有个服务，用户使用用户名和密码来登陆。服务就需要将密码进行存储，下一次用户登录的时候，就可以验证用户提供的密码。

存储密码有很多的问题，除了明显的字符串比对带来的时间上的攻击，如果存储密码的数据库暴露，攻击者可以更进一步读取所有的密码。由于很多用户的密码都会多次使用，这将是个灾难性的问题。大多数服务的用户数据库也会存储用户的电子邮箱，这样就很容易去攻击其他无关服务的用户账户。

对密码做摘要

一个直接的方法是将密码使用安全的hash算法计算摘要。因为hash是容易计算的，这样每次登录就可以计算hash和数据库中存储的进行比较即可。

如果一个攻击者攻破了用户数据库，他们可以看见一堆hash值，而不是实际的密码。由于hash值计算的逆过程对攻击者来说基本是不可能的，他们无法将这些hash转化会原始的密码。这也是人们通常认为的。

彩虹表

事实证明这个方案是有瑕疵的。人们真正使用的密码是非常有限的。即使是非常好的密码实例，通常也只有10到20个字符，包括了大多是键盘上可以打出来的字符。实际中，人们使用的密码更加糟糕，通常是基于一些单词（password，swordfish），包含更少的符号和更少的类型（1234），或者是以上的可以预见的修改（passw0rd）。

由于对于相同的输入，hash计算产生一样的摘要。如果用户在两个网站上使用相同的密码，然后两者都适用MD5做hash，那么密码数据库存储的值将会是一样的。然后很多人用的密码有非常通用，这样很多用户的密码都是同一个。

然后记住hash是容易计算的这一点，假设我们尝试这些比较通用的密码，然后把它们和其hash值对应的存储在一个巨大的表里。很多人正是这么做的，这个表会非常的有效，完全地攻破了很多密码存储设备。这些表被称为“彩虹表”。因为它们本质上是hash函数输出的列表。这些输出多少会随机分布。当被用十六进制格式记录，这个类似于HTML中颜色的表达方式，例如#52f211就是柠檬绿。

盐

彩虹表有效的原因是每一个系统都是在用通用的几个hash函数之一。同样的密码在各个地方都产生了同样的hash。

这个问题可以依靠加“盐”来解决。通过在密码上添加随机的前缀或者随机的后缀，然后再进行hash，同样的hash函数就会产生截然不同的hash结果。已经证明，同一个家族的hash函数，和相关的hash函数，拥有相当的安全和性能系统，但是会拥有完全不同的输出值。

盐的值和密钥hash一样要存储到数据库中。当用户使用密码授权的时候，将盐和密码结合在一起，然后进行hash，再和数据库中存储的hash进行比对。

如果选用的是一个比较大（例如32字节）的随机数做盐，就可以完全打败像类似彩虹表的提前攻击。为了能够有效使用彩虹表攻击，攻击者可能会对这些盐的值单独有一张表。由于即使是单张表通常已经很大，存储很多张这样的表基本是不可能的。尽管有攻击者可以存储所有的数据，他们也需要提前计算出这些数据。计算一张表就需要很大量的时间，计算2^160个不一样的表是不可能的。

有的系统对于所有的用户都是用同一个盐。这样可以阻止彩虹表攻击，但是它也给了攻击者，一旦知道了盐，就同时攻破所有密码的机会。攻击者可能可以简单的为这个盐计算一个彩虹表。然后将结果和已经hash的密码进行比较。这点可以通过每个用户都是用不同的盐来解决。现在的系统通常每个用户都有不同的盐，但是依然会被认为是可以被从根本上破坏的，虽然比较难地去猜测，但是依然不是安全的。

对于盐来说最大的问题可能是很多程序员可能灵光一闪认为他们在做正确的事情。他们听说了密码存储的破环机制，他们也知道应该做什么来代替，然后他们就忽略了密码存储服务的折衷的部分。他们没有把密码明文存储，也没有忘记加盐，也没有对与不同用户复用盐。这些是通常不知道这些问题的人容易犯的错误。然而不幸的是，即便是这样，依然还存在很多其他问题。

对于弱密码系统的现代攻击

对于一个现代攻击来说，加盐基本上起不到作用。现代攻击利用hash值很容易计算的特点。使用更快的硬件，可以简单的枚举所有的密码可能性。

加盐可以使得一些提前计算的攻击变为不可能，但是他们对于知道盐的情况，作用很小。一个方法是，你可能会想要去尝试隐藏盐。这个通常不是很有用，如果攻击者可以接触到这些数据库，尝试隐藏盐就不会成功。选用一个好的密码存储作为开始比尝试去修复有问题的那个要有用的多。

所以我们应该怎么做？

为了保护密码，需要的是密钥派生函数，其将会在后续章节中介绍。

然而密钥派生函数也是在密码学的hash函数上构建的，其性能和hash有很大不同。密码hash函数是很多安全工具（例如密钥派生函数或者消息认证算法）最重要的基础，它们和这些工具自身一样存在着大量的滥用的情况。在本章后面的内容，可以看到密码hash函数的一些好的用法和一些滥用。

10.7 长度扩展攻击

很多hash函数，特别是早期诞生的那些，hash函数内部会存储一个状态来计算摘要值。在一些简陋的工程系统中，这就引起了一个严重的法则：如果一个攻击者知道了M1的摘要H（M1）,那么就可以很容易计算H(M1||M2),即便攻击者并不知道M1的值。因为一旦知道了H(M1)，可以以此来重构hash函数，然后让其hash更多个字符。将hash函数的内部状态设置为已知的状态例如H(M1)被称为固定攻击（fixation）.

大多数现实世界的hash函数,会比上述的操作要复杂一些。通常hash函数会有一个填充的步骤，该步攻击者需要去重构。MD5和SHA-1拥有相同的填充步骤。这个步骤很简单，介绍如下：

1. 在消息后面增加1位1
2. 在后面增加0，直到长度满足448（模512）
3. 将填充前消息的总长度，作为一个64位的整数。填充到最后。

攻击者可以利用H(M1)计算出H(M1||M2),攻击者伪造填充，攻击者实际上计算H(M1||G||M2)其中G被称为填充胶（glue padding），被这么叫是因为它像胶一样将两个消息连接到一起。最难的部分是知道消息M1的长度。

在很多系统中，攻击者会对M1的长度进行非常有参考价值的猜测。例如，考虑密钥前缀身份认证码。用户发送消息Mi，对其进行认证Ai=H(S||Mi),其中S是一个共享的密钥。该部分内容将会在MAC算法章节进行讨论。

对于消息的接受者来说很容易计算函数，验证码的正确性。由于hash算法的特性，任何对于消息Mi的修改会给Ai的值带来颠覆性的改变。然后不幸地是攻击者很容易伪造消息。因为MAC通常会将消息原文一起发送，攻击者久知道了原消息的长度。然后攻击者简单低猜一下密钥的长度，这个通常是协议中固定的部分，即便不是，攻击者也只要最多尝试几百次就可以得到该值。与之相对猜测密钥的内容，对于任何合理选择的密钥来说都是不可能的。

有其他安全的使用hash函数的身份认证码算法，上文的正好不是安全的。在后面的章节会介绍那些安全的算法。

一些hash函数，特别是比较新的那些像SHA-3家族，就不会有这个长度攻击的问题。摘要的计算从内部状态开始计算，而不是直接使用内部的状态。

这就使得SHA-3hash函数不仅只是多了一点安全可靠性，它们也是的消息认证的机制变得简单。长度扩展攻击仅仅影响那些密码hash函数被滥用的场景。本书希望能尽可能地减少人们在使用中犯错误。

10.8 hash树

hash树是每个节点都是一个hash值的树，每个节点都包含了自己的内容和它的祖先的hash。根节点，没有祖先，通常仅仅hash自身的内容。

这个定义非常的广，实际中的hash树通常有严格的限制。它们可以是二叉树，或者可能仅有叶子节点携带数据，父节点携带派生数据。通常这些严格限制的树被称为Merkle树。

类似的树或者它们的变种在很多系统，特别是分布式系统中有广泛的应用。例子中包括分布式版本控制系统如Git，数字货币如比特币，分布式p2p网络如Bittorrent，以及分布式数据库如Cassandra。

10.9 遗留问题

本章介绍了hash函数，单纯依靠hash函数无法进行消息认证，以为任何人都可以计算这个值。另外，本书认为hash函数不能用来进行密码存储。本书将在之后的章节里继续跟踪这些问题。

然后本章集中了大量部分描述了hash函数不可以做什么，但是不用担心，hash依然是密码学基础中非常重要的一环。它们只是在一些场景中存在一些滥用。