it-swarm-es.com

¿Qué son las mesas Rainbow y cómo se usan?

¿Dónde puedo encontrar uno? ¿Hay una olla de oro al final?
¿Cómo me protejo contra ellos?


Del propuesta Area51

Esta pregunta fue Pregunta de seguridad de TI de la semana.
Lea el 09 de septiembre de 2011 entrada del blog para más detalles o envíe el suyo Pregunta de la semana.

149
AviD

Las tablas del arco iris se confunden comúnmente con otra técnica más simple que aprovecha una compensación de almacenamiento de tiempo de cálculo en la recuperación de contraseña: tablas hash.

Las tablas hash se construyen mediante el hash de cada palabra en un diccionario de contraseñas. Los pares de contraseña-hash se almacenan en una tabla, ordenados por valor hash. Para usar una tabla hash, simplemente tome el hash y realice una búsqueda binaria en la tabla para encontrar la contraseña original, si está presente.

Las tablas del arco iris son más complejas. La construcción de una tabla Rainbow requiere dos cosas: una función de hashing y una función de reducción. La función de hash para un conjunto dado de Rainbow Tables debe coincidir con la contraseña de hash que desea recuperar. La función de reducción debe transformar un hash en algo utilizable como contraseña. Una función de reducción simple es codificar Base64 el hash, luego truncarlo a un cierto número de caracteres.

Las mesas arcoiris están construidas con "cadenas" de cierta longitud: 100,000 por ejemplo. Para construir la cadena, elija un valor semilla aleatorio. Luego aplique las funciones de hashing y reducción a esta semilla y su salida, y continúe iterando 100,000 veces. Solo se almacenan la semilla y el valor final. Repita este proceso para crear tantas cadenas como desee.

Para recuperar una contraseña usando Rainbow Tables, el hash de la contraseña se somete al proceso anterior por la misma duración: en este caso 100,000 pero cada enlace en la cadena se retiene. Cada eslabón de la cadena se compara con el valor final de cada cadena. Si hay una coincidencia, la cadena se puede reconstruir, manteniendo tanto la salida de cada función de hashing como la salida de cada función de reducción. Esa cadena reconstruida contendrá el hash de la contraseña en cuestión, así como la contraseña que la produjo.

Los puntos fuertes de una tabla hash son que recuperar una contraseña es muy rápido (búsqueda binaria) y la persona que construye la tabla hash puede elegir lo que contiene, como las 10.000 contraseñas principales. La debilidad en comparación con Rainbow Tables es que las tablas hash deben almacenar cada par de hash-contraseña.

Rainbow Tables tiene el beneficio de que la persona que construye esas tablas puede elegir cuánto almacenamiento se requiere seleccionando el número de enlaces en cada cadena. Cuantos más enlaces entre la semilla y el valor final, se capturan más contraseñas. Una debilidad es que la persona que construye las cadenas no elige las contraseñas que capturan, por lo que Rainbow Tables no se puede optimizar para contraseñas comunes. Además, la recuperación de contraseña implica calcular largas cadenas de hashes, lo que hace que la recuperación sea una operación costosa. Cuanto más largas son las cadenas, más contraseñas se capturan en ellas, pero se necesita más tiempo para encontrar una contraseña dentro.

Las tablas hash son buenas para contraseñas comunes, las tablas Rainbow son buenas para contraseñas difíciles. El mejor enfoque sería recuperar tantas contraseñas como sea posible utilizando tablas hash y/o descifrado convencional con un diccionario de las N contraseñas principales. Para los que quedan, use las Tablas Rainbow.

180
Crunge

Hay muchas buenas explicaciones de lo que son las tablas Rainbow, esta Cómo funcionan las tablas Rainbow es particularmente buena. También artículo de Wikipedia tiene una muy buena explicación también. Para leer un poco más en profundidad, el documento definitivo sobre el tema es Hacer un intercambio criptoanalítico de memoria de tiempo más rápido .

Una explicación simple de Rainbow Tables es que hacen uso de una técnica de intercambio de memoria de tiempo. Es decir, en lugar de tomar un valor hash objetivo y un diccionario de palabras, luego hash cada palabra y hacer la comparación sobre la marcha (enfoque de fuerza bruta usando algo como John ), en su lugar hash todos los valores en el diccionario de antemano (esto puede llevar mucho tiempo dependiendo del tamaño del diccionario). Pero una vez hecho esto, puede comparar tantos hashes como desee contra los valores pre hash en las tablas Rainbow, esto es significativamente más rápido que calcular los hashes nuevamente.

