暗号学的ハッシュ関数のセキュリティ

根本的な問題は「難しい」の意味です。この問いに答えるには2つのアプローチがあります。1つ目は直感的・実践的なアプローチで、「難しいとは、システムのセキュリティが重要視されている限り、システムを破ることを阻止しなければならない攻撃者にとって、ほぼ確実に手の届かないものであることを意味する」というものです。2つ目は理論的なアプローチで、計算複雑性理論に基づいています。問題Aが難しい場合、整数因数分解や離散対数問題など、多項式時間では解けないと広く考えられている問題から、形式的なセキュリティ還元が存在します。

しかし、多項式時間アルゴリズムが存在しないからといって、システムが安全であるとは限らない。問題の難易度は、その大きさにも左右される。例えば、RSA公開鍵暗号（整数因数分解の難しさに依拠する）は、少なくとも2048ビット長の鍵を使用した場合にのみ安全とみなされるが、ElGamal暗号システム（離散対数問題の難しさに依拠する）の鍵は、一般的に256～512ビットの範囲である。

ハッシュへの入力のセットが比較的小さいか、何らかの方法で可能性によって順序付けられている場合、理論的なセキュリティに関係なく、総当たり検索が実用的である可能性があります。原像を復元できる可能性は、入力セットのサイズとハッシュ関数の計算速度またはコストに依存します。一般的な例として、パスワード検証データを保存するためにハッシュを使用することがあります。アクセス制御システムは、通常、ユーザーパスワードの平文を保存する代わりに、パスワードのハッシュを保存します。ユーザーがアクセスを要求すると、送信されたパスワードがハッシュ化され、保存されている値と比較されます。保存されている検証データが盗まれた場合、泥棒はパスワードではなくハッシュ値のみを入手します。ただし、ほとんどのユーザーは予測可能な方法でパスワードを選択し、パスワードは多くの場合十分に短いため、高速ハッシュを使用するとすべての可能な組み合わせをテストできます。^{[ 1 ]}検索を遅くするために、鍵導出関数 と呼ばれる特別なハッシュが作成されています。パスワードクラッキングを参照してください 。

多項式時間では解けないと想定される問題の例としては、

• 離散対数
• モジュラー平方根
• 整数因数分解
• 部分集合の合計

• 証明可能なセキュリティ削減機能を備えた現在の衝突耐性ハッシュアルゴリズムは、実用化するには効率が悪すぎる。従来のハッシュ関数と比較すると、処理速度が比較的遅く、暗号学的ハッシュに従来期待されてきたすべての基準を常に満たすとは限らない。非常にスムーズなハッシュはその一例である。
• 証明可能なセキュリティを備えたハッシュ関数を構築することは、ハッシュアルゴリズムにおけるビットの複雑な混合が、攻撃者が衝突を発見するのを防ぐのに十分強力であることをただ期待するだけの古典的なアプローチを用いるよりもはるかに難しい。
• 証明は多くの場合、漸近的に困難な最悪ケースまたは平均ケースの複雑性を持つ問題への還元によって行われます。最悪ケースの複雑性とは、基礎となる問題の典型的なケースではなく、特異なケースを解決する難易度を測るものです。平均ケースの複雑性が困難な問題への還元であっても、問題空間のサブセットに対して容易に問題を解決できるアルゴリズムが存在する可能性があるため、セキュリティは限定的です。例えば、Fast Syndrome Based Hashの初期バージョンはセキュリティ上の問題があることが判明しました。この問題は最新バージョンで解決されています。

SWIFFTは、これらのセキュリティ上の問題を回避するハッシュ関数の例です。推定時間t内に確率pでSWIFFTを破ることができる任意のアルゴリズムに対して、 tとpに応じて時間t ′内に特定の難しい数学的問題の最悪シナリオを解決するアルゴリズムを見つけることができることが示されています。^{[ 3 ]}

hash( m ) = xm ^mod nとします。ここで、_ⁿは因数分解が難しい合成数、xはあらかじめ指定された基数です。衝突xm1 ≡ xm2 (mod n )^_は、 nを法とするxの乗法位数の倍数m1 − m2_{を明らかにします。この情報は}^、 xの特定の性質を仮定すれば、多項式時間でn を_因数分解するために使用できます。

しかし、このアルゴリズムは、メッセージビットあたり平均1.5回のnを法とする乗算を必要とするため、非常に非効率的である。

• VSH （Very Smooth Hash）は、合成数nを法とする非自明な平方根を求める難しさを前提とした、証明可能な安全性を持つ衝突耐性ハッシュ関数です（これはnの素因数分解 と同じくらい難しいことが証明されています）。
• ムハシュ
• ECOH（楕円曲線のみのハッシュ関数）は、楕円曲線、部分集合和問題、および多項式の和​​の概念に基づいています。衝突耐性のセキュリティ証明は、弱められた仮定に基づいており、最終的に第2の原像攻撃が発見されました。
• FSB（高速シンドロームベースハッシュ関数）は、NP完全問題として知られる通常のシンドローム復号を解くのと少なくとも同程度に難しいことが証明されています。
• SWIFFT — SWIFFTは高速フーリエ変換に基づいており、巡回格子や理想格子における短いベクトルを見つける最悪の場合の困難さに関する比較的緩やかな仮定の下で、衝突耐性があることが証明されています。
• Chaum、van Heijst、Pfitzmannハッシュ関数—有限群F _{2 p +1}における離散対数問題を解くのと同じくらい衝突を見つけるのが難しい圧縮関数。
• ナップサック問題に基づくハッシュ関数—ナップサック問題に基づくハッシュ関数のファミリー。
• ゼモール・ティリッヒハッシュ関数は、行列群SL2の算術に依存するハッシュ関数のファミリーです。衝突を見つけることは、この群の特定の要素の因数分解を見つけることと少なくとも同程度に困難です。これは、少なくともPSPACE完全であるはずの難しさです。このハッシュに対して、最終的に2n ^/2_に近い時間計算量を持つ攻撃が発見されました。これは^、ゼモール・ティリッヒハッシュ関数の誕生日境界と理想原像の複雑性（それぞれ23n/2と23n）をはるかに上回りました。攻撃^には、サイズ2n^の縮小セットでの誕生日検索が含まれているため、証明可能なセキュリティの考え方を破壊したり、スキームを無効にしたりするものではなく、むしろ初期パラメータが小さすぎたことを示唆しています。^{[ 4 ]}
• シグマプロトコルからのハッシュ関数― 証明可能な安全性を備えたハッシュ関数を構築する一般的な方法が存在し、具体的には、任意の（適切な）シグマプロトコルから構築できます。この方法により、 VSHの高速版（VSH*と呼ばれる）が得られます。