レインボーテーブル

レインボー テーブルは、暗号化ハッシュ関数の出力をキャッシュするための事前計算された テーブルで、通常はパスワード ハッシュを解読するために使用されます。パスワードは通常、プレーン テキスト形式ではなくハッシュ値として保存されます。ハッシュされたパスワードのデータベースが攻撃者の手に渡った場合、事前計算されたレインボー テーブルを使用してプレーン テキストのパスワードを復元できます。この攻撃に対する一般的な防御策は、ハッシュする前に各パスワードに「ソルト」を追加するキー導出関数を使用してハッシュを計算することです。異なるパスワードには異なるソルトが与えられ、ハッシュとともにプレーン テキストで保存されます。

レインボー テーブルは、空間と時間のトレードオフの実際的な例です。試行ごとにハッシュを計算するブルート フォース攻撃よりもコンピューターの処理時間が短く、ストレージ容量は多くなりますが、考えられるすべてのパスワードのハッシュを保存する単純なテーブルよりも処理時間が長く、ストレージ容量は少なくなります。

レインボーテーブルは、マーティン・ヘルマン^[2]によるより初期のより単純なアルゴリズムの応用としてフィリップ・エクスリン^[1]によって発明されました。

ユーザー認証では、パスワードはプレーンテキストまたはハッシュとして保存されます。プレーンテキストとして保存されたパスワードは、データベースへのアクセスが侵害された場合に簡単に盗まれるため、データベースは通常、代わりにハッシュを保存します。したがって、認証システムを含め、誰もデータベースに保存された値を見るだけではパスワードを知ることはできません。

ユーザーが認証のためにパスワードを入力すると、そのパスワードのハッシュが計算され、そのユーザー用に保存されているハッシュと比較されます。2 つのハッシュが一致しない場合は認証が失敗します。さらに、ハッシュ値がパスワードとして入力された場合も、認証システムがそれを 2 度ハッシュするため、認証は同様に失敗します。

ハッシュからパスワードを知るということは、ハッシュ関数に入力したときに同じハッシュを作成する文字列を見つけることです。これはハッシュ関数を 反転することと同じです。

ブルートフォース攻撃（辞書攻撃など）はハッシュ関数を逆転させるために使用できますが、可能性のあるパスワードのセットが十分に大きい場合は実行不可能になる可能性があります。ブルートフォースの代替手段は、事前に計算されたハッシュ チェーン テーブルを使用することです。レインボー テーブルは、特定の技術的な困難を克服する特別な種類のテーブルです。

レインボー テーブルという用語は、Oechslin の最初の論文で初めて使用されました。この用語は、攻撃の成功率を高めるためにさまざまな削減関数を使用する方法を指します。Hellman による元の方法では、それぞれ異なる削減関数を持つ多数の小さなテーブルを使用します。レインボー テーブルははるかに大きく、各列で異なる削減関数を使用します。削減関数を表すために色を使用すると、レインボー テーブルにレインボーが表示されます。Oechslin の論文の図 2 には、これらのセクションの関係を示す白黒のグラフィックが含まれています。Crypto 2003 カンファレンスでのプレゼンテーションでは、Oechslin はレインボーの関連性をより明確にするためにグラフィックに色を追加しました。カンファレンスで発表された強化されたグラフィックは、図に示されています。

パスワード ハッシュ関数 H と有限のパスワード セット P が与えられた場合、ハッシュ関数の任意の出力h が与えられたときに、 H( p ) = hとなる要素p をP 内で見つけるか、またはそのようなp がP 内に存在しないことを判断できるデータ構造を事前計算することが目標です。これを行う最も簡単な方法は、 P 内のすべてのpに対して H( p )を計算することですが、その場合、テーブルを格納するためにΘ (|P| n ) ビットのスペースが必要になります。ここで、|P| はセット P のサイズ、n はH の出力のサイズであり、大きな |P| ではこれは許容できません。ハッシュ チェーンは、このスペース要件を削減する手法です。アイデアは、ハッシュ値を P 内の値にマップし直すリダクション関数R を定義することです。ただし、リダクション関数は実際にはハッシュ関数の逆関数ではなく、ハッシュ関数のドメインとコドメインを入れ替えた別の関数であることに注意してください。ハッシュ関数とリダクション関数を交互に使用することで、交互に使用されるパスワードとハッシュ値のチェーンが形成されます。たとえば、P が小文字のアルファベット 6 文字のパスワードのセットであり、ハッシュ値の長さが 32 ビットの場合、チェーンは次のようになります。

