Ataques de consumo de recursos contra algoritmos

Este ataque se conoce como Hash DoS, o más generalmente como ataque de complejidad algorítmica.

Hay varias formas de implementar tablas de búsqueda:

1. árboles equilibrados
   Las operaciones relevantes tienen un rendimiento logarítmico, independientemente de los datos. Estos son naturalmente inmunes a este ataque, pero son más lentos.
2. Hashtables
   Si los hashes están bien distribuidos, las operaciones relevantes son O (1) y realmente rápidas, pero si están mal distribuidas se convierten en O (n).

Hay dos estrategias comunes para evitar el Hash DoS: puedes cambiar a árboles o usar hashes con clave.

Para los hashes con clave, el servidor elige una clave secreta aleatoria. Dependiendo de la situación, esta clave puede ser por proceso, por tabla, por solicitud, ... Los tiempos de vida más largos pueden permitir ataques adaptables a múltiples solicitudes, pero no estoy seguro de qué tan grande es el problema en la práctica.

Luego utiliza un hash con clave para determinar el grupo, en lugar de una función hash sin clave. Si el hash codificado es bueno, esto evita que el atacante produzca colisiones rápidamente. Los hashes codificados anteriormente a menudo sufrían de colisiones independientes clave, y por lo tanto no evitaban el ataque una vez que se encontraban. Actualmente, SipHash está ganando popularidad, ya que es rápido, pero sigue siendo criptográficamente seguro.

Mi recomendación es usar SipHash y evitar la reutilización de claves en las solicitudes cuando sea posible.

• Breaking Murmur: DoS de inundación de hash Recargado (en el blog de Martin Boßlet)

• SipHash / Attacks

    

  Ataques
    Conjuntamente con Martin Boßlet, demostramos debilidades en MurmurHash (usado en Ruby, Java, etc.), CityHash (usado en Google) y en el hash de Python. Algunas de las tecnologías afectadas han cambiado a SipHash. Consulte esta oCERT advisory y los siguientes recursos:

       

  • Diapositivas de la presentación "DoS de inundación de hash recargado: ataques y defensas" en Application Security Forum Western Switzerland 2012 (Aumasson , Boßlet)
    

• Hash DoS contra BTRFS

• Muchos lenguajes de programación están actualizando sus bibliotecas estándar para evitar Hash DoS. Estos ataques afectan a los idiomas tipificados dinámicamente, ya que suelen utilizar tablas hash en casi todas partes (nombres de miembros a valores, etc.)

  Algunos grandes proyectos que actualizan sus tablas hash:

  • Ruby , JRuby - SipHash
  • Perl - SipHash
  • Haskell - SipHash ,
  • .net : personalizado, probablemente inspirado en SipHash pero parece mucho más débil
  • Redis - SipHash

El error de agotamiento de recursos específico es causado por buffers de transmisión replicados para cada fragmento solicitado. Como tal, una configuración que tiene un búfer de envío de 16kB consumiría realmente 1 MB de memoria si se envían 64 rangos de longitud completa, o 10 MB si envía 640 encabezados de rango. Mientras la conexión se mantenga abierta, los buffers no enviados permanecerán en la memoria. Obviamente, esto se puede utilizar para realizar un DoS efectivo, ya que solo 10 conexiones abiertas con 640 cabeceras de rango podrían consumir hasta 100 MB. Su millaje puede variar en diferentes ajustes de configuración.

No conozco ningún artículo sobre el análisis de seguridad de algoritmos, pero una de las mejores maneras de buscar errores de agotamiento de recursos es identificar cualquier punto en el algoritmo en el que una entrada sin restricciones pueda alterar la cantidad de memoria asignada o dónde el cliente ha realizado significativamente menos trabajo que el servidor.