レインボーテーブル

レインボーテーブルとは

レインボーテーブルは、ハッシュ関数によって生成されたハッシュ値から、元の平文（パスワードなど）を効率的に復元するための技術です。この技術は、特にパスワード解析の分野で利用され、時間と空間のトレードオフを実現することで、総当たり攻撃よりも高速な解析を可能にします。

基本的なアイデア

レインボーテーブルの基本的なアイデアは、「あるハッシュ値に対する総当たり攻撃の結果を、別のハッシュ値を攻撃する際に再利用する」というものです。最も単純な例として、平文とそれに対応するハッシュ値のペアをテーブルに格納しておき、このテーブルを逆引きすることでハッシュ値から平文を得る方法が考えられます。しかし、この方法では、すべてのペアを記録する必要があるため、莫大な記憶容量を消費するという課題があります。

チェイン化による効率化

この記憶容量の問題を解決するために、平文とハッシュ値のペアを「チェイン化」します。具体的には、ハッシュ値から次の平文候補を生成する「還元関数」と呼ばれる関数を利用し、ハッシュ値と平文を交互に連結した鎖のようなデータ構造を作成します。

このチェインは、次のような処理の流れで生成されます。

1. 初期の平文Piをハッシュ関数Hに通してハッシュ値Ciを得る。
2. ハッシュ値Ciを還元関数Rに通して、次の平文候補Pi+1を得る。
3. Pi+1をハッシュ関数Hに通してハッシュ値Ci+1を得る。
4. この処理を繰り返すことで、平文とハッシュ値が連なったチェインが生成される。

このチェインを大量に作成し、各チェインの開始平文と最終ハッシュ値のみを記録することで、必要な記憶容量を大幅に削減できます。ハッシュ値から平文を復元する際には、与えられたハッシュ値を還元関数とハッシュ関数に通して、テーブル内の最終ハッシュ値と一致するかを探索します。一致するチェインが見つかれば、その開始平文からチェインを再生成することで、元の平文を特定できます。

レインボーテーブルの特徴

レインボーテーブルは、チェイン生成時に同じ平文やハッシュ値が衝突する可能性があり、効率が低下する場合があります。この問題に対処するため、各チェインのステップごとに異なる還元関数を使用します。これにより、衝突の発生確率を低減し、より多くの平文をカバーできるようになります。

具体的な処理例

ハッシュ値 `re3xes` から対応する平文を復元する例を考えます。

1. `re3xes` に最後の還元関数を適用し、長さ1のチェインを作成。テーブルに末尾の平文がないか検索。
2. 見つからなければ、最後から2つ分の還元関数を適用し、長さ2のチェインを作成。テーブルに末尾の平文がないか検索。
3. 一致する平文 `linux23` が見つかったら、`linux23` を含むチェインの開始平文 `passwd` を取得。
4. `passwd` からチェインを再生成し、`re3xes` がチェイン中に存在するかを確認。存在すれば、その直前の平文 `culture` が対応する平文となる。

レインボーテーブルの弱点

レインボーテーブルには、以下の弱点があります。

テーブルの事前作成が必要: ハッシュ関数、平文の文字種や長さごとに異なるレインボーテーブルが必要になります。
ソルトへの脆弱性: ハッシュにソルトが使用されている場合、レインボーテーブルの効果は著しく低下します。ソルト付きハッシュには、ソルトの数だけテーブルが必要となり、実質的にレインボーテーブルは利用できなくなります。

ソルト対策とレインボーテーブルの限界

ソルトを使用することで、パスワードの解析難易度を大幅に上げることができ、レインボーテーブルの有効性を低下させることが可能です。また、平文の文字種や長さがテーブルの想定外である場合、レインボーテーブルでは平文を復元することができません。そのため、パスワードには十分な長さと多様な文字種を使用することが、レインボーテーブルに対する有効な対策となります。

現在の技術では、8文字を超えるパスワードに対するレインボーテーブルは、そのデータ量の大きさから、一般的ではありません。

レインボーテーブルの応用

レインボーテーブルは、ソルト付きハッシュ関数が使用されていないアプリケーションや、古いシステムで使用されていたソルトなしのハッシュ関数を使用している場合に、パスワード解析に使われてきました。Windowsの古いバージョンで使用されていたLMハッシュなどは、レインボーテーブルによる攻撃の対象となっていました。

発明者

レインボーテーブルは、Philippe Oechslinによって発明されました。彼は、レインボーテーブルを利用したパスワードクラッカーであるOphcrackの開発者でもあります。その後、より多くの種類の文字やハッシュ関数に対応したRainbowCrackも開発されています。

まとめ

レインボーテーブルは、ハッシュ値から平文を高速に復元するための強力なツールですが、ソルト付きハッシュや複雑なパスワードには効果が限定的です。パスワードのセキュリティを確保するためには、ソルトの使用、十分な長さと複雑さを持ったパスワードの使用が重要です。

参考文献

Making a Faster Cryptanalytical Time-Memory Trade-Off, Philippe Oechslin, Advances in Cryptology - CRYPTO 2003
Rainbow tables explained, Ph. Oechslin, (ISC)2 Newsletter, Mar-Apr 2005

もう一度検索