3.2 Hash函数

Hash函数，也称为散列函数、哈希函数、杂凑函数，是现代密码学中另外一类重要的函数，它能够将任意长的字符串M映射成一个较短的定长字符串L，这一特性使其在数字签名和消息的完整性校验等方面有着重要的应用。Hash函数主要分为两类：一类是有密钥控制的Hash函数，即基于Hash函数的消息认证码；另一类是不带有密钥的Hash函数，用于产生消息摘要。

本节将介绍Hash函数的基本概念、基本用法、安全性以及常见的Hash函数，包括MD4和MD5算法以及SHA系列的安全Hash算法。

3.2.1 Hash函数的概念

1. Hash函数的基本概念

Hash函数的输入长度是可变的，返回一个固定长度串，这个串被称为输入信息的Hash值，也称为消息摘要。计算给定输入内容的Hash值是简单的，但给定某个Hash值，求其输入内容是比较困难的，即Hash函数是单向函数。Hash函数H一般满足下列性质。

1）函数H是公开的，其输入内容可为任意长度。

2）函数H的输出长度固定。

3）不同的输入内容不能产生相同的函数值（即无碰撞性）。

4）无法根据函数值推导出输入的内容。

Hash值的长度由具体的Hash函数确定，例如MD4算法的输出为128位，SHA-1的输出为160位。

2. Hash函数的通用结构

图3-2展示了Hash函数的一种通用结构，目前包括MD5、SHA-1等被广泛使用的Hash函数都采用这种结构。

在图3-2中，Hash函数的具体工作过程如下。

1）先把原始消息M分成L个固定长度为b的分组M_i（1≤i≤L），如果最后一个分组长度不够，需要将它填充成长度b。

2）将CV₀的初始值设定为IV。

3）重复使用压缩函数f，每次按次序将原始消息的分组M_i与上一级压缩函数的输出值CV_i-1作为输入，并产生一个固定长度为n的输出，即CV_i=f（CV_i-1，M_i-1），其中1≤i≤L。

4）最后一个输出值CV_i作为Hash值，即H（M）=CV_L。

3. Hash函数的基本用法

Hash函数与对称加密算法、公钥加密算法以及数字签名算法结合使用，可以实现有效的保密与认证等安全功能。图3-3展示了Hash函数的6种应用方法。

图3-3a可以实现保密性和认证，发送方A将消息M与其Hash值H（M）连接，用对称密码算法加密后发送至接收方B。接收方用与发送方共享的密钥K对密文解密后得到M′和H（M），而后计算M′的Hash值H（M′），通过比较H（M）和H（M′）来完成对消息M的认证。

图3-3b只提供了认证，未对消息M进行保密，只对消息的Hash值进行了加解密变换。

在图3-3c中，发送方A采用公钥密码算法，用A自己的私钥PR_a对消息M的Hash值进行签名得到E（PR_a，H（M）），而后与M连接后发出，接收方B用A的公钥PU_a对E（PR_a，H（M））进行解密得到H（M），再与B自己由接收消息M′计算得到的H（M′）进行比较来实现认证。该方案提供了认证和数字签名，称作签名—哈希方案。这个方案用对消息M的Hash值签名来代替对任意长消息M本身的签名，大大提高了签名速度和有效性。

在图3-3d中，发送方A发送给接收方B的信息是E（K，[M || E（PR_a，H（M））]），是在图3-3c的方案基础上增加了对称密钥加密保护，可提供认证、数字签名和保密性。

图3-3e是在哈希运算H中增加了通信双方共享的秘密值S，加大了对手攻击的困难性。但是，它仅仅提供了认证。

图3-3f是在图3-3e的方案基础上增加了对称密钥加密保护，可以提供保密性和认证。

4.针对Hash函数的攻击方法

Hash函数的安全性在于良好的单向性以及对碰撞的有效避免，通过Hash值来求得原消息是非常困难的，寻找两组消息使其Hash值相同也是非常困难的。对于Hash函数的攻击，其主要目标是用相同Hash值的非法消息来代替合法消息，以此来伪造信息。

