SHA-1的简单探究

上学期选修了一门信息安全讨论,期末的时候是写一个关于信息安全方面的报告,找本科毕设精简一下交上去,被老师发现了,开学来了要重新写,哭,于是遂有下文。

摘 要: Google对于SHA-1的破解是一个重大的突破,从应用层上验证了SHA-1的不安全 性。本文详细的介绍了哈希函数及 SHA-1 的发展和应用,其中着重介绍了针对 SHA-1 的攻 击的历史发展。最后我们介绍了在 SHA-1 之后的一些哈希函数的安全性和发展现状。

关键词:SHA-1,哈希函数,碰撞

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 被业内广泛用于数字签名、文件 完整性验证、以及保护广泛的数字资产(包括信用卡交易、电子文档、开源软件资源库与 软件更新等)的加密标准。

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

2 哈希函数

哈希函数(Hash Function)又称散列函数、散列算法。是一种将任意长度的数据映射到有限长度的域上。即对一串数据进行杂糅,输出一段固定长度的数据 h,这段固定长度的数 据称为指纹。

哈希函数需要满足一定的条件,首先是要满足确定性,哈希函数算法是确定性的算法,算法执行过程不引入任何随机变量。即相同消息的哈希结果一定相同。如果相同消息产生的 结果不同,那这种算法也就不是哈希函数。高效性,给定任意一个消息,可以快速计算Hash(m)。哈希函数一个特点就是计算速度快,这样就可以把长的消息转为短的消息,然后供其他计算速度慢的算法去计算,用哈希函数做一个预处理。目标抗碰撞性,给定任意一个消息$m_0$ ,很难找到另一个消息$m_1$ ,使得 Hash($m_0$)=Hash($m_1$)。这也是在破解的时候,是基于目标抗碰撞性的。如果给定任意一个消息$m_0$ ,都能找到另外一个消息与它哈希值相同,
那么就可以称完全破解了这种算法。广义碰撞性,很难找到两个消息$m_0≠m_1$,使得 Hash($m_0$)= Hash($m_1$)。如果第四个条件不满足,则这个哈希函数是不安全的。如果第三个条件完全不满足,那么此哈希函数已经彻底不安全,应该直接弃用。哈希函数要具有抗碰撞的能力以及抗篡改能力,对于一个数据块,哪怕只是改动其一个比特位,其hash值的改动也会非常大。

哈希函数在信息安全方面的一个作用就是进行文件校验,相比于我们熟悉的奇偶校验和CRC校验,使用哈希函数的校验具有抗数据篡改的能力,防止对数据的恶意破坏。在文件 传送后,将得到的目标文件计算的哈希值和源文件的哈希值进行对比,由着两者的一致性,可以保证两个文件的每一个码元都是相同的。可以校验文件传输过程中是否出现错误,以及更重要的是可以保证文件在传输过程中未被恶意破坏。比如我们在上Oracle官网上下载JDK的时候,就会有checksum。供用户下载后进行验证,保证下载JDK的正确性。还有在Linux系统安装软件包的时候,也可以进行校验,以保证安装的软件包是来自于官方的源,不被破坏者植入恶意代码。

哈希函数的另一个作用就是数字签名,由于非对称算法的运算速度较慢,所以在数字签名协议中也包含了哈希函数,在这种签名协议中,双发必须事先协商好双方都支持的 Hash 函数和签名算法。签名方先对数据文件使用哈希函数计算散列值,然后对较短的哈希值结果用非对称算法进行数字签名操作,接受方先对数据文件进行计算哈希值,然后再用非对称算法验证数字签名。具体过程如图1所示,数字签名进行身份认证,并保证完整性和不可否认性。

SHA-1

3 SHA-1

3.1 SHA-1简介

SHA(Secure Hash Algorithm)安全散列算法是一个密码散列家族,由美国国家安全局(NSA)所设计,也是一种哈希函数。是FIPS所认证的安全散列算法。能计算出一个数字消息所对应到的,长度固定的字符串(又称消息摘要)的算法。输入的消息不同,它们对应到不同字符串的概率很高。

SHA-1发布于1995年,与前身MD5相比,SHA-1的输出长度更长,(MD5输出长度为128bit,SHA-1输出长度为160bit),曾被视为是MD5(更早以前被广泛使用的散列函数)的后继者。在许多安全协议中广为使用,包括TLS和SSL,PGP、SSH、S/MIME和IPsec。但SHA-1的安全性在2000年以后已经不被大多数的加密场景所接受。

3.2 SHA-1算法

SHA-1 可以对不超过$2^{64}$比特的消息进行计算,输入以512位数据块为单位处理,产生160比特的消息摘要作为输出。该算法的处理流程主要分为5个步骤:

步骤 1:对输入的数据进行填充,是的数据位长度对512求余的结果为448。填充比特 串的最高位补一个 1,其余位补0。附加填充总是要进行的,即使消息的长度满足所要求的长度。

步骤 2:将64比特加在报文后表示报文的原始长度,是报文长度为512比特的倍数。

步骤 3:一个160位MD缓存用以保存中间和最终的散列函数的结果。它可以表示为32位寄存器(A,B,C,D,E)。初始化为 A=67452301,B=EFCDAB89,C=98BADCFE, D=10325476,E=C3D2E1F0。前四个是与MD5相同的,但存储为big-endian format,即将高 序字节存储在起始地址。

步骤 4: 以512比特(16个字)分组处理消息。此算法的核心就是称为压缩算法(compression function)的模块。这个模块包括4次循环,每次循环又包含20 个处理步骤。 4次循环具有相似的结构,但每次循环使用不同的基本逻辑函数,称为 f1,f2,f3,f4。

