160ビットのSHA1ハッシュの最初の32ビットはCRC32ハッシュの代用として受け入れられますか？

Question

私は.NET 3.5プロジェクトで作業しており、32ビットのハッシュ値が必要です。 32ビットハッシュ（MD5は128ビット、SHA1は160ビットなど）を返す.NET暗号化クラスのメソッドはありません。私はCRC32クラスを実装しましたが、すでに存在するSHA1とMD5のハッシュ関数ははるかに高速です。

SHA1ハッシュ関数を使用して私のハッシュ値として格納するために最初の32ビットを切り捨てるだけで問題が発生する（つまり、衝突の可能性が増しますか）？

Answer 1

CRC32（線形コード）の余分な機能を必要としない限り、あなたは32ビット。

いくつかの暗号化ハッシュ関数の出力を切断することは、衝突耐性に関してセキュリティを傷つけるかどうかは、オープンな研究上の問題です（正しく覚えていれば、 "不自然な"例が存在します）。しかしNIST（おそらくNSAの承認を得て）は、とにかくSHA-256をSHA-256から得るために切断技術を使用しました（article about SHA in wikipedia参照）。

EDIT：CRC32は単一のビットエラーを検出することができますが、暗号ハッシュ関数は同じハッシュ値を持つ2つの入力を見つけることができないという特性を持つ必要があります。

「誕生日のパラドックス」（もう一度wikipediaを参照）に気付いていますか？ 32ビットのチェックサムでは、約2^16の入力を持つときに衝突（つまり、同じハッシュ値を持つ2つの入力）が発生し、より多くの入力をハッシュしたいと考えます。 （あなたのコメントを読み返すことはあなたにとって問題ではないかもしれません）

Answer 2

暗号化目的で32ビットを使用するつもりがない場合は、OKである必要があります。さもなければ、私は全体のハッシュと同じ分布を持つ最初の32ビットに頼らないでしょう。

利用できる幅の広いハッシュを使用できないのはなぜですか？

Answer 3

CRC32はおそらくあなたのニーズに合っています。これはthis questionで議論されています。

ハッシュプリミティブを切り捨てるという点では、キーの生成に使用されるSSL/TLS Pseudo Random Function (PRF)が唯一よく使われています。 HMAC、シード、およびラベルを使用して、必要なだけ多くのバイトを生成します。必要なバイト数に切り捨てます。ご質問のよう

しかし、あなたはのInt32のにハッシュの出力を読み、あなたが妄想している場合、それらを一緒にXORできます

ハッシュ関数は同じようにその入力を配布することを前提として考えると

static void Main() 
{ 
    int xorCrc = GetHashedCrc(new SHA1Cng(), new byte[] {0xDE, 0xAD, 0xBE, 0xEF}); 
} 

private static int GetHashedCrc(HashAlgorithm algorithm, byte[] bytesToHash) 
{ 
    byte[] hash = algorithm.ComputeHash(bytesToHash); 
    int totalInt32s = hash.Length/sizeof(int); 
    int result = 0; 
    for(int i = 0; i < totalInt32s; i++) 
    { 
     int currentInt = BitConverter.ToInt32(hash, sizeof(int)*i); 
     result = result^currentInt; 
    } 

    return result; 
} 

Answer 4

そのcodomain上で、それがまたそれの任意の部分集合の上に均等に配分すると仮定することは論理的であると思われる。 しかし、 "ネイティブ" 32ビットのハッシュ関数を使用することはおそらくもっと良い選択です。たぶん私の腸の感情よりも良い理由を私たちに与えるかもしれません：

Answer 5

なぜ単にstring.GetHashCode（）を使用しないでください。これは、32ビットのハッシュ値を計算し、実際のデータが与えられた場合に衝突をほとんど発生させないように設計されています。もちろん、それは安全ではありませんが、あなたの質問にはそれが要件として含まれていません。