問題タブ [hash-collision]

5,651,744 行のテーブルがあり、主キーは 6 列 (int x 3、smallint、varchar(39)、varchar(2)) で構成されています。このテーブルと、この主キーを共有する別のテーブルと追加の列が追加されていますが、37m 行ある別のテーブルでパフォーマンスを改善したいと考えています。

ハッシュ キーを作成するための列を追加することを見越して、分析を行ったところ、18,733 の衝突が見つかりました。

約2倍悪いBINARY_CHECKSUM()

私がカバーしている宛先スペースの相対的な量が少ないことを考えると、これは高すぎるように見えますか (.33%)? また、衝突がこれほど多い場合、時折の衝突を処理するために通常の列で結合する必要があることを考えると、行ごとに余分な 4 バイトのコストをかけて結合で最初にこの製造されたキーで結合する利点はありますか?

これは基本的に数学の問題ですが、非常にプログラミングに関連しています。URL を含む 10 億の文字列があり、それぞれの MD5 ハッシュの最初の 64 ビットを取得すると、どのような衝突頻度が予想されるでしょうか?

URL が 1 億しかない場合、答えはどのように変わりますか?

衝突は非常にまれであるように私には思えますが、これらは混乱を招く傾向があります。

MD5 以外のものを使用した方が良いでしょうか? 注意してください、私はセキュリティを探しているのではなく、高速なハッシュ関数を探しているだけです。また、MySQL のネイティブ サポートも優れています。

編集：まったく重複していません

ハッシュ関数でのマルチコリジョンと1番目または2番目のプリイメージの違いは何ですか。

• 最初の原像攻撃：ハッシュhが与えられた場合、次のようなメッセージmを見つけます。

  hash（m）=h。

• 2番目の原像攻撃：固定メッセージm1が与えられた場合、次のような別のメッセージm2を見つけます。

  hash（m2）= hash（m1）。

• マルチコリジョン攻撃：一連のメッセージm1、m2、...mNを生成します。

  hash（m1）= hash（m2）= ... = hash（mN）。

ウィキペディアによると、原像攻撃は、攻撃されている固定ハッシュまたはメッセージがあるという点で衝突攻撃とは異なります。

私は次のような発言をする論文に混乱しています：

この手法は、衝突を検索するのに効率的であるだけでなく、MD4の2番目のプリイメージを探索するためにも適用できます。2番目の原像攻撃について、彼らは、ランダムメッセージが確率2 ^ –122の弱いメッセージであり、弱いメッセージに対応する2番目の原像を見つけるために1回のMD4計算のみが必要であることを示しました。

MD4に対する2番目の原像攻撃

著者が言っているように思われることを理解すると、ランダムなメッセージを与えるのに十分な数のメッセージのセットを含むマルチコリジョン攻撃を開発したということです。衝突。

私は多くの論文で同様の議論を見ました。私の質問は、攻撃がマルチコリジョン攻撃でなくなり、2番目の原像攻撃になるのはいつですか。

• マルチコリジョンが2^300の他のメッセージと衝突した場合、それは2番目のプリイメージとしてカウントされます。マルチコリジョンは、衝突したメッセージの1つの「プレイメージ」を計算するために使用できるためです。2 ^ 60、2 ^ 100、2 ^ 1000の境界線はどこにありますか？

• 23で始まるすべてのハッシュダイジェストのプレイメージを生成できるとしたらどうでしょうか。確かに、それはプリイメージの厳密な定義を満たしていませんが、暗号化ハッシュ関数の重大な欠陥でもあります。

• 誰かが大きなマルチコリジョンを持っている場合、ハッシュがマルチコリジョンと衝突したメッセージのイメージをいつでも回復できます。例えば、

  hash（m1）= hash（m2）= hash（m3）= h

  誰かがhのプリイメージを要求し、m2で応答します。これが愚かでなくなり、本当の攻撃になるのはいつですか？

経験則？ハッシュ関数攻撃の評価に関する優れたリソースを知っていますか？

関連リンク：

• 衝突衝突に関するQ＆A
• 暗号化ハッシュ
• eHashメインページ

