レインボーテーブルとレインボー攻撃

　あまり聞き慣れない用語かもしれませんが，パスワード破りの手法にはレインボー攻撃と呼ばれるやり方もあります。レインボー攻撃は，レインボー・テーブルと呼ばれる情報を基に，ハッシュ化されたパスワードを解析する手法です。

　この連載のハッシュ値の回で，『パスワードを保存する時に，パスワードそのものを保存しておくのではなく，パスワードのハッシュ値と，それが誰のものであるかという情報をシステムに保存しておいて認証する』という手法を勉強しました。これは，『ハッシュ値とハッシュ関数がわかっても，基のデータを算出できない』という特徴（一方向性）を生かした使い方です。この特徴により，攻撃者がハッシュ化されたパスワードとハッシュ関数（ハッシュ・アルゴリズム）を入手できても，パスワードが解読されにくくできるわけです。この条件のもとで，パスワード破りを考えてみます。

　もちろんハッシュ関数のアルゴリズムとハッシュ値からパスワードを解読するのは，困難です（図4）。

図4●ハッシュ関数（のアルゴリズム）とハッシュ値がわかってもパスワードを推測するのは困難

　そこで，「逆」に攻撃を仕掛けます。適当な文字列（パスワード）を作り，これに一つ一つハッシュ関数をかけて出てきたハッシュ値と同一なものがないかを試すのです（図5）。

図5●適当な文字列をハッシュ関数に通してハッシュ値を作り，パスワード・ファイル中のハッシュ値と一致するか調べる

　ただし，このやり方だと計算量が膨大になってしまい時間がかかります。そこで，あらかじめパスワードとなる文字列のハッシュ値を計算してテーブルを作っておきます。このテーブルがレインボー・テーブルです（図6）。

図6●あらかじめ文字列の組み合わせ（パスワード）に対するハッシュ値のテーブル（レインボー・テーブル）を作っておく

　そしてレインボー攻撃は，ターゲットとなるパスワードのハッシュ値をレインボー・テーブル中から検索してパスワードを推測します。このため，ハッシュ化されたパスワードを高速に解読することができます（図7）。

図7●レインボー攻撃は，既に計算済みのハッシュ値のテーブル（レインボー・テーブル）の中から該当するハッシュ値を検索する

　例えば，レインボー攻撃でWindowsアカウントのパスワード破りをするophcrackというツールがあります。実際に筆者のパソコンに，ユーザー名：bpuser，パスワード：bpuserというアカウントを作り，解読を試みました。このような単純で短いパスワードだと1分程度で解読できました（図8）。

図8●ophcrackの画面。ユーザー名：bpuser，パスワード：bpuserのように単純なものだと1分程度で解読できた

　パスワードを登録する機会は数多くあります。一般に，安全な（破られにくい）パスワードは覚えにくいため，妥協して覚えやすい安易なものを利用してしまいがちです。しかし，今回見て頂いた通り，パスワード破りは誰にでもできる身近な攻撃手法です。パスワードをかける情報の機密度にもよりますが，もしも自分がターゲットになってしまった場合でも極力被害を被らないようにするために，どのようにパスワードを作ればよいか，という点を改めて確認しておきましょう。