简介

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/
最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！
欢送关注我的公众号:「程序那些事」,懂技术，更懂你！