Remote Tools: Otros conceptos (III) - Rainbow Tables

Buenas!

En esta entrada vamos a tratar el concepto de "Tabla Rainbow".

Ya en la primera entrada de esta tanda, y sobretodo en la anterior vimos que es una tarea prácticamente imposible el almacenar todo un hash en un sistema.

Pues bien, hay un método, llamado "Rainbow Generation" que permite almacenar una gran cantidad de hashes en muy poco espacio.

¿Quieres saber más?

¡Vamos allá!



Una tabla Rainbow (TR, en adelante) se basa en una serie de cadenas de hashes. Esto tiene a imaginarse como un diccionario, tal que vemos parejas del estilo:

A -> hash(A)

Una TR no trabaja al 100% de este modo... usa una cadena (como decía antes) de hashes.

En este momento es un buen punto para explicar lo que en los documentos de TR se conoce como "Función de reducción" o "redux".

Una "redux" es una función que, digamos, hace las veces de inversa a un hash. Digo "hace las veces" porque un hash no tiene inversa (sino no sería un hash), y a la vez estabiliza la longitud de la cadena. Para que os hagáis una idea; imaginad que yo en mi TR quiero hashes de longitud 5, ¿ok? y digamos que usamos como hash el algoritmo SHA1.

Definiré mi redux(t, l) como:

/**
* redux ejemplo
* Función que efectúa una redux de ejemplo
* @param t: texto a convertir
* @param l: longitud deseada
* @return: cadena que va desde el primer caracter
*          hasta completar la longitud deseada
*/
public String redux(String t, int l){
    return t.substring(0, l);
}

De ahí que se llame "reducción", puesto que por norma general acorta el texto de entrada (si pasásemos cadenas de 20 caracteres y quisiéramos una de 40 tendríamos que aumentar, no reducir).

Ahora que ya sabemos lo que es una redux, se puede explicar el proceso general de una RT:

T0 -> T1 = hash(T0) -> T2 = redux(T1) -> T3 = hash(T2) ... -> Tn = redux(Tn-1)

Es decir, se hace una serie de n*2 pasos. Este "n*2" se conoce como longitud de cadena (Chain Length, en inglés).

En el fichero RT solo guardaremos T0 y Tn. Puede que parezca no tener sentido, pero poco a poco iréis viendo todo el conjunto más claro.

Entonces, tendremos un número "m" de cadenas de longitud "n", es decir algo como:

T00 -> T0n
T10 -> T1n
...
Tm0 -> Tmn

Pero hay un pequeño problema... resulta que nuestras redux son muy sensibles a colisiones, es decir, en el supuesto de que busquemos cadenas de caracteres de longitud 3, es relativamente fácil encontrar dos hash que empiecen por "abc".

Entonces, puede ser que una cadena se solape con otra.

No lo capto

Imaginemos que nuestra primera cadena tiene como T00 el valor "hol". Sobre este T00 se generaría T01 = hash(T00), digamos que T01 = "abc00099".

Generamos ahora T02 como redux(T01) = "abc", y vamos haciendo hasta llegar a T0n = "def".

Ahora, en la quinta cadena (por ejemplo), en T53 tenemos T53 = hash(T52) = "abc12300".

Nuestro T54 = redux(T53) = "abc" sería el mismo que T02, por lo que a partir de ahí ambas cadenas serían iguales (puesto que el hash resultante sería el mismo, y por consiguiente las redux y hashes siguientes).

Gráficamente es algo así:





















También puede ser que tengamos como inicio un T00 = "abc" y su T01 sea "abc123456", con lo que su T02 sería de nuevo "abc" y así hasta que terminase.

La segunda situación se solventa más o menos con facilidad: se trata de, por una parte, nunca usar T0x que contengan caracteres contenidos en el hash (en SHA1, los caracteres HEX), y por otra parte, en nuestra redux, asegurarnos de que al menos un carácter no corresponde al "charset" del hash.

