レインボーテーブルとは
レインボーテーブルとは平文とハッシュ値の対応表であり、ハッシュ値を検索して対応する平文を探す手法として活用されます。ハッシュ関数と還元関数を活用し、ハッシュ値の解析が可能です。不正入手したパスワードなどのハッシュ値を解析するレインボーテーブル攻撃に活用されることもあります。
ここでは、レインボーテーブルの概要について詳しく解説します。
ハッシュ値を平文に戻せる
ハッシュ値は平文を不可逆的に変換したものです。この変換をハッシュ化といいます。後に復号することを想定した暗号化とは異なり、ハッシュ値から元の平文に復号することはできません。
しかし、レインボーテーブルを使えばハッシュ値から元文を割り出せる場合があります。
例えば、「リンゴ」のハッシュ値が「a2f4」だとしましょう。この平文とハッシュ値の間には数学的関連性がないため、暗号化のようなアルゴリズムによる復号は不可能です。しかし、レインボーテーブルから「a2f4」を探せば、対応する平文が「リンゴ」だとわかります。
このことから、レインボーテーブルはハッシュ化によって秘匿された情報を不正に取得する攻撃手段として使われます。
ハッシュ関数と還元関数が使われる
レインボーテーブルでは、ハッシュ関数と還元関数という２種類の関数が用いられます。それぞれの関数について詳しく解説します。
ハッシュ関数
ハッシュ関数とは、平文をハッシュ化するための関数です。前述の例でいえば、「リンゴ」を「a2f4」に変換するのがハッシュ関数です。不可逆的な変換を担うことから、一方向関数や要約関数とも呼ばれます。
一口にハッシュ関数といっても、いくつかのアルゴリズムが存在します。平文が同じ「リンゴ」でも、どのようなハッシュ値になるかはハッシュ関数のアルゴリズム次第です。しかし、アルゴリズムと平文が同じであれば、得られる結果は常に同じになります。
還元関数
還元関数とは、ハッシュ値から平文を得る関数です。ただし、ハッシュ化の変換をそのまま逆に行うのは不可能であり、例のハッシュ値「a2f4」からハッシュ化前の平文「リンゴ」を得る関数は作れません。
還元関数の役割は、ハッシュ値をパスワードなどの条件を満たす平文候補のどれかに対応づけることです。「a2f4」の本当の平文は「リンゴ」ですが、還元関数ではそのことは気にせず別の平文と結び付けます。
一見無意味な操作ですが、還元関数は次の項で解説するチェインの作成に役立ちます。
レインボーテーブル攻撃の仕組み
レインボーテーブル攻撃（レインボー攻撃）とは、レインボーテーブルを利用して不正にハッシュ化内容を解読するサイバー攻撃です。レインボーテーブル攻撃はチェイン化と復元の２つの手順があります。それぞれの仕組みを見ていきましょう。
１．チェインを作成する
ハッシュ関数と還元関数を使い、以下のような手順で平文とハッシュ値のチェインを作成します。
- １．平文「リンゴ」にハッシュ関数を使い、ハッシュ値「a2f4」を得る
- ２．ハッシュ値「a2f4」に還元関数を使い、平文「ミカン」を得る
- ３．手順１と２を一定の回数繰り返し「リンゴ-a2f4-ミカン-bf55-…イチゴ」というチェインを作る
上記の例では「リンゴ」のハッシュ値「a2f4」から還元関数で、別の平文「ミカン」を得るのがポイントです。
これによりランダムに多種の平文がテーブルに加わることになります。還元関数は、手順１と２の繰り返しごとに変更します。たまたま同じ平文が出現した場合に、以後のデータがすべて重複してしまう事態を避けるためです。
異なる平文からスタートして同様な手順で複数のチェインを作ります。これらのチェインを並べたものがレインボーテーブルです。各チェインの同じ列では共通の還元関数を使っていることになります。
しかし、このままではデータの量が多すぎるため、膨大なメモリが必要です。そこで、各チェインの先頭と末尾だけを残し、それ以外の部分は削除します。上記の例でいえば、チェインは「リンゴ-イチゴ」の状態になります。
２．還元関数を使って復元する
レインボーテーブルは、複数のチェインの先頭と末尾だけが並び、下記のような状態になっています。
- リンゴ-イチゴ
- サクラ-スミレ
- ・
- ・
- トマト-パセリ
関数を使って計算すれば、先頭と末尾以外の部分を復元できます。これを活用し、ハッシュ値から元の平文を求める手順は以下のとおりです。
- １．対象のハッシュ値に、チェインの末尾の列を得た還元関数を適用する。
- ２．得られた平文と同一のものがないか各チェインの末尾を調べる。
- ３．ない場合は末尾の一つ前に使った還元関数を、対象のハッシュ値に適用する。得られた平文のハッシュ値を求め、このハッシュ値に末尾の列に使った還元関数を適用して平文を得る。
この平文で２．の照合を行う。いずれかのチェインの末尾に一致する平文が得られるまで、開始列をさかのぼり繰り返す。 - ４．一致する末尾をもつチェインが見つかれば、そのチェインを復元する。チェイン内にある対象のハッシュ値の、直前の平文が求める元文になる。
例えば、手順１で得た平文が「スミレ」だった場合に、手順２で末尾に「スミレ」が見つかったとします。このとき、そのチェインを復元すれば、「スミレ」の一つ手前にあるハッシュ値と解読対象のハッシュ値は同一です。
さらにその手前の平文が、求めたい元文になります。末尾の列に一致する平文がない場合は、列をさかのぼってチェックするわけですが、テーブルには先頭と末尾しかありません。そこで、もしチェックしたい列に対象のハッシュ値があるとしたら、チェインの末尾が何になるかを計算して一致を調べます。
以下の記事では、暗号化で活用される「平文」について詳しく解説しています。暗号化の仕組みについて理解を深めたい方は、あわせて参考にしてください。
レインボーテーブル攻撃への対策方法
レインボーテーブル攻撃によるハッシュ値の解読を防ぐ方法は、「ソルト処理」と「ストレッチング」の２つです。それぞれの対策方法について詳しく解説します。
ソルト処理を行う
ソルト処理とは、平文に余分な文字列を付加してからハッシュ化することで、解読を困難にする手法です。付加する文字列をソルトと呼びます。
例えば、あるユーザーがログインパスワードを「リンゴ」に設定しているとしましょう。これをハッシュ化すると「a2f4」になります。この「a2f4」を第三者に取得されると、レインボーテーブルで平文が「リンゴ」だと特定され、ハッシュ値「a2f4」のユーザーは全員パスワードが「リンゴ」であると判明してしまうのです。
しかし、「リンゴ」にソルトを付けて「リンゴabcd」などとしてハッシュ化すれば、解読が難しくなります。また、ユーザーごとにソルトを変えれば、仮に同じパスワードを使っていても、攻撃者はその都度解読が必要です。
以下の記事では、ソルト処理についてより詳しく解説しています。セキュリティ対策としてソルト処理の導入を検討したい方は、あわせてご覧ください。
ストレッチングを実施する
ソルト処理は多数のユーザーを被害から守る点では有効です。しかし、特定のユーザーに対する攻撃にはあまり意味がありません。ソルトを付けた「リンゴabcd」が割り出されれば、攻撃者がそこから「リンゴ」にたどりつくのは難しくないでしょう。
そのような被害を防ぐのに有効なのがストレッチングです。ストレッチングとは、保護したい平文に繰り返しハッシュ化を行うことです。
レインボーテーブル攻撃は１回のハッシュ化を解読するだけでも大きな時間がかかります。そのため、ハッシュ化を複数回繰り返したものは現実的な時間では解読不可能です。例えば、ハッシュ化を数万回繰り返せば、解読に必要な時間は数十年にも及びます。
ただし、ハッシュ化すればするほどサーバに負荷がかかるため、充分な安全性を確保できる範囲でサーバの負荷を抑えられるように調節が必要です。
レインボーテーブルを理解してセキュリティ強度を上げよう
レインボーテーブルで取り出せるデータ量は膨大ですが、ハッシュ関数と還元関数を使うことで使用容量を抑えられ、必要に応じて復元して使用できます。しかし、レインボーテーブル攻撃によって自社の情報を不正に解読される場合もあるため、適切なセキュリティ対策を行いましょう。
ITトレンドでは、レインボーテーブル攻撃対策のほか、企業の情報セキュリティ強化に有効な暗号化ソフトを多数紹介しています。以下のボタンから各社製品の資料請求も可能なので、自社のセキュリティ対策を強化したい方はぜひご活用ください。
