7

ある特定の価値の独自性に依存する多くのシステムがあります。GUIDを使用するもの（Windowsレジストリやその他のデータベースなど）だけでなく、オブジェクトを識別するためにオブジェクトからハッシュを作成するため、このハッシュが一意である必要があるものも思い浮かびます。

ハッシュテーブルは通常、2つのオブジェクトが同じハッシュを持っているかどうかを気にしません。これは、ハッシュがオブジェクトをカテゴリに分類するために使用されるため、ルックアップ時に、テーブル内のすべてのオブジェクトではなく、同じカテゴリ内のオブジェクトのみが含まれるためです（バケット）は、検索されたオブジェクトとの同一性を比較する必要があります。

ただし、他の実装は（そう思われる）一意性に依存します。私の例（これが私にこれを尋ねさせる理由です）は、MercurialのリビジョンIDです。Mercurialメーリングリストのエントリには、正しく記載されています

最初の10億回のコミットで、チェンジセットハッシュが偶然に衝突する確率は基本的にゼロです。しかし、それが起こるかどうかはわかります。そして、あなたは偶然にSHA1を壊した男として有名になるでしょう。

しかし、最も小さな確率でさえ不可能を意味するわけではありません。さて、なぜ一意性に依存してもまったく問題がないのかについての説明は必要ありません（これについては、たとえばここで説明しました）。これは私には非常に明白です。

むしろ、私は知りたいです（多分あなた自身の仕事からの例によって）：

  • とにかく、これらのありそうもないケースをカバーするためのベストプラクティスはありますか？

  • 特に強い太陽風がハードディスクの読み取りに失敗する可能性が高いため、無視する必要がありますか？

  • ユーザーへの「私はあきらめます、あなたは不可能なことをしました」というメッセージで失敗するだけなら、少なくともそれらをテストする必要がありますか？

  • それとも、これらのケースでさえ適切に処理する必要がありますか？

私にとって、特に以下は興味深いものですが、やや手触りが良いです。

  • あなたがこれらのケースを処理しない場合、あなたは確率に耳を傾けない腸の感情に対して何をしますか？

  • あなたがそれらを処理する場合、スーパーノンバのようにあなたが処理しない可能性の高いケースがあることを考慮して、この作業を（あなた自身と他の人に）どのように正当化しますか？

4

2 に答える 2

7
  • あなたがそれらを処理する場合、超新星のようにあなたが処理しない可能性の高いケースがあることを考慮して、この作業を（あなた自身と他の人に）どのように正当化しますか？

その答えは、偶然に発生したGUIDの衝突を見つけるためのテストではないということです。GUIDコードのバグ、またはGUIDコードが違反した（または一部の攻撃者によってだまされて違反した）ことをGUIDコードが依存しているという前提条件（V1のMACなど）が原因で発生するGUIDの衝突を特定するためにテストしています。アドレスは一意であり、時間が進みます。どちらも、超新星ベースのバグよりもかなり可能性が高いです。

ただし、GUIDコードのすべてのクライアントが、特に本番コードでその正確性をテストする必要があるわけではありません。それが単体テストが行​​うことになっていることなので、実際の使用でキャッチできるバグを見逃すコストと、ライブラリを常に推測するコストとのトレードオフを行います。

GUIDは、GUIDを生成するすべての人が協力する場合にのみ機能することにも注意してください。アプリがカウントロールするマシンでIDを生成する場合は、とにかくGUIDは必要ない可能性があります。インクリメントカウンターのようなローカルで一意のIDで問題ない場合があります。明らかに、Mercurialはそれを使用できないため、ハッシュを使用しますが、最終的にSHA-1は衝突（またはさらに悪いことに、プレイメージ）を生成する攻撃に陥り、変更する必要があります。

クライアントなど、制御できないマシンでアプリがハッシュ以外の「GUID」を生成し、偶発的な衝突を忘れた場合、サーバーをDOSしようとする悪意のあるクライアントによる意図的な衝突が心配になります。それから身を守ることは、とにかく事故からあなたを守るでしょう。

  • それとも、これらのケースでさえ適切に処理する必要がありますか？

これに対する答えはおそらく「いいえ」です。ハッシュテーブルのように、衝突するGUIDを適切に処理できるのであれば、なぜGUIDを気にする必要があるのでしょうか。「識別子」の要点は、2つのものが同じIDを持っている場合、それらは同じであるということです。それらを同じように扱いたくない場合は、最初にハッシュテーブルのようにバケットにそれらを向けてから、別のスキーム（ハッシュなど）を使用します。

于 2009-07-08T13:09:29.360 に答える
4

優れた128ビットハッシュが与えられた場合、ランダムな入力が与えられた場合に特定のハッシュ値と衝突する可能性は次のとおりです。

1 / 2 ** 128これはほぼに等しい3 * 10 ** -39。

誕生日の問題pを説明するために使用されるロジックを使用して、サンプルが与えられたときに衝突が発生しない確率（ ）nを計算できます。

p = (2 ** 128)! / (2 ** (128 * n) * (2 ** 128 - n)!)

ここで、!は階乗関数を示します。次に、サンプル数が増えるにつれて衝突が発生しない確率をプロットできます。

サンプル数の増加に伴うランダムなSHA-1衝突の確率。http://img21.imageshack.us/img21/9186/sha1collision.png

10**17とハッシュの間で10**18、0.001％から0.14％まで、そして最後に10**19ハッシュで13％まで、衝突の重要な可能性が見られ始めます。したがって、100万、10億のシステムでは、一意性を考慮したレコードはおそらく賢明ではありません（そのようなシステムは考えられます）が、大多数のシステムでは、衝突の可能性が非常に小さいため、ハッシュの一意性に依存できます。すべての実用的な目的のために。

理論はさておき、バグや誰かがシステムを攻撃することで衝突がシステムに導入される可能性がはるかに高いため、偶発的な衝突の可能性はほとんどありませんが、一人一人の答えが衝突をチェックする正当な理由を提供します（つまり、バグや悪意の可能性は、偶発的な衝突よりもはるかに高いということです）。

于 2009-07-08T19:32:40.153 に答える