¿Qué son las tablas arcoíris y cómo se utilizan?

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

Las tablas hash se construyen usando hash para 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 arco iris son más complejas. Construir una tabla 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 que se pueda utilizar como contraseña. Una función de reducción simple es Base64 codificar el hash, luego truncarlo a un cierto número de caracteres.

Las tablas Rainbow están construidas con «cadenas» de cierta longitud: 100.000 por ejemplo. Para construir la cadena, elija un valor de semilla 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 utilizando Rainbow Tables, el hash de la contraseña se el proceso anterior para 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 construye la tabla hash puede elegir qué 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 Rainbow tienen 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, 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 calcular 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 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 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.

Comentarios

• Oh, Dios mío, admito que me sorprendí – hablo y explico todas las tablas Rainbow tiempo, y todo este tiempo parece que he sido uno de los » comúnmente confundidos «. Lo haría totalmente +1000 veces, realmente aprendí algo nuevo aquí (y pensé que sabía la respuesta). Me alegro de haber hecho la pregunta después de todo … ¡Gracias!
• Aunque para ser específico (ahora que abriste mis ojos, investigué un poco más :)), Rainbow Tables se diferencia de Hellman Hash Chains al usar varias funciones de reducción diferentes. Más complejo de hecho … pero realmente una idea bastante hermosa (¡Ah! ¿Es ese por qué ‘ se les llama » Rainbow » tablas?)
• Estoy de acuerdo en que esta es una muy buena explicación. En mi respuesta lo expliqué de manera simple y también realmente lo expliqué mal por ser demasiado simple.La belleza de las tablas Rainbow es el hecho de que no ‘ t almacenan todos los valores hash. Voy a editar el mío, pero también votaré esto, ya que definitivamente es una mejor explicación.
• Hmm … Aunque cuanto más lo pienso, en los sistemas de la vida real, las tablas arcoíris no son tan útiles como tablas hash. Como dijiste, para las contraseñas comunes, las tablas hash son mucho mejores (ya que son un orden de magnitud más rápidas, y los requisitos de tamaño para un diccionario de contraseñas son, por supuesto, mucho más pequeños que todo el rango posible de contraseñas). ¿Y a quién ‘ estamos engañando? La mayoría de las contraseñas entran en esa categoría, es muy raro (y será por algún tiempo) que necesite llamar en RT.
• Desafortunadamente, me perdió aquí: » Para recuperar una contraseña usando Rainbow Tables, la contraseña pasa por el proceso anterior por la misma longitud. » ¿Cómo puede la contraseña pasar por el proceso cuando ‘ ¿ni siquiera se conoce? ¿Quiso decir el hash de la contraseña? Además, hay ‘ esto: » Cada eslabón de la cadena se compara con el valor final de cada cadena. » No puedo ver una situación en la que un eslabón de la cadena coincidiría con el valor final de la cadena, ya que el valor del enlace se reduciría y reduciría continuamente.

Hay muchas buenas explicaciones de qué son las tablas de arco iris, esta Cómo funcionan las tablas de arco iris es particularmente bueno. 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 Cómo hacer un intercambio criptoanalítico más rápido entre tiempo y memoria .

Una explicación simple de Rainbow Tables es que hacen uso de una técnica de compensación de memoria de tiempo. Es decir, en lugar de tomar un valor hash objetivo y un diccionario de palabras, luego aplicar un hash a cada palabra y hacer la comparación sobre la marcha (enfoque de fuerza bruta con algo como John ), en su lugar, utiliza el hash de todos los valores del diccionario por adelantado (esto puede llevar mucho tiempo dependiendo del tamaño del diccionario). Pero una vez hecho esto, puede comparar tantos hashes como desee con los valores previamente hash en las tablas del arco iris, 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 era engañoso, ya que no explicaba el uso de reducciones que utilizan las tablas de arco iris. Para una mejor explicación hasta que reescriba este bit, vea respuesta @Crunge .

Puede generar las tablas del arco iris usted mismo usando una aplicación como RainbowCrack o puede descargarlos de fuentes como The Shmoo Group , Sitio web gratuito del proyecto Rainbow Tables , proyecto Ophcrack y muchos otros lugares, según el tipo de hashes para el que necesites 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 sea 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.

Comentarios

• Además (considere editar esto en), si usa una sal diferente para cada contraseña, registrándola sin cifrar en la base de datos, entonces la atacado necesitaría generar un conjunto personalizado de tablas para cada hash, lo que derrotaría el objeto del ejercicio: el objetivo de la tabla del arco iris es forzar todo el espacio de contraseña y luego obtener todas las contraseñas para una fuerza bruta esfuerzo; si ‘ solo obtiene una contraseña por cada tabla de arco iris, entonces también podría usar la fuerza bruta directamente en el hash.

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 almacenaban históricamente como hashes simples en bases de datos, y eso es contra lo que las tablas de arco iris son efectivas: 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 [almacenar] contraseñas de forma segura? ya no es «vulnerable» 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 iris 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 hacer inútil una tabla de arco iris.

Cómo funcionan

Crear 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 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 valor para empezar). Cuando aplicamos el hash a MD48, se convierte en cfcd208495d5. Ahora aplicamos una función «reducir» que básicamente formatea este hash de nuevo en un contraseña, y terminamos con «z». Cuando volvemos a codificar eso, obtenemos fbade9e36a3f, luego lo reducimos nuevamente y obtenemos renjaj820 . Hay algunos ciclos más, y el resultado final es WLgOSj.

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

Nuestra tabla de arco iris 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 descifrarlo usando nuestra tabla!

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, los ejemplos anteriores se crearon utilizando este script de Python: https://gist.github.com/lgommans/83cbb74a077742be3b31d33658f65adb

Propiedades de escala

En resumen:

• Las búsquedas rápidas significan tablas más grandes, asumiendo que la cobertura se mantiene 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, 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 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 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, 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 correspondiente. 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 es 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 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 asumiendo que necesitamos 1 microsegundo (una millonésima de segundo) por hash + reducir el ciclo, 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 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. unos 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 Rainbow pueden ser considerado una compensación tiempo-memoria : uno almacena solo una pequeña parte de la tabla y la recupera mediante un 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, lo cual sería extremadamente ineficiente y anula todo el propósito.

Tenga en cuenta que se aplica algo similar 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 debe 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 reutilizarlo), siempre ejecútelo a través de un algoritmo de almacenamiento de contraseña adecuado (lento) para que sea lento y único para descifrar.

Comentarios

• Buena explicación. Si lo entendí correctamente, el poder de las tablas arcoíris radica en tener una buena función de reducción, ¿verdad? ¿Cómo se me ocurre una buena? ¿Y cómo evito colisiones para todos los candidatos a través de las cadenas?
• @ Kyu96 ¡Buenas preguntas! No ‘ no sé la respuesta, pero me interesaría si encuentras una. Esta página trata solo de la pregunta general de qué es una tabla de arco iris, no de detalles como cómo diseñar un algoritmo. Debería abrir una nueva pregunta , pero este sitio web trata sobre » proteger los activos de las amenazas digitales » (iirc ). Creo que estaría relacionado con el tema de nuestro sitio hermano, crypto.stackexchange.com , que se trata de » las matemáticas y propiedades de los sistemas criptográficos, su análisis (» criptoanálisis «) y temas subsidiarios que generalmente componen la criptología, como el número aleatorio generación. »