レインボーテーブルとは？概要、攻撃の仕組みや対策方法も解説！

レインボーテーブルとは

レインボーテーブルの概要を見ていきましょう。

ハッシュ値を平文に戻す方法の１つ

ハッシュ値は平文を不可逆的に変換したものです。この変換をハッシュ化といいます。後に復号することを想定した暗号化とは異なり、ハッシュ値から元の平文に復号することはできません。

しかし、レインボーテーブルを使えばハッシュ値から元文を割り出せる場合があります。レインボーテーブルは平文とハッシュ値の対応表であり、ハッシュ値を検索して対応する平文を探せます。

たとえば、「リンゴ」のハッシュ値が「a2f4」だとしましょう。この平文とハッシュ値の間には数学的関連性がないため、暗号化のようなアルゴリズムによる復号は不可能です。しかし、レインボーテーブルから「a2f4」を探せば、対応する平文が「リンゴ」だと分かります。

このことから、レインボーテーブルはハッシュ化によって秘匿された情報を不正に取得する攻撃手段として使われます。

２つの関数が使われる

レインボーテーブルでは、ハッシュ関数と還元関数という２種類の関数が用いられます。

１．ハッシュ関数

ハッシュ関数とは、平文をハッシュ化するための関数です。前述の例で言えば、「リンゴ」を「a2f4」に変換するのがハッシュ関数です。不可逆的な変換を担うことから、一方向関数や要約関数とも呼ばれます。

一口にハッシュ関数と言っても、いくつかのアルゴリズムが存在します。平文が同じ「リンゴ」でも、どのようなハッシュ値になるかはハッシュ関数のアルゴリズム次第です。しかし、アルゴリズムと平文が同じであれば、得られる結果は常に同じになります。

２．還元関数

還元関数とは、ハッシュ値から平文を得る関数です。ただし、ハッシュ化の変換をそのまま逆に行うのは不可能です。「リンゴ」の例でいえば、ハッシュ値「a2f4」からハッシュ化前の平文「リンゴ」を得る関数は作れません。

還元関数の役割は、ハッシュ値をパスワードなどの条件を満たす平文のどれかに対応づけることです。「a2f4」の本当の平文は「リンゴ」ですが、還元関数ではそのことは気にせず別の平文と結び付けます。

一見無意味な操作ですが、還元関数は次の項で解説するチェインの作成に役立ちます。

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

レインボーテーブル攻撃とは、レインボーテーブルを利用して不正にハッシュ化内容を解読するサイバー攻撃です。その仕組みを見ていきましょう。

１．チェインを作成する

ハッシュ関数と還元関数を使い、以下のような手順で平文とハッシュ値のチェインを作成します。

1. １．平文「リンゴ」にハッシュ関数を使い、ハッシュ値「a2f4」を得る
2. ２．ハッシュ値「a2f4」に還元関数を使い、平文「ミカン」を得る
3. ３．手順１と２を一定の回数繰り返し「リンゴ-a2f4-ミカン-bf55-…イチゴ」というチェインを作る

上記の例では「リンゴ」のハッシュ値「a2f4」から還元関数で、別の平文「ミカン」を得るのがポイントです。

これによりランダムに多種の平文がテーブルに加わることになります。還元関数は、手順１と２の繰り返しごとに変更します。たまたま同じ平文が出現した場合に以後のデータが全て重複してしまう事態を避けるためです。

異なる平文からスタートして同様な手順で複数のチェインを作ります。これらのチェインを並べたものがレインボーテーブルです。各チェインの同じ列では共通の還元関数を使っていることになります。

しかし、このままではデータの量が多すぎるため、膨大なメモリが必要です。そこで、各チェインの先頭と末尾だけを残し、それ以外の部分は削除します。上記の例で言えば、チェインは「リンゴ-イチゴ」の状態になります。

２．還元関数を使って復元する

レインボーテーブルは、複数のチェインの先頭と末尾だけが並び、下記のような状態になっています。