${\displaystyle {\color {赤}{\mathtt {aaaaaa}}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {281DAF40}}\,{\xrightarrow[{\;R\;}]{}}\,{\mathtt {sgfnyd}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {920ECF10}}\,{\xrightarrow[{\;R\;}]{}}\,{\color {紫}{\mathtt {kiebgt}}}}$

削減関数の唯一の要件は、特定のサイズの「プレーンテキスト」値を返すことができることです。

テーブルを生成するには、P からランダムな初期パスワードセットを選択し、それぞれに対して固定長kのチェーンを計算し、各チェーンの最初と最後のパスワードのみを保存します。最初のパスワードは開始点と呼ばれ、最後のパスワードはエンドポイントと呼ばれます。上記のチェーンの例では、「aaaaaa」が開始点、「kiebgt」がエンドポイントとなり、他のパスワード (またはハッシュ値) は保存されません。

ここで、反転するハッシュ値h（対応するパスワードを見つける）が与えられ、R、H、R などを適用してhから始まるチェーンを計算します。いずれかの時点で値がテーブル内のエンドポイントの 1 つと一致する場合、対応する開始点によって完全なチェーンを再作成できます。このチェーンには値h​​ が含まれる可能性が高く、その場合、チェーンの直前の値が、探しているパスワードpです。

たとえば、ハッシュ920ECF10が与えられた場合、そのチェーンは最初に R を適用することで計算できます。

${\displaystyle {\mathtt {920ECF10}}\,{\xrightarrow[{\;R\;}]{}}\,{\color {Violet}{\mathtt {kiebgt}}}}$

「 kiebgt」はテーブル内のエンドポイントの 1 つであるため、対応する開始パスワード「 aaaaaa 」は、 920ECF10に到達するまでそのチェーンをたどることができます。

${\displaystyle {\color {Red}{\mathtt {aaaaaa}}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {281DAF40}}\,{\xrightarrow[{\;R\;}]{}}\,{\mathtt {sgfnyd}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {920ECF10}}}$

したがって、パスワードは「sgfnyd」（または同じハッシュ値を持つ別のパスワード）になります。

ただし、このチェーンにはハッシュ値hが常に含まれているわけではないことに注意してください。 hで始まるチェーンが、異なる開始点を持つチェーンと合流することもあります。たとえば、ハッシュ値FB107E70のチェーンもkiebgtにつながります。

${\displaystyle {\mathtt {FB107E70}}\,{\xrightarrow[{\;R\;}]{}}\,{\mathtt {bvtdll}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {0EE80890}}\,{\xrightarrow[{\;R\;}]{}}\,{\color {Violet}{\mathtt {kiebgt}}}}$

対応する開始パスワード「 aaaaaa 」によって生成されたチェーンは、FB107E70に到達するまで追跡されます。この値はチェーンに含まれていないため、検索はFB107E70に到達せずに終了します。これは誤報と呼ばれます。この場合、一致は無視され、hのチェーンが拡張されて別の一致が検索されます。hのチェーンが長さkまで拡張されても適切な一致がない場合、パスワードはどのチェーンでも生成されなかったことになります。

テーブルの内容は、反転するハッシュ値に依存しません。一度作成され、変更されずに検索に繰り返し使用されます。チェーンの長さが長くなると、テーブルのサイズは小さくなります。ただし、検索の実行に必要な時間も長くなります。これがレインボー テーブルの時間とメモリのトレードオフです。1 つの項目のチェーンの単純なケースでは、検索は非常に高速ですが、テーブルは非常に大きくなります。チェーンが長くなると、検索は遅くなりますが、テーブルのサイズは小さくなります。

