Have I been pwned? にパスワードを入力するとどうなるか
Have I been pwned? Pwned Passwords (以下 HIBP と呼ぶ)が公開されました。ここでは、過去に情報漏えいで実際に暴露された 5 億個のパスワードのオンライン検索とダウンロードが提供されています。セキュリティに関心のある方は、検索するために入力したパスワードを HIBP の管理者に知られることに懸念を感じるでしょう。I've Just Launched "Pwned Passwords" V2 With Half a Billion Passwords for Download では、検索されたパスワードの秘密がどのように守られるかが解説されています。
ダウンロードとオフライン検索
その前に、安全にオフラインで検索する方法を説明します。
HIBP では、パスワードはソルトなしの SHA-1 ハッシュのリストで管理されています。利用者が自らのパスワードを検索したい場合、そのパスワードの SHA-1 ハッシュを求める必要があります。利用者が HIBP から 5 億個のパスワードのハッシュリストの全体をダウンロードし、それを検索すれば、管理者に自らのパスワードを知られるおそれはありません。ですが、そのリスト全体のサイズは約 9 ギガバイトあり、配布や更新にコストがかかります。
オンライン検索
それでは、利用者がパスワードのハッシュのみを HIBP に送信し、一致しているか結果を返す方法はどうでしょうか。
残念ながら、HIBP はハッシュする前の生のパスワードリストを持っているので、一致している場合、管理者に利用者のパスワードを知られてしまいます。一致していない場合も、レインボーテーブル - Wikipedia により、総当たり攻撃が可能です。
そこで、HIBP はパスワードハッシュの最初の 5 文字のみを送信するというアイデアを採用しました。
例えば "P@ssw0rd" というパスワードを検索するには、そのハッシュである "21BD12DC183F740EE76F27B78EB39C8AD972A757" の先頭の "21BD1" を HIBP に送信 します。HIBP はプレフィックス "21BD1" に一致するハッシュの残り 35 文字のリストを返します。
1. (21BD1) 0018A45C4D1DEF81644B54AB7F969B88D65:1 (password "lauragpe")
https://www.troyhunt.com/ive-just-launched-pwned-passwords-version-2/
2. (21BD1) 00D4F6E8FA6EECAD2A3AA415EEC418D38EC:2 (password "alexguo029")
3. (21BD1) 011053FD0102E94D6AE2F8B83D76FAF94F6:1 (password "BDnd9102")
4. (21BD1) 012A7CA357541F0AC487871FEEC1891C49C:2 (password "melobie")
5. (21BD1) 0136E006E24E7D152139815FB0FC6A50B15:2 (password "quvekyny")
6. ...
利用者は、このリストに "(21BD1) 2DC183F740EE76F27B78EB39C8AD972A757" が含まれているかを調べ、あれば漏えいしていると判断できます。
実際のところ Have I been pwned? Pwned Passwords の検索フォームは上記のように動作します。また、同様のことをおこなう Bash スクリプト も存在します。
1. Every hash prefix from 00000 to FFFFF is populated with data (16^5 combinations)
https://www.troyhunt.com/ive-just-launched-pwned-passwords-version-2/
2. The average number of hashes returned is 478
3. The smallest is 381 (hash prefixes "E0812" and "E613D")
4. The largest is 584 (hash prefixes "00000" and "4A4E8")
それぞれのプレフィックスは、最小でも 381 個のハッシュが存在しており、そこに利用者のパスワードが含まれていたとしても、管理者にはどれに一致するかわかりません。この HIBP が返すデータが持つ性質を k-匿名性 - Wikipedia と呼びます。
管理者が最悪でパスワード候補を 381 個までしか絞り込めないという意味であり、前述の完全なハッシュを送信するケースと比較して、リスクが緩和されています。利用者のパスワードが含まれていない場合は、ハッシュの残り 35 文字が不明なため 16^35 パターンの可能性があり、総当たり攻撃は現実的ではありません。
パスワードを推測されやすいシナリオ
ここからは筆者の考えですが、管理者がより正確にパスワードを推測できる利用シナリオがあります。
HIBP はハッシュしか返さないため、説明のために小規模なパスワードリストから生成したハッシュと、生のパスワードのペアを返すエンドポイントを用意しました。HIBP は 5 億ですが、ここでベースにしたパスワードリストは 100 万と小さいため、プレフィックス 3 文字で平均 244 個(最小 193 個)のハッシュとパスワードを返します。
https://asannou.github.io/badpasswords/21b.txt
利用者
あるサービスのアカウントを作るにあたって、新しく作成したパスワードが漏えい済みかを確かめる。
新しいパスワード "trustme" をチェックするため、そのハッシュ "b6a34a9f8b81a6964ff5b983bcc739ff2efb569f" のプレフィックスを送信する。
$ curl -s https://asannou.github.io/badpasswords/b6a.txt | grep ^b6a34a9f8b81a6964ff5b983bcc739ff2efb569f b6a34a9f8b81a6964ff5b983bcc739ff2efb569f trustme
リストに含まれていたので、続いて "trustme2", "trustme3" のハッシュ "30d22e311391fb2da70422f7402eb240908cf8e5", "42c540d61d64f38f334b2f350ea0e32d3a208a2e" をチェックする。
$ curl -s https://asannou.github.io/badpasswords/30d.txt | grep ^30d22e311391fb2da70422f7402eb240908cf8e5 30d22e311391fb2da70422f7402eb240908cf8e5 trustme2 $ curl -s https://asannou.github.io/badpasswords/42c.txt | grep ^42c540d61d64f38f334b2f350ea0e32d3a208a2e $
"trustme3" はリストになかったため、アカウントのパスワードとして決定する。
管理者
このとき、送られたプレフィックス "b6a", "30d", "42c" をみて、以下の推測ができる。
まず "b6a" と "30d" に含まれるパスワードで前方一致するものを探す。
$ wget -q https://asannou.github.io/badpasswords/b6a.txt https://asannou.github.io/badpasswords/30d.txt $ cut -f 2 b6a.txt | while read password; do cut -f 2 30d.txt | grep ^$password; done trustme2
この結果から、最初のリクエストで "trustme" 次のリクエストで "trustme2" が検索された可能性が高い。最後のリクエストを "trustme3" と仮定してハッシュを計算すると "42c..." が一致する。
考察
是非は別として、作成したパスワードが漏えい済みだった場合、文字を付加して回避することは、利用者の行動としてありえるでしょう。特に Nextcloud will check passwords against database of HaveIBeenPwned のように導入する場合は、パスワードが推測されないよう、適宜 HIBP にダミーのリクエストを送るなどの対策が必要と考えます。