Rainbow tables: qué son y cómo funcionan las tablas arco iris

Con un nombre más acorde a un juego infantil, las tablas arco iris son un poderoso in­s­tru­me­n­to con el que es posible crackear co­n­tra­se­ñas. A esta tarea se dedica con ahínco un buen número de personas a ambos lados de la legalidad, unos por el beneficio que aspiran a obtener con ellas, los otros porque su trabajo como expertos consiste en comprobar pe­rió­di­ca­me­n­te la efe­c­ti­vi­dad de los es­tá­n­da­res de seguridad vigentes y las tablas arco iris -tra­du­c­ción del original rainbow tables, también conocidas como tablas rainbow- permiten encontrar claves en unos pocos segundos si se dan ciertas ci­r­cu­n­s­ta­n­cias.

Aun cuando confiamos en que nuestros lectores no tengan in­te­n­cio­nes cri­mi­na­les, es co­n­ve­nie­n­te co­m­pre­n­der cómo funcionan estas tablas de búsqueda, pues permiten entender, por un lado, por qué deben usarse co­n­tra­se­ñas difíciles y, por el otro, cómo pueden pro­te­ge­r­se las cuentas de los usuarios de una página web.

Hoy las co­n­tra­se­ñas ya no se guardan sin cifrar –o eso se espera. Cuando los usuarios de una pla­ta­fo­r­ma fijan una clave de acceso para su cuenta, esta secuencia de ca­ra­c­te­res no aparece en texto plano en una base de datos en algún servidor, puesto que no sería seguro: si en­co­n­tra­ra la forma de entrar en ella, un hacker lo tendría muy fácil para acceder a todas las cuentas de un de­te­r­mi­na­do usuario.

Para el eCommerce, la banca en línea o los servicios gu­be­r­na­me­n­ta­les online esto tendría co­n­se­cue­n­cias fatales. En lugar de ello, los servicios online utilizan diversos me­ca­ni­s­mos cri­p­to­grá­fi­cos para cifrar las co­n­tra­se­ñas de sus usuarios de modo que en las bases de datos solo aparezca un valor hash (valor resumen) de la clave.

Incluso co­no­cie­n­do la función cri­p­to­grá­fi­ca que lo ha originado, desde este valor hash no es posible deducir la co­n­tra­se­ña, porque no es posible re­co­n­s­truir el pro­ce­di­mie­n­to a la inversa. Esto lleva a los ci­be­r­de­li­n­cue­n­tes a recurrir a los ataques de fuerza bruta, en los cuales un programa in­fo­r­má­ti­co intenta “adivinar” la secuencia correcta de ca­ra­c­te­res que co­n­s­ti­tu­ye la co­n­tra­se­ña durante tanto tiempo como haga falta.

Este método puede co­m­bi­nar­se con los llamados “di­c­cio­na­rios” de co­n­tra­se­ñas. En estos archivos, que circulan li­bre­me­n­te en Internet, pueden en­co­n­trar­se numerosas co­n­tra­se­ñas que bien son muy populares o ya fueron in­te­r­ce­p­ta­das en el pasado. Los hackers prueban primero todas las co­n­tra­se­ñas del di­c­cio­na­rio, lo que les permite ahorrar tiempo, aunque, en función de la co­m­ple­ji­dad de las co­n­tra­se­ñas (longitud y tipo de ca­ra­c­te­res), este proceso puede resultar más largo y consumir más recursos de lo esperado.

También di­s­po­ni­bles en la Red y también un recurso para descifrar claves secretas, las tablas rainbow van un paso más allá de los di­c­cio­na­rios. Estos ficheros, que pueden llegar a tener un tamaño de varios cientos de gigabytes, contienen un listado de claves junto con sus valores hash, pero de forma in­co­m­ple­ta: para reducir su tamaño y así su necesidad de espacio en memoria, se crean cadenas de valores a partir de las cuales pueden re­co­n­s­trui­r­se fá­ci­l­me­n­te los demás valores. Con estas tablas los valores hash en­co­n­tra­dos en un banco de datos pueden ordenarse con sus claves en texto plano.

