Java Hash Collision之資料生産

hashtable是一種非常常用的資料結構。它存取速度快，結構簡單，深得程式員喜愛。hashtable大緻資料結構如下圖：

hash function也叫哈希散列函數，通過散列函數我們能将各種類型的key轉換為有限空間内的一個記憶體位址。常見的散列函數有md5，sha*。不過hashtable中基本不會用md5，sha*算法,因為這兩類算法太耗時，基本所有的程式設計語言都會選擇times*類型算法，比如times31,times33,times37。java使用的hash算法為times31，php使用的hash算法為times33……

如果正常的使用hashtable，hashtable會是一種完美的資料結構。不過總有一些時候hashtable會被不正常使用，例如被攻擊。假設"layne","abbc"這兩個key通過雜湊演算法得到的記憶體位址一樣，我們的程式就不知道到底要擷取哪一個key的參數。針對這種情況我們引入了bucket（一個連結清單結構）的概念，當遇到這種情況時，程式會将同一個記憶體位址對應的多個資料存入同一個bucket連結清單，這樣能解決資料擷取不到的問題，但是會帶來額外的運算。當數十萬甚至百萬的資料都打到同一個bucket，對hashtable的影響是緻命的，運算量将急劇增加，分分鐘将cpu耗盡。

通過研究各種語言底層的hashtable雜湊演算法就能生産對應的攻擊資料，這種攻擊很難防禦。不過在我們知道攻擊原理之後，還是能很好應對。

通過google，我們很輕松的就搜尋到了java hashtable實作的雜湊演算法，在java中有個叫hashcode()的方法，我們可以這樣使用。

system.out.println("it2048.cn".hashcode());

hashcode()函數底層就是使用times31算法，至于為什麼選擇times31，官方說法是 『 31 * i == (i << 5) - i 』，運算起來更快。源代碼如下：

核心的計算的公式如下：

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

通過推導計算，得到的計算公式如下：

f(n) = 31*f(n-1) + str[i]

使用php實作如下（這裡隻為加強說明哈希雜湊演算法底層都是很簡單的公式）：

通過如下公式

我們可以進一步推導出如下方程式：

31*x + y = 31*(x+1) + y-31 = 31*(x+2) + y-62

我們很容易找到滿足條件的3組ascii字元，分别是：

at = 97*31 + 116 = 3123 bu = 98*31 + 85 = 3123 c6 = 99*31 + 54 = 3123

通過如上資料，理論上我們可以構造任何偶數位的字元串，比如：

atatatatatatatat (16位)

c6atatatatatatbu (16位)

atatatatatatbuat (16位)

c6c6c6c6c6c6buat (16位)

如上16位字元串得到的hashcode都是一樣，理論上我們可以得到 pow(3,16/2) = 6561 個字元串；22位長度的字元串可以得到pow(3,22/2) = 177147 個字元串，用來發起簡單的攻擊完全足夠。接下來我們封裝一個簡單的函數來生成 177147 個攻擊字元串；

如上我們已經推算出碰撞資料的實作方程式，接下來我通過php快速的生成碰撞資料。這裡最好不要使用java來生成碰撞資料，因為操作不當就會變成攻擊自己的腳本。

最後我們生成了如下資料(截取了前面幾條)：

通過程式我們生成了177147條碰撞資料，然後在springboot中做個簡單的測試，測試代碼如下：

測試結果，一個cpu被打到100%，持續了20多分鐘。mac pro馬上發燙，風扇開啟。結束該java程序後電腦恢複。

未完待續……