关于散列函数安全性的知识扩展

一、给出散列函数的具体应用

（1）消息认证

当Hash 函数用于提供消息认证功能时，Hash函数值通常称为消息摘要。消息认证

是用来验证消息完整性的一种机制或服务。消息认证确保收到的数据确实和发送时的一样（即没有修改、插入、删除或重放）。此外，通常还要求消息确认机制确保发送方声称的身份是真实有效的。

（2）数字签名

与消息认证应用类似，对于Hash函数的另外一个重要应用就是数字签名。数字签名的操作与MAC相似，在进行数字签名过程中使用用户的私钥加密消息的Hash值，其他任何知道该用户公钥的人都能够通过数字签名来验证消息的完整性。在这种情况下，攻击者要想篡改消息，则需要知道用户的私钥。

（3）产生单向口令文件

当用户输入口令时，操作系统将比对输入口令的Hash值和存储在口令文件中的Hash值，这样一来，黑客即使能够访问口令文件，也不能够获取真正的口令。

（4）入侵检测和病毒检测

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

（5）构建随机函数（PRF）或用做伪随机数发生器（PRNG）

基于Hash函数的PRF可用于对称密码中密钥产生。

二、结合生日攻击、以及2004、2005年王晓云教授有关MD5安全性和2017年google公司SHA-1的安全性，说明散列函数的安全性以及目前安全散列函数的发展。

Hash函数的特性：

1. 特性概述：可以将任意长度的消息，压缩为某一固定长度的消息。
2. 单向性：对于给定消息x，H(x)很容易得出。但是对于给定z，寻找H(x)=z是不可行的。
3. 安全性： 抗弱碰撞性：有x,找一个y，使得H(x)=H(y)计算不可行；抗强碰撞性：寻找(x,y)，使得使得H(x)=H(y)计算不可行。
4. 雪崩性：雪崩效应，散列值的每一位都与消息的每一位有关，相近的消息，输出很大差别。

假定：一个取整数的随机变量，服从1到n的随机分布，一个含有k个这种变量的集合，至少有一对重复的概率记为P，P大于二分之一，求k的范围

解：对于h（x）=a（a为某个特定的值）的概率为1/n

对于h（x）<>a（a为某个特定的值）的概率为1-1/n

k个变量没有重复的概率为： =1(1-1/n) (1-2/n) (1-3/n)… [1-(k-1)/n]

至少一对重复的概率：P=1 – n!/[(n-k)!n^k]

根据不等式：(1-x) ≤e^-x(对于0 ≤ x ≤ 1)

P>1-e^{(-(k(k-1)/(2n))}

设E=1-e^{(-(k(k-1)/(2n))}

k约等于(2nln(1/(1-E))^0.5

当E=0.5，k约等于1.18n^0.5

生日攻击：

第一类生日攻击，就是说，n个输入，其中有一个输出H(x),那我要多少个y才能使H(y)=H(x)的概率达到0.5？答案是2/n个。假如输出为m位长，那么就有2^m个输出。引出了第二类生日攻击，k~=2^m/2，说明了散列值不能小于128位。

MD5算法：

两个不同的输入M和M’，但其Hash值一样，我们就称之为碰撞。

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

隐秘性指的是，找不到一种算法，能够由MD5值反推出输入M。换句话说，Hash函数是不可逆的。

MD5算法首先会将原始消息按512bit进行分组，那么最后一组很大概率是不到512bit的，这时候会对最后一组进行补齐，即补满512bit。这个过程称为padding。padding的规则是，在最末一个字节之后补充0x80，其余的部分填充为0x00，padding最后的8字节用来表示需要哈希的消息长度。

王晓云教授的碰撞算法：

王小云教授的成果集中在加速构造碰撞对。原来理论上构造出一个MD5碰撞对需要2^64次尝试，而现在只需要2^39次，其算法大大加速了这一过程。

长度拓展攻击：

在已知输入M的长度和其MD5值的情况下，可以在原文M后面附加任意内容，同时能够推算出新的MD5。在某些将MD5作为签名手段的系统中，攻击者可以在原文M后面随意添加内容同时能够提供正确的MD5值。

存在这一问题的原因是算法使用了Merkle–Damgård construction进行数据的压缩，不止MD5，很多流行的算法都存在这个问题，比如SHA1。

google公司攻破SHA-1：

SHA-1，被称作哈希(Hash)算法，一个非常流行的加密散列函数。在许多安全协议中广为使用，通常被用做密码加密，文件校验等，曾被视为MD5的后继者，且存在不可逆性。

但是，Google在公布的结果中，显示了两个不同的PDF文件，经过SHA-1处理后，产生了相同的哈希值。

它们包含了不同的内容，却拥有相同的 SHA-1 数字签名，意味着一个有效签名可被另一份 PDF 文件所滥用。

散列函数的发展：

1. 尽管有不建议被使用的算法，也不代表这就是完全过时的，事实上，就是因为有就得算法被发现问题，才会不断和更新新的算法，现有的优秀的算法都是在旧的算法的基础上改动的。

2.散列函数目前还是使用最为广泛的加密算法，尽管会出现安全性的问题，在找到新的更为有效的算法之前，应该会持续发展，更新算法并且网站也开始随之更新。但是旧的算法尽管使用的人数更少了，也依旧会有可能被继续发现安全性能的缺失

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

几位密码学家使用的是“构造前缀碰撞法”（chosen-prefix collisions）来进行此次攻击（是王小云所使用的攻击方法的改进版本）。

他们所使用的计算机是一台 Sony PS3，且仅用了不到两天。

他们的结论：MD5 算法不应再被用于任何软件完整性检查或代码签名的用途。

试验中的两个程序完全不同，但他们的MD5值校验却是一样的。
证实了两种不同格式的程序，其文件MD5是可以相同的。

两个文件绝大部分数据不同，但尾部数据高度相似，而且文件大小一致，这种构造方式是基于“选择前缀碰撞法”（Chosen-prefix collsion[[1]]）实现的，其原理图大致如下：

md5算法来验证软件完整性时可能出现的问题：由于可以构造出MD5值相同的软件，黑客会通过构造MD5相同的软件以此来躲避安全软件对恶意程序的查杀。