210

git の使用中にハッシュ衝突が発生した場合、実際にはどうなりますか?

たとえば、同じ sha1 チェックサムで 2 つのファイルをコミットできた場合、git はそれを認識したり、ファイルの 1 つを破損したりしますか?

それに対応するためにgitを改善できますか、それとも新しいハッシュアルゴリズムに変更する必要がありますか?

（それがどれほどありそうもないかについて議論して、この質問をそらさないでください-ありがとう）

4

9 に答える 9

133

10個の月で原子を拾う

SHA-1 ハッシュは 40 の 16 進文字列です... これは、1 文字あたり 4 ビット× 40... 160 ビットです。これで、10 ビットが約 1000 (正確には 1024) であることがわかりました。これは、1 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 の異なる SHA-1 ハッシュがあることを意味します... 10 48 .

これは何に相当しますか？月は約 10 47個の原子でできています。10 個の月があり、これらの月の 1 つでランダムに 1 つの原子を選択し、それらの衛星でランダムな原子をもう一度選択すると、同じ原子を 2 回選択する可能性が高くなります。は、与えられた 2 つの git コミットが同じ SHA-1 ハッシュを持つ可能性です。

これを拡張すると、質問をすることができます...

衝突を心配し始める前に、リポジトリにいくつのコミットが必要ですか?

これは、いわゆる「誕生日攻撃」に関連しており、「誕生日のパラドックス」または「誕生日問題」を指します。これは、特定のセットからランダムに選択すると、驚くほど少数の選択が必要になる前に、可能性が高くなるということです。何かを二度選んだこと。しかし、「驚くほど少ない」というのは、ここでは非常に相対的な用語です。

ウィキペディアには、誕生日のパラドックスの衝突確率に関する表があります。40 文字のハッシュのエントリはありません。しかし、32 文字と 48 文字のエントリを補間すると、衝突の確率が 0.1% の 5*10 22 git commit の範囲になります。これは、衝突が発生する可能性が 0.1% に達する前に、50 千億の異なるコミット、または 50 のZettacommitに相当します。

これらのコミットのハッシュだけのバイト合計は、1 年間に地球上で生成されるすべてのデータよりも多くのデータになります。つまり、YouTube がビデオをストリーミングするよりも速くコードを量産する必要があるということです。頑張ってください。:D

これの要点は、誰かが故意に衝突を引き起こしていない限り、衝突がランダムに発生する確率は驚くほど小さいため、この問題を無視できるということです。

「しかし、衝突が発生した場合、実際には何が起こるのでしょうか?」

OK、ありそうもないことが起こったと仮定するか、誰かが意図的に SHA-1 ハッシュ衝突を調整したとします。その後どうなりますか？

その場合、誰かが実験した優れた答えがあります。私はその答えから引用します：

  1. 同じハッシュを持つ BLOB が既に存在する場合、警告はまったく表示されません。すべて問題ないように見えますが、プッシュしたり、誰かがクローンを作成したり、元に戻したりすると、最新バージョンが失われます (上記の説明に従って)。
  2. ツリー オブジェクトが既に存在し、同じハッシュで BLOB を作成した場合: プッシュを試みるか、誰かがリポジトリをクローンするまで、すべてが正常に見えます。次に、レポが破損していることがわかります。
  3. コミット オブジェクトが既に存在し、同じハッシュで BLOB を作成する場合: #2 と同じ - 破損
  4. BLOB が既に存在し、同じハッシュでコミット オブジェクトを作成すると、"ref" の更新時に失敗します。
  5. BLOB が既に存在し、同じハッシュでツリー オブジェクトを作成する場合。コミットの作成時に失敗します。
  6. ツリー オブジェクトが既に存在し、同じハッシュでコミット オブジェクトを作成すると、"ref" の更新時に失敗します。
  7. ツリー オブジェクトが既に存在し、同じハッシュでツリー オブジェクトを作成すると、すべて問題ないように見えます。しかし、コミットすると、すべてのリポジトリが間違ったツリーを参照します。
  8. コミット オブジェクトが既に存在し、同じハッシュでコミット オブジェクトを作成すると、すべて問題ないように見えます。ただし、コミットすると、コミットは作成されず、HEAD ポインターは古いコミットに移動します。
  9. コミット オブジェクトが既に存在し、同じハッシュでツリー オブジェクトを作成すると、コミットの作成時に失敗します。

ご覧のとおり、一部のケースは良くありません。特にケース #2 と #3 はリポジトリを台無しにします。ただし、障害はそのリポジトリ内にとどまっているようであり、攻撃または奇妙な可能性は他のリポジトリには伝播しません。

また、意図的な衝突の問題が現実の脅威として認識されつつあるようで、例えばGitHubはそれを防ぐための対策を講じています.

于 2014-04-23T19:09:30.457 に答える
67

2つのファイルのgitのハッシュサムが同じである場合、それらのファイルは同一として扱われます。非常にまれなケースですが、これが発生した場合は、いつでも1つのコミットに戻って、ファイル内の何かを変更して、それらが衝突しないようにすることができます...

スレッド「sha-256について考え始めましたか？」のLinusTorvaldsの投稿を参照してください。gitメーリングリストで。

于 2012-05-03T15:31:15.427 に答える
25

