99

私が常に疑問に思っている概念の 1 つは、暗号化ハッシュ関数と値の使用です。これらの関数が、一意で事実上元に戻すことが不可能なハッシュ値を生成できることは理解していますが、私がいつも疑問に思っていることは次のとおりです。

私のサーバーの場合、PHPで次を生成します。

md5("stackoverflow.com") = "d0cc85b26f2ceb8714b978e07def4f6e"

MD5 関数を介して同じ文字列を実行すると、PHP インストールで同じ結果が得られます。プロセスは、開始値から何らかの値を生成するために使用されています。

これは、何が起こっているかを分解してハッシュ値を逆にする方法があるということではないでしょうか?

これらの関数について、結果の文字列をたどることができないのはなぜですか?

4

16 に答える 16

215

入力マテリアルは無限の長さにすることができ、出力は常に 128 ビット長です。これは、無数の入力文字列が同じ出力を生成することを意味します。

乱数を選んで 2 で割り、余りだけを書き留めると、それぞれ偶数または奇数の 0 または 1 になります。その 0 または 1 を取って元の数を取得することは可能ですか?

于 2008-12-01T07:19:56.063 に答える
53

MD5 などのハッシュ関数が可逆であれば、データ圧縮アルゴリズムの歴史における転機となったでしょう! MD5 が可逆である場合、任意のサイズのデータ​​の任意のチャンクを、情報を失うことなくわずか 128 ビットで表すことができることは簡単にわかります。したがって、元のメッセージのサイズに関係なく、128 ビットの数値から元のメッセージを再構築できたはずです。

于 2008-12-01T09:22:00.123 に答える
34

ここで最も支持された回答が強調していることとは反対に、大きな(潜在的に無限の)入力サイズと固定出力サイズの違いによって引き起こされる暗号化ハッシュ関数の非単射性(つまり、同じ値にハッシュする複数の文字列があること)はそうではありません重要な点は、実際には、これらの衝突ができるだけ発生しないハッシュ関数を好むということです。

この関数を考えてみましょう(PHP表記で、質問として):

function simple_hash($input) {
     return bin2hex(substr(str_pad($input, 16), 0, 16));
}

これにより、文字列が短すぎる場合にいくつかのスペースが追加され、文字列の最初の 16 バイトが取得され、16 進数としてエンコードされます。MD5 ハッシュと同じ出力サイズです (32 の 16 進文字、または bin2hex 部分を省略した場合は 16 バイト)。

print simple_hash("stackoverflow.com");

これは出力されます:

737461636b6f766572666c6f772e636f6d

この関数には、MD5 に対する Cody の回答で強調されているのと同じ非単射性プロパティもあります。任意のサイズの文字列を渡すことができ (コンピューターに収まる限り)、32 桁の 16 進数のみを出力します。もちろん、それは注射ではありません。

しかし、この場合、同じハッシュにマップする文字列を見つけるのは簡単です (ハッシュに適用するだけhex2binで、それが得られます)。元の文字列の長さが (この例のように) 16 の場合、この元の文字列も取得されます。MD5 では、入力の長さが非常に短いことがわかっている場合でも、このようなことはできません (ブルート フォース攻撃など、一致するものが見つかるまで可能なすべての入力を試す以外に)。

暗号化ハッシュ関数の重要な仮定は次のとおりです。

  • 特定のハッシュを生成する文字列を見つけるのは難しい (プリイメージ耐性)
  • 特定の文字列と同じハッシュを生成する別の文字列を見つけるのは難しい (2 番目のプリイメージ耐性)
  • 同じハッシュを持つ文字列のペアを見つけるのは難しい (衝突耐性)

明らかに、私のsimple_hash機能はこれらの条件のどちらも満たしていません。(実際には、入力スペースを「16 バイトの文字列」に制限すると、関数は単射になり、証明可能な 2 番目のプリイメージ耐性と衝突耐性さえあります。)

現在、MD5 に対する衝突攻撃が存在します (たとえば、与えられた同じプレフィックスを使用しても、同じハッシュを持つ文字列のペアを生成することが可能です。かなりの作業が必要ですが、多くの作業は不可能ではありません)。重要な場合は MD5。プリイメージ攻撃はまだありませんが、攻撃は良くなります。

実際の質問に答えるには:

これらの関数について、結果の文字列をたどることができないのはなぜですか?

MD5 (および Merkle-Damgard 構造に基づいて構築された他のハッシュ関数) が効果的に行うことは、メッセージをキーとして、固定値を「プレーン テキスト」として、結果の暗号文をハッシュとして使用する暗号化アルゴリズムを適用することです。(その前に、入力はパディングされ、ブロックに分割されます。このブロックのそれぞれは、前のブロックの出力を暗号化するために使用され、逆計算を防ぐためにその入力と XOR 演算されます。)

