Una tabla arco iris es una tabla precalculada para almacenar en caché las salidas de una función hash criptográfica , generalmente para descifrar hashes de contraseñas. Las contraseñas normalmente no se almacenan en texto plano, sino como valores hash. Si dicha base de datos de contraseñas hash cae en manos de un atacante, puede utilizar una tabla de arcoíris precalculada para recuperar las contraseñas en texto plano. Una defensa común contra este ataque es calcular los hashes utilizando una función de derivación de claves que agrega una " sal " a cada contraseña antes de aplicar el hash, y diferentes contraseñas reciben diferentes sales, que se almacenan en texto sin formato junto con el hash.
Las tablas Rainbow son un ejemplo práctico de compensación espacio-temporal : utilizan menos tiempo de procesamiento informático y más almacenamiento que un ataque de fuerza bruta que calcula un hash en cada intento, pero más tiempo de procesamiento y menos almacenamiento que una simple tabla que almacena el hash de todas las contraseñas posibles.
Las tablas Rainbow fueron inventadas por Philippe Oechslin [1] como una aplicación de un algoritmo anterior y más simple de Martin Hellman . [2]
Para la autenticación de usuarios , las contraseñas se almacenan como texto plano o hashes . Dado que las contraseñas almacenadas como texto sin formato se roban fácilmente si el acceso a la base de datos se ve comprometido, las bases de datos suelen almacenar hashes. Por lo tanto, nadie (incluido el sistema de autenticación) puede aprender una contraseña simplemente mirando el valor almacenado en la base de datos.
Cuando un usuario ingresa una contraseña para la autenticación, se calcula un hash y luego se compara con el hash almacenado para ese usuario. La autenticación falla si los dos hashes no coinciden; Además, la autenticación fallaría igualmente si se ingresara un valor hash como contraseña, ya que el sistema de autenticación lo haría por segunda vez.
Aprender una contraseña a partir de un hash es encontrar una cadena que, cuando se ingresa en la función hash, crea ese mismo hash. Esto es lo mismo que invertir la función hash.
Aunque se pueden utilizar ataques de fuerza bruta (por ejemplo, ataques de diccionario ) para intentar invertir una función hash, pueden volverse inviables cuando el conjunto de contraseñas posibles es lo suficientemente grande. Una alternativa a la fuerza bruta es utilizar tablas de cadena hash precalculadas. Las mesas Rainbow son un tipo especial de mesa que supera ciertas dificultades técnicas.
El término mesas arcoíris se utilizó por primera vez en el artículo inicial de Oechslin. El término se refiere a la forma en que se utilizan diferentes funciones de reducción para aumentar la tasa de éxito del ataque. El método original de Hellman utiliza muchas tablas pequeñas con una función de reducción diferente cada una. Las tablas Rainbow son mucho más grandes y utilizan una función de reducción diferente en cada columna. Cuando se utilizan colores para representar las funciones de reducción, aparece un arco iris en la tabla del arco iris. La Figura 2 del artículo de Oechslin contiene un gráfico en blanco y negro que ilustra cómo se relacionan estas secciones. Para su presentación en la conferencia Crypto 2003, Oechslin añadió color al gráfico para hacer más clara la asociación del arco iris. En la ilustración se muestra el gráfico mejorado que se presentó en la conferencia.
Dada una función hash de contraseña H y un conjunto finito de contraseñas P, el objetivo es precalcular una estructura de datos que, dada cualquier salida h de la función hash, pueda ubicar un elemento p en P tal que H( p ) = h , o determinar que no existe tal p en P. La forma más sencilla de hacer esto es calcular H( p ) para todo p en P, pero luego almacenar la tabla requiere Θ (|P| n ) bits de espacio, donde |P| es el tamaño del conjunto P y n es el tamaño de una salida de H, lo cual es prohibitivo para |P| grande. Las cadenas hash son una técnica para disminuir este requisito de espacio. La idea es definir una función de reducción R que mapee los valores hash nuevamente en valores en P. Sin embargo, tenga en cuenta que la función de reducción no es en realidad una inversa de la función hash, sino más bien una función diferente con un dominio y un codominio intercambiados de la función hash. función hash. Al alternar la función hash con la función de reducción, se forman cadenas de contraseñas y valores hash alternos. Por ejemplo, si P fuera el conjunto de contraseñas alfabéticas de 6 caracteres en minúscula y los valores hash tuvieran 32 bits de longitud, una cadena podría verse así:
El único requisito para la función de reducción es poder devolver un valor de "texto sin formato" en un tamaño específico.
Para generar la tabla, elegimos un conjunto aleatorio de contraseñas iniciales de P, calculamos cadenas de una longitud fija k para cada una y almacenamos solo la primera y la última contraseña de cada cadena. La primera contraseña se llama punto de partida y la última se llama punto final . En la cadena de ejemplo anterior, "aaaaaa" sería el punto de partida y "kiebgt" sería el punto final, y ninguna de las otras contraseñas (o valores hash) se almacenaría.
Ahora, dado un valor hash h para invertir (buscar la contraseña correspondiente), calcule una cadena que comience con h aplicando R, luego H, luego R, y así sucesivamente. Si en algún punto un valor coincide con uno de los puntos finales de la tabla, el punto de partida correspondiente permite recrear la cadena completa. Existe una alta probabilidad de que esta cadena contenga el valor h y, de ser así, el valor inmediatamente anterior en la cadena es la contraseña p que buscamos.
Por ejemplo, dado el hash 920ECF10 , su cadena se puede calcular aplicando primero R:
Dado que " kiebgt " es uno de los puntos finales de nuestra tabla, la contraseña inicial correspondiente " aaaaaa " permite seguir su cadena hasta alcanzar 920ECF10 :
Por tanto, la contraseña es " sgfnyd " (o una contraseña diferente que tenga el mismo valor hash).
Sin embargo, tenga en cuenta que esta cadena no siempre contiene el valor hash h ; puede suceder que la cadena que comienza en h se fusione con una cadena que tiene un punto de partida diferente. Por ejemplo, la cadena de valor hash FB107E70 también conduce a kiebgt :
A continuación se sigue la cadena generada por la correspondiente contraseña inicial " aaaaaa " hasta llegar a FB107E70 . La búsqueda finalizará sin llegar al FB107E70 porque este valor no está contenido en la cadena. Esto se llama falsa alarma . En este caso, la coincidencia se ignora y la cadena de h se extiende buscando otra coincidencia. Si la cadena de h se extiende hasta la longitud k sin buenas coincidencias, entonces la contraseña nunca se produjo en ninguna de las cadenas.
El contenido de la tabla no depende del valor hash que se va a invertir. Se crea una vez y luego se utiliza repetidamente para las búsquedas sin modificar. Al aumentar la longitud de la cadena, se reduce el tamaño de la mesa. Sin embargo, también aumenta el tiempo necesario para realizar búsquedas, y este es el equilibrio entre tiempo y memoria de la tabla Rainbow. En un caso simple de cadenas de un solo elemento, la búsqueda es muy rápida, pero la tabla es muy grande. Una vez que las cadenas se alargan, la búsqueda se ralentiza, pero el tamaño de la tabla disminuye.
Las cadenas hash simples tienen varios defectos. Lo más grave es que si en algún momento dos cadenas chocan (producen el mismo valor), se fusionarán y, en consecuencia, la tabla no cubrirá tantas contraseñas a pesar de haber pagado el mismo costo computacional para generarlas. Debido a que las cadenas anteriores no se almacenan en su totalidad, esto es imposible de detectar de manera eficiente. Por ejemplo, si el tercer valor de la cadena 3 coincide con el segundo valor de la cadena 7, las dos cadenas cubrirán casi la misma secuencia de valores, pero sus valores finales no serán los mismos. Es poco probable que la función hash H produzca colisiones, ya que generalmente se considera una característica de seguridad importante no hacerlo, pero la función de reducción R, debido a su necesidad de cubrir correctamente los textos claros probables, no puede ser resistente a las colisiones .
Otras dificultades surgen de la importancia de elegir la función correcta para R. Elegir R como identidad es poco mejor que un enfoque de fuerza bruta. Sólo cuando el atacante tenga una buena idea de los textos sin formato probables podrá elegir una función R que garantice que el tiempo y el espacio solo se utilicen para textos sin formato probables, no para todo el espacio de posibles contraseñas. En efecto, R dirige los resultados de los cálculos hash anteriores a probables textos sin formato, pero este beneficio tiene el inconveniente de que R probablemente no producirá todos los textos sin formato posibles en la clase que el atacante desea verificar, negándole la certeza de que no hay contraseñas provenientes de su clase elegida. Además, puede resultar difícil diseñar la función R para que coincida con la distribución esperada de textos sin formato. [2]
Las tablas Rainbow resuelven eficazmente el problema de las colisiones con cadenas hash ordinarias reemplazando la función de reducción única R con una secuencia de funciones de reducción relacionadas R 1 a R k . De esta manera, para que dos cadenas choquen y se fusionen, deben alcanzar el mismo valor en la misma iteración : en consecuencia, los valores finales de estas cadenas serán idénticos. Una pasada final de posprocesamiento puede ordenar las cadenas en la tabla y eliminar cualquier cadena "duplicada" que tenga los mismos valores finales que otras cadenas. Luego se generan nuevas cadenas para completar la tabla. Estas cadenas no están libres de colisiones (pueden superponerse brevemente), pero no se fusionarán, lo que reduce drásticamente el número total de colisiones. [ cita necesaria ]
El uso de secuencias de funciones de reducción cambia la forma en que se realiza la búsqueda: debido a que el valor hash de interés puede encontrarse en cualquier ubicación de la cadena, es necesario generar k cadenas diferentes. La primera cadena supone que el valor hash está en la última posición hash y simplemente aplica R k ; la siguiente cadena supone que el valor hash está en la penúltima posición hash y aplica R k −1 , luego H, luego R k ; y así sucesivamente hasta la última cadena, que aplica todas las funciones de reducción, alternando con H. Esto crea una nueva forma de producir una falsa alarma: una "suposición" incorrecta de la posición del valor hash puede evaluar innecesariamente una cadena.
Aunque las tablas arcoíris tienen que seguir más cadenas, lo compensan con menos tablas: las tablas de cadena hash simples no pueden crecer más allá de cierto tamaño sin volverse rápidamente ineficientes debido a la fusión de cadenas; Para solucionar esto, mantienen varias tablas y cada búsqueda debe buscar en cada tabla. Las tablas Rainbow pueden lograr un rendimiento similar con tablas que son k veces más grandes, lo que les permite realizar un factor de k menos búsquedas.
Las tablas Rainbow utilizan un algoritmo refinado con una función de reducción diferente para cada "eslabón" de una cadena, de modo que cuando hay una colisión hash en dos o más cadenas, las cadenas no se fusionarán mientras la colisión no ocurra en el misma posición en cada cadena. Esto aumenta la probabilidad de un descifrado correcto para un tamaño de tabla determinado, a costa de elevar al cuadrado el número de pasos necesarios por búsqueda, ya que la rutina de búsqueda ahora también necesita iterar a través del índice de la primera función de reducción utilizada en la cadena. [1]
Las tablas Rainbow son específicas de la función hash para la que fueron creadas, por ejemplo, las tablas MD5 solo pueden descifrar hashes MD5. La teoría de esta técnica fue inventada por Philippe Oechslin [3] como una forma rápida de compensación tiempo/memoria , [1] que implementó en el descifrador de contraseñas de Windows Ophcrack . Posteriormente se desarrolló el programa RainbowCrack , más potente , que puede generar y utilizar tablas Rainbow para una variedad de conjuntos de caracteres y algoritmos hash, incluidos LM hash , MD5 y SHA-1 .
En el caso simple en el que la función de reducción y la función hash no tienen colisión, dada una tabla de arcoíris completa (una que asegura encontrar la contraseña correspondiente dado cualquier hash), el tamaño de la contraseña establecida | P |, el tiempo T que se necesitó para calcular la tabla, la longitud de la tabla L y el tiempo promedio t necesario para encontrar una contraseña que coincida con un hash determinado están directamente relacionados: [ cita necesaria ]
Por lo tanto, el caso de contraseñas alfanuméricas en minúsculas de 8 caracteres (| P | ≃ 3×10 12 ) sería fácilmente manejable con una computadora personal, mientras que el caso de contraseñas alfanuméricas en minúsculas de 16 caracteres (| P | ≃ 10 25 ) sería completamente intratable.
Una tabla arcoíris es ineficaz contra hashes unidireccionales que incluyen sales grandes . Por ejemplo, considere un hash de contraseña que se genera usando la siguiente función (donde " + " es el operador de concatenación ):
saltedhash(password) = hash(password + salt)
O
saltedhash(password) = hash(hash(password) + salt)
El valor de la sal no es secreto y puede generarse aleatoriamente y almacenarse con el hash de la contraseña. Un valor de sal grande evita ataques de cálculo previo, incluidas las tablas de arcoíris, al garantizar que la contraseña de cada usuario tenga un hash exclusivo. Esto significa que dos usuarios con la misma contraseña tendrán diferentes hashes de contraseña (suponiendo que se utilicen diferentes sales). Para tener éxito, un atacante necesita calcular previamente tablas para cada valor de sal posible. La sal debe ser lo suficientemente grande; de lo contrario, un atacante puede crear una tabla para cada valor de sal. Para contraseñas Unix más antiguas que usaban sal de 12 bits, esto requeriría 4096 tablas, un aumento significativo en el costo para el atacante, pero no poco práctico con discos duros de terabytes. Los métodos SHA2-crypt y bcrypt , utilizados en Linux , BSD Unixes y Solaris , tienen sales de 128 bits. [4] Estos valores de sal más grandes hacen que los ataques de cálculo previo contra estos sistemas sean inviables para casi cualquier longitud de contraseña. Incluso si el atacante pudiera generar un millón de tablas por segundo, todavía necesitaría miles de millones de años para generar tablas para todas las sales posibles.
Otra técnica que ayuda a prevenir ataques previos al cálculo es el estiramiento clave . Cuando se utiliza la extensión, el salt, la contraseña y algunos valores hash intermedios se ejecutan a través de la función hash subyacente varias veces para aumentar el tiempo de cálculo necesario para aplicar hash a cada contraseña. [5] Por ejemplo, MD5-Crypt utiliza un bucle de 1000 iteraciones que introduce repetidamente el salt, la contraseña y el valor hash intermedio actual en la función hash MD5 subyacente. [4] El hash de la contraseña del usuario es la concatenación del valor salt (que no es secreto) y el hash final. Los usuarios no notan el tiempo extra porque solo tienen que esperar una fracción de segundo cada vez que inician sesión. Por otro lado, el estiramiento reduce la efectividad de los ataques de fuerza bruta en proporción al número de iteraciones porque reduce la Número de intentos que un atacante puede realizar en un período de tiempo determinado. Este principio se aplica en MD5-Crypt y en bcrypt. [6] También aumenta en gran medida el tiempo necesario para construir una tabla precalculada, pero en ausencia de sal, esto solo debe hacerse una vez.
Un enfoque alternativo, llamado fortalecimiento de clave , extiende la clave con una sal aleatoria, pero luego (a diferencia del estiramiento de clave) elimina la sal de forma segura. Esto obliga tanto al atacante como a los usuarios legítimos a realizar una búsqueda de fuerza bruta del valor de la sal. [7] Aunque el artículo que introdujo el estiramiento de teclas [8] se refería a esta técnica anterior y eligió intencionalmente un nombre diferente, el término "fortalecimiento de teclas" ahora se usa a menudo (posiblemente incorrectamente) para referirse al estiramiento de teclas.
Las tablas Rainbow y otros ataques de precómputo no funcionan contra contraseñas que contengan símbolos fuera del rango presupuesto o que sean más largos que los precalculados por el atacante. Sin embargo, se pueden generar tablas que tengan en cuenta formas comunes en las que los usuarios intentan elegir contraseñas más seguras, como agregar un número o un carácter especial. Debido a la considerable inversión en procesamiento informático, las tablas arcoíris de más de catorce lugares de longitud aún no son comunes. Por lo tanto, elegir una contraseña de más de catorce caracteres puede obligar a un atacante a recurrir a métodos de fuerza bruta. [ cita necesaria ]
Se encuentran disponibles públicamente esfuerzos intensivos específicos centrados en LM hash , un algoritmo hash más antiguo utilizado por Microsoft. El hash LM es particularmente vulnerable porque las contraseñas de más de 7 caracteres se dividen en dos secciones, cada una de las cuales se procesa por separado. Elegir una contraseña de quince caracteres o más garantiza que no se generará un hash LM. [9]
Casi todas las distribuciones y variaciones de Unix , Linux y BSD usan hashes con sales, aunque muchas aplicaciones usan solo un hash (típicamente MD5 ) sin sal. La familia Microsoft Windows NT/2000 utiliza el método de hash LAN Manager y NT LAN Manager (basado en MD4 ) y tampoco tiene sal, lo que la convierte en una de las tablas generadas más popularmente. Las tablas Rainbow han visto un uso reducido a partir de 2020, ya que la salazón es más común y los ataques de fuerza bruta basados en GPU se han vuelto más prácticos. Sin embargo, hay tablas de arcoíris disponibles para contraseñas NTLM de ocho y nueve caracteres. [10]
![{\displaystyle {\color {Rojo}{\mathtt {aaaaaa}}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {281DAF40}}\,{\xrightarrow[{ \;R\;}]{}}\,{\mathtt {sgfnyd}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {920ECF10}}\,{\xrightarrow [{\;R\;}]{}}\,{\color {Violeta}{\mathtt {kiebgt}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/609e4ea6eac3f25b5982f3c9c6ccdaead642540d)
![{\displaystyle {\mathtt {920ECF10}}\,{\xrightarrow[{\;R\;}]{}}\,{\color {Violeta}{\mathtt {kiebgt}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c5d0f08a2a5598244e082b88810425f16b660270)
![{\displaystyle {\color {Rojo}{\mathtt {aaaaaa}}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {281DAF40}}\,{\xrightarrow[{ \;R\;}]{}}\,{\mathtt {sgfnyd}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {920ECF10}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/96219a92ee1b95f41144e0498463f884939d996a)
![{\displaystyle {\mathtt {FB107E70}}\,{\xrightarrow[{\;R\;}]{}}\,{\mathtt {bvtdll}}\,{\xrightarrow[{\;H\;}] {}}\,{\mathtt {0EE80890}}\,{\xrightarrow[{\;R\;}]{}}\,{\color {Violeta}{\mathtt {kiebgt}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/91cb90a3ee395b1ffaea3e25ae60d03cf331ba5c)
