こんにちは。ディマージシェアの技術担当です。今回は「パスワードハッシュの安全性」について書いてみようと思います。
パスワードハッシュとは
パスワードは他者に知られてはいけません。サービスの管理者であっても閲覧できないのが普通です。そのために欠かせないのが「ハッシュ関数」と呼ばれる技術です。例えば「PASSWORD」という文字列（パスワード）を
$2a$10$SyZ5r1GZ8Dw0SPTF4pKKlOiwdcNja2MVYbnsSGD8ykTIV2JXWkrLq
のような文字列（ハッシュ）に変換する仕組みです。ハッシュから元の文字列に戻すことは出来ない（とても時間がかかる）ようになっています。
多くのシステムではパスワードはハッシュ化された文字列で管理しています。構築されたのが最近のシステムではbcryptというアルゴリズムが採用されていることがほとんどです。「最近」と強調したのは、古いシステムではMD5やSHA-1といったアルゴリズムが採用されていることがあるからです。今回は、パスワード管理の歴史を振り返り、古い方式のリスクと、bcryptがいかに安全か、という事実を、実験を交えながら紹介します。
パスワード管理の歴史
パスワードを平文で管理するのは危険なため、ハッシュ化して管理するという思想自体は古くからありました。初期の頃はMD5やSHA-1というアルゴリズムが用いられていました。後に、これらのアルゴリズムにセキュリティ上の欠陥が発見されたり、計算機の性能向上に伴う総当たり攻撃のしやすさが問題視されたりして、bcryptやArgon2などの後発のアルゴリズムが採用されるようになりました。
しかしながら、歴史の長いシステムなどでパスワードハッシュ化アルゴリズムにMD5を用いており、かつ現在も稼働中、といったケースは未だに残っています。もし、そういった案件に関わった際は、古い方式の撤廃を少なくとも1度は提案してあげてください。もしくは、古い方式を安全な方式でラップして解決するようにしましょう（本コンテンツ末尾）。
パスワードハッシュにMD5は不適切
MD5は1992年に開発された昔ながらのハッシュアルゴリズムです。「hogehoge」という入力に対し「329435e5e66be809a656af105f42401e」のようなハッシュ文字列が得られます。一見、32文字もあるし、元の文字列に戻すのも大変そうだし、十分なのでは？と思う方もいると思います。実際に、過去にはパスワード管理に用いられた実績もあり、今もなお稼働システムがあることは先述の通りです。
MD5の弱点
今回注目するMD5の弱点は、
・入力に対してハッシュ値の計算が高速
・同じ入力に対して同じハッシュ値が得られる
の2点です。暗号学的な脆弱性が発見されてたりもしますが、そういったマニアックな世界は各々楽しんでください。
総当たり攻撃に弱いMD5（1）
C言語で簡単な総当たり攻撃のプログラムを作ってみます。
void brute_force(md5bin* hash) {
char pass[MAX_PASSWORD_LEN];
unsigned long long int ct = 1;
while (1) {
next_str(pass); // チェックするパスワードを得る、この関数をコールする毎に次のパスワードを得る
if (check_pass(pass, hash)) { // 一致していたら表示して終了
printf("%s\n", pass); // パスワードを表示
printf("%lld\n", ct); // 試行回数を表示
return;
}
ct++;
}
}
雰囲気としては上記のようになります。検査する文字セットを大小アルファベット52文字として、パスワード「ZZZZ」を分析してみます。
$ time ./a.out
md5 digest: 4ddf7fd96ffcf749d2f1ee6efb64cc88
ZZZZ
7454980
real 0m0.767s
user 0m0.382s
sys 0m0.382s
7454980回の試行の末、パスワードが分析できました。4桁のパスワードが1秒もかからずに分析できてしまいました。MD5は値を高速に計算できるのが特徴で、セキュリティ的にはその特徴がデメリットとして現れます。
では、bcryptだとどのくらい遅いの？という質問に対する実験結果を載せておきます。
$ time ./a.out
Hashed password: $2a$10$5DfbZcgM5tUhlm.tHcAtJ.BIXAlrjV1CxWS.WMv7IttYTLGl6MvcC
ZZ
2756
real 2m2.614s
user 2m1.533s
sys 0m0.157s
ZZまでたどり着くのに2分以上かかります（4桁は時間がかかりすぎるので諦めました）。ハッシュ文字列がわかっている場合で同じパスワードを総当たりで分析するのに、bcryptはMD5の43万倍の時間が必要なことがわかりました。
総当たり攻撃に弱いMD5（2）
入力に対してハッシュ値の計算が高速であることがデメリットであることはわかりました。もう一つ、「同じ入力に対して同じハッシュ値が得られる」がどのようにデメリットとして作用するのか観察してみたいと思います。
とあるシステムのアカウントテーブルが漏洩してしまった！
もう字面から危険なのですが、ハッシュ値のリストに対して総当たり攻撃をした場合の挙動を見てみます。ハッシュ値のリストは、
5f543a73c535ad57387d92b71d6c3d53
ed5b65830f0e316d0d53f37fd83a9fd1
1833a34dc613ec00d342030c26f09cdd
bf2d2a05daef1349c552a70b3a2002b7
386c21104088a40c1d75b3271052ee6d
...
のように、たくさん（10000件）あります。全てのハッシュ値は大小アルファベット4文字という条件で用意しました。aaaa～ZZZZまで全てチェックすれば、全てのハッシュ文字列の分析ができるようになっています。10000件のハッシュ文字列を全て、元の文字列に戻すのに要した時間を計ってみます。
$ time ./a.out > /dev/null
real 0m0.853s
user 0m0.231s
sys 0m0.614s
結果、1秒かかりませんでした。パスワード1つ「ZZZZ」を分析するのに要した時間、0.767秒から0.1秒も増加していません。人によっては、検査対象の件数が10倍になれば必要な時間も10倍になるのでは？と感じた方もいると思います。一般的なアルゴリズムにそこそこ詳しい人ならば、「10000件のリストの中に目的の値があるかどうか」を検査することが一瞬で可能なことを知っていると思います。
紙の辞書で何か単語を調べた経験のある方ならわかるのではないでしょうか。辞書はアルファベット順に「ソート済」であるため、目的のキーワードを見つけるのにさほど時間はかかりません。少なくとも、1ページ目から最後のページまで1ページずつ調べる、という行為は行われません。
ハッシュ文字列のリストも、攻撃するときに「ソートして」持っておけば、後のチェック処理が非常に高速に行えます。他にも、過去に分析済のハッシュ文字列リストも用意できてしまいます（参考：レインボーテーブル攻撃）。「同じ入力に対して同じハッシュ値が得られる」という性質が良くないことが確認できました。bcryptでは「ソルト」という仕組みでこの問題を解決しています。詳しくはgoogleに聞けばわかります。
※
上記の文面に「あれ？」と違和感を持った方は優秀です。ソートやTreeを使った方法では、実際はもう少し時間がかかります。技術者でない方にもわかりやすい表現で嘘を書きました。実際にはHashMapを使った方法で実装しています。
bcryptの適切なコスト
少し話が飛びます。bcryptに関して細かい解説を書いてもgoogle検索で得られるコンテンツの焼き直しになってしまうので割愛しました。この記事で書き留めておきたい大切な内容をピックアップします。
bcryptはハッシュ文字列を得るために必要な計算機リソースの量を調節するパラメータを持っています。PHPのpassword_hashのページなどがわかりやすいと思います（https://www.php.net/manual/ja/function.password-hash.php ）。コストを1増やすと計算回数が2倍になります。例えばPHPではデフォルト値が10で、1回の計算に50ミリ秒前後かかるように調整されています。コストの値は扱う要件に応じて適宜設定します。ほとんどの場合はデフォルトの10で問題ないと思いますが、8～14の範囲で選ばれる傾向にあります。このように、bcryptでは計算コストを設定できるので、計算機の進化により計算時間が短くなってきたらコストの値を1増やす、といった対応ができる仕組みが用意されています。
古いハッシュアルゴリズムの撤廃
理想的な方法はアルゴリズムを差し替えて全ユーザのパスワードを再登録することですが、難しいシステムもあります。そのような場合は、既に保存されているハッシュ値を新しいアルゴリズムで再ハッシュ化して保存する、という手段が選べます。
bcrypt(md5(password))
とすれば、誰にも気付かれずにmd5のハッシュ文字列を除去することが可能です。ハッシュアルゴリズムの一方向性の性質に着目すれば、上記の方法で「入力されたパスワードがハッシュ値と一致しているか」の検証に問題がないことがわかります。
当社に興味を持たれた方はHPもご覧ください。