Breached Password Screening With k-Anonymity

The single most effective password policy is not a complexity rule; it is refusing passwords that are already published. Credential stuffing works because people reuse credentials, and every reused credential in your user base is a successful login waiting for someone with the right list. Screening at password-set time removes that inventory, and it does so without asking users to memorise a symbol requirement that pushes them toward predictable substitutions.

This guide implements screening with k-anonymity range queries, so the password never leaves your process, plus the self-hosted variant for environments where an external call in the credential path is unacceptable. It is part of the Password Storage & Credential Hygiene guide within Secure Authentication & Session Architecture, and it is the supply-side complement to rate limiting login endpoints.

Prerequisites

  • A password-set path you control: registration, change and reset all route through it
  • Outbound network access from that path, or disk space for a local corpus
  • A cache with a short lifetime for repeated prefixes
  • A decision, made before implementation, about what happens when the corpus is unreachable

Expected Outcomes

  • Known-breached passwords refused at the moment they are chosen
  • No password and no full digest ever transmitted off the host
  • Screening latency bounded and cached, with a hard timeout
  • A deliberate, documented failure mode for corpus unavailability

Step 1: Hash Locally, Send a Prefix, Compare at Home

The protocol is three lines of logic and one property worth understanding: the bucket you request contains hundreds of entries, and only you know which one you were asking about.

import hashlib, httpx

RANGE_URL = "https://api.pwnedpasswords.com/range/{prefix}"

async def breach_count(password: str, client: httpx.AsyncClient) -> int:
    digest = hashlib.sha1(password.encode("utf-8")).hexdigest().upper()
    prefix, suffix = digest[:5], digest[5:]          # only the prefix ever leaves the process

    resp = await client.get(RANGE_URL.format(prefix=prefix), timeout=2.0,
                            headers={"Add-Padding": "true"})   # padding hides bucket size
    resp.raise_for_status()

    for line in resp.text.splitlines():              # the bucket: many candidate suffixes
        candidate, _, count = line.partition(":")
        if candidate == suffix:                      # the comparison happens here, locally
            return int(count)
    return 0

Two details are easy to skip and worth keeping. Requesting padding means every response is a similar size, so a network observer cannot infer bucket size from response length. And the timeout is short and explicit, because this call sits in a user-facing path where a hanging dependency is a broken registration form.

What Crosses the Network, and What Does Not The password is hashed inside the application process. Only the first five characters of the digest are sent. The service returns a bucket of several hundred suffixes with counts, learning nothing about which one was of interest. The comparison against the remaining digest characters happens locally, so neither the password nor the full digest ever leaves the host. Inside your process the password, in memory only its full digest, computed locally the suffix comparison and the verdict Nothing here is logged, and nothing here is written to disk at any point. 5 chars bucket What the service sees a five-character prefix, nothing more it returns every suffix in that bucket padded, so size reveals nothing either It cannot tell which entry mattered, or whether any of them did.

Step 2: Apply It at Set Time, With a Useful Message 

MIN_LENGTH = 12
BREACH_THRESHOLD = 1        # any appearance is enough; the corpus is not a popularity contest

async def validate_new_password(user, password: str, client):
    if len(password) < MIN_LENGTH:
        raise ValidationError(f"Use at least {MIN_LENGTH} characters.")
    if password.lower() in derived_from_profile(user):        # name, email local part, company
        raise ValidationError("This is too close to information on your account.")

    try:
        count = await breach_count(password, client)
    except (httpx.TimeoutException, httpx.HTTPError):
        metrics.increment("breach_screen.unavailable")
        if SCREENING_REQUIRED:                                 # decided in advance, see Step 3
            raise ServiceUnavailable("Please try again shortly.")
        flag_for_recheck(user)                                 # allowed, but revisit later
        return

    if count >= BREACH_THRESHOLD:
        raise ValidationError(
            "This password has appeared in a public breach. Choose one you have not used elsewhere."
        )

The message is part of the control. “Appeared in a public breach — choose something you have not used elsewhere” tells the user what happened and what to do; “does not meet complexity requirements” sends them to append an exclamation mark. Never echo the password back and never show the count, which only invites curiosity about the corpus.

The Message Decides What the User Does Next A generic complexity error leads users to append a symbol to the same password, which does nothing about reuse. A message stating that the password appeared in a public breach, and asking for one not used elsewhere, leads to a genuinely different credential — which is the outcome the control exists for. "Does not meet complexity requirements" user response: append an exclamation mark outcome: the same reused password, plus a symbol The credential is still in the corpus an attacker is working from, so nothing has actually changed. "This password appeared in a public breach" user response: choose something else entirely outcome: a credential not in any corpus Say what happened and what to do; never show the count, and never echo the rejected password back.

Step 3: Choose the Failure Mode Before You Need It

Screening is an external dependency in the credential path, so decide what an outage means.