La explicación que escribí aquí anteriormente en un esfuerzo por ser breve fue engañosa, ya que no explicaba el uso de las reducciones que utilizan las tablas Rainbow. Para una mejor explicación hasta que reescriba este bit, vea @ Respuesta de Crunge .

Puede generar las tablas Rainbow usted mismo utilizando una aplicación como RainbowCrack o puede descargarlas de fuentes como The Shmoo Group , Free Rainbow Tables project sitio web, Ophcrack proyecto y muchos otros lugares según el tipo de hashes para los que necesita tablas.

Para protegerse contra un ataque basado en Rainbow Table, el método más efectivo para combatirlo es asegurarse de que cada hash dentro de un sistema sea salado . Esto hace que las tablas Rainbow generadas previamente sean inútiles y significaría que un atacante tendría que generar un conjunto personalizado de tablas para usar contra los hashes objetivo, lo que solo sería posible si conocieran la sal.

15
Mark Davidson

Propósito y relevancia

Las tablas Rainbow ayudan a descifrar contraseñas difíciles, es decir, aquellas que ni siquiera se pueden encontrar en un diccionario grande. Las contraseñas se almacenaron históricamente como hashes simples en bases de datos, y eso es contra lo que las tablas Rainbow son efectivas: cree una sola tabla Rainbow (lenta) y ejecute cualquier cantidad de bases de datos llenas de hashes contra ella (rápido).

En la actualidad, cada vez más sistemas utilizan algoritmos de almacenamiento de contraseña adecuados, como Bcrypt, Scrypt o Argon2. Consulte: ¿Cómo [almacenar] contraseñas de forma segura? Esos algoritmos ya no son "vulnerables" a las tablas Rainbow: dado que cada hash es único, incluso si las contraseñas son iguales, las tablas Rainbow ya no funcionan.

Es por eso que las mesas Rainbow no son populares hoy en día. Incluso si no se usa algo moderno como Argon2, los desarrolladores de hoy en día generalmente saben que al menos deberían usar una sal. Eso ya es suficiente para inutilizar una mesa Rainbow.

Cómo trabajan ellos

Crear una tabla

Imagine que creamos una tabla Rainbow con solo dos cadenas, cada una de longitud 5. La tabla Rainbow es para la función hash ficticia MD48, que genera 48 bits (solo 12 caracteres hexadecimales). Al construir la cadena, vemos esto:

Chain 0: 0=cfcd208495d5 => z=fbade9e36a3f => renjaj820=7668b2810262 => aL=8289e8a805d7 => ieioB=2958b80e4a3a => WLgOSj
Chain 1: 1=c4ca4238a0b9 => ykI4oLkj=140eda4296ac => Dtp=1b59a00b7dbe => W=61e9c06ea9a8 => 6cBuqaha=d4d2e5280034 => 0uUoAD

Comenzamos con 0 porque es la primera cadena (solo necesitamos un poco de valor para empezar). Cuando analizamos esto con MD48, se convierte en cfcd208495d5. Ahora aplicamos una función "reducir" que básicamente formatea este hash en una contraseña, y terminamos con "z". Cuando volvemos a eso, obtenemos fbade9e36a3f, luego reduzca nuevamente y obtenga renjaj820. Hay algunos ciclos más, y el resultado final es WLgOSj.

Lo mismo para la segunda cadena. Simplemente comenzamos con otro valor y hacemos lo mismo. Esto termina en 0uUoAD.

Nuestra tabla completa de Rainbow es ahora esta:

WLgOSj => 0
0uUoAD => 1

Eso es todo lo que tienes que almacenar.

Buscar un hash

Digamos que encontramos un hash en línea, 7668b2810262. ¡Vamos a descifrarlo usando nuestra mesa!

Looking for hash '7668b2810262', reduced to 'aL'.
hashed=>reduced 'aL' to ieioB
hashed=>reduced 'ieioB' to WLgOSj
Found a match, 'WLgOSj' is in our Rainbow table:
    WLgOSj => 0
The chain starts with '0'. Let's walk that chain and look for the hash.
hashed '0' to cfcd208495d5
hashed 'z' to fbade9e36a3f
hashed 'renjaj820' to 7668b2810262
That hash matches! Found the password: renjaj820

Para jugar con usted mismo, los ejemplos anteriores se crearon usando este Python script: https://Gist.github.com/lgommans/83cbb74a077742be3b31d33658f65adb

Propiedades de escala