Para poder entender cómo funcionan las tablas arco iris conviene echar un vistazo a la mecánica de los al­go­ri­t­mos de cifrado, pues esto permite co­m­pre­n­der más fá­ci­l­me­n­te las ventajas de estas listas de búsqueda y el llamado co­m­pro­mi­so tiempo-espacio.

Desde que se co­me­n­za­ron a aplicar funciones hash cri­p­to­grá­fi­cas en el cifrado, los al­go­ri­t­mos no han dejado de evo­lu­cio­nar y los es­tá­n­da­res que hace diez años se co­n­si­de­ra­ban in­e­x­pu­g­na­bles hoy son vistos como graves vu­l­ne­ra­cio­nes de la seguridad. Todos, no obstante, tienen algo en común, y es que el contenido que debe cifrarse se somete a diversos al­go­ri­t­mos hasta que fi­na­l­me­n­te se genera un valor hash. Este valor resumen es no­r­ma­l­me­n­te una cifra he­xa­de­ci­mal con una longitud fija, que no depende de la del contenido inicial. Al final del proceso siempre resulta, por ejemplo, un valor hash de 128 bits.

Tres son los aspectos decisivos en el cifrado:

1. La misma entrada genera siempre el mismo valor hash: solo así este valor puede funcionar como suma de ve­ri­fi­ca­ción (del inglés “checksum”). ¿Es la clave in­tro­du­ci­da idéntica a la que hay en la base de datos? El sistema solo autoriza el acceso cuando ambos valores hash coinciden.
2. Un valor hash debería ser siempre único: dos entradas di­fe­re­n­tes no deberían generar el mismo valor resumen, pues solo siendo únicos pueden ga­ra­n­ti­zar que se ingresa la clave correcta. Como el número de valores hash posibles está limitado, pero el de posibles entradas no, es imposible descartar este tipo de coin­ci­de­n­cias, llamadas co­li­sio­nes en este contexto. Las funciones hash modernas y los valores hash con una longitud su­fi­cie­n­te intentan mantener este riesgo a raya.
3. Los valores resumen no son re­ve­r­si­bles, es decir, que a partir del valor resumen no es posible deducir el contenido original (la clave). Por ello tampoco es posible descifrar valores resumen, como se sostiene a veces de forma algo imprecisa. Solo pueden re­co­n­s­trui­r­se.
4. Las funciones hash deben ser muy complejas, pero no en exceso: si un algoritmo trabaja demasiado rápido, facilita el trabajo a los atacantes y ya no puede ga­ra­n­ti­zar la seguridad. Pero la tra­n­s­fo­r­ma­ción tampoco debe ser ex­ce­si­va­me­n­te compleja porque en de­fi­ni­ti­va ha de llevarse a la práctica.

Los valores hash co­n­te­ni­dos en las tablas rainbow no se crean con ocasión de un ataque, sino con an­te­rio­ri­dad, de modo que los hackers puedan hacerse con ellas y uti­li­zar­las para encontrar claves de acceso. Pero como estos ficheros son muy grandes, se aplica una función de reducción que permite ahorrar memoria. Esta función convierte al valor hash en un texto plano –no devuelve al valor original del valor hash, esto es, a la co­n­tra­se­ña original, pues esto no es posible, sino que genera un texto co­m­ple­ta­me­n­te nuevo.

A partir de este texto se crea otro valor resumen nuevo, un proceso que en una tabla arco iris no sucede una sola vez, sino muchas, de forma que se genera una cadena. En la tabla de­fi­ni­ti­va, no obstante, solo aparecen la primera clave y el último valor resumen de la cadena. Con esta in­fo­r­ma­ción y uti­li­za­n­do las mismas funciones de reducción es posible averiguar todos los demás valores. El valor hash que se quiere romper se reduce y se resume una y otra vez siguiendo las mismas reglas, co­m­pro­ba­n­do cada resultado con los valores que figuran en la tabla para encontrar su clave co­rre­s­po­n­die­n­te.