最新の暗号化アルゴリズム (ハッシュ関数で使用されるものを含む) は、平文と暗号文の両方が与えられたとしても (または敵がそれらのいずれかを選択したとしても)、キーを回復するのが困難になるように作られています。これは一般に、各出力ビットが各キー ビット (数回) と各入力ビットによって決定されるように、多くのビット シャッフル操作を行うことによって行われます。そうすれば、完全なキーと入力または出力のいずれかを知っている場合にのみ、内部で何が起こっているかを簡単にたどることができます。

MD5 のようなハッシュ関数とプリイメージ攻撃 (物事を簡単にするために単一ブロックのハッシュ文字列を使用) の場合、暗号化関数の入力と出力のみがあり、キーはありません (これが探しているものです)。

于 2011-08-22T18:00:41.413 に答える
18

Cody Brocious の答えは正しいものです。厳密に言えば、多くの文字列が同じハッシュにマップされるため、ハッシュ関数を「反転」することはできません。ただし、特定のハッシュにマップされる 1 つの文字列を見つけるか、同じハッシュにマップされる2 つの文字列 (つまり、衝突) を見つけることは、暗号解読者にとって大きなブレークスルーになることに注意してください。これらの問題の両方が非常に困難であることが、優れたハッシュ関数が暗号化に役立つ理由です。

于 2008-12-01T07:32:59.997 に答える
12

MD5 は一意のハッシュ値を作成しません。MD5 の目標は、ソースへの小さな変更に基づいて大幅に変化する値を迅速に生成することです。

例えば、

"hello" -> "1ab53"
"Hello" -> "993LB"
"ZR#!RELSIEKF" -> "1ab53"

(明らかに、それは実際の MD5 暗号化ではありません)

ほとんどのハッシュ (すべてではないにしても) も一意ではありません。むしろ、それらは十分に一意であるため、衝突はほとんどありませんが、それでも可能です。

于 2008-12-01T07:41:05.893 に答える
8

ハッシュ アルゴリズムを考える良い方法は、Photoshop で画像のサイズを変更することを考えることです...たとえば、5000x5000 ピクセルの画像を 32x32 にサイズ変更するとします。あなたが持っているのは元の画像の表現ですが、はるかに小さく、画像データの特定の部分を効果的に「破棄」して、より小さいサイズに収まるようにしています。したがって、その 32x32 の画像のサイズを 5000x5000 に戻すと、ぼやけた混乱が生じるだけです。ただし、32x32 の画像はそれほど大きくないため、理論的には別の画像を縮小してまったく同じピクセルを生成できると考えられます。

これは単なる例えですが、ハッシュが何をしているかを理解するのに役立ちます。

于 2008-12-13T11:26:27.873 に答える
4

ハッシュの衝突は、あなたが思っているよりもずっと起こりそうです。誕生日のパラドックスを見て、その理由をより深く理解してください。

于 2008-12-01T07:49:05.177 に答える
4

可能な入力ファイルの数は 128 ビット出力の数よりも多いため、可能性のあるそれぞれに MD5 ハッシュを一意に割り当てることは不可能です。

暗号化ハッシュ関数は、データの整合性またはデジタル署名 (ハッシュは効率のために署名されています) をチェックするために使用されます。したがって、元のドキュメントを変更すると、元のハッシュが変更されたドキュメントと一致しないことを意味するはずです。

これらの基準が使用されることがあります。

  1. プリイメージ耐性: 特定のハッシュ関数と特定のハッシュについて、その関数の特定のハッシュを持つ入力を見つけるのは難しいはずです。
  2. 2 番目のプリイメージ耐性: 特定のハッシュ関数と入力に対して、同じハッシュを持つ 2 番目の異なる入力を見つけるのは難しいはずです。
  3. 衝突耐性: 特定の has 関数の場合、同じハッシュを持つ 2 つの異なる入力を見つけるのは難しいはずです。

これらの基準は、特定のハッシュに一致するドキュメントを見つけるのを困難にするために選択されます。そうしないと、元のドキュメントをハッシュに一致するドキュメントに置き換えることによってドキュメントを偽造することが可能になります。(意味不明な置き換えであっても、単にオリジナルを置き換えるだけでは混乱を招く可能性があります。)

数字の 3 は数字の 2 を意味します。

特に MD5 に関しては、欠陥があることが示されています: How to break MD5 and other hash functions .

于 2008-12-02T14:17:38.760 に答える
2

しかし、ここでレインボー テーブルの出番です。基本的には、個別にハッシュされた大量の値であり、結果がディスクに保存されます。次に、反転ビットは、非常に大きなテーブルでルックアップを行うための「ちょうど」ものです。

