¿Por qué las sales hacen que los ataques de diccionario sean “imposibles”?

Actualización: Tenga en cuenta que no estoy preguntando qué es una sal, qué es una tabla de arcoíris, qué es un ataque de diccionario, o cuál es el propósito de una sal. Estoy preguntando: si conoce los usuarios salt and hash, ¿no es bastante fácil calcular su contraseña?

Entiendo el proceso y lo implemento yo mismo en algunos de mis proyectos.

s = random salt storedPassword = sha1(password + s) 

En la base de datos que almacena:

 username | hashed_password | salt 

Cada implementación de salazón que he visto agrega la sal al final de la contraseña o al principio:

 hashed_Password = sha1(s + password ) hashed_Password = sha1(password + s) 

Por lo tanto, un ataque de diccionario de un hacker que valga la pena (ja ja) simplemente ejecutaría cada palabra clave contra las sales almacenadas en las combinaciones comunes enumeradas anteriormente.

Sin duda, la implementación descrita anteriormente simplemente agrega otro paso para el pirata informático, sin resolver realmente el problema subyacente. ¿Qué alternativas hay para evitar este problema o estoy malinterpretando el problema?

Lo único que puedo hacer es tener un algoritmo de combinación secreto que encaje la sal y la contraseña juntas en un patrón aleatorio, o agregue otros campos de usuario al proceso de hash, lo que significa que el pirata informático tendrá que tener acceso a la base de datos Y codificar para un ataque de diccionario para demostrar fructífera. (Actualización, como se señala en los comentarios, es mejor asumir que el pirata informático tiene acceso a toda su información, así que probablemente esto no sea lo mejor).

Permítanme dar un ejemplo de cómo propongo que un pirata informático piratee una base de datos de usuarios con una lista de contraseñas y hash:

Datos de nuestra base de datos pirateada:

 RawPassword (not stored) | Hashed | Salt -------------------------------------------------------- letmein WEFLS... WEFOJFOFO... 

Diccionario común de contraseñas:

  Common Password -------------- letmein 12345 ... 

Para cada registro de usuario, repita las contraseñas comunes y cópielas:

 for each user in hacked_DB salt = users_salt hashed_pw = users_hashed_password for each common_password testhash = sha1(common_password + salt) if testhash = hashed_pw then //Match! Users password = common_password //Lets visit the webpage and login now. end if next next 

Espero que esto ilustre mi punto mucho mejor.

Dadas 10.000 contraseñas comunes y 10.000 registros de usuarios, tendríamos que calcular 100.000,000 hashes para descubrir tantas contraseñas de usuario como sea posible. Puede tomar algunas horas, pero no es realmente un problema.

Actualización sobre Cracking Theory

Asumiremos que somos un servidor web corrupto, que tiene acceso a una base de datos de hash y sales SHA1, junto con su algoritmo para combinarlos. La base de datos tiene 10,000 registros de usuario.

Este sitio afirma ser capaz de calcular 2,300,000,000 hash SHA1 por segundo usando la GPU. (En la situación del mundo real, probablemente sea más lento, pero por ahora usaremos esa cifra citada).

(((95 ^ 4) / 2300000000) / 2) * 10000 = 177 segundos

Dado un rango completo de 95 caracteres ASCII imprimibles, con una longitud máxima de 4 caracteres, dividido por la tasa de cálculo (variable), dividido por 2 (suponiendo que el tiempo promedio para descubrir la contraseña requerirá un promedio del 50% de las permutaciones) por 10,000 a los usuarios les llevaría 177 segundos calcular todas las contraseñas de los usuarios cuya longitud es <= 4.

Vamos a ajustarlo un poco por realismo.

(((36 ^ 7) / 1000000000) / 2) * 10000 = 2 días

Suponiendo que no hay mayúsculas y minúsculas, con una longitud de contraseña <= 7, solo caracteres alfanuméricos, tomaría 4 días resolver 10.000 registros de usuario, y reduje a la mitad la velocidad del algoritmo para reflejar circunstancias generales y no ideales.

Es importante reconocer que se trata de un ataque lineal de fuerza bruta, todos los cálculos son independientes entre sí, por lo que es una tarea perfecta para resolver en múltiples sistemas. (Por ejemplo, es fácil configurar 2 computadoras que ejecutan ataques desde diferentes extremos que equivalen a la mitad del tiempo de ejecución).

