Una tabla arcoíris es una tabla precalculada para almacenar en caché los resultados de una función hash criptográfica , generalmente para descifrar hashes de contraseñas. Las contraseñas normalmente no se almacenan en forma de texto simple, sino como valores hash. Si una base de datos de contraseñas hasheadas cae en manos de atacantes, pueden usar una tabla arcoíris precalculada para recuperar las contraseñas en texto simple. Una defensa común contra este ataque es calcular los hashes usando una función de derivación de claves que agrega una " sal " a cada contraseña antes de convertirla en hashes, y cada contraseña recibe diferentes sales, que se almacenan en texto simple junto con el hash.
Las tablas arco iris son un ejemplo práctico de una compensación espacio-tiempo : utilizan menos tiempo de procesamiento de la computadora 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 tabla simple que almacena el hash de cada contraseña posible.
Las tablas arcoíris 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 en texto simple o en hashes . Dado que las contraseñas almacenadas en texto simple se pueden robar fácilmente si se ve comprometido el acceso a la base de datos, las bases de datos suelen almacenar en su lugar hashes. Por lo tanto, nadie (incluido el sistema de autenticación) puede averiguar una contraseña simplemente mirando el valor almacenado en la base de datos.
Cuando un usuario introduce una contraseña para autenticarse, se calcula un hash para ella 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 codificaría una segunda vez.
Para aprender una contraseña a partir de un hash hay que encontrar una cadena que, al introducirla en la función hash, genere 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 resultar inviables cuando el conjunto de contraseñas posibles es lo suficientemente grande. Una alternativa a la fuerza bruta es utilizar tablas de cadenas hash precalculadas. Las tablas arco iris son un tipo especial de tabla de este tipo que superan ciertas dificultades técnicas.
El término tablas 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 arcoíris 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íris en la tabla arcoíris. 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 agregó color al gráfico para que la asociación del arcoíris fuera más clara. El gráfico mejorado que se presentó en la conferencia se muestra en la ilustración.
Dada una función hash de contraseñas 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 localizar 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 todos los 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| grandes. 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 valores hash nuevamente en valores en P. Nótese, sin embargo, 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 codominio intercambiados de la 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 de 6 caracteres alfabéticos en minúscula y los valores hash tuvieran una longitud de 32 bits, una cadena podría verse así:
El único requisito para la función de reducción es poder devolver un valor de "texto simple" 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 en cada cadena. La primera contraseña se denomina punto de inicio y la última se denomina punto final . En la cadena de ejemplo anterior, "aaaaaa" sería el punto de inicio y "kiebgt" sería el punto final, y no se almacenaría ninguna de las otras contraseñas (ni los valores hash).
Ahora, dado un valor hash h para invertir (para encontrar 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 inicio 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 de inicio correspondiente " aaaaaa " permite seguir su cadena hasta alcanzar 920ECF10 :
Por lo 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 tenga un punto de inicio diferente. Por ejemplo, la cadena con el valor hash FB107E70 , también conduce a kiebgt :
La cadena generada por la contraseña inicial correspondiente " aaaaaa " se sigue hasta llegar a FB107E70 . La búsqueda terminará sin llegar a FB107E70 porque este valor no está incluido 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 coincidencias buenas, 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. Aumentar la longitud de la cadena disminuye el tamaño de la tabla. Sin embargo, también aumenta el tiempo necesario para realizar las búsquedas, y este es el equilibrio entre tiempo y memoria de la tabla arcoíris. En un caso simple de cadenas de un elemento, la búsqueda es muy rápida, pero la tabla es muy grande. Una vez que las cadenas se hacen más largas, la búsqueda se hace más lenta, pero el tamaño de la tabla disminuye.
Las cadenas hash simples tienen varios defectos. El más grave es que si en algún momento dos cadenas colisionan (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 en la cadena 3 coincide con el segundo valor en 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 planos probables, no puede ser resistente a las colisiones .
Otras dificultades resultan de la importancia de elegir la función correcta para R. Elegir R como identidad es poco mejor que un enfoque de fuerza bruta. Solo cuando el atacante tiene una buena idea de los textos claros probables podrá elegir una función R que asegure que el tiempo y el espacio solo se usen para los textos claros probables, no para todo el espacio de posibles contraseñas. En efecto, R conduce los resultados de los cálculos hash anteriores de vuelta a los textos claros probables, pero este beneficio viene con el inconveniente de que R probablemente no producirá todos los textos claros posibles en la clase que el atacante desea verificar, negando al atacante la certeza de que ninguna contraseña provenga de la clase elegida. También puede ser difícil diseñar la función R para que coincida con la distribución esperada de textos claros. [2]
Las tablas arcoiris resuelven eficazmente el problema de las colisiones con las cadenas hash ordinarias al reemplazar la función de reducción única R por una secuencia de funciones de reducción relacionadas R 1 a R k . De esta manera, para que dos cadenas colisionen y se fusionen, deben alcanzar el mismo valor en la misma iteración : en consecuencia, los valores finales en estas cadenas serán idénticos. Un paso de posprocesamiento final 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 requerida ]
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 se puede encontrar en cualquier ubicación en 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 segunda posición hash anterior 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 simple no pueden crecer más allá de un cierto tamaño sin volverse rápidamente ineficientes debido a la fusión de cadenas; para lidiar con esto, mantienen múltiples tablas y cada búsqueda debe buscar en cada tabla. Las tablas arcoíris pueden lograr un rendimiento similar con tablas que son k veces más grandes, lo que les permite realizar un factor de k búsquedas menos.
Las tablas arcoiris utilizan un algoritmo refinado con una función de reducción diferente para cada "enlace" de una cadena, de modo que cuando hay una colisión de hash en dos o más cadenas, las cadenas no se fusionarán siempre que la colisión no ocurra en la misma posición en cada cadena. Esto aumenta la probabilidad de una ruptura correcta 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 arcoíris 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 de 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 usar tablas arcoíris para una variedad de conjuntos de caracteres y algoritmos hash, incluidos LM hash , MD5 y SHA-1 .
En el caso simple donde la función de reducción y la función hash no tienen colisión, dada una tabla arco iris completa (una que se asegura de encontrar la contraseña correspondiente dado cualquier hash) el tamaño del conjunto de contraseñas | P |, el tiempo T que se había necesitado 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 dado están directamente relacionados: [ cita requerida ]
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 iris no es eficaz contra hashes unidireccionales que incluyen valores de sal grandes . Por ejemplo, considere un hash de contraseña que se genera utilizando 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 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 precomputación, incluidas las tablas arco iris, al garantizar que la contraseña de cada usuario se haya codificado de forma única. 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 precomputar 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 las contraseñas de Unix más antiguas que usaban una sal de 12 bits, esto requeriría 4096 tablas, un aumento significativo en el costo para el atacante, pero no impráctico con discos duros de terabytes. Los métodos SHA2-crypt y bcrypt , utilizados en Linux , Unix BSD y Solaris , tienen sales de 128 bits. [4] Estos valores de sal más grandes hacen que los ataques de precomputación 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, aún necesitaría miles de millones de años para generar tablas para todas las sales posibles.
Otra técnica que ayuda a prevenir ataques de precomputación es el estiramiento de clave . Cuando se utiliza el estiramiento, la sal, 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 hacer el hash de cada contraseña. [5] Por ejemplo, MD5-Crypt utiliza un bucle de 1000 iteraciones que alimenta repetidamente la sal, la contraseña y el valor hash intermedio actual de nuevo a la función hash MD5 subyacente. [4] El hash de la contraseña del usuario es la concatenación del valor de sal (que no es secreto) y el hash final. El tiempo adicional no es perceptible para los usuarios porque tienen que esperar solo 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 el 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 enormemente 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 claves , implementa dos sales, una pública y otra secreta, pero luego (a diferencia de la ampliación de claves) elimina de forma segura la sal secreta. Esto obliga tanto al atacante como a los usuarios legítimos a realizar una búsqueda por fuerza bruta del valor de la sal secreta. El tamaño de la sal secreta se elige de modo que la búsqueda por fuerza bruta sea imperceptible para el usuario legítimo. Sin embargo, hace que el diccionario arcoíris que necesita el atacante sea mucho más grande. [7] Aunque el artículo que introdujo la ampliación de claves [8] se refirió a esta técnica anterior y eligió intencionalmente un nombre diferente, el término "fortalecimiento de claves" ahora se usa a menudo (posiblemente de manera incorrecta) para referirse a la ampliación de claves.
Las tablas arcoíris y otros ataques de precomputación no funcionan contra contraseñas que contienen símbolos fuera del rango presupuesto, o que son más largas que las precalculadas por el atacante. Sin embargo, se pueden generar tablas que tengan en cuenta las formas comunes en 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 computacional, las tablas arcoíris de más de catorce lugares de longitud aún no son comunes. Por lo tanto, elegir una contraseña que tenga más de catorce caracteres puede obligar a un atacante a recurrir a métodos de fuerza bruta. [ cita requerida ]
Se han realizado esfuerzos intensivos específicos centrados en el algoritmo hash LM , un algoritmo hash más antiguo utilizado por Microsoft, que está disponible al público. El algoritmo 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 codifica por separado. Elegir una contraseña de quince caracteres o más garantiza que no se generará un algoritmo 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 (normalmente MD5 ) sin sal. La familia Microsoft Windows NT/2000 usa el método de hash LAN Manager y NT LAN Manager (basado en MD4 ) y también no tiene sal, lo que la convierte en una de las tablas generadas más populares. Las tablas arcoíris han visto un uso reducido a partir de 2020, ya que el uso de sal es más común y los ataques de fuerza bruta basados en GPU se han vuelto más prácticos. Sin embargo, las tablas arcoíris están 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)
