36

md5ハッシュに関するウィキペディアの記事を読みましたが、ハッシュを元のテキストに「再構成」できない方法を理解できません。

暗号化についてほとんど知らない人に、これがどのように機能するかを誰かが説明できますか？関数のどの部分が一方向になりますか？

4

7 に答える 7

51

今まで誰もがハッシュ関数とは何かを簡単に定義していたので、噛み付きます。

一方向関数は、単なるハッシュ関数 (情報を失う関数) ではなくf、イメージy(「SE」または既存の回答の 294) が与えられた場合、プレイメージ x を見つけるのが難しい関数です。そのようなf(x)=y。

これが一方向と呼ばれる理由です。画像を計算することはできますが、特定の画像の前の画像を見つけることはできません。

既存の回答でこれまで提案された通常のハッシュ関数には、このプロパティはありません。いずれも一方向の暗号化ハッシュ関数ではありません。たとえば、"SE" を指定すると、入力 "SXXXE" を簡単に取得できます。これは、X-encode("SXXXE")=SE というプロパティを持つ入力です。

「単純な」一方向関数はありません。入力を非常にうまく混合する必要があるため、出力で入力がまったく認識されないだけでなく、別の入力も認識されません。

SHA-1 と MD5 は以前は一般的な一方向関数でしたが、どちらもほとんど機能していません (専門家は特定のイメージのプリイメージを作成する方法を知っているか、ほとんど作成できます)。SHA-3という名前の新しい標準を選択するためのコンテストが進行中です。

一方向関数を反転するための明白なアプローチは、多くの画像を計算し、それを生成した前の画像を各画像に関連付けるテーブルに保持することです。これを実際に不可能にするために、すべての一方向関数は、少なくとも 64 ビットですが、場合によってはもっと大きい (たとえば、512 ビットまで) という大きな出力を持ちます。

編集: ほとんどの暗号化ハッシュ関数はどのように機能しますか?

通常、それらのコアには、ビットのブロック (ブロック暗号) で複雑な変換を行う単一の機能があります。この関数は、ほぼ全単射であるべきですが (あまりにも多くのシーケンスを同じ画像にマップするべきではありません。後で弱点が生じるためです)、完全に全単射である必要はありません。そして、この関数は、入力 (または可能な入力) を認識できないようにするのに十分な回数だけ反復されます。

SHA-3 コンテキストの強力な候補の 1 つであるSkeinの例を見てみましょう。そのコア機能は 72 回繰り返されます。関数の作成者が出力をいくつかの入力に関連付ける方法を知っている唯一の反復回数は25回です。彼らは、2.9の「安全係数」があると言います。

于 2010-01-21T20:59:40.770 に答える
49

本当に基本的なハッシュを考えてみてください。入力文字列については、各文字のASCII値の合計を返します。

hash( 'abc' ) = ascii('a')+ascii('b')+ascii('c')
              = 97 + 98 + 99
              = 294

さて、ハッシュ値が294の場合、元の文字列が何であったかわかりますか？'abc'と'cba'（および他の無数の）が同じハッシュ値を与えるため、明らかにそうではありません。

暗号化ハッシュ関数は、明らかにアルゴリズムがはるかに複雑であることを除いて、同じように機能します。s常に衝突が発生しますが、文字列のハッシュを知っている場合は、もハッシュする別の文字列を作成hすることは非常に困難です（「計算上実行不可能」）。h

于 2010-01-21T20:43:24.803 に答える
34

ここでは、複雑な説明ではなく、単純な類推を求めています。

まず、主題を一方向操作とハッシュの 2 つの部分に分けてみましょう。一方向操作とは何ですか? なぜそれが必要なのですか?

一方向操作は、元に戻すことができないため、そう呼ばれます。加算や乗算などのほとんどの一般的な演算は逆にすることができますが、剰余除算は逆にすることができません。なぜそれが重要なのですか？1）元の入力なしでは複製が困難であり、2）出力からの入力を把握する方法がない出力値を提供したいためです。