El desafío a la hora de crear una tabla reside en el hecho que la palabra inicial que re­pre­se­n­ta el comienzo de una cadena no puede figurar como texto plano en otra cadena pre­ce­de­n­te.

Con este método puede reducirse en gran medida el tamaño de estas tablas, aun teniendo todavía un volumen de varios cientos de gigabytes.

Se habla de una situación de co­m­pro­mi­so espacio-tiempo o tiempo-memoria cuando la memoria se reduce a costa de una ejecución más lenta o a la inversa, el tiempo de ejecución se reduce in­cre­me­n­ta­n­do el uso de la memoria. Un ataque de fuerza bruta necesita muy poco espacio, porque los cálculos cri­p­to­grá­fi­cos comienzan siempre de cero en cada ataque. En cambio, una tabla que contiene miles de millones de co­n­tra­se­ñas junto con sus valores hash ocupa mucha memoria, aunque puede descifrar muy rápido. Las rainbow tables re­pre­se­n­tan un acuerdo in­te­r­me­dio, pues aunque también lleva a cabo cálculos en tiempo real, lo hace a pequeña escala, de modo que, en co­m­pa­ra­ción con las tablas completas, reduce cla­ra­me­n­te las ne­ce­si­da­des de memoria.

La situación inicial es esta: dado un valor hash, se pretende conocer la clave de acceso que lo originó. En un primer paso, se busca este valor en la lista. Si se encuentra al comienzo o al final de una cadena, entonces es fácil encontrar la co­n­tra­se­ña, porque solo habrá que re­co­n­s­truir los pasos que recorrió la cadena hasta obtener el resultado que se busca. ¿Qué ocurre entonces cuando el valor resumen no se encuentra en la tabla?

En este caso, se comienza re­du­cie­n­do el valor con la misma función con la cual se creó la cadena. El resultado se somete a su vez a la función resumen, proceso que se denomina hashear y que se repite tantas veces como sean ne­ce­sa­rias hasta que se encuentre al valor resumen en algún punto final. Con todo, esto no significa que se haya en­co­n­tra­do la clave, aunque sí se ha en­co­n­tra­do la cadena en la cual se esconde el valor hash. Entonces se comienza en el punto inicial de la cadena y se lleva a cabo de nuevo esta al­te­r­na­n­cia de reducción y hashing hasta que se logra encontrar el valor hash que se busca y con él a la clave en texto plano.

Llegados a este punto, quizá lo más normal sea pre­gu­n­tar­se qué tiene que ver el arco iris con estas tablas de de­s­ci­fra­do de claves. La razón es muy sencilla: en la práctica no se utiliza solo una función de reducción, sino una diferente en cada paso, porque así se consigue un mejor resultado y se evita que se repitan valores hash en la tabla, si bien con un in­co­n­ve­nie­n­te: encontrar en la cadena co­m­bi­na­cio­nes de valores hash y claves es más complejo.

Para lograrlo se han de seguir las re­du­c­cio­nes por orden. Si se parte de la su­po­si­ción de que se ha creado una cadena con las re­du­c­cio­nes R₁, R₂, R_3, la búsqueda co­me­n­za­ría con la función R₃. Si esta no arroja re­su­l­ta­dos, se pasa a R₂ y luego otra vez a R₃, etc. Si se marcan con colores, esta al­te­r­na­n­cia de funciones puede dar lugar a un colorido arco iris, dando así nombre a estas tablas de búsqueda de claves.

