パスワードをハッシュ化したからといって安全じゃない、レインボーテーブルを使ったブルートフォース攻撃の脅威と対策

はじめに

「パスワードはハッシュ化しておけば大丈夫」

エンジニア2年目でそんな固定概念がありました
ではなぜ大丈夫なのか？
そもそも大丈夫という認識が適切なのか？
そういった疑問のクリアにしたいと思います

ちなみにシステム開発でプログラミング言語によってハッシュ化で使用されるアルゴリズムが異なっていたり、ハッシュ化に伴う処理の過程に違いがあるので、言語選定や関数選択、クラウドサービス(Amazon Cognitoなど)の使用時に、それぞれの特徴を理解しておく必要があります
この記事ではどの点に着目することでセキュリティリスクを下げることができるのかもまとめています

どうしてパスワードはハッシュ化しておけば大丈夫(と考えられている)か

そもそも論ですが、ハッシュ化することでどうして大丈夫と言われているのでしょうか？

ある値をハッシュ化する際に用いられるのはハッシュ関数と呼ばれる関数です
こちらは別名、一方向性関数とも呼ばれています

Wikipedia曰く、

一方向性関数（いちほうこうせいかんすう、英: one-way function）とは関数値は容易に計算できるが逆関数の計算は非常に困難である関数を指す。

一方向関数には以下のような種類があります(他にもあります)

• SHA-256
  • 任意の長さの原文から256ビットの出力をする
• SHA-512
  • 任意の長さの原文から512ビットの出力をする

つまり、ここから言えることはハッシュ値が流出してしまっても、その値から元の値を特定することが困難であるということです
一般的にハッシュ化された値は元に戻すことができず、このことを不可逆性があるといいます

ハッシュ値が戻せないということは、DBにハッシュ化されたパスワードを格納しておけば仮に流出したとしてもパスワード自体は特定できないことを意味します
これは堅牢性が高いといえます

ここまでが世間でハッシュ化しておけば大丈夫の大まかな所以です

なぜハッシュ化が安全とはいえないのか？

ではなぜ不可逆性がありながら、ハッシュ値自体がハッシュ化する前の値が特定されないことに必ずしもつながらないのでしょうか？

ハッシュ化された値を割り出す方法

これはハッシュ化に使われたハッシュ関数と時間があれば元の値の特定ができるからです

例えばパスワードが1111でハッシュ関数によってハッシュ化し、「eks3」というランダムなハッシュ値が流出したとします
このとき悪意のあるユーザーは、ハッシュ関数さえ知っていれば、どんな値がハッシュ化によって「eks3」になるかを推測します
仮にこのユーザーが4桁の数字であるという情報さえあれば9999通りを試すことで、目的のパスワードには確実に到達できます
つまり、ハッシュ値を復元できなくてもその候補をハッシュ化することを繰り返せばいつかは元の値が特定できるということです

このように不正にパスワードを割り出すことをパスワードクラック(password cracking) と呼びます
上記にあるようなあり得るパターンを大量に検証してパスワードクラックを行うことをブルートフォースアタック(brute-force attack) と呼びます
brute-forceは腕力の意味です

ブルートフォースアタックの脅威

様々な暗号アルゴリズムがありますが、ブルートフォースアタックはハッシュ関数に対しても一定の脅威であることはわかっていただけたかと思います
ここで、この記事のタイトルの半分の伏線は回収しました

ただし、脅威はまだ続きます
ハッシュ値を特定する際にブルートフォースアタックとセットで使うことでさらに強力な脅威となってしまうのがレインボーテーブルです

レインボーテーブルとは

ハッシュ関数によりハッシュ化された元のデータ（平文）を効率的に導きだすためのテーブルです
一部不正確なのですが、概要を抑える上で最適な記事はこちらです

まず前提として、ブルートフォースアタックの非効率性についてまとめると以下の通りです

• ストレージが過剰に必要になる
  • 総当たりで平文を特定するために平文とそのハッシュ値のペアを大量に準備しておく必要がある
• ペアを用意していない場合は平文にハッシュ関数を実行することになるため、時間がかかる
  • 一般的にハッシュ関数は計算に時間がかかるように設計されている
  • 時間と空間のトレードオフ

以上を補う役割としてレインボーテーブルが使われます

レインボーテーブルを使うことで最小限のストレージ使用であるにも関わらず幅広い平文とハッシュ値の組み合わせを保存し、先ほど挙げた課題を解決できます

仕組みは以下の通りです

まず、以下のような特殊なテーブル(レインボーテーブル)を用意します
Hで表したのがハッシュ関数で、あるハッシュ値からランダムに選んだ平文を導く関数(還元関数)をRxとしています
これを繰り返すことで 「平文1」→「ハッシュ値1」→「平文2」→「ハッシュ値2」→「平文3」 というチェーンが出来上がります
以下の画像は3つを組み合わせただけですが、本来はこのつながりが1000セット、10000セットとあり、ここでは例えのために３セットとします

