Las rainbow tables (tablas arcoíris) son las más potentes para cracking de hash. Explicar la lógica de creación y uso de estas para crackear una contraseña es difícil, por lo tanto te propongo explicártelo en tres pasos.
Primero voy a explicar cómo se crea y se usa una tabla sencilla de consulta de hash, luego voy a explicar cómo se crea una tabla rainbow (aunque no entiendas para que lo estoy haciendo) y por último te voy a explicar exactamente por que acorta el tiempo encontrando la contraseña en texto plano.
Definición rainbow table
Rainbow tables y cracking de hash. Un rainbow table es una tabla especialmente creada para hallar coincidencias de un hash resultado de aplicar una función resumen con su texto plano de contraseña original, de manera efectiva, reduciendo el tiempo de calculo necesario significativamente frente a buscar la colisión por fuerza bruta. Son usadas para recuperar una contraseña u otro secreto que has perdido o no conoces, si dispones del hash producto de este.

Son efectivas si el secreto que queremos encontrar tiene un formato concreto y una limitación de conjunto y tamaño de caracteres conocido, como por ejemplo contraseñas de un sistema, tarjetas de crédito cuyo hash se guarda en base de datos, etc…
Una tabla sencilla de consulta de hash (prepara almacenamiento)
Si queremos creación y uso de una tabla de consulta de hash el método es muy sencillo, por ejemplo vamos haciendo hash de todas las contraseñas de un diccionario de contraseñas en texto plano como rockyou y creamos una tabla. En esta tabla guardamos contraseña (texto plano de la contraseña) y hash. Después a partir de un hash, buscamos esté en nuestra columna de hash y al encontrarlo, en nuestra columna de contraseña tendremos esta allí en texto plano disponible.
123456 – E10ADC3949BA59ABBE56E057F20F883E
12345 – 827CCB0EEA8A706C4C34A16891F84E7B
123456789 – 25F9E794323B453885F5181F1B624D0B
password – 5F4DCC3B5AA765D61D8327DEB882CF99
iloveyou – F25A2FC72690B780B2A14E140EF6A9E0
etc…

Si queremos hacer el procedimiento anterior usando como input de contraseñas diccionarios más grandes, pues adelante, prepara tamaño de almacenamiento disponible y tendrás tablas de consulta sencillas de crear y fáciles de consultar. Sin embargo esta manera es poco práctica ya que estas limitado por tamaño de almacenamiento y lo más normal es que puedas hacerlo solo para un número limitado de contraseñas y estas seguramente serán muy predecibles.
Como hacer el proceso con un tiempo de consulta mayor, pero aprovechando considerablemente mejor el almacenamiento, que es el primer cuello de botella que nos encontraremos? con una rainbow table.
Como crear una rainbow table (sin entender todavía para que servirá exactamente)
El proceso de creación de un rainbow table es parecido al de creación de una tabla sencilla contraseña/hash explicada en el punto anterior, pero esta vez solo iremos guardando registros de vez en cuando, por ejemplo cada billón de iteraciones. Estos registros que guardaremos de vez en cuando después nos servirán como marcapáginas para volver a ese punto.

En un ejemplo muy simple del proceso empezaremos a crear nuestra tabla rainbow para contraseñas de ocho caracteres, con la contraseña de ocho caracteres «12345678» y para la función de resumen hash MD5 concretamente. El texto «12345678» nos resulta en el siguiente MD5 «25d55ad283aa400af464c76d713c07ad», pues bien cogemos solo los primeros ocho caracteres del hash y aplicamos MD5 a estos 8 caracteres.
Para crear la tabla repetiremos esta lógica de forma constante, registrando cada billón de veces el par contraseña/hash, por lo que obtendremos algo similar a esto:
12345678 – 25d55ad283aa400af464c76d713c07ad
4bd56f8d – c4110f242978a7b5c1a8740eacb64226
cccf7842 – 2bc1ec01fd9a4e117658e9026406b812
5bd4d6be – 245ed5260418556e62b9633c6136d0c8
etc…
Potencial de un rainbow table y lógica de búsqueda en ella
Una vez tuviéramos lista nuestra tabla rainbow tendríamos una ventaja efectiva para encontrar la contraseña en texto plano (dato del que no disponemos) que coincida con un hash dado (dato que si tenemos). En qué consiste esta ventaja? en el paso anterior hemos dividido billón a billón las posibilidades de coincidencia y hemos ido guardando unos marcapáginas por los que volver a puntos concretos.

