澳门新葡萄京所有网站 1

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

今日有消息报道荷兰阿姆斯特(CWI)研究所和谷歌研究人员发布了世界上第一例公开的SHA-1哈希碰撞实例。

近期,Google和荷兰国家数学和计算机中心(Centrum Wiskunde &
Informatica,CWI)的研究人员完成了针对第一例SHA-1的碰撞攻击,创造了两个hash值完全相同但内容截然不同的文件。然而,在真实的信息安全世界中,这种攻击又会怎样对个人和组织机构造成何种威胁呢?

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

在现实世界里,哈希碰撞事件也确有发生。如利用 MD5 碰撞伪造合法 CA
证书,进而攻击 HTTPS 安全体系。

对SHA-1算法不安全的担心由来已早。在2015年荷兰国家数学和计算中心和新加坡南洋理工大学研究员联合发表的论文中,描述了SHA-1碰撞攻击的各种理论性可能。同时,在RSA
2016的密码学家研讨会上,该篇论文得到了很多关注,参会的著名密码学专家Adi
Shamir也预测,真实的SHA-1碰撞攻击在未来几个月将会成功实现。在此次会议之后,一些安全公司正式对外宣布SHA-1机制可能存在缺陷;与此同时,因为没有真实的攻击成功案例,这种攻击也带来了诸多质疑。

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

消息称,CWI 研究所的 Marc Stevens 是此次攻击的关键人物,2016
年找到了SHA-1算法内部的核心组件 internal compression function
的一个碰撞实例,开始攻克 SHA-1 完全实际碰撞攻击。近日在 Google
的强大资源支持下,终将 SHA-1 算法的碰撞实例展示出来。

澳门新葡萄京所有网站 2

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

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

此次攻击使用了强大计算资源,Google Security Blog 公布数据:

但为了防止任何理论攻击可能,去年开始,一些安全公司开始反对继续使用SHA-1算法。尽管谷歌、Facebook、微软和Mozilla等公司已采取措施替换SHA-1算法,但哈希函数仍在广泛使用。当Google和CWI的实验成功之后,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所示,数字签名进行身份认证,并保证完整性和不可否认性。

澳门新葡萄京所有网站 3

SHA-1

  • Nine quintillion (9,223,372,036,854,775,808) SHA1 computations in
    total

  • 6,500 years of CPU computation to complete the attack first phase

  • 110 years of GPU computation to complete the second phase

影响分析

几年前,针对MD5算法存在“构造前缀碰撞攻击”(chosen-prefix
collisions),而真实案例中,Flame(火焰)病毒就使用了此种攻击方法。SHA-1碰撞攻击实现后,恶意软件开发者将会创造什么样的病毒,值得想像。

在此,我们就针对一些利用微软签名校验的恶意程序,结合SHA-1碰撞作一些攻击可能的探讨。为了说明SHA-1碰撞攻击的现实威胁,我们找到了一例很有趣的例子:微软内核模式代码签名策略,攻击针对目标是加载的内核模式驱动程序签名认证,以下是包括WIN
10在内的该类签名规范和要求:

澳门新葡萄京所有网站 4

我们可以看到,其中列出的哈希机制就包括SHA-1,所以,毫无疑问,SHA-1碰撞攻击将会产生驱动签名滥用情况,为恶意内核代码程序的利用传播敞开大门。事实上,SHA-1签名校验的驱动程序并不少见,以下就是一些我们发现的实例:

澳门新葡萄京所有网站 5

澳门新葡萄京所有网站 6

在Win
10系统中,这类存在“风险隐患”的驱动程序是不是就非常少呢?但由于存在很多第三方驱动,所以,情况让你超乎想像。虽然微软在最新的系统适配产品中明确反对SHA-1机制认证程序,但很多第三方驱动依然大范围存在此种情况。另外,在一些之前的操作系统版本(Win
7Win 8)中,还存在着大量且多年未更新的此类驱动。例如:

