2.3 Hash算法

讲解完随机数生成器算法后，接下来讲解密码学Hash算法（Cryptographic Hash Function），读者可能很奇怪为什么不先讲解更常用的加密算法，而先讲解随机数生成器算法和密码学Hash算法呢？

原因就在于随机数生成器算法和密码学Hash算法都是密码学中的基础算法，很多其他的密码学算法选择这两个算法作为加密基元（Cryptographic Primitives）。

2.3.1 加密基元

在介绍密码学Hash算法之前，简单介绍加密基元的概念，大部分算法完成的功能是单一的，很少有某个算法能够解决密码学中的所有问题。加密基元就是一些基础的密码学算法，通过它们才能够构建更多的密码学算法、协议、应用程序。加密基元类似于房屋的内部材料（砖头、水泥），基于材料搭建出房屋，才真正对人类有用。

加密基元的功能很单一，也很可靠，一般不会出现使用不当的问题，但为了构建出更多的密码学算法和协议，必须充分理解加密基元的原理、作用、注意点，否则很难基于加密基元构建出安全的密码学算法和协议。想象一下，建造房屋的时候，如果使用不好的材料或者错误地选用了材料，搭建出来的房屋会牢固吗？

对于大部分开发者来说，不要轻易设计加密基元，应该正确理解加密基元。密码学Hash算法就是非常重要的一个加密基元，表2-5列举了基于密码学Hash算法产生的其他密码学算法，读者暂时不用详细理解。

2.3.2 Hash算法和密码学Hash算法

开发者其实经常听到Hash算法这个名词，比如Hash表（散列表），通过Hash表能够根据键值快速找到数据，在Web开发中使用很广泛，比如memcached快速的原因就在于利用了Hash表。需要注意的是，密码学Hash算法和普通的Hash算法不是同一个概念，密码学Hash算法有Hash算法的所有特性，但从安全的角度考虑，密码学Hash算法还有其他的一些特性。基于普通Hash算法实现的应用，比如Hash表和校验和（checksums）不能用于密码学。

2.3.3 密码学Hash算法的特性

密码学Hash算法是非常重要的一个算法，是现代密码学中的核心组成部分，密码学中有很多密码学Hash算法，有很多的功能。读者在学习的时候，不用过于理解密码学Hash算法的内部实现原理，更应该关注其特性、用途、注意点。

密码学Hash算法的使用非常简单，可以用下列的公式描述：

摘要/散列值/指纹=hash（消息）

该公式由三部分组成，hash表示特定的Hash算法，消息就是输入值。由于Hash算法有很多功能，所以Hash算法有多种称呼，比如摘要算法（Message Digest Algorithms）、单向散列函数（Cryptographic One-way Hash Functions）。输出值也有多种称呼，比如摘要值、散列、指纹。读者看到这些名词的时候，都可以理解为Hash算法，重要的是甄别出什么样的Hash算法才能用于密码学。

密码学Hash算法的主要特性如下：

◎相同的消息总是能得到同样的摘要值，特定的Hash算法，不管消息长度是多少，最终的摘要值长度是相同的。

◎不管多长的消息，Hash运算非常快速，这是非常重要的特性。

◎通过摘要值很难逆向计算出原始消息，Hash算法具备单向性，摘要值是不可逆的，这也是非常重要的特性。为了逆向计算出原始消息，唯一的方法就是采用暴力攻击、字典攻击、彩虹表，对不同的消息组合进行迭代运算，运算的结果如果匹配该消息的摘要值，表示该Hash算法不应该用于密码学。

◎原始消息一旦修改，即使是很轻微的修改，最终的摘要值也会产生变化。

◎很难找出两个不同的消息，并且它们的摘要值是相同的。

从密码学的角度考虑，Hash算法能够实现密码学的某个目标，那就是消息防篡改，本章后面会描述。由于Hash算法的特性比较多，基于Hash算法有很多的应用场景，下面列举几个常见的例子。

2.3.4 Hash算法的用途

本节简单列举几个Hash算法应用的例子，读者借此会对Hash算法有进一步的理解，在阅读的时候，仔细体会Hash算法的5个特性。

1）文件比较

某个用户从互联网上下载了两个MP4格式的电影，但不确定是不是同一个电影，最快速的校验方法就是计算这两个电影的摘要值。采用Hash算法的原因有两点：不管多大的文件，摘要值的计算非常快速；第二个原因就是不同的文件，内容即使99%相同，对应的摘要值也是不同的。

大部分用户都在下载站下载过文件，每个下载页面会标识出文件对应的MD5值（MD5是一种Hash算法），用户完成文件下载后，为了避免该文件被攻击者篡改（比如被替换为一个木马文件），可以手动计算下载文件的MD5值，一旦该值和下载页面标识的MD5值是一致的，就可以放心使用。

