¿Cuál es la ventaja de tener un algoritmo hash criptográficamente seguro en los hashmaps?

Algunas veces las aplicaciones usan datos no confiables como la clave en un mapa hash. Una implementación simple puede permitir que los datos que no son de confianza causen un ataque de denegación de servicio.

Los mapas hash son rápidos - O (1) - en el mejor de los casos, pero lento - O (n) - en el peor de los casos. Esto se debe a que las claves normalmente están en grupos separados, pero algunos valores pueden resultar en el mismo hash, una colisión, que se maneja mediante una lista enlazada más lenta. Con datos aleatorios, las colisiones serán poco frecuentes. Sin embargo, algunas implementaciones tienen una vulnerabilidad donde los datos maliciosos pueden causar muchas colisiones, lo que hace que el mapa hash sea lento. Hace algunos años hubo un DoS del kernel de Linux debido a esto.

La causa raíz de la vulnerabilidad de Linux fue que el hash era predecible. Se solucionó introduciendo una clave en la función hash que un usuario remoto no sabría. No sé exactamente cómo funcionan los mapas hash de Rust, pero espero que utilicen un tipo similar de hash con clave.

Debes optar por un hash más seguro cada vez que utilices datos no confiables como clave.

Las operaciones de inserción, búsqueda y eliminación en tablas hash tienen el peor comportamiento de O (n). Si un atacante puede elegir claves para ser insertadas en una tabla hash y pueden computar la función hash, entonces eso crea una oportunidad para la denegación de servicio. Todo lo que deben hacer es elegir las claves que se asignan al mismo grupo.

La cita sugiere que el uso de un algoritmo de hash criptográfico (SHA, MD5, Blake, Skein, etc.) resuelve el problema. Esa interpretación es totalmente incorrecta . El algoritmo que utiliza HashMap de Rust se llama SipHash . Es un algoritmo hash. Y es un algoritmo criptográfico. Pero no es una cryptographic-hash-function . El término correcto para SipHash en el mundo de la criptografía es PRF .

La diferencia clave es que (en la criptografía) todos los detalles de una función hash pueden ser de conocimiento público. Un PRF, por otro lado, requiere una clave secreta. Sin la información secreta, no hay forma de anticipar, para ninguna entrada, cuál será la salida. (Todos los demás detalles son públicos.)

Algo como SHA-2 no evitará la denegación de servicio. Será totalmente imparcial para insumos no adversarios. (Debido a que las funciones criptográficas de hash pueden modelarse como oracles aleatorios .) Sin embargo, cualquier persona puede evaluar SHA-2 sin formato, para que alguien pueda encontrar Colisiones en tabla hash por fuerza bruta.

El hecho de que una función hash criptográfica sea resistente a la colisión (con una salida de al menos 256 bits) no se traduce en una falta de colisiones en el caso de las tablas hash. En última instancia, su función hash, para una tabla con cubos n , se reducirá a uno de los valores posibles de n . Por prueba y error, puede encontrar una entrada que se asigna a un grupo específico aproximadamente una vez cada n intentos. Ninguna tabla hash usa suficientes cubos para hacer esto imposible.

El uso de una función hash sin clave es inherentemente vulnerable a la denegación de servicio, sin importar qué tan buena sea la función hash. El hecho de que el atacante y el servidor-con-hash-mapa consulten el mismo oracle permite a un DOSer usar entradas específicamente elegidas para amarrar su CPU.

Los PRF como SipHash no tienen esta vulnerabilidad si se usan correctamente. El servidor utiliza una función / oracle elegida de un grupo de 2 ¹²⁸ posibles funciones. Para explotar una función hash basada en PRF (hash-table-), el atacante debe adivinar cuál de las 2 funciones ¹²⁸ debería usar (una "recuperación de clave") o encontrar un sesgo en el PRF independiente de la clave (una forma de distinguir el PRF de un oráculo aleatorio).

Finalmente, existen matices más confusos que involucran algoritmos hash. Pero resumido simplemente:

• Las funciones hash criptográficas son un subconjunto de todas las funciones hash ordinarias
• Bajo la definición clásica de función hash criptográfica, no se requiere aleatoriedad. Sin embargo, la aleatoriedad es una característica de todas las funciones hash criptográficas de gran nombre de todos modos.
• No todas las PRF son funciones hash criptográficas
• No todas las funciones hash criptográficas son PRF
• Un algoritmo puede tener las propiedades de un PRF y una función criptográfica de hash.
  • Blake2, Skein y KMAC tienen ambos conjuntos de propiedades
  • Las familias SHA-2 y SHA-3 son ejemplos de funciones hash criptográficas (sin clave)
  • SipHash es solo un PRF (y una función hash ordinaria, pero no criptográfica)
• Un PRF se puede construir utilizando funciones hash criptográficas típicas, pero la función hash en sí no es necesariamente un PRF.
• El "hashing aleatorio" y el "hashing universal" son similares a los PRF en algunos aspectos, pero no tienen los mismos requisitos de seguridad.
  • Se pueden crear colisiones incluso si la semilla de MurmurHash3 es aleatoria

Estoy de acuerdo en que es un poco vago y dependerá en gran medida de cómo se utilicen los hashmaps.

Esta es mi suposición: supongamos que está recibiendo información de los usuarios, diga [Firstname.Lastname] y la utiliza como el valor de búsqueda en su tabla hash. Digamos que está construyendo su tabla hash usando la función hash simple que toma las iniciales de manera que [Firstname.Lastname] --> FL , entonces sería fácil para un atacante enviar cargas de valores que todos los hash a la misma cosa. Básicamente, eso convertiría su tabla hash en una lista que niega todas las ganancias de rendimiento de usar una tabla hash. Búsquedas lentas = denegación de servicio.

AA -> [ ]
AB -> [ ]
...
FK -> [ ]
FL -> [First.Last, F1.F2, F1.F2, Fanotheu.Lonteuh, ...]
FM -> [ ]
...
ZZ -> [ ]

Las funciones criptográficas de hash están diseñadas específicamente para evitar esto porque es muy difícil construir dos entradas diferentes que tengan el mismo valor de hash (llamadas colisiones).

  

¿Cuándo debería optar por un hash más seguro en lugar de uno más rápido?

La respuesta es simple: opte por un hash criptográfico cada vez que el valor de búsqueda sea proporcionado por los usuarios y pueda ser creado de manera maliciosa. Si los valores de búsqueda provienen de alguna fuente interna en la que confía que no sea malintencionado y que se distribuya uniformemente, entonces puede usar un hash más rápido.