En esta ecuación, k es la clave de acceso, m es un mu­l­ti­pli­ca­dor (que en nuestro ejemplo es 2.000). Para A se suele utilizar la pro­po­r­ción áurea 0,618. (φ). Mod (modulo) extrae el resto de una división que en esta función tiene lugar por 1. La función de parte entera redondea el resultado a un número entero en caso que sea necesario. El resultado, h(k) es el valor hash del valor de entrada k.

Como nuestro valor hash está compuesto de 4 cifras lo co­m­ple­ta­mos con un 0: 0408.

En una tabla rainbow para esta función hash se aplican ahora funciones de reducción. Una forma muy sencilla de reducir un valor hash es uti­li­za­n­do solo sus dos últimas cifras. Si tomamos la clave 78 y su co­rre­s­po­n­die­n­te valor hash 0408, su reducción es 08. A partir de aquí se vuelve a re­co­m­po­ner el valor hash con ayuda de la función mu­l­ti­pli­ca­ti­va.

La fre­cue­n­cia de las re­pe­ti­cio­nes es libre, pero cuantas más re­pe­ti­cio­nes, menos memoria necesita la tabla –si bien se in­cre­me­n­ta el tiempo de ejecución. En nuestro ejemplo apli­ca­re­mos la reducción tres veces:

Esta tabla re­pre­se­n­ta la cadena completa con todos los re­su­l­ta­dos de las funciones hash y de reducción. El objetivo de una tabla arco iris es reducir su tamaño, así que la rainbow table final solo contiene el valor inicial (c1) y el final (h4); el resto de valores puede deducirse de ellos:

En esta tabla vemos que ya no están todos los valores hash. Si el valor hash conocido fuera 1888, lo bu­s­ca­ría­mos en la tabla en vano, puesto que este valor ahora se esconde en una cadena. En co­n­se­cue­n­cia, se le aplica la reducción, dando como resultado 88. Este valor tampoco está en la tabla, así que se calcula de nuevo su valor hash (0768) y su reducción (68). El valor hash que le co­rre­s­po­n­de (0048) se encuentra en la tercera fila, si bien la clave en la misma fila (03) tampoco pertenece di­re­c­ta­me­n­te al valor hash, puesto que solo es el comienzo de la cadena. Pero sí ofrece un punto de partida para el siguiente cálculo: a partir de 03 se calcula el valor hash 1708. Lo reducimos a 08 y re­co­n­s­trui­mos de nuevo el valor hash: 1888, que es el valor hash que bu­s­cá­ba­mos. En co­n­se­cue­n­cia, la co­n­tra­se­ña que co­rre­s­po­n­de a 1888 es 08.

Ahora que hemos visto cómo los atacantes pueden acceder a cuentas de usuario uti­li­za­n­do rainbow tables, queda clara la necesidad de tomar medidas de defensa. Tanto los usuarios como los re­s­po­n­sa­bles de páginas web tienen a mano algunas es­tra­te­gias con las que impedir este tipo de ataques o al menos di­fi­cu­l­tar­los.

Como regla de oro, sobra decir que las claves han de ser su­fi­cie­n­te­me­n­te largas y contener ma­yú­s­cu­las, mi­nú­s­cu­las, cifras y ca­ra­c­te­res es­pe­cia­les. Como descifrar una clave así es difícil, seguir esta regla te defiende de los ataques de fuerza bruta y de tablas arco iris, ya que con la longitud de la clave aumenta ex­po­ne­n­cia­l­me­n­te el tamaño de la tabla. Tampoco se re­co­mie­n­da utilizar palabras, sino solamente se­cue­n­cias alea­to­rias, lo que impide los ataques de di­c­cio­na­rio. Cualquier gestor de co­n­tra­se­ñas puede ayudarte a crear claves seguras. Tampoco conviene utilizar las claves más de una vez. No importa qué tipo de ataque se utilice: una vez que alguien ha logrado allanar una base de datos, descifrar las co­n­tra­se­ñas y acceder a datos pe­r­so­na­les, es muy sencillo probar si con la misma co­n­tra­se­ña se puede acceder a otras cuentas.

