レインボーテーブル

レインボーテーブルは時間と空間のトレードオフの実用的な例である。レインボーテーブルは、試行ごとにハッシュを計算する総当たり攻撃よりも計算処理時間は短くて済むが、より多くのストレージを必要とする。一方で、あらゆる可能なパスワードのハッシュを保存する単純なテーブルと比較すると、処理時間は長くなるが、必要なストレージは少なくて済む。

レインボーテーブルは、マーティン・ヘルマンによる初期のより単純なアルゴリズムを応用したものとして、フィリップ・エクスリン（Philippe Oechslin）によって発明された。

 背景 
ユーザー認証において、パスワードは平文またはハッシュとして保存される。平文として保存されたパスワードは、データベースへのアクセスが侵害された場合に容易に盗まれるため、データベースは通常、代わりにハッシュを保存する。したがって、認証システムを含む誰も、データベースに保存された値を見るだけではパスワードを知ることはできない。

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

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

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

 語源 
右|サムネイル|Crypto 2003で発表されたレインボーテーブルの図解
レインボーテーブルの発明者はフィリップ・エクスリン（Philippe Oechslin）であり、Windows のパスワードクラッカーである Ophcrack の実装も行っている。後には、より多くの種類の文字やハッシュ関数（LMハッシュ, MD5, SHA-1 など）に対応した :en:RainbowCrack も開発されている。この用語は、攻撃の成功率を高めるために異なる還元関数（reduction function）を使用する方法に由来する。元のマーティン・ヘルマンの手法では、それぞれ異なる還元関数を持つ多数の小さなテーブルを使用していた。レインボーテーブルはそれよりもはるかに大きく、各列で異なる還元関数を使用する。還元関数を色で表現すると、レインボーテーブルには虹が現れることになる。 エクスリンの論文の図2には、これらのセクションがどのように関連しているかを示す白黒の図が含まれている。Crypto 2003会議でのプレゼンテーションのために、エクスリンは虹との関連性をより明確にするために図に色を追加した。会議で提示された拡張された図解は、右図の通りである。

 最も単純な方法 
レインボーテーブルは「あるハッシュ値に対して総当たり攻撃を行った際の計算結果を、別のハッシュ値を攻撃する際に使用する」というアイデアに端を発する。例えば、平文 Pi (i = 1, 2, ...) と、それらをハッシュ化した値 Ci をテーブルに格納しておき、このテーブルを逆引きすればハッシュ値から対応する平文が得られる。

ただし、この方法では、得られた平文とハッシュ値とのペアを全て記録しておく必要があり、実現には莫大な記憶領域を必要とする。

 チェイン化 
使用する記憶域の量を削減するために、平文とハッシュ値とのペアを「チェイン化」することを考える。

ここで、あるハッシュ値 Ci を種として、次のターゲットとなる平文を適当に選ぶ関数 R を考える。ここで、関数 R には、出力が平文の候補として正当であること（例えば、パスワードが英数字しか受け付けないならば、常に英数字だけからなる文字列を出力すること）と、副作用がないという条件を満たせば、どんな関数を使用してもよい。このハッシュ値から平文候補となる値を生成する関数 R を「還元関数」(reduction function) と呼ぶ。

ハッシュ関数を H とすると、適当に選んだ最初の平文 Pi から、Pi をハッシュ関数に通した値 Ci 、次のターゲットとなる平文 Pi+1 を得るという処理の流れは次のようになる。



この処理を何度か繰り返すと、平文1、ハッシュ値1、平文2、ハッシュ値2、…… という、平文とハッシュ値のペアから成る「チェイン（鎖）」ができあがる。

続いて、このようなチェインを大量に作成する。作成したチェインの集まりをテーブルと呼ぶ。各チェインの長さを m とすると、テーブルの内容は次のようになる。



ここで、各チェインの先頭になる平文 Pi, Pj, Pk, …… は、他のチェインの内容と重複しないように適当に選択する。チェインの長さは任意であり、また各チェインの長さが異なっていてもよい。ここでは説明のため、全てのチェインの長さが同じとして考える。

チェインを作成したら、チェインの先頭にある平文 Pi, Pj, Pk, …… と、チェインの末尾にあるハッシュ値 Ci+m-1, Cj+m-1, Ck+m-1, …… だけを結果として記録しておく（記憶域を削減する）。

ハッシュ値から平文を得るには、パスワードが知りたいハッシュ値 Cx を還元関数とハッシュ関数に次々に通していき、その都度 Ci+m-1, Cj+m-1, Ck+m-1, …… と比較を行えばよい。もし一致するものが見つかれば、対応する Pi, Pj, Pk, …… からチェインを復元する。

この方法を使うと、記録しておく平文とハッシュ値の個数は、チェインの長さを m とすれば、最初の方法の  になる。

 レインボーテーブル 
上記のチェインを作成する際に問題となるのが、ハッシュ値および平文の衝突である。上記の方法では、例えば平文 Pi と Pj+1 とがたまたま同じ平文になってしまった場合、以降のチェインの内容 Ci, Pi+1, … と Cj+1, Pj+2, … は全て同じ値になってしまう。その結果、テーブルに格納されているペアの実質的な個数が少なくなってしまう。つまり、衝突が起こらなかったテーブルを使用する場合と比べて、平文を得る確率が低くなってしまう。

