6

重複の可能性:
md5 デコード。彼らはどのようにそれをしますか？

このページでは、md5() や sha1() などのハッシュ アルゴリズムは、現在の処理能力が非常に高いため、逆にすることができることを示唆しています。この時点で、Rainbow Tables でのみ可能だと思いました。私は間違っていましたか？

レインボーテーブルが唯一の方法である場合、ソルトで作成されたハッシュを元に戻すにはどうすればよいでしょうか?

4

6 に答える 6

16

まあ、この質問は一般的にこの質問の複製です。ただし、正確な質問に答えるには：

この時点で、Rainbow Tables でのみ可能だと思いました。私は間違っていましたか？

技術的には、はい、あなたは間違っています。十分な処理能力があれば、回復不能なハッシュ関数はありません。重要な点は、どれだけの処理能力が必要かということです。ほとんどの場合、これは想像をはるかに超えるものです。その理由は、可能な値の数がハッシュ サイクルの各段階で指数関数的に増加するためです。MD5 の場合、各ステージ (64 個あります) は、可能性の数に 10^77 (多数のゼロ) を掛けます。そのため、MD5 を正常に反転するには、非常に多数の可能な順列を試行する必要があります (エンベロープの計算では、10^4932 試行のオーダーのどこかで示されます) 。今日作成された最速のスーパー コンピューター (約 8 ペタフロップス、または毎秒 8x10^15 浮動小数点演算) では、約 10^4908年を見ています。それを逆にします。ちなみに、これは現在の宇宙の年齢の 2.5x10^4898 倍です。本当に、私たち人間の理解を超えた膨大な数です...

そして、それは可能な限り最高の状況です。

したがって、技術的には逆転することが可能です。しかし、実際にはそうではありません。

レインボーテーブルが唯一の方法である場合、ソルトで作成されたハッシュを元に戻すにはどうすればよいでしょうか?

問題は、誰もそれを元に戻す必要がないということです。彼らはただ衝突を見つける必要があります。基本的に、衝突は同じ出力につながる 2 つの入力です。したがって、hash(a) = xとhash(b) = x、aとbは互いに衝突します。したがって、必要なのは衝突を見つけることだけです (技術的には、特定の出力を与えることができる入力は無限にあるため、正確な入力を見つけるよりも簡単であると信じています)。パスワードのサイズを入力すると、通常、衝突は元のパスワードです。

この衝突を見つける最も簡単な方法は、事前に計算されたハッシュのリスト (通常はレインボー テーブルと呼ばれます) を使用することです。基本的に必要なことは、テーブル内のハッシュを調べて、オリジナルが存在するかどうかを確認することだけです。これで完了です (簡単です)。

ソルトは通常、レインボー テーブルと戦うために追加されます。これは、ユーザー1234がパスワードとして入力し、あなたabcdefghijklmnopがソルトとして使用する場合、オリジナルは になり1234abcdefgjhijklmnop、レインボー テーブルに表示される可能性が大幅に低くなるためです。したがって、強力なソルトを追加すると、事前計算されたレインボー テーブルから保護されます。

ブルートフォーシング

ただし、そのままだと重大な懸念がありますhash(pass + salt)。事前計算されたレインボー テーブルの影響を受けませんが、ブルート フォーシングの影響を受けやすくなります。その理由は、暗号化ハッシュ関数 (sha1、md5、sha256 など) が高速になるように設計されているためです。それらの伝統的な役割は署名であるため、有用であるためには高速である必要があります。ただし、パスワード ストレージでは、これが弱点です。最新の GPU を使用すると、攻撃者は数時間でソルトを使用した単純なハッシュをブルート フォース (すべての可能なパスワード順列を試すだけ) にすることができます (詳細については、それに関する私のブログ投稿を参照してください)...

最善の予防

最善の予防策には、次の 2 つの機能があります。

  1. 値のテーブル (レインボー テーブル) を事前に計算するのは簡単ではありません

  2. 単一の値をハッシュするのは高速ではありません (総当たり攻撃は容易ではありません)。

結局のところ、ハッシュ関数を使用してそれを行う簡単な方法があります。それを単純に繰り返し、多数のハッシュ関数に依存する出力を作成します。

