¿Cuál es el límite práctico para la fuerza bruta basada en la tabla arco iris?

Digamos que eligieron aleatoriamente alfanumérico (A-Za-z0-9 sin símbolos) tanto para el salt como para la contraseña; por ejemplo, el espacio de muestra es (62) ^ M posibles sales y (62) ^ N contraseñas.

Digamos que tienen un millón de GPU en una granja a su disposición que pueden generar mil millones de hashes por segundo (suponiendo que sean simples hashes tipo MD5 o SHA, los hashes basados en bcrypt o PBKDF son mucho más lentos). Entonces, para una sal determinada, pueden descifrar una contraseña de 8 caracteres en 0.2 segundos (200 000 GPU-segundos), una contraseña de 10 caracteres en 14 minutos (26 GPU-años), una contraseña de 12 caracteres en 37 días (100 000 GPU). - años), una contraseña de 16 caracteres en 1,5 millones de años (1,5 billones de años de GPU).

O otra forma de pensar en ello; una GPU típica para generar mil millones de hash por segundo utiliza ~ 200 W. Por lo tanto, si la electricidad le cuesta $ 0,10 por kWHr y descuidando los costos de inicio, una hora de GPU cuesta $ 0.02. Entonces, una contraseña de 8 caracteres cuesta ~ $ 1, 10 caracteres $ 4600, 12 caracteres $ 18 millones, 16 caracteres - $ 260 billones (la oferta monetaria mundial es del orden de $ 10 billones). (Y esto descuida el costo de comprar / mantener un millón de GPU, solo electricidad).

En cuanto a una tabla de arco iris, en algún punto tiene que construirse. Así que quieres una tabla de arco iris completa para los 4 prefijos de caracteres; y desea cubrir todas las contraseñas de hasta 8 caracteres (por ejemplo, un total de 12 contraseñas de caracteres) tomará 100 000 años de GPU (37 días de un millón de GPU) y costará alrededor de $ 18 millones en factura eléctrica.

Básicamente, cuando M + N > ~ 12 para los alfanuméricos aleatorios, comienza a volverse inviable (por ejemplo, es inviable en M + N = 16).

EDITAR: Nueva tabla de resumen, donde enumero la longitud y el tipo de la contraseña (por ejemplo, 8 A-Za-z0-9 significa 8 caracteres en mayúscula + minúscula + contraseña numérica).
También se incluye una contraseña específica de la aplicación de Google ( 16 letras minúsculas aleatorias) aunque, obviamente, las contraseñas de tipo google normalmente tendrían que ser atacadas en línea (no como un hash sin conexión atacado por una granja de GPU).

  PW Length  | # of PW | PW Entropy |       GPU-time | Electricity Cost at $0.10/kW-hr
-------------------------------------------------------------------------------------------
 8 A-Za-z0-9 | 2x10^14 | 47.6 bits  |       60 hours |                  $1
10 A-Za-z0-9 | 8x10^17 | 59.5 bits  |       26 years |              $4 600
12 A-Za-z0-9 | 3x10^21 | 71.4 bits  |   100 000 years|         $18 000 000 ($18 million)
14 A-Za-z0-9 | 1x10^25 | 83.4 bits  | 390 million yrs|     $69 000 000 000 ($69 billion)
16 A-Za-z0-9 | 5x10^28 | 95.2 bits  |1500 billion yrs|$260 000 000 000 000 ($260 trillion)
-------------------------------------------------------------------------------------------
16 a-z       | 4x10^22 | 75.2 bits  | 1.4 million yrs|        $242 000 000 ($242 million)

Pido disculpas con anticipación porque esta respuesta no será una respuesta directa a tu pregunta, pero quería publicarla para que la gente sepa que la pregunta que haces es en realidad solo académica. La respuesta real a esta pregunta es: no use sha1, use bcrypt . Los sha1 y md5 del mundo fueron diseñados para ser rápidos y no es una buena calidad para las contraseñas de hash. Bcrypt está diseñado para permitir la configuración de la cantidad de tiempo que lleva el hash de una contraseña, por lo que puede ralentizar el proceso de hash solo lo suficiente para que los usuarios no noten la diferencia, pero tomará órdenes de magnitud más tiempo para que un atacante generar una tabla de arco iris o fuerza bruta una contraseña. Para obtener más información sobre bcrypt y por qué debería usarlo, consulte esta question .

Además de todo esto, bcrypt también incluye un esquema de salazón. Debido a las razones mencionadas anteriormente, puede estar bastante seguro de que las sales de 20 bytes mencionadas por woliveirajr serán viables en el futuro.

