レインボーテーブル攻撃とは？ハッシュ関数や攻撃方法まで徹底解説！

レインボーテーブルとは

レインボーテーブルとはハッシュ関数によりハッシュ化された元のデータ（平文）を導きだすための手法のことです。レインボーテーブルは不正入手したハッシュ値（パスワード）の解析などに利用されています。レインボーテーブルには「ハッシュ関数」と「還元関数」の2つの関数が用いられます。

ハッシュ関数とは

ハッシュ関数とは入力データを一定の手順で計算し、入力値のデータの長さに関係なく決まった長さの文字列を出力する関数のことです。一方向関数、要約関数などと呼ばれることもあります。ハッシュとは、ごちゃ混ぜにするという意味です。ハッシュ関数で得られたデータを「ハッシュ値」と呼び、ハッシュ関数にはMD5 、SHA-1、SHA-2などさまざまな関数が存在します。

例えば、最も有名なmd5を使って、「persol」という単語を変換してみると「c4c0ac673fd8010a257753cc2c7922cc」となります。また、先頭を大文字にした「Persol」を変換してみると「e453f5acbd718a36eaf46b5a04e647d6」となります。先頭のpが大文字か小文字かの違いしかないのに、出力値はがらりと変わります。

また、この出力値から元のpersolやPersolを演算で求めるのはものすごく大きな計算コストが必要になり、非現実的だと言ってもいいでしょう。このため一方向関数などとも呼ばれるのです。

このハッシュ関数を使うと、安全にパスワード保存ができるようになります。ハッシュ関数は目的に応じて、出力値が256文字にするもの、512文字にするものなどさまざまありますが、わかりやすくするため、出力値が短いcrc32（セキュリティは弱く、実際のパスワード保存には不向きです）というハッシュ関数を使って説明を進めます。

先ず、新規登録した会員にパスワードを自分で決めてもらいます。これがabc123だったとし、サイト側では、これをハッシュ関数で変換した「dbf164c4」を保存します。

このユーザーがアクセスしてくるとパスワードを入力します。その入力値をハッシュ関数で変換し、それが保存してあるハッシュ値と同じであるかどうかを確認します。一致すれば正しいパスワードを入力したということになるのです。

保存しているパスワードリストはすべてハッシュ値のみですから、万が一流出をしても、ハッシュ値からパスワードを復元することはできません。内部の人間もわかるのはハッシュ値のみで、元のパスワードが何であるかはわかりません。

還元関数とは

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

ハッシュ化されたパスワードをクラックする方法

還元関数があることでハッシュ関数を使った方法も完璧に安全というわけにはいきません。また、攻撃する簡単な方法があります。それは、使っているハッシュ関数がわかっているのであれば、あらかじめ主だったパスワードがハッシュ関数でどのように変換されるかの一覧表を作っておき、ハッキングして手に入れたハッシュ関数を検索してみればいいのです。

全員のパスワードを解析することはできませんが、ありがちな脆弱パスワード「password」「abc123」「admin」「qwerty」「iloveyou」などのハッシュ値一覧表を作って検索してみれば、ハッシュ値リストの中からきっと見つかることでしょう。

ダークサイドハッカーの目的は、アカウントの乗っ取りであることが多いので、誰のアカウントでもかまいません。じゅうぶん、目的は果たせます。

ハッシュ関数がわかっていれば、弱いパスワード「abc123」がどのようなハッシュ値（dbf164c4)になるかは簡単に計算ができる。入手したハッシュ化されたパスワードリストからハッシュ値「dbf164c4」を検索し、ヒットすれば、その人（ここではBetty）のパスワードが「abc123」であることがわかる。

とは言っても今時、単純なパスワードを使っている人はあまりいないのではないでしょうか。そこで、この保存領域を節約するというのが、レインボーテーブル攻撃の基本的発想です。

レインボーテーブルにおける還元関数の役目

レインボーテーブルを作成するのに重要なのが先述した還元関数です。

還元関数は、ハッシュ値を元にパスワードリストのどれかに対応させる関数。

今、「Tokyo」というパスワードはハッシュ関数によってハッシュ値「5a62c」に変換されたとして、このハッシュ値「5a62c」を還元関数によって、パスワードリストのうちのどれかに対応づけます。仮に「Beijing」に対応づけられたとします。さらに「Beijing」はハッシュ関数を使って「6ge2f」に変換され、このハッシュ値を還元関数で「London」に対応づけるということを延々繰り返して、ひとつのチェインを作成します。これをレインボーテーブルの一行に相当するものとします。

