Privacy-Preserving Password Leak Detection with Blind Exponentiation

Password leak detection services like Have I Been Pwned have become essential security tools, allowing users to check if their passwords appear in known data breaches. However, traditional implementations face a critical privacy concern: users must either send their password hash directly to the server or rely on k-anonymity models that reveal partial hash information. Even with prefix-based approaches, these systems leave traces that could enable targeted attacks or privacy violations.

This article proposes an alternative approach using blind exponentiation—a cryptographic protocol that allows password leak checking while protecting both user privacy and the password database integrity. This method prevents dictionary attacks on the server’s breach database while ensuring the server never sees the user’s actual password hash.

The Privacy Problem

Typically, existing password leak detection systems operate under one of two models:

Direct Hash Submission: Users send hash(password) directly to the server. The server compares it against the breach database and responds with a match result. This approach is simple but problematic—the server observes every password hash being checked, creating a searchable log of user security decisions. A compromised server exposes not just breach data but active user behavior patterns.

$k$-Anonymity Model (Have I Been Pwned): Users submit only a hash prefix, typically the first $k$ bytes. The server responds with a list of all compromised hashes that share this prefix. The client then performs a local comparison to verify if their password is listed. A significant security drawback is that the server discloses valid hashes belonging to other users. This exposes sensitive data to the client and enables potential offline dictionary attacks on these unrelated credentials.

Both approaches share a common vulnerability: anyone with access to the breach database can perform unlimited offline dictionary attacks against the leaked passwords.

Blind Exponentiation Protocol

This protocol employs a commutative blinding scheme in a cyclic group where both client and server hold secret exponents. The fundamental security property is that the operations are commutative but computationally hard to reverse due to the Discrete Logarithm Problem.

System Components

• Client Secret ($x$): A large random integer known only to the client, coprime to $p-1$.
• Server Secret ($y$): A large random integer known only to the server, generated fresh for each session (ephemeral).
• Hash ($h$): SHA-256 output of the user’s password, mapped to an integer in the group.
• Prefix: First $k$ bytes of the hash, used for efficient database indexing.
• Modulus ($p$): A large safe prime number defining the finite field $\mathbb{Z}_p$.

Server Setup

Before users can check passwords, the server must populate its breach database with blinded hashes:

1. Data Acquisition: Server obtains leaked password hashes from breach compilations.

2. Prefix Indexing: For each leaked hash $h$, extract prefix = h[0...k] (first $k$ bytes).

3. Database Storage: Store records containing:

   • hash: Full SHA-256 hash of the leaked password
   • prefix: $k$-byte prefix for fast lookup
   • breachId: Source breach identifier (e.g., “example.com_2012”)

The prefix index enables efficient querying. When a client submits a prefix, the server retrieves only the small subset of hashes sharing that prefix rather than scanning the entire database.

CREATE TABLE LeakedPassword (
  id TEXT PRIMARY KEY,
  hash TEXT NOT NULL,
  prefix TEXT NOT NULL,
  breachId TEXT NOT NULL,
  UNIQUE(hash, breachId)
);

CREATE INDEX idx_prefix ON LeakedPassword(prefix);

Client Protocol

When a user wants to check if their password has been compromised, it generates a fresh secret $x$ specifically for this request:

1. Hash Generation: Client computes $h =$ sha256(password)

const sha256 = async (str: string): Promise<string> => {
  const buffer = new TextEncoder().encode(str);
  const hashBuffer = await crypto.subtle.digest('SHA-256', buffer);
  const hashArray = Array.from(new Uint8Array(hashBuffer));
  return hashArray.map((b) => b.toString(16).padStart(2, '0')).join('');
};

const h = await sha256(password);

2. Prefix Extraction: Extract prefix = h.substring(0, 6) (example: 3 bytes / 6 hex chars)

3. Blinding: Compute modular exponentiation: $h^x \pmod p$

import { getDiffieHellman } from 'crypto';
import bigInt from 'big-integer';

const dh = getDiffieHellman('modp14');

// Large prime p (e.g., 2048-bit Safe Prime defined in RFC 3526)
const p = bigInt(dh.getPrime().toString('hex'), 16);

// Client secret x (must be coprime to p-1)
const x = generateSecret();

const hBigInt = bigInt(h, 16);

// Blind the hash: h^x mod p
const hx = hBigInt.modPow(x, p);

4. Transmission: Send pair $(h^x, \text{prefix})$ to server.

The client transmits the blinded hash $h^x$. Unlike multiplication, recovering $h$ from $h^x$ requires solving the Discrete Logarithm Problem, which is computationally infeasible.

Server Protocol

The server processes the client’s request without learning the actual password hash. It generates a fresh secret $y$ specifically for this request:

1. Prefix Lookup: Query database for all hashes matching the client’s prefix:

SELECT hash FROM LeakedPassword WHERE prefix = ?

2. Blinding: For each matching hash $h_i$, compute $h_i^y \pmod p$ using the fresh $y$:

import bigInt from 'big-integer';

// Generate ephemeral server secret y for this session
const y = generateSecret();

const matchingHashes = await db.query(
  'SELECT hash FROM LeakedPassword WHERE prefix = ?',
  [prefix],
);

// Server blinds the candidates: h_i^y
const candidates = matchingHashes.map((hash) => {
  const h = bigInt(hash, 16);
  return h.modPow(y, p).toString(16);
});

3. Double Blinding: Apply server secret to client’s blinded hash: $(h^x)^y = h^{xy} = (h^y)^x \pmod p$

4. Response: Return $(h^{xy}, \{ h_1^y, h_2^y, \dots, h_n^y \})$

The server never observes the unblinded hash $h$. It only sees $h^x$, which appears random.

Client Verification