Dado el caso de hash recurrentemente, una contraseña 1,000 veces para hacer que esta tarea sea más costosa desde el punto de vista computacional:

(((36 ^ 7) / 1 000 000 000) / 2) * 1000 segundos = 10.8839117 horas

Esto representa una longitud máxima de 7 caracteres alfanuméricos, con una ejecución de menos de la mitad de la velocidad de la cifra citada para un usuario .

Recursivamente hashing 1.000 veces bloquea eficazmente un ataque general, pero los ataques dirigidos a los datos del usuario siguen siendo vulnerables.

Sí, necesitas solo 3 días para sha1 (salt | password). Es por eso que los buenos algoritmos de almacenamiento de contraseñas utilizan hashing de iteración de 1000: necesitará 8 años.

No detiene los ataques de diccionario.

Lo que hace es evitar que alguien que logra obtener una copia de su archivo de contraseña use una tabla de arcoíris para descubrir cuáles son las contraseñas de los hashes.

Eventualmente, puede ser brutalmente forzado, sin embargo. La respuesta a esa parte es forzar a los usuarios a no usar palabras de diccionario como contraseñas (requisitos mínimos de al menos un número o carácter especial, por ejemplo).

Actualización :

Debería haber mencionado esto antes, pero algunos (¿la mayoría?) Los sistemas de contraseñas usan una sal diferente para cada contraseña, probablemente almacenada con la contraseña misma. Esto hace que una sola tabla de arcoiris sea inútil. Así es como funciona la biblioteca crypt de UNIX, y los sistemas operativos modernos tipo UNIX han ampliado esta biblioteca con nuevos algoritmos hash.

Sé con certeza que el soporte para SHA-256 y SHA-512 se agregaron en las versiones más nuevas de GNU crypt.

Para ser más precisos, un ataque de diccionario , es decir, un ataque donde se prueban todas las palabras en una lista exhaustiva, no es “imposible”, pero se vuelve poco práctico : cada bit de sal duplica la cantidad de almacenamiento y cálculo requeridos .

Esto es diferente de los ataques de diccionario precalculados, como los ataques con tablas de arcoíris, donde no importa si la sal es secreta o no.

Ejemplo: con una sal de 64 bits (es decir, 8 bytes) necesita verificar 2 64 combinaciones de contraseñas adicionales en su ataque de diccionario. Con un diccionario que contiene 200,000 palabras, tendrá que hacer

200,000 * 2 64 = 3.69 * 10 24

pruebas en el peor de los casos: en lugar de 200,000 pruebas sin sal.

Un beneficio adicional de usar sal es que un atacante no puede calcular previamente los valores hash de contraseña de su diccionario. Simplemente tomaría demasiado tiempo y / o espacio.

Actualizar

Su actualización supone que un atacante ya conoce la sal (o la ha robado). Esta es, por supuesto, una situación diferente. Aún así, no es posible que el atacante use una tabla de arcoiris pre calculada. Lo que importa aquí es la velocidad de la función hash. Para que un ataque no sea práctico, la función de hashing debe ser lenta. MD5 o SHA no son buenos candidatos aquí porque están diseñados para ser rápidos, los mejores candidatos para los algoritmos hash son Blowfish o algunas variaciones del mismo.

Actualización 2

Una buena lectura sobre la cuestión de asegurar los hashes de contraseña en general (yendo mucho más allá de la pregunta original pero aún interesante):

Suficiente con The Rainbow Tables: lo que debe saber sobre los esquemas de contraseña segura

Corolario del artículo: use hashes salados creados con bcrypt (basado en Blowfish) o Eksblowfish que le permite usar un tiempo de configuración configurable para hacer que el hashing sea lento.

Un diccionario es una estructura donde los valores están indexados por claves. En el caso de un ataque de diccionario precalculado, cada clave es un hash, y el valor correspondiente es una contraseña que da como resultado el hash. Con un diccionario precalculado en la mano, un atacante puede buscar “instantáneamente” una contraseña que producirá el hash necesario para iniciar sesión.

Con sal, el espacio requerido para almacenar el diccionario crece rápidamente … tan rápido, que tratar de precomputar un diccionario de contraseñas pronto se vuelve inútil.

Las mejores sales se eligen al azar de un generador de números aleatorios criptográficos. Ocho bytes es un tamaño práctico, y más de 16 bytes no sirve para nada.


