[解決済み] ハッシュ化アルゴリズムと暗号化アルゴリズムの根本的な違い

質問

ハッシュと暗号化アルゴリズムが混同されているのを見かけますが、もう少し専門家のアドバイスを聞きたいと思います。

1. ハッシュと暗号の使い分け

2. ハッシュアルゴリズムと暗号化アルゴリズムは何が違うのか（理論・数学的なレベルより） すなわち、ハッシュを（レインボーツリーの助けを借りずに）不可逆にするもの

以下は 類似 SOの質問は、私が探しているほど詳しくはありません。

難読化、ハッシュ化、暗号化の違いは何ですか？
暗号化とハッシュ化の違い

どのように解決するのですか？

で調べればいいんだけど ウィキペディア ... しかし、あなたは説明を求めているので、私はここで最善を尽くします。

ハッシュ関数

任意の長さの入力と、（通常は）固定長（またはそれより小さい長さ）の出力との間のマッピングを提供します。 単純な crc32 から、MD5 や SHA1/2/256/512 のような本格的な暗号ハッシュ関数まで、何でも可能です。 ポイントは、一方通行のマッピングが行われていることです。 どの関数も入力可能な値よりも小さな出力を生成するため、常に多：1のマッピング（つまり常に衝突が発生する）です（1MBのファイルをすべてMD5に入力すると、衝突が大量に発生します）。

逆上がりが難しい（あるいは現実的には不可能）理由は、内部での仕組みにあります。 ほとんどの暗号ハッシュ関数は、入力セットに対して何度も繰り返し処理を行い、出力を生成しています。 つまり、入力の固定長の塊（アルゴリズムに依存する）をそれぞれ見ると、ハッシュ関数はそれを「現在の状態」と呼ぶ。 そして、その状態を繰り返し、新しい状態に変更し、それを自分へのフィードバックとして使用します（MD5は512ビットのデータチャンクごとに64回この処理を行います）。 MD5は512ビットのデータチャンクごとに64回これを行う）そして、これらの反復処理の結果の状態を何らかの方法で結合し、結果のハッシュを形成する。

ここで、ハッシュを解読しようと思ったら、まず与えられたハッシュをどのように反復状態に分割するかを考える必要があります（データチャンクのサイズより小さい入力には1つの可能性、大きい入力には多くの可能性）。 そして、各状態で繰り返しを逆転させる必要があります。 では、なぜこれが非常に難しいかを説明するために、次のようなことを想像してみてください。 a と b を次の式から求める。 10 = a + b . の正の組み合わせは10通りあります。 a と b というのは、うまくいくことがあります。 今度はそれを何度もループさせて tmp = a + b; a = b; b = tmp . 64回繰り返せば、10^64以上の可能性を試すことができます。 これは単純な足し算で、ある状態が反復から反復へと保存されるだけです。 実際のハッシュ関数は1回の演算よりずっと多くの演算をします（MD5は4つの状態変数に対して約15回の演算をします）。また、次の反復は前の状態に依存し、前の状態は現在の状態を作成する際に破壊されるため、ある出力状態に至った入力状態を（各反復について）決定することはほとんど不可能です。 このことと、関係する多くの可能性を組み合わせると、MD5さえ解読するのに無限に近い（しかし無限ではない）量のリソースが必要になります。入力のサイズがわかっている場合、ハッシュをブルートフォースする方が、ハッシュを解読するよりもはるかに安上がりなのです（小さい入力の場合）。

暗号化関数

任意の長さの入力と出力を1対1に対応させることができる。 また、常に可逆である。 重要なのは、何らかの方法を用いて可逆であることです。 そして、与えられたキーに対して常に1:1であることです。 さて、同じ出力を生成する可能性のある入力と鍵のペアは複数存在します（実際、暗号化関数によっては通常存在します）。 良い暗号化データは、ランダムなノイズと区別がつきません。 これは、常に一貫した形式で出力される優れたハッシュ出力とは異なります。

使用例

ある値を比較したいが、（様々な理由で）プレーンな表現を保存できない場合にハッシュ関数を使用する。 パスワードは、セキュリティ上の理由から平文で保存したくない（保存すべきではない）ので、このユースケースに非常によく合うはずです。 しかし、海賊版の音楽ファイルをファイルシステムでチェックしたい場合はどうでしょう？ 音楽ファイル1つにつき3MBを保存するのは非現実的でしょう。 そこで、代わりにファイルのハッシュ値を取って、それを保存します（md5なら3MBではなく16バイトを保存します）。 この方法では、各ファイルをハッシュ化し、保存されたハッシュのデータベースと比較するだけです（再エンコードやファイルヘッダの変更などにより、実際にはそれほどうまくいきませんが、使用例として挙げました）。

ハッシュ関数は、入力データの妥当性をチェックするときに使う。 そのために設計されているのだから。 2つの入力があり、それらが同じかどうかをチェックしたい場合、両方をハッシュ関数に通してください。 小さな入力サイズであれば、衝突の確率は天文学的に低い（良いハッシュ関数であると仮定して）。 そのため、パスワードにはハッシュ関数が推奨される。 32文字までのパスワードの場合、md5は出力スペースが4倍になる。 SHA1は6倍の出力スペースがあります（約）。 SHA512は約16倍の出力スペースがあります。 パスワードが何であるかはあまり気にしない でした 保存されているものと同じかどうかが重要なのです。 だから、パスワードにはハッシュを使うべきなのです。