単純なハッシュ チェーンには、いくつかの欠陥があります。最も深刻なのは、いずれかの時点で 2 つのチェーンが衝突(同じ値を生成する) した場合、それらのチェーンが結合され、その結果、生成に同じ計算コストを支払ったにもかかわらず、テーブルがカバーするパスワードの数が少なくなることです。以前のチェーンは完全には保存されないため、これを効率的に検出することは不可能です。たとえば、チェーン 3 の 3 番目の値がチェーン 7 の 2 番目の値と一致する場合、2 つのチェーンはほぼ同じ値のシーケンスをカバーしますが、最終的な値は同じではありません。ハッシュ関数 H は、衝突を生成しないことが重要なセキュリティ機能であると通常考えられているため、衝突を生成する可能性は低いですが、リダクション関数 R は、可能性のある平文を正しくカバーする必要があるため、衝突耐性を持つことはできません。

その他の困難は、R に適切な関数を選択することの重要性から生じます。R をアイデンティティとして選択することは、ブルート フォース アプローチとほとんど変わりません。攻撃者が可能性のある平文について十分な知識を持っている場合にのみ、時間と空間が可能性のある平文にのみ使用され、可能性のあるパスワードの空間全体に使用されることはないことを保証する関数 R を選択できます。実質的に、R は以前のハッシュ計算の結果を可能性のある平文に戻しますが、この利点には、攻撃者がチェックしたいクラスのすべての可能性のある平文を R が生成しない可能性が高いという欠点があり、攻撃者は選択したクラスからパスワードが来ていないことを確信できません。また、関数 R を予想される平文の分布と一致するように設計することは困難です。^[2]

レインボー テーブルは、単一のリダクション関数 R を一連の関連するリダクション関数 R ₁から R _kに置き換えることで、通常のハッシュ チェーンの衝突の問題を効果的に解決します。この方法では、2 つのチェーンが衝突してマージするには、同じ反復で同じ値に到達する必要があります。その結果、これらのチェーンの最終値は同一になります。最終的な後処理パスでは、テーブル内のチェーンをソートし、他のチェーンと同じ最終値を持つ「重複」チェーンを削除できます。その後、新しいチェーンが生成され、テーブルを埋めます。これらのチェーンは衝突がないわけではありません(一時的に重なる場合があります) が、マージされることはなく、衝突の総数が大幅に減少します。^{[引用が必要]}

削減関数のシーケンスを使用すると、検索の方法が変わります。対象のハッシュ値はチェーン内の任意の場所にある可能性があるため、k個の異なるチェーンを生成する必要があります。最初のチェーンは、ハッシュ値が最後のハッシュ位置にあると想定し、 R _{k を}適用します。次のチェーンは、ハッシュ値が最後から 2 番目のハッシュ位置にあると想定し、 R _{k −1}、次に H、次に R _kを適用します。最後のチェーンまでこれを繰り返し、最後のチェーンでは、H と交互にすべての削減関数を適用します。これにより、誤報を生成する新しい方法が生まれます。ハッシュ値の位置の誤った「推測」によって、チェーンが不必要に評価される可能性があります。

レインボー テーブルはより多くのチェーンに従う必要がありますが、テーブルの数を少なくすることでこれを補っています。単純なハッシュ チェーン テーブルは、チェーンのマージにより急速に非効率になることなく、特定のサイズを超えて拡大することはできません。これに対処するために、複数のテーブルを維持し、各ルックアップで各テーブルを検索する必要があります。レインボー テーブルは、k倍大きいテーブルで同様のパフォーマンスを実現できるため、ルックアップをk倍少なく実行できます。

1. 下の画像のハッシュ (「re3xes」) から始めて、テーブルで使用された最後の削減を計算し、パスワードがテーブルの最後の列に現れるかどうかを確認します (手順 1)。
2. テストが失敗した場合（ramboが表に表示されない）、最後の2つの削減を含むチェーンを計算します（これらの2つの削減はステップ2で表されます）

   注: この新しいテストが再度失敗した場合は、パスワードが見つかるまで 3 回の削減、4 回の削減などを継続します。チェーンにパスワードが含まれていない場合、攻撃は失敗します。

