1.1.1 摘要 最近網絡安全成了一個焦點，除了國內明文密碼的安全事件，還有一件事是影響比較大的——Hash Collision DoS（通過Hash碰撞進行的拒絕式服務攻擊），有惡意的人會通過這...

1.1.1 摘要

 

      最近網絡安全成了一個焦點，除了國內明文密碼的安全事件，還有一件事是影響比較大的——Hash Collision DoS（通過Hash碰撞進行的拒絕式服務攻擊），有惡意的人會通過這個安全漏洞讓你的服務器運行巨慢無比，那他們是通過什么手段讓服務器巨慢無比呢？我們如何防范DoS攻擊呢？本文將給出詳細的介紹。

 

1.1.2 正文

 

      在介紹Hash Collision DoS攻擊之前，首先讓我們復習一下哈希表（Hash table）。

      哈希表（Hash table，也叫散列表），是根據關鍵碼值（Key/Value）而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做哈希函數（它的好壞將關系到系統的性能），存放記錄的數組叫做哈希表。

     大家知道哈希函數在計算哈希值時不可以避免地會出現哈希沖突。

     假設我們定義了一個哈希函數hash()，m代表未經哈希計算的原始鍵，而h是m經過哈希函數hash()計算后得出的哈希值。

     現在我們對原始鍵m1和m2進行哈希計算就可以獲取相應的哈希值分別為：hash(m1)和hash(m2)。

     如果原始鍵m1=m2，那么將可能得到相同的哈希值，但是鍵m1!=m2也可能得到相同的哈希值，那么就發生了哈希沖突（Hash collision），在大多數的情況下，哈希沖突只能盡可能地減少，而無法完全避免。

     當發生哈希沖突時，我們可以使用沖突解決方法解決沖突，而主要的哈希沖突解決方法如下：

開放地址法

再哈希法

鏈地址法

建立一個公共溢出區

      當發生哈希沖突時，我們的確可以采用以上的方法解決哈希沖突，但我們能不能盡可能避免哈希沖突的出現呢？如果哈希沖突被減少到微乎其微，那么我們系統性能將得到很大提高，我們通過使用沖突幾率更低的算法計算哈希值。

      一般情況衡量一種算法的好壞是通過它的最優，一般和最差情況的時空復雜度來衡量算法好壞的。

      在理想情況下，哈希表插入、查找和刪除一個元素操作的時間復雜度都為O(1)，那么插入、查找和刪除n個元素的時間復雜度就為O(n)，任何一個數據項可以在一個與哈希表長度無關的時間內計算出一個哈希值（Key），然后根據哈希值（Key）定位到哈希表中的一個槽中（術語bucket，表示哈希表中的一個位置）。最理想情況是我們在長度為n的哈希表中插入n個元素，而且經過哈希計算后它們的哈希值恰好均勻地分配到哈希表的每個槽中完全沒有沖突，這的確太理想了。但這不符合實際情況，由于我們無法預知插入元素的個數，而且哈希表的長度也是有限的，所以說哈希沖突是無法避免的。

 

圖1 哈希表時間復雜度

 

      碰撞解決大體有兩種思路，第一種策略是根據某種原則將被碰撞數據定為到其它槽中，例如開放地址法的線性探索，如果數據在插入時發生了碰撞，則順序查找這個槽后面的槽，將其放入第一個沒有被占有的槽中；第二種策略是每個槽不只是只能容納一個數據項的位置，而是一個可容納多個數據項的數據結構（例如鏈表或紅黑樹），所有碰撞的數據以某種數據結構的形式組織起來（線性探索：di = 1，2，3，…，m – 1）。

 

圖2 開放地址法

      不論使用哪種碰撞解決策略，都導致插入、查找和刪除的操作的時間復雜度不再是O(1)。以查找為例：不能通過哈希值（Key）定位到槽就結束，還需要比較原始鍵（即未經過哈希的Key）是否相等，如果不相等，則使用與插入相同的算法繼續查找，直到找到匹配的值或確認數據不在哈希表中。

     .NET是使用第一種策略解決哈希沖突，它根據某種原則將碰撞數據定位到其他槽中。

     而PHP是使用單鏈表存儲碰撞的數據，因此實際上PHP哈希表的平均查找復雜度為O(L)，其中L為桶鏈表的平均長度；而最壞復雜度為O(N)，此時所有數據全部碰撞，哈希表退化成單鏈表。下圖是PHP中正常哈希表和退化哈希表的示意圖。

 

圖3 正常哈希表

 

 

