Loading article…
コンピュータサイエンスにおいて、ハッシュ衝突またはハッシュクラッシュ[1]とは、ハッシュテーブル 内の2つの異なるデータが同じハッシュ値を共有することです。この場合のハッシュ値は、データ入力を受け取り、固定長のビットを返すハッシュ関数から導出されます。[2]
ハッシュアルゴリズム、特に暗号ハッシュアルゴリズムは衝突耐性を持たせることを目的として作成されていますが、異なるデータを同じハッシュにマッピングしてしまうことがあります（鳩の巣原理による）。悪意のあるユーザーはこれを利用してデータを模倣、アクセス、または変更することができます。[3]
データ管理やコンピュータ セキュリティ(特に、暗号ハッシュ関数)におけるハッシュ衝突の潜在的な悪影響のため、衝突回避はコンピュータ セキュリティにおける重要なトピックとなっています。
背景
ハッシュ衝突は、セット内のオブジェクトの数と、それらがマッピングされるビット文字列の長さが十分かどうかに応じて避けられない場合があります。n個のオブジェクトのセットがある場合、nが| R |（この場合、Rはハッシュ値の範囲）より大きい場合、ハッシュ衝突が発生する確率は1であり、確実に発生することを意味します。[4]
ハッシュ衝突がいつか起こりやすいもう一つの理由は、数学における誕生日のパラドックスという考え方から来ています。この問題は、 n人の中からランダムに選ばれた 2 人の誕生日が同じである確率を調べます。 [5]この考え方は、誕生日攻撃と呼ばれるものにつながっています。この攻撃の前提は、自分の誕生日や特定の誕生日と正確に一致する誕生日を見つけることは難しいが、一致する誕生日を持つ任意の 2 人の集合を見つける確率は、その確率を大幅に高めるというものです。悪意のある人物は、このアプローチを使用して、特定の値を検索するのではなく、他のハッシュ値と衝突するハッシュ値を簡単に見つけることができます。[6]
衝突の影響はアプリケーションによって異なります。ハッシュ関数とフィンガープリントが相同な DNA配列や類似のオーディオ ファイルなどの類似データを識別するために使用される場合、関数は、局所性に敏感なハッシュなどの技術を使用して、異なるが類似するデータ間の衝突の確率を最大化するように設計されています。[7]一方、チェックサムは、非常に異なる入力間の衝突を考慮せずに、類似の入力間の衝突の確率を最小限に抑えるように設計されています。 [8]悪意のある人物がハッシュ衝突を作成または発見しようとするインスタンスは、衝突攻撃として知られています。 [9]
実際には、セキュリティ関連のアプリケーションでは、ランダムな一致が起きにくいほど十分に長く、どこでも使用できるほど高速で、衝突を見つけるのが極めて困難であるほど十分に安全な暗号化ハッシュアルゴリズムが使用されています。[8]
衝突解決
ハッシュ テーブルではハッシュ衝突は避けられないため、衝突解決と呼ばれる衝突に対処するメカニズムがハッシュ テーブルに用意されています。最も一般的な 2 つの戦略は、オープン アドレッシングとセパレート チェイニングです。キャッシュを考慮した衝突解決は、文字列ハッシュ テーブルについて過去に議論された別の戦略です。
オープンアドレス
この方法では、ハッシュ テーブル内のセルに、占有、空、削除の 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)、「Embedded Security」、Practical Embedded Security、Elsevier、pp. 83–114、doi :10.1016/b978-075068215-2.50006-9、ISBN 9780750682152、 2021-12-08取得
- ^ 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-08取得
- ^ 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. (編著)。文字列ハッシュ テーブルでのキャッシュを考慮した衝突解決。文字列処理と情報検索に関する国際シンポジウム。文字列処理と情報検索 SPIRE 2005。コンピュータ サイエンスの講義ノート。第 3772 巻。ベルリン、ハイデルベルク: Springer Berlin Heidelberg。pp. 91–102。doi : 10.1007 /11575832_11。ISBN 978-3-540-29740-6。