レインボーテーブルのソースを表示

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

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

[[Image:simple_rainbow_table.svg|thumb|550px|none|3 種類の還元関数を使った簡単なレインボーテーブルの例]]

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

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

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

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

ハッシュ関数を ''H'' とすると、適当に選んだ最初の平文 ''P<sub>i</sub>'' から、''P<sub>i</sub>'' を[[ハッシュ関数]]に通した値 ''C<sub>i</sub>'' 、次のターゲットとなる平文 ''P<sub>i+1</sub>'' を得るという処理の流れは次のようになる。

:<math>
P_i ~ \xrightarrow{H(P_i)} ~ C_i ~ \xrightarrow{R(C_i)} ~ P_{i+1} ~ \xrightarrow{H(P_{i+1})} ~ \cdots
</math> 

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

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

:<math>
\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_k & P_{k+1} & C_{k+1} & P_{k+2} & \cdots & C_{k+m-1} \\
  \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
 \end{array}
\right]
</math> 

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

チェインを作成したら、チェインの先頭にある平文 ''P<sub>i</sub>'', ''P<sub>j</sub>'', ''P<sub>k</sub>'', …… と、チェインの末尾にあるハッシュ値 ''C<sub>i+m-1</sub>'', ''C<sub>j+m-1</sub>'', ''C<sub>k+m-1</sub>'', …… だけを結果として記録しておく（記憶域を削減する）。

ハッシュ値から平文を得るには、パスワードが知りたいハッシュ値 ''C<sub>x</sub>'' を還元関数とハッシュ関数に次々に通していき、その都度 ''C<sub>i+m-1</sub>'', ''C<sub>j+m-1</sub>'', ''C<sub>k+m-1</sub>'', …… と比較を行えばよい。もし一致するものが見つかれば、対応する ''P<sub>i</sub>'', ''P<sub>j</sub>'', ''P<sub>k</sub>'', …… からチェインを復元する。

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

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

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

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

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

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

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

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

* [[パスワードクラック#ソルト|ソルト]]の使用
:ハッシュにソルト (salt) が使われている場合、レインボーテーブルの有効性は著しく低下する。例えば、次のようなハッシュ関数 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 でソルトなしのハッシュ関数を使用しており、これらに対しては盛んにレインボーテーブルの生成が行われていた。

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

== 関連項目 ==
* [[:en:Pollard's lambda algorithm]]
* [[原像攻撃]]

== 参考文献 ==
*  [http://lasecwww.epfl.ch/~oechslin/publications/crypto03.pdf 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
* [https://www.isc2.org/cgi-bin/content.cgi?page=738 Rainbow tables explained], Ph. Oechslin, (ISC)2 Newsletter, Mar-Apr 2005

== 脚注 ==

<references/>

== 外部リンク ==
*[http://lasecwww.epfl.ch/~oechslin/projects/ophcrack Ophcrack page by Philippe Oechslin] レインボーテーブルに関する最初の研究とオンラインデモ
*[http://rainbowtables.ddl.cx/ download Rainbow Table]
*[http://kestas.kuliukas.com/RainbowTables/ How Rainbow Tables work]
*[http://rainbowtables.shmoo.com/] フリーのレインボーテーブル
*[http://www.freerainbowtables.com/] レインボーテーブルの分散コンピューティングプロジェクト

{{cryptography navbox|hash}}
{{DEFAULTSORT:れいんほてふる}}
[[Category:データ構造]]
[[Category:コンピュータセキュリティ]]
[[Category:ハッシュ関数]]
[[Category:検索アルゴリズム]]
[[Category:暗号解読攻撃]]

{{Computer-stub}}