database-design - ハッシュ衝突-チャンスは何ですか？

Question

PHPを利用したサイトに（を使用してsha1()）ランダムハッシュを作成するコードがあり、それを使用してデータベース内のレコードを照合します。

衝突の可能性は何ですか？ハッシュを生成する必要がある場合は、最初にデータベースにあるかどうかを確認するか（余分なクエリを避けたい）、他のハッシュと衝突しない可能性に基づいて自動的に挿入します。

score 28 · Accepted Answer

SHA-1が適切に機能すると仮定すると、2つのメッセージが同じハッシュを持つ可能性は2 ^ 160分の1であると結論付けることができます（SHA-1は160ビットのハッシュを生成するため）。

2^160は途方もなく大きな数です。およそ10^48です。データベースに100万のエントリがある場合でも、新しいエントリが同じハッシュを共有する可能性は10^42分の1です。

SHA-1はかなり良いことが証明されているので、衝突について心配する必要はまったくないと思います。

補足として、SHA-1を使用する場合はPHPのraw_output機能を使用してください。これにより、文字列が短くなり、データベース操作が少し速くなります。

編集：誕生日のパラドックスに対処するために、10 ^ 18（1億万）のエントリを持つデータベースには、衝突の0.0000000000003に約1の確率があります。本当に心配する価値はありません。

score 16 · Accepted Answer

ID (およびその他の値) をクライアントに送信するときに対称暗号化スキームとプライベートサーバーキーを使用して暗号化し、受信時に再度復号化します。暗号化関数が機密性と整合性の両方のチェックを提供するように注意してください。

これにより、衝突なしで DB と対話するときに適切な値を使用でき、クライアントと対話するときに優れたセキュリティを実現し、dailyWTFに到達する可能性を約 2^160 減らすことができます。

くぎを叩く: 古い靴かガラス瓶か?も参照してください。!

score 14 · Accepted Answer

衝突が発生しないことを保証するだけでなく、GETパラメータを変更して、表示すべきでないものを表示できないようにすることもできません。ソルトを使用して、IDとそのハッシュを組み合わせます。

$salt = "salty";
$key = sha1($salt . $id) . "-" . $id;
// 0c9ab85f8f9670a5ef2ac76beae296f47427a60a-5

（ソルトを使用して）まったく同じsha1ハッシュを持つ2つの数値に偶然遭遇した場合でも、$ keyは異なり、すべての衝突を回避できます。

score 5 · Accepted Answer

入力として数値的に増加するIDを使用する場合、SHA-1が衝突する可能性は実質的にゼロです。

IDが唯一の入力である場合、SHA-1はかなりやり過ぎのようです。32ビット整数から160ビットハッシュを生成します。むしろ、べき乗剰余を使用します。たとえば、大きな（32ビット）プライムpを選択し、そのグループのべき乗ジェネレータgを計算してから、g^idを使用します。これにより、衝突が発生しないことが保証され、32ビットの「ハッシュ」のみが提供されます。

score 4 · Accepted Answer

SHA-1は160ビット長のダイジェストを生成します。したがって、エントリが2 ^（160/2）未満である限り、安全です。2による除算は、誕生日のパラドックスによるものです。

score 4 · Accepted Answer

第一原理から：

SHA-1は160ビットのダイジェストを生成します。ビットスペース全体を均等に使用すると仮定すると（おそらくそれが設計されたものです）、衝突が発生する可能性は各インサートで2^-160の確率にすぎません。

したがって、挿入ごとに、衝突がないと想定し、衝突がある場合はエラーに対処するのが安全です。

それはあなたが衝突の可能性を完全に無視できるということではありません。

誕生日のパラドックスは、O（N ^ 2）の衝突の可能性があるため、データベースに少なくとも1つの衝突が発生する可能性が予想よりも高いことを示しています。

score 1 · Accepted Answer

衝突が発生した場合、どのくらいの費用がかかりますか？これが無料のサイトであれば問題ありません。あなたが金儲けのビジネスを営んでいて、オーバーライトがあなたに百万ドルの契約を要するなら、私はもう一度考えます。

私はあなたがこれについて間違った方法で行っていると思います。
一意のIDを保持する必要があると思いますが、ユーザーがIDを手動で変更できないようにする必要があります。

これを行う1つの方法は、IDとIDのハッシュ（いくつかの追加データを含む）をリンクに配置することです。

例:(私のPHPは錆びているので、一般的なアルゴリズムは次のようになります:)

id   = 5;
hash = hash("My Private String " + id)
link = "http://mySite.com/resource?id=" + id + "&hash=" + hash

次に、リクエストを受け取ったら、IDからハッシュを再生成できることを検証します。これにより、「マイプライベート文字列」を解決するための攻撃にさらされる可能性がありますが、計算が非常に難しく、ユーザーが直接利用できない独自の何か（セッションIDなど）をいつでも追加できます。

score 0 · Accepted Answer

ここで sha1() が問題を引き起こすとは思いません。弱い乱数生成は、衝突の可能性が高い候補です。

Stefan Esser は、このトピックに関する優れた記事を書きました。

score 0 · Accepted Answer

他のコメントは確率について説明しましたが、これを実際的に見ると、明確な答えを得ることができます。

あなたは、連続した ID をハッシュするつもりだと自分自身に言いました。テストケースをコーディングするのは簡単です。~100,000,000 の ID を反復処理し、衝突をチェックします。それにはそれほど時間はかかりません。一方、途中でメモリが不足する可能性があります。

database-design - ハッシュ衝突-チャンスは何ですか？

11 に答える 11

Related

Reference