var result = password + salt;
for (var i = 0; i < 10000000; i++) {
    result = hash(result + salt);
}

重要なのは、人為的に遅くし、ソルトを使用することで、事前計算とブルート フォースに耐性を持たせることです。

結局のところ、これを行う標準アルゴリズムが 2 つあります (原則を使用します)。

最良のものは、Blowfish ハッシュ (bcrypt) です。これは、ハッシュ プリミティブ関数を実際には使用しませんが、Blowfish 暗号の鍵導出サイクルを使用します。経由で PHP で利用できますcrypt()。使用するには:

$hash = crypt($password, '$2a$07$' . $salt . '$');

そして、それを確認してください

$hash == crypt($password, $hash);

もう 1 つの方法 (あまり好まれません) はPBKDF2です。PHP でプログラムするには、次のようにします。

function pbkdf2($hashFunc, $password, $salt, $iterations, $length = 32) {
    $size   = strlen(hash($hashFunc, '', true));
    $len    = ceil($length / $size);
    $result = '';
    for ($i = 1; $i <= $len; $i++) {
        $tmp = hash_hmac($hashFunc, $salt . pack('N', $i), $password, true);
        $res = $tmp;
        for ($j = 1; $j < $iterations; $j++) {
            $tmp  = hash_hmac($hashFunc, $tmp, $password, true);
            $res ^= $tmp;
        }
        $result .= $res;
    }
    return substr($result, 0, $length);
}

ノート：

これらのいずれも、非常に脆弱なパスワードからユーザーを保護しません。辞書の単語や一般的なパスワードを入力した場合でも、攻撃者が解読できる可能性は高くなります。ただし、中程度の強度のパスワードに対する防御を強化します...

もう少し読む：

于 2011-10-07T18:07:16.380 に答える
2

まず、一般に、暗号化ハッシュ関数を「逆にする」ことはできません。これは、これらの関数は通常、出力よりもはるかに多くの入力データを受け取るためです。

たとえば、MD5は512入力ビット（64バイト）を受け取り、128ビット出力（16バイト）を生成します。したがって、出力を再構築するための十分な情報が入力にないだけです。実際、まったく同じ出力ハッシュを持つ異なる入力が約2 ^ 384（非常に多い数）あります。

代わりに、暗号研究者はハッシュに対する3種類の攻撃について話します。

  • 最初の原像攻撃：ハッシュhが与えられた場合、hash（m）=hとなるようなメッセージmを見つけます。
  • 2番目の原像攻撃：固定メッセージm1が与えられた場合、hash（m1）= hash（m2）となる他のメッセージm2を見つけます。
  • 衝突攻撃：hash（m1）= hash（m2）となるような2つのメッセージm1とm2を見つけます

ここで、この「逆転」ビジネスに戻ります。「MD5パスワードを破る」場合、本当にやりたいのは最初の原像攻撃です。hash （m）が保存されているハッシュhと一致するような「パスワード」mを見つけます。通常、これは総当たり攻撃で2 ^ 128の推測になります（地球上のすべてのコンピューターが1世紀で管理できる以上の数）。MD5には、これを〜2 ^ 123に下げる既知の弱点がありますが、それでも実用的ではありません。

ただし、パスワードは一般に文字と数字の短い文字列であるため、実際に使用される可能性のあるパスワードは2^128よりはるかに少なくなります。2 ^ 40（つまり約1兆）のようなものがあります。それはまだたくさんありますが、1年かそこらまたはたくさんのPS3を持っているならそれらすべてを試すことは不可能であるほど多くはありません。しかし、たくさんのパスワードを破りたいと思ったらどうしますか？毎回2^40の推測を行うのではなく、将来使用するために、可能性のあるすべてのパスワードのハッシュをディスクに保存できます。これは（多かれ少なかれ）レインボーテーブルとは何かです。誰かがすでにすべての作業を行っているので、答えを検索してほとんどの作業をスキップできます。

