5

興味深いことに、ワールプールのような単一の 512 ビット ハッシュと md5、sha1 などの 4 つの 128 ビット ハッシュの連結との衝突の可能性のテストまたは実験に関する十分な情報が見つかりませんでした。

4 つの 128 ビット ハッシュが同じように見える可能性は、ハッシュが実行されるデータが平均 100 文字のかなり小さいサイズの場合、単一の 512 ビット ハッシュよりも可能性が低いようです。

しかし、私はテストを実行していないため、根拠のない明らかな推測にすぎません。あなたはそれについてどう思いますか？

512 ビット ハッシュと 128 ビット ハッシュのように編集します。128 ビット ハッシュ。128 ビット ハッシュ。128bit ハッシュ (4 つの 128bit ハッシュ連結)

Edit2 RAMを考慮したURLまたはハッシュ のこのインデックスにハッシュを使用したい のですが、URL列ではなくハッシュ列を一意に設定したいため、衝突の可能性を最小限に抑えることが目的です。

Edit3 この質問の目的は、衝突の可能性を最小限に抑える方法を見つけることであることに注意してください。そうは言っても、なぜ衝突の可能性を最小限に抑えることにもっと集中する必要があるのでしょうか? これは、RAM の使用量を減らすための解決策を見つけることにつながる私の Edit2 の説明です。そのため、衝突を最小限に抑えることと、RAM の使用量を減らすことに関心があります。しかし、この質問の主な焦点は、衝突の可能性を下げることです。

4

4 に答える 4

6

次の衝突動作を比較したいようです。

hash512(x)

の衝突動作：

hash128_a(x) . hash128_b(x) . hash128_c(x) . hash128_d(x)

ここで、「.」は連結を示し、、hash128_aなどhash128_bは4つの異なる128ビットハッシュアルゴリズムです。

答えは次のとおりです。それは、関係する個々のハッシュのプロパティに完全に依存します。

たとえば、128ビットのハッシュ関数を次のように実装できると考えてください。

uint128_t hash128_a(T x)   { return hash512(x)[  0:127]; }
uint128_t hash128_b(T x)   { return hash512(x)[128:255]; }
uint128_t hash128_c(T x)   { return hash512(x)[256:383]; }
uint128_t hash128_d(T x)   { return hash512(x)[384:511]; }

その場合、パフォーマンスは同じになります。

于 2011-09-14T13:09:02.833 に答える
4

その質問について読むべき古典的な記事は、HochとShamirによるものです。これは、特にJouxによる以前の発見に基づいています。結論は次のとおりです。128ビット出力の4つのハッシュ関数を使用し、4つのハッシュ関数がMerkle-Damgård構造を使用する場合、512ビット出力全体の衝突を見つけることは、ハッシュ関数の1つの衝突。MD5、SHA-1...MD構造を使用します。

一方、ハッシュ関数の一部が別個の構造を使用している場合、特に実行状態が広い場合は、連結によってより強力な関数が生成される可能性があります。@Oliの例を参照してください。4つの関数すべてがSHA-512であり、出力に何らかの手術が行われている場合、連結されたハッシュ関数はプレーンなSHA-512である可能性があります。

4つのハッシュ関数の連結について唯一確実なことは、結果が4つのハッシュ関数の中で最も強力なものよりも衝突耐性が低くないことです。これはSSL/TLS内で使用されており、バージョン1.1までは、MD5とSHA-1の両方を同時に使用して、どちらかでの中断に抵抗しようとしています。

于 2011-09-14T16:56:17.517 に答える
3

512ビットは512ビットです。唯一の違いは、ハッシュの欠陥の違いです。全体として最良のハッシュは、利用可能な最良のアルゴリズムを使用した512です。

コメントするには長すぎるため、編集して説明を追加します。

理想的なハッシュは、コンテンツをxビットに均一にマッピングします。4つの（完全に独立した）xビットハッシュがある場合、ファイルを4xビットに均一にマップします。4xビットハッシュは、同じファイルを4xビットに均一にマップします。4xビットは4xビットです。完全に均一である限り、1つの（4x）ハッシュ関数からのものか4（x）からのものかは関係ありません。ただし、完全に理想的なハッシュはないため、取得可能な最も均一な分布が必要です。4つの異なる関数を使用する場合、最適に最も近いのは1つだけなので、x個の最適ビットと3x準最適になりますが、1つのアルゴリズムでカバーできます。最適な分布を持つ4倍の空間全体。

十分に大きなアルゴリズムでは、単一の512よりも均一に分散されたビットのサブセットを使用でき、組み合わせて均一性を高めることができると思いますが、それは、ほとんど可能性がないため、非常に多くの追加の調査と実装になると思われます。利点。

于 2011-09-13T20:22:19.383 に答える
2

4 つの異なる「理想的な」128 ビット ハッシュ アルゴリズムを 1 つの理想的な 512 ビット ハッシュ アルゴリズムと連結して比較している場合、はい、両方の方法で同じ衝突確率が得られます。ただし、md5 を使用すると、ハッシュの解読が容易になります。たとえば、攻撃者があなたが md5 + md5 w/ salt + md5 with another salt を実行していることを知っていた場合、それは md5 衝突攻撃としてクラックするのがはるかに簡単になります。攻撃が知られているハッシュ関数の詳細については、こちらを参照してください。

于 2011-09-13T20:24:48.487 に答える