Comprobación privada de credenciales comprometidas mediante índices ofuscados y filtros de Bloom (2/4)

En la primera entrega dejamos planteado el problema: comprobar si una contraseña aparece en un corpus de filtraciones sin que el servidor que responde aprenda nada útil sobre ella. Vimos por qué el hash directo —incluso con sal, incluso con bcrypt— no resuelve la cuestión, y mencionamos que el esquema que nos ocupa toma una vía distinta: descomponer la búsqueda en muchas subconsultas pequeñas e individualmente insignificantes, y ocultar cuáles son las reales. Toca construirlo.

4. Filtros de Bloom: propiedades relevantes

Un filtro de Bloom es un vector de bits B[0…m−1] junto con k funciones hash h₁, …, h_k que proyectan entradas arbitrarias en [0, m−1]. Para insertar un elemento x, se establece B[h_i(x)] = 1 para cada i. Para comprobar la pertenencia de y, se verifica si B[h_i(y)] = 1 para todos los i.

Tres propiedades son especialmente relevantes para nuestro caso de uso:

1. Ausencia de falsos negativos. Si alguna de las k celdas de y vale cero, y definitivamente no pertenece al conjunto. Es exactamente lo que necesitamos para una respuesta de «definitivamente no comprometida».

2. Tasa de falsos positivos ajustable. Para n elementos insertados, la probabilidad de falso positivo es:

(1)

que se minimiza para k* = (m/n) ln 2, con lo que:

y:

(2)

Para un corpus de 6 × 10⁸ hashes comprometidos y una tasa objetivo de p = 10⁻³, la ecuación (2) da m/n ≈ 14,4 bits por elemento, equivalente a m ≈ 8,6 × 10⁹ bits (≈ 1,08 GB de almacenamiento en el servidor), con un número óptimo de funciones hash k* ≈ 10.

3. Proyección de muchos a uno. Un único bit B[i] = 1 no identifica ningún elemento concreto; con un factor de carga típico, cada celda acumula el residuo de millones de entradas. Esta es la propiedad que hace al esquema relevante para la privacidad: revelar el valor de una sola celda revela muy poco.

La consulta ingenua —el cliente calcula los k índices para su contraseña y los envía al servidor— no aprovecha esta propiedad: revelar el conjunto de k índices es suficiente para identificar pw en cualquier diccionario razonable. La construcción de la siguiente sección intenta recuperar la privacidad por celda añadiendo ruido denegable al conjunto de índices.

5. Índices deterministas ofuscados

5.1. Construcción del protocolo

Sean H una función hash criptográfica, F una función pseudoaleatoria (PRF) y σ un secreto a largo plazo custodiado exclusivamente por el cliente. Para comprobar una contraseña pw:

1. Calcular el hash de la contraseña: h_pw = H(pw).
2. Índices reales: derivar las k posiciones del filtro de Bloom a las que se proyecta la contraseña:
   (3)
3. Índices de ruido: derivar d posiciones adicionales de forma determinista a partir de la contraseña y el secreto del cliente:
   (4)
4. Formar la unión Q = T ∪ N, permutarla de forma determinista (Fisher–Yates inicializado con H(h_pw ‖ σ) y dirigido por un GNPA criptográficamente seguro) y enviarla al servidor.
5. El servidor devuelve B[i] para cada i ∈ Q.
6. El cliente examina únicamente los bits en posiciones de T. Si alguno vale 0, la contraseña es definitivamente segura. En caso contrario, posiblemente comprometida (con probabilidad de falso positivo p del filtro).

5.2. Requisitos de implementación

Generación de índices sin sesgo. La reducción hash mod m introduce un sesgo cuando m no es potencia de dos; este sesgo se convierte en canal lateral observable por el servidor. Dos soluciones:

• Elegir m = 2^t y usar máscara de bits: índice = hash & (m − 1).
• Si m no puede ser potencia de dos, usar la reducción de Lemire: (h · m) >> 64, con paso de rechazo para uniformidad total.

Permutación criptográficamente segura. Usar un PRNG débil (Mersenne Twister, random.shuffle) permite que un adversario con recuperación de semilla identifique los índices reales por su posición. La semilla debe derivarse como SHA-256(h_pw ‖ σ) y el GNPA debe ser ChaCha20, HMAC-DRBG o equivalente.

5.3. Por qué el ruido debe ser determinista

La decisión de diseño central es que N es función determinista de (pw, σ). La alternativa —usar aleatoriedad fresca en cada consulta— parece superficialmente equivalente, pero introduce una vulnerabilidad crítica bajo consultas repetidas.

Con ruido aleatorio, consultas sucesivas producen:

y su intersección converge hacia T. Formalmente: si cada N_i se extrae uniformemente e independientemente de [0, m−1], la probabilidad de que un índice fijo j sobreviva en la intersección de n conjuntos de ruido es:

(5)

El tamaño esperado del ruido superviviente vale:

(6)

Este valor cae por debajo de 1 —la intersección está casi con certeza vacía— cuando n > log m / log(m/d). Para los parámetros representativos d = 30, m = 8 × 10⁹:

(7)

Con ruido determinista, cada consulta sobre la misma contraseña produce el mismo Q. La intersección de n consultas es siempre Q: el servidor no puede acotar progresivamente T por observación repetida, que es precisamente la amenaza que el diseño determinista neutraliza.

5.4. Dimensionamiento del parámetro de ruido d

Bajo el modelo de oráculo aleatorio, cada candidato cae independientemente en AS(Q) con probabilidad:

(8)

El tamaño esperado del conjunto de anonimato (excluyendo la contraseña real, que siempre es compatible) es por tanto:

(9)

Para garantizar una ambigüedad de al menos K candidatos, se requiere:

(10)

La ecuación (10) revela la tensión central del esquema. Para |𝒟| = 10⁹, m = 8 × 10⁹, k = 10 y un objetivo de K = 10³ candidatos (equivalente a la ambigüedad de k-anonimato):

(11)

Una consulta de 2 × 10⁹ índices de 4 bytes supone 8 GB de ancho de banda: nueve órdenes de magnitud por encima del punto de operación práctico de d = 30. Para K = 2 (ambigüedad mínima no trivial) el resultado es d ≈ 1,1 × 10⁹, igualmente inviable.

El exponente 1/k es el hecho estructural clave. Los filtros de Bloom deben su eficiencia espacial a la independencia k veces de sus funciones hash; esa misma propiedad exige que, para que una comprobación de candidato compatible se cumpla aleatoriamente, los k índices elegidos independientemente deban caer en el pequeño conjunto Q. La eficiencia del esquema y su falta de resistencia a la enumeración comparten la misma causa raíz.

En la tercera entrega situaremos el esquema en el mapa: rendimiento (almacenamiento, cómputo, ancho de banda, falsos positivos) y comparación punto a punto con los enfoques existentes —el modelo de k-anonymity de HIBP, OPRF, PSI y la opción de descarga local del corpus—. Es donde se ve dónde encaja la propuesta y dónde no.