3. このテストが肯定的である場合 (ステップ 3、linux23 がチェーンの最後とテーブルに表示される)、linux23 を生成するチェーンの先頭でパスワードが取得されます。ここで、テーブルに格納されている対応するチェーンの先頭でpasswd が見つかります。
4. この時点で (ステップ 4)、チェーンを生成し、各反復でハッシュをターゲット ハッシュと比較します。チェーン内でハッシュre3xesが見つかり、チェーン内の 1 ステップ前にそれを生成したパスワード ( culture ) が見つかった場合、攻撃は成功です。

レインボー テーブルは、チェーン内の各「リンク」ごとに異なるリダクション関数を使用する洗練されたアルゴリズムを使用しているため、2 つ以上のチェーンでハッシュ衝突が発生した場合、各チェーンの同じ位置で衝突が発生しない限り、チェーンは結合されません。これにより、特定のテーブル サイズで正しいクラックが行われる可能性が高まりますが、ルックアップ ルーチンではチェーンで使用される最初のリダクション関数のインデックスも反復処理する必要があるため、ルックアップごとに必要なステップ数が 2 乗されるというコストがかかります。^[1]

レインボーテーブルは、作成されたハッシュ関数に固有のものです。たとえば、MD5テーブルはMD5ハッシュのみを解読できます。この技術の理論は、時間とメモリのトレードオフを高速化する方法としてPhilippe Oechslin ^[3]によって発明され、^{[1]彼はこれを}WindowsパスワードクラッカーOphcrackに実装しました。その後、より強力なRainbowCrackプログラムが開発され、 LMハッシュ、MD5、SHA-1など、さまざまな文字セットとハッシュアルゴリズムのレインボーテーブルを生成して使用できるようになりました。

リダクション関数とハッシュ関数が衝突しない単純なケースでは、完全なレインボーテーブル（任意のハッシュに対応するパスワードが確実に見つかるテーブル）が与えられている場合、パスワードセットのサイズ | P |、テーブルの計算に要した時間T 、テーブルの長さL、および与えられたハッシュに一致するパスワードを見つけるのに要した平均時間tは直接関係しています。^[要出典]

${\displaystyle T=|P|}$

${\displaystyle t={\frac {|P|}{2L}}}$

したがって、8 文字の小文字の英数字パスワードの場合 (| P | ≃ 3×10 ¹² ) はパーソナル コンピュータで簡単に処理できますが、16 文字の小文字の英数字パスワードの場合 (| P | ≃ 10 ²⁵ ) はまったく処理不可能になります。

レインボー テーブルは、大きなソルトを含む一方向ハッシュに対しては効果がありません。たとえば、次の関数を使用して生成されるパスワード ハッシュを考えてみましょう (ここで、「+ 」は連結演算子です)。

saltedhash(password) = hash(password + salt)

または

saltedhash(password) = hash(hash(password) + salt)

ソルト値は秘密ではなく、ランダムに生成され、パスワード ハッシュとともに保存される場合があります。ソルト値を大きくすると、各ユーザーのパスワードが一意にハッシュされることが保証されるため、レインボー テーブルなどの事前計算攻撃を防ぐことができます。つまり、同じパスワードを持つ 2 人のユーザーは、異なるパスワード ハッシュを持つことになります (異なるソルトが使用されていると仮定)。攻撃者が成功するには、考えられるソルト値ごとにテーブルを事前計算する必要があります。ソルトは十分に大きくなければなりません。そうでないと、攻撃者はソルト値ごとにテーブルを作成できます。12ビットのソルトを使用する古いUnix パスワードの場合、4096 個のテーブルが必要になり、攻撃者にとってはコストが大幅に増加しますが、テラバイトのハード ドライブでは非現実的ではありません。Linux 、BSD Unix、Solarisで使用されるSHA2 暗号化およびbcrypt方式のソルトは 128 ビットです。^{[4]これらの大きなソルト値により}、これらのシステムに対する事前計算攻撃は、パスワードの長さに関係なくほぼ不可能になります。たとえ攻撃者が 1 秒あたり 100 万個のテーブルを生成できたとしても、すべての可能なソルトのテーブルを生成するには、まだ数十億年かかります。