圖4 退化哈希表

 

       通過上圖正常哈希表我們發現在正常情況下，哈希值分配的均勻沖突幾率很低，而退化的哈希表中全部數據都在同一個槽上發生了沖突，這將導致數據插入、查找和刪除的時間復雜度變為O(n²)，由于時間復雜度提升了一個數量級，因此會消耗大量CPU資源，導致系統無法及時響應請求，從而達到拒絕服務攻擊（DoS）的目的。

.NET中哈希表的實現

 

數據結構

      在.NET中定義一個結構體bucket來表示槽，它只包含三個字段，具體代碼如下：

 

/// <summary>
/// Defines hash bucket.
/// </summary>
private struct bucket
{
    /// <summary>
    /// The hask key.
    /// </summary>
    public object key;

    /// <summary>
    /// The data value.
    /// </summary>
    public object val;

    /// <summary>
    /// The key has hash collision.
    /// </summary>
    public int hash_coll;
}

 

     當發生沖突時，線性探索再散列在處理的過程中容易產生記錄的二次聚集，而.NET通過使用再哈希和動態增加哈希表長度來減少再發生哈希沖突。

 

/// <summary>
/// Rehashes the specified newsize.
/// </summary>
/// <param name="newsize">The newsize.</param>
private void rehash(int newsize)
{
    this.occupancy = 0;

    // Creates a new bucket.
    Hashtable.bucket[] newBuckets = new Hashtable.bucket[newsize];
    for (int i = 0; i < this.buckets.Length; i++)
    {
        Hashtable.bucket bucket = this.buckets[i];
        if ((bucket.key != null) && (bucket.key != this.buckets))
        {
            this.putEntry(newBuckets, bucket.key, bucket.val, bucket.hash_coll & 0x7fffffff);
        }
    }
    Thread.BeginCriticalRegion();
    this.isWriterInProgress = true;

    // Changes the bucket.
    this.buckets = newBuckets;
    this.loadsize = (int)(this.loadFactor * newsize);
    this.UpdateVersion();
    this.isWriterInProgress = false;
    Thread.EndCriticalRegion();
}

 

     通過上面的rehash()方法我們知道當發生沖突時，.NET通過再哈希和增大哈希表的長度來避免再發生沖突。

 

哈希算法

   現在讓我們看看.NET使用什么哈希算法，查看Object.GetHashCode()方法，具體代碼如下：

 

public virtual int GetHashCode()
{
    return InternalGetHashCode(this);
}

 

    我們發現Object.GetHashCode()方法調用了另一個方法InternalGetHashCode()，我們進一步查看InternalGetHashCode()方法，發現它映射到CLR中的一個方法ObjectNative::GetHashCode，具體實現代碼如下：

 

 FCIMPL1(INT32, ObjectNative::GetHashCode, Object* obj) {  
    CONTRACTL  
    {  
        THROWS;  
        DISABLED(GC_NOTRIGGER);  
        INJECT_FAULT(FCThrow(kOutOfMemoryException););  
        MODE_COOPERATIVE;  
        SO_TOLERANT;  
    }  
    CONTRACTL_END;  

    VALIDATEOBJECTREF(obj);  

    DWORD idx = 0;  

    if (obj == 0)  
        return 0;  

    OBJECTREF objRef(obj);  

    HELPER_METHOD_FRAME_BEGIN_RET_1(objRef);        // Set up a frame  

    // Invokes another method to create hash code.
    idx = GetHashCodeEx(OBJECTREFToObject(objRef));  

    HELPER_METHOD_FRAME_END();  

    return idx;  
}  
FCIMPLEND

 

      該方法的實現并不復雜，但我們很快就發現其實該方法里再調用GetHashCodeEx()方法，它才是具體的哈希算法的實現，這里就不做詳細的介紹因為實現代碼很長，如果大家想查看它的C++源代碼請點這里。

      現在主流編程語言都采用的哈希算法是DJB（DJBX33A），而.NET中的NameValueCollection.GetHashCode()方法就是使用DJB算法。

DJB的算法實現核心是通過給哈希值（Key）乘以33（即左移5位再加上哈希值）計算哈希值，接下來讓我們看一下DJB算法的實現吧！

 

