6

このテクニックは多くの場所（スタックを含む）で推奨されているのを目にしますが、これによってエントロピーが減少することを頭から離れることはできません。結局のところ、あなたは何かを再びハッシュしているのですが、それはすでにハッシュされており、衝突の可能性があります。衝突の可能性よりも衝突の可能性が高くなると、衝突の可能性が高くなりませんか？調べてみると、間違っているようですが、なぜですか？

4

2 に答える 2

3

md5 にタグを付けたので、それを例として使用します。ウィキペディアから：

同じハッシュを持つ 2 つのプレフィックスを構築できる場合は、両方に共通のサフィックスを追加して、それを使用するアプリケーションが衝突を有効なデータとして受け入れやすくすることができます。さらに、現在の衝突検出技術では、任意のプレフィックスを指定できます。攻撃者は、同じ内容で始まる 2 つの衝突するファイルを作成できます。攻撃者が 2 つの衝突するファイルを生成するために必要なのは、衝突検出アルゴリズムによって自由に変更できる 64 バイトの境界に配置された 128 バイトのデータ ブロックを含むテンプレート ファイルだけです。2 つのメッセージの 6 ビットが異なる MD5 衝突の例を次に示します。

そして、彼らが提供する平文の例は 256 バイトの長さです。衝突攻撃は 128バイトのデータ ブロックに依存しており、ハッシュ ダイジェストはわずか 128ビットであるため、最初の反復を超えて衝突攻撃が成功するリスクは実際には増加しません。最初のハッシュを超えた衝突の可能性に影響を与えます。

また、ハッシュのエントロピーが前述の 128 ビットであることも考慮してください。合計の衝突確率がわずか 2^20.96 (ウィキペディアから) であることを考慮しても、2 つの入力を衝突させるには多数の反復が必要です。あなたが犠牲になっていると私が思う一見した理由は次のとおりです。

  • 任意の 2 つの入力は、x% 衝突する可能性があります。
  • 最初のハッシュの出力は、そのような 2 つの入力そのものです。
  • したがって、反復ごとに衝突の可能性が x% 増加します。

これは、反例によってかなり簡単に反証できます。もう一度 MD5 を考えてみましょう:

  • 2 つの入力が衝突する可能性は 1:2^21 です (ウィキペディアの MD5 の暗号分析から最悪のシナリオを採用)
  • 再びハッシングを行うと、衝突の可能性が等しくなる可能性が高くなります。したがって、2 回目のラウンドでの衝突の可能性は 1:2^20 です。
  • したがって、ダイジェストのエントロピーに等しい回数ハッシュされた任意の 2 つの入力は、衝突することが保証されます。

任意の 2 つの入力を 128 回連続して MD5 すると、これが正しくないことがわかります。それらの間で繰り返される単一のハッシュはおそらく見つからないでしょう - 結局、可能な 2^128 ハッシュ値のうち 256 しか作成していないため、2^120 の可能性が残っています。各ラウンド間の衝突の確率は、他のすべてのラウンドとは無関係です。

この理由を理解するには、2 つのアプローチがあります。1 つ目は、各反復が本質的に移動するターゲットを攻撃しようとしていることです。誕生日のパラドックスに基づいて、ある入力からの 1 つのハッシュ ダイジェストが別の入力のハッシュ ダイジェストと一致する可能性が高いハッシュの反復回数が驚くほど少ないという証明を構築できると思います。しかし、それらは反復のさまざまな段階でほぼ確実に発生していたでしょう。そして、それが発生すると、ハッシュアルゴリズム自体が決定論的であるため、同じ反復で同じ出力を持つことはできません.

もう 1 つのアプローチは、実行中にハッシュ関数が実際にエントロピーを追加することを理解することです。空の文字列には、他の入力と同様に 128 ビットのダイジェストがあると考えてください。これは、アルゴリズムのステップでエントロピーを追加しないと発生しません。これは、実際には暗号化ハッシュ関数の必然的な部分です。データを破棄する必要があります。そうしないと、ダイジェストから入力を復元できます。ダイジェストよりも長い入力の場合、はい、エントロピーは全体的に失われます。ダイジェストの長さに収まるようにする必要があります。しかし、いくらかのエントロピーも追加されます。

他のハッシュアルゴリズムの正確な数値はわかりませんが、私が行ったすべてのポイントは、他のハッシュ関数と一方向/マッピング関数に一般化されていると思います.

于 2012-07-30T04:01:08.187 に答える