En breve:

  • Las búsquedas rápidas significan tablas más grandes, suponiendo que la cobertura se mantenga igual.
  • Una mejor cobertura significa búsquedas más lentas o tablas más grandes.
  • Las tablas más pequeñas significan búsquedas más lentas o peor cobertura.

Las siguientes secciones suponen que el tiempo por hash + reducción es 1 µs, y no tiene en cuenta las colisiones. Todos estos son números de estadio, como ejemplos y no como valores exactos.

Tiempo de búsqueda

Si una operación de reducción hash + toma un microsegundo, generar una tabla con un millón de cadenas y 10 000 reducciones por cadena tomaría aproximadamente 3 horas:
chain_length × chain_count / reductions_per_second / seconds_per_hour
= 10 000 × 1 000 000 / 1 000 000 / 3600 = 2.8 horas.

Hacer una búsqueda en esa tabla toma un promedio de 10 milisegundos. Esto se debe a que normalmente tendremos que pasar por chain_length/2 reducciones antes de encontrar qué cadena contiene el hash. Por ejemplo, podríamos tener que hacer 3000 reducciones en un hash antes de encontrar un valor que esté en la tabla. Luego, tenemos que rehacer esa cadena desde el principio hasta que encontremos el valor correspondiente. Si solo tuvimos que hacer 3000 para encontrarlo en nuestra tabla, entonces debemos hacer 7000 reducciones desde el principio para llegar al punto correcto de la cadena. Básicamente, hacemos tantas operaciones cuando miramos hacia arriba como cuando generamos una sola cadena. Por lo tanto, el tiempo de búsqueda es de 10 000 veces por microsegundo, que es de diez milisegundos (o un centisegundo, si lo desea).

Requisitos de almacenamiento

Cuando desee hacer una tabla de búsqueda rápida y completa para una función hash, incluso MD5, aún necesitará cien mil millones de billones de terabytes de almacenamiento. Eso no es muy útil. Pero, ¿qué pasa si queremos cubrir solo contraseñas en minúsculas hasta 10 caracteres?

Si queremos pasar como máximo 30 segundos buscando un hash, y suponiendo que necesitamos 1 microsegundo (una millonésima de segundo) por hash + ciclo de reducción, entonces podemos tener una longitud de cadena de: 1 million × 30 = 30 millones. Hay 2610 (o 1014) posibles contraseñas en minúsculas de 10 caracteres, y por cadena cubrimos 30 millones de valores. Eso nos deja con 4 millones de cadenas. Sabemos que cada cadena tiene solo un valor inicial y final almacenado, y que los valores son de 10 caracteres cada uno. Entonces 2 × 10 × 4 million = 76 datos MiB.

Generar la tabla iterando a través de todas las contraseñas de 10 caracteres lleva mucho tiempo: 30 segundos por cadena, multiplicado por 4 millones de cadenas, son aproximadamente 91 años. Sin embargo, mucha gente estaría interesada en una tabla de este tipo, por lo que al agrupar 1092 CPU (= 91 × 12), solo lleva 1 mes. Esto muestra cuán pequeña puede compararse dicha tabla con el espacio de contraseña que cubre: las búsquedas tardan solo 30 segundos y solo tiene que almacenar datos de 76MiB.

Conclusión

Las tablas de arco iris pueden considerarse un compensación de memoria de tiempo : uno almacena solo una pequeña parte de la tabla y la recupera a través de algún cálculo adicional en el tiempo de búsqueda. Esta es parte de la razón por la cual las sales, o mejor dicho, un buen algoritmo de almacenamiento de contraseñas como Scrypt o Argon2 son importantes para mantener las contraseñas seguras. Una tabla Rainbow solo puede recuperar una contraseña con sal si la tabla contiene una entrada lo suficientemente grande como para contener tanto la sal como la contraseña, lo que sería ¡extremadamente ineficiente y anula todo el propósito.

Tenga en cuenta que algo similar se aplica con el cifrado: cuando las personas cifran archivos con una contraseña, se puede construir una tabla Rainbow para descifrar los archivos. Digamos que el software usa AES, y el primer bloque del archivo debe descifrar para "corregir con contraseña" usando la contraseña proporcionada por el usuario, luego una tabla Rainbow usaría AES en lugar de una función hash.

Siempre que maneje una contraseña (un secreto que tiene una fuerza desconocida, y especialmente si el usuario puede volver a usarla), siempre ejecútelo a través de un algoritmo de almacenamiento de contraseña adecuado (lento) para hacerlo lento y único para descifrar.

7
Luc