原像攻撃

暗号化において、暗号化ハッシュ関数に対する原像攻撃は、特定のハッシュ値を持つメッセージを見つけようとします。暗号化ハッシュ関数は、原像（可能な入力のセット）に対する攻撃に耐える必要があります。

攻撃の文脈では、原像抵抗には 2 つの種類があります。

原像計算困難性: 基本的にすべての事前に指定された出力に対して、その出力にハッシュされる入力を見つけることは計算上不可能である。つまり、 $yが与えられた場合、$ $h$ $($ $x$ $) =$ $y$ となるような $x を$ 見つけることは困難である。^[1]
第二原像抵抗: 指定された入力に対して、同じ出力を生成する別の入力を見つけることは計算上不可能である。つまり、 $xが与えられた場合、$ $h$ $($ $x$ $) =$ $h$ $($ $x$ $')$ となる第二の入力 $x' \neq x$ を見つけることは困難である。^[1]

これらは衝突耐性と比較することができ、衝突耐性では、同じ出力にハッシュされる2つの異なる入力 $x$ 、 $x'を$ 見つけることは計算上不可能である、つまり、 $h (x)= h (x')$ となる。^[1]

衝突耐性は、第二原像攻撃耐性を意味します。第二原像攻撃耐性は、ハッシュ関数の入力のサイズがハッシュ関数の出力のサイズよりも大幅に（たとえば、2倍）大きい場合にのみ、原像攻撃耐性を意味します。^{[1]逆に、第二原像攻撃は衝突攻撃を意味します（当然のことですが、} $x'$ に加えて、 $x は$ 最初から既にわかっているので）。

応用原像攻撃

定義により、理想的なハッシュ関数とは、第 1 または第 2 の原像を計算する最も速い方法がブルートフォース攻撃であるような関数です。 $n$ ビットのハッシュの場合、この攻撃の時間計算量は $2 n$ $であり、これはn$ = 128 ビットの一般的な出力サイズには大きすぎると考えられます。このような計算量が攻撃者が達成できる最善のものである場合、ハッシュ関数は原像攻撃耐性があると考えられます。ただし、量子コンピューターはで構造化原像攻撃を実行するという一般的な結果があり、これは第 2 の原像^[2]と衝突攻撃も意味します。 ${\sqrt {2^{n}}}=2^{\frac {n}{2}}$

より高速なプリイメージ攻撃は、特定のハッシュ関数を暗号解析することで発見できますが、その関数に固有のものです。すでにいくつかの重要なプリイメージ攻撃が発見されていますが、まだ実用的ではありません。実用的なプリイメージ攻撃が発見された場合、多くのインターネットプロトコルに劇的な影響が及ぶでしょう。この場合、「実用的」とは、攻撃者が妥当な量のリソースを使用して実行できることを意味します。たとえば、1 つの目的のハッシュ値または 1 つのメッセージをプリイメージ化するのに数兆ドルの費用がかかり、数十年かかるプリイメージ化攻撃は実用的ではありません。数千ドルの費用がかかり、数週間かかる攻撃は非常に実用的かもしれません。

MD5とSHA-1に対する現在知られているすべての実際的またはほぼ実際的な攻撃^[3]^[4]は衝突攻撃です。^[5]一般に、衝突攻撃は設定された値によって制限されないため（任意の2つの値を衝突に使用できる）、原像攻撃よりも簡単に実行できます。原像攻撃とは対照的に、ブルートフォース衝突攻撃の時間計算量はわずかです。 $2^{\frac {n}{2}}$

制限された原像空間攻撃

理想的なハッシュ関数に対する最初の原像攻撃が計算上不可能なのは、ハッシュ入力の可能なセットが総当たり検索には大きすぎることが前提です。ただし、特定のハッシュ値が比較的小さい入力セットから生成されたか、何らかの方法で尤度順に並べられていることがわかっている場合は、総当たり検索が効果的である可能性があります。実用性は、入力セットのサイズとハッシュ関数の計算速度またはコストによって異なります。

一般的な例としては、認証用のパスワード検証データを格納するためにハッシュを使用することが挙げられます。アクセス制御システムは、ユーザーパスワードのプレーンテキストを格納するのではなく、パスワードのハッシュを格納します。ユーザーがアクセスを要求すると、送信したパスワードがハッシュ化され、格納されている値と比較されます。格納されている検証データが盗まれた場合、窃盗犯が持つのはハッシュ値のみで、パスワードはわかりません。ただし、ほとんどのユーザーは予測可能な方法でパスワードを選択し、多くのパスワードは十分に短いため、高速ハッシュを使用すると、ハッシュが原像攻撃に対して安全であると評価されていても、すべての可能な組み合わせをテストできます。^{[6]検索を遅くするために、}キー導出関数と呼ばれる特別なハッシュが作成されています。「パスワードクラッキング」を参照してください 。短いパスワードのテストを防ぐ方法については、「ソルト (暗号化)」を参照してください。

参照

参考文献

^ abcd Rogaway, P.; Shrimpton, T. (2004). 「暗号ハッシュ関数の基礎: 原像耐性、第 2 原像耐性、衝突耐性の定義、影響、分離」( PDF) .高速ソフトウェア暗号化. コンピュータサイエンスの講義ノート。第 3017 巻。Springer-Verlag。pp. 371–388。doi : 10.1007/978-3-540-25937-4_24。ISBN 978-3-540-22171-5. 2012年11月17日閲覧。
^ Daniel J. Bernstein (2010-11-12). 「Blue Midnight Wish、ECHO、Fugue、Grøstl、Hamsi、JH、Keccak、Shabal、SHAvite-3、SIMD、Skeinに対する量子攻撃」(PDF)。イリノイ大学シカゴ校。 2020年3月29日閲覧。
^ Bruce Morton、Clayton Smith (2014-01-30)。「SHA-2 に移行する必要がある理由」。Certificate Authority Security Council。
^ 「Google オンラインセキュリティブログ: 最初の SHA1 衝突のお知らせ」。2017年 2 月 23 日閲覧。
^ 「MD5 と展望」 2009-01-01。
^ Goodin, Dan (2012-12-10). 「25-GPU クラスターが 6 時間未満ですべての標準 Windows パスワードを解読」Ars Technica . 2020 年 11 月 23日閲覧。

[crypto-hash-def-1] Rogaway, P.; Shrimpton, T. (2004). 「暗号ハッシュ関数の基礎: 原像耐性、第 2 原像耐性、衝突耐性の定義、影響、分離」( PDF) .高速ソフトウェア暗号化. コンピュータサイエンスの講義ノート。第 3017 巻。Springer-Verlag。pp. 371–388。doi : 10.1007/978-3-540-25937-4_24。ISBN 978-3-540-22171-5. 2012年11月17日閲覧。

[2] Daniel J. Bernstein (2010-11-12). 「Blue Midnight Wish、ECHO、Fugue、Grøstl、Hamsi、JH、Keccak、Shabal、SHAvite-3、SIMD、Skeinに対する量子攻撃」(PDF)。イリノイ大学シカゴ校。 2020年3月29日閲覧。

[3] Bruce Morton、Clayton Smith (2014-01-30)。「SHA-2 に移行する必要がある理由」。Certificate Authority Security Council。

[4] 「Google オンラインセキュリティブログ: 最初の SHA1 衝突のお知らせ」。2017年 2 月 23 日閲覧。

[5] 「MD5 と展望」 2009-01-01。

[6] Goodin, Dan (2012-12-10). 「25-GPU クラスターが 6 時間未満ですべての標準 Windows パスワードを解読」Ars Technica . 2020 年 11 月 23日閲覧。