Rainbow Tables: ¿Para qué se usa la reducción?

La función de reducción ayuda al almacenar más candidatos de texto simple dentro de los propios hashes. El artículo brinda un ejemplo de reducción realmente simple: tomar los primeros seis números de su hash "222f00dc4b7f9131c89cff641d1a8c50". El resultado de la reducción es otra posible contraseña de seis dígitos (222004) que está en hash. Luego, se extrae otra contraseña de texto simple candidata de ese hash, y así sucesivamente, creando una cadena larga. La mesa del arco iris almacena solo el final de esa larga cadena. No es necesario que almacene todos los hash porque puede hacer que cada hash vuelva a salir de la función de reducción mientras viaja hacia la cadena.

cuando le das un hash que deseas agrietar, primero busca en el primer conjunto de hashes que ha almacenado (que son el resultado final de esta cadena larga). Si por casualidad el hash está ahí, devuelve el texto plano y sale. De lo contrario, sube un paso en la cadena y comprueba el hash contra el que proporcionó. y así sucesivamente.

Al principio pensé que se estaba realizando algún tipo de operación de cubo, que redujo la cantidad de lugares necesarios para buscar el hash, pero no creo que la cadena dé pistas sobre dónde comenzar en función del hash original. . Simplemente es un intercambio de trabajo intesivo de memoria para una reducción en los requisitos de almacenamiento.

Como dice el artículo, no hay garantía de que cada texto simple tenga un hash correspondiente en este esquema. Las tablas de arco iris obtienen la mayor cantidad posible cambiando la función de reducción en cada columna (es por eso que se llaman tablas de arco iris, se imagina que cada columna tiene un color diferente ...)

Es una forma de hacer un compromiso entre el almacenamiento y los requisitos computacionales.

Es una implementación de una tabla hash : en lugar de almacenar todos los valores únicos posibles en la tabla (lo que dará como resultado problema real para almacenar la indexación y buscar el resultado), simplemente reduce el número de cálculos necesarios para encontrar un hash válido.

Básicamente, cuando creas la tabla del arco iris, creas un hash (aquí llamado función de reducción porque reduce el tamaño del espacio clave) del resultado para cada entrada que intentas. A continuación, almacena el valor original en un contenedor etiquetado con el resultado de la función de reducción.

Cuando usas la tabla del arco iris, haces lo siguiente: tomas el valor de hash que quieres invertir, pásalo a través de la función de reducción y miras lo que está dentro de la cubeta que tiene esa etiqueta: luego tratas de hash cada uno de los elementos en ese cubo y ver si coincide con su valor original.

En cuanto a cómo elegir una función de reducción adecuada, querrá una que le permita reagrupar todos los datos que ve en partes manejables: no quiere tener solo unos cuantos cubos grandes o demasiados pequeños. Ahí es donde se debe encontrar un equilibrio. Aparte de esto, la forma exacta en que selecciona la función de reducción no es realmente importante: debe intentar usar algo fácil de calcular, que dividirá sus datos en grupos estadísticamente iguales y que será fácil de manejar para su entorno. Prefiero elegir los últimos 6 números en lugar de los 6 primeros, no importaría al final.

Hay un muy buen tutorial que ilustra cómo funciona la tabla de arco iris aquí: enlace

Una tabla de reducción es una tabla que se asigna de código hash a texto simple. Un ejemplo sería tomar los primeros 6 dígitos del código hash (por ejemplo, 134503 del código hash abcd13450d3 ...).

La función de reducción intentará distribuirse al texto sin formato de manera equitativa, e intentar no dar como resultado muchos mapas de hashcodes a un texto sin formato. Eso dará lugar a una colisión como se describe en el video.

Cuando una función de reducción y hash se entrelaza, permite formar una cadena larga que se asigna entre el dominio de hashcode y el texto plano repetidamente.