¿Cómo pueden los crackers reconstruir los hashes de contraseña con sal de 200k tan rápido?

Ninguna de las respuestas existentes cubre la parte crítica de esta pregunta para mi satisfacción: ¿qué pasa con las sales?

Si solo se publicaron los valores de hash de la contraseña, es posible que otros crackers no puedan saberlo:

1. El valor real de sal por contraseña (supuestamente aleatorio, según la fuente).

2. Cómo se mezcla la sal con la contraseña en el código.

¡Todo lo que tienen es el hash final, resultante!

Hay muchas maneras que la contraseña y el salt se pueden combinar para formar el hash:

sha256(pass + salt)
sha256(salt + pass)
sha256(sha256(pass) + sha256(salt))
sha256(pass + sha256(salt))
sha256(sha256(...(salt + pass + salt)...))

Pero si la sal es la recomienda 8 caracteres de pura aleatoriedad ...

sha256("monkey1" + "w&yu2P2@")
sha256("w&yu2P2@" + "monkey1")

... esto significa que una contraseña "típica" de 7 u 8 caracteres se vuelve extremadamente difícil de forzar, ¡porque es efectivamente 15 o más caracteres! Además, para descifrar la contraseña los hashes que sabes están salados, a menos que también tengas sal, no tienes otra opción, excepto fuerza bruta!

Sobre la base de la investigación que realicé utilizando el cracking de GPU , obtuve 8213.6 M c s utilizando dos tarjetas ATI de gama alta, fuerza bruta, craqueo de hashes de contraseña MD5. En mi evaluación comparativa, esto significaba que podía intentar:

all 6 character password MD5s   47 seconds
all 7 character password MD5s   1 hour, 14 minutes
all 8 character password MD5s   ~465 days
all 9 character password MD5s   fuggedaboudit

Tenga en cuenta que SHA-256 es el 13% de la velocidad de MD5 en las GPU que utilizan Hashcat . Así que multiplica estos números por aproximadamente 8 para ver cuánto tiempo tomaría.

Si las sales no se conocían , eso significa que eres esencialmente brutal forzando el equivalente de más de 12 contraseñas de caracteres. Eso está mucho más allá del ámbito de cualquier poder computacional conocido.

Ahora, si quieres argumentar que ...

1. Los crackers originales también obtuvieron las sales, pero optaron por no publicarlas.

2. Los crackers original también tienen el código fuente (o es de código abierto) para que sepan cómo se eliminan las contraseñas, pero decidieron no publicar esa información.

3. Formspring miente y sus contraseñas no fueron tratadas de manera inadecuada, por lo que las sales no tuvieron ningún efecto.

... entonces sí, es fácil descifrar 200k de hashes de contraseña de 400k en unos pocos días.

Editar: Todo lo que sigue a continuación asume que las sales son conocidas, porque esa es la uso estándar de la industria de la palabra sal (tercera línea) .

Como ejemplo de cómo se ve esto a menudo en la base de datos, eche un vistazo a esta Cripta Unix SHA-256 salida:

$5$rounds=80000$wnsT7Yr92oJoP28r$cKhJImk5mfuSKV9b3mumNzlbstFUplKtQXXMo4G6Ep5

.. donde wnsT7Yr92oJoP28r es la sal en texto simple. La documentación de Python Passlib tiene buenas descripciones de muchos formatos comunes de contraseñas con hash , y la mayoría de estos almacena sales de texto simple concatenadas junto con la representación de contraseña hash.

El ' desconocido para el atacante salt' que @Jeff Atwood analiza con frecuencia se llama "pimienta". Consulte Contraseña Hashing ¿agregar sal + pimienta o es suficiente sal?

En 2009, Daniel J. Bernstein escribió una implementación SHA-1 altamente optimizada para el marco CUDA de NVIDIA. En ese entonces, administraban 690 millones de hashes SHA-1 por segundo en un solo servidor usando cuatro tarjetas gráficas.

