¿Qué son las tablas de arco iris y cómo se usan?

Las tablas arco iris se confunden comúnmente con otra técnica más simple que aprovecha un compromiso de almacenamiento de tiempo de cómputo en la recuperación de contraseñas: tablas hash.

Las tablas hash se construyen mediante hashing de cada palabra en un diccionario de contraseñas. Los pares de contraseña-hash se almacenan en una tabla, ordenados por valor de hash. Para usar una tabla hash, simplemente toma el hash y realiza 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 de arco iris requiere dos cosas: una función de hashing y una función de reducción. La función de hashing 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 en base64 el hash, luego truncarlo a un cierto número de caracteres.

Las tablas de arco iris se construyen con "cadenas" de cierta longitud: 100,000, por ejemplo. Para construir la cadena, elige 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. Sólo 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 experimenta el proceso anterior con la misma longitud: en este caso, 100,000, pero cada enlace en la cadena se mantiene. Cada enlace en 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 generó.

Las fortalezas de una tabla hash son que la recuperación de una contraseña es muy rápida (búsqueda binaria) y la persona que crea 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 y contraseña.

Las tablas arco iris tienen el beneficio de que la persona que construye esas tablas puede elegir la cantidad de almacenamiento requerido al seleccionar el número de enlaces en cada cadena. Cuantos más enlaces entre la semilla y el valor final, más contraseñas se capturan. Un punto débil es que la persona que construye las cadenas no elige las contraseñas que captura, por lo que Rainbow Tables no puede optimizarse para contraseñas comunes. Además, la recuperación de la contraseña implica el cálculo de largas cadenas de hashes, lo que hace que la recuperación sea una operación costosa. Cuanto más largas sean las cadenas, más contraseñas se capturarán en ellas, pero se necesitará más tiempo para encontrar una contraseña dentro.

Las tablas hash son buenas para las contraseñas comunes, las tablas arcoiris son buenas para las 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 aquellos que permanecen, use tablas de arco iris.

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

Una explicación simple de Rainbow Tables es que utilizan una técnica de intercambio de memoria temporal. Signifique en lugar de tomar un valor hash de destino y un diccionario de palabras, luego mezcle cada palabra y haga la comparación sobre la marcha (enfoque de fuerza bruta utilizando algo como John ), en cambio, 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 de hash prehispuestos en las tablas del arco iris, esto es significativamente más rápido que calcular los hashes de nuevo.

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 de arco iris. Para una mejor explicación hasta que reescriba este bit, vea Respuesta de @Crunge .

Puede generar las tablas del arco iris usted mismo utilizando una aplicación como RainbowCrack o puede descargarlas de fuentes como El Grupo Shmoo , Sitio web gratuito del Rainbow Tables , Ophcrack y muchos otros lugares, dependiendo del tipo de hashes que necesite para las 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 salados . Esto hace que las tablas arcoiris 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 dirigidos, lo que solo sería posible si supieran la sal.

Propósito y relevancia

Las tablas arco iris 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 las bases de datos, y eso es contra lo que son efectivas las tablas rainbow: crear una tabla rainbow única (lenta) y ejecutar cualquier cantidad de bases de datos llenas de hashes contra ella (rápida).

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

Es por eso que las tablas de arco iris son impopulares hoy. Incluso si no se usa algo moderno como Argon2, los desarrolladores hoy en día generalmente saben que deberían usar al menos una sal. Eso ya es suficiente para hacer una mesa de arco iris inútil.

Cómo funcionan

Creando una tabla

Imagine que creamos una tabla de arco iris con solo dos cadenas, cada una de longitud 5. La tabla de arco iris es para la función de 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 algo de valor para empezar). Cuando hacemos hash con MD48, se convierte en cfcd208495d5 . Ahora aplicamos una función de "reducción" que básicamente formatea este hash nuevamente en una contraseña, y terminamos con "z". Cuando volvemos a hacer eso, obtenemos fbade9e36a3f , luego lo reducimos de nuevo y obtenemos 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 del arco iris es ahora esto:

WLgOSj => 0
0uUoAD => 1

Eso es todo lo que tienes que almacenar.

Buscando un hash

Digamos que encontramos un hash en línea, 7668b2810262 . ¡Rompámoslo 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 contigo mismo, los ejemplos anteriores se crearon usando este script de Python: enlace

Propiedades de escalado

En resumen:

• 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 una cobertura peor.

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

Tiempo de búsqueda

Si una operación de reducción de 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 en promedio 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. A continuación, tenemos que volver a hacer esa cadena desde el principio hasta que encontremos el valor coincidente. Si solo tuviéramos 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 buscamos como cuando generamos una sola cadena. Por lo tanto, el tiempo de búsqueda es 10 000 veces por microsegundo, que es de diez milisegundos (o un centisegundo, si lo desea).

Requisitos de almacenamiento

Cuando desee crear una tabla de búsqueda rápida y completa para una función hash, incluso MD5, todavía necesitará cien mil millones de billones de terabytes de almacenamiento. Eso no es de mucha ayuda. Pero, ¿y si queremos cubrir solo las contraseñas en minúscula hasta 10 caracteres?

Si queremos gastar a lo sumo 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 26 ¹⁰ (o 10 ¹⁴ ) 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 solo tiene almacenados un valor inicial y final, y que los valores son de 10 caracteres cada uno. Entonces, 2 × 10 × 4 million = 76 datos de MiB.

Por supuesto, la generación de la tabla mediante la iteración de todas las contraseñas de 10 caracteres lleva mucho tiempo, pero se puede paralelizar y muestra cuán pequeña puede compararse con el espacio de contraseñas que cubre.