Con un ejemplo práctico iniciaremos el mismo proceso que hemos realizado en el punto anterior para crear la tabla, esta vez partiendo de los primeros ocho caracteres de nuestro hash. Iremos iterando en la producción de MD5 de los primeros ocho caracteres de cada hash resultante hasta que uno de los resultados coincida con alguno de nuestros registros (o marcapáginas) de ocho caracteres.
Imaginemos que salta una coincidencia con «cccf7842», que nos dice esto? que siguiendo nuestra lógica de creación de la tabla, cuando la creamos en su día, procesamos la contraseña en texto plano que buscamos cronológicamente antes de ese registro o marcapáginas («cccf7842»). E indirectamente sabemos que procesamos la contraseña en texto plano que buscamos después del marcapáginas anterior de nuestra tabla rainbow «4bd56f8d», ya que la coincidencia con la tabla, ya se ha producido en el siguiente punto, en otro registro o marcapáginas diferente.

Por lo tanto sabemos en qué billón de iteraciones pasaremos por la contraseña en texto plano que origina el hash, y por lo tanto por el propio hash que buscamos. En negrita en la tabla anterior veremos los dos registros entre los cuales conseguiremos la contraseña en texto plano que buscamos:
12345678 – 25d55ad283aa400af464c76d713c07ad
4bd56f8d – c4110f242978a7b5c1a8740eacb64226
… por aquí andará la contraseña…
cccf7842 – 2bc1ec01fd9a4e117658e9026406b812
5bd4d6be – 245ed5260418556e62b9633c6136d0c8
Conclusiones y uso de salt
Espero haber contado bien la lógica de rainbow tables y cracking de hash, es una lógica que a mi me costo especialmente entender. La mejor forma de proteger un sistema de este tipo de ataque de cracking de contraseña a partir de su hash, es usar un salt (sal criptográfica) en todos los algoritmos de reducción o hash que implemente.
Esta protección consiste en sumar un dato adicional a las contraseñas antes de generar su hash, tanto en almacenamiento inicial del hash como en posteriores consultas. De esta manera, aunque alguien se hiciera con hash de tu sistema, la explotación de este posible ataque se complica considerablemente.
Pongamos que el atacante dispone del hash, pero no conoce el salt usado en tu sistema. En este caso la contraseña en texto plano que obtendría a partir del hash usando un rainbow table no valdría, ya que la original sería diferente. Y esto contando con que consiguiera algo para el conjunto de caracteres con el que trabaje. En un segundo caso de que el atacante conociera el salt, aun así, debería crear una rainbow table específicamente y de forma única para ese salt concreto. Es por esta razón que se recomienda para más seguridad salt personalizados.
Referencias y recursos para profundizar más en el tema
- Wikipedia: https://es.wikipedia.org/wiki/Tabla_arco%C3%ADris
- Explicación más en detalle (en ingles): https://www.ionos.com/digitalguide/server/security/rainbow-tables/
- Protección con salt, wikipedia: https://es.wikipedia.org/wiki/Sal_(criptograf%C3%ADa)
- Para hacerte una idea de tamaño de almacenamiento o descargarte una «Distributed Free Rainbow Tables»: https://freerainbowtables.com/
- Interesante articulo profundizando en detalles y desventajas de usar rainbow tables: https://blog.ircmaxell.com/2011/08/rainbow-table-is-dead.html
- Manos a la obra con RainbowCrack: https://null-byte.wonderhowto.com/how-to/create-rainbow-tables-for-hashing-algorithms-like-md5-sha1-ntlm-0193022/