可逆

追加： 

4 + 3 = 7

これは、合計を取り、加数の 1 つを引くことによって逆にすることができます。

7 - 3 = 4

乗算:

4 * 5 = 20

これは、積をとって因数の 1 つで割ることによって逆にすることができます。

20 / 4 = 5

不可逆

モジュロ除算:

22 % 7 = 1

除数を再構成するために商と被除数に対して実行できる操作がないため (またはその逆)、これを元に戻すことはできません。

「?」の場所を埋める操作を見つけることができますか? は？ 

1  ?  7 = 22  
1  ?  22 = 7

そうは言っても、一方向ハッシュ関数はモジュロ除算と同じ数学的品質を持っています。

何でこれが大切ですか？

1,000 個のロッカーがあるバスターミナルのロッカーの鍵をあなたに渡し、それを私の銀行員に届けるように頼んだとしましょう。あなたは賢い人なので、疑わしいことは言うまでもなく、すぐにキーを見て、キーに書かれているロッカー番号を確認します。これを知って、私はいくつかのよこしまなことをしました。最初に、剰余除算を使用して割ると 1 から 1000 の範囲の数値が得られる 2 つの数値を見つけました。次に、元の数値を消去して、数値のペアからの除数を書き込みました。次に、悪党からロッカーを守るために、鍵を使って 1 日に 1 つのロッカーだけを試してもらいます。3 番目に、銀行家はすでに配当を知っているので、鍵を手に入れたら、計算して残りを計算し、どのロッカーを開くかを知ることができます。

オペランドを賢く選択すれば、商と被除数の間の 1 対 1 の関係に近づくことができます。これにより、各ロッカーを試す必要が生じます。これは、答えが可能な入力の結果を希望する数値の範囲 (ロッカー) に広げるためです。ターミナルで利用できます。基本的には、オペランドの 1 つを知っていても、剰余についての知識を取得できないことを意味します。

これで、鍵がどのロッカーに属しているか簡単に推測できることを心配することなく、正当な所有者に鍵を届けることを「信頼」できます。確かに、すべてのロッカーを力ずくで検索することはできますが、それにはほぼ 3 年かかり、銀行員が鍵を使用してロッカーを空にするのに十分な時間がかかります。

さまざまなハッシュ関数の詳細については、他の回答を参照してください。

于 2010-01-22T15:46:28.453 に答える
12

これは非常に簡単な例です。私は初心者の暗号学者であり、次のことを行うハッシュ関数を作成するとします。

int SimpleHash(file) {
    return 0 if file.length is even;
    return 1 if file.length is odd;
}

では、テストです。 SimpleHash(specialFile)は 0 です。元のファイルは何ですか?

明らかに、知る方法はありません (ただし、私のハッシュがファイルの長さに基づいていることはかなり簡単にわかるでしょう)。ハッシュには私のファイルが行ったすべてが含まれていないため、ハッシュに基づいてファイルを「再構成」する方法はありません。

于 2010-01-21T21:11:49.880 に答える
10

簡単に言えば、ハッシュ関数は、入力データを大きく絡み合わせることによって機能します。

たとえば、MD5を参照してください。入力データを 512 ビットのブロック単位で処理します。各ブロックは 16 個の 32 ビット ワードに分割されます。64 のステップがあり、各ステップは 16 の入力単語の 1 つを使用します。したがって、各単語はアルゴリズムの過程で 4 回使用されます。ここから一方向性が生まれます。任意の入力ビットがいくつかの場所で入力され、そのような 2 つの入力の間で、関数は現在のすべてのデータを混合して、各入力ビットが 128 ビットの実行状態のほとんどに影響を与えるようにします。これにより、データの一部だけを見て、関数を逆にしたり、衝突を計算したりすることがなくなります。128 ビット全体を調べる必要があり、128 ビット ブロックのスペースは広すぎて効率的に調べることができません。