なぜそれが問題ではないのかを説明せずに、この質問に正しい「しかし」で答えることは実際には不可能です. ハッシュが実際に何であるかをよく理解していなければ、それを行うことはできません。これは、CS プログラムで遭遇した可能性のある単純なケースよりも複雑です。

ここに情報理論の基本的な誤解があります。いくらかの量 (つまりハッシュ) を破棄して大量の情報を少量に減らすと、データの長さに直接関連する衝突の可能性があります。データが短いほど、可能性は低くなります。現在、衝突の大部分は意味不明であり、実際に発生する可能性がはるかに高くなります (意味不明なことをチェックインすることはありません... バイナリ イメージでさえ構造化されています)。結局、可能性は限りなく低い。あなたの質問に答えるには、はい、git はそれらを同じものとして扱います。ハッシュ アルゴリズムを変更しても役に立ちません。何らかの「2 回目のチェック」が必要になりますが、最終的には「追加のチェック」データが必要になります。データの長さは 100% 確実なので... 99.99999 になることを覚えておいてください.... 本当に長い桁数に....あなたが説明したような簡単なチェックで確認してください。SHA-x は暗号学的に強力なハッシュです。つまり、互いに非常に似ていて同じハッシュを持つ 2 つのソース データ セットを意図的に作成することは一般的に難しくありません。データの 1 ビットの変更は、ハッシュ出力に複数の (できればできるだけ多くの) ビットの変更を作成する必要があります。これは、ハッシュから完全なセットの完全なセットに戻ることも非常に困難であることを意味します (ただし、まったく不可能ではありません)。衝突、それによってその一連の衝突から元のメッセージを引き出します-いくつかを除いてすべてが意味不明であり、メッセージの長さがかなりの長さである場合、ふるいにかけられる膨大な数の衝突がないものもあります。暗号ハッシュの欠点は、計算が遅いことです...一般的に。

では、それは Git にとって何を意味するのでしょうか? あまりない。ハッシュは (他のすべてに比べて) めったに実行されないため、操作に対する計算上のペナルティは全体的に低くなります。衝突のペアが発生する可能性は非常に低いため、発生してすぐに検出されない可能性は現実的ではなく (つまり、コードのビルドが突然停止する可能性が最も高い)、ユーザーは問題を修正できます (リビジョンをバックアップし、変更を再度行うと、時間の変更により、ほぼ確実に異なるハッシュが得られます。これは、git にもハッシュをフィードします)。任意のバイナリを git に保存している場合、実際の問題になる可能性が高くなります。これは、実際には主な使用モデルではありません。それを行いたい場合は、おそらく従来のデータベースを使用する方がよいでしょう。

これについて考えるのは間違いではありません。多くの人が「考える価値がない可能性が非常に高い」と見ているのは良い質問ですが、実際にはそれよりも少し複雑です。発生した場合、それは非常に簡単に検出できるはずであり、通常のワークフローではサイレントな破損にはなりません。

于 2013-06-30T00:03:42.863 に答える
9

それに対応するためにgitを改善できますか、それとも新しいハッシュアルゴリズムに変更する必要がありますか?

衝突はどのハッシュ アルゴリズムでも発生する可能性があるため、ハッシュ関数を変更しても問題が解消されるわけではなく、発生する可能性が低くなるだけです。したがって、本当に優れたハッシュ関数を選択する必要があります（SHA-1はすでにありますが、言われないように頼みました:)

于 2012-05-03T15:26:45.637 に答える
1

ハッシュの衝突が起こる可能性は非常に低いため、まったく気が狂いそうです! 世界中の科学者がこれを達成しようと懸命に努力していますが、まだ達成できていません。ただし、MD5 などの特定のアルゴリズムでは成功しました。

オッズは？

SHA-256には 2^256 の可能なハッシュがあります。それは約10^78です。または、より具体的に言うと、衝突の可能性は約

1 : 100 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000

宝くじの当選確率は約1:14澪です。SHA-256 との衝突の可能性は、11 日連続で宝くじに当選したようなものです。

数学的な説明: 14 000 000 ^ 11 ~ 2^256

さらに、宇宙には約10^80個の原子があります。これは、SHA-256 の組み合わせの 100 倍です。

MD5 衝突の成功

MD5の場合でも、可能性はわずかです。ただし、数学者は衝突を作成することに成功しました。

d131dd02c5e6eec4 693d9a0698aff95c 2fcab5 8 712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325 7 1415a 085125e8f7cdc99f d91dbdf280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2 b 487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080 80d1e c69821bcb6a88393 96f965 2 b6ff72a70

と同じ MD5 を持っています

d131dd02c5e6eec4 693d9a0698aff95c 2fcab5 0 712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325 f 1415a 085125e8f7cdc99f d91dbd7280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2 3 487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080 2 80d1e c69821bcb6a88393 96f965 b6ff72a70

これは、MD5 のアルゴリズムがクラックされたために安全性が低下したという意味ではありません。意図的に MD5 衝突を作成することはできますが、MD5 衝突が偶発的に発生する可能性は依然として 2^128 であり、これは依然として大きいです。

結論

衝突について心配する必要はありません。ハッシュ アルゴリズムは、ファイルの同一性をチェックする 2 番目に安全な方法です。より安全な唯一の方法は、バイナリ比較です。

于 2015-03-19T13:50:20.620 に答える