¿No es seguro tener hashes de partes de una cadena privada?

3

Tenemos la cadena B y los hashes hash(P+B) , hash(P) ; ¿es posible que P sea más fácil de usar con esta información que con hash(P) ? ¿Cuál es la diferencia?
Cualquier enlace a artículos o cualquier tipo de información que me ayude a comprender mejor esto es realmente apreciado.

    
pregunta Behrooz 11.10.2014 - 13:24
fuente

2 respuestas

3

La información adicional solo puede ayudar al atacante; pero esa ayuda adicional podría ser insignificante.

Si modelamos la función hash como una oráculo aleatorio , luego muestra h ( P + B ) para una cadena no vacía dada B no proporciona información adicional útil para el atacante (creo que "+" significa aquí concatenación de cadenas, no suma numérica). Un "oráculo aleatorio" es (en términos aproximados) una función tal que no sabes nada en su salida para ninguna entrada dada sin intentarlo. Cuando tiene h ( x ), puede obtener información sobre x solo a través de la fuerza bruta, es decir, probar valores potenciales para x hasta que se encuentre una coincidencia. Por lo tanto, h ( P + B ) no le da ningún poder adicional al atacante, en comparación con h ( P ), e independientemente de cómo se eligió B : el atacante todavía tiene que probar los valores potenciales de P y espera tener suerte. Lo mejor que puede hacer el atacante para optimizar las cosas de su lado es elegir una estrategia que minimice el costo computacional de cada intento; como las funciones hash comunes tienen un costo proporcional al tamaño de entrada, el atacante preferirá trabajar con h ( P ) que h ( P + B ) de todos modos.

El problema con el modelo de oráculo aleatorio es que las funciones hash habituales son no oráculos al azar. Sin embargo, en el caso de Merkle – Damgård funciones hash (una categoría que incluye funciones hash comunes como MD5, SHA-1, SHA-256 y SHA-512), existe una propiedad llamada " ataque de extensión de longitud ": dado h ( P ), es posible calcular h ( P + B ) para los valores de B que pueden ser, en gran medida, elegidos a voluntad, y puede hacerlo sin saber P (debe saber la longitud de P , pero no su valor real). El ataque de extensión de longitud generalmente se considera una curiosidad inofensiva o una debilidad (en la mayoría de los protocolos, es inofensivo y puede ignorarse); Pero, en nuestro caso, tiene una consecuencia interesante. Es decir, nos permite mostrar que revelar h ( P + B ) no proporciona información adicional al atacante, precisamente porque el atacante sí lo hizo. no es necesario que nos espere: él ya puede calcular h ( P + B ) para una gran clase de < em> B valores.

    
respondido por el Thomas Pornin 11.10.2014 - 15:09
fuente
2

Estoy un poco confundido por la construcción de tu pregunta, pero de todos modos debería poder arrojar algo de luz sobre el tema.

Primero, voy a suponer que cuando dices P+B querías decir que P y B se van a concatenar, en lugar de que esa adición de alguna forma se esté realizando, y yo ' Esto se indica a continuación con la notación || en lugar de + .

En segundo lugar, la salida de una función hash criptográficamente segura no revela ninguna información sobre su entrada. Si lo hiciera, dejaría de ser considerada una función segura. Por lo tanto, simplemente saber que H(P||B) es, de hecho, el hash de dos entradas desconocidas, (P y B) y H(P) es también el hash de una de esas incógnitas que no le proporciona ninguna información sobre lo que realmente son las entradas desconocidas son.

Tercero, una función hash criptográficamente segura producirá resultados que son indistinguibles de los aleatorios para pruebas eficientes. Esto significa que las entradas relacionadas (en este caso el P es la parte relacionada de la entrada) no producirán salidas relacionadas. Dado H(P||B) sin saber que en realidad es un hash de P y B producirá una salida que no está relacionada con la salida de H(P) . No aprenderá nada sobre P o B de H(P) o sobre P de H(P||B) .

Entonces, ¿qué puede ser atacado? Debido a que no se aprende nada sobre las entradas de la salida de una función hash criptográficamente segura, la forma de atacarla es probando las entradas candidatas y comparándolas con la salida de hash dada para ver si coincide, generalmente utilizando un diccionario. o fuerza bruta para generar los candidatos de entrada. Dado esto, cuanto más corta y menos aleatoria sea la entrada, menos candidatos se deben probar para encontrar una coincidencia. Por lo tanto, el enfoque obvio que tomaría un atacante suponiendo que sabe que los hashes son el resultado de H(P||B) y H(P) y sabe cuál es cuál, pero no sabe que P o B sería atacar el salida de H(P) . Debido a que la entrada es más pequeña y los bits de entropía son necesariamente menores ( B debe agregar al menos un bit de entropía a la entrada en virtud de la existencia), un atacante podrá encontrar P más rápidamente que P||B y luego úsalo para atacar a H(P||B) para tratar de encontrar a B .

Sin embargo, esto no significa que encontrar P a partir de H(P) sea necesariamente fácil, o incluso realista, sin embargo. Es solo teóricamente más fácil. puede ser posible, e incluso fácil, pero eso depende completamente de las propiedades de P . Si es pequeño, y no aleatorio, para algunos valores de pequeño y no aleatorio, es completamente factible. Si es grande y bastante aleatorio, el número de pruebas candidatas requeridas puede hacer que no sea factible calcular el número requerido de valores hash para encontrar la entrada correcta.

    
respondido por el Xander 11.10.2014 - 15:22
fuente

Lea otras preguntas en las etiquetas