現在、MD5 は、その関数の衝突が見つかる可能性があるため、うまく機能しません。暗号学者の観点から見ると、MD5 はローテーションされた暗号化機能です。1 つのメッセージ ブロック M (512 ビット) の処理では、入力状態 V (128 ビット値) を使用し、新しい状態 V' を V' = V + E(M, V) として計算します。ここで、'+' は単語です。賢明な追加であり、「E」はたまたま対称暗号化関数（別名「ブロック暗号」）であり、M をキーとして使用し、V を暗号化するメッセージとして使用します。よく見ると、E can は一種の「拡張 Feistel ネットワーク」であり、DES ブロック暗号に似ており、2 つの半分ではなく 4 つの四分の一を備えています。ここでは詳細は重要ではありません。私のポイントは、その構造を使用するハッシュ関数 (「Merkle-Damgård」と呼ばれる) の中で、何が「良い」ハッシュ関数を作るのかということです。ブロック暗号を「安全」にするものに似ています。MD5 で成功した衝突攻撃は、そもそもブロック暗号を攻撃するために設計されたツールである差分暗号解読を使用しています。

優れたブロック暗号から優れたハッシュ関数まで、無視できないステップがあります。Merkle-Damgård 構造では、基礎となるブロック暗号が「関連キー攻撃」に耐性がある場合、ハッシュ関数は安全です。対称暗号化の場合、関連キー攻撃はほとんど実用的でないため、ブロック暗号が強化されることはめったにありません。影響。たとえば、AES 暗号化は、関連するキー攻撃に対して期待したほど耐性がないことが判明しましたが、これは一般的なパニックを引き起こすことはありませんでした。その耐性は、AES が設計されたときに求められた特性の一部ではありませんでした。AESをハッシュ関数に変換するのを防ぐだけです。Rijndael の派生物に基づいて構築された Whirlpool と呼ばれるハッシュ関数があります。「Rijndael」は AES になったものの最初の名前です。

また、ハッシュ関数を構築するために使用できる他の構造もあります。現在の標準関数 (MD5、SHA-1、および「SHA-2」ファミリ、別名 SHA-224、SHA-256、SHA-384、および SHA-512) は Merkle-Damgård 関数ですが、その多くは後継者はそうではありません。「SHA-3」と呼ばれる新しい標準ハッシュ関数を選択するために、NIST (その種のものを扱う米国連邦機関) によって組織された進行中の競争があります。詳しくはこちらのページをご覧ください。現在、最初の 51 人から 14 人の候補者に減っています (適切にコンパイルおよび実行されるコードを含む完全な提出物を送信するという管理テストに失敗した 12 人の余分な人は数えません)。

ここで、より概念的な外観を見てみましょう。安全なハッシュ関数は、ランダム オラクルのように見える必要があります。オラクルは、メッセージMが入力として与えられると、ランダムに選択された答えh(M)を出力空間で一様に出力するブラック ボックスです(つまり、すべてのn -ハッシュ関数の出力長がnの場合はビット文字列)。同じメッセージMが入力として再び与えられると、オラクルは以前と同じ値を出力します。その制限とは別に、以前に使用されていない入力Mに対するオラクルの出力予測不可能です。オラクルは、サイコロを投げ、入力メッセージと対応する出力を大きな本に注意深く記録するノームの入れ物としてオラクルを想像することができます。gnome 自身はそれを知らないため、次の出力がどうなるかを予測する方法はありません。

ランダムなオラクルが存在する場合、ハッシュ関数の反転には2^nのコストがかかります。特定の出力を得るには、期待値が得られるまで個別の入力メッセージを使用するよりも優れた戦略はありません。一様ランダム選択のため、各試行での成功確率は1/(2^n)であり、サイコロを投げるノームへのリクエストの平均数は2^nになります。衝突 (同じハッシュ値を生成する 2 つの異なる入力を見つける) の場合、コストは約1.4 2^(n/2)* (大まかに言えば、1.4 2^(n/2)* 出力で、約2^を組み立てることができます) nペアの出力。それぞれの確率は1/(2^n)つまり、同じ出力を持つ 2 つの別個の入力を持つ)。これらは、ランダムなオラクルで実行できる最高のものです。