Context Reasonable choice Reasoning
Consumer product registration Allow, flag, re-check later Blocking sign-up over a third-party outage costs more than the residual risk
Password change for an existing account Allow, flag, re-check at next login The account already exists; a weak new password is recoverable
Administrative or privileged accounts Block The population is small, the blast radius is large, and the delay is tolerable
Regulated environment with a mandate Block, or self-host so the dependency is local The requirement is to screen, not to screen when convenient

The flag matters as much as the decision: an allowed-under-outage password should be re-screened on the next successful login, so a temporary outage does not permanently exempt a credential.

Step 4: Self-Host When the Dependency Is Unacceptable

For high-assurance or high-volume systems, keep the corpus local. It is static data, so a probabilistic filter answers in microseconds with a small memory footprint.

from pybloom_live import ScalableBloomFilter

# Built once from the corpus, memory-mapped at boot; ~1% false positive rate.
BREACH_FILTER = load_filter("/opt/corpora/breached-sha1.bloom")

def is_breached_local(password: str) -> bool:
    digest = hashlib.sha1(password.encode()).hexdigest().upper()
    if digest not in BREACH_FILTER:
        return False                    # definitively absent
    return exact_lookup(digest)         # possible match: confirm against the sorted index

A false positive here rejects a password that is not actually breached, which is a mild inconvenience and never a security failure — but confirming against an exact index keeps even that from happening. Schedule the corpus refresh explicitly, because a stale corpus quietly degrades into no screening at all.

Hosted Range Query or Local Corpus The hosted range query needs no storage and stays current automatically, but adds a network call and a third-party availability dependency to the password-set path. The local corpus answers in microseconds with no external dependency and no residual privacy question, at the cost of storage and a refresh cycle you must own. Hosted range query latency: tens to hundreds of milliseconds availability: someone else's uptime freshness: automatic, always current operational burden: essentially none Best for: most consumer products Self-hosted corpus latency: microseconds, in-process availability: yours, no external call freshness: only as good as your refresh job operational burden: storage and a schedule Best for: regulated, air-gapped, high volume

Verification 

# 1. A famously breached password must be refused.
curl -s -o /dev/null -w '%{http_code}\n' -X POST http://localhost:3000/account/password \
  -H "Cookie: $SESSION" -H 'Content-Type: application/json' \
  -d '{"password":"Password123!"}'
# Expected: 400 with a breach-specific message.

# 2. A strong, unique passphrase must be accepted.
curl -s -o /dev/null -w '%{http_code}\n' -X POST http://localhost:3000/account/password \
  -H "Cookie: $SESSION" -H 'Content-Type: application/json' \
  -d '{"password":"tram-vellum-quiet-harbour-92"}'
# Expected: 204.

# 3. Nothing sensitive crosses the wire: inspect the outbound request.
sudo tcpdump -A -s0 -i any 'host api.pwnedpasswords.com' | grep -iE 'GET /range/[0-9A-F]{5}'
# Expected: exactly five hexadecimal characters in the path, and nothing else.

Add a unit test that asserts the request path contains only a five-character prefix — a refactor that “simplifies” the code by sending the whole digest is otherwise invisible in review.

Troubleshooting

Symptom Likely cause Fix
Registration occasionally hangs No timeout on the range request Set a short explicit timeout and handle it as an outage, not an error page
Every password is rejected Digest case mismatch between local computation and the corpus Upper-case the hexadecimal digest before comparing
Screening rejects nothing at all Response parsed as JSON when it is line-delimited text Split on newlines and partition each line at the colon
Latency spikes at peak Every request hits the network Cache buckets briefly; repeated common prefixes are frequent
Users complain about unclear errors Generic validation message State that the password appeared in a public breach and what to do instead
Local filter reports matches for good passwords Bloom false positives without an exact confirmation step Confirm every filter hit against the exact index

Common Implementation Mistakes

Frequently Asked Questions

Does sending a hash prefix leak the password?

A five-character prefix identifies a bucket of several hundred candidate digests, and the comparison of the remaining characters happens entirely inside your process. The service learns that someone asked about a bucket — not which entry was of interest, and certainly not the password. With response padding enabled, even the size of the reply reveals nothing. The residual signal is that a password was being set, which the request itself already implies.

Should screening run at login as well as at password set?

Screen at set time, and treat a login-time match as a signal rather than a block. Corpora grow, so a password that was clean when chosen may appear later; refusing the login at that moment locks a legitimate user out of an account they still own, with no path to fix it. Authenticate them, then require a change before they continue — optionally behind a second factor if the risk signals warrant it.

When is self-hosting the corpus worth it?

When an external dependency in the password-set path is unacceptable: regulated environments, air-gapped deployments, or very high volumes where per-request latency matters. The corpus is large but static, so a local filter plus an exact index answers in microseconds with no network call and no third-party availability risk. The trade is that the refresh cycle becomes yours to schedule — and a corpus nobody refreshes decays into no screening at all.