2023年7月27日发(作者：)

散列函数的应⽤及其安全性⽬录：⼀，给出散列函数的具体应⽤。⼆，结合⽣⽇攻击、以及2004、2005年王晓云教授有关MD5安全性和2017年google公司SHA-1的安全性，说明散列函数的安全性以及⽬前安全散列函数的发展。问题2的回答可以结合下⾯给出的第⼀个链接。三，结合md5算法中的选择前缀碰撞以及第⼆个链接中的和两个可执⾏⽂件的md5消息摘要值和两个⽂件的执⾏结果说明md5算法来验证软件完整性时可能出现的问题。⼀，给出散列函数的具体应⽤。 哈希函数（英语：Hash Function）是⼀种从任何⼀种数据中创建⼩的数字“指纹”的⽅法。散列函数把消息或数据压缩成摘要，使得数据量变⼩，将数据的格式固定下来。该函数将数据打乱混合，重新创建⼀个叫做散列值的指纹。散列值通常⽤来代表⼀个短的随机字母和数字组成的字符串。好的散列函数在输⼊域中很少出现散列冲突。在散列表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更难找到。由于散列函数的应⽤的多样性，它们经常是专为某⼀应⽤⽽设计的。例如，加密散列函数假设存在⼀个要找到具有相同散列值的原始输⼊的敌⼈。⼀个设计优秀的加密散列函数是⼀个“单向”操作：对于给定的散列值，没有实⽤的⽅法可以计算出⼀个原始输⼊，也就是说很难伪造。为加密散列为⽬的设计的函数，如MD5，被⼴泛的⽤作检验散列函数。这样软件下载的时候，就会对照验证代码之后才下载正确的⽂件部分。此代码有可能因为环境因素的变化，如机器配置或者IP地址的改变⽽有变动。以保证源⽂件的安全性。 总体来说，散列函数的具体应⽤主要有以下⽅⾯：1.错误校正 使⽤⼀个散列函数可以很直观的检测出数据在传输时发⽣的错误。在数据的发送⽅，对将要发送的数据应⽤散列函数，并将计算的结果同原始数据⼀同发送。在数据的接收⽅，同样的散列函数被再⼀次应⽤到接收到的数据上，如果两次散列函数计算出来的结果不⼀致，那么就说明数据在传输的过程中某些地⽅有错误了。这就叫做冗余校验。 对于错误校正，假设相似扰动的分布接近最⼩(a distribution of likely perturbations is assumed at least approximately)。对于⼀个信息串的微扰可以被分为两类，⼤的（不可能的）错误和⼩的（可能的）错误。我们对于第⼆类错误重新定义如下，假如给定 H(x) 和 x+s，那么只要s⾜够⼩，我们就能有效的计算出x。那样的散列函数被称作错误校正编码。这些错误校正编码有两个重要的分类：循环冗余校验和⾥德所罗门码。2.语⾳识别 对于像从⼀个已知列表中匹配⼀个MP3⽂件这样的应⽤，⼀种可能的⽅案是使⽤传统的散列函数——例如MD5，但是这种⽅案会对时间平移、CD读取错误、不同的⾳频压缩算法或者⾳量调整的实现机制等情况⾮常敏感。使⽤⼀些类似于MD5的⽅法有利于迅速找到那些严格相同（从⾳频⽂件的⼆进制数据来看）的⾳频⽂件，但是要找到全部相同（从⾳频⽂件的内容来看）的⾳频⽂件就需要使⽤其他更⾼级的算法了。那些并不紧随IT⼯业潮流的⼈往往能反其道⽽⾏之，对于那些微⼩差异⾜够鲁棒的散列函数确实存在。现存的绝⼤多数散列算法都是不够鲁棒的，但是有少数散列算法能够达到辨别从嘈杂房间⾥的扬声器⾥播放出来的⾳乐的鲁棒性。有⼀个实际的例⼦是Shazam服务，⽤户可以⽤电话机拨打⼀个特定的号码，并将电话机的话筒靠近⽤于播放⾳乐的扬声器，该项服务会分析正在播放的⾳乐，并将它于存储在数据库中的已知的散列值进⾏⽐较，⽤户就能够收到被识别的⾳乐的曲名。3，散列表　　散列表是散列函数的⼀个主要应⽤，使⽤散列表能够快速的按照关键字查找数据记录。（注意：关键字不是像在加密中所使⽤的那样是秘密的，但它们都 是⽤来“解锁”或者访问数据的。）例如，在英语字典中的关键字是英⽂单词，和它们相关的记录包含这些单词的定义。在这种情况下，散列函数必须把按照字母顺 序排列的字符串映射到为散列表的内部数组所创建的索引上。　　散列表散列函数的⼏乎不可能/不切实际的理想是把每个关键字映射到唯⼀的索引上（参考完美散列），因为这样能够保证直接访问表中的每⼀个数据。　　⼀个好的散列函数（包括⼤多数加密散列函数）具有均匀的真正随机输出，因⽽平均只需要⼀两次探测（依赖于装填因⼦）就能找到⽬标。同样重要的是，随机散列函数⼏乎不可能出现⾮常⾼的冲突率。但是，少量的可以估计的冲突在实际状况下是不可避免的（参考⽣⽇悖论）。　　在很多情况下，heuristic散列函数所产⽣的冲突⽐随机散列函数少的多。Heuristic函数利⽤了相似关键字的相似性。例如，可以设 计⼀个heuristic函数使得像, , , 等等这样的⽂件名映射到表的连续指针上，也就是说这样的序列不会发⽣冲突。相⽐之下，对于⼀组好的关键字性能出⾊的随机散列函数，对于⼀组坏的关键字经常 性能很差，这种坏的关键字会⾃然产⽣⽽不仅仅在攻击中才出现。性能不佳的散列函数表意味着查找操作会退化为费时的线性搜索。4.信息安全 Hash算法在信息安全⽅⾯的应⽤主要体现在以下⽅⾯：（1）消息认证 消息认证是⽤来验证消息完整性的⼀种机制和服务。消息认证确保收到的数据确实和发送时的⼀样（即没有修改，插⼊，删除或重放）。此外，通常还要求消息认证机制确保发送⽅声称的⾝份是真实有效的。⽬的：保证信息的完整性——验证信息的发送者是不是伪冒的（信源识别）；验证信息在传送或存储过程中未被篡改，重放或延迟等。⽅法：使⽤鉴别函数——证实收到的消息来⾃可信的源点且未被篡改。鉴别函数分类：（1）信息加密；（2）散列函数；（3）消息认证码；　Hash码能够通过如下不同⽅法⽤于提供消息认证

