security - なぜレインボーテーブルと呼ばれるのですか？

Question

レインボーテーブルと呼ばれる理由を知っている人はいますか? 「辞書攻撃」と呼ばれる攻撃があることを知ったのを思い出しました。なぜコール辞書ではないのですか？

Answer 1

可能性の「スペクトル」全体が含まれているからです。

辞書攻撃は、可能性を試すだけのブルートフォース手法です。このように（python疑似コード）

mypassworddict = dict()

for password in mypassworddict:
    trypassword(password)

ただし、レインボー テーブルはハッシュを反転するためのものであるため、動作が異なります。ハッシュの高レベルの概要は、多数のビンがあることです。

bin1, bin2, bin3, bin4, bin5, ...

これは、出力文字列のバイナリ部分に対応します。これが、文字列がその長さになる方法です。ハッシュが進むにつれて、さまざまな方法でビンのさまざまな部分に影響を与えます。したがって、最初のバイト (または入力フィールドが受け入れられるもの) の入力は、(簡単に言うと) ビン 3 と 4 に影響を与えます。次の入力は、ビン 2 と 6 に影響を与えます。

レインボー テーブルは、指定されたビンのすべての可能性の計算です。つまり、すべてのビンについて、そのビンのすべての可能な逆数です...そのため、非常に大きくなります。最初のビンの値が の場合は、bin3 のすべての値と bin3 のすべて0x1の値のルックアップ リストが必要です。これにより、最終的に値が得られます。bin2

辞書攻撃と呼ばれないのはなぜですか? そうではないからです。

以前の質問を見たので、お探しの詳細を詳しく説明させてください。暗号的に安全なハッシュは、小さな入力サイズからファイル全体まで、理想的には安全である必要があります。ファイル全体のハッシュ値を事前に計算するには、とてつもなく時間がかかります。したがって、レインボー テーブルは、出力のよく理解された小さなサブセットで設計されます。たとえば、10 文字のフィールド全体のすべての文字の順列です。

これが、辞書攻撃を打ち負かすためのパスワードのアドバイスがここで機能する理由です。ハッシュの入力に入れる可能な入力セット全体のサブセットが多いほど、それを検索するためにレインボー テーブルに含める必要があるものが多くなります。必要なデータ サイズは途方もなく大きくなり、検索時間も長くなります。それで、それについて考えてください：

• [a-z]文字用の入力がある場合5-8、それはそれほど悪くないレインボー テーブルです。
• 長さを 42 文字に増やすと、巨大なレインボー テーブルになります。各入力はハッシュに影響を与えるため、そのハッシュのビンに影響を与えます。
• 検索条件に数字を入れると、[a-z][0-9]さらに多くの検索を行う必要があります。
• 同様に[A-Za-z0-9]。最後に、[\w]考えられる印刷可能な任意の文字を貼り付けます。ここでも、巨大なテーブルが表示されます。

したがって、パスワードを長く複雑にすると、レインボー テーブルはブルーレイ サイズのディスクのデータを取得し始めます。次に、前の質問に従って、ソルティングとハッシュ派生関数の追加を開始し、ハッシュクラッキングの一般的な解決策を作成します (er)。

ここでの目標は、利用可能な計算能力の先を行くことです。

Answer 2

レインボーは辞書攻撃 (正確には事前計算された辞書攻撃) の変形ですが、完全な辞書よりも少ないスペースしか必要としません (テーブル内のキーを見つけるのに必要な時間を犠牲にして)。このスペースとメモリのトレードオフのもう一方の端は、完全な検索です (ブルート フォース攻撃 = 事前計算ゼロ、多くの時間)。

レインボー テーブルでは、事前に計算されたキーと暗号文のペアの辞書がチェーンで圧縮されています。チェーンのすべてのステップは、異なる圧縮機能を使用して実行されます。そして、テーブルにはチェーンがたくさん付いているので、虹のように見えます。

この図では、さまざまな圧縮関数 K1、K2、K3 が虹のような色をしています。ファイルに保存されているテーブルには、最初と最後の列のみが含まれています。これは、中央の列を再計算できるためです。

Answer 3

名前の由来はわかりませんが、違いは次のとおりです。

• 辞書にはいくつかの選択された項目 (英単語など) が含まれていますが、レインボー テーブルには可能なすべての組み合わせが含まれています。
• ディクショナリには入力のみが含まれますが、レインボー テーブルには入力と出力の両方が含まれます。
• ディクショナリは、さまざまな入力をテストして出力が有効かどうかを確認するために使用されます。一方、レインボー テーブルは逆引き、つまり特定の出力を与える入力を見つけるために使用されます。

Answer 4

残念ながら、一部の記述は正しくありません。投稿されたものとは反対に、レインボーテーブルには、私が見た使用のために生成されたものではなく、特定のキースペースのすべての可能性が含まれているわけではありません。それらは 99.9 をカバーするように生成できますが、ハッシュ関数のランダム性のため、すべての平文がカバーされるという保証はありません。

各チェーンはリンクまたはステップで構成され、各ステップはハッシュ関数とリダクション関数で構成されます。チェーンが 100 リンクの長さである場合、その数のハッシュ/リダクション関数を実行し、最初と最後を除いてその間のすべてを破棄します。

特定のハッシュのプレーンを見つけるには、チェーンの長さの削減 / ハッシュ x を実行するだけです。そのため、ステップを 1 回実行し、エンドポイントを確認して失敗したかどうかを繰り返します... チェーンの全長をステップ実行するまで。一致する場合は、開始点からチェーンを再生成することができ、プレーンを見つけることができる場合があります. 再生成後に正しくない場合、これは誤報です。これは、リダクション ハッシュ関数によって引き起こされる衝突が原因で発生します。テーブルには多くのチェーンが含まれているため、各ステップですべてのチェーン エンドポイントに対して大規模なルックアップを行うことができます。これは基本的に、スピードを可能にする魔法が発生する場所です。一致するチェーンを再生成するだけでよく、不要なチェーンをスキップすることで多くの時間を節約できるため、これは誤報にもつながります。

それらには辞書が含まれていません....伝統的なテーブルではありませんが、辞書の使用を組み込んだレインボーテーブルのバリエーションがあります。

それはそれについてです。マージ/重複チェーンの削除、完全なテーブルの作成、スペースと読み込み時間を節約するための異なるパッキングでの保存など、このプロセスが最適化された多くの方法があります。