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")
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. ...

https://www.troyhunt.com/ive-just-launched-pwned-passwords-version-2/

利用者は、このリストに "(21BD1) 2DC183F740EE76F27B78EB39C8AD972A757" が含まれているかを調べ、あれば漏えいしていると判断できます。

実際のところ Have I been pwned? Pwned Passwords の検索フォームは上記のように動作します。また、同様のことをおこなう Bash スクリプト も存在します。

1. Every hash prefix from 00000 to FFFFF is populated with data (16^5 combinations)
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")

https://www.troyhunt.com/ive-just-launched-pwned-passwords-version-2/

それぞれのプレフィックスは、最小でも 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 にダミーのリクエストを送るなどの対策が必要と考えます。