Hay tablas de arco iris y hay fuerza bruta ... estas son dos cosas distintas.

Una rainbow table es un caso especial de una gran tabla precomputada de contraseñas con hash. Como tal, una tabla arco iris puede "invertir" un hash, es decir, recuperar una contraseña coincidente, solo si, en algún momento durante la construcción de la tabla, esa contraseña fue considerada y hash. En consecuencia, si se puede encontrar una contraseña con una tabla de arco iris, entonces se podría haber encontrado con un simple ataque de diccionario que No han costado más que el edificio de la mesa. El "arco iris" no cambia eso; de hecho, la cosa del arco iris en realidad hace que la tabla sea más costosa para construir, por un factor de alrededor de 1.7 (esto se debe a que la construcción de la tabla tiende a considerar y hash varias veces las mismas contraseñas, y eso es bastante inevitable).

Una consecuencia es que ninguna tabla de arco iris vale la pena, a menos que se pueda aplicar al menos dos veces . Utilizamos sales precisamente para evitar que eso suceda. Se puede considerar que la sal es una variante de la función hash, ya que cada nueva sal implica una nueva variante. Una tabla precomputada vale cualquier cosa solo si se precomputó con la misma variante (la misma sal) que el valor hash que se va a atacar. Si no se usa un valor de sal más de una vez, el atacante inteligente no perderá su tiempo construyendo mesas de arco iris de Kleenex; él solo correrá un ataque de diccionario.

Consideramos que el atacante conoce la sal. Por qué ? Debido a que el servidor lo sabe, y el modelo de ataque es que el atacante podría obtener un volcado de la base de datos del servidor. Lo que el servidor sabe, el atacante también lo sabe. Por lo tanto, al atacar una contraseña con hash, la longitud o el contenido de la sal no importan (el atacante debe incluir el valor de la sal en sus cálculos, pero la longitud de la sal no hará que su tarea sea más fácil o más difícil).

Por lo tanto, solo tenemos la contraseña como línea de defensa. Si queremos saber cuánto cuesta el ataque, esto se convierte en economía y, como tal, surge cierta complejidad. En particular, queremos saber si estamos hablando de un atacante que busca una contraseña muy valiosa (por ejemplo, la contraseña que protege la computadora principal de la fuerza alienígena que está a punto de destruir la Tierra). o un atacante que se gana la vida rompiendo muchas contraseñas. En este último caso, los costos de hardware se vuelven insignificantes con respecto al consumo de energía.

Si tomamos las estimaciones de @ jimbob, el hardware que calcula 10 hass por segundo ⁹ utiliza 200W de potencia, y la potencia es de $ 0.1 por kWh (tenga en cuenta que el costo de energía incluye refrigeración: cada vatio gastado en la computación también se convierte en calor, que debe ser disipado de alguna manera). Esto nos da 1.8 * 10 ¹⁴ valores hash por dólar. De eso, obtenemos lo siguiente:

• Con $ 10K, un atacante puede probar 1.8 * 10 ¹⁸ valores hash, que es más o menos el número de contraseñas posibles de 10 caracteres alfanuméricos (mayúsculas, minúsculas y dígitos).

• Con 683.7 billones de dólares (ese es el presupuesto militar de los EE. UU. en 2010 ), un atacante podría intentarlo aproximadamente 1.23 * 10 ²⁶ valores hash, correspondientes a aproximadamente 14.5 caracteres alfanuméricos. Permítanme agregar que esta cifra corresponde a la producción anual de aproximadamente cien plantas de energía nuclear, por lo que el esfuerzo de craqueo difícilmente sería imperceptible.

Conclusión: con 15 caracteres alfanuméricos aleatorios, sus contraseñas se resistirán incluso a los enemigos inverosímiles, incluso si usted frustró totalmente el hashing utilizando una sola invocación de SHA-1, en lugar de usar bcrypt o PBKDF2 con un alto recuento de iteraciones, como debes hacer . Tenga en cuenta que esto solo es válido para los caracteres aleatorios , no para el tipo de caracteres que pueda encontrar en la privacidad de su cerebro. Los cerebros humanos no son buenos en absoluto al azar.

