密码学系列之：碰撞抵御和碰撞攻击collisionattack
密码学系列之：碰撞抵御和碰撞攻击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中的hash攻击
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攻击的⽅案。
原像攻击Preimage attack
和碰撞攻击类似的还有⼀个攻击叫做原像攻击。
原像攻击的抵御需要满⾜两个条件，第⼀个条件是给定⼀个hash值y，很难到⼀个x，使得hash（x）=y。
第⼆个条件就是给定⼀个x，很难到⼀个y，使得hash(x) = hash(y)。
很明显，碰撞攻击的抵御⼀定满⾜第⼆个条件，但是不⼀定满⾜第⼀个条件。
最通俗的解读，最深刻的⼲货，最简洁的教程，众多你不知道的⼩技巧等你来发现！
欢迎关注我的:「程序那些事」，懂技术，更懂你！

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。