Entiendo que una tabla de arco iris resuelve el problema de almacenamiento cuando uno ataca una contraseña usando hashes precalculados. Sin embargo, dado que las tablas de arco iris son esencialmente una versión comprimida de los hashes, ¿no es necesario descomprimirlos antes de compararlos con los hashes de destino? ¿No es caro este proceso de descompresión? ¿Cómo se compara el tiempo utilizado para descomprimir una tabla de arco iris con el de los hashes informáticos desde cero?
No. La compresión no funciona como la compresión de estilo RLE o LZMA tradicional.
Las tablas de arco iris son, esencialmente, una tabla de búsqueda que te permite encontrar una cadena dado su hash. Están diseñados para ser increíblemente eficientes para encontrar un hash en el índice en miles de millones de entradas, al tiempo que minimizan el espacio en disco.
Ahora, imagina que estás construyendo una mesa para muchas y muchas cadenas. Los hashes de algunas de estas cadenas comienzan con los mismos bytes, por ejemplo, "StackExchange", "ILikeWaffles9", "ILikeWaffles13507" y "Decompression242" cuando el hash con MD5 comienza con 0xF2. En lugar de almacenar los tres hashes completamente, puede construir una estructura similar a un árbol para que los datos se vean así:
f2 ="ILikeWaffles13507" 173dcd3c1a83febadc8ed1759c3ffc ="Decompression242" 17f4a64e4036025c07b24a96ec787a ="ILikeWaffles9" 50514201b94be52c1ea16cd688384e ="StackExchange" Tenga en cuenta que los hashes están ordenados por orden numérico.
De hecho, dado que las dos primeras cadenas también comparten el mismo segundo byte (0x17), estas también pueden encadenarse:
5cb1c6953bb0c62c639f3d7a242ec4 ="ILikeWaffles13507" f2 ="Decompression242" 17 ="ILikeWaffles9" 3dcd3c1a83febadc8ed1759c3ffc ="StackExchange" Esto también le permite realizar una búsqueda increíblemente rápida: en lugar de tener que buscar en la tabla completa, solo tiene que atravesar el árbol y luego buscar en una lista más pequeña de hashes. Dado que los hashes están ordenados, puede realizar una búsqueda binaria , que también tiene un rendimiento muy bueno.
Como ejemplo, si tengo el hash f4a64e4036025c07b24a96ec787a , busco el primer nodo de árbol 50514201b94be52c1ea16cd688384e y luego veo si hay un subnodo para el segundo byte, 5cb1c6953bb0c62c639f3d7a242ec4 . Hay, así que continúo hacia abajo. Verifico si hay un subnodo para f217f4a64e4036025c07b24a96ec787a . No hay, así que ahora busco en la lista dentro del nodo f2 . Sé que es probable que 17 esté cerca del final de esa lista, así que comienzo allí. Encuentro que el hash coincide con el que estoy buscando, por lo que ahora sé que el texto en claro es "Decompression242".
También es increíblemente eficiente en cuanto al espacio cuando tienes millones o miles de millones de hashes, porque no duplicas partes del hash que se comparten con otros plaintexts.
EDITAR: Lo siento, debería haber señalado que esto no es literalmente cómo funcionan las tablas de arco iris. Este es solo un ejemplo de cómo la compresión puede funcionar en este sentido, sin necesidad de guardar realmente un hash completo para cada texto plano. No quise decir lo contrario. La respuesta de IMSoP describe mejor el funcionamiento real.
Lo más importante que debes recordar es que las tablas de arco iris son solo útiles cuando quieres realizar múltiples búsquedas de hash para ese tipo de hash. Genera una tabla de arco iris para una lista de cadenas o caracteres en particular por adelantado, solo una vez, y luego puede usar ese conjunto de datos generados tantas veces como lo desee. Es un compromiso de hacer mucho trabajo antes de tiempo, por lo que tus búsquedas posteriores son muy rápidas.
Otra cosa clave es que cualquier sistema de hash que incluya un salt hace que las tablas del arco iris se vuelvan automáticamente inútiles, ya que cada combinación de contraseña y sal debe (idealmente) ser única y lo suficientemente larga como para que sea poco práctico crear una tabla del arco iris para cada contraseña combinación de hash.
Su premisa básica es errónea: una tabla de arco iris no es solo una lista comprimida de todas las posibles búsquedas de hash, y aún necesita hacer un hashing sobre la marcha. En su lugar, es una forma de explotar la naturaleza de los hash para evitar almacenar las búsquedas en primer lugar, y minimizar la cantidad que necesita volver a calcular.
Wikipedia tiene una explicación bastante detallada y hay una pregunta existente aquí con buenas respuestas , pero la idea básica es crear una tabla como esta:
De los valores que ha almacenado, puede recuperar todas las conjeturas generadas en el paso 3. En cierto sentido, cada par de {primera conjetura, último hash} "comprime" toda la cadena de conjeturas generadas.
Pero el truco es que no es necesario que pruebes todas las cadenas para revertir un hash, porque si tomas el hash estás atacando y comienzas en el paso 2, finalmente terminarás en uno de los hashes finales. almacenado (en el paso 6). Una vez que haya encontrado eso, puede recrear ("descomprimir", si lo desea) solo esa cadena , yendo desde el paso 1 (la conjetura de contraseña almacenada) y generando todas las conjeturas intermedias.
Una diferencia importante entre esto y la compresión es que puede hacer que la tabla almacenada sea tan pequeña como desee , al hacer que las cadenas sean más largas, solo tendrá que gastar más tiempo en generar hashes para Elija una cadena, y para volver a crear la cadena elegida. Podría tener un millón de cadenas de longitud diez, o diez de longitud un millón, intercambiando almacenamiento contra el tiempo de CPU .
Por supuesto, es posible comprimir los datos resultantes utilizando cualquier algoritmo que desee. Algunos de estos requerirán la descompresión de toda la tabla antes de buscarla, otros podrían organizar los datos para que aún puedan buscarse pero ocupen menos espacio. Pero también sería posible almacenar toda la tabla del arco iris como, por ejemplo, una lista ordenada en un SSD rápido, y todavía habría guardado espacio en una tabla hash completa porque solo está almacenando el inicio y al final de cada cadena, no todos los hash posibles.
Lea otras preguntas en las etiquetas hash password-cracking rainbow-table