はじめに
パスワード漏洩のニュースを見て気になったので調べてみました。
最もダメな平文保存パターンから、漏洩した場合の危険性とそれを防ぐより安全なパターンを順々に列挙します。
ハッシュアルゴリズムについての詳しい説明は割愛。またユーザーが入力したパスワードは十分な強度かつ他サービスで使いまわされていないとします。
結論
どういう風にハッシュ化されているかどうかに強く依存します。
ソルト + 遅いハッシュ化アルゴリズム（Argon2id）が最善ですが、適切に運用されている必要があり、それ塞いでいたとしても原理的に安全というよりは「コスト的に見合わないことが多い」という判断にとどまります。
具体的なパターン
1. 平文保存
どういう方式か
ユーザーが入力したパスワードをそのままDBに保存します。
漏洩した場合の危険性
IDと一緒に漏洩すれば特に知識がなくても認証可能です。
2. ハッシュ化
どういう方式か
ユーザーが入力したパスワードをハッシュ関数で計算したハッシュ値をDBに保存します。
hash = SHA256("superstrongpassword")
= c3a83... (64文字の16進文字列)
ログイン時はユーザーの入力したパスワードを同様にハッシュ化し、DBのハッシュ値と同じかどうかで検証します。
ハッシュ値は平文に戻すことはできないので、ハッシュ値が漏洩しても元のパスワードはわかりません。
漏洩した場合の危険性
攻撃者はパスワードそのものを知る必要はなく、そのハッシュ値を出せる文字列がわかればログインできます。以下はその方法の例です。
-
レインボーテーブル
あらかじめ全てのハッシュ値と対応する平文の対応表を作っておく方法です。実際調べればネットにもSHA-256のレインボーテーブルが落ちているようです。 -
総当たり攻撃（ブルートフォース）
パソコンの処理能力に任せて攻撃対象のハッシュにヒットする文字列が出るまでひたすらハッシュ化し続けます。SHA-256の場合、英小文字＋数字8文字（36^8 ≒ 2.8兆通り）の空間なら、ハイエンドGPU 1枚あれば数分で全探索が終わるようです。
3.ソルト付きハッシュ化
どういう方式か
ユーザーそれぞれにつきランダムな値（ソルト）を生成し、パスワードと連結してハッシュ化します。ソルトは秘密ではないので、ハッシュと一緒に保存します。
salt_alice = "x7Kp2mQz" (暗号論的乱数, 16バイト以上)
hash_alice = SHA256("x7Kp2mQz" + "superstrongpassword")
salt_bob = "9fRt4wLc"
hash_bob = SHA256("9fRt4wLc" + "superstrongpassword") ← 同じパスワードでも全く別のハッシュ
漏洩した場合の危険性
前述の総当たり攻撃は防げません。
ただし、ソルトの種類だけレインボーテーブルが必要になるので実質的にレインボーテーブル攻撃は防げます。（ソルトがわかっても、そのソルトに対応するレインボーテーブルを作るより総当たり攻撃した方が早い）
4. より遅いアルゴリズムでのハッシュ化（キーストレッチング）
どういう方式か
3のソルトに加えて、ハッシュ化アルゴリズムにあえて遅いアルゴリズム（bcrypt, Argon2idなど）を使います。（正確にはbcryptやArgon2idの中にソルトが含まれている）
ユーザーのログイン時には1回しかハッシュ化を実行しないので1回あたり100msのアルゴリズムを利用してもある程度許容されますが、この遅さが総当たり攻撃に効きます。
先ほどのハイエンドGPUで概算すると以下のような差が出ます。
| アルゴリズム | GPU 1枚での概算試行速度 | 8文字英小数字(2.8兆通り)の全探索目安 |
|---|---|---|
| SHA-256（ソルト付き） | 約 200億回/秒 | 約2分 |
| bcrypt (cost 12) | 約 1,500回/秒 | 約60年 |
| Argon2id（推奨設定） | 約 数百〜数千回/秒 | 数十年〜数百年 |
さらに scrypt と Argon2 はメモリハードに設計されています。計算のために数十〜数百MBのメモリを要求するため、「小さな演算ユニットを何千個も並べる」というGPU/ASICの強みを潰します。
GPUのメモリ帯域とVRAM容量がボトルネックになり、並列度を上げられなくします。bcryptも小さな作業メモリ（4KB）を使うため、GPUに対して部分的な耐性を持ちます。
漏洩した場合の危険性
この方式が現状のベストですが、それでも実装によって危険性は残ります。
-
コストパラメータが古い
bcryptとArgon2idどちらもコストパラメータ（アルゴリズムの反復回数）を設定できますが、このコストパラメータの適切な値はハードの性能の進化により変わります。定期的に新しい値に更新しリハッシュする運用が必要です。 -
実装の不備を突く
a. bcryptの72バイト制限
bcryptは入力の73バイト目以降を黙って切り捨てます。長いパスフレーズの後半が無視されるほか、事前にSHA-256などを掛けてから渡す実装で、そのバイナリ出力にNULバイトが含まれると、そこで文字列が終端されてエントロピーが激減する不具合が知られています（事前ハッシュするならBase64等でエンコードしてから渡す）b.ソルトの再利用・リハッシュ漏れ：移行時に古いハッシュが残る
2015年の Ashley Madison 侵害では本体は bcrypt(cost 12) だったにもかかわらず、レガシーコードに残っていたMD5ベースのトークンが併存していたため約1,100万件が短期間で解読されました。強いアルゴリズムを導入しても、古い経路が1つ残っていればそこが全体の強度になります（参考記事） -
計算資源を投入する
キーストレッチングは「解読不能」ではなく「解読が高価」なだけで、価値の高いアカウントには十分な資金が投下されます。
前提の再確認
そもそもここまで「ユーザーが入力したパスワードは十分な強度かつ他サービスで使いまわされていない」ことを前提としましたが、攻撃者がまず最初に行うのは辞書攻撃です。
総当たりでハッシュ値を調べるのではなく、人間が入力しやすいパスワードや、すでに流出しているパスワードのリストを使ってハッシュ値にマッチしないかを調べます。たとえ遅いアルゴリズムだったとしても、数千万件程度であれば現実的に全てを調べあげられます。
感想
いろいろ考えると全然安全じゃなさそうですね。漏洩しないことに越したことはない（当たり前）。
いつも何も考えずに使用しているフレームワークの推奨に従っているのですが、裏では頭のいい人同士のイタチごっこが行われているんですね（結局古典的な方法が残るのもあるある）。
最終的に経済合理性が見合わないようにして防ぐというのが人間臭い解決策で非常に巧妙だと思いました。