Las tablas de arco iris representan una compensación entre el tiempo de CPU y el almacenamiento, por lo que en teoría la respuesta a esta pregunta es incognoscible. Depende de qué lado de la compensación favorezca su atacante: si tienen mucho tiempo de CPU disponible, al encontrar un nuevo valor de sal, el atacante puede comenzar a calcular una nueva tabla, por lo que no tiene ningún valor (este extremo es equivalente a el atacante es capaz de forzar una clave de forma bruta sin utilizar tablas precomputadas). Si tienen mucho espacio de almacenamiento, pueden calcular de antemano las tablas para cualquier valor de sal, pero les llevará mucho tiempo, así que cuanto más grande mejor.

Por supuesto, las cosas que no funcionan en teoría a menudo funcionan muy bien en la práctica. El mundo real se inyecta a sí mismo en este punto y nos dice que para muchos atacantes, tanto el tiempo de almacenamiento como el de CPU son limitados. Cuanto más larga es la sal, más atacantes no tienen los recursos para montar un ataque exitoso. Aceptando esa relación, entonces hay una desigualdad que proporciona un límite superior en su elección del tamaño de sal:

El total de recursos de su lado requeridos para trabajar con los hash salados debe ser menor que los recursos necesarios para satisfacer los otros requisitos de su aplicación.

Este es mi entendimiento, me disculpo si esto es incorrecto de todos modos.

El uso de un salt con contraseñas hace que las tablas de arco iris sean casi inútiles para los ataques en la mayoría de los casos. Con la longitud de la contraseña P y una longitud de sal de S , necesitaría espacio P * S con búsquedas de fuerza bruta ingenuas (agregando una sal aleatoria tiene que crear las tablas de S para cada contraseña). Las tablas del arco iris reducen el espacio requerido para almacenar las búsquedas de la contraseña pero no eliminan la multiplicación en S (my Uni maths no es lo suficientemente bueno como para darle la correcta Notación Big O , que puede ser un ejercicio para el lector: P).

El cálculo se puede considerar como la longitud de su conjunto de caracteres aceptado ( c ) elevado a la potencia de la contraseña ( p ) multiplicado por el número de sales posibles ( s ).

(c^p) * s

Basta con decirlo, esto puede llegar a ser un número muy grande muy rápidamente.

Escenario 1

¿Podría un gobierno construir un sistema suficientemente grande para romper un esquema de contraseña y sal utilizando tablas de arco iris? Esto depende del tamaño de las contraseñas, el conjunto de caracteres disponible y el tamaño de sal. Por encima de un cierto tamaño, empiezas a alcanzar límites físicos (¿puedes realmente codificar todas las permutaciones en un dispositivo usando la materia / energía disponible?). Los gobiernos a menudo tienen mayores recursos que la mayoría de las instituciones, pero incluso ellos no pueden agotar estos límites físicos.

La única forma de evitar esto sería intentar y usar la intuición o el conocimiento previo para reducir el espacio de búsqueda. Para un sistema de uso común, las contraseñas de las personas estarán por debajo de cierta longitud, por lo que solo se molestarán en comprobarlas. Es probable que también usen solo un subconjunto del conjunto de caracteres disponible. Puede usar estos para concentrar qué hashes se usan para poblar su tabla de arco iris ( p y c ). Pero siempre se enfrentará al hecho de que se multiplica por la sal aleatoria ( s ).

Tienes un sal aleatorio ¿no es así? Aquí es donde la gente comienza a preocuparse por la entropía de los números aleatorios. Es bastante difícil de explotar cuando se usan datos no aleatorios donde se necesitan datos aleatorios reales, pero esta es una de esas situaciones en las que entra en juego. Considere el problema anterior en el que ha logrado reducir (p ^ c) haciendo intuiciones sobre la naturaleza de la contraseña. Si sabemos algo sobre qué tan aleatorias son las sales (o podemos influirlas de alguna manera) podemos comenzar a reducir el tamaño de s . Podemos saber (o podemos influir) que el s esté entre un determinado conjunto de valores y, por lo tanto, reducir drásticamente las permutaciones en las tablas del arco iris. Si un atacante puede obtener esto por debajo de los límites físicos razonables, entonces un gobierno (que estaba tan inclinado) podría usar tablas arco iris para descifrar las contraseñas.

(Espero que esto también haya respondido a su pregunta relacionada)

Escenario 2

En los niveles actuales de 2012, diría que, a menos que haya sido increíblemente afortunado, la posibilidad de que usted pueda descifrar contraseñas de sal y contraseña (ignorando las debilidades técnicas en su implementación) es increíblemente escasa. Esto supone que usas longitudes razonables para p , c y s .

Consulte enlace y enlace para una lectura interesante sobre este asunto (que es casi seguro que he usado y abusado incorrectamente).