关于密码学:密码学系列之碰撞抵御和碰撞攻击collision-attack

hash 是密码学和平时的程序中常常会用到的一个性能，如果 hash 算法设计的不好，会产生 hash 碰撞，甚至产生碰撞攻打。

明天和大家具体探讨一下碰撞攻打。

所谓碰撞攻打指的是对于同一个 hash 函数来说，两个不同的 input 通过 hash 计算失去了同样的 hash 值。用公式来说就是：

hash(m1) = hash(m2)

这个攻打有什么作用呢？

举个例子，通常咱们通过网络下载应用程序或者软件，除了下载链接之外，还会提供一个 MD5 的校验码。这个校验码就是用来校验下载的软件是不是官网提供的软件。

MD5 算法也是一种 hash 算法，如果歹意用户能够结构一个和原始软件一样 MD5 的软件的话，就很可能施行碰撞攻打。

还有一种状况用在数字签名中。在数字签名中，因为效率的起因，如果文章特地大的状况下，通常会先取文章的 hash 值，而后对这个 hash 进行签名。

所以这外面有两个能够被攻打的中央，一个就是 hash 碰撞，一个就是签名算法。

举个例子，比如说师妃暄给徐子陵写了一封信 A，说是凌晨的时候在竹林有事件相告，然而没有间接交给徐子陵而是给了他的好兄弟寇仲，寇仲思考到夜晚太危险了，不想让他的好兄弟冒险，于是伪造了这封信 A，结构了和原来的信 A 同样 hash 值的信 B，并附带了师妃暄的签名。

徐子陵收到了信 B 和签名，通过验证发现的确是师妃暄写的，于是就没有去赴约。

碰撞攻打取决于 hash 算法的强度，像是 MD5 和 SHA- 1 这些 hash 算法曾经被证实是不平安的，能够在很快的工夫内被攻破。

除了后面传统的碰撞攻打之外，还有一种叫做 Chosen-prefix collision attack 抉择前缀抵触攻打。

攻击者能够抉择两个不同的前缀 p1 和 p2, 而后附在不同的字符串 m1,m2 后面，那么有：

 hash(p1 ∥ m1) = hash(p2 ∥ m2)    其中 ∥ 示意连接符

咱们看一个在 SHA- 1 中由盖坦. 勒伦（Gatan Leurent）和托马. 佩林（Thomas Peyrin）发现的一个攻打的例子，这是两个别离带有前缀 99040d047fe81780012000 和 99030d047fe81780011800 的例子。

两个音讯内容能够从上面下载：

messageA: sha-mbles.github.io/messageA

messageB:sha-mbles.github.io/messageB

咱们能够看下音讯的截图：

这两个音讯通过 sha1sum 运算，能够失去雷同的 hash 值。

sha1sum messageA：8ac60ba76f1999a1ab70223f225aefdc78d4ddc0

sha1sum messageB：8ac60ba76f1999a1ab70223f225aefdc78d4ddc0

java 中有一个常常会用到的类叫做 hashMap，在 JDK7 之前，HashMap 在存储数据的时候如果遇到了 hash 抵触，则会将数据以链表的模式插入到这个 hash 节点的最初。

这样会有什么毛病呢？

那么就是如果有歹意攻击者，始终向 hashMap 中插入同样 hash 值的 key 对象，那么 hashMap 实际上就会进化成为一个链表。

这样会大大影响 hashMap 的查问效率。如果数据特地大的话，可能就会导致 DDOS 攻打。

这个问题的根本原因就是 java 中 hashMap 中的 hash 计算太过简略，很容易就可能找到雷同 hash 值的 key。

实际上在 2011 年 tomcat 还公布了一个对于这个问题的破绽解决方案。

尽管这是 java 的问题，然而最初的锅还是由 tomcat 来背。tomcat 的做法就是限度 maxPostSize，从最大的 20M 改成了 10K，这样能够无效的缩小申请中的 item 大小。

当然，在 JDK8 中，原来的链表构造曾经被改成了红黑树结构，置信也是为了防止这种 DDOS hash 攻打的计划。

和碰撞攻打相似的还有一个攻打叫做原像攻打。

原像攻打的抵挡须要满足两个条件，第一个条件是给定一个 hash 值 y，很难找到一个 x，使得 hash（x）=y。

第二个条件就是给定一个 x，很难找到一个 y，使得 hash(x) = hash(y)。

很显著，碰撞攻打的抵挡肯定满足第二个条件，然而不肯定满足第一个条件。

本文已收录于 http://www.flydean.com/collision-attack/

最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！

欢送关注我的公众号:「程序那些事」, 懂技术，更懂你！

简介