专栏名称: 中科院物理所
物理所科研动态和综合新闻;物理学前沿和科学传播。
目录
相关文章推荐
环球物理  ·  【物理笔记】功和能精美手写笔记,值得收藏! ·  17 小时前  
环球物理  ·  【科技前沿】全球未来最具革命性的六大技术 ·  17 小时前  
中科院物理所  ·  恒星物理的发展 ·  23 小时前  
中科院物理所  ·  好消息:火星上又发现水了!坏消息… ·  23 小时前  
51好读  ›  专栏  ›  中科院物理所

Google 破解 SHA-1算法,到底为啥?

中科院物理所  · 公众号  · 物理  · 2017-03-02 10:01

正文

前几天,

Google 破解 SHA-1 算法的新闻刷了我的朋友圈。


其实破解二字不太准确,

应该是

公布了一个攻破SHA-1算法的实例。


对此新闻,

我看到了两种不同的评论


A: 哇好牛X呀,居然破解了加密算法,世界好危险,我要不要回火星?


B: 谷歌这次只是花费了大量的计算资源,验证了一下破解算法,没啥可牛逼的。我几年前就知道 SHA-1 算法不安全了。。




本着求真的精神,

今天就来(xia)聊聊:


一、谷歌此次成果到底意义何在?

二、谷歌为啥要搞出这么大动静?


---


先还是简单科普一下哈希算法。


我们知道,每个人的指纹都不一样,

所以能用指纹来验证人的真伪。

(孙猴子除外)




在计算机系统中,

每个不同的文件内容也有自己的指纹——哈希值


用来计算哈希值的方法有很多,

比如 SHA-1、SHA-2、MD5等等

它们统称“哈希算法”




美国有部著名的电影叫 乱世佳人

用 SHA-1算出的哈希值是 :

5C9CD8EEECE37D8A66206D4652132C00B4D9F8F4


如果你下载的 乱世佳人.avi

哈希值不一样,

很可能你会被忽悠下载了葫芦娃全集



简单来说,哈希值就是数字世界的指纹。


那么问题来了,

虽然概率极低,但是

两个人的指纹还是有可能完全相同

两个文件的哈希值也有可能相同


也就是说,

只要我找到和马云爸爸指纹相同的人

就有可能盗走马云爸爸的财产

只要构造一个和电影的哈希值相同的视频文件

就能成功忽悠你下载葫芦娃全集。



其实谷歌这次就干了这么一件事。

他们成功构造了两个不同的PDF文件,

SHA-1 哈希值完全相同



那么这意味着什么呢?

谷歌官方是这么说的:


我们从应用角度破解了SHA-1。

这一工业界应用的密码学哈希函数标准被用于数字签名、文件完整性验证中,并在多个领域保护着人们的数字财产,这些数字财产包括信用卡交易、电子文档、开源软件仓库、软件更新等。

在实际中,我们可以构造两个SHA-1结果相同的PDF文件。这使得第二个文件SHA-1后的数字签名可以通过第一个文件SHA-1后数字签名的验证。

举例来说,可以构造两个SHA-1结果相同的PDF租赁协议文件,协议文件中标注的租金不同,但高租金文件的SHA-1后签名结果与低租金文件的SHA-1后签名结果一样。这样,可以让租赁方在低租金文件上签字,再用高租金文件替换,达到伪造租赁协议文件的目的。



之所以有的朋友觉得谷歌这个结果

不牛X,不令人震精


是因为 SHA-1 很早就从理论上被证明能破解了

只是计算量极大,成本比较高。


2005年,

我国密码学专家王小云教授

联手姚期智夫妇

提出了一种破解方法

将破解SHA-1 的时间从2^69步到2^63步

让中国密码界闪耀在世界舞台


【王小云】


顺便说一下,

上文所说的姚期智就是前不久和杨振宁一起放弃外籍转为中科院院士的那个 图灵奖得主 姚期智。


【姚期智】


那次的研究结果,

让国家标准技术局 NIST 不得不着手选择新SHA-2系列哈希函数。


但由于破解的成本太高

SHA-1 依然在广泛应用


之后,

学者们一直努力寻找更高效的破解方法。


2013年,

一个叫Stevens的小伙将破解计算量降低到


2016年,

他再一次将计算量降低到

此次谷歌就借鉴了他的破解方法


利用这种方法,

100个GPU大约需要计算一年就能破解

大概得花个几十万

成本确实不低,

但对于国家机构、高级黑客组织来说

简直就是毛毛雨



对于这次成果的意义,

我认为更多的还是敲响警钟


就好比人们知道弱口令不安全

但只有当一个个盗号事件发生在他们身边







请到「今天看啥」查看全文