簡介
hash是密碼學和平時的程式中經常會用到的一個功能，如果hash算法設計的不好，會産生hash碰撞，甚至産生碰撞攻擊。
今天和大家詳細探讨一下碰撞攻擊。
什麼是碰撞攻擊
所謂碰撞攻擊指的是對于同一個hash函數來說，兩個不同的input通過hash計算得到了同樣的hash值。用公式來說就是：
這個攻擊有什麼作用呢？
舉個例子，通常我們通過網絡下載下傳應用程式或者軟體，除了下載下傳連結之外，還會提供一個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前面，那麼有：
我們看一個在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)。
很明顯，碰撞攻擊的抵禦一定滿足第二個條件，但是不一定滿足第一個條件。
本文已收錄于 http://www.flydean.com/collision-attack/ 最通俗的解讀，最深刻的幹貨，最簡潔的教程，衆多你不知道的小技巧等你來發現！ 歡迎關注我的公衆号:「程式那些事」,懂技術，更懂你！