入力されたデータを取り出す必要があるときは、いつでも暗号化を使用します。 ここで 必要 . クレジットカードの番号を保存している場合、いつかは取り出す必要がありますが、平文で保存することは避けたいものです。 そこで、暗号化したものを保存し、鍵はできるだけ安全に保管します。

ハッシュ関数は、データへの署名にも最適です。 例えば、HMACを使用する場合、データのハッシュ値と既知だが送信されていない値（秘密値）を連結して、データの一部に署名することになります。 そこで、平文とHMACのハッシュを送信します。 そして、受信者は送信されたデータを既知の値でハッシュ化し、送信されたHMACと一致するかどうかをチェックするだけである。 もし同じなら、秘密の値を持たない人物によって改ざんされていないことがわかります。 これは、HTTPフレームワークによるセキュアクッキーシステムや、データの完全性をある程度保証したいHTTP上のデータメッセージ送信でよく使用されています。

パスワードのハッシュ化に関する注意点

暗号ハッシュ関数の主な特徴は、作成が非常に高速であること、そして 非常に 逆引きが難しい／遅い（事実上不可能なほど）。 このことは、パスワードの場合に問題となる。 もし、あなたが sha512(password) レインボーテーブルやブルートフォースアタックに対抗することはできないのです。ハッシュ関数は高速化のために設計されていることを忘れないでください。 だから、攻撃者が辞書をハッシュ関数に通して、それぞれの結果をテストするのは簡単なことなのだ。

ソルトを追加すると、ハッシュに未知のデータが追加されるため、問題解決に役立ちます。 つまり md5(foo) を生成するものを見つける必要があります。 md5(foo.salt) (これは非常に難しいのですが)。 しかし、塩がわかっていれば、あとは辞書を走らせるだけなので、スピードの問題はまだ解決していない。

そこで、これに対処する方法があります。 よく使われる方法として キー強化 (またはキーストレッチ）。 基本的には、ハッシュを何度も（通常は数千回）繰り返し処理します。 これには2つの意味があります。 まず、ハッシュアルゴリズムの実行時間が大幅に短縮される。 第二に、正しく実装された場合（反復のたびに入力とソルトを渡す）、実際に出力のエントロピー（利用可能な空間）が増加し、衝突の可能性を減らすことができます。 些細な実装は

var hash = password + salt;
for (var i = 0; i < 5000; i++) {
    hash = sha512(hash + password + salt);
}

その他にも、以下のような標準的な実装があります。 PBKDF2 , BCクリプト . しかし、この技術はかなり多くのセキュリティ関連システム（PGP、WPA、Apache、OpenSSLなど）で使用されています。

肝心なのは hash(password) は十分ではありません。 hash(password + salt) の方が良いですが、まだ十分ではありません...。 パスワードハッシュを生成するために、ストレッチングされたハッシュ機構を使用する...

トリビアルストレッチに関するもう一つの注意点

どんなことがあっても、あるハッシュの出力を直接ハッシュ関数にフィードバックしないでください。 :

hash = sha512(password + salt); 
for (i = 0; i < 1000; i++) {
    hash = sha512(hash); // <-- Do NOT do this!
}

その理由は、衝突と関係があります。 すべてのハッシュ関数が衝突を起こすのは、可能な出力空間（可能な出力の数）が入力空間より小さいからです。 その理由を知るために、何が起こるか見てみましょう。 まず、衝突の確率は0.001%であると仮定します。 sha1() (それは 大いに 実際にはもっと低いのですが、デモンストレーションのためです)。

hash1 = sha1(password + salt);

今すぐ hash1 は衝突する確率が0.001%である。 しかし、次の hash2 = sha1(hash1); , のすべての衝突は hash1 の衝突になります。 hash2 . そこで、hash1 のレートを 0.001% とし、2 番目の sha1() の呼び出しが追加されます。 だから今 hash2 が衝突する確率は0.002%です。 これは2倍の確率です 各反復処理で、さらに 0.001% となります。 つまり、1000回の繰り返しで、衝突の確率は0.001%という些細なものから1%に跳ね上がったのです。 さて、劣化は線形であり、実際の確率は次のようになります。 はるか との1回の衝突の確率を推定した場合）、その効果は同じです。 md5 は約1/(2 ¹²⁸ ) または 1/(3x10 ³⁸ ). これは小さいように見えますが バースデーアタック は、実際には見かけほど小さくはありません）。

その代わり、ソルトとパスワードを毎回再適用することで、ハッシュ関数にデータを再投入していることになります。 そのため、特定のラウンドでの衝突は、次のラウンドではもう衝突しないのです。 だから

hash = sha512(password + salt);
for (i = 0; i < 1000; i++) {
    hash = sha512(hash + password + salt);
}

ネイティブと同じ確率で衝突します。 sha512 関数を使用します。 これは、あなたが望むものです。 代わりにそれを使ってください。