事前計算攻撃を防ぐのに役立つもう 1 つの手法は、キー ストレッチングです。ストレッチングを使用すると、ソルト、パスワード、およびいくつかの中間ハッシュ値が、基礎となるハッシュ関数を複数回通過して、各パスワードのハッシュに必要な計算時間が増加します。^[5]たとえば、MD5-Crypt は、ソルト、パスワード、および現在の中間ハッシュ値を繰り返し基礎となる MD5 ハッシュ関数に返す 1000 回の反復ループを使用します。^[4]ユーザーのパスワード ハッシュは、ソルト値 (秘密ではありません) と最終ハッシュの連結です。ログインするたびに数分の 1 秒しか待たないため、余分な時間はユーザーにはわかりません。一方、ストレッチングでは、反復回数に比例してブルート フォース攻撃の有効性が低下します。これは、攻撃者が特定の時間枠内で実行できる試行回数が減るためです。この原理は、MD5-Crypt と bcrypt に適用されています。^[6]また、事前計算されたテーブルの構築に必要な時間も大幅に増加しますが、ソルトがない場合、これは一度だけ実行すれば済みます。

キー強化と呼ばれる別のアプローチでは、公開ソルトと秘密ソルトの 2 つのソルトを展開しますが、その後 (キー ストレッチングとは異なり) 秘密ソルトを安全に削除します。これにより、攻撃者と正当なユーザーの両方が秘密ソルト値の総当たり検索を実行する必要があります。秘密ソルトのサイズは、正当なユーザーが総当たり検索を感知できないように選択されます。ただし、攻撃者が必要とするレインボー ディクショナリは大幅に大きくなります。^[7]キー ストレッチングを紹介した論文^[8]では、この以前の手法に言及し、意図的に別の名前を選択しましたが、現在では「キー強化」という用語は (おそらく誤って) キー ストレッチングを指すためによく使用されています。

レインボー テーブルやその他の事前計算攻撃は、想定範囲外の記号を含むパスワードや、攻撃者が事前計算した記号よりも長いパスワードには効果がありません。ただし、数字や特殊文字を追加するなど、ユーザーがより安全なパスワードを選択する一般的な方法を考慮したテーブルを生成することはできます。コンピューティング処理に多大な投資がされているため、14 桁を超える長さのレインボー テーブルはまだ一般的ではありません。そのため、14 文字を超えるパスワードを選択すると、攻撃者はブルート フォース方式に頼らざるを得なくなる可能性があります。^{[引用が必要]}

マイクロソフトが使用する古いハッシュアルゴリズムであるLMハッシュに焦点を当てた特別な集中的な取り組みが公開されています。LMハッシュは、7文字を超えるパスワードが2つのセクションに分割され、それぞれが別々にハッシュされるため、特に脆弱です。15文字以上のパスワードを選択すると、LMハッシュが生成されないことが保証されます。^[9]

Unix、Linux、BSDのほぼすべてのディストリビューションとバリエーションはソルト付きのハッシュを使用していますが、多くのアプリケーションはソルトなしのハッシュ（通常はMD5）のみを使用しています。Microsoft Windows NT/2000ファミリは、LAN ManagerとNT LAN Managerのハッシュ方式（ MD4に基づく）を使用しており、ソルトも使用されていないため、最も一般的に生成されるテーブルの1つとなっています。2020年現在、ソルトがより一般的になり、GPUベースのブルートフォース攻撃がより現実的になったため、レインボーテーブルの使用は減少しています。ただし、8文字と9文字のNTLMパスワードではレインボーテーブルが利用可能です。^[10]

• A5/1
• ブルートフォース攻撃
• ディストリビューション
• ポラードのカンガルーアルゴリズム

• Oechslin, Philippe (2003-08-17)。「暗号解読の時間とメモリのトレードオフを高速化する」。Advances in Cryptology - CRYPTO 2003 ( PDF)。Lecture Notes in Computer Science。Vol. 2729。サンタバーバラ、カリフォルニア、米国: Springer。pp. 617–630。doi :10.1007/ 978-3-540-45146-4_36。ISBN 978-3-540-40674-7. S2CID 16086595. 2020年9月26日時点の オリジナル（PDF）からアーカイブ。 2019年3月13日閲覧。

• Philippe OechslinによるOphcrackページ オリジナルのレインボーテーブル研究