Una tabla de arco iris es una tabla precalculada para almacenar en caché la salida de funciones hash criptográficas , generalmente para descifrar hash de contraseñas. Las tablas se utilizan generalmente para recuperar una función de derivación de claves (o números de tarjetas de crédito, etc.) hasta una cierta longitud que consta de un conjunto limitado de caracteres. Es un ejemplo práctico de una compensación espacio-tiempo , que usa menos tiempo de procesamiento de 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 función de derivación de clave simple con una entrada. por hash. Uso de una derivación de clave que emplea una sal hace inviable este ataque.
Las tablas de arco iris fueron inventadas por Philippe Oechslin [1] como una aplicación de un algoritmo anterior y más simple de Martin Hellman . [2]
Fondo
Para la autenticación de usuarios , las contraseñas se almacenan como texto sin formato o hash . 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 se realiza correctamente si los dos hashes coinciden. (Por otro lado, intentar usar un valor hash como contraseña para iniciar sesión fallaría ya que el sistema de autenticación lo haría por segunda vez).
Aprender una contraseña 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 los ataques de fuerza bruta (por ejemplo, ataques de diccionario ) pueden usarse para intentar invertir una función hash, pueden volverse inviables cuando el conjunto de posibles contraseñas 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 .
Etimología
El término "Tablas de arco iris" se utilizó por primera vez en el artículo inicial del Dr. Oechslin. El término se refiere a la forma en que se utilizan las 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 usan 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 de arco iris. La Figura 2 del artículo del Dr. 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, el Dr. Oechslin agregó color al gráfico para hacer más clara la asociación del arco iris. El gráfico mejorado que se presentó en la conferencia se muestra a la derecha.
Cadenas de hash precalculadas
Supongamos que tenemos 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 yn es el tamaño de una salida de H, que es prohibitivo para | P | grande. Las cadenas hash son una técnica para reducir este requisito de espacio. La idea es definir una función de reducción R que mapee los valores hash de nuevo en valores en P. Tenga en cuenta, 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 intercambiado y codominio de la función hash. Alternando la función hash con la función de reducción, se forman cadenas de contraseñas alternas y valores hash. Por ejemplo, si P fuera el conjunto de contraseñas alfabéticas en minúsculas de 6 caracteres y los valores hash fueran 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 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 en 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 no se almacenaría ninguna de las otras contraseñas (o los valores hash).
Ahora, dado un valor hash h que queremos invertir (busque la contraseña correspondiente), calcule una cadena que comience con h aplicando R, luego H, luego R, y así sucesivamente. Si en algún momento observamos un valor que coincide con uno de los puntos finales de la tabla, obtenemos el punto de partida correspondiente y lo usamos para recrear la cadena. Existe una buena posibilidad de que esta cadena contenga el valor h , y si es así, el valor inmediatamente anterior en la cadena es la contraseña p que buscamos.
Por ejemplo, si nos dan el hash 920ECF10 , calcularíamos su cadena aplicando primero R:
Desde " kiebgt "es uno de los puntos finales en nuestra tabla, luego tomamos la contraseña de inicio correspondiente" aaaaaa "y siga 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 tenga un punto de partida diferente. Por ejemplo, se nos puede dar un valor hash FB107E70, y cuando seguimos su cadena, obtenemos kiebgt:
Pero FB107E70 no está en la cadena que comienza en "aaaaaa". A esto se le llama falsa alarma . En este caso, ignoramos la coincidencia y continuamos extendiendo la cadena de h buscando otra coincidencia. Si la cadena de h se extiende a 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 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 mesa. También aumenta el tiempo necesario para realizar búsquedas, y esta es la compensación de tiempo-memoria de la tabla de arco iris. 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 alargan, la búsqueda se ralentiza, pero el tamaño de la tabla disminuye.
Las cadenas de hachís simples tienen varios defectos. Más grave 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 posibles textos sin formato, no puede ser resistente a las colisiones .
Otras dificultades resultan de la importancia de elegir la función correcta para R. Elegir R para que sea la identidad es poco mejor que un enfoque de fuerza bruta. Solo cuando el atacante tenga una buena idea de cuáles serán los posibles textos sin formato, podrá elegir una función R que asegure que el tiempo y el espacio solo se utilicen para los posibles textos sin formato, no todo el espacio de posibles contraseñas. En efecto, R guía los resultados de los cálculos hash anteriores a los posibles 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, negando al atacante la certeza de que no provienen contraseñas de su clase elegida. También puede ser difícil diseñar la función R para que coincida con la distribución esperada de textos sin formato. [2]
Mesas arcoiris
Las tablas de arco iris 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 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. Una pasada de posprocesamiento final puede clasificar 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 reducirá 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 lugar de la cadena, es necesario generar k cadenas diferentes. La primera cadena asume que el valor hash está en la última posición hash y solo aplica R k ; la siguiente cadena asume 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: si "adivinamos" la posición del valor hash incorrectamente, podemos evaluar innecesariamente una cadena.
Aunque las tablas de arco iris tienen que seguir más cadenas, lo compensan con menos tablas: las tablas de cadenas de hash simples no pueden crecer más allá de un cierto tamaño sin volverse rápidamente ineficientes debido a la fusión de cadenas; para hacer frente a 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.
Ejemplo
- A partir del hash ("re3xes") de la imagen siguiente, se calcula la última reducción utilizada en la tabla y se comprueba si la contraseña aparece en la última columna de la tabla (paso 1).
- Si la prueba falla ( rambo no aparece en la tabla), se calcula una cadena con las dos últimas reducciones (estas dos reducciones se representan en el paso 2)
- Nota: Si esta nueva prueba vuelve a fallar, se continúa con 3 reducciones, 4 reducciones, etc. hasta que se encuentra la contraseña. Si ninguna cadena contiene la contraseña, el ataque ha fallado.
- Si esta prueba es positiva (paso 3, linux23 aparece al final de la cadena y en la tabla), la contraseña se recupera al comienzo de la cadena que produce linux23 . Aquí encontramos passwd al comienzo de la cadena correspondiente almacenada en la tabla.
- En este punto (paso 4), se genera una cadena y se compara en cada iteración el hash con el hash objetivo. La prueba es válida y encontramos el hash re3xes en la cadena. La contraseña actual ( cultura ) es la que produjo toda la cadena: el ataque es exitoso.
Las tablas de arco iris 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 de hash en dos o más cadenas, las cadenas no se fusionarán siempre que la colisión no se produzca en el misma posición en cada cadena. Esto aumenta la probabilidad de una grieta correcta para un tamaño de tabla dado, a costa de cuadrar el número de pasos requeridos 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]
Tablas de arco iris son específicos de la función hash fueron creadas, por ejemplo, MD5 tablas sólo puede agrietar hash 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 crackeador de contraseñas de Windows Ophcrack . Más tarde se desarrolló el programa RainbowCrack más poderoso que puede generar y usar tablas de arco iris 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 iris completa (una que asegure 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 dado están directamente relacionados: [ cita requerida ]
Por lo tanto, el caso de las contraseñas alfanuméricas minúsculas de 8 caracteres (| P | × 3 × 10 12 ) sería fácilmente manejable con una computadora personal, mientras que el caso de las contraseñas alfanuméricas minúsculas de 16 caracteres (| P | ≃ 10 25 ) sería completamente intratable.
Defensa contra tablas arcoiris
Una tabla de arco iris es ineficaz contra hashes unidireccionales que incluyen sales grandes . Por ejemplo, considere un hash de contraseña que se genera mediante 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 al azar y almacenarse con el hash de la contraseña. Un alto valor de sal evita los ataques de precomputación, incluidas las tablas de arco iris, 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 usen diferentes sales). Para tener éxito, un atacante necesita calcular previamente tablas para cada posible valor de sal. La sal debe ser lo suficientemente grande, de lo contrario, un atacante puede hacer una tabla para cada valor de sal. Para las contraseñas 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 poco práctico con discos duros de terabytes. Los métodos SHA2-crypt y bcrypt , que se utilizan en Linux , BSD Unixes 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 no sean factibles para casi cualquier longitud de contraseña. Incluso si el atacante pudiera generar un millón de tablas por segundo, aún necesitarían miles de millones de años para generar tablas para todas las posibles sales.
Otra técnica que ayuda a prevenir los ataques de precomputación es el estiramiento clave . Cuando se usa el estiramiento, la sal, la contraseña y algunos valores de hash intermedios se ejecutan a través de la función de hash subyacente varias veces para aumentar el tiempo de cálculo necesario para aplicar el hash a cada contraseña. [5] Por ejemplo, MD5-Crypt usa un bucle de 1000 iteraciones que alimenta repetidamente el valor de sal, contraseña y hash intermedio actual de vuelta a la función de 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 extra no es notorio 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 la número de intentos que puede realizar un atacante 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 mesa 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 de forma segura la sal. 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 claves [8] se refería a esta técnica anterior y eligió intencionalmente un nombre diferente, el término "fortalecimiento de claves" ahora se usa a menudo (posiblemente incorrectamente) para referirse al estiramiento de claves.
Las tablas de arco iris y otros ataques de precomputación no funcionan con contraseñas que contienen símbolos fuera del rango presupuestado, o que son más largos que los precalculados 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 informático, las tablas arco iris 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 al atacante a recurrir a métodos de fuerza bruta. [ cita requerida ]
Los esfuerzos intensivos específicos centrados en el hash LM , un algoritmo hash más antiguo utilizado por Microsoft, están disponibles públicamente. 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 tiene un hash por separado. La elección de una contraseña de quince caracteres o más garantiza que no se generará un hash LM. [9]
Usos comunes
Casi todas las distribuciones y variaciones de Unix , Linux y BSD usan hash con sales, aunque muchas aplicaciones usan solo un hash (típicamente MD5 ) sin sal. La familia de Microsoft Windows NT / 2000 utiliza el método de hash de LAN Manager y NT LAN Manager (basado en MD4 ) y también es sin sal, lo que la convierte en una de las tablas generadas más popularmente. Se ha reducido el uso de las tablas de arco iris 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, las tablas Rainbow están disponibles para contraseñas NTLM de ocho y nueve caracteres . [10]
Ver también
- A5 / 1
- Ataque de fuerza bruta
- DistrRTgen
- El algoritmo canguro de Pollard
Notas
- ↑ a b c Oechslin, P. (2003). "Hacer un intercambio criptoanalítico de memoria-tiempo más rápido" (PDF) . Avances en criptología - CRYPTO 2003 . LNCS . 2729 . págs. 617–630. doi : 10.1007 / 978-3-540-45146-4_36 . ISBN 978-3-540-40674-7.
- ^ a b Hellman, M. "Un intercambio criptoanalítico de tiempo-memoria" (PDF) . Transacciones IEEE sobre teoría de la información . 26 (4): 401–406. CiteSeerX 10.1.1.120.2463 . doi : 10.1109 / TIT.1980.1056220 . ISSN 0018-9448 .
- ^ Lasecwww.epfl.ch
- ^ a b Alexander, Steven (junio de 2004). "Protección con contraseña para sistemas operativos modernos" (PDF) . Iniciar sesión . Asociación USENIX . 29 (3).
- ^ Ferguson, Neils; Bruce Schneier (2003). Criptografía práctica . Indianápolis: John Wiley & Sons. ISBN 978-0-471-22357-3.
- ^ Provos, Niels ; Mazières, David (6 de junio de 1999). "Un esquema de contraseña adaptable al futuro" (PDF) . Actas de FREENIX Track: Conferencia técnica anual de 1999 USENIX . Monterey, CA, EE.UU .: Asociación USENIX.
- ^ Manber, U. (1996). "Un esquema simple para hacer que las contraseñas basadas en funciones unidireccionales sean mucho más difíciles de descifrar" (PDF) . Computadoras y seguridad . 15 (2): 171-176. CiteSeerX 10.1.1.102.2597 . doi : 10.1016 / 0167-4048 (96) 00003-X .
- ^ Kelsey, J .; Schneier, B .; Hall, C .; Wagner, D. (1998). "Aplicaciones seguras de claves de baja entropía" (PDF) . Seguridad de la información . LNCS . 1396 . pag. 121. doi : 10.1007 / BFb0030415 . ISBN 978-3-540-64382-1.
- ^ Cómo evitar que Windows almacene un hash de administrador de LAN de su contraseña en Active Directory y bases de datos SAM locales , Microsoft
- ^ Un caso para el uso moderno de la mesa de arco iris
Referencias
- Oechslin, Philippe (17 de agosto de 2003). "Haciendo un intercambio de tiempo-memoria criptoanalítico más rápido". Hacer un intercambio criptoanalítico entre tiempo y memoria más rápido (PDF) . Avances en criptología: Actas de CRYPTO 2003, 23ª Conferencia Anual Internacional de Criptología . Apuntes de conferencias en Ciencias de la Computación. 2729 . Santa Bárbara, California , Estados Unidos: Springer. págs. 617–630. doi : 10.1007 / 978-3-540-45146-4_36 . ISBN 978-3-540-40674-7.
enlaces externos
- Página de Ophcrack por Philippe Oechslin La investigación original de la tabla del arco iris
- Criptografía en Curlie