How k-Anonymity Lets You Check Breaches Without Leaking Your Password

Updated on February 28, 2026

There is a paradox buried inside every "check if your password was breached" tool. To find out whether a service knows about your compromised credential, you seemingly have to hand that credential to the service. It is the security equivalent of asking a stranger whether they've seen your wallet — and showing them the wallet to help them recognize it.

For years, this uncomfortable trade-off quietly discouraged people from checking at all. The HaveIBeenPwned API changed everything — not by building better trust policies, but by redesigning the cryptographic interaction so that trust became unnecessary. The technique it uses is called k-anonymity, and understanding how it works will permanently change how you think about privacy-preserving API design.

What We're Actually Protecting Against

Before diving into the mechanics, it helps to be precise about the threat. When you check a password against a breach database, three things could go wrong:

  1. The service logs your query and now knows exactly what password you use.
  2. An attacker intercepting the connection sees your password in transit.
  3. The service is compromised, and the logs of billions of queries become a fresh password dump.

Even if you fully trust the operator — Troy Hunt, in the case of HIBP — threats two and three exist at the infrastructure level, not the intent level. A well-designed protocol should make logging your specific password structurally impossible, not just policy-prohibited.

Hashing as the First Layer

The foundation of the approach is a SHA-1 hash. Before any network request happens, the client computes the SHA-1 digest of the password locally. SHA-1 produces a 40-character hexadecimal string — for the password "correct horse battery staple" that digest is 6f5902ac237024bdd0c176cb93063dc4b1711fca.

Sending that hash instead of the raw password is already better than sending plaintext. An attacker who intercepts 6f5902ac237024bdd0c176cb93063dc4b1711fca can't reverse it directly into the password — hash functions are one-way by design. But this alone still leaks information. The server receives a specific, unique identifier that maps to exactly one password. The server can log it, and if they ever obtain the original password (say, from another breach), they can connect the dots. You've traded plaintext exposure for pseudonymous exposure — an improvement, but not elimination.

More practically: if the password is common, the server just has to check their SHA-1 rainbow tables. "123456" hashes to 7c4a8d09ca3762af61e59520943dc26494f8941b — every security researcher on earth knows that mapping.

Enter k-Anonymity: The Hash Prefix Trick

Here is where the protocol becomes genuinely elegant. Instead of sending the full 40-character hash, the client sends only the first five characters — the prefix. For our example password, the client sends 6f590 and nothing else.

The HIBP API responds with every hash in its database that begins with those five characters. That response might contain 400 to 900 entries. The client then searches that local list for the complete hash. If it finds a match, the password has been breached. If it doesn't, it hasn't.

The server never receives the full hash. It receives a prefix shared by hundreds of different hashes. It cannot determine which specific password you were checking — it knows only that you were interested in one of hundreds of candidates. That is k-anonymity: your query is indistinguishable from k-1 other plausible queries, where k in this case is the size of the returned set.

The math here is straightforward. SHA-1 produces 16^5 = 1,048,576 possible five-character hex prefixes. The HIBP database contains roughly 900 million compromised hashes. That means each prefix bucket contains, on average, about 858 hashes. An observer who intercepts 6f590 learns that you were asking about one of those ~858 passwords — which is to say, they learn essentially nothing specific about your credential.

The Protocol in Practice

If you want to see this working directly rather than through a library abstraction, it's worth running it yourself. Open a terminal and try:

$ echo -n "hunter2" | sha1sum
f3bbbd66a63d4bf1747940578ec3d0103530e21  -

$ curl https://api.pwnedpasswords.com/range/f3bbb

The curl response comes back with a list of hash suffixes and hit counts, something like:

...
D66A63D4BF1747940578EC3D0103530E21:17394
...

Read that carefully. The API returns only the suffix — the part after the prefix you sent. You reconstruct the full hash by prepending your prefix. Then you check whether that full hash matches what you computed locally. In this case, "hunter2" has been seen 17,394 times. The server never received the string f3bbbd66a63d4bf1747940578ec3d0103530e21. It received f3bbb.