目前，对Hash函数较有效的攻击方法是生日攻击和中途相遇攻击，这两种方法对Hash值为128位的Hash函数在理论上是有效的，但是当Hash值超过160位时，在计算上就是不可行的，所以目前使用Hash值大于160位以上的Hash函数是较为安全的。下面将介绍这两种针对Hash函数的攻击方法。

（1）生日攻击

生日攻击是指为了寻找到能够发生碰撞的消息而在消息空间中进行搜索的一种攻击方式。它适用于任何Hash函数，并被作为衡量一个Hash函数安全与否的重要参考。它来源于概率论上著名的生日悖论问题，即在一个教室中至少需要有多少个学生才能保证有两个学生的生日相同的概率不小于1/2。若从某些人中指定一个人，则他与其他人的生日相同的概率为1/365，但是如果不指定某个日期，从这些人里面找到生日相同的人，成功的概率就大得多。

将生日问题推广到消息的集合中，就可以得到在生日攻击的成功概率尽量低的情况下所需的Hash值长度。按照现在的计算条件，要想使一个Hash函数比较安全，其输出的Hash值长度不应小于128位。

（2）中间相遇攻击

中间相遇攻击的思路与生日攻击类似，但这种攻击只适合于具有分组链接结构的Hash函数。这种攻击也是通过不断地搜索和计算，在消息集合中寻找能够产生碰撞的消息。在进行中间相遇攻击时，攻击者首先随意选出若干个消息分组，将它们分为两部分。然后对其中的第一部分从初值开始进行迭代，到中间的某一步结束，得到I个输出；第二部分从Hash值（任意选定）开始用逆函数进行反向迭代，也是到中间的某一步结束，得到J个输出。最后，对这两部分的输出进行比较，如果能得到相同的输出值，就可以得到一对碰撞消息。

类似于生日攻击，可以通过计算得到为了获得对应的碰撞消息概率所需的消息数I+J的大小。通过研究发现，为了能够抵抗选择明/密文攻击，需要分组加密函数的分组长度不小于128位，同时函数还需要具有伪随机置换的性质。

目前常用的Hash算法有：MD4、MD5、SHA-1和SHA-2。这些算法的优点是运算速度要比对称密码算法快。下面将逐一介绍MD4、MD5和SHA-1算法。

3.2.2 MD4和MD5算法

美国麻省理工学院教授Ronald Rivest分别于1990年和1991年设计出了MD4和MD5两种信息摘要算法。MD5是在MD4的基础上发展而来的，虽然比MD4稍微晚一些，但更加安全。下面对这两种算法做详细介绍。

1.算法简介

MD4算法是一种用来测试信息完整性的Hash算法。它是通过32位操作数的位操作来实现的，所以适用在32位的处理器上并用高速软件进行实现。它的安全性并不是基于大数分解这样的数学难题，有人很快就用分析和差分的方法成功攻击了MD4算法三轮变换中的两轮，证明了它并不像期望的那样安全。于是，Rivest对MD4算法进行了改进，从而发明了MD5算法。

MD5算法是MD4的改进版本。消息在初始化处理之后，需要对附加位进行填充。消息首先被拆成若干个512位的分组，其中最后一个分组是“消息尾部+1和0组成的填充字节+64位消息长度”，以确保不同长度的消息在填充后不相同。之后，MD5将每一个512位分组又划分为16个32位子分组。

接下来，每个512位消息分组就以16个32位字的形式进入算法的主循环，512位消息分组的个数决定了循环的次数。图3-4所示，MD5的主循环有4轮，每轮进行16次操作，每一轮的操作过程相似。每次操作对a、b、c、d中的3个做一次非线性函数运算，并将所得结果加上第4个变量、一个子分组和一个常数。再将所得结果向右循环移动一位，并加上a、b、c、d中的一个。最后，用该结果取代a、b、c、d中的一个。MD5算法的输出由4个32位分组组成，将它们级联形成一个128位的Hash值。