澳门新葡萄京所有网站 7

澳门新葡萄京所有网站 8

澳门新葡萄京所有网站 9

澳门新葡萄京所有网站 10

从这里就可以看出,SHA-1将会成为很多组织机构和相关系统的一个心头大患。受影响的系统和服务包括:数字证书签名、邮件、PGP/GPG
签名、软件发布签名、备份系统、冗余热备份系统、Git……等等,除了网络安全之外,影响将会波及很多使用传统操作系统的大型组织机构。这种很多第三方软件公司持续使用的,运行机制本身就存在的问题,将会成为一个严重的信息安全问题。要保证安全,只有从核心和本质上进行处理,但对很多软件公司来说,这又会成为一个“牵一发动全身”的棘手问题。

深入研究之后,我们甚至发现一些固件和硬件也受到此问题影响。例如,普遍使用的仅支持SHA-1验证的TPM
1.2芯片,SHA-1碰撞攻击将会直接对一些使用SHA-1算法的固件可信启动机制造成影响。在这方面,微软在Win10系统中已经作了一些限制,如其加密方式不支持TPM1.2芯片。

SHA-1碰撞攻击的恶梦才刚刚开始,我们应该尽快结束使用SHA-1的时代。谷歌将在接下来的90天内公布SHA-1碰撞攻击的测试工具。

3 SHA-1

规模程度看实验配图:

SHA-1碰撞会被用到一些野生攻击中吗?

证据表明,攻击者必须在拥有原始文件和已知哈希的情况下才能完成碰撞攻击,另外,由于攻击利用了定向编辑,不是每次编辑都会有效。换句话说,即使是破解了SSH或TLS的认证证书,也都不可能实现,需要对原始文件进行一些非常细微的定向更改才能保证碰撞攻击成功。

虽然在某种程度上来说,更改签名验证很容易实现,但如果要进行伪装式的SHA-1碰撞攻击,想要让受害者迷惑,完全对看不出马脚,这就需要对利用文档进行破坏性的改造,而不只是通常性修改。后续可能会有一些针对SHA-1碰撞攻击的检测研究。

总体上来说,要实现该项攻击需要很大的代价成本。如果攻击者使用类似于比特币挖矿的专业装备和技能,攻击可能将会变得更加便捷。Google和CWI声称,该攻击实现需要大量的CPU和GPU计算,同时还需高效的分布式操作,攻击第一阶段攻击是在Google的异质CPU集群上进行的,并扩展至8个物理地址;第二阶段攻击代价更高,是在Google的K20、K40和K80异质GPU集群上进行的。经相关研究人员计算得出,使用亚马逊云服务AWS进行第二阶段的攻击,耗资约56万美元。但是,若攻击者足够耐心并利用现场参考案例,成本可降至11万美元。

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年以后已经不被大多数的加密场景所接受。

澳门新葡萄京所有网站 11

如何修复和预防这种攻击呢?

作为安全和开发团队来说,最好的方法就是使用SHA-256等更复杂的算法,或使用两个独立的加密算法。当然,对于攻击检测来说,仍然可以使用Google发布的开源检测代码。

参考来源:Cylance

稿源:freebuf.com

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个人生日都不相同的概率为$$prod_{i=1}^{23}(1-frac{1}{365-i+1})$$,上述事件同时发生时,23个人生日才会各不相同。因此23个人中存在2个人生日相同的概率为:
$$1−frac{365!}{(365-23)!365^{23}} ≈ 50%
$$。所以在寻找哈希碰撞时,选择大约$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 所示,

澳门新葡萄京所有网站 12

SHAttered1

第二个 PDF 文件打开如图 3 所示,

澳门新葡萄京所有网站 13

SHAttered2

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

澳门新葡萄京所有网站 14

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
这些现在安全的的哈希函数。
当然本文只是一个简单的探究,还有好多关于哈希函数的其他知识尚未涉及到。