明らかに、これは可能なすべての入力値のサブセットに対してのみ実行可能ですが、入力値の境界がわかっている場合は、それを計算できる可能性があります。

于 2008-12-01T07:47:34.820 に答える
2

中国の科学者は、2 つの異なる文字列間で衝突を起こす「選択プレフィックス衝突」と呼ばれる方法を発見しました。

以下に例を示します: http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5.exe.zip
ソース コード: http://www.win.tue.nl/hashclash/fastcoll_v1.0.0。 5_source.zip

于 2012-03-13T06:07:36.080 に答える
1

ほとんどの人がすでに言っているように、MD5 は可変長のデータ ストリームを固定長のデータ チャンクにハッシュするように設計されているため、1 つのハッシュが多くの入力データ ストリームで共有されます。

ただし、チェックサムから元のデータを見つける必要があった場合、たとえば、パスワードのハッシュがあり、元のパスワードを見つける必要がある場合は、ハッシュをグーグル (または任意のサーチャー) で検索する方が速いことがよくあります。ブルートフォースよりも答えを求めて。この方法を使用して、いくつかのパスワードを見つけることに成功しました。

于 2008-12-03T10:42:37.540 に答える
0

定義上、暗号化ハッシュ関数は反転可能であってはならず、可能な限り衝突が少ない必要があります。

あなたの質問に関して:それは一方向のハッシュです。入力(長さに関係なく)は固定サイズの出力を生成し、アルゴ(MD5の場合は512ビット境界)に基づいてパディングされます。情報は圧縮され(失われ)、逆変換から生成することは事実上不可能です。

MD5に関する追加情報:衝突に対して脆弱です。私は最近この記事を読みました、 http://www.win.tue.nl/hashclash/Nostradamus/

暗号化ハッシュ実装(MD5およびSHA)のオープンソースコードは、Mozillaコードにあります。(freeblライブラリ)。

于 2008-12-01T08:14:20.790 に答える
0

現在、MD5ハッシュまたはその他のハッシュは、考えられるすべての文字列に対して事前に計算され、簡単にアクセスできるように保存されています。理論的にはMD5は可逆的ではありませんが、そのようなデータベースを使用すると、どのテキストが特定のハッシュ値をもたらしたかを知ることができます。

たとえば、 http: //gdataonline.com/seekhash.phpで次のハッシュコードを試して、ハッシュの計算に使用したテキストを確認してください。

aea23489ce3aa9b6406ebb28e0cda430
于 2009-05-30T15:04:55.760 に答える
0

f(x) = 1 は不可逆です。ハッシュ関数は元に戻せません。

これは、ハッシュ化されたデータの破損していないコピーを誰かが所有しているかどうかを判断する機能を実行するために実際に必要です。これにより、最近では特に MD5 に対して非常に強力なブルート フォース攻撃が発生しやすくなります。

数学の知識はあるが暗号解読の知識がほとんどない人々の間でも、あちこちで混乱が生じています。いくつかの暗号は、キーストリームを使用してデータを単純に XOR するため、任意のキーストリームを使用できるため、暗号文はその長さのすべての平文に対応すると言えます。

ただし、これは、シードから生成された合理的な平文が、シードpasswordによって生成された別の平文よりもはるかに可能性が高いことを無視しWsg5Nm^bkI4EgxUOhpAjTmTjO0F!VkWvysS6EEMsIJiTZcvsh@WI$IH$TYqiWvK!%&Ue&nk55ak%BX%9!NnG%32ftud%YkBO$U6oており、2番目の平文が可能であると主張する人が笑われるほどです。

同様に、 と の 2 つの潜在的なパスワードのどちらかを決定しようとしている場合passwordWsg5Nm^bkI4EgxUO一部の数学者が信じさせるほど難しいことではありません。

于 2013-02-19T22:45:24.920 に答える
-5

私はすべてのさまざまな議論が好きです。ハッシュ値の真の価値は、パスワードなどの文字列に人間が判読できないプレースホルダーを提供することであることは明らかです。特定の強化されたセキュリティ上の利点はありません。攻撃者がハッシュ化されたパスワードを使用してテーブルにアクセスしたと仮定すると、攻撃者は次のことができます。

  • 彼/彼女がテーブルへの書き込み/編集権限を持っている場合、彼/彼女が選択したパスワードをハッシュし、結果をパスワード テーブル内に配置します。
  • 一般的なパスワードのハッシュ値を生成し、パスワード テーブルに同様のハッシュ値が存在するかどうかをテストします。

この場合、パスワードがハッシュされているという事実だけでは、脆弱なパスワードを保護することはできません。

于 2014-09-23T21:38:55.400 に答える