作业题目：散列函数的应用及其安全性。
内容要求：(1) 给出散列函数的具体应用。(2) 结合生日攻击、以及2004、2005年王晓云教授有关MD5安全性和2017年google公司SHA-1的安全性，说明散列函数的安全性以及目前安全散列函数的发展。问题2的回答可以结合下面给出的第一个链接。（3）结合md5算法中的选择前缀碰撞以及第二个链接中的helloworld.exe和goodbyworld.exe两个可执行文件的md5消息摘要值和两个文件的执行结果说明md5算法来验证软件完整性时可能出现的问题。
链接1：https://www.win.tue.nl/hashclash/
链接2：http://www.win.tue.nl/hashclash/SoftIntCodeSign/
（1）所有散列函数都有如下一个基本特性：如果两个散列值是不相同的(根据同一函数)，那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果。但另一方面，散列函数的输入和输出不是一一对应的，如果两个散列值相同，两个输入值很可能是相同的，但并不能绝对肯定二者一定相等。输入一些数据计算出散列值，然后部分改变输入值，一个具有强混淆特性的散列函数会产生一个完全不同的散列值。典型的散列函数都有无限定义域，比如任意长度的字节字符串，和有限的值域，比如固定长度的比特串。在某些情况下，散列函数可以设计成具有相同大小的定义域和值域间的一一对应。一一对应的散列函数也称为排列。可逆性可以通过使用一系列的对于输入值的可逆"混合"运算而得到。
由于散列函数的应用的多样性，它们经常是专为某一应用而设计的。例如，加密散列函数假设存在一个要找到具有相同散列值的原始输入的敌人。一个设计优秀的加密散列函数是一个"单向"操作:对于给定的散列值，没有实用的方法可以计算出一个原始输入，也就是说很难伪造。为加密散列为目的设计的函数，如MD5，被广泛的用作检验散列函数。这样软件下载的时候，就会对照验证代码之后才下载正确的文件部分。此代码有可能因为环境因素的变化，如机器配置或者IP地址的改变而有变动。以保证源文件的安全性。
错误监测和修复函数主要用于辨别数据被随机的过程所扰乱的事例。当散列函数被用于校验和的时候，可以用相对较短的散列值来验证任意长度的数据是否被更改过。
1、错误校正：使用一个散列函数可以很直观的检测出数据在传输时发生的错误。在数据的发送方，对将要发送的数据应用散列函数，并将计算的结果同原始数据一同发送。在数据的接收方，同样的散列函数被再一次应用到接收到的数据上，如果两次散列函数计算出来的结果不一致，那么就说明数据在传输的过程中某些地方有错误了。这就叫做冗余检验。对于错误校正，假设相似扰动的分布接近最小。对于一个信息串的微扰可以被分为两类，大的(不可能的)错误和小的(可能的)错误。我们对于第二类错误重新定义如下，假如给定 H(x) 和 x+s，那么只要s足够小，我们就能有效的计算出x。那样的散列函数被称作错误校正编码。这些错误校正编码有两个重要的分类:循环冗余校验和里德所罗门码。
2、语音识别：对于像从一个已知列表中匹配一个MP3文件这样的应用，一种可能的方案是使用传统的散列函数--例如MD5，但是这种方案会对时间平移、CD读取错误、不同的音频压缩算法或者音量调整的实现机制等情况非常敏感。使用一些类似于MD5的方法有利于迅速找到那些严格相同(从音频文件的二进制数据来看)的音频文件，但是要找到全部相同(从音频文件的内容来看)的音频文件就需要使用其他更高级的算法了。那些并不紧随IT工业潮流的人往往能反其道而行之，对于那些微小差异足够鲁棒的散列函数确实存在。现存的绝大多数散列算法都是不够鲁棒的，但是有少数散列算法能够达到辨别从嘈杂房间里的扬声器里播放出来的音乐的鲁棒性。有一个实际的例子是Shazam[1]服务。用户可以用电话机拨打一个特定的号码，并将电话机的话筒靠近用于播放音乐的扬声器。该项服务会分析正在播放的音乐，并将它于储存在数据库中的已知的散列值进行比较。用户就能够收到被识别的音乐的曲名(需要收取一定的费用)
3、信息安全：
①文件校验：我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。MD5 Hash算法的"数字指纹"特性，使它成为目前应用最广泛的一种文件完整性校验和算法，不少Unix系统有提供计算md5 checksum的命令。
②数字签名：Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。对 Hash 值，又称"数字摘要"进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。
③ 鉴权协议：如下的鉴权协议又被称作挑战--认证模式:在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。以上就是一些关于hash以及其相关的一些基本预备知识。
（2）散列函数的安全性：
由于散列函数的应用的多样性，它们经常是专为某一应用而设计的。例如，加密散列函数假设存在一个要找到具有相同散列值的原始输入的敌人。一个设计优秀的加密散列函数是一个"单向"操作:对于给定的散列值，没有实用的方法可以计算出一个原始输入，也就是说很难伪造。为加密散列为目的设计的函数，如MD5，被广泛的用作检验散列函数。这样软件下载的时候，就会对照验证代码之后才下载正确的文件部分。此代码有可能因为环境因素的变化，如机器配置或者IP地址的改变而有变动。以保证源文件的安全性。
哈希函数的安全性直接关系到数字签名的安全性，如果哈希函数被攻破，数字签名的有效性就会受到质疑。 目前，已经发明的Hash函数有多种，如Snefru、N-Hash、LOKI、AR、GOST、MD、SHA等。它们在数学上实现的方法各有不同，安全性也各有不同。目前比较常用的Hash函数是MD5和SHA-1。 MD5哈希函数以512位来处理输入数据，每一分组又划分为16个32位的子分组。算法的输出由4个32位分组组成，将它们级联起来，形成一个128位的固定长度的哈希值，即输入数据的摘要。SHA-1哈希函数在MD4的基础上增加了数学运算的复杂程度，即SHA=MD4+扩展转换+附加轮+更好的雪崩效应（哈希值中，为0的比特和为1的比特，其总数应该大致相等；输入数据中一个比特的变化，将导致哈希值中一半以上的比特变化，这就叫做雪崩效应）。SHA能够产生160位的哈希值。对SHA还没有已知的密码攻击，并且由于它产生的哈希值位数长于MD5，所以它能更有效地抵抗穷举攻击（包括生日攻击）。但是，任何一种算法都有其漏洞和局限性。任何一个哈希函数都会存在碰撞——即在一些特定情况下，两个不同的文件或信息会指向同一个数字摘要。在一般情况下，类似碰撞只能尽可能地减少，而不能完全避免。从理论上讲，没有攻不破的密码。随着密码科学的发展，也许会找到攻破某一种密码算法的途径。
目前安全散列函数的发展：
安全散列算法(The Secure Hash Algorithm，SHA)由美国国家标准和技术协会(National Institute of Standards and technology，NIST)于1993年提出，并被定义为安全散列标准(Secure Hash Standard，SHS)。SHA-1是1994年修订的版本，纠正了SH一个未公布的缺陷。这种算法接受的输入文档小于2的64次方 位，产生160位的报文摘要。该算法实际的目标使得找出一个能够匹配给定的散列值的文本是不可能的计算，也就是说，如果对文档A已经计算出了散列值H(A)，那么很难找到一个文档B，使其散列值H(B)=H(A)，尤其困难的是无法找到满足上述条件的，而且有特定内容的文档B。SHA算法的缺点是速度比MD5慢，但是SHA的报文摘要更长，更有利于对抗野蛮的攻击。
到2005年2月，据王小云教授的研究报告，他们已经研究出了搜索SHA-1碰撞的一系列新技术。他们的分析表明，SHA-1的碰撞能在小于2^69次Hash操作中找到。对完整的80轮SHA-1的攻击，这是第一次在小于2^80次Hash操作这个理论界限的情况下找到碰撞。根据他们的估计，对于缩减到70轮的SHA-1能够用现在的超级计算机找出“实碰撞”。他们的研究方法，能自然地运用到SHA-0和缩减轮数的SHA-1的破译分析上。 2005年3月6日，Arjen Lenstra，王小云，Benne de Weger 宣布，他们构造出一对基于MD5 Hash函数的X.509证书，产生了相同的签名。他们提出了一种构造X.509证书的方法，在他们所构造出的证书对中，由于使用了MD5算法，签名部分产生了碰撞。因此，当证书发布者使用MD5作为Hash函数时，发布者就会在证书中产生相同的签名，导致PKI的基础原理遭到可信性破坏。这意味着，从单独某个证书无法确定是否存在另一个不同证书有着相同的签名。由于第二个相同签名证书存在的可能性，证书发布机构无法验证私钥的“拥有证明”，即无法验证证书中的签名。因此，使用“基于MD5函数”公钥证书的任何一方都无法确保所谓的证书拥有者是否真实拥有相应的私钥。他们也想构造一对基于SHA-1的X.509证书，产生相同的签名。然而，他们还做不到这一点，因为产生SHA-1碰撞还需要相当长一段时间的研究。
专家指出：A.Lenstra和王小云等人声称已经成功地构造了两张符合X．509证书数据结构，拥有同样签名而内容却不同的证书，但该构造方法对证书的部分域要有特殊安排，签名算法RSA的密钥也是按照特殊规律生成的，要用来攻击某个实际应用的电子签名系统仍需时日。而对于SHA-1算法，说其从理论上被破解都还为时过早，只能说其破解工作取得了重大突破，破解所需要运算次数已从原来设计时估算的2^80次降低为2^69次，这比穷举法快了２０４８倍，但2^69次运算需要６０００年左右的时间，在实际计算上仍然是不可行的。 除了运算方面的瓶颈外，哈希函数的不可逆性决定了攻击者无法轻易得手，没有人可以保证通过这个发现的每个碰撞都是“可用”的碰撞。在漫长的运算后，你得到的也许包含一些有价值的信息，也许就是理论上存在的单纯碰撞，运算瓶颈和信息匮乏都会使黑客们的种种努力成为徒劳……据业内人士估计，在当前的技术条件下，２^50或２^ ６０次运算量的范围内的攻击方法才会为我们带来麻烦，即引发实际意义上的攻击行为。在新研究成果发布前的一段时间内，SHA-1 算法只能被称作不完美，但还是安全的。基于PKI技术进行电子签名的最终用户，目前还不用担心自己的签名被伪造或遭遇签名人抵赖。
另外，安全专家强调：一种算法被破译，和整个企业的安全系统被攻破，是两个不同的概念。因为随着攻击技术和能力的提高，算法也会“水涨船高”，向前发展进步。王教授所取得的成就提醒密码学家研究新的算法，提醒有关标准化机构要提前修改算法标准，也提醒有关CA和电子签名产品开发商支持新的算法。当然，有些完全基于摘要算法的密押系统和电子货币系统，还需要尽早考虑替换方案。美国国家技术与标准局（NIST）曾经发表如下评论：“研究结果说明SHA-1的安全性暂时没有问题，但随着技术的发展，技术与标准局计划在2010年之前逐步淘汰SHA-1，换用其他更长更安全的算法（如：SHA-224, SHA-256, SHA-384和SHA-512）来代替。”
（3）散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。
影响产生冲突多少有以下三个因素：1.散列函数是否均匀；2. 处理冲突的方法；3.散列表的装填因子。散列表的装填因子定义为:α= 填入表中的元素个数/散列表的长度。α是散列表装满程度的标志因子。由于表长是定值，α与"填入表中的元素个数"成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大;α越小，填入表中的元素较少，产生冲突的可能性就越小。
实际上，散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。了解了hash基本定义，就不能不提到一些著名的hash算法，MD5和SHA-1可以说是目前应用最广泛的Hash算法，而它们都是以MD4为基础设计的。其中，MD5(RFC 1321)是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组，其输出是4个32位字的级联，与 MD4 相同。MD5比MD4来得复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好。MD5算法具有以下特点：1、压缩性:任意长度的数据，算出的MD5值长度都是固定的；2、容易计算:从原数据计算出MD5值很容易；3、抗修改性:对原数据进行任何改动，哪怕只修改1个字节，所得到的MD5值都有很大区别；4、强抗碰撞:已知原数据和其MD5值，想找到一个具有相同MD5值的数据(即伪造数据)是非常困难的。