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

题目内容要求：(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/

一、散列函数的具体应用

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

    对于HASH函数的使用，有很多误区，在此特列举其使用场景以及常见的使用误区。但是不论如何，我们都该记得HASH函数的特点：固定长度的输出，单向不可逆，碰撞约束。

    正确的应用场景：
    1，数据校验
    HASH函数有类似数据冗余校验类似的功能，但是它比简单的冗余校验碰撞的概率要小得多，顾而在现在密码学中总是用HASH来做关键数据的验证。
    2，单向性的运用
    利用HASH函数的这个特点，我们能够实现口令，密码等安全数据的安全存储。密码等很多关键数据我们需要在数据库中存储，但是在实际运用的过程中，只是作比较操作，顾而我们可以比较HASH结果。这一点相信在银行等系统中有所运用。
    3，碰撞约束以及有限固定摘要长度
    数字签名正是运用了这些特点来提高效率的。我们知道非对称加密算法速度较低，通过HASH处理我们可以使其仅仅作用于HASH摘要上，从而提高效率。
    4，可以运用HASH到随机数的生成和密码，salt值等的衍生中
    因为HASH算法能够最大限度的保证其唯一性，故而可以运用到关键数据的衍生中（从一个随机的种子数产生，并且不暴露种子本身秘密）。

二、散列函数的安全性以及目前安全散列函数的发展

    单向散列函数或者安全散列函数之所以重要，不仅在于消息认证(消息摘要，数据指纹)，还有数字签名（加强版的消息认证）和验证数据的完整性。常见的单向散列函数有MD5和SHA。散列函数的两个特点：1.输出固定长度的 2. 不可逆转

    生日攻击：利用“两个集合相交”问题的原理生成散列函数碰撞，达到目的的攻击称为生日攻击，也称为平方根攻击。生日攻击方法没有利用Hash函数的结构和任何代数弱性质，它只依赖于消息摘要的长度，即Hash值的长度。

    MD5：用于确保信息传输完整一致。是计算机广泛使用的杂凑算法之一，主流编程语言普遍已有MD5实现。将数据（如汉字）运算为另一固定长度值，是杂凑算法的基础原理，MD5的前身有MD2、MD3和MD4。

简单散列函数

    所有的散列函数都按照下面的基本操作，把输入（消息、文件等）看成n比特块的序列。对输入用迭代方法处理一块，生成n比特的散列函数。

        一种最简单散列函数的每一个数据块都按照比特异或：

                C_i = b_i1⊕ b_i2⊕ … ⊕ b_im

        其中：

                Ci为散列码的第i比特，1<=  i <=n;

                m为输入中n比特数据块的数目；

                b_ij为第j块的第i比特；

                ⊕为异或操作

        下图说明了这个操作：

    因为没一列都有相同的可能性。所以这个函数的有效性差。

SHA安全散列函数

    SHA-1：该算法的原始规范于1993年作为美国政府标准机构NIST（国家标准与技术研究院）的安全散列标准FIPS PUB 180发布。现在这个版本通常被称为SHA-0。它在出版后不久被国家安全局撤回，并被1995年发布的FIPS PUB 180-1修订版所取代，通常称为SHA-1。SHA-1与SHA-0的不同之处仅在于其压缩功能的消息调度中的单个按位旋转; 根据美国国家安全局的说法，这项工作已经完成，以纠正原有算法中的一个缺陷，从而降低了其密码安全性。然而，国家安全局并没有提供任何进一步的解释或确定哪些缺陷被纠正。随后在SHA-0和SHA-1中报告了弱点。SHA-1在许多安全协议中广为使用，包括TLS和SSL、PGP、SSH、S/MIME和IPsec，曾被视为是MD5（更早之前被广为使用的散列函数）的后继者。

    近些年，应用最广泛的散列函数是SHA。由于其他每一种被广泛应用的散列函数都已经被证实存在这密码分析学中的缺陷，接着到2005年，SHA或许仅存的安全散列算法。SHA由美国国家标准与技术研究院（NIST）开发。

    ● 1995年公布SHA-1
    ● 2002年，公布了SHA-2(SHA-256、SHA-384、SHA-512)
    ● 2008年，增加了SHA-224

更详细的如下图所示：

安全散列函数的发展

    有两种方法可以攻击安全散列函数：密码分析法和暴力攻击法。散列函数抵抗暴力攻击的强度完全依赖于算法生成的散列码长度。Van Oorschot和Wiener曾经提出，花费1000万美元涉及一个被专门用来搜索MD5算法碰撞的机器，则平均24天内就可以找到一个碰撞。2004年8月中国密码学家王小云教授等首次公布了提出一种寻找MD5碰撞的新方法，目前利用该方法用普通微机几分钟内即可找到MD5的碰撞，MD5已经被彻底攻破。

三、MD5算法在验证软件完整性时可能出现的问题

    MD5算法具有以下特点：

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

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

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

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

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

    MD5的用处主要有一下几个场景：

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

　　（2）不可逆的加密： 像Unix系统中，用户用用户名和密码登陆系统，由于系统中存放的是用户名和密码组合MD5校验值，所以登陆框将会把用户名和密码进行MD5算法从而生成用户名和密码组合的MD5校验值，系统由此可以知道能不能登陆成功。

    选择前缀碰撞:将碰撞合并到一对文件中时，除了构成碰撞的相对较小的随机查找字节块之外，构造碰撞的原始方法要求文件完全相等。前缀冲突只有在碰撞后文件应该完全相等的要求。之前发现碰撞的两个文件的碰撞可以是任何事情：我们的选择前缀碰撞查找方法总是会产生一个碰撞，该碰撞可以合并到两个文件中，而不管在碰撞之前存在什么数据。

    可能出现的问题：如果有第三方在验证软件完整性时截取软件代码，使用快速MD5碰撞生成器，在短时间内伪造一份相同的MD5，并恶意篡改软件，那么安全性将会大大下降。当软件过大时，在验证过程中所需的时间也会大大增加，对于第三方而言，攻击的成功概率也会增加。无法定位给定的散列值，并生成一个（有意义的）输入位串哈希到给定的值。在加密术语中：我们的攻击是对抗碰撞的攻击，而不是对原像或第二原像的抵抗。这意味着，攻击者必须专门准备两个相互冲突的文件，然后才能在下载网站上发布或通过代码签名方案进行签名。已知散列的现有文件尚未用这种方法准备好，这些文件不容易受到攻击。 

    然而，我们可以很容易地做的是在几个额外的字节上进行强力搜索，例如让散列值的前三个和最后三个字节与给定目标匹配。这已经可能引入额外的漏洞，因为很多人（包括我们中的至少两个人）通常在检查散列值时仅查看第一个和最后三个字节。 

    为了滥用软件完整性保护或代码签名方案中的选择前缀冲突，攻击者应能够在文件被散列和/或签名之前对其进行操作。这可能意味着攻击者需要内部人员访问运行可信软件完整性保护或代码签名过程的一方。具有此类访问权限的攻击者无论如何都可能会造成更多伤害，而无需选择前缀冲突，从而获得恶意软件上的“官方”数字签名。