　　　a) 使⽤对称密码E加密消息和Hash码，由于只有A和B共享密钥K，所以消息必然发⾃A处，且可通过验证Hash码证明数据在传输过程中未被更改。　　　　b) 使⽤对称密码只对Hash码加密。由于明⽂⽆需加密性的应⽤，这种⽅案⼤⼤减少了加密操作的负担。　　　　c) 不使⽤加密算法，仅使⽤Hash函数实现消息验证。该⽅案中，通信双⽅共享相同的秘密值S，发送⽅A将消息M和秘密值S串联后计算其Hash值，并将得到的Hash值附在消息M后发送。因为接收⽅B同时掌握S值，所以能够重新计算该Hash值进⾏验证。　　　　d) 在⽅案c的基础上将整个消息和Hash值加密，以提供保密性。（2）数字签名⽬的：防⽌通信双⽅的抵赖⾏为。原理：利⽤已公开的验证算法⽣成数字签名，并将签名连接到被签消息上，数字签名可复制。Hash 算法也是现代密码体系中的⼀个重要组成部分。由于⾮对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了⼀个重要的⾓⾊。对 Hash 值，⼜称"数字摘要"进⾏数字签名，在统计上可以认为与对⽂件本⾝进⾏数字签名是等效的。⽽且这样的协议还有其他的优点。　数字签名的应⽤⽐消息认证更加⼴泛。主要有如下两种⽅案：　　

