レインボーテーブル 【rainbow table】 レインボー攻撃

概要

レインボーテーブル(rainbow table)とは、ハッシュ値から原文(平文)を求める効率的な手法の一つで、あらかじめ計算した大量の平文候補を少ない容量で記録しておき、短時間で総当たり攻撃うもの。

認証暗号化電子署名などではよく「暗号学的ハッシュ関数」という計算法が用いられる。これは任意の長さの平文から一定の長さの「ハッシュ値」を求めるもので、ある特定のハッシュ値が得られるような平文を効率的に割り出すことはできないように設計されている。

どのようなハッシュ関数でも、すべての平文候補を用意して端から順にハッシュ化して一致するか試す「総当たり攻撃」をえば、平文を割り出すことは可能だが、これには膨大な計算量が必要で、現実的な時間で解くことは通常は困難である。

レインボーテーブルでは総当たり攻撃を効率化するため、あらかじめ大量の平文候補からハッシュ値を計算しておき、これをコンパクトな表現形式にまとめ、短い手順で照合が済むよう工夫する。最初に照合表を用意する工程には時間がかかるが、ある特定のハッシュ値への攻撃は短時間でえるようになる。

具体的な手法

レインボーテーブルでは、あるハッシュ値から何らかの平文候補を算出する「還元関数」(reduction function)を用意する。この関数入力するハッシュ値に応じて異なる出力が得られ、出力が標的の平文の仕様(文字数や文字種など)を満たす符号列になれば、どのようなものでも良い。

まず適当に生成した平文候補P1,1ハッシュ関数Sでハッシュ化し、ハッシュ値H1,1を得る。これを還元関数Rに与えると別の平文候補P1,2が得られ、ハッシュ化するとハッシュ値H1,2が得られる。この過程をn回繰り返すと、P1,1→H1,1→…→P1,n→H1,nという、ひと連なりの「チェーン」(鎖)ができる。

別の平文候補P2,1に対して同様にn回計算すると、P2,1→H2,1→…→H2,nというチェーンが得られる。これをm個の平文候補に対して繰り返すと、P1,1→…→H1,nからPm,1→…→Hm,nまでm×n個のが並んだ表が得られる。

還元関数が常に同じ場合、チェーンの途中で他のチェーンにすでに存在するが出現すると、以降の内容もすべて同一になってしまい効率が低下する。これを避けるため、実際には還元関数をn個用意しておき、k回目の処理には還元関数Rkを用いるようにする。

nとmが十分大きい場合、得られたを記録したデータの容量もとてつもない大きさになるが、レインボーテーブルではチェーンの途中のを取っておく必要はなく、各チェーンの先頭の平文候補P1,1~P1,nと、末尾のハッシュ値H1,n~Hm,nのみを保存する。これにより必要な容量は1/nで済む。

ハッシュ値から平文探索する際には、まず標的のハッシュ値Xが末尾のハッシュのどれかに一致しないか探す。一致しなければ、Xがチェーン末尾から2番目のハッシュ(H1,n-1~Hm,n-1)に含まれる可能性を考える。その場合に末尾に来るはずのはXにRn→Sを順に作用させたもので、これを末尾のハッシュと照合する。

見つからなければ、Xが末尾から3番目のハッシュ(H1,n-2~Hm,n-2)に含まれる可能性を考える。このとき末尾に来るはずのは、XにRn-1→S→Rn→Sを順に作用させたで、これを末尾のハッシュから探す。以降も同様に、XにRj→S→Rj+1→…→Rn→Sを順に適用して末尾候補を算出し、実際の末尾のハッシュ値に一致しないか探索する。

途中で一致するが見つかれば、そのチェーンのの算出を先頭の平文候補からやり直すことで、Xの算出に使われた目的の平文を容易に見つけ出すことができる。一方、先頭のハッシュに含まれる可能性まで探索し尽くしても見つからない場合には、表に含まれる範囲に平文は存在せず、攻撃失敗となる。

(2022.4.22更新)

他の辞典による解説 (外部サイト)

この記事の著者 : (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。
ホーム画面への追加方法
1.ブラウザの 共有ボタンのアイコン 共有ボタンをタップ
2.メニューの「ホーム画面に追加」をタップ
閉じる