このように事前にテーブルを用意しておくことでブルートフォースアタックの非効率性2つ目で挙げた、候補となる平文全てにハッシュ化をする時間のネックを解消することができます

また、レインボーテーブルの脅威はここからです
レインボーテーブルの特性を使うと、1つ目の過剰なストレージも不要になります
レインボーテーブルで必要となるのはチェーン1つに含まれる平文とハッシュ値全てではありません
最初の平文と最後のハッシュ値だけで十分なのです

どういうことかというと、以下のようにハッシュ値が流出したとします

そこで流出したハッシュ値に一番最後の還元関数R2を使います
導き出された平文がレインボーテーブルの末尾にあるか調べます

「東京」に一致する値がレインボーテーブルにはないため、「avnioe」に1つ前の還元関数R1を使い、そこで導かれた平文にハッシュ関数Hを使い、そのハッシュ値にR2を使います
以下のように「いちご」が導かれ、レインボーテーブルにあるチェーンの1つの末尾の平文と一致したとします

つまり還元関数R1を使って最終的な平文が一致したということはR1の1個前の平文が流出したハッシュ値の元の値であるとわかりますよね
そのため、一致したチェーンの一番最初の値に戻りハッシュ化を行うことで目的のハッシュ値とも一致したため元の値は「りんご」であるとわかります

還元関数が大量にあったとしても、どこかで末尾の平文と一致していたら最初に戻りハッシュ関数と還元関数を順序に行うことでどこかで目的の平文は見つかるという仕組みです
従って最初の平文と最後の平文さえストレージに入れておけばチェーン全てを保持していなくても、全てを保持していることと同様にハッシュ値の元の値を特定することができます

ハッシュ化による堅牢性を高めるには

以上に挙げたようにセンシティブな情報をハッシュ化しておけば、万が一情報が流出してしまっても大丈夫...とは限らないことがわかっていただけたかと思います
それではハッシュ化は全く使えないのかというとそうではありません
現実的な範囲でハッシュ化を強固にしておくことで、(非現実なほど)膨大な時間や豊富なコンピューティングリソースがない限り破られることのないハッシュ化を施すことができます

ここで取り上げる方法は以下3つです

ソルトを使う

ソルトとは平文に任意の文字列を加えてハッシュ化する方法、もしくはその任意の文字列のことです

ソルト化に伴うメリットは

• 元の平文が推測しづらくなる
  • ユーザーが推測しやすいパスワードをつけてしまったとしてもその値を複雑化することができる
• 平文が長くなり候補が増える
  • レインボーテーブルのサイズが増加する
• ソルトが付与されていないテーブルが使えなくなる
  • ソルトに対応したテーブルを改めて作る必要がある
• 同じパスワードを有するユーザーに対して異なるソルトを付与することで、異なるハッシュ値を得ることができる
  • 利用者毎にブルートフォース攻撃を行う必要がある

以上のようにソルトを付与するだけでレインボーテーブルによる効力をかなり抑えられることがわかると思います

ストレッチングを行う

ストレッチングとはハッシュ値の計算を繰り返し行う方法のことです
ソルトを使っただけでは、総当たりすることで特定されてしまうリスクをストレッチングによって抑制することができます

そもそもハッシュ計算には時間がかかります
そのハッシュ計算を繰り返すことによってレインボーテーブル作成コスト、作成後の解読コストを高めセキュリティの向上に役立ちます

例えばPHPの password_hash() 関数を使った場合にはデフォルトで2の10乗回(1024回)ハッシュ関数に伴う計算を行なっています
これがパスワード候補となる全ての平文に行わなければならないとすると、かなりのコンピューターリソースと時間が必要になると想像できると思います

ご自身のAPサーバーの性能が高ければ、この数字は大きくすればするほどセキュリティ性能を高めることができますが、それは同時に普段のパスワードのハッシュ化処理にかかる時間が長くなることにもなるので適切な値はハードウェアとシステム要件によって異なります

ハッシュ値衝突の起こりにくいアルゴリズムを使う

アルゴリズムによってはハッシュ値がある値に偏りやすいものがあります
そういったアルゴリズムを使ってしまうと、少ないレインボーテーブルで目的の平文を割り出されてしまう可能性が高まります
そのため、ハッシュ値の偏りがなく異なった平文には異なったハッシュ値を導くアルゴリズムを選定する必要があります

まとめ

ハッシュ化すれば大丈夫と考えている方(自分を含め)へ、ハッシュがどうして大丈夫なのか、そして堅牢性を高めるためにハッシュ化について意識すべき項目をまとめました
普段使っているフレームワークなどのハッシュ化について見つめ直すことで、自身のシステムがセキュリティ的に安全かどうか確かめると、意外とソルトの使用やストレッチングが行われておらず、セキュリティホールが見つかるかもしれません

良いセキュリティライフを...