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

En las entregas anteriores hemos construido el esquema y lo hemos comparado con los protocolos existentes. Si solo se mira el rendimiento y la resistencia a la correlación pasiva, parece una elección sólida. Pero el modelo de amenaza tiene aristas que no aparecen en la tabla comparativa, y conviene ser preciso sobre ellas porque tanto la literatura como la mayoría de los análisis prácticos no lo son suficientemente.

8. Limitaciones y cuestiones abiertas

8.1. Ataque de diccionario fuera de línea a partir de una única consulta

Para la contraseña real, T_real ⊆ Q por construcción. Para cualquier otro candidato, T_c es un conjunto de k índices esencialmente aleatorios en [0, m−1], y la probabilidad de que todos caigan entre los k + d índices de Q es:

(12)

Para los parámetros típicos (k = 10, d = 30, m ≈ 8 × 10⁹) esto es del orden de 10⁻⁸³. El número esperado de candidatos «falsamente compatibles» en cualquier diccionario plausible —10⁹, 10¹², incluso 10²⁰— es esencialmente cero.

La contraseña real es, con probabilidad abrumadora, el único candidato compatible con la consulta observada.

Comparación desde la teoría de la información

Sea 𝒟 el universo de candidatos, con la contraseña distribuida uniformemente. La información mutua filtrada por la consulta es:

(13)

La entropía condicional satisface H(pw | Q) ≈ log₂ 𝔼[|AS(Q)|]. La tabla 2 sintetiza la comparación:

Frente a un adversario enumerador, el esquema de índices ofuscados es indistinguible desde el punto de vista de la teoría de la información de una búsqueda directa del hash: ambos dejan incertidumbre residual nula sobre pw tras una única consulta. k-anonymity preserva H(pw) − 20 bits; OPRF preserva toda la entropía.

Causa raíz. La tupla T(pw) de k índices tiene aproximadamente:

El esquema transmite el superconjunto Q ⊃ T(pw) y, dadas las funciones hash públicas, el adversario identifica T(pw) como el único subconjunto de Q de tamaño k compatible con alguna contraseña de su diccionario. Esto agota los 290 bits en un único paso fuera de línea. Un prefijo SHA-1 de 20 bits filtra, en contraste, exactamente 20 bits.

Esta comparación es válida bajo el modelo de oráculo aleatorio con contraseñas distribuidas uniformemente. Para contraseñas muy comunes (10³ más frecuentes), el prior del adversario ya concentra casi toda la masa de probabilidad, y el valor marginal de la protección de cualquier esquema es bajo. Para contraseñas raras de alta entropía, k-anonymity preserva incertidumbre sustancial; el esquema de índices ofuscados no preserva ninguna.

La propiedad de privacidad útil es por tanto más estrecha que la indistinguibilidad: obliga a que cualquier ataque de extracción sea una búsqueda completa por diccionario en lugar de una divulgación directa, y el ruido determinista impide adicionalmente que esa búsqueda se refine de forma incremental. Eso supone una mejora real en modelos de amenaza dominados por correlación pasiva, pero no es equivalente a la privacidad criptográfica de las OPRF y no debe presentarse como tal.

8.2. Gestión del secreto a largo plazo

Si σ se filtra, todas las consultas pasadas del cliente pueden analizarse retroactivamente: el atacante recalcula N para cada contraseña plausible e identifica qué T era el real. σ debe tratarse como cualquier otra clave a largo plazo: enclave seguro en móvil, almacén de claves del sistema operativo en escritorio, respaldo en hardware cuando sea posible. La rotación periódica de σ mitiga parcialmente la exposición de claves antiguas.

8.3. Actualizaciones del filtro

Un filtro de Bloom básico no admite borrado. Los nuevos datos de filtraciones son compatibles (se establecen más bits), pero correcciones o podas requieren reconstruir el filtro. Para corpus de filtraciones, que son monótonamente crecientes, esto rara vez es un problema. Para casos de uso adyacentes (listas de revocación, listas blancas), un filtro de Bloom contador o un filtro cuco son el sustituto natural con mayor complejidad de implementación.

8.4. Servidor activo o malicioso

El modelo asume un servidor honesto pero curioso. Un servidor malicioso puede devolver bits arbitrarios e inducir falsos negativos —indicar que una contraseña es segura cuando figura en el corpus—. Este es un modo de fallo peor que la pérdida de privacidad descrita, porque el usuario no toma ninguna acción correctiva. La mitigación es un compromiso de árbol de Merkle sobre el filtro con verificación periódica por parte del cliente.

