K-Anonymity Explained
The privacy technique behind breach checking
K-Anonymity: Privacy Through Ambiguity
How do you check if a password has been breached without revealing the password itself? This is the paradox that k-anonymity solves.
The Problem
Naive Approach: Send your password to a server, server checks its database of breached passwords, returns yes/no.
Why This Fails: You just sent your password over the internet to a third party. Even if you trust them, what if their server is compromised? What if they log your request?
You've exposed the very thing you were trying to protect.
The K-Anonymity Solution
K-anonymity uses a clever trick: partial matching.
Instead of sending your full password, you send only a small part of a cryptographic hash. The server responds with all passwords that match that partial hash, and your browser checks locally for an exact match.
The Process (Simple)
Hash your password locally:
- Password: "MySecret123" - SHA-1 Hash: 8cb2237d0679ca88db6464eac60da96345513964
Send only the first 5 characters:
- Hash Prefix: 8cb22
Server responds with ~800 hashes that start with 8cb22
Your browser checks for an exact match locally
What the server learns: Someone is checking some password whose hash starts with 8cb22.
What the server doesn't learn: Which specific password, or even which of the 800+ possibilities.
Why "K-Anonymity"?
The "k" in k-anonymity represents the size of the anonymity set - how many other possibilities you're hiding among.
In our case, k ≈ 800-1000.
Each 5-character hash prefix matches approximately 800-1000 different passwords in the breach database. Your password is one of ~1000 possibilities, making you anonymous within that set.
The larger k is, the more anonymous you are.
Real-World Analogy
Bad Approach (No Anonymity): Walking into a police station and asking, "Do you have a warrant for John Smith at 123 Main St, DOB 1/15/1990?"
K-Anonymity Approach: Asking, "Do you have any warrants for someone with initials J.S.?" The officer hands you a list of 800 people with those initials, and you check privately if your full name is on the list.
The officer learns: Someone is checking for initials J.S. The officer doesn't learn: Which specific person you're inquiring about.
Practical Use: Breach Checker
When you use Redactorr's Breach Checker:
Your password is hashed in your browser (never sent in plaintext)
Only the first 5 characters of the hash are sent to HaveIBeenPwned (HIBP)
HIBP returns ~800 hash suffixes that match that prefix
Your browser compares these locally to find a match
HIBP never sees your actual password or even the full hash
Privacy preserved. Breach checked.
Statistical Guarantees
With SHA-1 hashes (40 hex characters) and 5-character prefixes:
- Total possible hashes: 16^40 (astronomically large)
- Total possible 5-char prefixes: 16^5 = 1,048,576
- Breached passwords in HIBP: ~600 million
- Average matches per prefix: ~600 million / 1 million ≈ 600-1000
Conclusion: Any given query is indistinguishable from ~1000 other queries.
Limitations
K-anonymity is not perfect:
Frequency attacks: If your password is extremely common (e.g., "password123"), the attacker might guess you're checking it because it appears in almost every prefix query.
Correlation attacks: If an attacker monitors multiple queries from the same IP and sees overlapping prefixes, they could narrow down possibilities.
Not full anonymity: The server still knows you checked something. For truly sensitive passwords (e.g., master passwords for password managers), consider offline breach databases.
But for most use cases, k-anonymity provides excellent privacy with minimal trust assumptions.
Why Redactorr Uses K-Anonymity
K-anonymity principle: The breach check sends only a hash prefix, not the full password, API key, or credential.
Industry standard: K-anonymity for password breach checking was pioneered by Troy Hunt (HaveIBeenPwned) and is now recommended by security experts worldwide.
Auditable: The protocol is simple and auditable. Open your browser's DevTools, watch the network requests, and verify that only hash prefixes are transmitted.
Need help?