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

---

---

给出散列函数的具体应用

---

---

参考论文及博客

• 单向散列函数在密码学中的应用
  • 数字签名技术
    • 利用单向散列函数计算出需要签名的消息的邮摘，再利用签名算法对邮摘签名来代替直接对原来的消息进行签名
    • 有效地提高了签名的效率和速度，也减少了传输的信息量，节约了网络的带宽
  • 消息的完整性认证
    • 通常做法是文件的所有者用Hash算法计算出文件的Hash值，自己保存Hash值的一份拷贝，然后把文件存放在一个公开的地方。需要验证一个文件的完整性时，就用一个Hash算法计算存储文件的Hash值，和原来自己保存的Hash值相比较，相等则完整，反之则有改动。
    • 实际中使用 在网络上利用Hash函数进行完整性鉴别
      • 

      • 这种方法实现了再不安全的通信信道上的完整性认证，广泛地使用在电子商务的认证系统中
  • 一种改进的用户密钥管理方案
    • 用户的口令使用DES算法加密后存放在机器中的，但该算法对被加密的数据的长度有要求，即用户不能输入过长的密钥
    • 利用单向散列函数提出一种安全的用户密钥管理方案 如果K=E(H(P1))

    • 

    • 这个方法改进后允许用户输入任意长度的口令，由于单项散列函数的单向性，还可以弥补DES的一些不有缺陷，同时能够对付穷举攻击的威胁
• 其他方面的应用
  • 保密增强邮件 PEM（Privacy Enhanced Mail）
    • 因特网保密性增强邮件标准，提供的消息完整性检查中的鉴别使用的单项散列函数MD2和MD5
  • 邮件加密软件PGP 中2.6.3版本中使用的单项散列函数是MD5
  • 文件校验
    • 奇偶校验和CRC校验并没有抗数据篡改的能力
    • MD5 Hash算法的“数字指纹特性”，使它成为目前应用最广泛的一种文件网整形校验和（Checksum）算法
    • 应用场景为
      • 文件传送后的校验 得到的目标文件计算md5 checksum与源文件的做比对
      • 用作保存二进制文件系统的数字指纹，以便检测文件系统是否未经允许的被修改
  • 鉴权协议
    • pop3协议中就有这一应用
    • 需要鉴权的一方，向被鉴权的一方发送随机串（“挑战”），被鉴权方将该随机串和自己的鉴权口令字一起进行 Hash 运算后，返还鉴权方，鉴权方将收到的Hash值与在己端用该随机串和对方的鉴权口令字进行 Hash 运算的结果相比较（“认证”），如相同，则可在统计上认为对方拥有该口令字，即通过鉴权。

---

---

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

---

---

参考论文及博客

• MD5和SHA-1算法
  • MD5和SHA-1算法的核心是哈希函数。密码学哈希函数(Cryptography Hash Function，简称为哈希函数)又称杂凑函数，是在信息安全领域有广泛和重要应用的密码算法，主要作用是数据完整性验证和消息认证。它有一种类似于指纹的应用,所以有时候我们也把它叫做“数字指纹”。因为它具有以下特性：原始信息只要改变一点点，哪怕是几比特，对应的消息摘要也会改变很大。
  • 2004年8月17日在美国加州圣巴巴拉举行了一次国际密码学学术年会(Crypto’2004),当晚来自中国山东大学的王小云教授做了关于破译 MD5、HAVAL-128、 MD4和RIPEMD算法的报告。
  • SHA-1已经被公众密码社群做了非常严密的检验而还没发现到有不安全的地方，它在一段时间被认为是安全的，直到2017.02.23，Google宣布攻破SHA-1。
  • 结果显示是目前还不受Google发现的这个碰撞攻击方法影响。SHA-1发布于1993年，至今已经24年，计算机系技术这二十年是日新月异，二十多年已经很了不起了，加密算法都不得不在计算效率与破解难度之间权衡。一般来说十年左右更新一代，继任者sha-2发布于2001年，sha-3发布于2015年。实际的影响应该很有限。对于中国网站来说连https都没部署，大部分还是明文保存密码的，即使一些比较尊重客户的网站，也仅仅使用了早已经被公开碰撞方法的MD５加密方法而已。Google，facebook，微软，苹果等早已经换成了暂时安全的sha-256，sha-512等算法，属于sha-2系列，也已经发布快十五年了。应该很快就可以看到国际主流的网站更换sha-3算法了。