步骤 5:全部L个512位数据块处理完毕后,输出160位消息摘要。

3.3 SHA-1碰撞

1990 年 MD4 算法提出,但是很快发现了严重的安全问题,在1992年被MD5算法取代,MD5算法在之后的十几年内被软件行业广泛使用,但之后也被破解。随后开始使用SHA-1。

关于寻找哈希函数碰撞的难度和一般方法,SHA-1输出长度为160bit。如果SHA-1本身没有漏洞,而攻击者想要找到一组碰撞的话,最显然的方法是选取$2^{160}$ 组不同的数据,依次计算它们的哈希结果。根据著名的抽屉原理,必然会出现一组数据,使得其哈希结果相同。 此攻击方法需要调用$2^{160}$次 SHA-1,即计算量级大约为$2^{160}$。这样的计算代价是巨大的,实际操作根本不可能。

上面的方法可以通过放宽条件,用概率的方法寻找,能降低一定的计算量。 一个屋子里必须有366个人(一年有365天,不考虑闰年的情况)才能保证有两个人的生日是同一天。
但假设现在有23个人,根据概率论:第2个人和第1个人生日不同概率为1-$\frac{1}{365}$,第3个人和前两个人生日不同的概率为$(1−\frac{1}{365})(1−\frac{1}{364})$ ,第4个人和前三个人生日都不相同的概率为$(1−\frac{1}{365})(1−\frac{1}{364})(1−\frac{1}{363})$,依次类推,第23个人和前22个人生日都不相同的概率为,上述事件同时发生时,23个人生日才会各不相同。因此23个人中存在2个人生日相同的概率为:

。所以在寻找哈希碰撞时,选择大约$\sqrt{2^{160}}=2^{80}$组不同的数据并计算哈希结果,则有50%的概率有2个哈希结果相同。此方法的数量级远优于前一种方法,但是引入的代价是成功率变为50%。密码学上认为,如果能找到一种方法,能在计算时间小于$2^{80}的情况下,有超过生日攻击概率下找到一组碰撞,则认为这个哈希函数就不安全了。

SHA-1自提出后,学者们一直认为它是安全的,并没有找到计算时间小于$2^{80}$攻击方法。 我国著名密码学家王小云教授所在的团队提出了一种寻找SHA-1碰撞的,相对快速的攻击方法。此攻击方法的计算量级为269,这标志着SHA-1存在漏洞。NIST不得不选择新的哈希函数,因此才有了SHA-256、SHA-384、SHA-512等。

王小云教授的开创性工作让进一步破解SHA-1成为了可能。然而,王小云教授的方法 仅可破解SHA-1的广义抗碰撞性,且计算时间相对较长。在计算发杂度上也很高,具体操 作上可行度并不是很高。这表明SHA-1在一段时间内还是可以使用的。后来Stevens提出了 一种攻击方法,可以在$2^{61}$计算量级内找到一组哈希碰撞。

上述方法都是使用纯CPU计算的方法。Stevens等人在2016年提出了新的攻击方法, 把显卡(即GPU)引入破解工作,使用大规模并行处理,进行并行计算,则计算量级会进一步降低到$2^{57.5}$。这样使得具体的破解成为了可能,本次Google的破解工作也使用了类似的方法。

3.4 Google 的破解工作

Google 发布了两个 PDF 文件,第一个 PDF 文件打开打开如图 2 所示,
SHAttered1
第二个 PDF 文件打开如图 3 所示,
SHAttered2
这两份PDF文件经过SHA-1 哈希后的值是一样的,可以证明针对SHA-1找到了一组碰撞。但是这PDF的内容还是有意义的。可见Google的工作不仅仅是找到一组碰撞那么简单。 Google的官方网站的后续说明也证明了这一点。Google让用户上传任意文件,来检测文件本身是否可能被这种攻击威胁。可见这对于哈希函数本身虽不能算彻底的破解,但是基本以宣 告SHA-1 的死刑。如果你想查看自己的文件是否存在碰撞,可以将文件上传 到 https://shattered.io/ 这个网站。比如我把本文生成的PDF上传,得到的检测结果如图 4 所示, 从检测结果可以知道,本文生成的文档还是安全的。
upload

4 一些其他的SHA

在SHA-0和 SHA-1 之后,NSA 又设计发布了 SHA-2 和 SHA-3,其中 SHA-2 包括SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224和SHA-512/256。后面跟的数字是哈希后的 bit 位数。至今尚未出现对 SHA-2 有效的攻击,但是由于其算法与 SHA-1 相似。 需要一个其他替代的散列算法,于是 SHA-3 出现了,SHA-3 并不是要替换 SHA-2,而是算 法不同,更加的安全。
现在很多网络上很多地方还在使用SHA-1,比如我们现在我们打开网站好多都是https。 但是一些一些网站使用的 https 证书是用 SHA-1 进行哈希计算的,这样是很不安全的。现在 很有必须更换为 SHA-2 等安全性算法,当然国内还有好多网站没有实现 https,这也需要尽 快加上 https,使用户访问网站更加安全。

5 结论

本文根据最近Google对SHA-1的破解,了解了关于哈希函数的定义以及它的一些应用发展。之后着重讨论了SHA-1的算法及破解的历程,以及Google这次破解对信息安全一些 领域的影响。最后介绍了其他的哈希函数 SHA-2 和 SHA-3 这些现在安全的的哈希函数。
当然本文只是一个简单的探究,还有好多关于哈希函数的其他知识尚未涉及到。

您的支持将鼓励我继续创作!