無料セキュリティ対策に不安がある企業必見！「セキュリティ対策無料相談窓口」

通販サイトやクラウドサービスなど、多くのWebサイトはユーザーのIDとパスワードを使用しています。事業者がパスワードをサーバーに保管する際は、ハッシュ化によりセキュリティ対策を行う形が一般的です。そこで注意すべき攻撃が、ハッシュ化したデータからパスワードを割り出す「レインボーテーブル攻撃」です。この記事では、レインボーテーブル攻撃の仕組みと対策について解説します。

レインボーテーブルとは

レインボーテーブルとは、ハッシュ関数によって生成された「ハッシュ値」から、平文（元のデータ）を解読する手法です。ハッシュ値とは、平文を変換した無関係な文字列を意味します。レインボーテーブルの手法そのものは、不正行為ではありません。ですが、不正取得したハッシュ値からパスワードを割り出すために用いる事例が多い点から、「レインボーテーブル攻撃」と呼ばれます。

使われる関数

レインボーテーブルを構築する際の関数は、「ハッシュ関数」と「還元関数」の2種類を使用します。それぞれの役割を説明します。

ハッシュ関数

多くのWebサービスは、ユーザーのパスワードをハッシュ化してサーバーで保管しています。ハッシュ化とは、入力された平文を一定の長さの文字列に変換する作業です。ハッシュ化する際に用いるものが「ハッシュ関数」であり、ハッシュ化されたデータを「ハッシュ値」と言います。ハッシュ関数には、MD5やSHA-1などのアルゴリズムがあります。

たとえば、平文の入力値「sample」のMD5によるハッシュ値は「5e8ff9bf55ba3508199d22e984129be6」です。同じ平文とアルゴリズムであれば、全く同じハッシュ値が出力されます。反対に、平文が一文字でも違えば、全く異なるハッシュ値になる仕組みです。ハッシュ値から元の平文を逆算するのは非常に困難であるため、多くの事業者はパスワード管理にハッシュ関数を利用しています。

還元関数

還元関数とは、ハッシュ値から平文を生成する関数です。ただし、還元関数で得られる平文は、元のハッシュ値と対応する正しい文字列ではありません。つまり、「sample」のハッシュ値「5e8f〜」を還元関数にかけても、元の平文「sample」は導き出されないわけです。平文候補となる他の文字列と紐づけ、元の正しい平文を割り出すために利用します。

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

レインボーテーブル攻撃の仕組みを次の4つに分けて説明します。

1. チェインの作成
2. レインボーテーブルの構築
3. 平文の比較・特定
4. 末尾が一致するまで繰り返す

順番に確認しましょう。

1.チェインの作成

まず、攻撃者はレインボーテーブルの基礎となる「チェイン」を作成します。レインボーテーブルを構築するためには、最初にチェインと呼ばれる平文とハッシュ値の繰り返し処理を作成しなければいけません。ここでは、平文「システム」を例に手順を見てみましょう。

1. 平文「システム」にハッシュ関数をかけてハッシュ値「XXX」を出力
2. ハッシュ値「XXX」に還元関数Aをかけて平文「アカウント」を出力
3. 「アカウント」からハッシュ値「YYY」を出力
4. 還元関数Bを使い、「YYYY」から平文「ユーザー」を出力
5. 手順1〜4を一定回数繰り返し、チェイン「システム→XXX→アカウント→YYY→…セキュリティ」を構築

このように、平文→ハッシュ値→平文の連鎖を一定回数繰り返します。なお、還元関数は同じものは使わず、毎回異なる還元関数を使用します。

なお、チェインに使う平文を用意するのは攻撃者自身です。自身で用意したさまざまな平文に対し、ハッシュ関数をかけることでチェインを作成するわけです。

2.レインボーテーブルの構築

チェインは、1つの平文につき1つ作成します。レインボーテーブルは、いくつもの平文のチェインによって構成されています。ただし、レインボーテーブルに記録するのは、チェインの先頭と末尾のデータのみです。前項の例でいえば、「システム-セキュリティ」のみ記録します。

チェインの全情報を記録すると膨大な記憶領域が必要になるため、途中のデータは削除します。また、削除したデータは復元可能です。ハッシュ関数と還元関数によって簡単に削除前のデータを得られるため、記録する必要がありません。

3.平文の比較・特定

攻撃者は、不正入手したハッシュ値をもとに、以下の手順で平文を特定します。

1. チェイン末尾の平文を出力した還元関数を、不正入手したハッシュ値にかける
2. 得られた平文が、各チェイン末尾の平文と合致するか比較する
3. 一致する場合、チェインを復元する。末尾の1つ手前の平文が、目的の平文となる

例として、手順2で一致した平文を「セキュリティ」と仮定します。このチェインを復元すると、末尾「セキュリティ」の手前にあるハッシュ値「ZZZ」と、入手したハッシュ値は合致しています。したがって、ハッシュ値「ZZZ」の手前にある平文が、目的の平文（＝パスワード）になるわけです。

4.末尾が一致するまで繰り返す

前項の手順2で合致する平文がない場合、以下の手順で復元するチェインを絞り込みます。

1. 末尾の1つ前の平文に使った還元関数を、不正入手したハッシュ値にかけて平文を得る
2. 得られた平文にハッシュ関数をかけ、ハッシュ値を出力する
3. 出力したハッシュ値に、末尾の平文を出力した還元関数をかける
4. 得られた平文が、各チェインの末尾と合致するか比較する（合致する末尾が現れるまで先頭に遡っていく）
5. 末尾が合致したチェインを復元する

上記手順の通り、末尾の平文が合致するチェインが見つかると、攻撃者はチェインを復元します。その結果、復元したチェインから、攻撃者は不正にパスワードを入手できてしまうわけです。

レインボーテーブル攻撃を防ぐための対策

レインボーテーブル攻撃の予防策として、以下2つの方法が効果的です。

1. 平文に文字列を付与する【ソルト処理】
2. 繰り返しハッシュ化を行う【ストレッチング】

具体的な内容を見てみましょう。

1.平文に文字列を付与する【ソルト処理】

1つ目の方法が、ソルト処理です。ソルト処理とは、不規則かつ複雑な文字列「ソルト」を平文に付与する作業を意味します。ソルト処理を施した平文をハッシュ化することで、レインボーテーブル対策が可能です。

たとえば、パスワード「sample」にソルトを付加すると、「sample1kf8dhal」のようになります。ハッシュ値のセキュリティ強度が増すため、レインボーテーブルを使った解読を防ぎやすくなります。

2.繰り返しハッシュ化を行う【ストレッチング】

2つ目の方法は、ストレッチングです。ストレッチングとは、平文を何度もハッシュ化する処理を指します。ソルト処理は有効な手段ではあるものの、時間をかければ元のパスワードを割り出せる可能性がゼロではありません。

そこで、ストレッチングで数千回以上ハッシュ化を繰り返せば、元のパスワードを逆算するのに途方もない時間が必要になります。関数を悪用したパスワード解析が非現実的になるため、レインボーテーブル攻撃対策として効果的です。

まとめ

レインボーテーブル攻撃を受けると、ハッシュ値によって保護しているパスワードが割り出される恐れがあります。多くのWebサービスの提供企業は、ソルト処理やストレッチングによってレインボーテーブル対策を実施しています。しかし、対策が不十分な可能性もあるため、ユーザー側の対策も重要です。パスワードを設定する際は、単純な単語の組み合わせはできる限り控えましょう。企業・ユーザーともに基本的なパスワードセキュリティを施して、レインボーテーブル攻撃に備えることが大切です。