Ataques de intercambio de memoria de tiempo

4

Dado, queremos crackear una contraseña. Con Time Memory Trade-Off Attacks , uno trata de encontrar el equilibrio adecuado entre el tiempo para calcular los hashes para todas las contraseñas posibles. Y la memoria utilizada para almacenar todas las tuplas de hash de contraseña, donde una búsqueda sería instantánea.

(Conozco algunos mecanismos de seguridad adicionales como la salazón, la salpicadura, la autenticación de dos factores, ...)

Pero lo que no entiendo es que el intercambio ocurre en el momento del ataque. Pero por lo general, uno escucha el momento para descifrar buenas contraseñas entre vidas humanas, siglos o incluso la vida del sol.

Por lo tanto, la generación de tales tablas todavía es factible para contraseñas cortas, ¿verdad?

Por ejemplo, utilicé zxcvbn y obtuve los siguientes resultados para un 9 caracteres de longitud contraseña.

password:   evhtsxuko
entropy:    42.304
crack time (seconds):   271475183.949
crack time (display):   10 years

Entonces, dado que bcrypt es una función hash lenta y dura aproximadamente 15 años, ¿es seguro asumir que incluso para la NSA es imposible descifrar una contraseña de 10 caracteres con bcrypt?

    
pregunta Angelo.Hannes 16.02.2014 - 14:24
fuente

3 respuestas

3

" Time-Memory Trade-off " es la terminología genérica de un algoritmo que mejora (acorta) el tiempo de ejecución al usar más espacio (memoria); o, de manera similar, eso mejora el uso de la memoria (es decir, usar menos RAM o disco, o usarlo "mejor", por ejemplo, con acceso secuencial en lugar de acceso aleatorio) a expensas de más tiempo de computación.

En el caso del hashing de contraseña , el algoritmo principal de TMTO se debe a Hellman en 1980; posteriormente se descubrieron una serie de mejoras locales, que dieron como resultado lo que se conoce coloquialmente como tablas de arco iris . Podemos obtener una vista conceptual de las tablas del arco iris considerando los dos puntos finales del espectro:

  • La búsqueda exhaustiva se trata de probar todas las contraseñas potenciales, hacerlas todas y comparar el valor con la que se debe descifrar. Esto tiene el costo computacional más alto (hash promedio de N / 2 para calcular las contraseñas potenciales de N con probabilidad uniforme) pero utiliza solo RAM insignificante.

  • Una tabla precomputada contiene los hashes de N contraseñas potenciales, y se debe realizar una única búsqueda. No contamos el esfuerzo de construir la tabla porque, presumiblemente, puede ser reutilizada para múltiples ataques, posiblemente por varios atacantes. El tamaño de la tabla es proporcional a N , pero el esfuerzo computacional es insignificante (bueno, sobre O ( log N) , que es pequeño ).

Las tablas del arco iris cabrán en el medio. Cuando se construye la tabla, elige un parámetro t denominado "longitud de cadena promedio". El tamaño de la tabla será proporcional a N / t : se reduce en un factor de t , en comparación con la tabla precomputada. Por otro lado, cada ataque implicará un esfuerzo de cálculo proporcional a los cálculos de hash t2 y a las búsquedas de t . Dependiendo de las condiciones operativas, las búsquedas o los cálculos serán el cuello de botella (por ejemplo, depende mucho de si la tabla está en la RAM, en un SSD o en un conjunto de discos duros mecánicos).

Las sales desbaratan completamente las tablas precalculadas, incluidas las tablas de arco iris . La construcción de una tabla precomputada para las contraseñas de N ha costado N ; la construcción de una tabla de arco iris para las mismas contraseñas de N tiene un costo aún mayor (aproximadamente 1.7 * N ). Esto vale la pena solo si la tabla se puede usar al menos dos veces, para atacar dos valores hash distintos; una mesa de un disparo (arco iris o no) no compite con una búsqueda exhaustiva. Pero el punto de las sales es que no hay una función una ; de hecho, hay una gran familia de funciones, y el valor de sal le indica cuál se usa realmente. Una tabla creada para una sal específica no tiene absolutamente ningún valor en romper un valor de hash para cualquier otra sal.

Bcrypt usa sales, por lo que no hay tablas, ni TMTO. Los atacantes han vuelto a la búsqueda exhaustiva. Bcrypt también tiene armas contra búsquedas exhaustivas, es decir, una lentitud configurable, obtenida a través de una gran cantidad de iteraciones internas: desde el punto de vista del usuario, no hay mucha diferencia entre un cálculo de hash que toma 1 microsegundo y uno que toma 100 milisegundos. ; pero para el atacante, este último significa 100000 veces el esfuerzo por su búsqueda exhaustiva.

Consulte esta respuesta para obtener más información sobre el hashing de contraseña seguro. . Breve resumen: si su contraseña es fuerte (es decir, tiene una alta entropía), incluso las agencias poderosas no podrán obtenerla rompiendo el hash bcrypt por adelantado (lo obtendrán rompiendo las rótulas, pero esa es otra historia).

    
respondido por el Thomas Pornin 18.04.2014 - 16:08
fuente
0

Bcrypt usa un "factor de trabajo"; los factores de trabajo más altos conducen a un mayor procesamiento requerido para un espacio de teclas determinado.

En cuanto a la estimación de "tiempo", ¿qué recursos se proyecta que tenga el atacante? Si la estimación se basa en N recursos, y el atacante arroja recursos de 1000N, entonces el atacante puede agotar el espacio de teclas o ejecutar su ataque de diccionario basado en reglas en 1/1000 del tiempo.

En lo que respecta al intercambio de tiempo / memoria real, si tiene una gran cantidad de sal aleatoria, no hay una forma razonable de generar listas precalculadas para cada valor posible de sal, por lo que todo es trabajo de tiempo de ejecución. Se pueden generar listas de WPA porque la sal es el SSID, que rara vez es aleatorio.

Tenga en cuenta también que si su contraseña no es realmente aleatoria, entonces los ataques a los diccionarios basados en reglas son el mayor peligro, no la fuerza bruta pura o incluso las cadenas de Markov.

Además, ¿la estimación de la fuerza tiene en cuenta la Ley de Moore (o algún otro factor de aumento exponencial)? Todas las estimaciones de "toda la vida del sol" no tienen en cuenta que los atacantes compran hardware nuevo una vez que mejora.

    
respondido por el Anti-weakpasswords 17.02.2014 - 08:20
fuente
0

Bcrypt toma dos parámetros: una contraseña y un factor de trabajo. El factor trabajo le dice cuánto tiempo gastar en el problema.

Los diferentes factores de trabajo dan diferentes resultados, por lo que el factor de trabajo actúa como una especie de sal secundaria. Normalmente no lo piensas de esa manera, pero es parte de por qué rara vez ves bcrypt en las bases de datos hash. Para hacer coincidir el hash, necesita tanto la contraseña como el factor de trabajo correcto. Por lo tanto, su base de datos necesita un conjunto separado de hash bcrypt para cada factor de trabajo potencial.

En cuanto a si la NSA será capaz de descifrar hashes de 10 caracteres, está en el extremo más alejado de la probabilidad, pero no del todo. Salta hasta 14 caracteres y prácticamente lo tienes.

    
respondido por el tylerl 19.03.2014 - 09:40
fuente

Lea otras preguntas en las etiquetas