La primera parte es lo que realmente cuesta y a la vez es el hecho por el que se les llama "Rainbow".

La solución se basa en usar más de un redux. Simple y elegante.

Para ilustrar, nuestras cadenas serían, en realidad:

T00 -> T01 = hash(T00) -> T02 = redux1(T01) -> T03 = hash(T02) -> T04 = redux2(T03) -> T0n = reduxn/2(T0n-1)

A su vez, se pueden usar también "orientados en columnas", es decir

T00 -> T01 = hash(T00) -> T02 = redux1(T01) -> T03 = hash(T02) ... -> T04 = redux2(T03) -> T0n = reduxn/2(T0n-1)

Tm0 -> Tm1 = hash(Tm0) -> Tm2 = reduxn(Tm1) -> Tm3 = hash(Tm2) ... -> Tm4 = reduxn(Tm3) -> Tmn = reduxn(Tmn-1)

También se puede usar una combinación de ambas (usar "n/2" funciones de redux, y en cada una de las "m" filas usarlas en un orden distinto).

Si a cada "redux" le asignamos un color tenemos... ¡Un arcoiris!.

De ahí que las RT se llamen así (no es broma!)

Bueno, muy bonito... pero ¿qué ganas con esto?

Cierto, cierto... me estoy dejando llevar por definiciones y conceptos y no estoy explicando qué ganamos con las RT. Vamos a ello, ahora que sabemos cómo funcionan las RT.

Una vez tenemos una RT (podemos buscar por Internet en busca de programas gratuitos - muy buenos - que generan RT) podemos "buscar" en ella un determinado valor.

Es decir, yo se que mi RT tiene un Chain Length de 400.000 (suele ser el habitual), y le paso un texto cifrado con un hash, y quiero saber su texto plano.

Entonces, le paso el hash a un programa que tratará la RT y esta ejecutará lo siguiente:

Si la RT es por filas (cada fila usa un único redux, distinto en cada fila)

//"reduxi" se refiere al redux aplicado
//"fin" se refiere al final de la cadena
//"text" es el texto encriptado
//"hash" es la función que encripta (SHA1, MD5, ...)

desde 0 hasta longitud usando i
    rdx = reduxi(text)
    rdxold = rdx

    desde 0 hasta chainLength usando j
        hsh = hash(rdx)
        rdx = reduxi(hsh)

        si(rdx = fin)
            devuelve rdxold
        sino
            rdxold = rdx
        finsi
    haz
haz

Si la RT es por columnas (cada fila usa n/2 redux, los mismos en cada fila)

Este caso es un poco distinto, ya que tenemos que tener en cuenta que por cada cadena se usan "n/2" redux distintos, y no obtendremos el mismo resultado si empezamos usando el "redux1" que si empezamos usando el "redux2" (los pasos que se hagan tampoco serán los mismos).

Así, tendríamos que empezar aplicando reduxn/2, y comprobar si coincide con algún final. Si no coincide, aplicamos reduxn/2-1, el hash, y luego reduxn/2, y comprobamos si hay alguna coincidencia... y así hasta que completemos la cadena (siempre y cuando no haya ninguna coincidencia).

De todas maneras, estamos usando el mismo concepto de colisión que explicábamos antes para encontrar el hash. ¿Ingenioso verdad?

Obviamente el método RT no es 100% preciso, es decir, ni se puede almacenar todo el hash, ni se puede asegurar que cubra el 100% de las posibilidades (es decir, hay posibilidades de que no se encuentre un hash).

No obstante, es una buena manera de guardar muchísimos hash en muy poco espacio, combinando ingenio y elegancia.

Y hasta aquí la entrada de hoy, chicos.

Espero que os haya entretenido... comprendo que puedan haber fallos en algunos conceptos, puesto que todavía no domino al 100% el funcionamiento interno de las RT (pero lo intento! :^P)

Nos veremos en la próxima entrada, que tratará sobre fuerza bruta.

¡Hasta la próxima!