2）身份校验

这也是Hash算法比较常用的一种功能，微博和微信系统中每个用户都有一个口令（password或者passphrase），用户登录微博和微信的时候，系统需要校验口令，校验通过则表示用户具有管理权限。

系统为了校验用户的口令，需要在数据库中存储口令，一旦数据库发生泄露，所有用户的口令都会暴露，这是相当严重的安全问题。考虑到Hash算法的一些特性，系统可以计算出口令的摘要值，然后存放到数据库中。采用这种解决方案的原理就是摘要值是很逆向的，即使数据库泄露，攻击者也无法通过口令的摘要值计算出原始口令，攻击者很难伪造用户进行攻击。

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

◎用户输入用户名和口令登录微博或者微信。

◎系统使用Hash算法计算出口令的摘要值。

◎系统使用用户名和摘要值在数据库表中进行检索，一旦匹配到就说明该用户输入的口令是正确的。

很多开发者喜欢使用该方案存储口令，但这个方案存在安全风险，本章后续部分会进一步讲解。

2.3.5 什么是安全的密码学Hash算法

普通的Hash算法会遇到各类的密码学攻击，而密码学Hash算法除了常规Hash算法的特性，还应该具备下面三个特性。

1）强抗碰撞性（Collision Resistance）

如果两个不相同的值能够得到同样的摘要值，表示产生了Hash碰撞。密码学中，Hash算法必须具备强抗碰撞性，否则不应该使用。

2）弱抗碰撞性（Second pre-image Resistance）

给定一个消息和这个消息对应的摘要值，很难找到一条不同的消息也具有相同的摘要值。如果某个算法不符合该特性，表示该算法遇到了second-preimage攻击。

在密码学中，选用的Hash算法至少也要具备弱抗碰撞性，具备弱抗碰撞性的算法必然也具备强抗碰撞性。读者需要注意的是，强抗碰撞性和弱抗碰撞性是相对的概念，强弱并不代表算法的安全程度。

3）单向性（Pre-image Resistance）

给定一个摘要值很难找出它的原始消息，如果计算出原始消息，表示该算法遇到了preimage攻击（attacks）。

大部分的密码学Hash算法都具备单向性，如果某个算法连单向性也不能保证，该算法肯定不能用于密码学。

对于攻击者来说，Hash算法的破解难度是：强抗碰撞性<弱抗碰撞性<单向性，也就是说首先破解的是强抗碰撞性。同时破解也分为理论破解和实用破解，一个Hash算法理论上产生了碰撞，并不代表该算法完全不能用于密码学，因为现实世界中发生碰撞的可能性还是非常低的。

2.3.6 密码学Hash算法的分类

密码学Hash算法有很多，比如MD5算法、SHA族类算法，MD5早已被证明是不安全的Hash算法了，目前使用最广泛的Hash算法是SHA族类算法。

1）MD5

MD5是一种比较常用的Hash算法，摘要值长度固定是128比特，MD5算法目前被证明已经不安全了，MD5算法违反了强抗碰撞性原则，但是还没有破坏单一性原则。

理论上经过280次运算就能产生碰撞，但目前最快只要经过263次运算就能破坏强抗碰撞性。

2）SHA

SHA（Secure Hash Algorithms）算法是美国国家标准与技术研究院（NIST）指定的算法，SHA算法不是一个算法，而是一组算法，主要分为三类算法。

（1）SHA-1

SHA-1算法类似于MD5算法，输出的长度固定是160比特。

目前SHA-1算法在严谨的加密学中已经被证明是不安全的，但是在实际应用过程中不并代表就有安全问题，在现实世界中要构造出碰撞还是非常困难的，需要经过大量的运算，不过还是尽量使用SHA-2类的Hash算法。

为什么说在实际应用过程中使用SHA-1算法并不代表就不安全了呢？举个例子，在Git中，所有存储的文件都会通过SHA-1算法计算出一个摘要值，在Git的内部结构中，摘要值和实际文件之间构成了索引关系。在计算摘要的过程中，原始输入除了文件本身的内容还包括其他一些元信息，文件内容可能会重复，但是元信息很难重复，所以最终摘要值很难发生碰撞，即使发生碰撞也只会影响这个仓库，更确切地说，在Git中使用SHA-1是为了保证数据的完整性而非机密性。

Hash算法的特点很多，在实际使用过程中要有分辨能力，不要看到SHA-1算法就潜意识认为有安全问题。

（2）SHA-2

SHA-2算法是目前建议使用的Hash算法，截至目前是安全的，主要有四种算法，分别是SHA-256、SHA-512、SHA-224、SHA-384，输出的长度分别是256比特、512比特、224比特、384比特。

（3）SHA-3

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

表2-6简单描述了相关Hash算法。