Loading article…
暗号学において、衝突耐性は暗号ハッシュ関数の特性です。ハッシュ関数Hは、同じ出力にハッシュされる 2 つの入力、つまり、a ≠ bであるがH ( a ) = H ( b ) である 2 つの入力 a と b を見つけるのが難しい場合、衝突耐性があります。[ 1 ] : 136鳩の巣原理とは、出力よりも入力の方が多いハッシュ関数では必ずこのような衝突が発生することを意味します。[1] : 136 衝突 を見つけるのが困難であればあるほど、ハッシュ関数は暗号的に安全です。
「誕生日のパラドックス」は衝突耐性に上限を設けます。ハッシュ関数がNビットの出力を生成する場合、ランダムな入力に対して2 N /2（または）ハッシュ演算のみを計算する攻撃者は、2つの一致する出力を見つける可能性が高くなります。ブルートフォース攻撃よりも簡単な方法がある場合、通常はハッシュ関数の欠陥と見なされます。[2]
暗号ハッシュ関数は通常、衝突耐性を持つように設計されています。しかし、かつては衝突耐性があると考えられていたハッシュ関数の多くが、後に破られました。特にMD5とSHA-1は、衝突を見つけるためのブルートフォースよりも効率的な手法を公開しています。[3] [4]しかし、一部のハッシュ関数では、衝突を見つけることが、整数因数分解や離散対数などの難しい数学的問題と同じくらい難しいことが証明されています。これらの関数は、証明可能安全と呼ばれます。[2]
意味
あるアルゴリズムGによって生成される関数の族 { h k : {0, 1} m ( k ) → {0, 1} l ( k ) }は、任意のkに対して | m ( k )| > | l ( k )| であるとき、つまりh k は入力文字列を圧縮し、すべてのh k はkが与えられたときに多項式時間内で計算できるとき、衝突耐性ハッシュ関数の族である。しかし、任意の確率多項式アルゴリズムAに対して、
- Pr [ k ← G (1 n ), ( x 1 , x 2 ) ← A ( k , 1 n ) st x 1 ≠ x 2ただしh k ( x 1 ) = h k ( x 2 )] < negl( n ),
ここでnegl(·)は無視できる関数を表し、nはセキュリティパラメータである。[5]
弱い衝突抵抗と強い衝突抵抗
衝突耐性には 2 つの種類があります。
ハッシュ関数 H と x が与えられたときに、H(x)=H(x') となるような他の x' が見つからない場合、ハッシュ関数は衝突耐性が弱いことになります。つまり、x が与えられたときに、ハッシュ関数が衝突を起こすような別の x' を見つけることはできません。
ハッシュ関数 H が与えられた場合、H(x)=H(x') となる任意の x と x' が見つからない場合、ハッシュ関数は強い衝突耐性を持ちます。言い換えると、ハッシュ関数が衝突を生成する 2 つの x が見つからないということです。
根拠
衝突耐性が望ましい理由はいくつかあります。
- 一部のデジタル署名システムでは、当事者は文書のハッシュに公開鍵署名を公開することで文書を証明します。同じハッシュを持つ 2 つの文書を作成できる場合、攻撃者は当事者に 1 つの文書を証明させ、その当事者がもう 1 つの文書を証明したと主張することができます。
- 一部の分散コンテンツ システムでは、ファイルの暗号化ハッシュを比較して、同じバージョンであることを確認します。同じハッシュを持つ 2 つのファイルを作成できる攻撃者は、実際には同じではないファイル バージョンがあるかのようにユーザーを騙すことができます。
参照
参考文献
- ^ ab Goldwasser, S.およびBellare, M.「暗号に関する講義ノート」 2012-04-21 にWayback Machineにアーカイブ。 暗号に関する夏期講習、MIT、1996-2001
- ^ ab Pass, R. 「講義 21: 衝突耐性ハッシュ関数と一般的なデジタル署名方式」 暗号学講座、コーネル大学、2009 年
- ^ Xiaoyun Wang、Hongbo Yu。「MD5 およびその他のハッシュ関数の破り方」(PDF)。2009 年 5 月 21 日のオリジナル(PDF)からアーカイブ。2009年 12 月 21 日閲覧。
- ^ 王暁雲;イークン・リサ・イン;本坊優。完全な SHA-1 での衝突の検出(PDF)。クリプト 2005。土井:10.1007/11535218_2。
- ^ Dodis, Yevgeniy. 「暗号化入門講義 12」(PDF) 。2016 年1 月 3 日閲覧。、def 1。