security - que - ¿Cómo funciona una función de reducción utilizada con tablas rainbow?

rainbow tables ophcrack

Question

He leído cuidadosamente sobre tablas de arcoíris y no puedo obtener una cosa. Para construir una cadena hash, se usa una función de reducción . Es una función que de alguna manera mapea hashes en contraseñas. Este artículo dice que la función de reducción no es un inverso de hash, es solo un mapeo .

No lo entiendo, ¿para qué sirve un mapeo que ni siquiera es el inverso de la función hash? ¿Cómo debería funcionar dicha asignación prácticamente y ayudar a deducir una contraseña?

Answer 1

La razón por la cual la función de reducción no es la inversa de un hash es que el verdadero inverso de un hash no sería una función (recuerde, la definición real de "función" requiere una salida para una entrada).

Las funciones hash producen cadenas que son más cortas que sus entradas correspondientes. Según el principio del casillero, esto significa que dos entradas pueden tener la misma salida. Si las cadenas arbitrariamente largas pueden ser hasheadas, un número infinito de cadenas puede tener el mismo resultado, de hecho. Sin embargo, una tabla de arcoíris generalmente solo conserva una salida para cada hash, por lo que no puede ser una verdadera inversa.

La función de reducción que utilizan la mayoría de las tablas de arcoiris es "almacenar la cadena más corta que tenga este hash".

Answer 2

No importa si lo que produce es la contraseña: lo que obtendrías también funcionaría como contraseña, y podrías iniciar sesión con ella tan bien como con la contraseña original.

Answer 3

Una tabla de arcoiris es "solo" un método de compresión inteligente para una gran tabla de hashes precalculados. La idea es que la tabla puede "invertir" una salida hash si y solo si se tuvo en cuenta una entrada correspondiente durante la construcción de la tabla.

Cada línea de tabla ("cadena") es una secuencia de invocaciones de función hash. El truco es que cada entrada se calcula de forma determinista a partir de la salida anterior en la cadena, de modo que:

• al almacenar los puntos inicial y final de la cadena, usted "moralmente" almacena la cadena completa, que puede reconstruir a voluntad (aquí es donde se puede ver una tabla arcoiris como un método de compresión);
• puede iniciar la reconstrucción de cadena desde una salida de función hash.

La función de reducción es el pegamento que convierte una salida de función hash en una entrada apropiada (por ejemplo, una cadena de caracteres que se parece a una contraseña genuina, que consiste únicamente en caracteres imprimibles). Su función principal es poder generar posibles entradas hash con probabilidad más o menos uniforme, dados los datos aleatorios para trabajar con (y la salida hash será aceptablemente aleatoria). La función de reducción no necesita tener ninguna estructura específica, en particular con respecto a cómo funciona la función hash; la función de reducción solo debe permitir seguir construyendo la cadena sin crear demasiadas colisiones espurias.