Los ataques de fuerza bruta contra contraseñas con hash son una carga de trabajo "vergonzosamente paralela" . En 2010, Thomas Roth demostró fuerza bruta atacando ~ 10 hashes por ~ 2 $ utilizando Amazon EC2. Esto podría ampliarse fácilmente, si la tasa no es lo suficientemente alta, simplemente agregue más instancias de EC2.

Entonces, esencialmente no es una cuestión de cuánto tiempo tomará forzar las contraseñas. Es más una cuestión de cuánto poder de cómputo está dispuesto o es capaz de pagar el atacante para obtener resultados más rápidamente.

  

los atacantes afirmaron haber encontrado ~ 200.000 contraseñas

Una explicación razonable es que los atacantes no se dirigieron a las representaciones de hash específicas, simplemente optaron por la "fruta de bajo rendimiento". En otras palabras, solo buscaron contraseñas que sean 'fáciles de adivinar'. Quizás algo como:

• Una lista de candidatos de las contraseñas más comunes en texto sin formato, construida a partir de listas publicadas de contraseñas de usuarios reales. (A lo largo de los años ha habido varias fugas de contraseñas de usuarios reales .)
• Y tal vez, además, probaron todas las contraseñas en minúsculas pronunciadas hasta un límite superior bajo, por ejemplo hasta 6 caracteres. (En el conjunto de datos de MySpace de 2006 anterior, se encontró que el 17% de todas las contraseñas de los usuarios finales tenían 6 o menos caracteres).

  

Mi conjetura es que Formspring estaba mintiendo sobre el hash.

Si entiendo sus enlaces correctamente, los hashes se descubrieron en un foro el 7 de julio. ¿Pero podrían haber sido robados de Formspring semanas o meses antes de eso?

Teniendo en cuenta lo que describo anteriormente, no me parece irrazonable que se haya utilizado una sola ronda de SHA256 con una sal única por contraseña, como dijo Formspring.

Todo depende de cuánto tiempo y esfuerzo pongan los atacantes en el craqueo de fuerza bruta. Pero dentro de los recursos que puede tener un pequeño grupo de hackers individuales, parece plausible descubrir 200.000 contraseñas débiles de un conjunto de datos de 11 millones de representaciones hash SHA-256 simples.

Hacer hash de hash sin sal es bastante trivial: solo busca hash en una tabla precalculada y encuentra su respuesta. No tiene sentido forzar el resto porque las tablas de arco iris ya cubren su diccionario de fuerza bruta.

Pero descifrar contraseñas saladas es todavía simple; Más lento pero aún simple. En la mayoría de los ataques de fuerza bruta, el atacante busca la amplitud, no la profundidad. En lugar de probar mil millones de contraseñas contra 1 cuenta, intenta decenas o cientos o miles de contraseñas comunes contra TODAS las cuentas. Ciertamente, las tablas de arco iris son más rápidas, pero la sal sola no impide la metodología clásica de fuerza bruta. Comience en la parte superior de su diccionario y pruebe esa contraseña con todas las cuentas: esto obviamente implica volver a calcular el hash para cada cuenta, pero, por otro lado, sus posibilidades de éxito son bastante altas (eso es precisamente lo que significa "contraseña común") , de todas formas). Luego, tome su siguiente contraseña más común, luego la siguiente, etc.

Al final, es posible que solo pase por miles de contraseñas, pero estadísticamente hablando, probablemente haya cientos de cuentas con la contraseña "123456" en su lista, y un número bastante grande que usa "password1" y "111111" y "prueba".

200K de 11M es creíble; sólo alrededor del 2%. 200K de 400K menos. No imposible pero no tan probable. La ley de los rendimientos decrecientes comienza en alguna parte; No estoy seguro de cuán lejos está, pero es probable que sea una proporción realmente simple como 1 / e o algo así. Más allá de eso me pongo escéptico.

