John the Ripper とレインボーテーブルを理解する

はじめに

サイバーセキュリティの世界では、パスワードがどのように保護されているか、そして逆にどのように侵害される可能性があるかを理解することが極めて重要です。この実験では、強力なパスワードクラッキングツールである John the Ripper と、暗号ハッシュ関数を逆算するために使用される事前計算済みテーブルであるレインボーテーブルという、2 つの基本的な概念を紹介します。John the Ripper は様々な攻撃手法を使用できますが、この実験では概念的にレインボーテーブルとの連携に焦点を当てます。

レインボーテーブルの基本的な原理を探求し、ブルートフォース攻撃との効率性を比較し、最も効果的なシナリオを特定し、その固有の限界を理解します。最後に、レインボーテーブルがどのように生成されるかについて概念的に議論します。この実験は、実際のレインボーテーブル操作の複雑さとリソース集約性のため、実践的な応用ではなく、これらのツールと技術の理論的な理解を提供することを目的としています。

レインボーテーブルの原則を理解する

このステップでは、レインボーテーブルのコア原則を掘り下げます。レインボーテーブルは、暗号ハッシュ関数を逆算するために使用される事前計算済みテーブルであり、通常はパスワードハッシュをクラッキングするために使用されます。あらゆる可能なパスワード（ブルートフォース）や辞書内のあらゆる単語を試す代わりに、レインボーテーブルはハッシュ値とそれに対応するプレーンテキスト値の事前計算済みチェーンを格納します。

基本的な考え方は、計算時間をストレージスペースと交換することです。システムがパスワードを格納する場合、通常はプレーンテキストパスワード自体ではなく、そのハッシュ値を格納します。たとえば、パスワードが password123 の場合、システムはその MD5 ハッシュである 4d7d7e7e7e7e7e7e7e7e7e7e7e7e7e7e を格納する可能性があります。ログインを試みると、入力されたパスワードがハッシュ化され、そのハッシュが格納されているハッシュと比較されます。

レインボーテーブルは、ハッシュとプレーンテキスト値の長い「チェーン」を作成することによって機能します。プレーンテキストから始まり、それをハッシュ化し、次にハッシュに「還元関数」を適用して別のプレーンテキストを取得し、それをハッシュ化し、というように繰り返します。これらのチェーンの開始点と終了点のみがテーブルに格納されます。

簡単な例を考えてみましょう。

プレーンテキスト P1 から開始します。
P1 をハッシュ化して H1 を取得します。
H1 に還元関数 R を適用して P2 を取得します。
P2 をハッシュ化して H2 を取得します。
H2 に R を適用して P3 を取得します。 ...そして、定義済みのチェーン長まで続けます。

クラッキングしたいターゲットハッシュ HT がある場合、還元関数 R を HT に適用して潜在的なプレーンテキスト P_temp を取得します。次に P_temp をハッシュ化し、再度 R を適用し、このプロセスを繰り返して、レインボーテーブルに格納されているいずれかの終了点と一致するハッシュを生成します。一致が見つかった場合、テーブルから対応する開始点を取得し、その開始点からチェーンを再生成して、ターゲットハッシュ HT を生成したプレーンテキストを見つけます。

この方法は、クラッキング時の計算量を大幅に削減します。なぜなら、ほとんどの重労働（ハッシュ化と還元）は、テーブル生成フェーズ中に事前に完了しているからです。

理解を確認するために、レインボーテーブルの使用に伴うトレードオフを考えてみてください。

レインボーテーブルとブルートフォースの比較

このステップでは、レインボーテーブルと従来のブルートフォース攻撃手法を比較します。それぞれの違いを理解することで、各手法の長所と短所が明らかになります。

ブルートフォース攻撃： ブルートフォース攻撃は、正しいパスワードが見つかるまで、文字（英字、数字、記号）のあらゆる可能な組み合わせを試行します。たとえば、4 文字の小文字英字パスワードをクラックする場合、aaaa、aaab、aaac、...、zzzz を試行します。