レインボーテーブルの中身

それではレインボーテーブルの中身はどのようになっているのか説明していきます。例えば1000のワードを起点として、それぞれが1000回のハッシュ変換→還元関数による変換を繰り返すと、1000回×1000行（チェイン）で100万個のパスワードとハッシュ値のペアを含むテーブルが完成します。

レインボーテーブルでは、ハッシュ関数はいつも同じものを使う。還元関数は列によってR1からR_nまで別々のものを用いる必要がある。この表の中には、無数の「パスワードとハッシュ値」のペアが含まれている。

わざわざこのようなテーブルを作るのは、メモリ空間を節約するためです。実はこのレインボーテーブル、最初の列と最後の列だけを残して、途中を全て捨ててしまうことができるのです。図で言えば、いちばん左の「Tokyo、Kyoto…」と最後の「Paris、Seoul…」の列だけを残し、途中のパスワードやハッシュ値はすべて捨ててしまいます。

なぜこんなことが可能かというと、あとから必要な部分だけを簡単に復元できるからです。Kyotoの行を復元したければ、ハッシュ関数、復元関数と次々に計算していけば、この行だけ簡単に復元できます。ですから、途中はすべて削除してしまってもいいのです。

レインボーテーブルを使った攻撃

では、実際にこのレインボーテーブルを使った攻撃を見てみましょう。

レインボーテーブルの攻撃の手順は、攻撃対象のサイトから入手したハッシュ値が、レインボーテーブルの最後のハッシュ値のいずれかではないかと仮定して検索します。それがうまくいかない場合は、最後列の1つ前の列のハッシュ値ではないかと仮定するように、後ろから前に探索していきます。

しかし、ハッシュ値はすべて削除してしまっています。そこで、入手したハッシュ値に最後に使った還元関数Rnを使います。もし「最後列のハッシュ値のどれかと同じ」という仮定が合っているのであれば、「Rn（入手したハッシュ値）」の結果から導かれる平文は、レインボーテーブルの最後尾のパスワードのいずれかと一致するはずです。

2回目の攻撃で、Liverpoolがレインボーテーブルの中から見つかった。ということは、このLiverpoolの行に、入手したハッシュ値とパスワードが含まれていることになる。このLiverpoolの行だけを復元してみると、入手したハッシュ値の前に「Beijing」が現れる。つまり、入手した値はBeijingから生成されたハッシュ値であり、目的のパスワードは「Beijing」であることがわかる。

今、攻撃対象から入手したハッシュ値を最後に使った還元関数を適用すると、Hanoiになります。

レインボーテーブルの最後尾のパスワードの中から、Hanoiを検索しますが見つかりません。つまり、「最後列のハッシュ値と同じ」という仮定が間違っていたことになります。

次に、最後列のひとつ前のハッシュ値ではないかと仮定します。入手したハッシュ値に、今度は還元関数Rn-1を適用するとFukuokaになりました。このFukuokaにハッシュ関数を提供し、さらに還元関数Rnを適用してみると、最後尾がLiverpoolになりました。これはレインボーテーブル側の最後尾のパスワード群と照合すべく、チェインを再現しているのです。

このLiverpoolという平文が、レインボーテーブル側の、あるチェインの最後尾に見つかりました。ということは、目的のハッシュ値、パスワードともにこのチェインの中にあるはずです。

最後尾がLiverpoolであるチェインの先頭はBeijingです。Beijingから出発して、ハッシュ関数と還元関数を適用して、このチェインだけを復元します。すると、攻撃対象から入手したハッシュ値が出てくるので、その前のパスワードが目的のパスワードだということがわかります。

まとめ

今回はレインボーテーブル攻撃についてご紹介しました。しかし、レインボーテーブル攻撃が使われることは実際にはほとんどありません。なぜなら、「ハッシュ関数を多重化する」「ソルト（パスワードにキーワードを追加してからハッシュ関数にかける）」という方法で、レインボーテーブル攻撃を予防できるからです。

しかしこのアルゴリズムを理解することは、セキュリティエンジニアリングをより理解するためにも重要なことだと思います。本記事を読んで少しでも興味を持っていただけたら幸いです。