The response also carries Cache-Control headers with a generous TTL, which means CDN infrastructure can cache prefix responses globally. The privacy model and the performance model align beautifully — caching works precisely because the server returns a bucket of results rather than a targeted lookup.

Why SHA-1 Specifically, and Does It Matter?

SHA-1 is cryptographically deprecated for certificate signing and digital signatures — there are known collision attacks. But collision resistance is not what we need here. We need preimage resistance: given the hash, you cannot recover the original input. SHA-1 remains perfectly adequate for that property. Using SHA-256 would also work, but the HIBP API standardized on SHA-1 when it launched, and changing it now would require rebuilding the entire dataset lookup infrastructure for no meaningful security gain.

The practical implication: if someone intercepts your five-character prefix in transit, the preimage resistance of SHA-1 is completely irrelevant — they don't have enough information to even attempt a reversal. You'd need the full 40-character hash before SHA-1's weaknesses become germane, and the protocol ensures they never receive it.

The Limits of the Technique

k-Anonymity through hash prefixes is not perfect, and being honest about its limitations matters more than overselling it.

Traffic analysis at scale. If an adversary can observe which prefixes you query over time — across many passwords, many logins — they can potentially narrow down your password candidates through elimination, especially if your password isn't in any common wordlist and thus uniquely identifies a rare hash bucket. This is a sophisticated attack requiring persistent observation, but it exists.

Password complexity still matters first. The k-anonymity protocol tells you whether a password has appeared in a breach — it doesn't protect you if that password was never breached but is trivially guessable. "Tr0ub4dor&3" might not be in HIBP's database yet. A credential stuffing attacker with a good wordlist might crack it anyway. Breach checking and password strength assessment are complementary tools, not substitutes for each other.

The endpoint itself must be trusted to some degree. If the API at api.pwnedpasswords.com were completely compromised and replaced with a malicious version, it could return empty result sets for everything — effectively blinding you to real breaches. The protocol prevents the server from learning your password, but a compromised server can still lie to you about results. DNS verification and TLS certificate pinning are the mitigations here, neither of which most end-users actively validate.

Implementing It Yourself

The HIBP API is one implementation, but the k-anonymity pattern is reusable. If you're building an internal tool that needs to check credentials against a private breach database without sending those credentials over a network, you can replicate the exact approach:

  • Pre-compute SHA-1 hashes of all credentials in your breach database.
  • Build an index of five-character prefixes pointing to suffix lists.
  • Your lookup endpoint accepts a prefix, returns the corresponding suffix list with counts.
  • The calling client reconstructs and compares locally.

The database size required is substantial — 900 million hashes at roughly 25 bytes each is around 22GB — but the prefix-bucketed lookup is fast, and the cacheability of responses means you can front the whole thing with a CDN and handle enormous query volumes cheaply.

What This Changes About How You Think About Privacy APIs

The deeper lesson here isn't specific to password breach checking. The hash-prefix technique is an instance of a broader design principle: structure your protocol so that the server receives the minimum information needed to be useful.

Most API design goes the opposite direction. Send us everything, and we'll filter server-side. It's computationally efficient and architecturally simple. But it creates a permanent record of exactly what each client was looking for, which becomes a liability the moment logs are subpoenaed, leaked, or sold.

k-Anonymity through hash prefixes achieves the query result with a deliberate information gap on the server side. The server is helpful without being informed. That distinction — useful versus informed — is where most privacy-preserving system design actually lives, and it's a distinction worth carrying into every API you build or evaluate.

The next time someone tells you that checking whether your password has been breached "requires" sharing that password with a third party, you now have a technically precise, mathematically grounded explanation for why that's wrong. The protocol that disproves it has been running in production for years, handling millions of queries daily, and the server truly cannot tell which password any individual user was checking.

That is not a policy promise. It is arithmetic.