レインボーテーブルについて

今回はレインボー（テーブル）攻撃で使用するレインボーテーブルについて自分なりに分かる範囲内で解説します。

レインボーテーブル攻撃とは

パスワードとそのハッシュ値のペアを事前に先回り計算して対応表を作っておき、その対応表からパスワードを割り出す攻撃の一種です。

但し普通に対応表を作るととんでもない容量のストレージを食うので、記憶容量節約のために特殊な保管方法で作成した表をレインボーテーブルといいます。

つまり保管方法の話です。

で、その特殊な保管方法の解説です。

１つの平文とそのハッシュ値のペアを１つの駅に例えます。

その駅を1本の線路で多数つないで長い鉄道路線を作り、その路線の始発駅と終点駅のペアだけを記録したのがレインボーテーブルです。

これを始発駅を変えながら多数の路線数を記録していきます。

つまりレインボーテーブルには数多くの路線の始発駅と終点駅のみが記録されている表となります。

例えばこんな感じ。

中間駅の記録は全て省略しているので、その分だけ記憶容量が少なくてすみます。

あなたがどこかの中間駅に目隠しと耳栓をされて放置されているとしましょう。

この駅からは下り各駅停車の列車しか出ません。

下り列車に乗ったところであなたは目隠しと耳栓をはずされます。そして先ほどまで居た駅を当ててみなさいと言われます。

あなたが持っているのは全ての鉄道路線の始発駅と終点駅をペアで記録されている上記レインボーテーブルだけです。

列車が次の駅に到着したところで、あなたはその駅名が終点駅全部の中に存在するかどうかを調べます。

しかし残念ながらありませんでした。

あなたは引き続き下り列車に乗って次の駅へ行きます。

駅に着いたらもう一度、その駅が終点駅のどれかと一致していないかをレインボーテーブルで調べます。

このようにして駅に着くたびに終点駅との照合を繰り返していれば、やがていつかは本当に終点駅に到着して、その終点駅名が分かります。（レインボーテーブルのデータ量が十分大きい場合）

終点駅に到着したあなたは、その路線の始発駅をレインボーテーブルから割り出してそこに向かいます。

そして始発駅から下り列車に乗ると、やがては必ずあなたが目隠しされ放置されていた最初の駅にたどり着きます。

この時当然、その駅名も判明します。

以上が中間駅の割り出し方法です。

駅と駅とをつなぐ線路となるのが還元関数です。

これはあるハッシュ値から別な平文を導き出せれば良い関数であり、正解の平文を導き出す必要はありません（この正解でなくていいってのが分かりにくい所ですね）

要は再現性があればいいということ。

ある駅から出発した列車が、繰り返し必ず同じ次の駅に到着すればいいわけです。

平文1　⇨　ハッシュ値1　▶　還元関数1　▶　平文２　⇨　ハッシュ値２　▶　還元関数２　▶　平文３　⇨　ハッシュ値3

このように計算して、スレッドを一定数まで伸ばしていきます。

そして次に、別な平文から出発して同じ順番で還元関数を適応していき、別スレッドの計算を行います。

これを多数の平文から出発して計算します。

最終的に各スレの最初と最後の値を記録に残して結果を蓄積していきます。

なお、どのように中間の計算をしたのか（還元関数1、還元関数2、還元関数3…）も当然一緒に記録しておきます。後で再現するためです。

始発駅と終点駅さえ記録しておけば、

という手順で必ず目的の駅に到達できます。

このことを利用して、中間駅の記載を省略して記憶容量を節約できることが、レインボーテーブルの本質です。