(7) 正しいパスワードストア

本記事は 暗号学一人アドベントカレンダー 第7日目(相当)の記事です。

昨日の記事の補足を書きたかったので順序を入れ替えて書きます。

SHAtteredは「強衝突耐性の突破」

性質の良いファイルが2つ生成されているという点を見ると、一見して弱衝突耐性(=第二原像計算困難性)が突破されているかのように見えます。しかし、第4回の記事で紹介した定義に基づけば、

  • 第二原像計算困難性の突破=ハッシュ値とそのメッセージが与えられて同じハッシュを与える別のメッセージが生成できること
  • 強衝突耐性の突破=同じハッシュを与える2つのメッセージが生成できること

で、SHAtteredでは「あるハッシュ値とそのメッセージに対して」同じハッシュを与えるメッセージを生成しているわけではないので、攻撃しているのは第二原像計算困難性ではなく強衝突耐性のほうになります。より具体的には、

  • PDFのヘッダとして有効なヘッダを作り、それをSHA-1圧縮関数にかけた内部状態を得る
  • その内部状態をもとに、変化を打ち消すような2つのブロックのペアを計算する(ここに263回程度の計算が必要)
  • フッタをくっつける

ということで2つの有効なPDFを生成しています。決して最初に生成したPDFに衝突するようなもう一つの有効なPDFを探すことに成功したわけではないことに注意が必要です。

SHA-1はパスワードハッシュに不適格」?

「SHAtteredで衝突耐性が突破された!SHA-1をパスワードハッシュに使うな!」というのは原理的にはウソです。

パスワードのハッシュ化とは、ハッシュ関数の原像計算困難性または第二原像計算困難性によって「ある既存のハッシュ値を得るようなメッセージを得ることが困難」な性質を使って、パスワードの代わりにそのハッシュ値を保存しハッシュ値同士を比較することによってセキュリティを保つ技術です。ということは、第二原像計算困難性が未だに保たれているSHA-1を使うことは原理的には問題がない、といえます。

とはいえもっといい選択肢はある

仮にそれぞれのハッシュ関数が弱/強衝突に対して理想的なハッシュ関数だったとしても、ハッシュ値の長さが長い=ハッシュ関数の値空間が広いほうが衝突の確率は下がるので、MD5(64bit)よりもSHA-1(160bit)のほうが性質がよいですし、SHA-1よりもSHA-2(256bit以上)のほうが性質がよいことになります。

また、一般的にパスワードに使われるハッシュ関数は「遅いこと」が良い性質になります。その理由は、正規の利用者は一度しかハッシュ関数を使うことがないのに対し、ブルートフォース攻撃をしかける攻撃者は複数回ハッシュ関数を使うので、遅い関数を使うとブルートフォース攻撃にかかる時間が延びるためです。

Password Hashing Contestの優勝アルゴリズムであるArgon2はパラメータによって時間とメモリの使用量を調節でき、どのような攻撃者に対して強いかを選べるようなチューニングができるようになっています。

現代のパスワード攻撃

現代的にも辞書アタックなどは使われることはありますが、現代のパスワード攻撃は主にハッシュ値をデータベースから入手してそのハッシュ値に対してオフラインでハッシュの原像攻撃/第二原像攻撃を試みることで行われます。別に効率のいい第二原像攻撃が知られていなくても構いません、大規模な計算クラスタを使ってひたすらハッシュ値を計算するだけなのですから。

レインボーテーブルアタックとsalt

また、いちいちハッシュを毎回計算するよりも既に計算されている値を使えばいいじゃないか!ということで、既に計算済みのハッシュ値のテーブルをルックアップすることでハッシュ値を攻撃するレインボーテーブルアタックという手法が使われることがあります。とはいえ現代的にはこれは対策していないほうが悪いレベルの問題で、パスワードpを保存するときには十分に長いランダムな文字列sとそれぞれを結合したハッシュ値h(p||s)を保存することでテーブルルックアップによる攻撃を回避することができます。このsのことをsalt(cryptographic salt)といいます。saltに求められる性質としては「各ユーザーごとに異なること(でないと同様のレインボーテーブルが作れる)」「十分な長さが必要(でないと通常のレインボーテーブルが使えてしまう)」という性質があります。

最も理想的にはHSM利用でのHMAC(keyed hash)

最も理想的にはハッシュ関数そのものが認証器の外に出にくいものがよいですが、だからといってオレオレハッシュアルゴリズムを実装するわけにはいきません(第2回参照)。そこで、HSM(ハードウェアセキュリティモジュール)の中で鍵を生成し、鍵を用いたメッセージ認証のために使うHMAC(Hash-based Message Authentication Code)を使うと、HSMを通さない限り該当する鍵を使ったHMACの計算ができない(困難)ため、外部の人がハッシュ値を手に入れてもそのハッシュ値を生成した元の関数がわからないので、それをもとにしたローカルでのブルートフォース攻撃ができなくなります。とはいえ鍵を閉じ込めておくことのできてHMAC計算のインターフェースのあるHSMを導入するコストは並大抵のものではないので、通常はsaltつきのSHA-2/bcrypt/scrypt/Argon2あたりを使うのがよいでしょう。

パスワードポリシーについては

RubyKaigiのDrinkupにてLTしたスライドがあるのでそちらをご参照ください。

speakerdeck.com


今度こそ次はNon-Merkle-Damgård HashであるSHA-3とBLAKEの話。