¿En qué momento la adición de más iteraciones a PBKDF2 no proporciona seguridad adicional?

16

Si mi frase de contraseña verdadera se usa solo para generar un hash que se usa como la clave real del cifrado, ¿no significa eso que es posible intentar y aplicar fuerza bruta al cifrado? Sé que tomaría un tiempo increíblemente largo en ambos sentidos, pero ¿en qué momento sería más rápido simplemente forzar la clave en sí, en lugar de pasar por cada iteración de hash? Para mi disco más seguro, uso iteraciones de 20 segundos (lo que da como resultado aproximadamente 2 millones de iteraciones SHA512) en lugar del valor predeterminado de 1. Si alguien quisiera descifrarlo y tuviera todo el tiempo en el universo (y varias veces), ¿Lo hacen más rápido si optaron por el hash resultante o todos los ASCII posibles por la frase de contraseña original?

EDITAR: Quiero señalar que solo tengo curiosidad por las matemáticas, no por lo práctico. Ya utilizo una frase de contraseña larga, y sé que la fuerza bruta sería increíblemente larga, sé sobre el criptoanálisis de la manguera de goma, etc. Lo único que pregunto es si un adversario en teoría sería capaz de forzar la clave AES directamente. , después de cuántas iteraciones hash sería más difícil forzar bruscamente la clave ASCII que la clave AES directamente ...

    
pregunta kkarl88 24.10.2013 - 07:14
fuente

4 respuestas

14

No hay una respuesta exacta, y he aquí por qué:

Fuerza bruta

Comenzamos con una clave simétrica de 128 bits. Suponiendo que el algoritmo (por ejemplo, AES) aún no esté roto, debemos observar el consumo de energía. Suponiendo que los dispositivos de cómputo sean 100% eficientes cuya tecnología exceda por mucho a cualquier computadora, ASIC, tarjeta gráfica u otro dispositivo de descifrado de claves que pueda imaginar, hay un requisito de energía mínimo para simplemente voltear los bits y contar tan alto. Wikipedia ha hecho los cálculos por nosotros , y sale a, para una clave de 128 bits, el Los requisitos mínimos de energía exigidos por la física son aproximadamente 10 18 joules, o 30 Gigawatts por un año. Obviamente, con el hardware "real", el requisito sería varios cientos de miles de veces eso; Más que la producción de energía de todo el mundo. Así que eso está muy por fuera de la capacidad de cualquier cuerpo terrestre existente.

Pero si nos movemos a una clave de 256 bits, las matemáticas se vuelven más serias. Schneier hizo los cálculos en este caso en Criptografía Aplicada, y se ha discutido aquí anteriormente . Para evitar aburrirte con los detalles repetidos, simplemente llegaré a la conclusión: nuestro sol no produce suficiente energía para realizar esta tarea.

La computación teóricamente reversible (que puede ser posible con las computadoras cuánticas) podría reducir a la mitad la longitud efectiva de los bits, haciendo que tal proyecto esté más allá del alcance de cualquier poder existente, en lugar de estar más allá del alcance de la física. Pero eso es todo académico.

Lo que se lleva es esto: no se puede hacer una clave simétrica de forzado brutal. No por ti, no por nadie.

Rondas equivalentes

Entonces, ¿cuántas rondas de PBKDF2? Si el atacante tiene que elegir entre esperar 10 años hasta que se complete la derivación clave en lugar de construir una esfera Dyson alrededor del sol, la ruta PBKDF2 es aún más rápida. Con cualquier métrica práctica, agregar más tiempo a su derivación de clave significa agregar más tiempo al ataque, y en ningún momento el intento de forzar la fuerza bruta se convertirá en una opción (a menos que la ruta PBKDF2 también requiera un proyecto de construcción extraterrestre).

Entonces, ¿dónde está el punto de equivalencia? ¿Cuándo el PBKDF2 de fuerza bruta requiere la configuración completa de Dyson Sphere? La respuesta es: depende . Vea, el punto principal de usar el proceso hash en su ataque en lugar de adivinar la clave en sí es para que pruebe con menos contraseña. Si sabes la contraseña es "mono" o "123456", entonces es mejor que adivines solo dos veces, en lugar de intentar acertar el hash correcto en un escaneo secuencial.

