2020年11月26日 08時00分ソフトウェア

パスワード解析などに使われる「レインボーテーブル」の仕組みとは？

パスワードやアクセスキーなどの重要なデータは「ハッシュ関数」で一方向の変換を行うことで、漏えいの被害を最小限に抑えることができます。しかし、パスワードとハッシュ値の組み合わせを記録したレインボーテーブルによって、ハッシュ値からパスワードを解析される攻撃を受ける危険性もあります。そんなレインボーテーブルの仕組みについて、ソフトウェアエンジニアのKestas "Chris" Kuliukas氏が図解しています。

How Rainbow Tables work
http://kestas.kuliukas.com/RainbowTables/

ハッシュ関数は文字列を別の文字列に変換することができる関数で、変換前の文字列から変換後の文字列を計算することはできますが、変換後の文字列から変換前の文字列を計算することはできません。変換前の文字列は「平文(Plaintexts)」、変換後の文字列は「ハッシュ値(Hashes)」と呼ばれ、パスワードやアクセスキーなどをハッシュ関数で平文からハッシュ値に変換しておけば、仮にハッシュ値だけが漏えいしても平文の元データを復元できないようにすることができるというわけです。

しかし、ひとつのハッシュ関数による平文からハッシュ値への変換結果は常に同じであるため、「平文とハッシュ値の組み合わせ」を知っていれば、ハッシュ値から平文を「還元する」ことは可能。この性質を利用したのが平文とハッシュ値の組み合わせを記録した「レインボーテーブル」で、ハッシュ値を照会することで組み合わせが記録された平文を導き出すことができます。

発想自体は単純なレインボーテーブルですが、膨大な種類の組み合わせをすべて記録するとデータ容量が大きくなりすぎてしまうとKuliukas氏。この問題を解決するためにレインボーテーブルに組み込まれているのが「還元関数」です。還元関数はハッシュ値を平文に変換できる関数ですが、ハッシュ値から変換前の平文を計算できるわけではなく、あくまでも「ハッシュ値から変換前の平文とは別の平文」を生成する関数である点には注意が必要。

レインボーテーブルでは、ハッシュ関数と還元関数を使って、平文をハッシュ値に、そのハッシュ値を平文に、さらにその平文をハッシュ値に、といった操作を繰り返し、大量の平文とハッシュ値の組み合わせをひとつのチェーンとして生成するとのこと。最終的に記録されるのは、チェーンにおける最初の平文と最後のハッシュ値のみであるとKuliukas氏は説明しています。

レインボーテーブルによるハッシュ値から平文への還元方法は以下。まずは入手したハッシュ値をチェーン最後尾のハッシュ値と比較。一致した場合はそのチェーンを復元し、チェーン最後尾のハッシュ値に対応する平文が、目的の平文となります。

先ほどの手順でハッシュ値が一致しなかった場合は、入手したハッシュ値を還元関数で平文に還元した後、ハッシュ関数でハッシュ値を計算。計算したハッシュ値をチェーン最後尾のハッシュ値と比較します。つまり、チェーンの「最後尾からひとつ前のハッシュ値」に入手したハッシュ値が含まれていると仮定して、チェーン生成時の処理を途中から行っているというわけです。

こんな感じでチェーンをさかのぼるように入手したハッシュ値に処理を加えていき、その都度チェーン最後尾のハッシュ値と比較。最後尾のハッシュ値と処理後のハッシュ値が一致するまで繰り返していきます。

どこかの段階で最後尾のハッシュ値と処理後のハッシュ値が一致した場合、そのチェーンには入手したハッシュ値が含まれているとKuliukas氏は説明。チェーンを復元すれば目的の平文を導き出すことができます。レインボーテーブルはこのようにして、データ量を削減しつつ膨大な組み合わせ数に対応しています。

レインボーテーブルの弱点は、別の値から同じ計算結果を導き出してしまう「衝突」であるとのこと。2つのチェーンが衝突した場合、その後はまったく同じ値しか生成されなくなってしまうため、保存できる情報量が減少してしまいます。レインボーテーブルでは衝突を避けるため、還元関数を段階ごとに変更しているとKuliukas氏は説明しています。