長所： 十分な時間とリソースがあれば、パスワードを見つけることが保証されます。事前計算は不要です。
短所： 特に長く複雑なパスワードの場合、非常に時間がかかり、計算負荷が高くなります。各推測には新しいハッシュ計算が必要です。

レインボーテーブル攻撃： 前のステップで説明したように、レインボーテーブル攻撃は事前計算されたハッシュチェーンを使用してハッシュを逆算します。

長所： テーブルが生成されれば、大量のハッシュをクラックする上でブルートフォースよりもはるかに高速です。一般的なパスワードに対する繰り返しハッシュ計算を回避します。
短所： 事前計算されたテーブルのために、かなりのストレージスペースが必要です。テーブルはハッシュアルゴリズム（例：MD5、SHA1）に固有であり、多くの場合、特定の文字セットとパスワード長範囲に固有です。これらは、「ソルト」付きハッシュ（ハッシュ化前にパスワードにランダムな文字列が追加される）に対しては効果が低くなります。なぜなら、各ソルトには新しく一意のレインボーテーブルが必要になるからです。

図書館の巨大な本の中から特定の本を見つける必要があると想像して、違いを説明しましょう。

ブルートフォース： 最初から本棚に向かい、各本を手に取り、タイトルを読み、探している本かどうかを確認します。それが見つかるまで、すべての一冊に対してこれを行います。これは網羅的ですが遅いです。
レインボーテーブル： 誰かがすでに図書館を巡り、特定の書籍のタイトルとその棚の場所をマッピングするインデックス（レインボーテーブル）を作成しました。本が必要なとき、インデックスを参照すると、すぐに適切な場所が示され、すべての一冊を確認する手間が省けます。ただし、そのインデックスを作成するには、最初に多くの労力とスペースが必要でした。

パスワードハッシュにおける「ソルト」の存在が、レインボーテーブル攻撃の効果にどのように影響するかを考えてみてください。

レインボーテーブルの使用シナリオを特定する

このステップでは、レインボーテーブルが最も効果的で一般的に使用される特定のシナリオを特定します。最新のハッシュ処理方法によりその有効性は低下していますが、その歴史的および概念的なユースケースを理解することは重要です。

レインボーテーブルは、特に以下の状況で役立ちます。

大規模なパスワードクラッキング（ソルトなしハッシュ）: その主な利点は、多数のソルトなしパスワードハッシュをクラックできることです。攻撃者がソルトなしの MD5 または SHA1 ハッシュのデータベースを入手した場合、事前計算されたレインボーテーブルは、それらの多くに対してプレーンテキストパスワードを迅速に見つけることができます。これは、同じハッシュ値が常に同じプレーンテキストに対応するため、テーブルを複数のターゲットに再利用できるからです。
オフライン攻撃： レインボーテーブルはオフライン攻撃で使用されます。これは、攻撃者がすでにハッシュ値を入手しており（侵害されたデータベースやネットワークスニッフィングなどから）、ターゲットシステムとやり取りすることなくそれらをクラックしようとしていることを意味します。これは、攻撃者がログインフォームに対して直接パスワードを試行するオンライン攻撃とは対照的です。オンライン攻撃は通常、レート制限されています。
既知のハッシュアルゴリズム： レインボーテーブルは、特定のハッシュアルゴリズム（例：MD5、SHA-1、NTLM）用に生成する必要があります。ターゲットシステムが未知またはカスタムのハッシュアルゴリズムを使用している場合、事前計算されたレインボーテーブルは役に立ちません。
クラッキングのための計算リソースは限られている（ただし生成には十分）: レインボーテーブルの生成は計算負荷が高いですが、ハッシュをクラックするために使用するのは比較的迅速です。これにより、初期のテーブル生成のために強力なリソースにアクセスできるが、それほど強力でないマシンや時間制約のある環境で迅速なクラッキングを実行する必要がある攻撃者に適しています。
一般的な/弱いパスワードのクラッキング： レインボーテーブルは、事前計算されたチェーンに含まれる可能性が高い、一般的、短い、または単純なパスワードに対して最も効果的です。複雑で長い、または真にランダムなパスワードは、一般的なレインボーテーブルで見つかる可能性が低いか、非現実的に大きなテーブルが必要になります。

