散列函数的应用及其安全性

本次作业为扩展有关散列函数安全性的知识扩展。

作业题目：散列函数的应用及其安全性。

内容要求：

(1) 给出散列函数的具体应用。

(2) 结合生日攻击、以及2004、2005年王晓云教授有关MD5安全性和2017年google公司SHA-1的安全性，说明散列函数的安全性以及目前安全散列函数的发展。问题2的回答可以参考下面给出的第一个链接。

链接1：https://www.win.tue.nl/hashclash/

(3）结合md5算法中的选择前缀碰撞以及第二个链接中的helloworld.exe和goodbyworld.exe两个可执行文件的md5消息摘要值和两个文件的执行结果说明md5算法在验证软件完整性时可能出现的问题。

链接2：http://www.win.tue.nl/hashclash/SoftIntCodeSign/

一 、散列函数的具体应用

1、散列函数的说明

Hash，一般翻译做"散列"，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

HASH函数，又称杂凑函数，是在信息安全领域有广泛和重要应用的密码算法，它有一种类似于指纹的应用。在网络安全协议中，杂凑函数用来处理电子签名，将冗长的签名文件压缩为一段独特的数字信息，像指纹鉴别身份一样保证原来数字签名文件的合法性和安全性。在前面提到的SHA-1和MD5都是目前最常用的杂凑函数。经过这些算法的处理，原始信息即使只更动一个字母，对应的压缩信息也会变为截然不同的“指纹”，这就保证了经过处理信息的唯一性。为电子商务等提供了数字认证的可能性。

散列的概念属于查找，它不以关键字的比较为基本操作，采用直接寻址技术。在理想情况下，查找的期望时间为O(1)。

散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来，比如我们自定义密码的存储。

散列（Hashing）通过散列函数将要检索的项与索引（散列，散列值）关联起来，生成一种便于搜索的数据结构（散列表）。

2、散列函数特征

HASH函数必须具备两个基本特征：单向性 和 碰撞约束。

单向性是指其的操作方向的不可逆性，在HASH函数中是指 只能从输入推导出输出，而不能从输出计算出输入；

碰撞约束是指 不能找到一个输入使其输出结果等于一个已知的输出结果 或者 不能同时找到两个不同的输入使其输出结果完全一致。

一个函数只用同时严格的具备了这样的特性，我们才能认可这样的一个HASH。

HASH函数的特点：固定长度的输出，单向不可逆，碰撞约束。

3.散列函数的具体应用

 Hash函数被广泛的应用于各种不同的安全应用和网络协议中

1、保证数据的完整性

就是用散列函数对数据或文件进行转换，生成一个散列码并保存，下次使用该数据和文件，同样进行散列函数计算得出结果与之比较，如果数据或文件被恶意篡改的，这两个值就不同了。以此发现病毒或入侵者。因为一个比特或几个比特被改变，它的hash结果就被改变。

2、单向数据加密

例子有口令加密，将用户口令的散列码存到一个表中，使用时将用户输入口令进行散列运算然后与准备好的散列表值进行对比，从而完成口令的有效验证。

3、数字签名

 

所谓数字签名(Digital Signature)（又称公钥数字签名、电子签章）是一种类似写在纸上的普通的物理签名，但是使用了公钥加密领域的技术实现，用于鉴别数字信息的方法。一套数字签名通常定义两种互补的运算，一个用于签名，另一个用于验证。

散列函数用于消息认证

MAC（消息认证码（带密钥的hash函数））

消息认证码（带密钥的Hash函数）：密码学中，通信实体双方使用的一种验证机制，保证消息数据完整性的一种工具。构造方法由M.Bellare提出，安全性依赖于Hash函数，故也称带密钥的Hash函数。消息认证码是基于密钥和消息摘要所获得的一个值，可用于数据源发认证和完整性校验。

 消息认证是用来验证消息完整性的一种机制和服务。消息认证确保收到的数据确实和发送时的一样，还要求消息认证机制确保发送方声称的身份是真实有效的。当Hash函数用于提供消息认证功能时，Hash函数值通常被称为消息摘要。

 

发送方根据待发送的消息使用该函数计算一组Hash值，然后将Hash值和消息一起发送过去。接收方接收后对于消息执行同样的Hash计算，并将结果与收到的Hash值进行比较。如果匹配，则消息准确。反之，消息遭受了篡改。

实际应用中，消息认证通常使用消息认证码（MAC）实现。MAC函数将通信双方共享的密钥和数据块作为输入，产生Hash值作为MAC码，然后将MAC码和受保护的消息一起传递或存储。需要检查消息的完整性时，使用MAC函数对消息重新计算，并将计算结果与存储的MAC码对比。MAC提供安全保护，用于抵抗不知道密钥的攻击者的攻击。在实现中，往往使用比加密算法效率更高的特殊设计的MAC函数。

消息验证码有两种计算方式：

一种是利用已有的加密算法，如DES等直接对摘要值进行加密处理；另一种是使用专门的MAC算法。HMAC，它基于MD5或者SHA-1，在计算散列值时将密钥和数据同时作为输入，并采用了二次散列迭代的方式，实际计算方法如下：

HMAC（K，M）=H（K⊕opad∣H（K⊕ipad∣M））

其中K是密钥，长度应为64字节，若小于该长度，则自动在密钥后面用“0”填充补足。M是消息；H是散列函数；opad和Ipad分别是由若干个0x5c和0x36组成的字符串；⊕表示异或运算，∣表示连接操作。

 

散列函数用于数字签名

数字签字可以用对称算法实现，也可以用公钥算法实现。但前者除了文件签字者和文件接受者双方，还需要第三方认证，较麻烦；通过公钥加密算法的实现方法，由于用秘密密钥加密的文件，需要靠公开密钥来解密，因此这可以作为数字签名，签名者用秘密密钥加密一个签名（可以包括姓名、证件号码、短信息等信息），接收人可以用公开的、自己的公开密钥来解密，如果成功，就能确保信息来自该公开密钥的所有人。

Hash签名是最主要的数字签名方法，也称之为数字摘要法（digital digest）、数字指纹法（digital finger print）。它与RSA数字签名是单独的签名不同，该数字签名方法是将数字签名与要发送的信息紧密联系在一起，它更适合于电子商务活动。将一个商务合同的个体内容与签名结合在一起，比合同和签名分开传递，更增加了可信度和安全性。下面我们将详细介绍Hash签名中的函数与算法。
　　
单向函数
　　
　　单向函数的概念是公开密钥密码的核心。尽管它本身并不是一个协议，但对大多数协议来说却是一个基本结构模块。
　　
　　单向函数的概念是计算起来相对容易，但求逆却非常困难。也就是说，已知x，我们很容易计算f（x）。但已知f（x），却难于计算出x。在这里，"难"定义成：即使世界上所有的计算机都用来计算，从f（x）计算出x也要花费数百万年的时间。
　　
　　打碎盘子就是一个很好的单向函数的例子。把盘子打碎成数千片碎片是很容易的事情，然而，要把所有这些碎片再拼成为一个完整的盘子，却是非常困难的事情。

Hash签名不属于强计算密集型算法，应用较广泛。很多少量现金付款系统，如DEC的Millicent和CyberCash的CyberCoin等都使用Hash签名。使用较快的算法,可以降低服务器资源的消耗,减轻中央服务器的负荷。Hash的主要局限是接收方必须持有用户密钥的副本以检验签名, 因为双方都知道生成签名的密钥，较容易攻破，存在伪造签名的可能。如果中央或用户计算机中有一个被攻破,那么其安全性就受到了威胁。

（1）数据校验
    HASH函数有类似数据冗余校验类似的功能，但是它比简单的冗余校验碰撞的概率要小得多，顾而在现在密码学中总是用HASH来做关键数据的验证。

（2）单向性的运用
    利用HASH函数的这个特点，我们能够实现口令，密码等安全数据的安全存储。密码等很多关键数据我们需要在数据库中存储，但是在实际运用的过程中，只是作比较操作，顾而我们可以比较HASH结果。

（3）碰撞约束以及有限固定摘要长度
    数字签名正是运用了这些特点来提高效率的。我们知道非对称加密算法速度较低，通过HASH处理我们可以使其仅仅作用于HASH摘要上，从而提高效率。

（4）可以运用HASH到随机数的生成和密码，salt值等的衍生中
    因为HASH算法能够最大限度的保证其唯一性，故而可以运用到关键数据的衍生中（从一个随机的种子数产生，并且不暴露种子本身秘密）。

（5）产生单向口令文件

在操作系统中，存储口令的Hash值而不是口令本身，当用户输入口令时，操作系统将比对输入口令的Hash值和存储在口令文件中的Hash值来进行用户验证。

（6）用于入侵检测和病毒检测

将每个文件的Hash值H(F)存储在安全系统中(如CD-R)，随后就能通过重新计算H(F)来判断文件是否被修改过。入侵者只能够改变F，而不能改变H(F)

在信息安全方面的应用

1）文件校验
　　我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。
　　MD5 Hash算法的"数字指纹"特性，使它成为目前应用最广泛的一种文件完整性校验和（Checksum）算法，不少Unix系统有提供计算md5 checksum的命令。

2）数字签名
　　Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。对 Hash 值，又称"数字摘要"进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。

3）鉴权协议
　　如下的鉴权协议又被称作"挑战--认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。

二、结合生日攻击、以及2004、2005年王晓云教授有关MD5安全性和2017年google公司SHA-1的安全性，说明散列函数的安全性以及目前安全散列函数的发展。问题2的回答可以参考下面给出的第一个链接。

1、生日攻击

利用“两个集合相交”问题的原理生成散列函数碰撞，达到目的的攻击称为生日攻击，也称为平方根攻击。

生日攻击方法没有利用Hash函数的结构和任何代数弱性质，它只依赖于消息摘要的长度，即Hash值的长度。

第一类生日攻击：

              就是说，n个输入，其中有一个输出H(x),那我要多少个y才能使H(y)=H(x)的概率达到0.5？

              答案是2/n个。假如输出为m位长，那么就有2^m个输出。引出了第二类生日攻击

第二类生日攻击：

              k~=2^m/2，说明了散列值不能小于128位啊。

 模差分攻击：

              最有效的方法，也叫比特追踪法。这个假期研究研究。

生日攻击的方法

设h：X->Y是一个Hash函数，X和Y都是有限的，并且|X|>=2|Y|，记|X|=m，|Y|=n。显然至少有n个碰撞，问题是如何去找到这些碰撞。一个很自然的方法是随机选择k个不同的元素x1,x2,x3,.....,xk ∈X,计算yI=h(xi)，1<=i<=k，然后确定是否有一个碰撞发生。这个过程类似于把k个球随机地扔到n个箱子里边，然后检查看是否某一箱子里边至少有两个球。k个球对应于k个随机数x1,x2,x3,.....,xk，n个箱子对应于Y中的n个可能的元素。我们将计算用这种方法找到一个碰撞的概率的下界，该下界只依赖于k和n，而不依赖于m。

因为我们关心的是碰撞概率的下界，所以可以假定对所有y∈Y，有|h-1(y)|≈m/n。这个假定是合理的，这是因为如果原像集h-1(y)( y∈Y)不是近似相等的，那么找到一个碰撞的概率将增大。

因为原像集h-1(y)( y∈Y)的个数都近似相等，并且xI(1<=i<=k)是随机选择的，所以可将yI=h(xi)，1<=i<=k视作Y中的随机元素（yi(1<=i<=k)未必不同）。但计算k个随机元素y1,y2, .....yk∈Y是不同的概率是一件容易的事情。依次考虑y1,y2, .....yk。y1可任意地选择；y2 ≠y1的概率为1-1/n；y3 ≠y1 ,y2的概率为1-2/n；.....；yk ≠y1,y2, .....,yk-1的概率为1-(k-1)/n。

因此，没有碰撞的概率是（1-1/n）(1-2/n）.....(1-(k-1)/n）。如果x是一个比较小的实数，那么1-x≈e^-x，这个估计可由下式推出：e^-x=1-x+x²/2!-x³/3!+ .....。现在估计没有碰撞的概率（1-1/n）(1-2/n）.....(1-(k-1)/n）约为e^-k(k-1)/2n。我们设ε是至少有一个碰撞的概率，则ε≈1-e^-k(k-1)/2n，从而有k²-k≈nln(1/(1-ε)²)。去掉-k这一项，我们有k²≈nln(1/(1-ε)²)，即k≈sqrt(nln(1/(1-ε)²))。

如果我们取ε=0.5，那么k≈1.17 sqrt(n)。这表明，仅sqrt(n)个X的随机的元素就能以50%的概率产生一个碰撞。注意ε的不同选择将导致一个不同的常数因子，但k与sqrt(n)仍成正比例。

如果X是一个教室中的所有学生的集合，Y是一个非闰年的365天的集合，h(x)表示学生x的生日，这时n=365，ε=0.5，由k≈1.17 sqrt(n)可知，k≈22.3。因此，此生日问题的答案为23。

生日攻击隐含着消息摘要的长度的一个下界。一个40比特长的消息摘要是很不安全的，因为仅仅用2^20（大约一百万）次随机Hash可至少以1/2的概率找到一个碰撞。为了抵抗生日攻击，通常建议消息摘要的长度至少应取为128比特，此时生日攻击需要约2^64次Hash。安全的Hash标准的输出长度选为160比特是出于这种考虑。

中间相遇攻击是生日攻击的一种变形，它不比较Hash值，而是比较链中的中间变量。这种攻击主要适用于攻击具有分组链结构的Hash方案。中间相遇攻击的基本原理为：将消息分成两部分，对伪造消息的第一部分从初试值开始逐步向中间阶段产生r1个变量；对伪造消息的第二部分从Hash结果开始逐步退回中间阶段产生r2个变量。在中间阶段有一个匹配的概率与生日攻击成功的概率一样。

在修正分组攻击中，为了修正Hash结果并获得期望的值，伪造消息和一个分组级联。这种攻击通常应用于最后一个组，因此也称为修正最后分组攻击。差分分析是攻击分组密码的一种方法。这种攻击也可用来攻击某些Hash算法。

2、MD5算法

　　 MD5是一种摘要算法，所以理论上是不可能从签名取得原文。认为要从MD5的结果中取得原文才算破解，本身就是对摘要算法的误解。它通常应用于数字签名中，用于标识原文的原始性--即在签名后未作任何的修改。如果可以用不同的原文可以产生相同的签名，这也就意味着签名可能失效，就已经可以证明这种摘要算法的不安全。

　　MD5是一个在国内外有着广泛的应用的杂凑函数算法，它曾一度被认为是非常安全的。然而，王小云教授发现，可以很快的找到MD5的“碰撞”，就是两个文件可以产生相同的“指纹”。这意味着，当你在网络上使用电子签名签署一份合同后，还可能找到另外一份具有相同签名但内容迥异的合同，这样两份合同的真伪性便无从辨别。王小云教授的研究成果证实了利用MD5算法的碰撞可以严重威胁信息系统安全，这一发现使目前电子签名的法律效力和技术体系受到挑战。因此，业界专家普林斯顿计算机教授Edward Felten等强烈呼吁信息系统的设计者尽快更换签名算法，而且他们强调这是一个需要立即解决的问题。

3、2017年google公司SHA-1的安全性

2017年2月23日，Google经过两年的研究，表示其已经成功破解了SHA-1加密，具体的详情在90天之后我们就能知道(根据Google的披露原则)。同时，还发布了两份特制 PDF 文档，它们拥有相同的SHA-1值，但是内容却不尽相同。谷歌公司多年来一直主张弃用SHA-1方案，特别是在TLS证书签署等场景之下。早在2014年，Chrome小组就宣布将逐渐淘汰对SHA-1的使用。Google希望自己针对SHA-1完成的实际攻击能够进一步巩固这一结论，让更多人意识到其已经不再安全可靠。

关于SHA-1的安全性，早在2005年，密码学家就证明SHA-1的破解速度比预期提高了2000倍，虽然破解仍然是极其困难和昂贵的，但随着计算机变得越来越快和越来越廉价， SHA-1 算法的安全性也逐年降低，已被密码学家严重质疑，希望由安全强度更高的 SHA-2 替代它。但是现在还是有好多领域在使用SHA-1。SHA-1 被业内广泛用于数字签名、文件 完整性验证、以及保护广泛的数字资产(包括信用卡交易、电子文档、开源软件资源库与 软件更新等)的加密标准。

互联网的出现给人们的生活或者工作带来了极大的方便。但是随着计算机被广泛应用的信息时代，面对越来越多的信息。如何保护信息的安全越来越显得重要。特别是在网络化的 今天，我们的很多信息暴露在网上，比如出生证明、身份信息、信用卡信息、学籍信息等。如果我们不对这些信息加以保护，那将给我们的生活带来危害。哈希算法在我们日常网络安 全、代码仓库安全、甚至是确认文件的完整性方面都扮演着重要的角色。比如我们在登录系统时，将我们的登录密码进行哈希后再保存起来，可以防止存放账号密码的数据库被人入侵 时，破坏者仍然不知道我们的密码。

4、散列函数安全性

有两种方法可以攻击安全散列函数：密码分析法和暴力攻击法。散列函数抵抗暴力攻击的强度完全依赖于算法生成的散列码长度。Van Oorschot和Wiener曾经提出，花费1000万美元涉及一个被专门用来搜索MD5算法碰撞的机器，则平均24天内就可以找到一个碰撞。

        2004年8月中国密码学家王小云教授等首次公布了提出一种寻找MD5碰撞的新方法。目前利用该方法用普通微机几分钟内即可找到MD5的碰撞。MD5已经呗彻底攻破。

Hash函数的安全要求

1．单向性：对任何给定的散列码h，找到满足H(x)＝h的x在计算上是不可行的。

单向散列函数的说明

　　单向散列函数也称为消息摘要函数, 哈希函数 或者 杂凑函数

　　  单向散列函数输出的散列值又称为消息摘要 或者 指纹

单向散列函数的特点：

 

   （1)加密后密文的长度是定长的(即对任意长度的消息三列,得到的散列值是定长的

   （2)散列计算速度快,非常高效

   （3)如果明文不一样，那么散列后的结果一定不一样

     (4)如果明文一样，那么加密后的密文一定一样（对相同数据加密，加密后的密文一样）

     (5)所有的加密算法是公开的

     (6)具备单向性,不可以逆推反算

2．抗弱碰撞性：对任何给定的消息x，找到满足y≠x且H(x)=H(y)的y在计算上是不可行的。

当给定某条消息的散列值时，单向散列函数必须确保要找到和该条消息具有相同散列值的另外一条消息是非常困难的。

3．抗强碰撞性：找到任何满足H(x)=H(y)的偶对(x,y)在计算上是不可行的。

是指要找到散列值相同的两条不同的消息是非常困难的。

5、安全散列函数

安全散列函数结构：

因为所需的安全散列长度越来越长，因此我们可以使用有限定义域上的散列函数（俗称压缩函数）通过迭代方式拓展为具有无限定义域的散列函数。而最为代表性的就Merkle-Damgard结构

 

 

 

 

 

这个结构的好处是，如果压缩函数是抗碰撞的，那经过此结构处理后的散列函数也是抗碰撞的。

SM3，HMAC就是基于这种结构，因为Merkle-Damgard结构并不能抵抗扩展攻击，因此HMAC引入了Key。

 

 

三、结合md5算法中的选择前缀碰撞以及第二个链接中的helloworld.exe和goodbyworld.exe两个可执行文件的md5消息摘要值和两个文件的执行结果说明md5算法在验证软件完整性时可能出现的问题。

MD5算法：

       输入消息：长度小于2⁶⁴，以512位一组。

       输出消息：128位

过程：

1.消息填充：将消息长度填充至差64位就是512的倍数。那64位是表示填充长度的，是先从低位表示填充长度的。

2．填充后的消息是512的倍数，然后按512分组，每组又是16个32位长的字。

3．初始化中间结果：128位的缓存区来存储中间结果，对其初始化4个32位长的寄存器分别存放四个固定的整数。

4．迭代压缩：每个分组经压缩函数H_MD5处理。

      那就说说这个压缩函数，H_MD5有四轮处理，四个轮函数结构相同但是逻辑函数不同。

5.    输出：最后一个H_MD5的输出即为消息摘要。

MD5算法具有以下特点：

1、压缩性：任意长度的数据，算出的MD5值长度都是固定的。

2、容易计算：从原数据计算出MD5值很容易。

3、抗修改性：对原数据进行任何改动，哪怕只修改1个字节，所得到的MD5值都有很大区别。

4、强抗碰撞：已知原数据和其MD5值，想找到一个具有相同MD5值的数据（即伪造数据）是非常困难的。

MD5的作用是让大容量信息在用数字签名软件签署私人密钥前被"压缩"成一种保密的格式（就是把一个任意长度的字节串变换成一定长的十六进制数字串）。除了MD5以外，其中比较有名的还有sha-1、RIPEMD以及Haval等。

数据校验是为保证数据的完整性进行的一种验证操作。通常用一种指定的算法对原始数据计算出的一个校验值，接收方用同样的算法计算一次校验值，如果两次计算得到的检验值相同，则说明数据是完整的。

数据完整性校验

         检查数据有没有被篡改过，这里取个例子。当用Android手机进行OTA升级的时候，下载完升级包（不管是全升包还是增量包），紧接着就是用该升级包的标准MD5进行验证，如果校验的结果等于标准的MD5值，那么就证明这个升级包没有被篡改过。

一个MD5摘要可以对应多个原文，从而使得MD5加密算法变得不可逆，就因为这样，假如数据库中存着一个用户密码的MD5摘要，当用户登录时，需要将用户输入的密码转换为MD5摘要并与数据库中对应用户的MD5摘要进行比对，那么这样岂不是意味着用户输入了一个错误的密码而刚好这个错误密码的摘要恰好与数据库中的摘要匹配成功，这不就等于使用了错误密码但是登录成功了。

 

MD5算法中，需要初始链接变量，作为算法第一轮运算的基础，它作为MD5算法的初始值，可以想象，就算是同一段原文在进行MD5生成时，只要链接变量不一样，生成的MD5校验值也是不一样的。