Solución:
Las tablas arco iris se confunden comúnmente con otra técnica más simple que aprovecha una compensación de almacenamiento de tiempo de cómputo en la recuperación de contraseñas: tablas hash.
Las tablas hash se construyen aplicando hash a cada palabra en un diccionario de contraseñas. Los pares de contraseña y hash se almacenan en una tabla, ordenados por valor de 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 de arco iris requiere dos cosas: una función hash y una función de reducción. La función hash para un conjunto dado de Rainbow Tables debe coincidir con la contraseña 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 el hash en Base64 y luego truncarlo a un cierto número de caracteres.
Las mesas Rainbow están construidas con “cadenas” de cierta longitud: 100.000 por ejemplo. Para construir la cadena, elija un valor inicial aleatorio. Luego, aplique las funciones de hash 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 longitud: en este caso 100.000, pero se retiene cada eslabón de la cadena. 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 hash 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 increíblemente rápido (búsqueda binaria) y la persona que crea la tabla hash puede elegir lo que incluye, 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íris tienen la ventaja de que la persona que las construye puede elegir cuánto almacenamiento se necesita seleccionando el número de eslabones en cada cadena. Cuantos más enlaces entre la semilla y el valor final, más contraseñas se capturan. 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ñas 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 son las cadenas, más contraseñas se capturan en ellas, pero se requiere más tiempo para encontrar una contraseña en su interior.
Las tablas hash son buenas para contraseñas comunes, las tablas arcoíris 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 Rainbow Tables.
Hay muchas buenas explicaciones de lo que son las tablas arcoíris, esta, Cómo funcionan las tablas arcoíris, es particularmente buena. Además, el artículo de Wikipedia también tiene una muy buena explicación. Para leer un poco más en profundidad, el artículo definitivo sobre el tema es Making a Faster Cryptanalytic Time-Memory Trade-Off.
Una explicación simple de las Rainbow Tables es que utilizan una técnica de compensación de memoria de tiempo. Lo que significa que en lugar de tomar un valor hash objetivo y un diccionario de palabras, luego hacer un hash de 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 por adelantado (esto puede tomar una mucho tiempo dependiendo del tamaño del diccionario). Pero una vez hecho esto, puede comparar tantos hash como desee con los valores previamente hash en las tablas del arco iris, esto es significativamente más rápido que calcular los hash nuevamente.
La explicación que escribí aquí anteriormente en un esfuerzo por ser breve fue engañosa, ya que no explica el uso de reducciones que utilizan las tablas de arco iris. Para una mejor explicación hasta que reescriba este bit, vea la respuesta de @Crunge.
Puede generar las tablas de arco iris usted mismo utilizando una aplicación como RainbowCrack o puede descargarlas de fuentes como The Shmoo Group, el sitio web del proyecto Free Rainbow Tables, el proyecto Ophcrack y muchos otros lugares, dependiendo del tipo de hashes para los que necesite tablas.
Para protegerse contra un ataque basado en Rainbow Table, el método más eficaz para combatirlo es asegurarse de que cada hash dentro de un sistema esté salado. Esto hace que las tablas arcoíris pregeneradas sean inútiles y significaría que un atacante tendría que generar un conjunto personalizado de tablas para usar contra los hashes específicos, lo que solo sería posible si conocieran la sal.
Objeto y relevancia
Las tablas de 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 almacenaban históricamente como hashes simples en bases de datos, y eso es contra lo que son efectivas las tablas de arco iris: crea una sola tabla de arco iris (lento) y ejecuta cualquier cantidad de bases de datos llenas de hashes (rápido).
En estos días, cada vez más sistemas utilizan algoritmos de almacenamiento de contraseñas adecuados, como Bcrypt, Scrypt o Argon2. Consulte: Cómo [store] contraseñas? Esos algoritmos ya no son “vulnerables” a las tablas de arco iris: dado que 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íris son impopulares en la actualidad. 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 de arcoíris.
Cómo trabajan ellos
Creando una mesa
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 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
Empezamos con 0 porque es la primera cadena (solo necesitamos algo de valor para empezar). Cuando hash esto con MD48, se convierte en cfcd208495d5. Ahora aplicamos una función “reducir” que básicamente formatea este hash de nuevo en una contraseña, y terminamos con “z”. Cuando volvemos a hacer hash, obtenemos fbade9e36a3f, luego redúzcalo de nuevo 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 de arcoíris completa ahora es esta:
WLgOSj => 0
0uUoAD => 1
Eso es todo lo que tienes que almacenar.
Buscando un hash
Digamos que encontramos un hash en línea 7668b2810262. ¡Vamos a romperlo 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 él usted mismo, los ejemplos anteriores se crearon utilizando este script de Python: 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.
- Tablas más pequeñas significan búsquedas más lentas o peor cobertura.
En las siguientes secciones se asume que el tiempo por hash + reducción es de 1 µs y no tiene en cuenta las colisiones. Todos estos son números aproximados, que son 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 10000 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 lleva una media 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, es posible que tengamos 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 miramos hacia arriba como cuando generamos una sola cadena. Por lo tanto, el tiempo de búsqueda es 10 000 veces un microsegundo, que son diez milisegundos (o un centisegundo, si se quiere).
Requisitos de almacenamiento
Cuando desee crear una tabla de búsqueda rápida y completa para una función hash, incluso MD5, aún necesitará cien mil millones de terabytes de almacenamiento. Eso no es de mucha ayuda. 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 asumiendo 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 tienen 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 es 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 se puede comparar una tabla de este tipo con el espacio de contraseña que cubre: las búsquedas toman solo 30 segundos y solo tiene que almacenar datos de 76MiB.
Conclusión
Las tablas de arco iris se pueden considerar una compensación de tiempo-memoria: 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 de arco iris solo puede recuperar una contraseña salada si la tabla contiene una entrada lo suficientemente grande como para contener tanto la sal como la contraseña, que sería extremadamente ineficaz y frustra 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 de arco iris para descifrar los archivos. Digamos que el software usa AES, y el primer bloque del archivo debería descifrarse para “corregir contraseña” usando la contraseña proporcionada por el usuario, luego una tabla de arco iris usaría AES en lugar de una función hash.
Siempre que maneje una contraseña (un secreto que es de fuerza desconocida, y especialmente si el usuario puede volver a usarlo), siempre ejecútelo a través de un algoritmo de almacenamiento de contraseña adecuado (lento) para que sea lento y único de descifrar.