Loading article…
暗号学において、暗号学的ハッシュ関数 に対する原像攻撃とは、特定のハッシュ値を持つメッセージを見つけようとする攻撃である。暗号学的ハッシュ関数は、その原像（可能な入力の集合）に対する攻撃に耐える必要がある。
攻撃の文脈において、原像抵抗には2つの種類がある。
これらは衝突耐性と比較することができ、衝突耐性では、同じ出力にハッシュされる2つの異なる入力x、x ′を見つけることは計算上不可能である。つまり、 h ( x ) = h ( x ′)となるようなものは存在しない。[ 1 ]
衝突耐性は第2原像耐性を意味しますが、原像耐性を保証するものではありません。[ 1 ]ただし、ハッシュ関数の範囲に関する特定の仮定の下では、衝突耐性は（暫定的な含意により）原像耐性を意味します。[ 1 ] 。逆に、第2原像攻撃は衝突攻撃を意味します（ x ′に加えて、xは最初からすでにわかっているので、自明です）。暫定的な含意により、原像攻撃は第2原像攻撃も意味し、それがさらに衝突攻撃に拡張されます。
定義上、理想的なハッシュ関数とは、第一または第二の原像を計算する最速の方法が総当たり攻撃であるような関数です。nビットハッシュの場合、この攻撃の時間計算量は2nであり、 n = 128ビットという一般的な出力サイズに対しては高すぎると考えられます。このような計算量が攻撃者が達成できる最良のものである場合、そのハッシュ関数は原像耐性があるとみなされます。しかし、量子コンピュータが構造化された原像攻撃を実行するという一般的な結果があります。これはまた、第二の原像[ 2 ]を意味し、したがって衝突攻撃を意味します。
より高速な原像攻撃は、特定のハッシュ関数を暗号解読することで発見でき、その関数に固有のものです。いくつかの重要な原像攻撃は既に発見されていますが、まだ実用的ではありません。実用的な原像攻撃が発見されれば、多くのインターネットプロトコルに深刻な影響を与えるでしょう。ここでいう「実用的」とは、攻撃者が妥当な量のリソースで実行できることを意味します。例えば、目的のハッシュ値やメッセージ1つを原像化するのに数兆ドルもの費用と数十年を要する原像攻撃は実用的ではありませんが、数千ドルの費用と数週間で実行できる原像攻撃は非常に実用的かもしれません。
現在知られているMD5およびSHA-1に対する実用的またはほぼ実用的な攻撃[ 3 ] [ 4 ]はすべて衝突攻撃である[ 5 ]。一般に、衝突攻撃は、特定の値に制限されないため（任意の2つの値を使用して衝突させることができる）、原像攻撃よりも実行しやすい。原像攻撃とは対照的に、総当たり衝突攻撃の時間計算量はわずかである。。
理想的なハッシュ関数に対する第一原像攻撃の計算上の非実現可能性は、可能なハッシュ入力の集合が総当たり探索には大きすぎることを前提としている。しかし、特定のハッシュ値が比較的小さな入力集合から生成されたことがわかっている場合、あるいは何らかの方法で尤度順に並べられている場合は、総当たり探索が有効となる可能性がある。実用性は、入力集合のサイズとハッシュ関数の計算速度またはコストに依存する。
一般的な例として、認証のためにパスワード検証データを保存するためにハッシュを使用することが挙げられます。アクセス制御システムは、ユーザーパスワードの平文を保存する代わりに、パスワードのハッシュを保存します。ユーザーがアクセスを要求すると、送信されたパスワードがハッシュ化され、保存されている値と比較されます。保存されている検証データが盗まれた場合、泥棒はパスワードではなくハッシュ値しか入手できません。しかし、ほとんどのユーザーは予測可能な方法でパスワードを選択し、多くのパスワードは十分に短いため、ハッシュが原像攻撃に対して安全と評価されていても、高速ハッシュを使用するとすべての可能な組み合わせをテストできます。[ 6 ]検索を遅くするために、鍵導出関数 と呼ばれる特別なハッシュが作成されています。パスワードクラッキングを参照してください 。短いパスワードのテストを防ぐ方法については、ソルト（暗号化）を参照してください。
