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

暗号学 では、暗号ハッシュ関数は主に 2 つのカテゴリに分けられます。最初のカテゴリは、数学的問題に基づいて設計され、厳密な数学的証明、複雑性理論、および形式的簡約からセキュリティが導かれる関数です。これらの関数は、証明可能セキュリティの暗号ハッシュ関数と呼ばれます。これらを構築するのは非常に難しく、紹介されている例はほとんどありません。実際の使用は限られています。

2 番目のカテゴリは、数学的な問題に基づくのではなく、メッセージのビットを混合してハッシュを生成するアドホックな構成に基づく関数です。これらは解読が難しいと考えられていますが、正式な証明はされていません。広く使用されているハッシュ関数のほとんどすべてがこのカテゴリに属します。これらの関数の一部はすでに解読されており、現在は使用されていません。ハッシュ関数のセキュリティの概要を参照してください 。

一般に、暗号ハッシュ関数の基本的なセキュリティは、原像抵抗性、第 2 原像抵抗性、衝突抵抗性、疑似ランダム性など、さまざまな角度から見ることができます。

• 原像攻撃耐性: ハッシュhが与えられた場合、 h = hash( m )となるメッセージm を見つけるのは困難でなければなりません。この概念は一方向関数の概念に関連しています。この特性を持たない関数は原像攻撃に対して脆弱です。
• 2 番目の原像攻撃耐性: 入力m ₁が与えられた場合、 hash( m ₁ ) = hash( m ₂ )となる別の入力m ₂ ≠ m ₁を見つけるのは困難です。この特性は、弱い衝突耐性と呼ばれることもあります。この特性を持たない関数は、2 番目の原像攻撃に対して脆弱です。
• 衝突耐性: hash( m ₁ ) = hash( m ₂ )となる2 つの異なるメッセージm ₁とm ₂を見つけるのは困難です。このようなペアは (暗号) ハッシュ衝突と呼ばれます。この特性は、強い衝突耐性と呼ばれることもあります。原像耐性に必要なハッシュ値の少なくとも 2 倍の長さのハッシュ値が必要です。そうでない場合、誕生日攻撃によって衝突が発見される可能性があります。
• 疑似乱数性:ハッシュ関数に基づく疑似乱数ジェネレータを真の乱数ジェネレータと区別することは困難であるはずです。たとえば、疑似乱数ジェネレータは通常の乱数テストに合格します。

基本的な質問は、困難の意味です。この質問に答えるには 2 つのアプローチがあります。1 つ目は、直感的/実用的なアプローチです。「困難とは、システムのセキュリティが重要であると見なされる限り、システムを破ることを阻止しなければならない敵の手の届かないところにあることを意味します。」2 つ目のアプローチは理論的なものであり、計算複雑性理論に基づいています。問題Aが困難である場合、整数因数分解や離散対数問題など、多項式時間では解決不可能であると広く考えられている問題から、正式なセキュリティ削減が存在します。

ただし、多項式時間アルゴリズムが存在しないからといって、システムが安全であると自動的に保証されるわけではありません。問題の難しさはそのサイズにも依存します。たとえば、RSA 公開鍵暗号(整数因数分解の難しさに基づく) は、少なくとも 2048 ビットの長さの鍵でのみ安全であると見なされますが、ElGamal 暗号システム(離散対数問題の難しさに基づく) の鍵は、通常 256 ～ 512 ビットの範囲です。

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

ほとんどのハッシュ関数はアドホックベースで構築されており、メッセージのビットがうまく混合されてハッシュが生成されます。さまざまなビット単位の操作（回転など）、モジュラー加算、圧縮関数が反復モードで使用され、出力の高い複雑性と疑似ランダム性が確保されます。このように、セキュリティを証明するのは非常に難しく、証明は通常行われません。ほんの数年前^{[いつ? ]}、最も人気のあるハッシュ関数の1つであるSHA-1が、その長さが示唆するほど安全ではないことが示されました。衝突は、ブルートフォースの数である2 ^{80ではなく、わずか2 51 [2]}テストでのみ発見されました。

言い換えれば、現在使用されているハッシュ関数のほとんどは、衝突耐性が証明されていません。これらのハッシュは、純粋に数学的な関数に基づいていません。このアプローチにより、一般的にはより効果的なハッシュ関数が実現されますが、そのような関数の弱点が最終的​​に衝突の検出に利用されるリスクがあります。有名な例の 1 つがMD5です。

