hash - 暗号化ハッシュ関数の重要なポイントは何ですか?

Question

私はMD5 ハッシュ値に関するこの質問を読んでいましたが、受け入れられた回答は私を混乱させます。私が理解しているように、暗号化ハッシュ関数の主な特性の 1 つは、同じハッシュ値を持つ 2 つの異なるメッセージ (入力) を見つけることができないということです。

しかし、なぜ MD5 ハッシュ値が元に戻せないのかという質問に対するコンセンサスの答えはまだありません。無限の数の入力文字列が同じ出力を生成するためです。 これは私には完全に矛盾しているように思えます。

また、アルゴリズムが公開されているにも関わらず、ハッシュ値が依然として元に戻せないという事実は、私を多少困惑させます。これは、ハッシュ関数で常にデータが失われるため、どのデータが破棄されたかを知る方法がないためですか?

入力データ サイズが固定出力データ サイズよりも小さい場合 (たとえば、パスワード "abc" のハッシュ) はどうなりますか?

編集：

OK、私がこれをまっすぐに持っているかどうか見てみましょう:

1. 同じ出力を生成する入力文字列が無数にあるため、ハッシュから入力を推測するのは非常に困難です(元に戻せないプロパティ)。
2. ただし、同じ出力を生成する複数の入力文字列のインスタンスを 1 つでも見つけることも非常に困難です (衝突耐性の特性)。

Answer 1

警告：長い答え

これらの答えはすべて、暗号化ハッシュ関数の非常に重要な特性を欠いていると思います。特定のハッシュを取得するためにハッシュされた元のメッセージを計算することは不可能であるだけでなく、特定のハッシュ値にハッシュされるメッセージを計算することも不可能です。 。これは、原像攻撃と呼ばれます。

（「不可能」とは、ハッシュにハッシュされたメッセージを推測するまで、考えられるすべてのメッセージを推測するよりも短い時間でそれを行う方法を誰も知らないことを意味します。）

（MD5の不安定さに対する一般的な信念にもかかわらず、MD5は依然として原像耐性があります。私を信じない人は誰でも私にハッシュするものを自由に与えることができます2aaddf751bff2121cc51dc709e866f19。MD5にないのは衝突耐性です。これはまったく別のものです。）

さて、暗号化ハッシュ関数で「逆方向に作業」できない唯一の理由が、ハッシュ関数がデータを破棄してハッシュを作成するためである場合、プリイメージの耐性は保証されません。「逆方向に作業」して、挿入するだけです。ハッシュ関数がデータを破棄する場合は常にランダムデータであり、元のメッセージを思い付くことができなくても、目的のハッシュ値にハッシュするメッセージを思い付くでしょう。しかし、できません。

したがって、質問は次のようになります。（つまり、関数の原像耐性をどのように作成しますか？）

答えは、暗号化ハッシュ関数がカオスシステムをシミュレートすることです。彼らはあなたのメッセージを受け取り、それをブロックに分割し、それらのブロックを混ぜ合わせ、いくつかのブロックを互いに相互作用させ、それらのブロックを混ぜ合わせ、そしてそれを何度も繰り返します（まあ、1つの暗号化ハッシュ関数がそれを行います;他のものはそれらを持っています独自のメソッド）。ブロックは相互に作用するため、ブロックCはブロックDと相互作用してブロックAを生成するだけでなく、ブロックEと相互作用してブロックBを生成する必要があります。これで、ブロックC、D、の値を見つけることができます。ハッシュ値にブロックAとBを生成するEですが、さらに戻ると、突然、Cと相互作用してDを作成し、Eと相互作用してBを作成するブロックFが必要になります。このようなブロックでは、同時に！C、D、およびEの間違った値を推測したに違いありません。

すべての暗号化ハッシュ関数がブロックの相互作用で上記とまったく同じであるとは限りませんが、同じ考えがあります。「逆方向に作業」しようとすると、行き止まりがたくさん発生し、その時間が発生するということです。プリイメージを生成するのに十分な値を試すのにかかる時間は、数百年から数百万年のオーダーです（ハッシュ関数によって異なります）。これは、機能するメッセージが見つかるまでメッセージを試すだけの時間よりもはるかに優れています。

Answer 2