したがって、ランダムオラクルと同じくらい優れたハッシュ関数を探します。関数2^(n/2 )回。ハッシュ関数の悩みの種は数学的構造です。つまり、攻撃者がハッシュ関数の内部状態 (大きく、少なくともnビット) を、はるかに短い空間に存在する数学的オブジェクトのバリエーションとして表示できるようにするショートカットです。対称暗号化システムに関する 30 年間の公的研究により、適用可能な概念とツール (拡散、雪崩、微分、直線性...) の道具一式が生み出されました。ただし、結論として、ランダムオラクルが実際に存在する可能性があるという証拠はありません。私たちは欲しい攻撃できないハッシュ関数。私たちが持っているのは、現在攻撃が知られていないハッシュ関数の候補です .

まだ研究が必要です。

于 2010-01-22T15:25:53.430 に答える
8

ハッシュは（非常に）不可逆エンコーディングです。

より簡単な例を示すために、Xエンコーディングと呼ばれる5文字の単語の架空の2文字のエンコーディングを想像してみてください。Xエンコーディングのアルゴリズムは単純です。単語の最初と最後の文字を取得します。

それで、

X-encode( SAUCE ) = SE
X-encode( BLOCK ) = BK

明らかに、エンコーディングSEからSAUCEを再構築することはできません（可能な入力の範囲がすべて5文字の単語であると想定しています）。単語は同じくらい簡単にスペースである可能性があります。

余談ですが、SAUCEとSPACEの両方がSEをエンコーディングとして生成するという事実は衝突と呼ばれ、X-ecodingはあまり良いハッシュを作成しないことがわかります。:)

于 2010-01-21T20:45:07.603 に答える
3

配列
少し目を細めてみると、連想配列はハッシュに非常によく似ています。主な違いは、ハッシュ名に % 記号がないことと、一度に 1 つのキーしか割り当てることができないことです。したがって、 と言う人もいます$foo{'key'} = 1;が、 だけ@keys = keys(foo);です。each、keys、values などの使い慣れた関数は、現在と同じように機能しました (そして、delete は Perl 2 で追加されました)。

Perl 3 には 3 つの完全なデータ型がありました: ハッシュ名に % 記号があり、ハッシュ全体を一度に割り当てることができ、dbmopen が追加されました (tie が優先されて非推奨になりました)。Perl 4 では、コンマ区切りのハッシュ キーを使用して多次元配列をエミュレートしました (これは、配列参照でより適切に処理されるようになりました)。

Perl 5 は、連想配列をハッシュとして参照するという大きな飛躍を遂げました。(私の知る限り、「ハッシュテーブル」などではなく、このようにデータ構造を参照した最初の言語です。) 皮肉なことに、関連するコードも hash.c から hv.c に移動しました。

前に説明したように、命名
辞書は、一意のキーによってインデックス付けされた値の順序付けられていないコレクションです。それらは、連想配列またはマップと呼ばれることもあります。これらはいくつかの方法で実装できますが、そのうちの 1 つは、ハッシュ テーブルと呼ばれるデータ構造を使用することです (これは Perl がハッシュと呼んでいるものです)。

Perl での「ハッシュ」という用語の使用は、潜在的な混乱の原因です。これは、ハッシュ関数の出力が (特に暗号化のコンテキストで) ハッシュと呼ばれることもあり、ハッシュ テーブルは通常、他の場所ではハッシュと呼ばれないためです。

安全を期すために、データ構造をハッシュテーブルと呼び、「ハッシュ」という用語は明らかな Perl 固有のコンテキストでのみ使用してください。

于 2012-07-31T18:37:20.717 に答える