a) 使⽤发送⽅的私钥利⽤公钥密码算法对Hash码进⾏加密。这种⽅法也可提供认证；由于只有发送⽅可以产⽣加密后的Hash码，所以这种⽅法也提供了数字签名。b) 若既希望保证保密性⼜希望有数字签名，则先⽤发送⽅的私钥对Hash码加密，再⽤对称密码中的密钥对象消息和公钥算法加密结果进⾏加密，这种技术⽐较常⽤。（3）⽂件校验 我们⽐较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能⼒，它们⼀定程度上能检测并纠正数据传输中的信道误码，但却不能防⽌对数据的恶意破坏。MD5 Hash算法的"数字指纹"特性，使它成为⽬前应⽤最⼴泛的⼀种⽂件完整性校验和(Checksum)算法，不少Unix系统有提供计算md5checksum的命令。（4）鉴权协议如下的鉴权协议⼜被称作挑战--认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是⼀种简单⽽安全的⽅法。（5）其他应⽤：（1）产⽣单向⼝令⽂件当⽤户输⼊⼝令时，操作系统将⽐对输⼊⼝令的Hash值和存储在⼝令⽂件中的Hash值，这样⼀来，⿊客即使能够访问⼝令⽂件，也不能够获取真正的⼝令。（2）⼊侵检测和病毒检测将每个⽂件的Hash值H(F)存储在安全系统中，随后就能够通过重新计算H(F)来判断⽂件是否被修改过。⼊侵者只能够改变F，⽽不能够改变H(F)。（3）构建随机函数（PRF）或⽤做伪随机数发⽣器（PRNG）基于Hash函数的PRF可⽤于对称密码中密钥产⽣。参考⽂件：1， ⽣⽇攻击⽣⽇攻击是利⽤概率论中的⽣⽇问题，找到冲突的Hash值，伪造报⽂，使⾝份验证算法失效。防范⽅法·················· • 使⽤安全的Hash算法：安全的Hash算法⽣成的Hash值有⾜够多的位数。这样，攻击者在寻找两个具有相同Hash值的⽂件时就会⾮常困难。• 加盐：在为⽂件签名之前，先向⽂件添加⼀个随机值，然后计算Hash值，再将⽂件、签名和随机值⼀起发送给接收者。这样，攻击者必须找出具有特定Hash值的伪造⽂件，这⾮常困难。• 改动⽂件：在为⽂件签名之前，对消息或⽂件做少许改动。这样，攻击者必须找出具有特定Hash值的伪造⽂件，这⾮常困难。2，MD5 和 SHA1 MD5 和 SHA1 是⽬前应⽤最⼴泛的Hash算法，⽽它们都是以 MD4 为基础设计的。MD4(RFC 1320）是 MIT 的Ronald L. Rivest在 1990年设计的，MD 是 Message Digest 的缩写。它适⽤在32位字长的处理器上⽤⾼速软件实现--它是基于 32位操作数的位操作来实现的。 MD5(RFC 1321）是 Rivest 于1991年对MD4的改进版本。它对输⼊仍以512位分组，其输出是4个32位字的级联，与 MD4 相同。MD5⽐MD4来得复杂，并且速度较之要慢⼀点，但更安全，在抗分析和抗差分⽅⾯表现更好。 SHA1是由NIST NSA设计为同DSA⼀起使⽤的，它对长度⼩于2^64位的输⼊，产⽣长度为160bit的散列值，因此抗穷举（brute-force）性更好。SHA-1 设计时基于和MD4相同原理，并且模仿了该算法。2004年8⽉中国密码学家王⼩云教授等⾸次公布了提出⼀种寻找MD5碰撞的新⽅法。⽬前利⽤该⽅法⽤普通微机⼏分钟内即可找到MD5的碰撞。MD5已经被彻底攻破。在2017年，Google公司宣布实现了对SHA-1算法的攻击。SHA-1算法宣告攻破。实际上对于MD5来说，由于它的摘要信息位数⽐较短(128 bit)，现在⽤普通的计算机可以在⼏⼩时甚⾄⼏分钟之内找到冲撞对，这就是相当“廉价”了。⽽对于SHA-1(160 bit)来说，王⼩云教授的成果证明可以在2的69次⽅次尝试后找到冲撞对（这个结果之后在被不断地被改进），但这个计算量仍然过⼤，以当代的计算机运算能⼒来说，现实上仍然很难实现（需要的运算量⼤意味着需要的资⾦⼤）。对MD5的冲撞攻击是⽐较容易的，对SHA-1的冲撞攻击相对代价较⼤，但是随着机算机能⼒年年的发展正变得越来越容易实现 MD5和SHA-1共性：1.都是“不可逆”的函数。不存在⼀个算法能够由哈希值倒算出原始信息。2.对原始信息的任何⼀点改变都会导致结果的哈希值巨⼤的不同。举个例⼦，假如原始数据是⼏百万字的⽂章，你在其中哪怕改动⼀个标点，计算出的哈希值都会有很⼤的变化。3.运算代价是相对较低的。普通的AMDOpteron 2.2GHz的芯⽚，每秒可以计算出335MB数据的MD5值，可以计算192MB数据的SHA-1值。MD5 与SHA-1 的⽐较由于MD5 与SHA-1均是从MD4 发展⽽来，它们的结构和强度等特性有很多相似之处，表（1）是对MD5 与SHA-1 的结构⽐较。SHA-1与MD5 的最⼤区别在于其摘要⽐MD5 摘要长 32 ⽐特。对于强⾏攻击，产⽣任何⼀个报⽂使之摘要等于给定报⽂摘要的难度：MD5 是2128 数量级的操作，SHA-1 是2160 数量级的操作。产⽣具有相同摘要的两个报⽂的难度：MD5是 264 是数量级的操作，SHA-1 是280 数量级的操作。因⽽,SHA-1对强⾏攻击的强度更⼤。但由于SHA-1 的循环步骤⽐MD5 多（80:64）且要处理的缓存⼤（160 ⽐特:128 ⽐特），SHA-1的运⾏速度⽐MD5 慢。散列函数的⽬的是⽂件、消息或者其他数据块产⽣“指纹”。为满⾜在消息认证中的应⽤，散列函数H必须具有下列性质：（1）H可适⽤于任意长度的数据块。（2）H能够⽣成固定长度的输出。（3）对于任意给定的x，计算H(x)相对容易，并且可以⽤软/硬件实现。（4）对于任意给定的h，找到满⾜H(x)=h的x在计算上不可⾏，满⾜这⼀特性的散列函数称之为：具备抗原像攻击性。（5）对于任意给定的数据块x，找到满⾜H(y)=H(x)的y ≠ x在计算上是不可⾏；满⾜这⼀特性的散列函数称之为：抗弱碰撞性。（6）找到满⾜H(x) = H(y)的任意⼀对(x,y)在计算上是不可⾏的。满⾜这⼀特性的散列函数称之为：抗碰撞性。 前三个性质是使⽤散列函数进⾏消息认证的实际可⾏要求。第四个属性，抗原像攻击，防⽌攻击者能够回复秘密值。抗弱碰撞性保证了对于给定的消息，不可能找到具有相同散列值的可替换消息。满⾜上⾯前5个性质的散列函数称之为弱散列函数。如果还满⾜第6个性质则称之为强散列函数。 Hash函数的安全性很⼤程度上取决于抗强碰撞的能⼒。⽬前已有的对Hash函数攻击的⽅法包括⽣⽇攻击、彩虹表攻击、差分攻击等。Hash函数的算法结构特点和Hash值的长度是决定函数碰撞性的⽽主要因素，Hash值越长，抵御越强。SHA-256有256⽐特Hash值，MD5和SHA-1分别有128和160⽐特的Hash值。到⽬前为⽌，有两种⽅法可以攻击安全散列函数：密码分析法和暴⼒攻击法。散列函数抵抗暴⼒攻击的强度完全依赖于算法⽣成的散列码长度。穷举攻击：• 不依赖于任何算法的细节，仅与相应的长度有关。2004年8⽉中国密码学家王⼩云教授等⾸次公布了提出⼀种寻找MD5碰撞的新⽅法。⽬前利⽤该⽅法⽤普通微机⼏分钟内即可找到MD5的碰撞。MD5已经被彻底攻破。• 对于长度为m的Hash码，对于穷举攻击所需付出的代价分别于下表中相应量成正⽐.（通过⽣⽇悖论进⾏穷举攻击）抗原像攻击抗弱碰撞攻击抗强碰撞攻击密码分析：依赖于具体算法的设计缺陷，利⽤算法的某种性质。理想的Hash函数要求密码分析攻击所需的代价⼤于或等于穷举攻击所需的代价。⽬前安全散列函数的发展• 近些年，应⽤最⼴泛的散列函数是SHA。由于其他每⼀种被⼴泛应⽤的散列函数都已经被证实存在这密码分析学中的缺陷，接着到2005年，SHA或许仅存的安全散列算法。SHA由美国国家标准与技术研究院（NIST）开发。• 直到2017年2⽉23⽇，Google经过两年的研究，表⽰其已经成功破解了SHA-1加密。⾕歌公司多年来⼀直主张弃⽤SHA-1⽅案，特别是在TLS证书签署等场景之下。早在2014年，Chrome⼩组就宣布将逐渐淘汰对SHA-1的使⽤。Google希望⾃⼰针对SHA-1完成的实际攻击能够进⼀步巩固这⼀结论，让更多⼈意识到其已经不再安全可靠。• ⾕歌亦希望这⼀针对SHA-1的实际攻击案例能够最终说服整个技术业界尽快转向更为安全的替代性⽅案，例如SHA-256和SHA-3。

● 1995年公布SHA-1● 2002年，公布了SHA-2(SHA-256、SHA-384、SHA-512)● 2008年，增加了SHA-224SHA算法各个版本参数⽐较：三.结合md5算法中的选择前缀碰撞以及第⼆个链接中的和两个可执⾏⽂件的md5消息摘要值和两个⽂件的执⾏结果说明md5算法来验证软件完整性时可能出现的问题。（1）MD5算法的特点：压缩性：任意长度的数据，算出的MD5值长度都是固定的。容易计算：从原数据计算出MD5值很容易。抗修改性：对原数据进⾏任何改动，哪怕只修改1个字节，所得到的MD5值都有很⼤区别。弱抗碰撞：已知原数据和其MD5值，想找到⼀个具有相同MD5值的数据（即伪造数据）是⾮常困难的。强抗碰撞：想找到两个不同的数据，使它们具有相同的MD5值，是⾮常困难的。MD5：Message Digest Algorithm MD5 为计算机安全领域⼴泛使⽤的⼀种散列函数，⽤以提供消息的完整性保护。MD5的作⽤是让⼤容量信息在⽤数字签名软件签署私⼈密钥前被"压缩"成⼀种保密的格式（就是把⼀个任意长度的字节串变换成⼀定长的⼗六进制数字串）。（2）MD5选择前缀碰撞:选择前缀冲突——前缀冲突只要求在碰撞后⽂件应该完全相等。在碰撞之前，要找到碰撞的两个⽂件可以是任何东西：我们所选择的前缀碰撞查找⽅法总是会产⽣⼀个冲突，该冲突可以被合并到两个⽂件中，⽽不管碰撞之前存在什么数据。和两个可执⾏⽂件不同，但md5相同。（3）md5算法来验证软件完整性时可能出现的问题：1，不能确保⽂件的完整性。尤其是不能确保在⽂件传输、磁盘错误或其他⽆恶意涉⼊的情况下⽂件的正确性。2，不能确保⾃⼰从⽹络下载的⽂件，是否就是原发布者所提供的⽂件。3，不能通过校验MD5知道⽹站是否被⿊客⼊侵篡改，是否曾被恶意植⼊病毒或⽊马。

2m2m2m/2