The protective value of "k-anonymity"¹ for Have I Been Pwned / Pwned Passwords API lookups is significantly reduced because frequency data is included. And the more common the password, the more this effect is magnified.
An example:
https://gist.github.com/roycewilliams/2034c9253d46fbcaefb13f8e5d42daa2
... with cracks:
https://gist.github.com/roycewilliams/2bb471cc90cce7f6834204344590fcac
Using "k-anonymity"¹ to return all hashes that begin with b2e98 is less "anonymous" ... when 98.6% of the passwords (by frequency across all leaks) are the top one.
It's not really hiding a needle in a haystack if you just lay it on top.
Edit: in fact, even *without* the frequency data, since some passwords are much more common than others ... left-skewed distribution is an intrinsic property of password data. Missing frequency data can be largely reconstructed from public cracking efforts. (And even if that weren't true, the hashes can just be cracked using traditional methods. If the cracking community can get a 97%+ cracking rate², what is being achieved other than plausible deniability?)
K-anonymity [as implemented by HIBP, anyway -- true K-anonymity is different¹] may just be a bad fit for password hashes.
¹ Not actually k-anonymity at all:
https://en.wikipedia.org/wiki/K-anonymity
² Actually closer to 99.29% across the entire corpus, publicly:
https://gist.github.com/roycewilliams/40f0e8c93ec9c69f5b5a1874c76f2587
#passwords #HaveIBeenPwned
Royce Williams
npub1d9…v7m3z
2025-03-18 23:15:47 UTC
Author Public Key
npub1d9j86kugzarj4skw6juglk2de6mful9svqu8yac6vum5wz5xtcwsyv7m3zSeen on
wss://relay.momostr.pinkPublished at
2025-03-18 23:15:47 UTCEvent JSON
{
"id": "8cbe2c72cdeeb2f9927b1fd9cdbf5d80d9914634e6d13ff7f0f51c7bffa1dd36",
"pubkey": "69647d5b8817472ac2ced4b88fd94dceb69e7cb0603872771a6737470a865e1d",
"created_at": 1742339747,
"kind": 1,
"tags": [
[
"t",
"haveibeenpwned"
],
[
"t",
"passwords"
],
[
"proxy",
"https://infosec.exchange/@tychotithonus/114185977710675432",
"web"
],
[
"proxy",
"https://infosec.exchange/users/tychotithonus/statuses/114185977710675432",
"activitypub"
],
[
"L",
"pink.momostr"
],
[
"l",
"pink.momostr.activitypub:https://infosec.exchange/users/tychotithonus/statuses/114185977710675432",
"pink.momostr"
],
[
"-"
]
],
"content": "The protective value of \"k-anonymity\"¹ for Have I Been Pwned / Pwned Passwords API lookups is significantly reduced because frequency data is included. And the more common the password, the more this effect is magnified.\n\nAn example:\n\nhttps://gist.github.com/roycewilliams/2034c9253d46fbcaefb13f8e5d42daa2\n\n... with cracks:\n\nhttps://gist.github.com/roycewilliams/2bb471cc90cce7f6834204344590fcac\n\nUsing \"k-anonymity\"¹ to return all hashes that begin with b2e98 is less \"anonymous\" ... when 98.6% of the passwords (by frequency across all leaks) are the top one.\n\nIt's not really hiding a needle in a haystack if you just lay it on top.\n\nEdit: in fact, even *without* the frequency data, since some passwords are much more common than others ... left-skewed distribution is an intrinsic property of password data. Missing frequency data can be largely reconstructed from public cracking efforts. (And even if that weren't true, the hashes can just be cracked using traditional methods. If the cracking community can get a 97%+ cracking rate², what is being achieved other than plausible deniability?)\n\nK-anonymity [as implemented by HIBP, anyway -- true K-anonymity is different¹] may just be a bad fit for password hashes.\n\n¹ Not actually k-anonymity at all:\nhttps://en.wikipedia.org/wiki/K-anonymity\n\n² Actually closer to 99.29% across the entire corpus, publicly:\nhttps://gist.github.com/roycewilliams/40f0e8c93ec9c69f5b5a1874c76f2587\n\n#passwords #HaveIBeenPwned",
"sig": "573747cbd3029b9286634faeae3fbaff50d52c7c25f8ac93c91122ab563d2a881694e9771bdcc9519b7a28ae74fdf9bb43fa8a30714bea28bd278097f08c801e"
}