/// <summary>
/// Uses DJBX33X hash function to hash the specified value.
/// </summary>
/// <param name="value">The value.</param>
/// <returns>The hash string</returns>
public static uint DJBHash(string value)
{
    if (string.IsNullOrEmpty(value))
    {
        throw new ArgumentNullException("The hash value can't be empty.");
    }

    uint hash = 5381;
    for (int i = 0; i < value.Length; i++)
    {
        // The value of ((hash << 5) + hash) the same as 
        // the value of hash * 33.
        hash = ((hash << 5) + hash) + value[i];
    }

}

 

   我們看到DJB算法實現十分簡單，但它卻是十分優秀的哈希算法，它生成的哈希值沖突幾率很低，接下來讓我們看一下.NET中String.GetHashCode()方法的實現——DEK算法。

 

/// <summary>
/// Returns a hash code for this instance.
/// </summary>
/// <returns>
/// A hash code for this instance, suitable for use in hashing algorithms
///  and data structures like a hash table. 
/// </returns>
public override unsafe int GetHashCode()
{
    // Pins the heap address, so GC can't collect it.
    fixed (char* str = ((char*)this))
    {
        char* chPtr = str;
        int num = 0x15051505;
        int num2 = num;
        int* numPtr = (int*)chPtr;
        for (int i = this.Length; i > 0; i -= 4)
        {
            // Uses DEK to generate hash code.
            num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
            if (i <= 2)
            {
                break;
            }

            // Uses DEK to generate hash code.
            num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1];
            numPtr += 2;
        }
        return (num + (num2 * 0x5d588b65));
    }
}

 

     String類中重寫了GetHashCode()方法，由于GetHashCode()會涉及到一些指針操作，所以把該方法定義為unsafe表示不安全上下文，也許有人會奇怪C#中還能像C/C++中的指針操作嗎？我們要在C#中使用指針操作，這時fixed關鍵字終于派上用場了。fixed 關鍵字是用來pin住一個引用地址的，因為我們知道CLR的垃圾收集器會改變某些對象的地址，因此在改變地址之后指向那些對象的引用就要隨之改變。這種改變是對于程序員來說是無意識的，因此在指針操作中是不允許的。否則，我們之前已經保留下的地址，在GC后就無法找到我們所需要的對象（fixed詳細介紹請參考這里）。

 

哈希碰撞攻擊

      通過前面介紹.NET中GetHashCode()方法，現在我們對于其中的實現算法有了初步的了解，由于哈希沖突的原理就是針對具體的哈希算法來構造數據，使得所有數據都發生碰撞。

      但如何構造數據呢？首先讓我們看一個例子，假設我們往一個類型為NameValueCollection的對象中插入數據。

 

圖5 插入數據

      通過上圖我們發現插入1000個數據只需88 ms，當插入2000個數據需時345 ms，隨著插入數據規模的增大我們發現插入時間越來越長，哈希表的插入時間復雜度不是O(n)嗎？大家肯定知道這是由于發生哈希沖突導致時間復雜度無法達到線性。

      這里我們使用了一個簡單方法構造沖突數據——蠻力法。（效率低）

      由于蠻力法效率低，所以我們采用更加高效的方法中途相遇攻擊（meet-in-the-middle attack）或等效子串（equivalent substrings）來構造沖突數據。

等效子串：

      如果哈希函數具有這樣的特性，當兩個字符串的哈希值發生沖突，例如：hash(“string1”)=hash(“string2”)，那么由這兩個子串在同一位置上構成的字符串也發生哈希沖突，例如：hash(“prefixstring1postfix”)=hash(“prefixstring2postfix”)。

      假設“EZ”和“FY”在哈希函數中發生沖突，那么字符串“EzEz”，“EzFY”，“FYEz”，“FYFY”兩兩之間也發生沖突。大家想查看使用等效子串的例子點這里。

中途相遇攻擊：

      如果在一個給定的哈希函數中不存在等效子串，那么蠻力法似乎是唯一的解決辦法了。但我們前面介紹蠻力法效率低，明顯的以32位為例這種方式命中目標的概率是1 /（2 ^ 32）。

      現在我們只需計算16位哈希值，那么命中目標的概率是1/(2^16)，這樣命中幾率大大的提高了，而且構造數據時間也縮短了。

      我們使用等效子串方法把字符串分成兩部分，前綴子串（長度為n）和后綴子串（長度為m），接著我們枚舉前綴子串的哈希值，并且使得它們的哈希值相等。

 

      這里要回顧一個數學知識——異或運算

 

圖6異或運算

 

      現在我們通過異或運算使得枚舉前綴子串的哈希值都相等，首先我們讓前綴子串乘以1041204193再經過DJB33計算哈希值。也許有人會問為什么要乘以1041204193呢？

      由于1041204193 * 33 = 34359738369

      二進制值：00000000000000000000000000000000001（使用Int32）

      我們知道1041204193 * 33 = 1，那么現在的前綴子串的哈希值只與它的字符相關，這將導致沖突幾率增大了。

      HashBack()方法的示意代碼如下：

 