現代のパスワードストレージの実践、例えば強力で遅いハッシュアルゴリズム（bcrypt、scrypt、Argon2 など）の使用、そして最も重要なこととして、各パスワードにユニークなランダム値をソルトとして追加することは、レインボーテーブルの有効性を大幅に軽減していることに注意することが重要です。ソルトは、たとえ 2 人のユーザーが同じパスワードを持っていても、保存されているハッシュは異なることを保証し、汎用的なレインボーテーブルを無用なものにします。

攻撃者がソルトなしの MD5 パスワードハッシュのリストを入手したシナリオを考えてみてください。レインボーテーブルは彼らにとって効率的なツールでしょうか？

レインボーテーブルの限界を理解する

このステップでは、レインボーテーブルの重大な限界を探ります。これらの限界が、現代のサイバーセキュリティの実践においてその有効性が低下した理由です。

ソルト（Salting）: これが最も重要な限界です。「ソルト」とは、ハッシュ化される前にパスワードに追加されるランダムなデータ文字列です。たとえば、パスワードが password123 でソルトが xyz の場合、システムは password123xyz をハッシュ化します。通常、各ユーザーには一意のソルトが与えられるため、2 人のユーザーが同じパスワードを持っていても、保存されているハッシュは異なります。これは、MD5(password) 用に生成されたレインボーテーブルが、MD5(password + salt) には機能しないことを意味します。ソルト付きハッシュをレインボーテーブルでクラックするには、攻撃者はすべてのユニークなソルトごとに個別のレインボーテーブルを生成する必要がありますが、これは多数のユーザーに対して事実上不可能です。
生成の計算コスト： レインボーテーブルの使用は高速ですが、生成は非常に計算負荷が高く、時間がかかります。幅広い文字と長さに対応する包括的なテーブルの場合、強力なハードウェアで数週間、数ヶ月、あるいは数年かかることもあります。
ストレージ要件： レインボーテーブルは膨大なストレージ容量を必要とします。特定のハッシュアルゴリズムの一般的なパスワードをクラックするために設計されたテーブルは、簡単にテラバイト単位のディスク容量を消費する可能性があります。これは、多くの攻撃者にとって非現実的です。
ハッシュアルゴリズムへの特異性： レインボーテーブルは、特定のハッシュアルゴリズム（例：MD5、SHA-1、NTLM）用に生成されます。異なるアルゴリズムによって生成されたハッシュをクラックするために使用することはできません。システムが MD5 から SHA-256 に切り替わった場合、古い MD5 レインボーテーブルは役に立たなくなります。
強力なハッシュに対する有効性： bcrypt、scrypt、Argon2 のような現代の「遅い」ハッシュアルゴリズムは、計算負荷が高くなるように設計されており、ブルートフォースおよびレインボーテーブル攻撃をはるかに遅くします。これらのアルゴリズムは意図的に計算遅延を追加し、毎秒数百万回のハッシュ計算を実行することを困難にします。
限定的な網羅性： レインボーテーブルは、有限個の事前計算されたチェーンしか含めることができません。その事前計算されたセットの一部ではないパスワード（例：非常に長く、複雑な、または真にランダムなパスワード）をクラックすることはできません。

これらの限界、特にソルトと強力なハッシュアルゴリズムの広範な採用により、レインボーテーブルは現代のパスワードストレージシステムに対してはるかに効果が低くなっています。しかし、それらは歴史的な攻撃手法と適切なパスワードセキュリティ実践の重要性を理解するための関連概念として残っています。

ソルトがレインボーテーブルに対する最も効果的な対策と見なされる理由を考えてみてください。

レインボーテーブル生成について議論する（概念）

最終ステップでは、レインボーテーブル生成のプロセスについて概念的に議論します。その複雑さとリソース要件のため、実際の生成は行いませんが、基盤となるプロセスを理解することが重要です。

レインボーテーブルの生成は、ハッシュチェーンを作成するための一連の反復ステップを含みます。

