TL;DR
VALU Advent Calendar 2019の10日目の記事です。
パスワードとハッシュの関係
一般的なサービスにおいて、パスワードは平文で保存されるのではなく、ハッシュ関数によってハッシュ化されて保存されます。ハッシュ関数は一方向性関数であり、復号化は通常の方法ではできない仕様です。
ユーザーがパスワードを入力するたびに、パスワードはハッシュ値に変換され、すでに格納されているハッシュ値と比較されます。値が一致する場合、ユーザーは認証されます。これが一般的な現代のパスワードの保存方法です。
Rainbow Table とは
Rainbow Tableは、パスワードのハッシュ値を解読してパスワードを取得するために使用されるデータベースです。これは、平文のパスワードとそれに対応するハッシュ値からなる、あらかじめ計算された辞書で、どの平文のパスワードが特定のハッシュ値を生成するかを調べるために使うことができます。
Rainbow Table の作り方
単純に平文とそのハッシュ値の対応表を作っていては、莫大な記憶領域が必要になってしまい、とても使えるようなものではなくなってしまいます。
そこで平文とハッシュ値による「チェイン化」という手法を用います。
チェイン化
ここであるハッシュ関数$H()$と、適当な平文を出力する還元関数$R()$について考えます。
1 . まず、ある平文$P_i$に対して、ハッシュ関数を用いて、ハッシュ値$C_i$を生成します。
2 . 1で生成されたハッシュに対して、還元関数を用いて、平文$P_{i+1}$を生成します。
3 . 2で生成された平文に対し、またハッシュ関数を用いて、ハッシュ値$C_{i+1}$を生成します。
4 . これを任意の回数$m$回繰り返します。
5 . m回繰り返した一連のものを「チェイン」と呼び、その集まりを「テーブル」と呼びます。
\begin{bmatrix}
P_i & C_i & P_{i+1} & C_{i+1} & P_{i+2} & \cdots & C_{i+m-1}\\
P_j & C_j & P_{j+1} & C_{j+1} & P_{j+2} & \cdots & C_{j+m-1}\\
P_k & C_k & P_{k+1} & C_{k+1} & P_{k+2} & \cdots & C_{k+m-1}\\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots
\end{bmatrix}
6 . ここで各チェインの先頭の平文は他のチェインの平文と重複しないように設定します。
7 . チェイン作成後、チェイン先頭の平文と、末尾のハッシュ値をのみを保存します。
こうすることにより、一対一の対応表と比べて、$\frac{1}{m}$の個数でRainbow Tableを作ることができます。
Rainbow Tableによる解読
- 対象のハッシュ値$C_x$を還元関数とハッシュ関数に次々に通していきます。
- その結果を末尾の $C_{i+m-1}$, $C_{j+m-1}$, $C_{k+m-1}$ ... と比較します。
- 一致するものが見つかった場合、$P_i$, $P_j$, $P_k$ ... からチェインを復元します。
Rainbow Tableの問題
Rainbow Table作成時に問題となるのが、ハッシュ値および平文の衝突です。
この場合、例えば平文$P_i$と$P_{j+1}$が偶然同じ平文になってしまった場合、以降のチェインの値も全て同じ値になってしまいます。
これにより本来のものと比べて、一意のペアが減ってしまい、結果として解読できる確率が下がってしまうのです。
問題の解決
この問題を解決するには、還元関数の引数にindexなどを持たせるなどして、同じ平文やハッシュ値がきたとしても別の値を生成するようにします。
こうすることで、衝突の発生確率を$\frac{1}{m-1}$にまで下げることができます。
実際にRainbow Table Attackをする
今回はRainbow Tableを作る時間がなかったので実践しやすいように、既存のOSSを用いてRTAをします。
今回使うOSSはこちらです。
https://github.com/k4m4/dcipher-cli
このOSSはいくつかのオンラインRainbow Tableを用いて、CLIのみで簡単にRTAを行うことができます。
では、実際に使っていきます。
まずはありきたりなパスワード123456789をハッシュ化します。今回はsha-256を用います。
$ echo -n 123456789 | openssl dgst -sha256
15e2b0d3c33891ebb0f1ef609ec419420c20e320ce94c65fbc8c3312448eb225
続いてRTAで解読します。
$ dcipher 15e2b0d3c33891ebb0f1ef609ec419420c20e320ce94c65fbc8c3312448eb225
✔ 123456789
ものの数秒もかからずに解読されました。
では、次は大文字小文字を合わせたアルファベットで試してみましょう
$ echo -n GeorgeOrwell | openssl dgst -sha256
645c11e721b6abd446e66445e71cb61e921cc54fe8d5b0511437137fb9f60f43
$ dcipher 645c11e721b6abd446e66445e71cb61e921cc54fe8d5b0511437137fb9f60f43
✔ GeorgeOrwell
5秒ほどかかりましたが、大文字小文字を合わせた12文字のアルファベットでも解読できてしまいました。
では、次はこれに数字も合わせてみましょう。
$ echo -n 1984GeorgeOrwell | openssl dgst -sha256
be3392c9371316daf1653305596b4e47c5cd76444fe3ecbae9e66027ecd2a8b4
$ dcipher be3392c9371316daf1653305596b4e47c5cd76444fe3ecbae9e66027ecd2a8b4
✖ Hash could not be deciphered
大文字小文字のアルファベットと数字を合わせた16文字だと、解読はできませんでした。
これに特殊文字を足したものが、一般に推奨されるパスワードの条件なので、少なくともRTAを防げる可能性が高いという点では正しいですね。
Rainbow Table Attackの対策
全てのユーザーが推奨されるようなパスワードを使ってくれたら、少しは安心なのですが、現実はそういきません。
なのでサービス側で対策をする必要があります。
ソルト
ソルトとは、平文に余分な文字列を追加してからハッシュ化することで、RTAによる解読を困難にするものです。
さらに、ユーザーごとに違う文字列のソルトを行うことで、同じパスワードを持つユーザーが1人解読されても、他のユーザーのパスワードの解読は別で必要になります。
ストレッチング
ストレッチングとはハッシュ化を複数回行うことです。
これにより、本来困難なハッシュ値の解読が、より困難なものなります。
一般に、ストレッチングはハッシュ化を数千回～数万回ほど行われるので、サーバーへの負荷が大きいのがデメリットとなります。
まとめ
暗号解読の技術は年々向上しており、今やパスワードの保存は暗号化やハッシュ化では十分でない時代になっています。
なので、ハッシュ化によるパスワード保存だけでなく、多要素認証や2段階認証といった様々な工夫をこらすことが会社の規模に関わらず重要になってきます。
この機会に多くのデータが安全に保管されることを祈っています。