• 关于生日攻击
  • 生日攻击是利用概率论中的生日问题，找到冲突的Hash值，伪造报文，使身份验证算法失效。
  • 防范方法
    • 使用安全的Hash算法：安全的Hash算法生成的Hash值有足够多的位数。这样，攻击者在寻找两个具有相同Hash值的文件时就会非常困难。
    • 加盐：在为文件签名之前，先向文件添加一个随机值，然后计算Hash值，再将文件、签名和随机值一起发送给接收者。这样，攻击者必须找出具有特定Hash值的伪造文件，这非常困难。
    • 改动文件：在为文件签名之前，对消息或文件做少许改动。这样，攻击者必须找出具有特定Hash值的伪造文件，这非常困难。

• 散列函数的安全性
  • 通过对于生日攻击的了解，散列函数的安全性是有待提高的。生日攻击并没有利用任何HASH函数的性质，是对任何HASH都适用的普适的攻击方法，应对方法也很简单，增加HASH的长度，但是很难完成。
  • 以为相对于安全的MD5和SHA-1算法，在相继公布被实现碰撞之后，可以预见，之后的算法发现碰撞只是实现计算机更好性能的 时间长短而已。
  • 举个例子：中国铁道部的12306使用SHA-1算法，上传Google的验证网站
    • 结果显示是目前还不受Google发现的这个碰撞攻击方法影响。SHA-1发布于1993年，至今已经24年，计算机系技术这二十年是日新月异，二十多年已经很了不起了，加密算法都不得不在计算效率与破解难度之间权衡。一般来说十年左右更新一代，继任者sha-2发布于2001年，sha-3发布于2015年。实际的影响应该很有限。对于中国网站来说连https都没部署，大部分还是明文保存密码的，即使一些比较尊重客户的网站，也仅仅使用了早已经被公开碰撞方法的MD５加密方法而已。Google，facebook，微软，苹果等早已经换成了暂时安全的sha-256，sha-512等算法，属于sha-2系列，也已经发布快十五年了。应该很快就可以看到国际主流的网站更换sha-3算法了。

• 安全散列函数的发展
  • 安全散列函数结构
    • 因为所需的安全散列长度越来越长，因此我们可以使用有限定义域上的散列函数（俗称压缩函数）通过迭代方式拓展为具有无限定义域的散列函数。而最为代表性的就Merkle-Damgard结构
    • 
    • 这个结构的好处是，如果压缩函数是抗碰撞的，那经过此结构处理后的散列函数也是抗碰撞的。SM3，HMAC就是基于这种结构，因为Merkle-Damgard结构并不能抵抗扩展攻击，因此HMAC引入了Key。
  • 常用的散列函数
    • MD4算法 1990年，MD4算法的前两圈已被Dobbertin等人攻破，证明MD4算法是不安全的，但整个算法并没有被攻破过。
    • MD5算法 2004年，王晓云教授做了关于破译 MD5、HAVAL-128、 MD4和RIPEMD算法的报告。
    • SHA-1 2017年，GOOGLE宣布实现了碰撞。
    • HAVAL 是MD5算法的改进版，HAVAL用高非线性的7-变量函数取代了MD5的简单非线性函数。
    • SHA-256 输出由SHA-1的160位扩大到256位，迭代次数由SHA-1的80次增加到128次。
    • SHA- 384 输出扩大到384位，迭代次数增加到192次。
    • SHA-512 输出扩大到512位，迭代次数增加到256次。
  • 散列函数的发展
    • 尽管有不建议被使用的算法，也不代表这就是完全过时的，事实上，就是因为有就得算法被发现问题，才会不断和更新新的算法，现有的优秀的算法都是在旧的算法的基础上改动的。
    • 散列函数目前还是使用最为广泛的加密算法，尽管会出现安全性的问题，在找到新的更为有效的算法之前，应该会持续发展，更新算法并且网站也开始随之更新。但是旧的算法尽管使用的人数更少了，也依旧会有可能被继续发现安全性能的缺失。

---

---

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

---

---