このアプローチでは、ハッシュ関数のセキュリティは難しい数学的問題に基づいており、ハッシュ関数の衝突を見つけることは根本的な問題を解くのと同じくらい難しいことが証明されています。これにより、従来のアプローチのようにビットの複雑な混合に頼るよりも、セキュリティの概念がいくらか強化されます。

暗号ハッシュ関数は、衝突を見つけることが多項式時間では解決できないはずの問題Pから多項式時間で帰着可能であることが証明できる場合、衝突攻撃に対して証明可能なセキュリティを持ちます。その場合、この関数は証明可能安全、または単に証明可能と呼ばれます。

これは、衝突を見つけることがアルゴリズムAによって多項式時間で実行可能である場合、一般的に多項式時間では解決不可能であると考えられている問題P を解決するためにアルゴリズムAを使用する多項式時間アルゴリズムR (削減アルゴリズム) を見つけて使用できることを意味します。これは矛盾です。つまり、衝突を見つけることはP を解決することよりも簡単ではないということです。

しかし、これは衝突を見つけることが一部のケースで難しいことを示しているに過ぎず、計算困難な問題のすべてのインスタンスが通常難しいわけではない。実際、NP 困難問題の非常に大規模なインスタンスは日常的に解決されているが、最も困難な問題だけが事実上解決不可能である。

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

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

• ^証明可能なセキュリティ削減機能を持つ現在の^衝突耐性ハッシュ アルゴリズムは、実際に使用するには効率が悪すぎます。従来のハッシュ関数と比較すると、比較的低速に^なる傾向があり、暗号ハッシュに従来期待されるすべての基準を常に満たすわけではありません。非常にスムーズなハッシュがその一例です。
• 証明可能なセキュリティを備えたハッシュ関数を構築することは、ハッシュ アルゴリズム内のビットの複雑な混合が十分に強力で、敵が衝突を見つけられないようにすることを期待するだけの従来のアプローチを使用するよりもはるかに困難です。
• 証明は、多くの場合、漸近的に困難な最悪ケースまたは平均ケースの複雑さを持つ問題への還元です。最悪ケースの複雑さは、根本的な問題の典型的なケースではなく、異常なケースを解決する難しさを測定します。困難な平均ケースの複雑さを持つ問題への還元でさえ、問題空間のサブセットの問題を簡単に解決するアルゴリズムがまだ存在する可能性があるため、限られたセキュリティしか提供されません。たとえば、Fast Syndrome Based Hashの初期バージョンは安全でないことが判明しました。この問題は最新バージョンで解決されました。

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

hash( m ) = x ^m mod nとします。ここで、nは因数分解が困難な合成数、x は事前に指定された基数値です。衝突x ^{m ₁} ≡ x ^{m ₂} (mod n )は、 x を法とするnの乗法順序の倍数m ₁ − m _{2 を}明らかにします。この情報は、 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}内の離散対数問題を解くのと同じくらい難しい圧縮関数。
• ナップザックベースのハッシュ関数 -ナップザック問題に基づくハッシュ関数のファミリ。
• ゼモール＝ティリッヒハッシュ関数—行列群SL ₂の算術演算に依存するハッシュ関数のファミリー。衝突を見つけることは、この群の特定の要素の因数分解を見つけることと同じくらい難しい。これは難しいはずで、少なくともPSPACE 完全である。^{[疑わしい–議論する]このハッシュに対して、最終的に}2 ^{n /2}に近い時間計算量で攻撃が発見された。これは、ゼモール＝ティリッヒハッシュ関数の誕生日境界と理想的な原像計算量である2 ^{3 n /2}と2 ^{3 n}をはるかに上回るものだった。攻撃にはサイズ2 nの縮小セットでの誕生日検索が含まれるため、証明可能セキュリティの概念を破壊したり、スキームを無効にしたりすることはなく、むしろ初期パラメータが小さすぎたことを示唆している。^[3]
• シグマ プロトコルからのハッシュ関数 - 証明可能な安全なハッシュを構築する一般的な方法が存在します。具体的には、任意の (適切な)シグマ プロトコルから構築します。この方法で、 VSHの高速バージョン(VSH* と呼ばれる) を取得できます。