パラメータの定義：
- ハッシュ関数： テーブルが生成される特定の暗号ハッシュ関数（例：MD5、SHA-1、NTLM）を選択します。
- 文字セット： 可能なパスワードに含まれる文字のセットを定義します（例：小文字、大文字、数字、記号）。
- パスワード長範囲： カバーするパスワードの最小長と最大長を指定します。
- チェーン長 (k): 各チェーンに含まれるハッシュ - 還元ステップの数を決定します。チェーンが長いほど、保存する開始/終了ポイントは少なくなりますが、クラッキング時の計算量は増えます。
- チェーン数 (m): 生成するユニークなチェーンの数を決定します。チェーンが多いほど網羅性は高まりますが、テーブルサイズも大きくなります。
初期プレーンテキストの選択：
- 定義された文字セットと長さの範囲から、開始プレーンテキスト P_start をランダムに選択します。この P_start がチェーンの「開始点」となります。
チェーン生成ループ：
- 各 P_start に対して、k 回の反復（k はチェーン長）を実行します。
- ハッシュ： 現在のプレーンテキスト P_i をハッシュ化してハッシュ H_i を取得します。
- 還元： 還元関数 R_j を H_i に適用して、それを定義された文字セットと長さ内の有効なプレーンテキスト P_{i+1} に変換します。還元関数は非常に重要であり、ハッシュ値を有効なプレーンテキストにマッピングするように設計されている必要があります。重要なのは、異なるチェーンが 1 つにマージされる「衝突」（collisions）を防ぐために、チェーン内の各ステップ j で異なる還元関数 R_j が使用されることが多いということです。
終了点の保存：
- k 回の反復後、最終的なハッシュ H_k と最終的なプレーンテキスト P_end が得られます。ペア (P_start, P_end) をレインボーテーブルに保存します。チェーン内の途中値ではなく、これらの 2 つのポイントのみが保存されます。
繰り返し：
- ステップ 2〜4 を m 回（m はチェーン数）繰り返して、目的の数のユニークなチェーンを生成します。

レインボーテーブル生成における主な課題は、効果的な還元関数を設計し、膨大なデータを管理することにあります。ophcrack や hashcat（ただし hashcat はブルートフォース/辞書攻撃に重点を置いていますが、事前計算されたテーブルを使用できます）のようなツールは、レインボーテーブルの生成と利用に使用できるソフトウェアの例です。John the Ripper は、主にパスワードクラッカーですが、事前計算されたテーブルと組み合わせて使用したり、辞書攻撃やブルートフォース攻撃を実行したりするためにも使用できます。

レインボーテーブル生成のこの概念的な理解は、これらの強力でありながら限定的なクラッキングツールを作成するために必要な、計算とストレージにおける多大な初期投資を浮き彫りにします。

まとめ

この概念的な実験（Lab）では、John the Ripper とレインボーテーブルの基本的な理解を得ました。レインボーテーブルは、ストレージ容量をクラッキング速度と引き換えに、暗号ハッシュ関数を逆変換するために使用される事前計算されたテーブルであることを学びました。レインボーテーブルとブルートフォース攻撃を比較し、大量のソルトなしハッシュに対するレインボーテーブルの効率性を強調しましたが、そのストレージと生成コストの大きさも指摘しました。

レインボーテーブルが歴史的に効果的であったシナリオ、主に侵害されたデータベースからのソルトなしハッシュのオフラインクラッキングについて特定しました。最も重要なのは、レインボーテーブルの主な限界を探求したことです。特にソルトは、現代のパスワードストレージの実践に対してそれらをほとんど無効にする最も重要な対策です。最後に、パラメータの定義、ハッシュチェーンの生成、開始点と終了点のみの保存を含む、レインボーテーブル生成の複雑なプロセスを概念的に議論しました。

この実験（Lab）は、パスワードセキュリティの進化と、攻撃者と防御者の間の継続的な軍拡競争を強調し、サイバーセキュリティにおけるこれらの重要な概念を理解するための理論的基盤を提供します。

John the Ripper とレインボーテーブル（概念）