/// <summary>
/// The hash back function.
/// </summary>
/// <param name="tmp">The string need to hash back.</param>
/// <param name="end">The hash back value.</param>
/// <returns>The hash back string.</returns>
[ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
private static unsafe int HashBack(string tmp, int end)
{
    int hash = end;

    fixed (char* str = tmp)
    {
        char* suffix = str;
        int length = tmp.Length;

        for (; length > 0; length -= 1)
        {
            hash = (hash ^ suffix[length - 1]) * 1041204193;
        }

        return hash;
    }
}

 

      我們看到HashBack()方法包含兩個參數，一個是要計算哈希值的字符串，而另外一個就是最后發生沖突的哈希值。

      接來下我們讓實現DJB33哈希函數示意代碼如下：

 

/// <summary>
/// The hash function with DJB33 algorithm.
/// </summary>
/// <param name="tmp">The string need to hash.</param>
/// <returns>The hash value.</returns>
[ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
private static unsafe int Hash(string tmp)
{
    int hash = 5381;

    fixed (char* str = tmp)
    {
        char* p = str;
        int tmpLenght = tmp.Length;
        for (; tmpLenght > 0; tmpLenght -= 1)
        {
            hash = ((hash << 5) + hash) ^ *p++;
        }

        return hash;
    }
}

 

      現在我們完成了HashBack()和Hash()方法，首先我們使用HashBack()方法計算出前綴子串的哈希值，然后再使用Hash()方法找出和前綴子串發生沖突的子串，最后把前綴和后綴拼接起來就構成了沖突字符串了。

      也許大家聽起來有點別扭，那么讓我們通過具體的例子來說明吧！

      假設我們找到前綴“BIS”，而且HashBack(“NBJ”) = 147958270，然后我們通過暴力方法找出了和前綴有沖突的后綴Hash(“SKF0FTG”) = 147958270，接著我們把它們拼接起來計算Hash(“NBJ” + “SKF0FTG”) = 6888888，我們看到拼接起來的字符串計數出來的哈希值是我們事先已經指定好的，所以我們可以通過這種方法不斷構造沖突數據。

      接著我們使用以上的沖突數據進行插入測試，一開始運行插入數據CPU的消耗就開始變得大了，曾經一度消耗到100%那時機器根本動不了，所以無法截圖。

 

圖7 哈希沖突測試

 

防御

限制CPU時間

      這是最簡單的方法可以減少此類攻擊的影響，它通過減少CPU請求時間將被允許參加。對于PHP可以設置max_input_time參數值；在IIS（ASP.NET）中，可以通過設置“關機時間限制”值（默認90s）。

限制POST請求參數個數

     本次微軟推出的安全性更新是通過限制 ASP.NET處理 HTTP POST 請求時最多只能接受1000個參數個。（補丁）

     如果我們的Web應用程序需要接受超過1000個參數，可以通過設置WebConfig中MaxHttpCollectionKeys的值來修改最多限制數，具體設置如下：

 

<!--Setting Max Http post value-->
<appSettings>
  <add key="aspnet:MaxHttpCollectionKeys" value="1001" />
</appSettings>

 

限制POST請求長度

使用隨機的哈希算法

      由于我們事先知道使用的哈希算法，所以構造沖突數據更加有針對性，但一旦才有隨機哈希算法我們沒有辦法預知使用算法，所以沖突數據很難構造，但不幸的是許多主流的編程語言都是采用非隨機哈希算法，除了Perl之外，像.NET，Java，Ruby，PHP和Python等都是采用非隨機算法。

 

1.1.3 總結

 

      本文通過引入哈希表，接著介紹哈希表的實現和發生哈希沖突時處理的方法，然后針對具體的哈希算法構造沖突數據（等效子串和中途相應），最后介紹該如何防御Hash Denial Of Service 攻擊。

      由于我們事先知道使用的哈希算法，所以構造沖突數據更加有針對性，所以通過使用隨機哈希算法可以更加有效防御Hash Denial Of Service 攻擊，估計許多語言將會重新設計它們的哈希函數。

 

參考：

[1] 2007_28C3_Effective_DoS_on_web_application_platforms

[2] advisory28122011

 

系列博客導航

網絡攻擊技術一：SQL Injection
網絡攻擊技術二：Cross-site scripting