Hash Collision DoS

oCERT Advisories ==> http://www.ocert.org/advisories/ocert-2011-003.html

Hashtable 在 Java 中是很常被使用的 class 之一, Hashtable 的原理是利用 hash code 的方式, 算出陣列的索引, 來加速資料搜尋, 最佳狀況下, hash code 是不會重覆的, 因此可以達到快速搜尋的效果

Wikipedia 對 Hash table 的說明 ==>  http://en.wikipedia.org/wiki/Hash_table

hash code 的運算方式有很多種, 但不管使用哪一種方式, 都難免發生兩種不同的 Key, 算出同樣 hash code 的狀況, 稱之為碰撞（collision）

我們來看 Java HashMap 如何去處理 collision

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<k> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry<k> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}

未發生 collision 的狀況下資料結構應該是長這樣

 

當發生 collision 時, Hashtable 變形為 single linked list

在一個線性串列中，如果資料量很大，花費在搜尋上的時間成本也就隨之增加,
有心人士可利用這個特性來對 Java 撰寫的 Web 做攻擊