64位的消息长度限制导致了MD5的安全输入长度必须小于2⁶⁴位，因为大于64位长度的信息会被忽略。4个32位寄存器字a、b、c、d被称为链接变量，将始终参与运算并形成最终的Hash结果。

2. MD5算法的安全性

对于任何一个Hash函数来说，碰撞都是不可避免的，从一个规模较大的集合映射到一个规模较小的集合，必然会出现相同的情况。所以，对Hash函数而言，应该具有的特性是碰撞阻力，即实践过程中难以发生，而并非避免碰撞。

Rivest猜想对于128位的Hash值来说，MD5的强度已经达到了最大。理论上，要执行2⁶⁴次运算才能找出具有相同Hash值的两个消息，现在需要执行2¹²⁸次运算才能找到某个固定散列值的原消息。然而，2004年山东大学的王小云等人成功地找出了MD5算法的碰撞。发生碰撞的消息是由两个1024位长的串M、N构成，用M_i‖N_i表示M‖N的碰撞。在IBM P690上找到M和M_i的时间大约为1h，找到M和M_i之后，则只需15s至5min就可以找出N和N_i。

3.2.3 安全Hash算法

1.安全Hash算法（SHA）的发展过程

1993年，美国国家标准与技术研究院（NIST）公布了安全散列算法SHA-0。1995年，NIST又公布了改进后的版本SHA-1，其设计上模仿了MD5算法，接受任意长度的输入消息，但生成的是160位的消息摘要，抗穷举搜索的能力更强。2001年，NIST公布SHA-2作为联邦信息处理标准，包含SHA-224、SHA-256、SHA-384、SHA-512等6个算法，分别生成224位、256位、384位和512位的Hash值。2008年，NIST启动了安全Hash函数SHA-3的评选。2012年10月，Guido Bertoni、Joan Daemen、Michael Peeters和Gilles Van Assche设计的密码学函数族Keccsk被选中，被公布为新的Hash函数标准。

接下来对SHA-1算法做简单介绍。

2. SHA-1算法

SHA-1算法首先将消息填充为512位的整数倍。填充方法与MD5完全一样：先添加一个1，然后填充尽量多的0使其长度为512的倍数刚好减去64位，最后64位表示消息填充前的长度。

SHA-1算法有5个32位变量（而MD5仅有4个），先对它们进行初始化：h₀ =0x67452301、h₁=0xEFCDAB89、h₂=0x98BADCFE、h₃=0x10325476、h₄=0xC3D2E1F0。完成初始化之后，将这5个变量复制到另外的变量中：h₀到a，h₁到b，h₂到c，h₃到d，h₄到e。

然后开始算法的主循环部分。它一次可以处理512位消息，循环的次数是消息中512位分组的数目。主循环有4轮，每轮有20次操作（MD5有4轮，每轮有16次操作）。图3-5所示，每次操作选取a、b、c、d、e中的3个数进行一次非线性运算，然后进行与MD5中类似的移位和加运算。

在这之后，a、b、c、d、e分别加上h₀、h₁、h₂、h₃、h₄ ，然后让下一个消息分组继续运行算法。最后，SHA-1算法的输出结果由h₀、h₁、h₂、h₃和h₄级联而成。

3.针对SHA系列算法的攻击进展

1997年，王小云首次使用“比特追踪法”分析SHA-0算法，并在理论上攻破了SHA-0算法。随后，在2004年CRYPTO的Rump会议上，王小云、冯登国、来学嘉和于红波宣布了攻击MD5、SHA-0和其他Hash函数的初步结果。2005年2月，王小云和殷益群、于红波等人发表了攻破SHA-0的算法，只需要2³⁹次计算就能找到碰撞，对SHA-1的攻击只需要2⁶⁹次计算就能找到一组碰撞。之后，在2005年8月的CRYPTO会议接近尾声时，王小云、姚期智、姚储枫再次发表了攻破SHA-1的算法，可以通过2⁶³次计算找到碰撞。

目前，针对SHA-2的攻击算法也已经出现，这里不做详细介绍，有兴趣的读者可查阅相关资料。