Los gestores de los se­r­vi­do­res también tienen recursos para proteger a sus usuarios. Antes que nada se ha de impedir con valores hash el acceso no au­to­ri­za­do a las bases de datos. Na­tu­ra­l­me­n­te, es más fácil decirlo que co­n­se­gui­r­lo, como prueban las numerosas in­tru­sio­nes a los se­r­vi­do­res de las grandes compañías. Por esto, el valor hash es de pro­te­c­ción obli­ga­to­ria y para ello es fu­n­da­me­n­tal evitar a toda costa los al­go­ri­t­mos obsoletos.

Tanto MD5 como SHA-1 vienen co­n­si­de­rá­n­do­se inseguros hace ya un tiempo y sus tablas arco iris se en­cue­n­tran fá­ci­l­me­n­te en Internet. Con ellas pueden en­co­n­trar­se claves hasheadas con gran facilidad. Por eso es deber del ad­mi­ni­s­tra­dor web ma­n­te­ne­r­se al día respecto a la exi­s­te­n­cia de al­go­ri­t­mos nuevos o a la eficacia de la función hash que se ha utilizado. SHA-2 y su variante más conocida, SHA-256, siguen siendo válidas, si bien en­tre­ta­n­to ya ha aparecido SHA-3, que promete aún más seguridad por más tiempo.

Para di­fi­cu­l­tar el de­s­ci­fra­do con tablas arco iris se utiliza el de­no­mi­na­do valor salt (“sal” o “semilla”), una secuencia aleatoria que crea el sistema para la clave que define un usuario al abrir una cuenta. Este valor se acopla a la clave y ambos se someten a la función hash, creando así un valor diferente que el que generaría la co­n­tra­se­ña sin salt.

Salt y el valor hash se guardan juntos en la base de datos, lo que puede dar lugar a cierta confusión por la facilidad con que un atacante podría obtener de una vez nombre de usuario, valor hash y salt si co­n­si­guie­ra acceder a ella. Y, de hecho, este método realmente no protege contra los ataques de fuerza bruta y de di­c­cio­na­rio, pero sí ante las tablas de colores, puesto que estas se crearon antes que la base de datos y de forma in­de­pe­n­die­n­te a ella. Como su creador no los conocía, los salts no pueden figurar en ellas.

Otra ventaja de salt es que los usuarios no tienen que re­co­r­dar­la, por lo que puede ser todo lo larga o caótica que sea posible. Esto ocasiona un valor hash complejo que dificulta trabajar con él. El valor salt también impide que una co­n­tra­se­ña genere siempre el mismo valor hash aunque la utilicen dos personas di­fe­re­n­tes. Del mismo modo, si un usuario utiliza la misma clave para varios servicios, salt evita que se guarde siempre el mismo valor hash en di­fe­re­n­tes páginas.

Además de salt también está pepper (“pimienta”). Este valor participa di­fi­cu­l­ta­n­do el ataque de fuerza bruta o de di­c­cio­na­rio. También co­n­s­ti­tu­ye una secuencia aleatoria que, sobre todo si se acompaña de salt, entra en el valor hash junto con la clave. A di­fe­re­n­cia del salt, pepper no se almacena junto con los otros datos de acceso en la base de datos, sino separado y en un lugar más seguro.

A menudo se utiliza como pepper una cadena de ca­ra­c­te­res fija para todas las claves de la pla­ta­fo­r­ma, de modo que no protege si varios usuarios poseen la misma clave, porque utilizan entonces el mismo pepper, lo que de nuevo conduce a un valor hash idéntico. En co­n­se­cue­n­cia, los ad­mi­ni­s­tra­do­res deberían de­ca­n­tar­se por una co­m­bi­na­ción de salt y pepper.