これはおそらく現実の世界ではまだ起こらなかったでしょうし、起こらないかもしれませんが、これを考えてみましょう：gitリポジトリがあり、コミットを行い、非常に不運になります：ブロブの1つが同じSHA-1を持つことになりますすでにリポジトリにある別のものとして。問題は、Gitがこれをどのように処理するかということです。単に失敗しますか？2つのブロブをリンクし、コンテキストに応じてどちらが必要かを確認する方法を見つけますか？
実際の問題よりも頭の体操ですが、この問題は興味深いものでした。
79081 次
6 に答える
790
この場合、Git がどのように動作するかを正確に調べるために実験を行いました。これはバージョン 2.7.9~rc0+next.20151210 (Debian 版) です。基本的に、次の差分を適用して git を再構築することで、ハッシュ サイズを 160 ビットから 4 ビットに減らしました。
--- git-2.7.0~rc0+next.20151210.orig/block-sha1/sha1.c
+++ git-2.7.0~rc0+next.20151210/block-sha1/sha1.c
@@ -246,6 +246,8 @@ void blk_SHA1_Final(unsigned char hashou
blk_SHA1_Update(ctx, padlen, 8);
/* Output hash */
- for (i = 0; i < 5; i++)
- put_be32(hashout + i * 4, ctx->H[i]);
+ for (i = 0; i < 1; i++)
+ put_be32(hashout + i * 4, (ctx->H[i] & 0xf000000));
+ for (i = 1; i < 5; i++)
+ put_be32(hashout + i * 4, 0);
}
その後、いくつかのコミットを行い、次のことに気付きました。
- 同じハッシュを持つ BLOB が既に存在する場合、警告はまったく表示されません。すべて問題ないように見えますが、プッシュしたり、誰かがクローンを作成したり、元に戻したりすると、最新バージョンが失われます (上記の説明に従って)。
- ツリー オブジェクトが既に存在し、同じハッシュで BLOB を作成した場合: プッシュを試みるか、誰かがリポジトリをクローンするまで、すべてが正常に見えます。次に、レポが破損していることがわかります。
- コミット オブジェクトが既に存在し、同じハッシュで BLOB を作成する場合: #2 と同じ - 破損
- BLOB が既に存在し、同じハッシュでコミット オブジェクトを作成すると、"ref" の更新時に失敗します。
- BLOB が既に存在し、同じハッシュでツリー オブジェクトを作成する場合。コミットの作成時に失敗します。
- ツリー オブジェクトが既に存在し、同じハッシュでコミット オブジェクトを作成すると、"ref" の更新時に失敗します。
- ツリー オブジェクトが既に存在し、同じハッシュでツリー オブジェクトを作成すると、すべて問題ないように見えます。しかし、コミットすると、すべてのリポジトリが間違ったツリーを参照します。
- コミット オブジェクトが既に存在し、同じハッシュでコミット オブジェクトを作成すると、すべて問題ないように見えます。ただし、コミットすると、コミットは作成されず、HEAD ポインターは古いコミットに移動します。
- コミット オブジェクトが既に存在し、同じハッシュでツリー オブジェクトを作成すると、コミットの作成時に失敗します。
#2 では、通常、「git push」を実行すると、次のようなエラーが発生します。
error: object 0400000000000000000000000000000000000000 is a tree, not a blob
fatal: bad blob object
error: failed to push some refs to origin
また：
error: unable to read sha1 file of file.txt (0400000000000000000000000000000000000000)
ファイルを削除してから「git checkout file.txt」を実行すると。
#4 と #6 の場合、通常、次のようなエラーが発生します。
error: Trying to write non-commit object
f000000000000000000000000000000000000000 to branch refs/heads/master
fatal: cannot update HEAD ref
「git commit」の実行時。この場合、新しいハッシュが作成されるため、通常は「git commit」と入力するだけで済みます (タイムスタンプが変更されるため)。
#5 と #9 の場合、通常、次のようなエラーが発生します。
fatal: 1000000000000000000000000000000000000000 is not a valid 'tree' object
「git commit」実行時
破損したリポジトリのクローンを作成しようとすると、通常、次のようなメッセージが表示されます。
git clone (one repo with collided blob,
d000000000000000000000000000000000000000 is commit,
f000000000000000000000000000000000000000 is tree)
Cloning into 'clonedversion'...
done.
error: unable to read sha1 file of s (d000000000000000000000000000000000000000)
error: unable to read sha1 file of tullebukk
(f000000000000000000000000000000000000000)
fatal: unable to checkout working tree
warning: Clone succeeded, but checkout failed.
You can inspect what was checked out with 'git status'
and retry the checkout with 'git checkout -f HEAD'
私が「心配している」のは、2 つのケース (2,3) では警告なしにリポジトリが破損し、3 つのケース (1,7,8) ではすべて問題ないように見えますが、リポジトリの内容が予想とは異なることです。することが。人々のクローンやプルには、あなたが持っているものとは異なるコンテンツがあります。ケース 4、5、6、および 9 は、エラーで停止するので問題ありません。せめて全てエラーで失敗した方が良いと思います。
于 2016-01-04T20:15:12.333 に答える
247
元の回答 (2012) (shattered.io以下の 2017 SHA1 衝突を参照)
Linusからの古い (2006) 回答はまだ関連している可能性があります。
いいえ。同じ SHA1 を持っている場合、相手からオブジェクトを受け取ったときに、既に持っているオブジェクトを上書きしないことを意味します。
したがって、衝突が発生した場合、特定のリポジトリ内の「以前の」オブジェクトが常にオーバーライドされることになります。ただし、git オブジェクト ネットワークが完全に順序付けされていない DAG を生成するという意味で、「以前」は明らかにリポジトリごとであることに注意してください。オブジェクトは別々の分岐を経由しており、直接関連していないため、2 つの異なるリポジトリが 2 つのオブジェクトを異なる順序で取得した可能性があります。
ただし、セキュリティの観点からは、「早期にオーバーライドする」ことが非常に重要です。git モデルでは、主に自分のリポジトリのみを信頼する必要があることを思い出してください。
したがって、"git pull" を実行すると、新しく入ってくるオブジェクトは定義上、既に持っているオブジェクトよりも信頼性が低くなります。そのため、古いオブジェクトを新しいオブジェクトに置き換えることを許可するのは正しくありません。したがって、衝突の 2 つのケースがあります。
何らかの形で非常に不運であり、2 つのファイルが同じ SHA1 を持つことになる不注意な種類です。
その時点で、そのファイルをコミットすると (または "git-update-index" を実行してインデックスに移動するが、まだコミットされていない場合)、新しいコンテンツの SHA1 が計算されますが、古いオブジェクトと一致するため、新しいオブジェクトは作成されず、 commit-or-index は古いobjectを指すことになります。
すぐには気付かないでしょう (インデックスは古いオブジェクト SHA1 と一致し、それは "git diff" のようなものがチェックアウトされたコピーを使用することを意味するため) が、ツリー レベルの diff を実行した場合 (またはクローンを実行した場合)またはプルするか、チェックアウトを強制する）、そのファイルが何かに変更されたことに突然気付くでしょうあなたが予想していたものとはまったく異なります。
したがって、通常、この種の衝突はかなり早く気付くでしょう。
関連ニュースでは、問題は不注意による衝突をどうするかということです..
まず最初に、不注意による衝突は本当に非常にありそうにないことを人々に思い出させてください。宇宙の。
しかし、それが起こったとしても、それは世界の終わりではありません:あなたがしなければならないことは、わずかに衝突したファイルを変更し、変更された内容で新しいコミットを強制することです(" " というコメントを追加します/* This line added to avoid collision */) 。次に、危険であることが示されている魔法の SHA1 について git に教えます。
したがって、200 万年以上経つと、1 つまたは 2 つの「毒された」SHA1 値を git に追加する必要があるかもしれません。メンテナンスの問題である可能性は非常に低いです;）攻撃者は、誰かが SHA1 を壊した (または力ずくで) 壊したため、一種の衝突を起こしました。
これは明らかに不注意によるものよりも可能性が高いですが、定義上、常に「リモート」リポジトリです。攻撃者がローカル リポジトリにアクセスできれば、もっと簡単にあなたをだますことができます。
したがって、この場合、衝突はまったく問題ではありません。攻撃者が意図したものとは異なる「悪い」リポジトリが得られますが、衝突するオブジェクトを実際に使用することはないため、文字通り、攻撃者は衝突をまったく発見していないだけです、しかし、あなたがすでに持っていたオブジェクトを使用しているだけです（つまり、同じSHA1を生成する同一のファイルの「些細な」衝突と100％同等です）。
SHA-256 の使用に関する質問は定期的に言及されていますが、現時点では対応していません (2012 年)。
注: 2018 および Git 2.19以降、コードは SHA-256 を使用するようにリファクタリングされています。
注 (ユーモア): Brad Fitzpatrick ( )のプロジェクトgitbruteを使用して、特定の SHA1プレフィックスへのコミットを強制できます。bradfitz
gitbrute は、作成者とコミッターのタイムスタンプのペアを総当たりして、結果の git コミットに目的のプレフィックスが含まれるようにします。
例: https://github.com/bradfitz/deadbeef
Daniel Dinnyesは7.1 Git Tools - Revision Selectionへのコメントで次のように指摘しています。
同じ夜に、プログラミング チームのすべてのメンバーがオオカミに襲われて殺される可能性が高くなります。
さらに最近 (2017 年 2 月)shattered.ioは、SHA1 衝突を偽造する可能性を示しました:
( Linus Torvalds の Google+ 投稿を含む、私の別の回答で詳細を参照してください)
- a/ それでも 9,223,372,036,854,775,808 回を超える SHA1 計算が必要です。これは、シングル CPU 計算で 6,500 年、シングル GPU 計算で 110 年分の処理能力を必要としました。
- b/ は1 つのファイルを (同じ SHA1 で) 偽造しますが、追加の制約により、そのコンテンツとサイズは同一の SHA1 を生成します (コンテンツの衝突だけでは十分ではありません): 「git ハッシュはどのように計算されますか?」を参照してください) 。 : blob SHA1 は、コンテンツとサイズに基づいて計算されます。
詳細については、 Valerie Anita Auroraの「暗号化ハッシュ関数の有効期間」を参照してください。
そのページで、彼女は次のように述べています。
Google は 6500 CPU 年と 110 GPU 年を費やして、セキュリティ クリティカルなアプリケーションでの SHA-1 の使用をやめる必要があるすべての人を説得しました。
それもかっこよかったから
以下の私の別の回答で詳細を参照してください。
于 2012-02-22T09:53:05.517 に答える
42
プロGitによると：
リポジトリ内の以前のオブジェクトと同じ SHA-1 値にハッシュされるオブジェクトをコミットした場合、Git は以前のオブジェクトが既に Git データベースにあることを確認し、既に書き込まれていると見なします。ある時点でそのオブジェクトを再度チェックアウトしようとすると、常に最初のオブジェクトのデータが取得されます。
したがって、失敗することはありませんが、新しいオブジェクトも保存されません。
コマンドラインでそれがどのように見えるかはわかりませんが、確かに混乱するでしょう.
もう少し下では、同じ参照がそのような衝突の可能性を説明しようとしています:
以下は、SHA-1 衝突が発生するのに何が必要かを示す例です。地球上の 65 億人全員がプログラミングを行っており、毎秒、Linux カーネルの全履歴 (100 万個の Git オブジェクト) に相当するコードを生成し、それを 1 つの巨大な Git リポジトリにプッシュしている場合、そのリポジトリには、単一の SHA-1 オブジェクト衝突の 50% の確率を持つ十分なオブジェクトが含まれていました。同じ夜に、プログラミング チームのすべてのメンバーがオオカミに襲われて殺される可能性が高くなります。
于 2012-02-22T09:52:42.757 に答える
6
暗号学者は喜ぶと思います。
SHA-1 に関するウィキペディアの記事からの引用:
2005 年 2 月、Xiaoyun Wang、Yiqun Lisa Yin、Hongbo Yu による攻撃が発表されました。攻撃は SHA-1 のフル バージョンで衝突を検出でき、必要な操作は 2^69 未満です。(ブルート フォース検索には 2^80 の操作が必要です。)
于 2012-02-22T10:37:34.917 に答える