Es lógico que no estén mintiendo.

1. Como @Jeff señaló que el acceso a la sal es esencial para un rápido craqueo, pero como @ Remus Rusanu señaló: "si obtuvieron los hashes entonces es difícil para mí ver cómo podrían no obtener la sal también", ya que deben almacenarse de tal manera que puedan asociarse entre sí. Asumiría que: al menos los hackers iniciales tenían acceso a la sal. ¹

2. @Jeff también declara que deben tener acceso al código fuente para saber cómo se combinan el salt y la contraseña. Propongo un enfoque diferente para descubrir cómo se combinan el salt y la contraseña:

   1. supongamos que tienen una cuenta de Formpring antes del ataque (una suposición bastante razonable)
   2. busque esa cuenta específica (salt, hash) en la lista obtenida
   3. sabiendo la contraseña, el salt y el hash resultante, debería ser fácil construir un pequeño script para probar todas las formas razonables (y algunas no razonables) de combinar la contraseña y el salt (¿no hay más de unos miles de modos?)
   4. ???
   5. ganancias!

3. afirman tener "decenas de millones de miembros", lo que hace que @Jesper fruta de bajo rendimiento La teoría suena muy razonable.

Ok, todavía pueden estar mintiendo, pero al menos parece razonable que no lo estén.

_{1. Si esta suposición es incorrecta, los piratas informáticos iniciales no publicaron la sal Y no intentaron descifrar las contraseñas por sí mismos; el resto puede no ser posible.}

hashcat puede hacer un poco más de 1 billón de hashes SHA256 por segundo en Radeon HD7970, que es solo la mitad de la velocidad de SHA1 y un cuarto de la velocidad de MD5. Sin embargo, esto ni siquiera es el cuello de botella :

  

Una cosa más antes de seguir adelante; ¿Notó que la velocidad del craqueo fue "solo" 258.7M por segundo? ¿Qué pasó con el rendimiento teórico de un par de miles de millones de hash SHA1 por segundo? El problema es que el rendimiento más alto solo se puede lograr con "mutaciones" de los valores del diccionario de contraseñas o trabajando a través de diferentes posibilidades de contraseñas directamente dentro de la GPU. En otras palabras, si deja que la GPU tome un valor de diccionario y luego lo transforme en una serie de posibilidades diferentes, puede trabajar mucho más rápido. La GPU no puede recibir contraseñas lo suficientemente rápido como para alcanzar el mismo nivel de rendimiento, por lo que efectivamente tener una lista de contraseñas es un cuello de botella.

Por lo tanto, usar SHA256 (o incluso SHA512) no es más seguro que usar SHA1 o MD5 contra este tipo de ataques.

Ninguna publicación menciona si los perpetradores obtuvieron acceso al código fuente de Formspring. Si este fuera el caso, el método de construcción de hash y la generación aleatoria de las sales estaría disponible para los atacantes. Esto haría que la tarea de descifrar sea mucho más fácil, especialmente si el método de generación de las sales "aleatorias" los limitara a valores establecidos relativamente pequeños.

Dada la velocidad aparente con la que se rompió este conjunto limitado, mi mejor conjetura sería que este es el caso.

Si estuvieran usando hashes con un salt único por contraseña, normalmente tomaría un tiempo considerable antes de que uno pudiera descifrar estas contraseñas. A menos que las contraseñas fueran extremadamente débiles o las contraseñas fueran palabras en el diccionario. La fuerza bruta pura parece un poco improbable si fueran fuertes.

El hardware de Tom tiene un artículo sobre contraseña de GPGPU . Las contraseñas débiles ( no más de 10 caracteres, incluidas mayúsculas, minúsculas, signos, ...) se pueden descifrar en cuestión de minutos, incluso con sal si se conoce la sal.

De lo contrario, tomará muchos días, meses, contraseñas más largas, incluso miles de años. Pero esto es sin sal. Con una sal tomará para siempre.