Salt hace mucho más que simplemente “hacer el trabajo de un atacante más irritante”. Elimina toda una clase de ataque: el uso de diccionarios precalculados.

Otro elemento es necesario para asegurar completamente las contraseñas, y eso es “fortalecer las claves”. Una ronda de SHA-1 no es lo suficientemente buena: un algoritmo de hashing de contraseña segura debe ser muy lento computacionalmente.

Mucha gente usa PBKDF2, una función de derivación clave, que retroalimenta los resultados a la función hash miles de veces. El algoritmo “bcrypt” es similar, utilizando una derivación de clave iterativa que es lenta.

Cuando la operación de hash es muy lenta, una tabla precalculada se vuelve cada vez más deseable para un atacante. Pero la sal apropiada derrota ese enfoque.


Comentarios

A continuación se encuentran los comentarios que hice sobre la pregunta.


Sin sal, un atacante no usaría el método demostrado en “Actualización 2”. Simplemente haría una búsqueda en una tabla pre calculada y obtendría la contraseña en O (1) u O (log n) tiempo (n es el número de contraseñas candidatas). La sal es lo que evita eso y lo obliga a utilizar el enfoque O (n) que se muestra en “Actualización 2”.

Una vez reducido a un ataque de O (n), debemos considerar cuánto tarda cada bash. El fortalecimiento de claves puede hacer que cada bash en el ciclo tome un segundo completo, lo que significa que el tiempo necesario para probar contraseñas de 10k en usuarios de 10k se extenderá de 3 días a 3 años … y con solo 10k contraseñas, es probable que contraseñas en ese momento.

Debe tener en cuenta que un atacante utilizará las herramientas más rápidas que pueda, no PHP, por lo que miles de iteraciones, en lugar de 100, serían un buen parámetro para fortalecer las claves. Se debe tomar una gran fracción de segundo para calcular el hash de una contraseña única.

El fortalecimiento de claves es parte de los algoritmos de derivación de clave estándar PBKDF1 y PBKDF2, de PKCS # 5, que hacen grandes algoritmos de ofuscación de contraseñas (la “clave derivada” es el “hash”).

Muchos usuarios de StackOverflow hacen referencia a este artículo porque fue una respuesta a la publicación de Jeff Atwood sobre los peligros de las tablas de arcoiris. No es mi artículo favorito, pero discute estos conceptos con más detalle.


Por supuesto, supones que el atacante tiene todo: sal, hash, nombre de usuario. Supongamos que el atacante es un empleado corrupto de una empresa de hosting que descargó la tabla de usuarios en su sitio de fans de myprettypony.com. Está tratando de recuperar estas contraseñas porque va a dar vuelta y ver si tus fanáticos del pony usaron la misma contraseña en sus cuentas de citibank.com.

Con un esquema de contraseñas bien diseñado, será imposible que este tipo recupere las contraseñas.

El objective de la salazón es evitar la amortización del esfuerzo del atacante.

Sin sal, se puede utilizar una única tabla de entradas de contraseña hash precalculadas (por ejemplo, MD5 de todas las cadenas alfanuméricas de 5 caracteres, fáciles de encontrar en línea) en cada usuario en cada base de datos del mundo.

Con una sal específica del sitio, el atacante tiene que calcular la tabla por sí mismo y luego puede usarla en todos los usuarios del sitio.

Con una sal por usuario, el atacante tiene que gastar este esfuerzo para cada usuario por separado.

Por supuesto, esto no hace mucho para proteger las contraseñas realmente débiles directamente del diccionario, pero protege las contraseñas razonablemente fuertes contra esta amortización.

Además, un punto más importante: el uso de una sal específica del USUARIO evita la detección de dos usuarios con la misma contraseña, sus valores hash coincidirían. Es por eso que muchas veces el hash es hash (sal + nombre de usuario + contraseña)

Si intenta mantener el hash en secreto, el atacante tampoco podrá verificar los hash.

Editar- acabo de notar que el punto principal se hizo en un comentario anterior.

Las sales se implementan para evitar ataques de tablas arcoiris. Una tabla de arcoíris es una lista de hashes precalculados, lo que hace que traducir un hash en su frase sea mucho más simple. Debes entender que la salazón no es efectiva como una prevención moderna para descifrar una contraseña a menos que tengamos un algoritmo de hash moderno.

