壊れたハッシュ関数を使用しても安全なのはいつですか？

StackOverflow https://stackoverflow.com/questions/2889473

質問

SHA-256のような安全なハッシュ関数を使用することは些細なことであり、セキュリティにMD5を使用し続けることは無謀な動作です。ただし、ハッシュ機能の脆弱性には複雑さがあり、よりよく理解したいと思います。

衝突があります MD4およびMD5用に生成されます. 。 NISTによると、MD5は安全なハッシュ関数ではありません。かかるだけです 239 衝突を生成する操作 決してそうすべきではありません パスワードに使用されます. 。ただし、SHA-1はaに対して脆弱です 同様の衝突攻撃 2で衝突が見つかります69 操作、ブルートフォースは2です80. 。誰もSHA-1衝突を生成していません NISTはまだSHA-1を安全なメッセージダイジェスト関数としてリストしています.

壊れたハッシュ関数を使用しても安全なのはいつですか？機能が壊れていても、「十分に大きい」ことがあります。 Schneierによると 衝突攻撃に対して脆弱なハッシュ関数は、 hmac. 。これは、HMACのセキュリティがその秘密の鍵に依存しており、この鍵が得られるまで衝突が見つからないためだと思います。 HMACでキーを使用すると、すでに壊れているため、それは論点です。 HMACのセキュリティを損なうハッシュ機能の脆弱性は何ですか？

このプロパティをもう少し進めましょう。塩がパスワードに加えられている場合、パスワードにMD4のような非常に弱いメッセージダイジェストを使用することは安全になりますか？ MD4およびMD5の攻撃は攻撃のプレフィックスであり、塩が準備されている場合、攻撃者はメッセージのプレフィックスを制御できません。塩が本当に秘密であり、攻撃者に知られていない場合、パスワードに追加されたかどうかは重要ですか？メッセージ全体が取得されるまで攻撃者が衝突を生成できないと想定しても安全ですか？

脆弱性を導入せずにセキュリティコンテキストで壊れたハッシュ関数を使用できる他のケースをご存知ですか？

（それが素晴らしいので、サポートの証拠を投稿してください！）

役に立ちましたか？

解決

実際、衝突は、MD5とSHA-1の両方にリストするものよりも簡単です。 MD5の衝突は、時間と同等の時間内に見つけることができます 226.5 操作（1つの「操作」は、短いメッセージでMD5の計算です）。見る このページ いくつかの詳細と攻撃の実装について（私はそのコードを書きました。64ビットモードで2.4 GHz Core2 X86で平均14秒以内に衝突が見つかります）。

同様に、SHA-1に対する最もよく知られている攻撃は 261 操作ではありません 269. 。それはまだ理論的です（実際の衝突はまだ生成されていません）が、それは実現可能な領域内にあります。

セキュリティへの影響については、ハッシュ関数には通常、3つのプロパティがあると言われています。

  • プリイメージなし：与えられます y, 、見つけることができてはなりません バツ そのような h（x）= y.
  • 2番目のプリイメージはありません：与えられます バツ1, 、見つけることができてはなりません バツ2 （とは異なります バツ1） そのような H（x1）= h（x2).
  • 衝突なし：何かを見つけることは実行可能ではありません バツ1 と バツ2 （互いに異なる）そのような H（x1）= h（x2).

aでハッシュ関数の場合 n- ビット出力、一般的な攻撃（ハッシュ関数の詳細に関係なく機能する）があります 2n 2つの最初のプロパティの操作、および 2n/2 3番目の操作。特定のハッシュ関数の場合、攻撃が見つかった場合、ハッシュ関数の動作方法の特別な詳細を活用することにより、対応する汎用攻撃よりも速くプリイメージ、2番目のプリイメージ、または衝突が見つかります。壊れる"。

ただし、ハッシュ関数のすべての使用法が3つのプロパティすべてに依存しているわけではありません。たとえば、デジタル署名は、署名されるデータをハッシュすることから始まり、ハッシュ値はアルゴリズムの残りの部分で使用されます。これは、プリイメージと2番目のプリイメージに対する抵抗に依存していますが、デジタル署名は衝突の影響を受けません。衝突は、攻撃者が被害者によって署名されるデータを選択できる特定の署名シナリオの問題である可能性があります（基本的に、攻撃者は衝突を計算し、被害者によって署名され、署名が有効になります他のメッセージも同様です）。これは、署名を計算する前に署名されたメッセージにランダムなバイトを準備することで打ち消すことができます（攻撃とX.509証明書のコンテキストで実証されているソリューション）。

HMACセキュリティは、に依存しています 他の ハッシュ関数が満たさなければならないプロパティ。すなわち、「圧縮関数」（ハッシュ関数が構築されている基本レンガ）は、 擬似ランダム機能 （PRF）。 PRFが何であるかの詳細は非常に技術的ですが、大まかに言えば、PRFはと区別できないはずです ランダムオラクル. 。ランダムオラクルは、ノーム、サイコロ、大きな本を含むブラックボックスとしてモデル化されています。いくつかの入力データで、GNOMEはランダム出力（サイコロを使用）を選択し、本に入力メッセージとランダムに選択された出力を書き留めます。 GNOMEは本を使用して、すでに同じ入力メッセージを見たかどうかを確認します。もしそうなら、GNOMEは以前よりも同じ出力を返します。構築により、試してみるまで、特定のメッセージにランダムオラクルの出力について何も知ることができません。

ランダムオラクルモデルにより、PRFの呼び出しでHMACセキュリティ証明を定量化できます。基本的に、PRFを大量に呼び出すことなくHMACを壊すことはできないという証明は、「巨大」とは計算的に実行不可能です。

