サイバー攻撃

セキュリティ

レインボーテーブルの仕組みを図解で分かりやすく解説

レインボーテーブルとは

レインボーテーブル (rainbow table)とは、ハッシュ値から元のデータ(平文)を導き出すための手法で、特殊なテーブルを使用します。

レインボーテーブルは不正入手したハッシュ値(パスワード)の解析などに利用されており、サイバー攻撃の一種です。

スポンサーリンク

ハッシュ関数とは

ハッシュ関数とは、入力データを一定の手順で計算を行い、入力値のデータの長さに関わらず、決まった長さの文字列を出力する関数のことです。

ハッシュ関数

ハッシュ関数により得られたデータのことを「ハッシュ値」と呼び、ハッシュ値から元の入力データを推測するのは非常に困難(一方向性関数)といわれています。

この困難な作業を行うのがレインボーテーブルです。

レインボーテーブルで使用する2つの関数

レインボーテーブルでは「ハッシュ関数」と「還元関数」の2つの関数の特性を利用します。それぞれの関数の特性は次の通りです。

ハッシュ関数

ハッシュ関数には様々な関数(MD5SHA-1SHA-2、SHA-3など)が存在します。そのため、「平文」から得られる「ハッシュ値」もハッシュ関数により異なります。

しかし、使用するハッシュ関数と「平文」が決まれば、得られる「ハッシュ値」は必ず同じです。

同じデータは同じハッシュ値になる

還元関数

還元関数とは、ハッシュ値から平文候補となる値を生成する関数です。

ハッシュ値は一方向性関数のため、ハッシュ値から元のデータである「平文」を推測することは困難です。そのため、還元関数を利用して平文候補となる値を生成し、元のデータである「平文」を導き出すための手助けをする役割を持ちます。

スポンサーリンク

レインボーテーブルの仕組み

[事前準備] チェーンを作成する(チェーン化)

使用する記憶域の量を削減するために、ハッシュ関数と還元関数を利用し、平文とハッシュ値とのペアを「チェイン化」していきます。

1. 任意の「平文」をハッシュ関数で「ハッシュ値」にする

任意の平文をハッシュ関数を利用してハッシュ値へと変換します。

レインボーテーブルのチェイン化手順1

2. 還元関数で「ハッシュ値」を「平文」に戻す

ハッシュ関数で変換した「ハッシュ値」を、還元関数で「平文」へと戻します。※ここで使用した還元関数は「還元関数1」とします。

レインボーテーブルのチェイン化手順2

3. 再び「平文」をハッシュ関数で「ハッシュ値」にする

循環関数で戻した「平文」をハッシュ関数で再び「ハッシュ値」へと変換します。

 

レインボーテーブルのチェイン化手順3

4. 再び還元関数で「ハッシュ値」を「平文」に戻す

ハッシュ関数で変換した「ハッシュ値」を、還元関数で再び「平文」へと戻します。そして、3と4の処理を一定回数繰り返し「平文」と「ハッシュ値」とのペアを「チェイン化」していきます。

還元関数は2で使った関数とは異なる関数を使用します。同じ還元関数は使用しないので、チェインの長さ分だけ還元関数を用意するのも特徴です。

※ここで使用した還元関数は「還元関数2」とします。

レインボーテーブルのチェイン化手順4

5. チェイン化した先頭と末尾を記録する

上記の1~4で生成したチェインの先頭と末尾の情報を記録しておきます。(全てを保存しておくと膨大な記憶域が必要なため、記憶域を削減する)

※今回は説明の都合上、還元関数は2回だけ実施した例(チェインの先頭「パスワード」の末尾が「いぬ」)で説明しています。

チェイン化

[攻撃例] ハッシュ値 から 平文 を導き出すまでの流れ

ここからは、不正入手したハッシュ値をレインボーテーブルを利用して元のデータ(平文)を導き出すまでの流れを図解で説明していきます。

1. 入手したハッシュ値を末尾の還元関数2で「平文」に戻し、記録してある末尾の「平文」と比較する

不正入手した「ハッシュ値」を、チェインの末尾で使用した還元関数2で「平文」に戻します。そして、記録してあるチェインの末尾の「平文」と比較し、一致しているものがないかを調べます。

一致している場合は、一致したチェインの先頭が不正入手した「ハッシュ値」の元のデータ(平文)なので処理は終了です。

一致していない場合は、2の処理へと進みます。

レインボーテーブル手順1

今回の例では一致していないので、2の処理へと進みます。

2. 入手したハッシュ値を一つ前の還元関数1で「平文」→「ハッシュ値」→「平文」と変換し、記録してある末尾の「平文」と比較する

不正入手した「ハッシュ値」を、チェインの末尾の一つ前で使用した還元関数1で「平文」に戻します。そして、チェインを作成した手順と同じで「ハッシュ値」へと変換(チェイン作成時の手順3)、還元関数2を使い「平文」へと変換(チェイン作成時の手順4)していきます。

チェインを作成した時と同じ手順で末尾の「平文」を導き出したら、記録してあるチェインの末尾の「平文」と比較し、一致しているものがないかを調べます。

一致している場合は、一致したチェインの先頭が不正入手した「ハッシュ値」の元のデータ(平文)なので処理は終了です。

一致していない場合は、更に前へ還元関数を使用して同様の手順を行います。このように記録したチェーンの末尾に一致する平文が得られるまで、開始列までさかのぼる形で処理を繰り返していきます。

レインボーテーブル手順2

今回の例では一致しているので、不正入手したハッシュ値「3f032...(省略)」の元データ(平文)は「パスワード」であることが、レインボーテーブルより導きだせています。

いいね!フォローをお願いします /

© 2020 ITを分かりやすく解説