1: ハッシュの主な目的は、非常に大きな空間を、小さいながらも非常に大きな空間にマッピングすることです (たとえば、MD5 は、「何でも」取り、それをサイズ 2^128 の空間に変換します -- 大きな、しかし aleph-0 ほど大きくはありません。)

他の機能に加えて、適切なハッシュは宛先スペースを均一に埋めます。不正なハッシュがスペースをぎこちなく埋め、多くの一般的な入力に対して同じハッシュを生成します。

入力数値のすべての桁を追加するだけのばかげたハッシュ関数 sum() を想像してみてください。下にマッピングすることには成功しますが、低い位置に衝突 (3 と 12 と 21 のような同じ出力を持つ入力) がたくさんあります。出力スペースの端とスペースの上端はほとんど空です。その結果、スペースの使い方が非常に悪くなり、割れやすくなります。

したがって、宛先スペースを均等に使用する優れたハッシュは、オッズだけで、同じ出力を持つ 2 つの入力を見つけるのを困難にします: MD5 が完全である場合、2 つの入力が同じ出力を持つオッズは 2^- になります。 128。これはかなりのオッズです。より大きな出力スペースに頼らずにできる最善の方法です。(実際には、MD5 は完全ではありません。これが、MD5 を脆弱にする原因の 1 つです。)

しかし、入力スペースが「無限」であり、無限を 2^128 で割っても無限になるため、膨大な数の入力が特定のハッシュにマップされることは依然として事実です。

2: はい、出力スペースが入力スペースと同じかそれより大きい場合を除いて、ハッシュは常にデータ損失を引き起こします。その場合、おそらくハッシュする必要はありませんでした!

3: 小さい入力の場合、ベスト プラクティスは入力をソルトすることです。実際、これは暗号化ハッシュの良い方法です。そうしないと、攻撃者が特定の入力を与えて、使用しているハッシュを見つけようとする可能性があるからです。「ソルト」は、入力に追加 (または先頭に追加) する一連の追加情報です。次に、結果をハッシュします。

編集: 暗号化では、ハッシュ関数がプリイメージ攻撃に耐性があることも重要です。直観的には、他の多くの入出力ペアを知っていても、特定の出力の入力を推測するのは困難です。「合計」関数はおそらくかなり簡単に推測できます (ただし、データを破壊するため、元に戻すのは簡単ではない可能性があります)。

Answer 3

これらは、一般的なハッシュ関数のプロパティです。

ただし、脆弱性が見つかっているため、MD5 は使用しないでください。これらの攻撃の詳細については、「脆弱性」セクションと外部リンクを確認してください。 http://en.wikipedia.org/wiki/Md5 メッセージ内の 128 ビットのみを変更することで、MD5 衝突を起こすことができます。

SHA-1 は単純なハッシュでは安全ですが、十分な資金のあるエンティティ (政府、大企業) に対して弱くなる攻撃がいくつかあります。

SHA-256 は、今後 20 年間のテクノロジーに対する安全な出発点です。

Answer 4

「MD5 ハッシュ値が元に戻せないのはなぜですか?」これは、「無限の数の入力文字列 > が同じ出力を生成する」ためです。

これが、ハッシュ関数を逆にする (同じ入力を取得する) ことができない理由です。つまり、同じ出力にマップされる別の入力値を見つけるのも難しいということです (ハッシュ関数が mod 2 の場合: 134 mod 2 = 0; 今では 134 を元に戻すことはできません)。結果は同じですが、同じ出力値を持つ番号 2 を見つけることができます (134 と 2 が衝突します)。

入力がブロック サイズより小さい場合、ブロック サイズに合わせてパディングが使用されます。

Answer 5

それでも、「なぜ MD5 ハッシュ値は元に戻せないのですか?」という質問に対するコンセンサスの答えはありません。これは、「無限の数の入力文字列が同じ出力を生成する」ためです。

これはどのハッシュ関数にも当てはまりますが、暗号化ハッシュ関数の本質ではありません。

パスワードなどの短い入力文字列の場合、暗号化ハッシュ関数を逆にすることは理論的には可能ですが、計算上実行不可能なはずです。つまり、計算が長すぎて役に立たないでしょう。

この実行不可能性の理由は、入力がハッシュ値で完全に「混合」されているため、すべての入力のハッシュ値を計算するブルート フォース攻撃よりも少ない労力でそれを解くことが不可能になるためです。