8.5. Correlación entre clientes

Los distintos clientes tienen valores σ diferentes, por lo que dos clientes consultando la misma contraseña producen distintos Q. Sin embargo, un adversario que controle múltiples instancias del cliente (compilaciones comprometidas, extensiones maliciosas) neutraliza esta separación. Es un problema de distribución de software, no de protocolo.

8.6. Adversario cuántico

La construcción depende de las asunciones sobre PRF y funciones hash. El algoritmo de Grover reduce a la mitad el nivel de seguridad efectivo de un hash de n bits. En la práctica, esto no supone urgencia inmediata para construcciones basadas en SHA-256, pero primitivas post-cuánticas basadas en SHAKE u otras pueden sustituirse sin cambios estructurales.

8.7. Problemas abiertos

• ¿Puede modificarse el esquema para recuperar indistinguibilidad formal frente a adversarios enumeradores sin sacrificar el rendimiento del filtro? Una dirección: incorporar σ en la derivación de los índices reales, pero eso requiere un servidor capaz de realizar búsquedas bajo transformaciones específicas de cada cliente —lo que aproxima la propuesta al territorio de las OPRF—.
• ¿Cuál es la forma correcta de caracterizar AS(Q) en función del corpus y el tamaño del ruido cuando las distribuciones de contraseñas no son uniformes e independientes?
• ¿Cómo se combina el esquema con la limitación de tasa? Los límites agresivos encarecen los ataques de enumeración, pero no existe un tratamiento riguroso de esta composición.

9. Cuándo es aplicable este esquema

La construcción de índices ofuscados es una elección razonable cuando se satisfacen aproximadamente todas las condiciones siguientes:

• Alta tasa de consultas por cliente (cientos o miles al día), donde la latencia de OPRF es perceptible y el comportamiento de correlación de k-anonymity en consultas repetidas es inaceptable.
• Clientes con recursos limitados (aplicaciones móviles, extensiones de navegador) que no pueden alojar un corpus local de más de 10 GB.
• Modelo de amenaza dominado por correlación pasiva más que por extracción activa —por ejemplo, un entorno regulado donde el operador actúa de buena fe pero está expuesto a citaciones de registros de actividad—.
• Presupuestos de almacenamiento y complejidad operacional que puedan asumir un filtro de varios gigabytes y reconstrucciones periódicas.

Es la elección incorrecta para:

• Entornos donde la privacidad criptográfica formal es un requisito, no una aspiración. Usar OPRF.
• Entornos donde el corpus es suficientemente pequeño para enviarse a los clientes. Usar búsqueda local.
• Entornos donde los falsos positivos son inaceptables. Usar estructuras de pertenencia exacta.
• Entornos donde la amenaza es un servidor malicioso. Incorporar esquemas de compromiso criptográfico o usar un protocolo diferente.

El resumen honesto es que se trata de un punto de ingeniería en el espacio de diseño —una capa intermedia razonable entre «enviar el prefijo» y «ejecutar criptografía de curva elíptica por consulta»—, no de un avance criptográfico. Merece conocerse y puede emplearse cuando el caso de uso lo justifique; no es un sustituto de la privacidad criptográfica formal cuando es eso lo que exige el modelo de amenaza.

Referencias

1. Bloom, B. H. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7), 1970.
2. Cable, J. Attacks on Have I Been Pwned’s model of k-anonymity. 2018. cablej.io/blog/k-anonymity
3. Cloudflare. Validating Leaked Passwords with k-Anonymity. 2018. blog.cloudflare.com
4. Google. Protect your accounts from data breaches with Password Checkup. 2019. security.googleblog.com
5. Hunt, T. Introducing 306 Million Freely Downloadable Pwned Passwords. 2017. troyhunt.com
6. Lemire, D. Fast random integer generation in an interval. ACM Transactions on Modeling and Computer Simulation, 29(1), 2019.
7. Verizon. 2023 Data Breach Investigations Report. 2023.

Con esta entrega cerramos la serie. Si te interesa el tema y quieres seguir profundizando, las referencias [2] y [4] son particularmente buenas como lecturas complementarias: el análisis de Cable de los ataques al modelo de k-anonymity y la descripción de Google del Password Checkup basado en OPRF.