レインボーテーブルでは、この問題をできる限り回避するため、還元関数を R1, R2, …, Rm と変化させて、チェインの長さと同じ個数だけ用意しておく。これによって、チェインの長さを m とすると、衝突の発生確率を通常のチェインと比較して  にすることができる。

 処理の例 
処理の例として、ハッシュ値 re3xes から対応する平文を探す処理を考える。以下の説明ではレインボーテーブルの末尾の要素としてハッシュ値ではなく平文を使用しているが、末尾がハッシュ値であるテーブルであっても生成および探索処理にほぼ変わりはない。

650px|thumb|none|レインボーテーブルを使ってハッシュ値から平文を得る処理

 ハッシュ値 re3xes に対して最後の還元関数を使い、長さ1のチェインを作成する。そこで得られた平文 (rambo) が、テーブルに格納されているチェインの末尾の平文の中にないか探す（ステップ 1）。
 もし見つからなければ（rambo がテーブル中になければ）、最後から還元関数2つ分の処理を行い、長さ2のチェインを作成する。そして、テーブルに格納されているチェインの末尾の平文の中に、作成したチェインの末尾の平文と合致するものがないか探す（ステップ 2）。
 それでも見つからなければ、還元関数3つ分、4つ分……と、平文が見つかるか、チェインの長さがテーブル中のチェインの長さを超えるまで続ける。平文が見つからなければ、攻撃は失敗である。
 合致する平文が見つかったら（ステップ3、linux23がテーブル中にある）、linux23 を含むチェインの先頭の平文をテーブルから取得する。
 テーブルから取得した平文 passwd で始まるチェインを作成し（ステップ4）、そのチェイン中にハッシュ値 re3xes がないか探す。ハッシュ値が見つかれば、その手前の平文 (culture) が対応する平文であると分かる（攻撃は成功）。

 弱点 
レインボーテーブルの弱点として、次の2点が挙げられる。

 定義域・値域・ハッシュの種類ごとに別のテーブルが必要 
平文の文字種や長さ、ハッシュ値の長さ、ハッシュ関数によって、できあがるレインボーテーブルの内容は異なる。これらのうち一つでも異なるハッシュ値に対しては、別のレインボーテーブルが必要となる。

 ソルトの使用 
ハッシュにソルトが使われている場合、レインボーテーブルの有効性は著しく低下する。例えば、次のようなハッシュ関数 MD5() を考える（ここで、 "." は文字列結合演算子とする）。

hash = MD5 (password . salt)

このようなハッシュからパスワードを得る場合、取りうる salt の値の個数だけテーブルを作成する必要がある。このような場合、レインボーテーブルの効果は大幅に薄れてしまう。ソルトを利用するとパスワードを長くしたのと同じ効果が得られる。ソルトを付加した後の平文の長さとテーブルが対象とする平文の長さとが異なる場合、テーブルから平文を得ることはできない。もし平文が見つかっても、得られた平文からソルト部分を判断して取り除く必要がある。また、テーブル作成時に指定していなかった文字種が平文に含まれていた場合も、テーブルから平文を得ることはできない。したがって、パスワードに十分な長さと文字種をもたせることが、レインボーテーブルへの有効な対策となる。今のところ、生成に必要な領域の問題から、8文字を超える長さの平文に対するレインボーテーブルは一般的に利用できるようにはなっていない。しかし、 LM hash （Windows のパスワードに使用されている）に対しては集中的な解析が行われており、例えば Shmoo Group によるレインボーテーブルが利用可能になっている。

 用途 
各種 Unix, Linux, BSD のほとんど全てではソルトつきのハッシュ関数が使われているが、ソルトなしのハッシュ関数（特に MD5）を使用しているアプリケーションは数多くある。また、 Windows NT/Windows 2000 ファミリは LAN Manager と NT Lan Manager でソルトなしのハッシュ関数を使用しており、これらに対しては盛んにレインボーテーブルの生成が行われていた。

 関連項目 
 :en:Pollard's lambda algorithm
 原像攻撃
 ソルト
 ペッパー

 参考文献 
  Making a Faster Cryptanalytical Time-Memory Trade-Off, Philippe Oechslin, Advances in Cryptology - CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17--21, 2003, Proceedings. Lecture Notes in Computer Science 2729 Springer 2003, ISBN 3-540-40674-3
 Rainbow tables explained, Ph. Oechslin, (ISC)2 Newsletter, Mar-Apr 2005

 脚注 

 外部リンク 
Ophcrack page by Philippe Oechslin レインボーテーブルに関する最初の研究とオンラインデモ
download Rainbow Table
How Rainbow Tables work
 フリーのレインボーテーブル
 レインボーテーブルの分散コンピューティングプロジェクト

Category:データ構造
Category:コンピュータセキュリティ
Category:ハッシュ関数
Category:検索アルゴリズム
Category:暗号解読攻撃