(Wikipedia レインボーテーブルより)

レインボーテーブル (rainbow table) は、ハッシュから平文を得るために使われるテクニックの一つである。特殊なテーブルを使用して表引きを行うことで、時間と空間のトレードオフを実現している。

以降では、このテクニックの元となっているアイディアについて説明する。

最も単純な方法

まず、このテクニックの発端は「あるハッシュ値に対して総当たり攻撃を行った際の計算結果を、別のハッシュ値を攻撃する際に使用できないか」という点にある。例えば、ある平文 P_i と、それをハッシュ化した値 C_i をテーブルに格納しておき、このテーブルを逆引きすればハッシュ値から対応する平文が得られる。

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

チェイン化

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

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

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

$P\_i\; ~\; \backslash xrightarrow\{H(P\_i)\}\; ~\; C\_i\; ~\; \backslash xrightarrow\{R(C\_i)\}\; ~\; P\_\{i+1\}\; ~\; \backslash xrightarrow\{H(P\_\{i+1\})\}\; ~\; \backslash cdots$

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

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

$\backslash left[$
\begin{array}{ccccccc}
P_i & C_i & P_{i+1} & C_{i+1} & P_{i+2} & \cdots & C_{i+m-1} \ P_j & C_j & P_{j+1} & C_{j+1} & P_{j+2} & \cdots & C_{j+m-1} \ P_k & C_j & P_{k+1} & C_{k+1} & P_{k+2} & \cdots & C_{k+m-1} \ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \ \end{array}
\right]

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

チェインを作成したら、チェインの先頭にある平文 P_i, P_j, P_k, … と、チェインの末尾にあるハッシュ値 C_i+m-1, C_j+m-1, C_k+m-1, ... だけを結果として記録しておく。

ハッシュ値から平文を得るには、ターゲットとなるハッシュ値を還元関数とハッシュ関数に次々に掛けていき、その都度 C_i+m-1, C_j+m-1, C_k+m-1, … と比較を行えばよい。マッチするものが見つかれば、対応する P_i, P_j, P_k, … からチェインを復元する。

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

レインボーテーブル

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

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

処理の例

処理の例として、ハッシュ値 re3xes から対応する平文を探す処理を考える。

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

弱点

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

• 定義域・値域・ハッシュの種類ごとに別のテーブルが必要

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

• salt の使用

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

hash = MD5 (password . salt)

このようなハッシュからパスワードを得る場合、取りうる salt の値の数だけテーブルを作成する必要がある。このような場合、レインボーテーブルの効果は大幅に薄れてしまう。

salt を利用するとパスワードを長くしたのと同じ効果が得られる。 salt 付加後の平文の長さとテーブルが対象とする平文の長さとが異なる場合、テーブルから平文を得ることはできない。もし平文が見つかっても、得られた平文から salt 部分を判断して取り除く必要がある。

また、テーブル作成時に指定していなかった文字種が平文に含まれていた場合も、テーブルから平文を得ることはできない。そのため、パスワードに十分な長さと文字種を持たせることが、レインボーテーブルへの有効な対策となる。
今のところ、生成に必要な領域の問題から、8文字を越える長さの平文に対するレインボーテーブルは一般的に利用できるようにはなっていない。しかし、 LM hash （Windows のパスワードに使用されている）に対しては集中的な解析が行われており、例えば Shmoo Group によるレインボーテーブルが利用可能になっている。

用途

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

発明者

レインボーテーブルの発明者は Philippe Oechslin であり、Windows のパスワードクラッカーである Ophcrack の実装も行っている。後には、より多くの種類の文字やハッシュ関数（LMハッシュ, MD5, SHA-1 など）に対応した も開発されている。