|
レインボーテーブルレインボーテーブル (rainbow table) は、ハッシュから平文を得るために使われるテクニックの一つである。特殊なテーブルを使用して表引きを行うことで、時間と空間のトレードオフを実現している。 以降では、このテクニックの元となっているアイディアについて説明する。  最も単純な方法レインボーテーブルは「あるハッシュ値に対して総当たり攻撃を行った際の計算結果を、別のハッシュ値を攻撃する際に使用する」というアイデアに端を発する。例えば、平文 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 とすれば、最初の方法の 1⁄m になる。 レインボーテーブル上記のチェインを作成する際に問題となるのが、ハッシュ値および平文の衝突である。上記の方法では、例えば平文 Pi と Pj+1 とがたまたま同じ平文になってしまった場合、以降のチェインの内容 Ci, Pi+1, … と Cj+1, Pj+2, … は全て同じ値になってしまう。その結果、テーブルに格納されているペアの実質的な個数が少なくなってしまう。つまり、衝突が起こらなかったテーブルを使用する場合と比べて、平文を得る確率が低くなってしまう。 レインボーテーブルでは、この問題をできる限り回避するため、還元関数を R1, R2, …, Rm と変化させて、チェインの長さと同じ個数だけ用意しておく。これによって、チェインの長さを m とすると、衝突の発生確率を通常のチェインと比較して 1⁄m-1 にすることができる。 処理の例処理の例として、ハッシュ値 re3xes から対応する平文を探す処理を考える。[1] 
弱点レインボーテーブルの弱点として、次の2点が挙げられる。
また、テーブル作成時に指定していなかった文字種が平文に含まれていた場合も、テーブルから平文を得ることはできない。したがって、パスワードに十分な長さと文字種をもたせることが、レインボーテーブルへの有効な対策となる。 今のところ、生成に必要な領域の問題から、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 も開発されている。 関連項目参考文献
脚注
外部リンク
|
||||||||||||||||||||||||||||||||||||||||||
![{\displaystyle \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]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84c6ef13878c44db4bafbfdff43f79460b35646c)
Portal di Ensiklopedia Dunia
