Función de hash sensible a la ubicación (LSH) que coincide aproximadamente con las contraseñas antiguas

Question

Función de hash sensible a la ubicación (LSH) que coincide aproximadamente con las contraseñas antiguas

#1 de jbms (1 votos)
#2 de DanielE (0 votos)

2

Recientemente, encontré un sitio web que me obliga a cambiar mi contraseña después de que hayan transcurrido X días desde la última vez que creé una. Inteligentemente, el servicio se aseguró de que la contraseña no coincidiera (aproximadamente) con ninguna otra que haya usado antes (algo que claramente no usaba permutaciones). Sin embargo, me intrigó la forma en que podría haber hecho esto, ya que mi ingenua comprensión en ese momento era que tendrían que almacenar texto sin formato para calcular una distancia entre dos cadenas.

Intentando no asumir lo peor del sitio web (es administrado por una organización multimillonaria, para uso interno de los empleados), indagué un poco más en los métodos que se han utilizado. Lo primero que pensé fue en la comparación de sub-cadena de hash (inmediatamente lo descarté debido al posible debilitamiento del texto simple). Pensé que podrían hacer un hash de permutación (una vez más, deseché esto porque coincidía con los aproximados, e incluso con algunas modificaciones, pareció funcionar bastante bien).

Fue entonces cuando me topé con LSH como un concepto. Pensé que era una buena idea, que permitía una comparación de datos de conocimiento cero. Es decir, crear un hash que tiene una alta probabilidad de hacer coincidir cosas similares a sí mismo, pero comprime y no contiene necesariamente la información del texto en llano del que se derivó.

Algo a lo largo de las líneas de enlace

773e2df0a02a319ec34a0b71d54029111da90838cbc20ecd3d2d4e18c25a3025 spam1   47182cf0802a11dec24a3b75d5042d310ca90838c9d20ecc3d610e98560a3645 spam2

El nilsimsa de estos dos códigos es 92 en una escala de -128 a +128. Eso significa que 36 bits son diferentes y 220 bits iguales. Cualquier nilsimsa sobre 24 (que es 3 sigma) indica que los dos mensajes probablemente no se generen de forma independiente.

¿Esto es seguro y, de no ser así, hay una versión segura de dicho método? Gracias.

passwords hash storage

pregunta Daymon Schroeder 04.03.2014 - 00:48

fuente

2 respuestas

Lea otras preguntas en las etiquetas passwords hash storage

¿Cómo puedo almacenar la información de forma segura cuando no puedo usar crypt o un hash? ¿El uso de Chrome omite el error gotofail de Apple iOS?

score 1 · Answer 1

Una función hash sensible a la localidad por definición no posee el efecto de avalancha ( enlace ), que es una propiedad clave Para una función criptográfica hash. Las propiedades deseables para LSH son esencialmente lo opuesto a lo que es deseable para una función criptográfica de hash.

Efectivamente, almacenar el hash sensible a la ubicación de una contraseña no es mejor que almacenar la contraseña en forma clara.

Un método simple que se puede usar para verificar si una contraseña es similar a la anterior, sin desviarse de la práctica recomendada de almacenar solo un hash criptográfico con sal de la contraseña, es simplemente usar algún método para enumerar un montón de contraseñas similares a una contraseña determinada (por ejemplo, alterar, agregar o eliminar una letra) y luego, para cada contraseña anterior, calcular el hash de cada contraseña similar con el salt apropiado para ver si coincide. Sin embargo, si se utiliza un hash de contraseña extremadamente lento, este método podría ser problemático.

score 0 · Answer 2

Este esquema no es seguro. Déjame explicarte por qué.

Salt

Una condición importante para que un esquema de hashing de contraseñas sea seguro es que se utiliza un salt aleatorio único que se combina con la contraseña antes de calcular el hash. Se requiere una sal para hash de contraseñas iguales a hashes diferentes. Esto protege de ataques donde se usa una tabla de arco iris. Además, un atacante no puede obtener información de las frecuencias observadas de los mismos hashes porque todos los hashes son diferentes. Si no se usa sal, un atacante podría intentar atacar los hashes más comunes primero porque estas suelen ser contraseñas muy débiles.

El uso de un salt un LSH ya no tiene sentido porque la combinación salt + password difiere demasiado. Los hashes resultantes también diferirán demasiado.

Ataque a hashes LSH sin sal

Si se usa un LSH sin sal y este LSH devuelve hashes similares (no iguales) para contraseñas similares, se me ocurre una forma de atacar esos hashes:

Si un atacante quiere descifrar una contraseña, puede comenzar con el hash de una contraseña arbitraria primero. Luego puede usar la diferencia del hash de destino y el hash de su contraseña seleccionada para adaptar esa contraseña que intentará en el siguiente paso. Repite esto hasta que encuentra la contraseña correcta.

Este es un simple problema de optimización. Hay algunos métodos bien conocidos para resolver problemas de optimización. Por ejemplo, los algoritmos genéticos podrían ser adecuados para este ataque. Usted define la función de aptitud como el número de bits que no coinciden y el objetivo es minimizar esa función.

Posible solución

Hay una solución posible que se me ocurre. Mantenga una lista de las contraseñas que un usuario ha usado hasta ahora y cifre esta lista. Para el cifrado / descifrado, use un HSM (módulo de seguridad de hardware). Las claves se almacenan en el HSM y no se puede acceder a ellas (por ejemplo, leer) a través del software. Por lo tanto, la clave no puede ser expuesta. La única forma en que el atacante puede obtener las contraseñas de texto simple es descifrar los textos cifrados en el hardware donde está instalado el HSM. También debe monitorear el HSM para detectar anomalías, por ej. para detectar un aumento en el número de operaciones de descifrado.