あなたは正しいです、塩を使うことはそれを壊します。今、あなたは2 ^ 40の推測に戻り、PS3の部屋一杯に戻ります。より優れたハッシュ関数（SHA512やSKEINなど）を使用しても、試行する必要のある可能性のあるパスワードの数は変わらないため、実際にはこれは変わりません。レッスン：パスワードを推測するのは非常に難しいです！

わかりましたが、MD5とSHA1はまだ壊れているとは見なされていませんか？はい、しかしここで本当に重要な方法ではありません（まだ）。この分野のエキサイティングなニュースはすべて、SSLセキュリティとデジタル署名の一部を破ることに関連しているが、保存されているパスワードを破ることには関係しない衝突攻撃に関するものです。暗号学者は、この作業がやがてさらに良い攻撃につながることを期待しているため、新しいプログラムでMD5またはSHA1を使用することはおそらく良い考えではありませんが、パスワードの保存にMD5 /SHA1+適切なソルトを使用しているプログラムは依然として問題ありません。

于 2011-10-08T02:34:05.147 に答える
2

おそらく、次の攻撃を使用できます。ハッシュを作成するために使用される手法は単純な計算です。

たとえば、計算が 100 のモジュラー ハッシュで行われる場合、次のようになります。

入力例: 8379547378 出力ハッシュ: 78

ハッシュ値 78 の一般式は 78 +100*k (k 個の整数) となります。したがって、すべての可能なシーケンスを試すことができます。これにより、検索スペースが 100% から 1% (この場合はモジュール 100) に減少することに注意してください。この数字が 10 桁であるという予感を確立することができれば、検索をさらに 78 +100 k (10 ^7<=k< 10^8)。

もう 1 つの方法は、非常に優れた多数のハッシュとその入口をデータベースに入力してから、このデータベースを検索することです。

少しでもお役に立てれば幸いです。

于 2011-10-05T19:02:44.603 に答える
2

レインボー テーブルは、事前に計算されたハッシュ値の「単なる」大きなテーブルであり、テーブルのごく一部のみを格納し、すべての値を参照できるようにするためのトリックが含まれています。詳細には、 N 個の可能な値を「反転」できるレインボー テーブル(つまり、テーブルが対応する入力を生成するN 個のハッシュ出力がある) の構築には約1.7*Nの時間がかかります。N 個の入力を「ただ」試して、指定されたハッシュ出力と一致するかどうかを確認します。テーブルの利点は、一致する入力を見つけたい複数のハッシュ出力がある場合です。

于 2011-09-24T01:49:41.047 に答える
1

技術的には、標準のハッシュアルゴリズムは元に戻せません。したがって、メッセージのハッシュを取得すると、そのハッシュ文字列から元のメッセージを取得する方法はありません。人々がそれをクラックしようとする唯一の方法は、ブルートフォース攻撃を使用することです。ブルートフォーシングは、可能なすべてのキーを試して、実行できる最も愚かなことです。これが、安全な暗号化アルゴリズムの特徴の1つが、大きなキースペースを持つことである理由を説明しています。しかし、場合によってはこのプロセスを利用すれば、それが実用的である可能性があります。それがまさにレインボーテーブルが行うことです。

レインボーテーブルは、特定の長さまでのすべての可能な組み合わせに対して事前に計算されたテーブルです。つまり、文字（大文字と小文字）、数字、および特定の長さまでの特殊文字のすべての可能な組み合わせを作成することを意味します。私の知る限り、最も完全なレインボーテーブルは、数字、大文字、特殊文字を含む最大10文字の文字列のハッシュを分割できるため、それより長い文字列がある場合は、ハッシュ自体を分割することについてセキュリティ上の懸念はありません。ここでわかるように、最大​​8文字のビスタパスワードを破ることができるテーブルのサイズは100 GBを超えており、その数は指数関数的に増加するため、10文字または12文字を超えることは不可能です。

文字列を推測するのが簡単でなく、十分な長さで、大文字、数字、特殊文字が含まれている限り、心配する必要はありません:)

于 2011-10-07T18:13:33.247 に答える
0

そのページが話しているブルート フォーシングは、基本的にその場でのレインボー テーブルの生成です。

于 2011-09-23T02:24:34.350 に答える