6 sept 2011

Rainbow Tables (tablas arco-iris)

Las rainbow tables o también conocidas, o más bien traducidas, como tablas arco iris son un elemento esencial en el mundo del crackeo o descifrado de credenciales. Las contraseñas no son almacenadas, habitualmente, en texto plano, aunque de todo hay en este mundo y nos podemos encontrar cualquier cosa. Normalmente una contraseña es almacenada como hash.

¿Qué es esto del hash?

Desde el punto de vista matemático un hash es una función unidireccional, es decir, la contraseña es pasada por una función matemática dando como resultado, el conocido como 'chorizo', el hash. Conseguir pasar del hash a la contraseña de nuevo no es nada fácil, de esto que la función sea unidireccional, es posible pasar de texto plano al hash, pero no del hash al texto plano.

 

En los sistemas operativos la contraseña se almacena como hash y nunca como texto plano ya que si el sistema fuera comprometido el atacante tendría acceso a todas las contraseñas en texto plano de los usuarios. Hay que recalcar que lo que se consigue con el tema de hashes es dificultar al atacante la obtención de las contraseñas pero nunca conseguiremos un modo seguro total, eso sí debemos seguir las recomendaciones para dificultar lo máximo al atacante.

¿Qué es la rainbow table?

Primero hablaremos de lo que no es, no es un par (hash, text plain), esta tabla ocuparía muchísimos TB debido a que existen mayúsculas, minúsculas, números, caracteres especiales, esto da como resultado muchísimas combinaciones por lo que sería inviable almacenar dicha tabla, e incluso sería inviable la búsqueda de los hashes en estas tablas.

Entonces, ¿Qué es? la rainbow table es una tabla que almacena un par, que son la palabra inicial y la palabra final. Después comentaremos exactamente que es eso de la palabra inicial y la palabra final. Hay que destacar también lo que es la función de reducción y de resumen. El algoritmo de resumen se aplica a una contraseña y se obtiene el hash de dicha contraseña. Por otro lado, los algoritmos de reducción se aplican sobre los hashes obteniendo otras palabras. Hay que recalcar que no estamos revertiendo el hash mediante el algoritmo de reducción, la palabra que se obtiene no tiene que ver con el hash anterior, mientras que con el algoritmo de resumen que se aplica a una contraseña si que da como resultado el hash de dicha palabra. Esto es muy importante que quede claro.

El proceso anterior se suele repetir en el proceso de creación de una rainbow table alrededor de 40.000 veces. A continuación se puede obversar el proceso gráficamente:

Como se puede observar en la imagen se empieza en un punto inicial, lo que anteriormente llamamos palabra inicial, y se aplica la función de resumen para obtener el hash de esta palabra inicial, después se aplica el algoritmo de reducción para obtener una palabra, en este caso 'sgfnyd', a esta palabra se le vuelve a aplicar el algoritmo de resumen obteniendo de nuevo el hash de la última palabra, y vuelta a empezar. Este proceso finaliza, en las tablas actuales cuando se realiza el proceso 40.000 veces y lo que se almacena en la tabla rainbow es la palabra inicial (punto de partida) y la palabra final o punto final. Entonces se puede observar fácilmente que el ahorro es enorme, pasar de almacenar las 40.000 duplas a solo almacenar una dupla con la palabra inicial y la palabra final. Imagen obtenida de una clase magistral de Gonzalo Álvarez.

¿Cómo se resuelve el descifrar una clave?

Nos ponemos en el siguiente escenario, se quiere descifrar un hash obtenido de alguna manera y disponemos de una rainbow table. Es bastante sencillo y rápido, ya que se realiza el mismo proceso que se ha descrito en el apartado anterior. Se comienza aplicando el algoritmo de reducción al hash del cual queremos averiguar la contraseña. Una vez obtenida la palabra de la aplicación del algoritmo de reducción se irá realizando el proceso 40.000 veces, en cada paso de resumen-reducción se observa si alguna de las palabras intermedias que se van generando el proceso coincide con alguna de las palabras fin que hay en la rainbow table. Si ocurre lo comentado anteriormente, es decir, alguna de las palabras intermedias está en la tabla como palabra fin se utilizará la palabra inicial de la dupla (palabra inicial, palabra final) y se vuelve a generar el proceso de las 40.000 ejecuciones. En algún momento se debe encontrar el hash, entonces la palabra que ha producido ese hash es la contraseña que se estaba buscando.

Ejemplo visual

Primero la creación de la tabla. Recordad que la tabla está formado por pares (palabra inicial, palabra final) y que desde la palabra inicial a la final hay una distancia de 40.000 ejecuciones de reducciones y resúmenes.

Hash(palabra inicial) -> Reducción(hash1) -> Hash(reducción1) -> Reducción(hash2) -> Hash(reducción2) -> Reducción(hash3) ... Hash(reducción40.000) -> Reducción(hash40.000) -> obtención palabra final

Ahora como se resuelve o se encuentra el hash y la clave en la tabla. Se realiza el proceso anterior partiendo de un hash, empezaríamos en el paso Reducción(hash1). Por cada palabra que se obtenga de la reducción hay que ver si se encuentra en alguna dupla, como palabra final en la tabla. Cuando se encuentre esta palabra volveríamos a realizar el proceso utilizando la palabra inicial, ejemplo:

Hash(palabra inicial) -> Reducción(hash1) -> Hash(reducción1) -> Reducción(hash2) -> Hash(reducción2) -> Reducción(hash3) ... Reducción(hashX) -> Hash(ReducciónX) = ¡Hash buscado!

En la última reducción obtenemos la clave en plano, y al aplicar el algoritmo de resumen obtenemos el hash que era del que partíamos por lo que la última reducción es la clave que equivale a ese hash.

6 comentarios:

  1. Muy interesante Pablo, dejo este documental de Eduard Punset donde hablan de criptografía, hashing y su fortaleza gracias a las cualidades de los números primos que me pareció muy bueno.http://www.rtve.es/television/20110206/redes-simetrias-del-universo/402059.shtmlsaludos

    ResponderEliminar
  2. Muy buena explicación sobre como obtener la clave que hay detrás de un hash.He utilizado rainbow tables en varias ocasiones pero creo que es la primera vez que lo veo tan bien explicado, paso a paso, como debe ser.Gracias.

    ResponderEliminar
  3. fossie tiene razón, yo tampo he visto una explicación sobre rainbow tables así... Felicidades por el post Pablo!No hace falta preguntarse por que flu-project tiene tantas visitas diarias =PUn saludo.

    ResponderEliminar
  4. [...] Pablo nos explica los secretos de las Rainbow Tables (tablas arco-iris) [...]

    ResponderEliminar
  5. Cierto. Es más, hace tiempo intenté explicar qué eran y lo hice de mala manera. Me gusta mucho cómo lo habéis hecho!!

    ResponderEliminar
  6. ¡Perfecta explicación! Es difícil explicar este concepto y aquí es donde mas claro está explicado de todos los sitios web que visité. ¡Enhorabuena!

    ResponderEliminar