散列函数的应用及其安全性
一、给出散列函数的具体应用。
1.消息认证
（1）概念：消息认证是用来验证消息完整性的一种机制和服务。消息认证确保收到的消息和发送时是一样的，同时。此外，还要确保发送方声称的身份是真实有效的，当Hash函数用于提供消息认证功能时，被称为消息摘要。
（2）使用本质：发送者根据待发送的消息使用该函数计算一组Hash值，然后将Hash值和消息一起发送过去。接收者收到后对于消息执行同样Hash计算，并将结果与收到的Hash值进行对比。如果不匹配，则接收者推断出消息（也可能是Hash值）遭到了篡改。
（3）Hash码提供消息认证的方法
a.使用对称密码算法加密消息和Hash码。
b.使用对称密码算法只对Hash码进行加密。
c.不使用加密算法，仅使用Hash函数实现消息认证。
d.通过将整个消息和Hash值加密，能够在方案c的基础上提供保密性。
（4）一般情况，消息认证是通过使用消息认证码（MAC）实现的，即带密钥的Hash函数。通常情况下，通信双方基于共享的同一密钥来认证彼此之间交互的信息时，就会使用MAC。MAC是Hash函数和加密函数操作的结合。MAC提供安全保护，用于抵抗不知道密钥的攻击者的攻击。
2.数字签名
（1）概述：操作与MAC类似，在进行数字签名过程中使用用户的私钥加密消息的Hash值，其他人任何知道该用户公钥的人都能够通过数字签名来验证消息的完整性。
（2）Hash码提供数字签名的方法
a.使用发送方的私钥，利用公钥密码算法仅对Hash码进行加密。
b.先用发送方私钥对Hash码加密，再用对称密码中的密钥对消息和公钥算法加密结果加密。
3.其他应用
（1）产生单向口令文件。
（2）入侵检测和病毒检测。
（3）用于构建随机函数（PRF）或用作伪随机数发生器（PRNG）。
二、结合生日攻击、以及2004、2005年王晓云教授有关MD5安全性和2017年google公司SHA-1的安全性，说明散列函数的安全性以及目前安全散列函数的发展。问题2的回答可以结合下面给出的第一个链接。
1.简述
（1）生日攻击
概念：生日攻击是指在网络安全中利用生日现象，找到冲突的密码学哈希函数值，伪造报文，攻击报文身份验证算法的模式
种类：签名方案中的生日攻击、基于离散对数的生日攻击
（2）2004、2005年王晓云教授有关MD5安全性
安全的Hash函数在设计时必须满足的一个要求是寻找两个输入得到相同的输出值在计算上是不可行的，这就是我们通常所说的抗碰撞的。MD5就是这样一个在国内外有着广泛的应用的Hash函数算法，它曾一度被认为是非常安全的。然而，王小云教授发现，可以很快的找到MD5的“碰撞”，就是两个文件可以产生相同的“指纹”。这意味着，当你在网络上使用电子签名签署一份合同后，还可能找到另外一份具有相同签名但内容迥异的合同，这样两份合同的真伪性便无从辨别。
（3）2017年google公司SHA-1的安全性
Google 的安全团队攻破了SHA-1安全加密算法。这次攻破被命名为 SHAttered attack。研究者提供了两张内容截然不同，在颜色上存在明显差异，但 SHA-1 哈希值却完全相同的 PDF 文件作为证明。哈希碰撞（hash collision，即两个不同文件哈希值一致，也有译作哈希冲突）本来不应该发生。但实际上，当哈希算法存在漏洞时，一个有足够实力的攻击者能够制造出碰撞。进而，攻击者可以用去攻击那些依靠哈希值来校验文件的系统，植入错误的文件造成恶果。
2.散列函数的安全性
表1列出了被广泛认同的密码学Hash 函数的安全性需求。前三个特性是Hash函数实际应用的需求。
表1 密码学Hash函数H的安全性需求
第4 个条件单向性是指，由消息很容易计算出Hash码，但是由Hash码却不能计算出相应的消息。对使用一个秘密值的认证方法，这个性质非常重要。虽然该秘密值本身并不传送，但若Hash函数不是单向的，则攻击者可以按如下方式很容易地找出这个秘密值: 若攻击者能够观察或截获到传送的消息，则他可以得到消息M 和Hash 码h= H(S || M)，然后求出Hash 函数的逆，从而得出S || M= H-1(MDM)。由于攻击者已知M 和SAB || M，所以可得出SAB。
第5 个性质抗弱碰撞性可以保证，不能找到与给定消息具有相同Hash值的另一消息，因此可以在使用对Hash码加密的方法中防止伪造。如果第5条不成立，那么攻击者可以先观察或截获一条消息及其加密的Hash码，然后由消息产生一个未加密的Hash码，最后产生另一个具有相同Hash码的替代消息。
如果一个Hash 函数满足上表中的前5个要求，就称其为弱Hash函数。如果第6 个性质抗强碰撞性也满足,就称其为强Hash 函数。强Hash 函数能够保证免受如下的攻击: 通信双方中的一方生成消息，而另一方对消息进行签名。
图1展示了三个安全特性(抗原像攻击、抗弱碰撞攻击、抗强碰撞攻击)之间的联系。
图1 Hash函数安全特性之间的联系
一个函数如果是抗强碰撞的，那么也同时是抗弱碰撞的,但反之则不一定成立。一个函数可以是抗强碰撞的，但不一定是抗原像攻击的，反之亦然。一个函数可以是抗弱碰撞的,但不一定是抗原像攻击的，反之亦然。
表2展示了在不同应用环境下Hash 函数的安全性需求。
表2 各种数据完整性应用中Hash函数安全性需求
表1中的最后一个性质是伪随机性,在传统观念中并没有作为密码学Hash 函数的安全性需求，但却在实际使用中或多或少有所要求。参考文献[ JOHNOS ]指出密码学Hash 函数通常用于密钥产生、伪随机数发生器以及消息完整性应用，上述三个安全特性都要求Hash 函数的输出是随机的。因此需要Hash 函数的输出具有伪随机性。
3.目前安全散列函数的发展。
近年来，安全Hash算法(SHA)是使用最广泛的Hash函数。事实上，由于其余的被广泛应用的Hash函数被发现存在安全性缺陷，从2005年以来SHA或许是这几年中仅存的Hash算法标准。SHA由美国标准与技术研究所( NIST)设计，并于1993年作为联邦信息处理标准( FIPS 180)发布。随后该版本的SHA(即SHA-0)被发现存在缺陷，修订版于1995年发布(FIPS 180-1),通常称之为SHA-1。实际的标准文件称其为“安全Hash标准”。SHA算法建立在MD4算法之上，其基本框架与MD4类似。
SHA-1产生160位的Hash值。2002 年，NIST发布了修订版FIPS 180-2,其中给出了三种新的SHA版本，Hash值长度依次为256位，384位和512位，分别称为SHA-256, SHA-384和SHA-512。这些算法被统称为SHA-2。SHA-2同SHA-1类似，都使用了同样的迭代结构和同样的模算术运算与二元逻辑操作。在2008年发布的修订版FIP PUB 180-3中，增加了224位版本(表3)。SHA-2在RFC 6234中也有描述，基本上也是复制FIPS 180-3中的内容，但增加了C代码实现。
表3 SHA参数比较
2005 年,NIST宣布了逐步废除SHA-1的意图,计划到2010 年逐步转而依赖SHA-2 的其他版本。此后不久，一个研究小组[WANG05]给出了一种攻击,用260次操作可以找到两个独立的消息使它们有相同的SHA-1值,而以前认为要找到一个SHA-1碰撞需要280次操作，所需操作大为减少。这一结果应该加速了向SHA-2 版本的过渡。
三、结合md5算法中的选择前缀碰撞以及第二个链接中的helloworld.exe和goodbyworld.exe两个可执行文件的md5消息摘要值和两个文件的执行结果说明md5算法来验证软件完整性时可能出现的问题。
1.选择前缀碰撞
通过选择不同的前缀，计算生日数和碰撞块添加到文件尾部，即可得到两个具有相同的MD5的文件。不过，要计算出这些尾部数据并不容易，直接使用hashclash[[1]]的工具需要相当大的时间成本，但是碰撞作者对该工具进行改进后已经能够高效完成大量正常程序与恶意程序的碰撞了，以下为此阶段样本的典型样例（每组正常程序与恶意程序对照），由于碰撞的原理与文件格式无关，所以样本形态呈现了多样化的特点。其原理图大致如下：
2.helloworld.exe和goodbyworld.exe两个可执行文件的md5消息摘要值和两个文件的执行结果
（1）消息摘要值
我们将我们所选择的前缀冲突查找方法应用到文件HelloWorld.exe 和GoodbyeWorld.exe。这是为了仔细构建两个832字节的块，并将它们附加到两个文件的末尾。这2次832字节已经被构建，使得结果文件被重命名为HelloWorld-colliding.exe 和 GoodbyeWorld-colliding.exe。
虽然HelloWorld-colliding.exe 和 GoodbyeWorld-colliding.exe 是不同的文件，包含不同功能的程序，但它们都具有MD5哈希值。
（2）执行结果
helloworld.exe的执行结果是窗口一闪而过；goodbyworld.exe的执行结果是“Goodbye World :-(”的循环输出。
3.md5算法来验证软件完整性时可能出现的问题。
（1）结果分析
虽然这个生成器仅仅用于构造两个文件, MD5相同但内容不同,不是从MD5值逆推出的,但是说明MD5不可靠已经足以了.
（2）可能出现的问题
黑客可以通过软件伪造MD5值，病毒木马就能很轻松的躲过MD5校检。
如果黑客从网上下载一个工具，给其捆绑上木马，然后通过工具让其MD5值和原文件一样。那么当用户下载了文件后用MD5校检工具进行校检时就会发现带毒文件和原文件MD5值完全一样，就会去放心地去运行，结果可想而知。
参考文献
【1】HashClash https://www.win.tue.nl/hashclash/
【2】Vulnerability of software integrity and code signing applications to chosen-prefix collisions for MD5 http://www.win.tue.nl/hashclash/SoftIntCodeSign/
【3】生日攻击 http://wiki.mbalib.com/wiki/生日攻击
【4】原 密码学领域重大发现：山东大学王小云教授成功破解MD5 https://blog.csdn.net/Danielqin/article/details/98038?locationNum=11
【5】九兆次演算实现碰撞！Google攻破了最重要的加密技术 http://www.sohu.com/a/127115784_114837
【6】MD5碰撞的演化之路 http://www.360doc.com/content/17/0616/09/42958972_663564734.shtml
【7】提高警惕！MD5可伪造 文件校检不再安全 http://www.grabsun.com/article/2012/408291.html