どうしてMD5ハッシュ値は元に戻せないのですか？

https://stackoverflow.com/questions/330207

11-07-2019
|

質問

私がいつも考えていた概念の1つは、暗号化ハッシュ関数と値の使用です。これらの関数は一意であり、実質的に元に戻すことが不可能なハッシュ値を生成できることを理解していますが、私がいつも考えていたのは次のとおりです：

サーバー上でPHPを使用する場合：

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

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

これは、何が起きているのかを解体し、ハッシュ値を逆にする何らかの方法があることを意味しないのですか？

結果の文字列のリトレースを不可能にするこれらの関数についてはどうですか？

解決

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

乱数を選択して2で除算し、残りだけを書き留めると、0または1のいずれか（それぞれ偶数または奇数）が得られます。その0または1を取り、元の番号を取得することは可能ですか？

他のヒント

MD5などのハッシュ関数が可逆的だった場合、データ圧縮アルゴリズムの歴史において重要な出来事でした！ MD5がリバーシブルである場合、任意のサイズの任意のデータチャンクは、情報を失うことなく、わずか128ビットで表すことができるのは簡単です。したがって、元のメッセージのサイズに関係なく、128ビットの数値から元のメッセージを再構築できたはずです。

ここで最も支持された答えが強調するものとは反対に、大きな（潜在的には）の違いによって引き起こされる暗号化ハッシュ関数の非単射性（つまり、同じ値にハッシュする複数の文字列がある）無限）入力サイズと固定出力サイズ重要なポイントではありません＆＃8211;実際には、それらの衝突が可能な限りめったに起こらないハッシュ関数を好みます。

この関数を検討してください（質問として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されます。）

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

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

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

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

たとえば、

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

（明らかに、実際のMD5暗号化ではありません）

ほとんどのハッシュ（すべてではないにしても）も一意ではありません。むしろ、それらはユニークな十分なので、衝突はほとんどありえませんが、それでも可能です。

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

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

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

可能な入力ファイルの数は128ビット出力の数よりも大きいため、MD5ハッシュを可能な各ファイルに一意に割り当てることはできません。

暗号化ハッシュ関数は、データの整合性またはデジタル署名を確認するために使用されます（効率のためにハッシュが署名されます）。したがって、元のドキュメントを変更すると、元のハッシュが変更されたドキュメントと一致しなくなります。

これらの基準は時々使用されます：

プレイメージ耐性：所定のハッシュ関数とハッシュに対して、その関数に対して指定されたハッシュを持つ入力を見つけるのは難しいはずです。
2番目の前画像耐性：与えられたハッシュ関数と入力に対して、同じハッシュを持つ2番目の異なる入力を見つけるのは難しいはずです。
衝突耐性：与えられた関数に対して、同じハッシュを持つ2つの異なる入力を見つけるのは難しいはずです。

これらの基準は、指定されたハッシュに一致するドキュメントを見つけることを困難にするために選択されます。（たとえ置き換えが意味のないものであったとしても、元のものを単に置き換えるだけで混乱が生じる可能性があります。）

番号3は番号2を意味します。

特にMD5に関しては、欠陥があることが示されています。方法MD5およびその他のハッシュ関数を破る。

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

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

中国の科学者は、「選択されたプレフィックスの衝突」と呼ばれる方法を発見しました。 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

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

ただし、パスワードのハッシュがあり、元のパスワードを見つける必要がある場合など、チェックサムから元のデータを見つける必要があった場合は、多くの場合、グーグル（または任意の検索者））答えのハッシュは、総当たりするよりも。この方法でいくつかのパスワードを見つけました。

最も多く投票された回答の意味を理解する最良の方法は、MD5アルゴリズムを元に戻すことです。数年前に MD5crypt アルゴリズムを元に戻そうとしましたが、明らかに不可能であるため元のメッセージを復元せず、元のハッシュと同じハッシュを生成するメッセージを生成しようとしました。これは、少なくとも理論的には、元のメッセージを使用する代わりに、生成されたメッセージ（パスワード）を使用して/ etc / passwdファイルにuser：passwordを保存したLinuxデバイスにログインする方法を提供します。両方のメッセージのハッシュは同じであるため、システムは（元のハッシュから生成された）パスワードが有効であると認識します。それはまったく機能しませんでした。数週間後、私が正しく覚えていれば、最初のメッセージで salt を使用したことが私を殺しました。有効な初期メッセージだけでなく、塩漬けの有効な初期メッセージを作成する必要がありましたが、これはできませんでした。しかし、この実験から得た知識は素晴らしかったです。

定義によりHash（cryptographic Hash）関数：可逆的であってはなりません;衝突してはなりません（可能な限り）。

質問に答えてください。これは一方向ハッシュです。入力（長さに関係なく）は、固定サイズの出力を生成します（MD5の512ビット境界に基づいてパディングされます）。情報は圧縮され（失われ）、実際には逆変換から生成することはできません。

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

暗号化ハッシュ実装（MD5およびSHA）のソースコードを開くには、Mozillaコードを参照してください。（freeblライブラリ）。

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

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

aea23489ce3aa9b6406ebb28e0cda430

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

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

数学的知識はあるが暗号解読の知識はほとんどない人々の間でも、ここや他の場所で混乱が生じています。いくつかの暗号は単にデータをキーストリームとXORします。したがって、キーストリームを使用できたため、暗号テキストはその長さのすべてのプレーンテキストに対応すると言うことができます。

ただし、これは、シード password から生成された合理的なプレーンテキストが、シード Wsg5Nm ^ bkI4EgxUOhpAjTmTjO0F！VkWvysS6EEMsIJiTZcvsh @ WI $ IH $ TYqiWvK！％＆amp; Ue＆amp; nk55ak％BX％9！NnG％32ftud％YkBO $ U6o で、2番目の可能性があると主張する人が笑われる程度に。

同様に、2つの潜在的なパスワード password と Wsg5Nm ^ bkI4EgxUO を決定しようとしている場合、数学者がするほど難しくはありません。信じてください。

さまざまな引数がすべて好きです。ハッシュ値の実際の値は、パスワードなどの文字列に人間が読み取れないプレースホルダーを提供することだけであることは明らかです。特に強化されたセキュリティ上の利点はありません。攻撃者がハッシュ化されたパスワードを使用してテーブルにアクセスした場合、次のことが可能になります。

自分で選択したパスワードをハッシュし、テーブルへの書き込み/編集権限がある場合は、結果をパスワードテーブル内に配置します。
一般的なパスワードのハッシュ値を生成し、パスワードテーブル内の同様のハッシュ値の存在をテストします。

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

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow