レインボーテーブルとは何ですか？どのように使用されますか？

レインボーテーブルは一般的にと混同されます計算時間を活用する別のより単純な手法-sパスワード回復のトレードオフを激怒させる：ハッシュテーブル。

ハッシュテーブルは、パスワード辞書の各単語をハッシュすることによって構築されます。パスワードとハッシュのペアは、ハッシュ値でソートされたテーブルに格納されます。ハッシュテーブルを使用するには、ハッシュを取得し、テーブル内でバイナリ検索を実行して、元のパスワードが存在する場合はそれを見つけます。

レインボーテーブルはより複雑です。レインボーテーブルの作成には、2つのことが必要です。 ：ハッシュ関数とリダクション関数。特定のレインボーテーブルセットのハッシュ関数は、回復するハッシュパスワードと一致する必要があります。リダクション関数は、ハッシュをパスワードとして使用できるものに変換する必要があります。単純なリダクション関数はBase64です。ハッシュをエンコードしてから、特定の文字数に切り捨てます。

レインボーテーブルは、特定の長さの「チェーン」で構成されます。たとえば、100,000です。チェーンを構築するには、ランダムなシード値を選択します。このシードとその出力にハッシュ関数とリダクション関数を適用し、100,000回繰り返します。シードと最終値のみが保存されます。このプロセスを繰り返して、必要な数のチェーンを作成します。

回復するにはレインボーテーブルを使用したパスワード、パスワードハッシュが実行されます同じ長さの上記のプロセス：この場合は100,000ですが、チェーン内の各リンクは保持されます。チェーン内の各リンクは、各チェーンの最終値と比較されます。一致する場合は、各ハッシュ関数の出力と各削減関数の出力の両方を保持したまま、チェーンを再構築できます。その再構築されたチェーンには、問題のパスワードのハッシュとそれを生成したパスワードが含まれます。

ハッシュテーブルの長所は、パスワードの回復が非常に高速であり（バイナリ検索）、人を構築することです。ハッシュテーブルは、上位10,000個のパスワードなど、何を入力するかを選択できます。レインボーテーブルと比較した場合の弱点は、ハッシュテーブルがすべてのハッシュとパスワードのペアを格納する必要があることです。

レインボーテーブルには、これらのテーブルを作成する人が、リンクの数を選択することで必要なストレージの量を選択できるという利点があります。各チェーン。シードと最終値の間のリンクが多いほど、より多くのパスワードがキャプチャされます。弱点の1つは、チェーンを構築する人がキャプチャしたパスワードを選択しないため、RainbowTablesを一般的なパスワード用に最適化できないことです。また、パスワードの回復にはハッシュの長いチェーンの計算が含まれるため、回復にはコストのかかる操作が必要になります。チェーンが長いほど、より多くのパスワードがチェーンに取り込まれますが、内部でパスワードを見つけるのに時間がかかります。

ハッシュテーブルは一般的なパスワードに適しており、レインボーテーブルはタフなパスワードに適しています。最善のアプローチは、ハッシュテーブルを使用してできるだけ多くのパスワードを回復するか、上位N個のパスワードの辞書を使用して従来のクラッキングを行うことです。残っているものについては、レインボーテーブルを使用してください。

コメント

• ああ、ショックを受けたことは認めます。レインボーテーブルについてすべて話し合い、説明します。時間、そしてこの間ずっと、私は”よく混乱している”の1人だったようです！私は完全に+1000回、ここで本当に新しいことを学びました（そして私は答えを知っていると思いました）。結局、質問をしてよかった…ありがとうございます！
• 具体的には（目を開けたので、もう少し調査しました:)）、レインボーテーブルはヘルマンハッシュチェーンと区別されます。 いくつかの異なる削減機能。確かにもっと複雑です…しかし、本当にとても美しいアイデアです（ああ、それがだから彼らが’と呼ばれる理由です” Rainbow “テーブル？）
• これは非常に良い説明であることに同意します。私の答えでは、私はそれを簡単に説明しましたが、単純にすることによってそれを本当に間違って説明しました。レインボーテーブルの美しさは、すべてのハッシュ値を保存しない’という事実です。私は自分の編集を行いますが、これは間違いなくより良い説明であるため、賛成票を投じます。
• うーん…考えれば考えるほど、実際のシステムではレインボーテーブルはそれほど有用ではありません。ハッシュテーブル。あなたが述べたように、一般的なパスワードの場合、ハッシュテーブルははるかに優れています（それらは桁違いに高速であり、パスワードディクショナリのサイズ要件はもちろんパスワードの可能な範囲全体よりもはるかに小さいため）。そして、誰が’冗談ですか？ほとんどのパスワードはこのカテゴリに分類され、RTで呼び出す必要があることは非常にまれです（しばらくの間はそうなります）。
• 残念ながら、ここで私を失いました：” Rainbow Tablesを使用してパスワードを回復するには、パスワードは同じ長さで上記のプロセスを実行します。”パスワードがも知られていない？パスワードハッシュのことですか？また、’次のようになります：”チェーン内の各リンクが各チェーンの最終値と比較されます。”リンク値が継続的にハッシュされて削減されるため、チェーン内のリンクがチェーン内の最終値と一致する状況がわかりません。

レインボーテーブルとは何かについて多くの良い説明があります。これはレインボーテーブルのしくみは特に良いです。また、ウィキペディアの記事にも非常に良い説明があります。このテーマに関する最も信頼のおける論文をもう少し詳しく読むには、暗号解読の時間とメモリのトレードオフを高速化するをご覧ください。

レインボーテーブルの簡単な説明は、時間と空間のトレードオフ手法を利用しているということです。つまり、ターゲットハッシュ値と単語の辞書を取得してから、各単語をハッシュしてその場で比較を行うのではなく（ John などを使用した強引なアプローチ）、代わりに、辞書内のすべての値を事前にハッシュします（辞書のサイズによっては、非常に長い時間がかかる場合があります）。ただし、完了したら、レインボーテーブルの事前にハッシュされた値と必要な数のハッシュを比較できます。これは、ハッシュを再度計算するよりも大幅に高速です。

以前にここで書いた説明レインボーテーブルが利用する削減の使用について説明していなかったため、短くする努力は誤解を招くものでした。このビットを書き直すまでのより良い説明については、 @Crunge answer を参照してください。

のようなアプリケーションを使用して自分でレインボーテーブルを生成できます。 div id = “7153fdb9cf”>

目的と関連性

レインボーテーブルは、難しいパスワード、つまり大きな辞書にも見つからないパスワードを解読するのに役立ちます。パスワードはこれまでデータベースにプレーンハッシュとして保存されていました。これがレインボーテーブルの効果です。単一のレインボーテーブルを作成し（低速）、ハッシュでいっぱいのデータベースをいくつでも実行します（高速）。

最近、Bcrypt、Scrypt、Argon2などの適切なパスワードストレージアルゴリズムを使用するシステムが増えています。パスワードを安全に[保存]する方法を参照してください。これらのアルゴリズムは次のとおりです。レインボーテーブルに対して「脆弱」ではなくなりました。各ハッシュは一意であるため、パスワードが同じであっても、レインボーテーブルは機能しなくなります。

そのため、今日、レインボーテーブルは人気がありません。Argon2のような最新のものが使用されていない場合でも、最近の開発者は通常、少なくともソルトを使用する必要があることを知っています。レインボーテーブルを役に立たなくするには、これですでに十分です。

動作方法

テーブルの作成

それぞれが長さ5の2つのチェーンだけでレインボーテーブルを作成するとします。レインボーテーブルは、48ビット（12個の16進文字のみ）を出力する架空のハッシュ関数MD48用です。チェーンを構築すると、次のように表示されます。

Chain 0: 0=cfcd208495d5 => z=fbade9e36a3f => renjaj820=7668b2810262 => aL=8289e8a805d7 => ieioB=2958b80e4a3a => WLgOSj Chain 1: 1=c4ca4238a0b9 => ykI4oLkj=140eda4296ac => Dtp=1b59a00b7dbe => W=61e9c06ea9a8 => 6cBuqaha=d4d2e5280034 => 0uUoAD 

最初のチェーンであるため、0から始めます。 （最初にいくつかの値が必要です）これをMD48でハッシュすると、cfcd208495d5になります。次に、基本的にこのハッシュをフォーマットして戻す「reduce」関数を適用します。パスワードを入力すると、「z」になります。これを再度ハッシュすると、fbade9e36a3fが取得され、次にそれを縮小してrenjaj820が取得されます。 。さらにいくつかのサイクルがあり、最終結果はWLgOSjです。

2番目のチェーンについても同じです。別の値から始めて、同じことを行います。これは0uUoADで終わります。

完全なレインボーテーブルは次のようになります：

WLgOSj => 0 0uUoAD => 1 

保存する必要があるのはこれだけです。

ハッシュを検索する

オンラインでハッシュを見つけたとしましょう。7668b2810262。テーブルを使って解読しましょう！

Looking for hash "7668b2810262", reduced to "aL". hashed=>reduced "aL" to ieioB hashed=>reduced "ieioB" to WLgOSj Found a match, "WLgOSj" is in our rainbow table: WLgOSj => 0 The chain starts with "0". Let"s walk that chain and look for the hash. hashed "0" to cfcd208495d5 hashed "z" to fbade9e36a3f hashed "renjaj820" to 7668b2810262 That hash matches! Found the password: renjaj820 

自分で試してみるために、上記の例は次のPythonスクリプトを使用して作成されました： https://gist.github.com/lgommans/83cbb74a077742be3b31d33658f65adb

スケーリングプロパティ

要するに：

• カバレッジが同じであると仮定すると、高速ルックアップはより大きなテーブルを意味します。
• カバレッジが良いとは、ルックアップが遅くなるか、テーブルが大きくなることを意味します。
• テーブルが小さいと、ルックアップが遅くなるか、カバレッジが悪くなります。

次のセクションでは、ハッシュ+リダクションあたりの時間が1µsであると想定しており、衝突を考慮していません。これらはすべて球場の数値であり、正確な値ではなく例として意図されています。

ルックアップ時間

ハッシュ+削減操作にマイクロ秒かかる場合、100万チェーンとチェーンあたり10,000削減のテーブルを生成するには、約3時間かかります。
chain_length × chain_count / reductions_per_second / seconds_per_hour
= 10 000 × 1 000 000 / 1 000 000 / 3600 = 2.8時間。

そのテーブルでルックアップを実行するには、平均10ミリ秒かかります。これは、ハッシュが含まれているチェーンを見つける前に、通常はchain_length/2の削減を行う必要があるためです。たとえば、テーブルにある値を見つける前に、ハッシュに対して3000回の削減を行う必要がある場合があります。次に、一致する値が見つかるまで、そのチェーンを最初からやり直す必要があります。テーブルでそれを見つけるために3000を実行する必要がある場合、チェーンの適切なポイントに到達するために、最初から7000の削減を実行する必要があります。基本的に、ルックアップするときは、単一のチェーンを生成するときと同じ数の操作を実行します。したがって、ルックアップ時間はマイクロ秒の10000倍、つまり10ミリ秒（または必要に応じてセンチ秒）です。

ストレージ要件

MD5であっても、ハッシュ関数の完全で高速なルックアップテーブルを作成する場合は、「1,000億テラバイトのストレージが必要です。」あまり役に立ちません。しかし、10文字まで小文字のパスワードのみをカバーしたい場合はどうなりますか？

ハッシュの検索に最大30秒を費やし、ハッシュごとに1マイクロ秒（100万分の1秒）が必要であると仮定した場合はどうなりますか？ +サイクルを減らすと、チェーンの長さは1 million × 30 = 3,000万になります。 10文字の可能な小文字のパスワードは26 ¹⁰ （または10 ¹⁴ ）あり、チェーンごとに3,000万の値をカバーします。それは私たちに400万のチェーンを残します。各チェーンには開始値と終了値のみが格納されており、値はそれぞれ10文字であることがわかっています。したがって、2 × 10 × 4 million = 76MiBデータ。

10文字のパスワードすべてを反復処理してテーブルを生成するには、長い時間がかかります。チェーンあたり30秒、チェーンの400万倍は約91年。しかし、多くの人がこのようなテーブルに興味を持っているので、1092個のCPU（= 91×12）をプールすることで、1か月しかかかりません。これは、そのようなテーブルがカバーするパスワードスペースと比較してどれほど小さいかを示しています。ルックアップには30秒しかかからず、76MiBデータのみを保存する必要があります。

結論

レインボーテーブルは時間とメモリのトレードオフと見なされます。テーブルのごく一部のみを格納し、ルックアップ時間の追加計算によってそれを回復します。これは、パスワードを安全に保つために、ソルト、またはむしろScryptやArgon2などの優れたパスワードストレージアルゴリズムが重要である理由の一部です。レインボーテーブルは、ソルトとパスワードの両方を含むのに十分な大きさのエントリがテーブルに含まれている場合にのみ、ソルトされたパスワードを回復できます。これは非常に非効率的であり、目的全体を無効にします。

同様のことが暗号化にも当てはまることに注意してください。パスワードを使用してファイルを暗号化すると、レインボーテーブルを作成してファイルを解読できます。ソフトウェアがAESを使用し、ファイルの最初のブロックがユーザーが指定したパスワードを使用して「passwordcorrect」に復号化する必要がある場合、レインボーテーブルはハッシュ関数の代わりにAESを使用するとします。

パスワード（強度が不明なシークレット、特にユーザーがパスワードを再利用する可能性がある場合）を処理するときは常に、適切な（低速の）パスワードストレージアルゴリズムを実行して、パスワードを低速でクラックに固有のものにします。

コメント

• 適切な説明。それを正しく理解していれば、レインボーテーブルの力は優れたリダクション機能を持っていることにありますよね？どうすれば良いものを思いつくことができますか？そして、チェーン全体のすべての候補者の衝突を回避するにはどうすればよいですか？
• @ Kyu96良い質問です！ ‘答えはわかりませんが、見つけたら興味があります。このページは、レインボーテーブルとは何かという一般的な質問であり、アルゴリズムの設計方法などの詳細ではありません。 新しい質問を開く必要がありますが、このウェブサイトは”デジタル脅威から資産を保護することに関するものです”（iirc ）。 “に関する姉妹サイト crypto.stackexchange.com では話題になると思います。暗号システムの数学と特性、それらの分析（” cryptoanalysis “）、および乱数など、一般的に暗号を構成する補助的なトピック世代。”