すべてのデータ行の主キーが次のように難読化されているデータベース駆動型の Web アプリケーションがあります: SHA256 (コンテンツ タイプ + 主キー + シークレット)、最初の 8 文字に切り捨てられます。コンテンツ タイプは、「投稿」や「メッセージ」などの単純な単語で、シークレットは 20 ～ 30 文字の ASCII 定数です。結果は、高速な DB ルックアップのために別のインデックス付きの列に格納されます。
このシナリオでハッシュ衝突の確率を計算するにはどうすればよいですか? 私はまったく数学者ではありませんが、友人は、誕生日のパラドックスにより、8 文字の切り捨てで 10,000 行の衝突確率が ~1% になると主張しました。この主張に真実はありますか？
はい、衝突の可能性があり、おそらくやや高すぎます。正確な確率は、「8 文字」が何を意味するかによって異なります。
「8文字」とは次のことを意味しますか:
バイナリ データを A) 16 進数または D) バイナリ バイトとして保存することは、私の好みのオプションです。しかし、「鍵の難読化」スキームを再検討するか、保存されている鍵のサイズを大幅に拡大して、鍵の衝突の (現在は過剰な) 可能性を減らすことを強くお勧めします。
ウィキペディアから: http://en.wikipedia.org/wiki/Birthday_problem#Cast_as_a_collision_problem
このより一般的な意味での誕生日の問題は、ハッシュ関数に適用されます。衝突が発生する前に生成できる N ビット ハッシュの予想数は 2^N ではなく、2^(N/2) のみです。
上記の最も保守的な設計の理解 (A、16 進数の 8 文字 == 32 ビットとして読み取る) では、スキーマが ~64,000 行のスケールで格納されている場合、スキームは衝突に苦しむことが予想されます。このような結果は、すべての本格的なシステム、またはおもちゃのシステムでさえ受け入れられないと考えています。
トランザクション テーブルにはボリュームがあり、1 日あたり 1000 ～ 100,000 トランザクション (またはそれ以上) のビジネスの成長を可能にします。システムは 100 年 (36500 日) 機能するように設計され、10 倍の成長因子が組み込まれている必要があります。
キーイング メカニズムが真に堅牢で専門的に有用であるためには、潜在的に最大 360 億 (2^35) 行を衝突なしで処理できるようにスケールアップできる必要があります。これは、70 ビット以上のハッシュを意味します。
たとえば、ソース管理システムの Git は、160 ビットの SHA-1 ハッシュ (40 文字の 16 進数 == 20 バイトまたは 160 ビット) を格納します。保存されているファイル リビジョンが 2^80 未満の場合、衝突の可能性は低いと予想されます。
キーを完全にハッシュして疑似ランダム化し、(希望に反して) 衝突を回避することを期待するよりも、ハッシュの 8 ～ 10 ビットをキーに追加/追加/折り畳むよりも、より良い設計の可能性があります。
これにより、元のキーのすべての一意性に加えて 8 ～ 10 ビットの検証を含む、より大きなキーが生成されます。その後、キーへのアクセス試行が検証され、無効なリクエストが 3 つを超えると、キースペースを「調査」してセキュリティを侵害しようとする試みとして扱われ、半永久的なロックアウトがトリガーされます。
ここでの唯一の主なコストは、指定された int-size で使用可能なキースペースのサイズがわずかに減少することです。ブラウザとの間の 32 ビット int には、セキュリティ専用の 8 ～ 10 ビットがあり、実際のキー用に 22 ～ 24 ビットが残されます。したがって、十分でない場合は 64 ビットの int を使用します。