リンゴ-イチゴ
サクラ-スミレ
・
・
トマト-パセリ

関数を使って計算すれば、先頭と末尾以外の部分を復元できます。これを活用し、ハッシュ値から元の平文を求める手順は以下のとおりです。

1. １．対象のハッシュ値に、チェインの末尾の列を得た還元関数を適用する。
2. ２．得られた平文と同一のものがないか各チェインの末尾を調べる。
3. ３．ない場合は末尾の１つ前に使った還元関数を、対象のハッシュ値に適用する。得られた平文のハッシュ値を求め、このハッシュ値に末尾の列に使った還元関数を適用して平文を得る。
   この平文で２．の照合を行う。いずれかのチェーンの末尾に一致する平文が得られるまで、開始列をさかのぼる形で繰り返す。
4. ４．一致する末尾を持つチェーンが見つかれば、そのチェーンを復元する。チェーン内にある対象のハッシュ値の、直前の平文が求める元文になる。

たとえば、手順１で得た平文が「スミレ」だった場合に、手順２で末尾に「スミレ」が見つかったとします。このとき、そのチェーンを復元すれば、「スミレ」の一つ手前にあるハッシュ値と解読対象のハッシュ値は同一です。

さらにその手前の平文が、求めたい元文になります。末尾の列に一致する平文がない場合は、列をさかのぼってチェックするわけですが、テーブルには先頭と末尾しかありません。

そこで、もしチェックしたい列に対象のハッシュ値があるとしたらチェーンの末尾が何になるかを計算して、一致を調べるわけです。

レインボーテーブル攻撃への対策方法

レインボーテーブル攻撃によるハッシュ値の解読を防ぐには、どうすればよいのでしょうか。

ソルト処理を行う

ソルト処理とは、平文に余分な文字列を付加することです。付加する文字列をソルトと呼びます。この処理を施してからハッシュ化することで解読が困難になります。

たとえば、あるユーザーがログインパスワードを「リンゴ」に設定しているとしましょう。これをハッシュ化すると「a2f4」になります。この「a2f4」を第三者に取得されると、レインボーテーブルで平文が「リンゴ」だと特定されます。

そして、一度特定してしまえばハッシュ値「a2f4」のユーザーは全員パスワードが「リンゴ」であると判明してしまうのです。

しかし、「リンゴ」にソルトを付けて「リンゴabcd」などとしてハッシュ化すれば、解読が難しくなります。また、ユーザーごとにソルトを変えれば、仮に同じパスワードを使っていても、攻撃者はその都度解読せねばなりません。

ストレッチングを実施する

ソルト処理は多数のユーザーを被害から守る点では有効です。しかし、特定のユーザーに対する攻撃にはあまり意味がありません。ソルトを付けた「リンゴabcd」が割り出されれば、攻撃者がそこから「リンゴ」にたどりつくのは難しくないでしょう。

そのような被害を防ぐのに有効なのがストレッチングです。ストレッチングとは、保護したい平文に繰り返しハッシュ化を行うことです。

レインボーテーブル攻撃は１回のハッシュ化を解読するだけでも大きな時間がかかります。そのため、ハッシュ化を複数回繰り返したものは現実的な時間では解読不可能です。たとえば、ハッシュ化を数万回繰り返せば、解読に必要な時間は数十年にも及びます。

ただし、ハッシュ化すればするほどサーバに負荷がかかります。充分な安全性を確保できる範囲で、サーバの負荷を抑えられるように調節が必要です。

レインボーテーブルを理解してセキュリティ強度を上げよう！

レインボーテーブルとは、ハッシュ値と平文の対応表です。取り出せるデータ量は膨大ですが、ハッシュ関数と還元関数を使うことで使用容量を抑えられ、必要に応じて復元して使われます。レインボーテーブル攻撃への対策として有効なのは以下の２つです。

ソルト処理

平文にソルトを付加してからハッシュ化

ストレッチング

ハッシュ化を繰り返す

以上を踏まえて、自社のセキュリティ強度を高めましょう。