コンピュータサイエンスにおいて、ハッシュ衝突またはハッシュクラッシュ[1]とは、ハッシュテーブル 内の2つの異なるデータが同じハッシュ値を共有することです。この場合のハッシュ値は、データ入力を受け取り、固定長のビットを返すハッシュ関数によって生成されます。[2]
ハッシュアルゴリズム、特に暗号ハッシュアルゴリズムは衝突耐性を考慮して開発されていますが、異なるデータを同じハッシュにマッピングしてしまう場合があります（鳩の巣原理による）。悪意のあるユーザーはこれを悪用して、データを模倣、アクセス、または改ざんすることができます。[3]
データ管理やコンピュータ セキュリティ(特に、暗号ハッシュ関数)においてハッシュ衝突が悪影響を及ぼす可能性があるため、衝突回避はコンピュータ セキュリティの重要なトピックになっています。
背景
ハッシュ衝突は、集合内のオブジェクトの数と、それらがマッピングされるビット文字列の長さが十分かどうかによって避けられない場合があります。オブジェクトの集合がある場合、が （この場合はハッシュ値の集合）より大きい場合、ハッシュ衝突は必ず発生します。 [4]
ハッシュ衝突がいつか起こりやすくなるもう一つの理由は、数学における誕生日のパラドックスという考え方から来ています。この問題は、一定数の人の中からランダムに選ばれた2人の組が同じ誕生日である確率を調べるものです。 [5]この考え方は、誕生日攻撃と呼ばれるものにつながっています。この攻撃の前提は、自分の誕生日や特定の誕生日と正確に一致する誕生日を見つけることは難しいが、一致する誕生日を持つ任意の2人の組を見つける確率は、その確率を大幅に高めるというものです。悪意のある人物はこのアプローチを使用することで、特定のハッシュ値を探すのではなく、他のハッシュ値と衝突するハッシュ値を見つけることをより簡単にすることができます。[6]
衝突の影響はアプリケーションによって異なります。ハッシュ関数やフィンガープリントが相同な DNA配列や類似の音声ファイルなどの類似データを識別するために使用される場合、これらの関数は、局所性依存ハッシュ法などの技術を用いて、異なるが類似するデータ間の衝突確率を最大化するように設計されます。[7]一方、チェックサムは、非常に異なる入力間の衝突を考慮せずに、類似する入力間の衝突確率を最小化するように設計されています。 [8]悪意のある人物がハッシュ衝突を作成または発見しようとする事例は、衝突攻撃として知られています。[9]
実際には、セキュリティ関連のアプリケーションでは、ランダムな一致が起きにくいほど十分に長く、どこでも使用できるほど高速で、衝突を見つけるのが極めて困難であるほど十分に安全な暗号ハッシュアルゴリズムが使用されています。[8]
衝突解決
ハッシュテーブルではハッシュ衝突は避けられないため、衝突解決と呼ばれるメカニズムがハッシュテーブルに備わっています。最も一般的な戦略は、オープンアドレッシングとセパレートチェイニングです。キャッシュを考慮した衝突解決は、文字列ハッシュテーブルにおいて過去に議論された別の戦略です。
オープンアドレス
この方法では、ハッシュテーブル内のセルに占有、空、削除の3つの状態のいずれかが割り当てられます。ハッシュ衝突が発生した場合、テーブルがプローブされ、レコードは空とされている別のセルに移動します。ハッシュ衝突が発生し、この方法が実装されている場合、さまざまな種類のプローブが実行されます。プローブの種類には、線形プローブ、二重ハッシュ、二次プローブなどがあります。[10]オープンアドレッシングはクローズドハッシュとも呼ばれます。[11]
分離連鎖
この戦略では、ハッシュテーブルのセルに複数のレコードを「連鎖」させることができます。2つのレコードが同じセルに向けられている場合、両方ともリンクリストとしてそのセルに格納されます。同じハッシュ値を持つレコードが同じセルに格納されるため、ハッシュ衝突の発生を効果的に防ぎますが、欠点もあります。多数のリストを管理するのは困難であり、使用するツールが非常に遅くなる可能性があります。[10]セパレートチェイニングはオープンハッシュとも呼ばれます。[12]
キャッシュを考慮した衝突解決
前述の2つに比べると利用度ははるかに低いものの、Askitis & Zobel (2005) は2005年にキャッシュを意識した衝突解決法を提案しました。 [13]これは、技術的には連鎖リストを必要としないものの、個別連鎖法に似た考え方です。この場合、連鎖リストの代わりに、ハッシュ値は連続した項目のリストで表現されます。これは文字列ハッシュテーブルに適しており、数値への応用はまだ知られていません。[10]
参照
- ユニバーサル一方向ハッシュ関数
- 暗号学 – 安全な通信技術の実践と研究
- ユニバーサルハッシュ – ハッシュ関数を選択するための手法
- 完全ハッシュ関数 – 衝突のないハッシュ関数
- 単射写像 – 一意性を保つ関数リダイレクト先の簡単な説明を表示するページ
参考文献
- ^ Thomas、Cormen (2009)、アルゴリズム入門、MIT Press、p. 253、ISBN 978-0-262-03384-8
- ^ Stapko, Timothy (2008)、「組み込みセキュリティ」、実践的な組み込みセキュリティ、Elsevier、pp. 83– 114、doi :10.1016/b978-075068215-2.50006-9、ISBN 9780750682152、 2021年12月8日取得
{{citation}}: CS1 maint: ISBNによる作業パラメータ（リンク） - ^ Schneier, Bruce . 「MD5とSHAの暗号解析：新たな標準の時代」. Computerworld . 2016年3月16日時点のオリジナルよりアーカイブ。 2016年4月20日閲覧。
暗号化アルゴリズムという枠を超えて、一方向ハッシュ関数は現代暗号の主力となっています。
- ^ サイバーセキュリティと応用数学. 2016. doi :10.1016/c2015-0-01807-x. ISBN 9780128044520。
- ^ ソルタニアン、モハマド・レザ・カリフェ（2015年11月10日）。DDoS攻撃に対する防御のための理論的および実験的手法。ISBN 978-0-12-805399-7. OCLC 1162249290。
- ^ Conrad, Eric; Misenar, Seth; Feldman, Joshua (2016)、「ドメイン3：セキュリティエンジニアリング（セキュリティのエンジニアリングと管理）」、CISSP学習ガイド、Elsevier、pp. 103– 217、doi :10.1016/b978-0-12-802437-9.00004-7、ISBN 9780128024379、 2021年12月8日取得
{{citation}}: CS1 maint: ISBNによる作業パラメータ（リンク） - ^ Rajaraman, A.; Ullman, J. (2010). 「大規模データセットのマイニング、第3章」
- ^ ab Al-Kuwari, Saif; Davenport, James H.; Bradford, Russell J. (2011). 暗号ハッシュ関数：最近の設計動向とセキュリティ概念. Inscrypt '10.
- ^ Schema, Mike (2012). Webアプリのハッキング.
- ^ abc Nimbe, Peter; Ofori Frimpong, Samuel; Opoku, Michael (2014-08-20). 「ハッシュテーブルにおける衝突解決のための効率的な戦略」. International Journal of Computer Applications . 99 (10): 35– 41. Bibcode :2014IJCA...99j..35N. doi : 10.5120/17411-7990 . ISSN 0975-8887.
- ^ Kline, Robert. 「Closed Hashing」. CSC241 データ構造とアルゴリズム. ウェストチェスター大学. 2022年4月6日閲覧。
- ^ 「オープンハッシュかセパレートチェーンか」Log 2 2 .
- ^ Askitis, Nikolas; Zobel, Justin (2005). Consens, M.; Navarro, G. (編). Cache-Conscious Collision Resolution in String Hash Tables . International Symposium on String Processing and Information Retrieval. String Processing and Information Retrieval SPIRE 2005 . Lecture Notes in Computer Science. Vol. 3772. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 91– 102. doi :10.1007/11575832_11. ISBN 978-3-540-29740-6。
外部リンク