Entonces digamos que estamos trabajando con SHA1, aprovechando los exploits descubiertos recientemente con este algo, y digamos que tenemos una computadora corriendo a 1,000,000 hashes / second, se necesitarían 5.3 millones de millones de años para encontrar una colisión , así que sí, php puede trabajar 300 por segundo, gran cosa, realmente no importa. La razón por la que saltamos es porque si alguien se molestó en generar todas las frases comunes del diccionario, (2 ^ 160 personas, bienvenidos a las hazañas de la era 2007).

Así que aquí hay una base de datos real, con 2 usuarios que uso para fines de prueba y administración.

 RegistrationTime UserName UserPass 1280185359.365591 briang a50b63e927b3aebfc20cd783e0fc5321b0e5e8b5 1281546174.065087 test 5872548f2abfef8cb729cac14bc979462798d023 

De hecho, el esquema de salazón es su sha1 (tiempo de registro + nombre de usuario). Adelante, dime mi contraseña, estas son contraseñas reales en producción. Incluso puedes sentarte allí y sacar una lista de palabras en php. Enloquecer.

No estoy loco, solo sé que esto es seguro. Por bien de la diversión, la contraseña de la test es test . sha1(sha1(1281546174.065087 + test) + test) = 5872548f2abfef8cb729cac14bc979462798d023

Necesitará generar una tabla rainbow completa perpendida con 27662aee8eee1cb5ab4917b09bdba31d091ab732 solo para este usuario. Eso significa que realmente puedo permitir que mis contraseñas no se vean comprometidas por una única tabla de arcoíris, el hacker necesita generar una tabla rainbow completa para 27662aee8eee1cb5ab4917b09bdba31d091ab732 para la prueba, y otra vez f3f7735311217529f2e020468004a2aa5b3dee7f para briang. Pensemos en los 5.3 millones de millones de años para todos los hashes. Piense en el tamaño de almacenar solo los hashes de 2 ^ 80 (eso es más de 20 yottabytes ), no va a suceder.

No confundas la salazón como un medio para hacer un hash algo que no puedas decodificar, es un medio de evitar que una tabla arcoiris traduzca todas tus contraseñas de usuario. Es imposible en este nivel de tecnología.

La idea detrás del ataque del diccionario es que tome un hash y encuentre la contraseña, desde la que se calculó este hash, sin cálculo hash. Ahora haz lo mismo con la contraseña salada: no puedes.

No usar una sal hace que la búsqueda de contraseñas sea tan fácil como buscarla en la base de datos. Al agregar un atacante de sal hacen un cálculo hash de todas las contraseñas posibles (incluso para el diccionario adjunto, esto aumenta significativamente el tiempo de ataque).

En términos simples: sin salazón, cada contraseña candidata solo debe procesarse una vez para verificarla frente a cada usuario, en cualquier parte del “universo conocido” (colección de bases de datos comprometidas), cuya contraseña se codifica mediante el mismo algoritmo. Con la salazón, si el número de posibles valores de sal supera sustancialmente el número de usuarios en el “universo conocido”, cada contraseña candidata se debe codificar por separado para cada usuario contra el que se probará.

Simplemente poner salting no previene un ataque de hash (fuerza bruta o diccionario), solo lo hace más difícil; el atacante tendrá que encontrar el algoritmo de salazón (que si se implementa correctamente utilizará más iteraciones) o aplicar fuerza bruta al algoritmo, que a menos que sea muy simple, es casi imposible. Salar también descarta casi por completo la opción de búsquedas de tabla arcoiris …

Salt hace que los ataques a la mesa Rainbow sean mucho más difíciles, ya que hace que un hash de contraseña sea mucho más difícil de descifrar. Imagina que tienes una contraseña horrible solo para el número 1. Un ataque de tabla de arcoiris podría crackear esto inmediatamente.

Ahora imagina que cada contraseña en el archivo db está salada con un gran valor aleatorio de muchos caracteres aleatorios. Ahora su pésima contraseña de “1” se almacena en el archivo db como un hash de 1 más un montón de caracteres aleatorios (el salt), por lo que en este ejemplo la tabla rainbow debe tener el hash para algo como: 1.

Entonces suponiendo que su sal es algo seguro y aleatorio, digamos ()% ISLDGHASKLU ( % #% #, la tabla de arcoiris del hacker necesitaría tener una entrada para 1 * ()% ISLDGHASKLU (*% #% #. Ahora usando una tabla de arcoíris incluso esta simple contraseña ya no es práctica.