The client receives the server’s response and performs local verification by removing their own secret $x$.

1. Inverse Exponentiation: Raise the double-blinded value to the modular inverse of $x$:

// Calculate modular inverse of x modulo (p-1)
const xInv = x.modInv(p.minus(1));

const hxy = bigInt(response.hxy, 16);

// Remove client secret: (h^(xy))^(x^-1) = h^y
const hy = hxy.modPow(xInv, p);

This yields $(h^{xy})^{x^{-1}} = h^{(x \cdot x^{-1})y} = h^y$, the server-blinded version of the client’s password hash.

2. Comparison: Check if $h^y$ appears in the candidate list:

const hyHex = hy.toString(16);
const leaked = response.candidates.some((candidate) => candidate === hyHex);

3. Result Display: Inform user whether their password is compromised.

If $h^y$ matches any candidate, the password appears in the breach database. Otherwise, the password is not known to be compromised.

Mathematical Foundation

The protocol’s security relies on the difficulty of the Discrete Logarithm Problem (DLP) and the properties of commutative exponentiation in a finite field.

Blinding Operation

Given:

• Hash $h \in \mathbb{Z}_p$
• Client secret $x$
• Server secret $y$

The blinding transformation is:

$$h \xrightarrow[\text{client}]{} h^x \pmod p \xrightarrow[\text{server}]{} (h^x)^y \equiv h^{xy} \pmod p$$

Commutativity Property

The protocol exploits the commutativity of exponents:

$$(h^x)^y \equiv h^{xy} \equiv (h^y)^x \pmod p$$

This allows the client to obtain $h^y$ by applying the inverse of their secret ($x^{-1}$) to the returned value:

$$(h^{xy})^{x^{-1}} \equiv h^{xy \cdot x^{-1}} \equiv h^{y \cdot 1} \equiv h^y \pmod p$$

The server computes $h_i^y$ for each candidate hash in the database. The client can then safely compare their computed $h^y$ against the list $\{h_1^y, h_2^y, \dots\}$.

Security Properties

Client Privacy: The server observes only $h^x$. Recovering $h$ (or $x$) from $h^x$ requires solving the Discrete Logarithm Problem, which is computationally hard. The server cannot perform dictionary attacks on the user’s query.

Database Protection: The client receives only server-blinded values $\{h_1^y, h_2^y, \dots\}$. Without knowledge of $y$, the client cannot recover the original hashes $\{h_1, h_2, \dots\}$. This prevents the client from harvesting the database.

Unlinkability & Forward Secrecy: Both the client ($x$) and server ($y$) generate fresh secrets for each session. This ensures that even if traffic is intercepted and stored, it cannot be decrypted later if the server is compromised (Forward Secrecy). Additionally, because $y$ changes every time, the list of candidates $\{h_1^y, h_2^y...\}$ appears completely random in every session, preventing the client from correlating results across multiple queries.

Implementation Considerations

Secret Generation

Both client and server secrets must be cryptographically random and large:

// Generate 256-bit cryptographic secret
const generateSecret = (): BigInteger => {
  const bytes = crypto.getRandomValues(new Uint8Array(32));

  let x = bigInt(0);
  for (const byte of bytes) {
    x = x.shiftLeft(8).add(byte);
  }

  // Force the secret to be Odd.
  //
  // The client must compute the modular inverse x^-1 to unblind
  // the response. If x is even, it shares a factor of 2 with the modulus (p-1),
  // making the inverse undefined.
  //
  // If y is even, the exponentiation h^y is not a bijection
  // (it maps h and -h to the same value). This creates collisions where valid
  // safe passwords could falsely match compromised hashes.
  x = x.or(1);

  return x;
};

Database Design

Efficient breach checking requires proper indexing. We assume a production-scale database:

model LeakedPassword {
  id          String   @id @default(uuid())
  hash        String
  prefix      String
  breachId    String

  @@index([prefix])
  @@unique([hash, breachId])
}

The prefix index enables $O(\log n)$ lookup performance. For a production-scale database of 500 million hashes with 3-byte prefixes ($2^{24}$ possible values), each prefix bucket contains approximately $500,000,000 \div 16,777,216 \approx 30$ hashes on average.

Network Efficiency

Typical request/response size:

• Request: ~67 bytes (64-byte blinded hash + 3-byte prefix)
• Response: Variable, ~64 bytes per candidate + 64 bytes for client’s double-blinded hash

With this distribution, a prefix lookup typically retrieves 10–50 candidates, resulting in approximately 1–3 KB responses. This balances network efficiency with a sufficiently large anonymity set.

Limitations

Prefix Information Leakage: The protocol reveals the $k$-byte prefix to the server. While this limits the search space, the server still cannot determine the exact hash within that bucket without breaking DLP.

Server Trust: The protocol assumes the server correctly applies its secret $y$. A malicious server could return random noise or omit specific breaches.

Computational Overhead and Key Management: The protocol uses an ephemeral server secret $y$ for each session to ensure forward secrecy. This requires the server to perform dynamic modular exponentiation for every candidate hash in the prefix bucket. A practical solution involves key rotation with caching, where the server uses a secret $y$ for a fixed time window. This allows the server to cache the blinded database values $\{h_i^y\}$ for that duration, reducing CPU load while preserving forward secrecy for past windows.

Conclusion

Privacy-preserving password leak detection represents a critical balance between security utility and user privacy. The blind exponentiation protocol demonstrates that effective breach checking does not require exposing password hashes or enabling database compromise.

By separating the concepts of “checking for leaks” and “learning leaked passwords,” we create a system where:

• Users discover if their specific password is compromised.
• The service provider operates a useful security tool.
• Neither party gains the ability to attack the other’s sensitive data.