Entonces, la respuesta depende del tamaño del diccionario que su atacante usará en su ataque. Si sabe la contraseña exacta, entonces solo adivina una vez. Y por lo tanto, el ataque de fuerza bruta tomará exactamente tanto tiempo como el inicio de sesión correcto. Por mucho que lo hagas ser. Si espera obtenerlo en dos intentos, entonces su fuerza bruta tomará exactamente el doble de tiempo que su inicio de sesión correcto. Si tiene un diccionario de 100 palabras para probar, entonces exactamente 100 veces más que su inicio de sesión correcto, y si su contraseña no está en su diccionario, entonces nunca podrá tener éxito, nunca.

Algunas matemáticas prácticas

Entonces, para garantizar que su ataque de fuerza bruta será imposible, también debe garantizar que su inicio de sesión exitoso sea imposible, porque debe tener en cuenta la posibilidad de que su contraseña sea la única. candidato en su lista.

Si, por otro lado, desea obtener un promedio razonable, simplemente haga una división simple. Digamos que quieres que el ataque de fuerza bruta tome 1 billón de años. Y digamos que nuestra contraseña es de 14 caracteres alfanuméricos (así que 1 de cada 10 25 ). Suponiendo que su diccionario tiene todas las contraseñas alfanuméricas, eso es 10 25 contraseñas en 10 12 años (trillón a pequeña escala), o 10 13 adivinanzas por año, o aproximadamente 316900 conjeturas por segundo.

Entonces, mientras ajustemos PBKDF2 de modo que se tarde más de 1 / 300,000 de segundo para adivinar cada contraseña, y nuestra contraseña tenga una longitud de al menos 14 letras, luego de 1 billón de años.

Advertencia

Tenga en cuenta que si el cripto subyacente se rompe, de modo que pueda ser atacado sin adivinar la clave, entonces probablemente se convierta en el método de ataque elegido. Pero no conocemos tal ataque en AES, ni esperamos que exista uno.

    
respondido por el tylerl 24.10.2013 - 09:27
fuente
6

Del artículo de Colin Percival en scrypt :

  

Al utilizar una función de derivación de claves que requiere operaciones criptográficas 2^s para calcular, el costo de realizar un ataque de fuerza bruta contra contraseñas con t bits de entropía se eleva de las operaciones de 2^t a 2^(s+t) .

2,000,000 es aproximadamente 2 ^ 21 iteraciones de SHA-512. Para que esto exceda la seguridad ofrecida por una clave de 128 bits, su contraseña debería tener aproximadamente 107 bits de entropía, o aproximadamente equivalente a una contraseña de 17 caracteres elegida al azar entre mayúsculas, minúsculas, dígitos y doce símbolos.

    
respondido por el Stephen Touset 24.10.2013 - 07:40
fuente
5

Las iteraciones están ahí para ralentizar al atacante. Supongamos que la función está correctamente salada, de modo que lo mejor que puede hacer un atacante es probar todas las contraseñas potenciales hasta que se encuentre una coincidencia. Definimos que la entropía de la contraseña sea igual a los bits n si lo mejor que puede hacer el atacante es, en promedio, intentar 2 n-1 contraseñas: el atacante sabe qué contraseñas son más a menudo elegidas por los usuarios e intenta las contraseñas en el orden "óptimo", y esto funcionará con ese promedio de éxito. (Tenga en cuenta que "promedio" es una palabra muy importante aquí. Todas las matemáticas caen sin esa palabra.)

El uso de "bits" viene del hecho de que si la contraseña es una secuencia de k bits, tal como todos los posibles 2 k las secuencias tienen la misma posibilidad de ser seleccionadas por el usuario, entonces la entropía es, según la definición anterior, igual a k bits. Consulte esta respuesta para obtener explicaciones más extensas en un caso famoso.

A continuación, aplica las iteraciones r en un intento de ralentizar al atacante. El costo computacional para el atacante es, en promedio, r·2n-1 . Por lo tanto, su objetivo es conseguir que r y n sean lo suficientemente altos como para que este costo sea prohibitivo, y el atacante no lo pueda lograr (ya sea que el atacante considere que no vale la pena). esfuerzo, o simplemente no puede). No hay un nivel de seguridad más allá de lo inquebrantable , por lo que existe un número máximo de iteraciones a partir del cual no se obtiene ninguna ganancia real de seguridad. Una vez que el atacante es derrotado, es derrotado. No hay manera de derrotarlo más (aunque podría haber una ganancia psicológica en humillar y intimidar al atacante con una cuenta de iteración tan alta como Burj Khalifa ). Un punto importante es que la motivación del atacante depende del valor de los datos que están protegidos por la contraseña, por lo que los datos de poco valor requieren menos protección.

