コラム

2018.08.10

4枚の図解でわかるレインボーテーブル攻撃

ECサイトなどの会員サイトでは、アカウント名とパスワードの組み合わせで本人確認をしてログインをします。サイト運営側では、このパスワードを一定の方式で変換をするハッシュ関数(後述)を使って保存しています。

ハッシュ関数を使ってハッシュ値として保存しておけば、そこから元のパスワードを推測するのは、ほとんど不可能です。しかし、このレインボーテーブルを使うと、ノートPC程度の計算能力、メモリ空間でハッシュ化されたパスワードを復元できてしまうのです。

1.ハッシュ関数とは

ハッシュ関数は、一方向関数、要約関数などと呼ばれることもあります。ハッシュとは、ごちゃ混ぜにするという意味です。ジャガイモを細切りにして、パンケーキミックスで和えて焼いたものはハッシュドポテトですね。

ハッシュ関数にはさまざまなアルゴリズムが考案されていますが、最も有名なmd5を使って、「persol」という単語を変換してみると「c4c0ac673fd8010a257753cc2c7922cc」となります。また、先頭を大文字にした「Persol」を変換してみると「e453f5acbd718a36eaf46b5a04e647d6」となります。先頭のpが大文字か小文字かの違いしかないのに、出力値はがらりと変わります。

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

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

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

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

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

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

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

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

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

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

と言っても、今時「password」「abcdefg」「qwerty」などという単純すぎるパスワードは使っている人はいないと思うので(いませんよね?)、本当にハッキングするのであれば、大量のハッシュ値一覧表を作っておく必要があります。

8文字のパスワードで大文字、小文字、数字、記号の合計64種類が利用できるとすると、すべての組み合わせは64^8=281兆という膨大な数になります。これが256バイト長さのハッシュ値に変換されるとすると、256バイト×281兆=約6700万テラバイト(64エクサバイト)もある一覧表を作らなければなりません。私の使っているHDDは2テラバイトのものなので、3350万台必要だということになります。とても現実的ではありません。

そこで、この保存領域を節約するというのが、レインボーテーブル攻撃の基本的発想です。具体的な方法は後でご紹介するとして、同じ8文字パスワードを攻撃するのに、レインボーテーブルなら、なんと約256メガバイトの一覧表で済んでしまうのです。この中に、8文字パスワードのハッシュ値リストがすべて入ってしまう。これがレインボーテーブルです。

3.ハッシュ値から元の平文を復元は出来ない ――還元関数の果たす役目――

このレインボーテーブルを作るのに、重要なのが還元関数(Reduction Function)です。

これはハッシュ値を平文に変換する関数です。といっても、ハッシュ値「dbf164c4」を元の「abc123」に戻す関数は作れません。還元関数は、元のパスワードリストのどれかにマッピングできればいいのです。どのパスワードに対応させるか、関連性を考えることはなく、とにかくどれかのパスワードに対応づけられます。

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

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

この不思議な関数とチェインに首をかしげる人も多いかと思います。でも、これがレインボーテーブルの考え方のキモになります。今は、ちょっと違和感があっても、還元関数が必要なのだと納得してください。あとでその必要性がすっきりと理解できます。

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

1000のワードを起点として、それぞれが1000回のハッシュ変換→還元関数による変換を繰り返すと、1000回×1000行(チェイン)で100万個のパスワードとハッシュ値のペアを含むテーブルが完成します。

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

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

そんな大胆なことをしていいのでしょうか。いいのです。あとから必要な部分だけを簡単に復元できるからです。Kyotoの行を復元したければ、ハッシュ関数、復元関数と次々に計算していけば、この行だけ簡単に復元できます。ですから、途中はすべて削除してしまってもいいのです。こうなると、メモリ空間は、8バイト×1000×2=16000バイト=約15.6Kバイトで住むことになります。わずか0.006%のサイズになってしまいました。

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

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

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

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

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

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

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

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

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

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

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

しかし、アルゴリズムとしては極めて面白く、パスワードのハッシュ化に対する理解も深まることから、学生や新人エンジニアは理解をして、簡単なコードを書いてみるぐらいのことは無駄にならないどころか、セキュリティエンジニアリングをより深く理解する助けになることは間違いありません。時間のあるときに、簡単なコーディングをしてみると、より理解しやすくなると思います。

記事一覧に戻る