デモンストレーションのために、ハッシュ化されたときに衝突する文字列の例をいくつか挙げてください。MD5 は比較的標準的なハッシュ オプションであるため、これで十分です。

Hashtable クラスの Java API ドキュメントを読んでいて、いくつかの質問に出くわしました。ドキュメントでは、「ハッシュテーブルが開いていることに注意してください。「ハッシュ衝突」の場合、単一のバケットに複数のエントリが保存され、順番に検索する必要があります。」私は自分で次のコードを試しました

アウトプットは

1. これが「開く」ということですか？
2. 整数 2 はどうなりましたか? ゴミとして回収？
3. 「閉じた」例はありますか？

AとBの2つの異なるメッセージ（サイズが重要な場合は、おそらく20〜80文字のテキスト）が与えられた場合、AのMD5ダイジェストがBのMD5ダイジェストと同じであり、AのSHA1ダイジェストが同じである確率はどれくらいですか。 BのSHA1ダイジェストと同じですか？あれは：

悪意のない意図、つまり、衝突を見つける目的でメッセージが選択されていないことを前提としています。これが自然に起こる確率を知りたいだけです。

「天文学的に低い」可能性は低いと思いますが、どうやって確認すればいいのかわかりません。

詳細：可能なメッセージのプールのサイズは制限されていますが、大きいです（数億）。誕生日のパラドックスの状況はまさに私が心配していることです。

これは暗号理論の質問ですが、ハッシュアルゴリズムの結果がソースと同じ値になる可能性はありますか？たとえば、文字列があるとします。

SHA1ハッシュを取得すると、結果は次のようになります。

理論的には、これら2つの値が一致する場合はありますか？ここでは特にSHA1について質問していません。これは単なる例です。これを防ぐような方法でハッシュアルゴリズムが構築されているのではないかと思っています。

ファイルを識別するためにハッシュを使用しているとしましょう。そのため、ファイルを安全にする必要はありません。衝突を最小限に抑える必要があります。SIMDを使用して4つのハッシュを並行して実行し、最終結果をハッシュすることで、ハッシュを高速化できると考えていました。ハッシュが512ビットブロックを取るように設計されている場合、一度に4x512ビットブロックを取るファイルをステップスルーし、そこから4つのハッシュを生成します。次に、ファイルの最後で、結果の4つのハッシュを一緒にハッシュします。

この方法ではハッシュが貧弱になると確信しています...しかし、どれだけ貧弱ですか？エンベロープ計算の裏側はありますか？

ウィキペディアや Google が見つけたさまざまな .edu Web サイトなどのさまざまな情報源によると、ハッシュ テーブルが衝突を解決する最も一般的な方法は、線形または二次プローブとチェーンです。ランダム化されたプロービングについては簡単に言及されていますが、あまり注目されていません。ランダム化されたプロービングを使用して衝突を解決するハッシュ テーブルを実装しました。衝突があると仮定すると、解決は次のように機能します。

1. オブジェクトの完全な (32 ビット) ハッシュは、線形合同乱数ジェネレーターをシードするために使用されます。
2. ジェネレーターは 32 ビットの数値を生成し、モジュラスを使用して、次にプローブするハッシュ テーブル内の場所を決定します。

これには、モジュラス空間にハッシュ衝突がいくつあっても、完全な 32 ビット ハッシュ空間で衝突がほとんどない限り、ルックアップと挿入の時間は O(1) であると予想されるという非常に優れた特性があります。プローブ シーケンスは疑似ランダムであるため、線形プローブとは異なり、モジュラス空間の衝突によるクラスタリング動作は発生しません。システム全体がオープン アドレスであり、リンク リストをどこにも使用しないため、連鎖とは異なり、挿入ごとにメモリ割り当てを実行する必要はありません。

さらに、ハッシュのサイズは通常、アドレス空間のサイズ (32 ビット マシンでは 32 ビット) であるため、完全な 32 ビット ハッシュで多数のハッシュ衝突を引き起こすのに十分なアイテムをアドレス空間に収めることは単純に不可能です。適切なハッシュスキームの下のスペース。

では、なぜランダム化されたプロービングがこのような人気のない衝突解決戦略なのですか?