簡介

hash是密碼學(xué)和平時的程序中經(jīng)常會用到的一個功能，如果hash算法設(shè)計的不好，會產(chǎn)生hash碰撞，甚至產(chǎn)生碰撞攻擊。

今天和大家詳細(xì)探討一下碰撞攻擊。

什么是碰撞攻擊

所謂碰撞攻擊指的是對于同一個hash函數(shù)來說，兩個不同的input通過hash計算得到了同樣的hash值。用公式來說就是：

hash(m1) = hash(m2)

這個攻擊有什么作用呢？

舉個例子，通常我們通過網(wǎng)絡(luò)下載應(yīng)用程序或者軟件，除了下載鏈接之外，還會提供一個MD5的校驗(yàn)碼。這個校驗(yàn)碼就是用來校驗(yàn)下載的軟件是不是官方提供的軟件。

MD5算法也是一種hash算法，如果惡意用戶可以構(gòu)造一個和原始軟件一樣MD5的軟件的話，就很可能實(shí)施碰撞攻擊。

還有一種情況用在數(shù)字簽名中。在數(shù)字簽名中，因?yàn)樾实脑?#xff0c;如果文章特別大的情況下，通常會先取文章的hash值，然后對這個hash進(jìn)行簽名。

所以這里面有兩個可以被攻擊的地方，一個就是hash碰撞，一個就是簽名算法。

舉個例子，比如說師妃暄給徐子陵寫了一封信A，說是凌晨的時候在竹林有事情相告，但是沒有直接交給徐子陵而是給了他的好兄弟寇仲，寇仲考慮到夜晚太危險了，不想讓他的好兄弟冒險，于是偽造了這封信A，構(gòu)造了和原來的信A同樣hash值的信B，并附帶了師妃暄的簽名。

徐子陵收到了信B和簽名，經(jīng)過驗(yàn)證發(fā)現(xiàn)確實(shí)是師妃暄寫的，于是就沒有去赴約。

碰撞攻擊取決于hash算法的強(qiáng)度，像是MD5和SHA-1這些hash算法已經(jīng)被證明是不安全的，可以在很快的時間內(nèi)被攻破。

選擇前綴沖突攻擊

除了前面?zhèn)鹘y(tǒng)的碰撞攻擊之外，還有一種叫做Chosen-prefix collision attack選擇前綴沖突攻擊。

攻擊者可以選擇兩個不同的前綴p1和p2,然后附在不同的字符串m1,m2前面，那么有：

hash(p1 ∥ m1) = hash(p2 ∥ m2) 其中 ∥ 表示連接符

我們看一個在SHA-1中由蓋坦.勒倫（Gatan Leurent）和托馬.佩林（Thomas Peyrin）發(fā)現(xiàn)的一個攻擊的例子，這是兩個分別帶有前綴99040d047fe81780012000和99030d047fe81780011800的例子。

兩個消息內(nèi)容可以從下面下載：

messageA: sha-mbles.github.io/messageA

messageB:sha-mbles.github.io/messageB

我們可以看下消息的截圖：

這兩個消息經(jīng)過sha1sum運(yùn)算，可以得到相同的hash值。

sha1sum messageA ： 8ac60ba76f1999a1ab70223f225aefdc78d4ddc0

sha1sum messageB： 8ac60ba76f1999a1ab70223f225aefdc78d4ddc0

java中的hash攻擊

java中有一個經(jīng)常會用到的類叫做hashMap，在JDK7之前，HashMap在存儲數(shù)據(jù)的時候如果遇到了hash沖突，則會將數(shù)據(jù)以鏈表的形式插入到這個hash節(jié)點(diǎn)的最后。

這樣會有什么缺點(diǎn)呢？

那么就是如果有惡意攻擊者，一直向hashMap中插入同樣hash值的key對象，那么hashMap實(shí)際上就會退化成為一個鏈表。

這樣會大大影響hashMap的查詢效率。如果數(shù)據(jù)特別大的話，可能就會導(dǎo)致DDOS攻擊。

這個問題的根本原因就是java中hashMap中的hash計算太過簡單，很容易就能夠找到相同hash值的key。

實(shí)際上在2011年tomcat還發(fā)布了一個關(guān)于這個問題的漏洞解決方案。

雖然這是java的問題，但是最后的鍋還是由tomcat來背。tomcat的做法就是限制maxPostSize，從最大的20M改成了10K，這樣可以有效的減少請求中的item大小。

當(dāng)然，在JDK8中，原來的鏈表結(jié)構(gòu)已經(jīng)被改成了紅黑樹結(jié)構(gòu)，相信也是為了避免這種DDOS hash攻擊的方案。

原像攻擊Preimage attack

和碰撞攻擊類似的還有一個攻擊叫做原像攻擊。

原像攻擊的抵御需要滿足兩個條件，第一個條件是給定一個hash值y，很難找到一個x，使得hash（x）=y。

第二個條件就是給定一個x，很難找到一個y，使得hash(x) = hash(y)。

很明顯，碰撞攻擊的抵御一定滿足第二個條件，但是不一定滿足第一個條件。

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

最通俗的解讀，最深刻的干貨，最簡潔的教程，眾多你不知道的小技巧等你來發(fā)現(xiàn)！

歡迎關(guān)注我的公眾號:「程序那些事」,懂技術(shù)，更懂你！

總結(jié)

以上是生活随笔為你收集整理的密码学系列之:碰撞抵御和碰撞攻击collision attack的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。