参考论文及博客

• MD5选择前缀
  • 针对王小云教授等破译的以MD5为代表的Hash函数算法的报告，美国国家技术与标准局（NIST）于2004年8月24日发表专门评论，评论的主要内容为：“在最近的国际密码学会议（Crypto 2004）上，研究人员宣布他们发现了破解数种HASH算法的方法，其中包括MD4，MD5，HAVAL-128，RIPEMD还有 SHA-0。分析表明，于1994年替代SHA-0成为联邦信息处理标准的SHA-1的减弱条件的变种算法能够被破解；但完整的SHA-1并没有被破解，也没有找到SHA-1的碰撞。研究结果说明SHA-1的安全性暂时没有问题，但随着技术的发展，技术与标准局计划在2010年之前逐步淘汰SHA-1，换用其他更长更安全的算法（如SHA-224、SHA-256、SHA-384和SHA-512）来替代。”

  • 老师的链接中给的两个例子，显示的文字是不一样的，但是其MD5是一样的，使用的就是“构造函数碰撞法”
    • • 输出为 Hello World ;-)
      • 其MD5 为 18fcc4334f44fed60718e7dacd82dddf
      • 
    • • 输出为 循环输出 Goodbye World :-(
      • 其MD5 为 18fcc4334f44fed60718e7dacd82dddf
      • 
  • 他们的结论：MD5 算法不应再被用于任何软件完整性检查或代码签名的用途
  • 这几位密码学家编写的“快速 MD5 碰撞生成器”：
  • MD5选择前缀算法
    • 已知前缀x1,x2的情况下构造一对后缀y1,y2使得M(x1y1)=M(x2y2)
    • 注意的两点：
      • 其实还是一种寻找强碰撞
      • 复杂度比王小云教授的直接构造高的多
        • 参考资料
        • 参考资料
        • 关于选择前缀算法的过程

• 验证软件完整性时可能出现的问题
  • 文件不完整的情况
    • 感染病毒
    • 植入木马/后门/人为篡改
    • 传输故障
  • 可能出现的问题
    • 如果有第三方在验证软件完整性时截取软件代码，使用快速MD5碰撞生成器，在短时间内伪造一份相同的MD5，并恶意篡改软件，那么安全性将会大大下降
    • 当软件过大时，在验证过程中所需的时间也会大大增加，对于第三方而言，攻击的成功概率也会增加
    • 网站链接中的Vulnerability analysis也给出了一些问题分析
      • On the other hand, there is the viewpoint of the relying party, i.e. the user downloading hashed or signed code who needs some guarantee that this software can be trusted. This relying party can not be sure anymore that the published hash value or the digital signature is valid for only the executable file he downloaded. There might very well be a sibling file with the same hash value or digital signature, while only one of these siblings went through the proper hashing or signing procedure. Especially when the software integrity verification takes place under the hood, with the user not knowing that the operating system or some hidden application is silently verifying digital signatures on software to be installed, the user may be more easily lured into installing malware.

      • Note that it is not necessary for an attacker to build both executables from source code. It is perfectly well possible to take as the first file any executable from any source, and as the second file produce a second executable as malware. Then a byte block to be appended to both files can be found such that the resulting files have the same MD5 hash value. If an attacker can then get the first file to be signed, e.g. by the original software vendor, this signature will also be valid for the attacker-constructed malware.

      • 即使用户能保证下载的文件的网站是能信任的，网站也不能保证用户下载到本地的文件是正确的。特别是当软件完整性验证发生在电脑主机下时，当用户不知道操作系统或某些隐藏的应用程序在安装软件时默默地验证数字签名时，用户可能更容易被诱骗安装恶意软件。（我猜应该是类似于360这种流氓软件的行为？）
      • 攻击者也不需要从源代码中构造出两个文件，完全可以将第一个文件作为任何源的任何可执行文件，并且作为第二个文件生成第二个可执行文件作为恶意软件。然后，可以找到要附加到两个文件的字节块，使得得到的文件具有相同的MD5哈希值。攻击者只需要获取第一个文件就可以了。

---

备注：

其实很多文章我都没有看懂，但是时间有限，博客可能之后会继续更改。

关于所有的我参考的网站、博客及论文，我都在博客中给出了。