Ahora puede haber un debate sobre la cuantificación de este nivel "inquebrantable". Tradicionalmente, los criptógrafos han utilizado "80 bits", es decir, 280 "operaciones simples", como límite. Una "operación simple" aquí debe entenderse como una invocación de la función de hash subyacente (por ejemplo, SHA-256) en un mensaje pequeño; en realidad involucra unos cuantos miles de operaciones aritméticas de 32 bits o 64 bits. Este nivel aún se mantiene bastante bien; el mayor esfuerzo comparable publicado fue el descifrado de una clave RC5 de 64 bits, con un esfuerzo continuo de 72 bits, pero actualmente casi se está completando (vea esta página ). Por otro lado, este límite de 80 bits ya se usó hace 20 años (ese es el límite que implica SHA-1 con una salida de 160 bits o firmas DSA con un subgrupo de 160 bits), y la tecnología ha mejorado desde entonces. (Consulte ley de Moore para el punto de entrada que se cita habitualmente en ese debate).

Hoy en día, "128 bits" se usa como "límite seguro" por ahora y también en las próximas décadas. De hecho, esto incluye un gran margen de seguridad, pero 128 es una potencia de 2, por lo que tiene un gran atractivo estético (si los criptógrafos usaran decimales en lugar de binarios, se habrían detenido en 100 bits).

En la práctica , sin embargo, no alcanzarás ese nivel con tus iteraciones. De manera realista, se puede esperar que los usuarios humanos normales tengan contraseñas con una entropía de 30 bits aproximadamente; Más sería demasiado optimista. Se sabe que los mismos usuarios tienen poca paciencia (aparentemente está preparado para esperar 20 segundos, pero la mayoría de las personas no serán tan pacientes). Por lo tanto, puede esperar que un r se cuente en millones, no mucho más. Esto va más o menos a 250 , es decir, un billón de veces más fácil que el límite tradicional de irrompibilidad de 80 bits. Esto lleva a dos conclusiones:

  1. Debe usar tantas iteraciones como sea tolerable para sus usuarios (incluido usted mismo), ya que un alto número de iteraciones implica un mayor retraso. Se le agotará la paciencia del usuario antes de alcanzar el límite de irrompibilidad.

  2. Siempre es mejor aumentar la entropía de la contraseña. El método del "caballo correcto" da como resultado contraseñas que no son difíciles de recordar, pero proporcionan una entropía sustancialmente mejor que los métodos habituales (44 bits, tal como se expuso).

respondido por el Tom Leek 24.10.2013 - 15:28
fuente
1

"Si alguien quisiera descifrarlo y tuviera todo el tiempo en el universo (y varias veces), ¿lo harían más rápido si eligieran el hash resultante o todos los ASCII posibles para la frase de contraseña original?"

Eso depende del ancho de salida de la función hash. Supongamos que la salida es de 32 bits muy baja y su "frase de contraseña verdadera" (¿cuál es la verdad?) Tiene 64 bits de entropía. Entonces, probablemente, los 32 bits tardan menos tiempo en resquebrajarse, si también conoce algún texto claro. El primero toma aproximadamente 2 ^ 32 descifrados y el segundo toma 2 ^ 64, aunque diferentes, adivina

Una frase de contraseña larga no puede ser atacada al intentar "todos los ASCII posibles para la frase de contraseña original", con éxito. Un ataque basado en el diccionario se utiliza en su lugar. Por lo tanto, el cálculo del tiempo de recuperación promedio es diferente del que se realiza con todos los caracteres.

¿Por qué no con éxito? Tomemos, por ejemplo, una frase de contraseña de 5 palabras, existente de solo 28 caracteres en minúscula. Un esquema de fuerza bruta tonta tendría que probar 26 ^ 28 = 10 ^ 40 combinaciones como máximo.

¿Consideró tomar una contraseña más larga en lugar de un retraso sustancial? El factor 2 millones toma aproximadamente 2 palabras adicionales cuando se usa un diccionario Diceware. Cada palabra proporciona aproximadamente 12.9 bits, consulte Cosas opcionales que realmente no necesita saber

    
respondido por el Dick99999 24.10.2013 - 09:09
fuente

Lea otras preguntas en las etiquetas