Tablas arco iris (Rainbow tables)

En la siguiente entrada expondremos una pequeña introducción de la evolución en los algoritmos de cifrado y el motivo por el cual son importantes las rainbow tables exponiendo su funcionamiento y donde aplicarlas.

Comencemos con algo de historia, en un principio las contraseñas se almacenaban en texto en claro, por lo cual cuando un entorno era comprometido lo eran también las contraseñas de los usuarios. Debido a esto se emplearon algoritmos de cifrado o resumen (hash) de una sola dirección, es decir, que dado una contraseña le aplicamos un algoritmo que nos genera un hash, pero dado ese hash no existe un algoritmo inverso que nos proporcionara la contraseña. Por tanto ya no se almacenaban las contraseñas en texto en claro sino su hash ¿solucionado?

No, surgió otro problema: ante una misma contraseña se generaba un mismo hash, es decir H(p)=h, por lo cual se podían generar ficheros con una relación de dupla contraseña -  hash. Estos ficheros son el nacimiento de las tablas Raibow Tables, pero lo veremos más adelante.

Ante esta situación se creo el concepto de semilla o pizca de sal, que no es mas que un valor de un tamaño fijo que se introduce en el proceso de cifrado de tal forma que ante una misma contraseña existen tantos hashes como posibles valores pueda valer la semilla. Por lo tanto, si yo tengo una semilla de 2 bits puedo generar cuatro hashes distintos ante una misma contraseña:

H(p+00)=h1
H(p+01)=h2
H(p+10)=h3
H(p+11)=h4

Esto se puede observar si analizamos un fichero Shadow de un entorno Linux donde el segundo campo de este presenta una estructura de tres subcampos separada por el símbolo dolar ($), donde la primera indica el algoritmo hash empleado (1 es MD5, 5 es SHA256 y 6 es SHA512), la seguin indica el valor de la semilla utilizada y la tercera es el hash resultante.

¿Y por qué entonces son importantes las Rainbow Tables? pues porque aunque exista la semilla algunos desarrolladores han decidido no usarla. Estos entornos son principalmente aplicaciones de uso genérico que almacenan algunas contrasellas, algunas bases de datos y los sistemas operativos Windows, repito por si te lo has saltado, y los sistemas operativos Windows, tanto LM como NTLM.

Ante esta situación uno puede decir, ya está, obtengo el control de un controlador de dominio, obtengo el listado de hash de todas las contraseñas de los usuarios mediante fgdump o alguna herramienta parecida y a crackear con mis ficheros de duplas contraseña - hash, ¿verdad?

Pues no, porque el tamaño necesario para almacenar un fichero de duplas contraseña- hash para las posibles combinaciones de 8 caracteres, los cuales pueden ser: mayúsculas, minúsculas, numero o 8 caracteres no alfanuméricos requeriría un espacio de  (26+26+10+8)^8 * tamaño_dupla, vamos que muchos muchos TeraBytes son eso.

Es en este punto donde entran en acción las rainbow tables con los algoritmos de resumen y de reducción. Éstas consisten en dado una contraseña aplicar un algoritmos de resumen obteniendo un hash y sobre éste se aplica un algoritmo de reducción obteniendo una palabra. Este proceso se suele repetir hasta 10.000 veces, y en las últimas rainbow tables, hasta 40.000 veces. Veamos un ejemplo:

H(elefante) = h1 
R(h1) = banco
H(banco) = h2
R(h2) = ladrillo
H(ladrillo) = h3
R(h3)=roto
...
R(h10000)=sefini

Este proceso se repetirá hasta generar 10.000 o 40.000 hashes y contraseñas. Una vez finalizado ÚNICAMENTE se almacenará en la rainbow table la primera contraseña ("elefante") y la última ("sefini"), pero no las 10.000 duplas contraseña - hash, siendo el ahorro enorme. A estas entradas le llamaremos "palabra_ini:palabra_fin".

La pregunta entonces es, ¿y como obtengo la contraseña dado un hash? pues lo que hace el algoritmo es realizar el mismo proceso que hemos descrito con anterioridad pero para el hash del cual se pretende obtener la contraseña, al que llamaremos "hashQueQueremos":

R(hashQueQueremos) = casa
H(casa) = h1
R(h1) = perro
H(perro) = h2
...
R(hX) = sefini
...

Mientas se generan las 10.000 posibles palabras con el "hashQueQueremos" se busca si alguna de las palabras generadas existe en las tablas rainbow como "palabra_fin" de una de las duplas. Si existe, entonce se obtiene la "palabra_ini" de esa dupla y se vuelve a generar las 10.000 palabras a partir de la "palabra_ini".

En el ejemplo anterior hemos visto que en la reducción X se ha obtenido la palabra "sefini" y que dicha palabra existe en las rainbow tables con el par "elefante:sefini", por tanto el algoritmo lo que hace es volver a generar las 10.000 combinaciones que genera la palabra elefante en busca del "hashQueQueremos":

H(elefante) = h1
R(h1) = banco
H(banco) = h2
...
R(hY) = secreto
H(secreto) =hashQueQueremos
...
R(h10000)=sefini

Con esto sabemos que secreto a generado el "hashQueQueremos" y por tanto la contraseña buscada es "secreto".

El ahorro es tal que con una rainbow tables de 2GB suelo obtener en 5 horas el 80% de las contraseñas de un controlador de dominio con unos 500 usuarios si emplea cifrado LM, por defecto en los Win2000/2003. Suelo usar la herramienta Ophcrack con unas rainbow tables que me descargue en su momento, aunque en este enlace tenéis unas cuantas para descargar.

Para ciertas bases de datos con MD5 o SHA1 y sobretodo para auditorias en entornos Windows me ha resultado de muchísima ayuda. Espero que os sea de utilidad.

PD: esta entrada va para esos dos cracks de compañeros que tengo enfrente: Jose Luis Chica Spankito y el dietista David lladró. Ah! y para Raúl que creo que ha sido padre!