使用SuperFastHash而不是CRC32？

注意：我不是試圖使用SuperFastHash，並期望它給出與CRC32相同的輸出值。使用SuperFastHash而不是CRC32？

我正在寫一個簡單的LZSS壓縮/解壓縮程序解壓縮時提供非常快速減壓，沒有內存開銷。輸入數據被分成長度爲4096個字節的塊，並按順序壓縮。

我的問題：我要添加一些錯誤檢測爲每個壓縮塊（塊大小< = 4096字節）。時間限制很激烈，因此校驗和例程必須非常快。我避開了密碼算法（MD5，SHA1），因爲它們涉及大量計算，我選擇了CRC32（一種更簡單明顯的算法）。

做一些測試後，我發現CRC32太慢了關於我的項目的限制。我使用了here的enwik9（10^9字節的維基百科文本轉儲）。我用我的LZSS例程壓縮它，並獲得一個570Mb文件。我測量以下持續時間（單線程的，磁盤IO排除處理之前加載在內存中的所有數據，平均10次試驗）：

 
|   Operation   | Time (GCC4.4.5/Linux) | Time (MSVC2010/Win7) | 
|-------------------------------+--------------------------+------------------------| 
|  Decompression   |  6.8 seconds  |  6.95 seconds  | 
| CRC32 on decompressed result |  4.9 seconds  |  4.62 seconds  | 
| CRC32 on compressed result |  2.8 seconds  |  2.69 seconds  |

然後我測試SuperFastHash，只是在好奇心：

 
|   Operation   | Time (GCC4.4.5/Linux) | Time (MSVC2010/Win7) | 
|-------------------------------+--------------------------+------------------------| 
| SFH on decompressed result |  1.1 seconds  |  1.33 seconds  | 
| SFH on compressed result |  0.7 seconds  |  0.75 seconds  |

這裏是我的CRC32實現（我跟着從以下文件的說明：http://www.ross.net/crc/download/crc_v3.txt）：

# include <stdint.h> 

// CRC32 lookup table (corresponding to the polynom 0x04C11DB7) 
static const uint32_t crc32_lookup_table[256] = 
{ 
    0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 
    0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3, 
    0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, 
    // many lines skipped 
    // ... 
    0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D 
} ; 

uint32_t crc32_hash(const uint8_t * data, size_t len) 
{ 
    uint32_t crc32_register = 0xFFFFFFFF ; 
    while(len--) 
    { 
     crc32_register = (crc32_register >> 8) 
        ^crc32_lookup_table[(crc32_register & 0x000000FF)^*data++] ; 
    } 
    return crc32_register^0xFFFFFFFF ; 
}

我的問題是：

我可以使用哈希代替循環冗餘校驗值，以壓縮數據塊進行錯誤檢測？據我所知（我記得我的電子學課程），CRC算法設計爲當數據在噪聲通道上傳輸時發生錯誤時非常高效，而不是從硬盤讀取數據的情況。如果我錯了，請糾正我。

感謝您的任何建議！

來源

2011-09-05 overcoder

如果你只是防範壓縮文件的意外損壞，並檢查_decompressed_數據上的校驗和，那麼很可能任何奇數校驗和方法都能正常工作，因爲壓縮數據中的任何錯誤都可能會破壞所有的東西跟隨它。也許除了一個簡單的模塊化總和或一切的異或，但即使像Adler32這樣的東西應該做的工作。 –

謝謝！我曾經想過同樣的事情，但是在解壓縮之後放置錯誤檢測步驟需要在出現錯誤數據時從解壓縮例程中進行非常好的錯誤處理。由於錯誤，我的意思是在壓縮塊中處理無效的LZ pos/len時可能發生的內存下溢/溢出。如果我只能在減壓程序的主循環內擺脫邊界測試，我可以輕鬆獲得15％的速度...... – overcoder

出於安全原因，您需要處理內存溢出。否則，攻擊者很容易產生崩潰（或可能顛覆）你的程序的輸入 - 並且合法壓縮器可能爲_compressed_數據產生的任何校驗和也可能由有人制造攻擊數據包手工模擬。 –

因爲你的問題不在於安全性，您可以使用「破碎的」加密散列函數，這對於有感知力的攻擊者來說並不安全，但仍然非常擅長檢測傳輸錯誤。我在考慮MD4，在某些平臺上測得的速度比CRC32快。您可能還想要檢查RadioGatún和巴拿馬;有關各種加密散列函數的C和Java中的開源實現，請參閱this library。

如果你的目標體系是近年/足夠大的x86處理器，其採用了AES-NI指令，那麼你可以通過簡單的計算CBC-MAC與塊加密AES和傳統的按鍵（例如所有做出過分地快速和非常好的校驗-zero鍵）;因爲這不是安全的，你甚至可以使用比標準AES少的輪次（例如5輪而不是標準10）。

來源

2011-09-07 06:50:35

對不起，我遲到的迴應！我最終使用了Adler16，這是着名的Adler32算法的修改版本。感謝您的好參考！ – overcoder

散列設計導致的結果，即使輸入非常小的改變有很大的變化。

我認爲SuperFastHash有這個propertie。它可能會更容易受到碰撞（因爲它似乎較少被社區分析），但它不應妨礙您的使用。

祝你好運:)

來源

2011-09-05 20:43:25 woliveirajr

如果SuperFastHash聲稱是一個加密哈希函數，那麼這句話「它可能會更容易受到碰撞（因爲它似乎不被社區分析）」。它沒有。沒有必要分析它，就像任何非密碼散列函數一樣，建立衝突是微不足道的。 –

我對Bob Jenkins的哈希感興趣的是，他們提供了大量統計測試的證據，表明他們已經被謹慎選擇，以便在輸入中翻轉不同位的結果具有良好的擴散和獨立性。據我所知，類似的測試程序_may_已經完成了SuperFastHash，但從它的網站上看不出這是如此。 –

@帕斯卡爾：這句話我只是說在那個散列函數中碰撞概率沒有很好的確定。我知道OP只是希望CRC-hash能夠確保他在解壓縮時獲得原始數據。碰撞也可能是一個問題，否則簡單的奇偶校驗就足夠了。 – woliveirajr

SuperFastHash已經發現有一些問題，與其他快速散列函數murmur2一起。如果您正在尋找適合碰撞較少的較大數據塊的東西，則可以嘗試谷歌城市散列（http://code.google.com/p/cityhash/）或murmur3的128位變體。另外還有一些像crap8和crapwow那樣的聲稱提供幾乎完美的位雪崩和漏斗並因此幾乎沒有碰撞的牆壁，你可以在這裏和其他非密碼哈希函數在這裏讀到：http://www.team5150.com/~andrew/noncryptohashzoo/

來源

2011-09-05 22:13:51 Necrolis

使用SuperFastHash而不是CRC32？

回答

相關問題