Duda sobre tablas rainbow

[Ethicalsk]

Muy buenas, estuve leyendo por distintos lados sobre el funcionamiento de las tablas rainbow... Hasta ahora lo que se, es que NO son tablas de pares password_hash | password_textplain  sino de pares palabra inicial | palabra final.  El funcionamiento básicamente sería que a la palabra inicial se le aplica determinado algoritmo de hash, y al hash obtenido un algoritmo de reduccion para obtener una nueva palabra. Asi 40.000 iteraciones. Si queremos crackear X hash, tenemos que aplicar todo éste proceso de resumen/reduccion por cada entrada de la tabla, hasta que alguno de los hashes sea identico al que queremos crackear. Por cada iteración, se comprueba que la palabra reducida no sea la palabra final, en caso de que sea la palabra final, se toma la palabra inicial de la siguiente entrada, o tupla en la tabla y se repite el proceso. Tal vez esté equivocado respecto a como funciona, porque la verdad no le encuentro la utilidad a éste método, ya que a través de fuerza bruta solo tengo que ejecutar los algoritmos de resumen (hash) por cada combinacion hasta encotrar un hash identico al que quiero crackear, en cambio en las tablas rainbow, ademas de ejecutar los algoritmos de hash tambien hay que ejecutar los algoritmos de reduccion, a los cuáles no les encuentro el sentido... Es decir, generan una palabra cualquiera, cuyo hash, puede ser o no correspondiente al que busco, nadie me garantiza que lo sea, entonces si simplemente pruebo todas las combinaciones posibles, de forma incremental, estaría evitando ejecutar el algoritmo de reducción y de ésta forma obtendría más rápido la coincidencia con el hash que estoy buscando...

Espero que me entiendan y me sepan aclarar en qué estoy equivocado o qué no estoy teniendo en cuenta, ya que no entender algo me desespera. Saludos y gracias!

[engel lex]

las tablas raimbow se le llaman tambien "tablas precompiladas" basicamente en lugar de ser como un diccionario donde tienes que a cada palabra sacarle hash y comparar, esta ya tiene la palabra y el hash calculado, ahorrandote el proceso de calcular el hash que normalmente es la parte más lenta y pesada del proceso

[Ethicalsk]

Gracias engel por escribir! O sea, para llegar a almacenar en la tabla la palabra final y la inicial, se tuvo que hacer de antemano el proceso de calcular hash/reduccion 40.000 veces, con eso obtendríamos la palabra final en base a una inicial. Lo que no puedo entender es como luego, a través de las palabras inicial/final, se podrían recuperar los hashes calculados de antemano sin necesidad de volver a repetir el proceso... Eso es lo que no puedo terminar de entender. Saludos y gracias

[engel lex]

simplemente comparas.... como ya tienes el hash calculado, no tienes sino solo que busca en la tabla el hash que coincida, cuando lo encuentres, ves que palabra representa

[Ethicalsk]

Hola Engel! Gracias por tu tiempo. Seguí leyendo las explicaciones de las rainbow tables hasta que finalmente creo haberlo entendido bien.

Aca dejo un enlace con el artículo que leí para entenderlo, hecho por una chica argentina muy conocida en la comunidad:

http://www.semecayounexploit.com/?sec=password-cracking&nota=5

Encontré una parte de la explicación con la que no estoy de acuerdo, según lo que llego a interpretar, ahí va la cita del artículo:

2) Volver a generar las 40.000 combinaciones de la dupla donde la palabra final ha coincidido:


Cuando se vuelven a generar las 40.000 combinaciones de la dupla donde, en el paso anterior, ha coincidido la palabra final, se compara cada hash que se va generando con el que se quiere crackear. En algún momento coincidirá y la búsqueda se detiene, mostrando como resultado la palabra que ha generado el mismo hash que teníamos por objetivo, es decir, su equivalente en texto plano ¡Lo que queríamos! :p

Lo que no entiendo es por qué una vez que X reducción del hash que quiero crackear se corresponde con la palabra final de alguna dupla de la tabla rainbow, en el paso 2) se tiene que "comparar cada hash que se va generando con el que se quiere crackear. En algún momento coincidirá y la búsqueda se detiene..." Por lo que yo llego a interpretar, ese momento en el que coincide, se puede saber de antemano. Explicación:

Supongamos que en la tabla rainbow tengo una entrada con las tuplas:

sheila | winker

entre sheila y winker tengo 40.000 resumenes/reducciones.

Si el hash que quiero crackear es:
hashX, y obtengo que luego de reducirlo 10.000 veces, la última reducción se corresponde con la palabra winker.

Entonces, en el paso 2), partiendo de la palabra sheila, puedo saber de antemano que tengo que aplicar 30.000 iteraciones hasta encontrar el hashX. Y me quedaría con la palabra que genero ese hashX, pero no sería necesario en esas 30.000 iteraciones comparar el hash que se va generando con el que se quiere crackear... No se si me explico...

Y entonces, deduzco también que si luego de reducir 40.000 veces el hashX, ninguna reducción se corresponde con ninguna palabra final de la tabla, entonces el proceso de crackeo habría fallado, ya que la palabra que generaría el hashX, estaría antes de la palabra inicial... A ver si me explico:

Supongamos hipotéticamente que al hashX lo reduzco 50.000 veces, y luego de reducirlo 50.000 la última reducción se corresponde con la palabra winker. Entonces se tomaría la palabra sheila y se aplicarían los resumenes/reducciones 40.000 veces hasta llegar a la palabra final, pero ningun hash coindiciría con hashX, ya que la palabra que generaría el hashX estaría 10.000 veces antes que la palabra inicial sheila. Me equivoco en ésto?

Espero que sepan entenderme y corregirme si estoy equivocado, ya que soy muy detallista, y me gusta entender las cosas bien y no por la mitad. Saludos y gracias!

[engel lex]

por resumir un poco...

las rainbow tables (estaba respondiendo por diccionarios precomputados, no son lo mismo)

son tablas de "salto" por llamarlo de una manera tienes un inicio y un fin, sabes cuantos pasos hay entre estos 2 y en el camino tienes un monton de posibilidades al "azar".... tu calculas una serie de hashes y reducciones y si coincide con alguno en la tabla, sabes que tienes que empezar a calcular desde ese punto en lugar de hacerlo todo desde 0

[Ethicalsk]

Claro, eso es lo que yo termine entendiendo también, lo único que tenía la discrepancia que plantié en el mensaje anterior respecto a lo que escribió Sheila. Solo es un detallecito igual. Y no es invento de ella lo de las tablas rainbow, en wikipedia y en otros sitios se puede apreciar que el funcionamiento es asi como lo planteó. palabra inicial, final, resumenes y reducciones. Yo también pensé en un principio, antes de ponerme a leer mas exhaustivamente, que las tablas precalculadas y las tablas rainbow eran lo mismo, es más, nuestro compañero APOKLIPTICO, dio a entender eso mismo en éste thread:

https://foro.elhacker.net/criptografia/como_usar_rainbowcrack-t328460.0.html

Al parecer todos estabamos equivocados...

Saludos y gracias