残念ながら、ランダムなオラクルはありませんので、実際にはハッシュ関数を使用する必要があります。 PRFプロパティを使用して、Hash機能が実際に存在するという証拠はありません。現在、私たちには候補者のみがあります。つまり、それらの圧縮関数がPRFではないことを（まだ）証明することはできません。

もしも 圧縮関数はPRFです それから ハッシュ関数は、衝突に対して自動的に耐性があります。それはPRFの魔法の一部です。 したがって, 、ハッシュ関数の衝突を見つけることができれば、内部圧縮関数はPRFではないことがわかります。これにより、衝突がHMACへの攻撃に変わることはありません。自由に衝突を生成できることは、HMACを破るのに役立ちません。ただし、これらの衝突は、HMACに関連するセキュリティ証明が適用されないことを示しています。保証は無効です。これはラップトップコンピューターと同じです。ケースを開くと、必ずしもマシンが壊れるわけではありませんが、その後は自分で壊れています。

の中に Kim-Biryukov-Preneel-Hong 記事では、HMACに対するいくつかの攻撃が提示されます。特に、HMAC-MD4に対する偽造攻撃です。この攻撃は、MD4の欠点（その「弱点」）を活用して、それを非PRFにします。同じ弱点のバリエーションを使用してMD4の衝突を生成しました（MD4は完全に破損しています。一部の攻撃は、ハッシュ関数自体の計算よりも速く衝突を生成します！）。したがって、衝突はHMAC攻撃を意味するのではなく、両方の攻撃が同じソースに餌を与えます。ただし、偽造攻撃にはコストがあることに注意してください 258, 、これは非常に高いです（実際の偽造は生成されませんでした、結果はまだ理論的です）が、HMACから予想される抵抗レベルよりも大幅に低い（ n- ビット出力、HMACは抵抗する必要があります 2n 作業要因; n = 128 MD4の場合）。

したがって、衝突はそうではありません それ自体 HMACの弱点を暗示していると、彼らは悪いニュースです。実際には、衝突は非常に少ないセットアップにとって問題です。しかし、衝突がハッシュ関数の特定の使用に影響するかどうかを知ることは十分に注意が必要であり、衝突が実証されたハッシュ関数を使用し続けることはまったく賢明ではありません。

SHA-1の場合、攻撃は依然として理論的であり、SHA-1は広く展開されています。このような状況は次のように説明されています：「アラームはオンですが、目に見える火や煙はありません。出口に向かって歩く時が来ましたが、走るのではありません。」

主題の詳細については、の第9章を読むことから始めます 適用された暗号化のハンドブック, 、Menezes、Van Oorschot、およびVanstoneによると、見習い暗号学者の必見です（B. Schneierによる「適用された暗号」と混同しないでください。

他のヒント

壊れたハッシュ関数を使用しても安全なのは、ファイルシステム上のバケットにファイルを割り当てる場合、衝突の結果が無害または些細な場合です。

安全かどうかを気にしないとき。

真剣に、ほとんどすべての言語で安全なハッシュ関数を使用するために余分な努力が必要ではなく、パフォーマンスへの影響は無視できないので、なぜそうしないのかわかりません。

実際にあなたの質問を読んだ後に編集

Schneierによれば、共同攻撃に対して脆弱なハッシュ関数は、まだHMACとして使用できます。これは、HMACのセキュリティがその秘密の鍵に依存しており、この鍵が得られるまで衝突が見つからないためだと思います。

実際、それは本質的に、ハッシュの衝突を生成できることが必ずしもあなたが衝突を生成するのに役立つとは限らないからです ハッシュオブアハッシュ （HMACSが使用するXoringと組み合わせて）。

パスワードに塩が行われた場合、パスワードにMD4のような非常に弱いメッセージダイジェストを使用することは安全になりますか？

いいえ、ハッシュが持っている場合ではありません プリイメージ攻撃 これにより、データを入力にプリデントできます。たとえば、ハッシュがあった場合 H(pass + salt), 、Pass2を見つけることができるプリイメージ攻撃が必要です。 H(pass2 + salt) = H(pass + salt).

過去に追加の攻撃があったので、プレップエンド攻撃が可能であると確信しています。

ダウンロードサイトでは、MD5ハッシュをチェックサムとして使用して、ダウンロード中にファイルが破損したかどうかを判断します。壊れたハッシュはその目的で十分であると思います。

MITMがファイルを変更することを決定したとしましょう（たとえば、ZIPアーカイブ、またはEXEなど）。今、攻撃者は2つのことをしなければなりません -

  1. ハッシュ衝突を見つけて、それから修正されたファイルを作成します
  2. 新しく作成されたファイルであることを確認してください また〜だ 有効なexeまたはzipアーカイブ

ハッシュが壊れた場合、1は少し簡単です。しかし、衝突がファイルの他の既知のプロパティを同時に満たしていることを保証することは、計算的に高すぎます。

これは完全に私自身の答えであり、私はひどく間違っている可能性があります。

答えは、あなたがそれを使用しているものに完全に依存します。数ミリ秒で誰かが衝突を生み出すのを防ぐ必要がある場合、数十年以内に誰かが衝突を起こすのを防ぐ必要がある場合よりも心配することは少なくなります。

実際にどのような問題を解決しようとしていますか？

パスワードにMD4のようなものを使用することに関する心配のほとんどは、現在既知の攻撃に関連していません。一度衝突生成が簡単であるという点まで分析されると、一般に誰かがかなり高いと推定されると推定されます。その知識を使用してプリイメージ攻撃を作成することができます - そして、それが起こる場合/その場合、そのハッシュ関数のすべての可能な用途は脆弱になります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top