Veo esta técnica recomendada en muchos lugares (incluida la pila), ¡y no puedo dejar de pensar que esto reduciría la entropía! Después de todo, has hashing algo de nuevo, eso ya ha sido hasheado y tiene una probabilidad de colisión. ¿La probabilidad de colisión sobre la probabilidad de colisión no generaría más posibilidades de colisión? Después de investigar, parece que estoy equivocado, pero ¿por qué?muchas iteraciones en un hash: ¿no reduce la entropía?
Como etiquetó md5, lo usaré como ejemplo. De wikipedia:
si dos prefijos con el mismo hash se pueden construir, un sufijo común se puede agregar a la vez para hacer la colisión más probabilidades de ser aceptados como válidos los datos de la aplicación de usarlo. Además, las técnicas actuales de búsqueda de colisiones permiten especificar un prefijo arbitrario: un atacante puede crear dos archivos colisionantes que comienzan con el mismo contenido. Todo lo que el atacante necesita para generar dos archivos colisionantes es un archivo de plantilla con un bloque de datos de 128 bytes, alineado en un límite de 64 bytes que se puede cambiar libremente mediante el algoritmo de búsqueda de colisiones. Un ejemplo de colisión MD5, con los dos mensajes que difieren en 6 bits, es:
Y luego los ejemplos de texto plano que dan tienen 256 bytes de longitud. Dado que el ataque de colisión se basa en un bloque de datos de 128 byte, y el resumen de hash es solo 128 bits, no existe realmente un mayor riesgo de que un ataque de colisión tenga éxito más allá de la primera iteración, es decir, realmente no puede influir en la probabilidad de una colisión más allá del primer hash.
También tenga en cuenta que la entropía del hash es el mencionado 128 bits. Incluso teniendo en cuenta que la probabilidad de colisión total es de solo 2^20.96 (nuevamente desde wikipedia), se necesitarían muchas iteraciones para hacer que dos entradas colisionen. El razonamiento de primer vistazo del que creo que está siendo víctima es:
Esto puede ser desaprobado por contraejemplo con bastante facilidad. Consideremos de nuevo MD5:
MD5 dos entradas cualesquiera 128 veces seguidas y verá que esto no es cierto. Probablemente no encuentre un solo hash repetido entre ellos - después de todo, solo ha creado 256 de un posible valor de hash de 2^128, dejando 2^120 posibilidades. Las probabilidades de colisiones entre cada ronda son independent de todas las demás rondas.
Hay dos maneras de entender por qué esto es así. El primero es que cada iteración es esencialmente intentar golpear un objetivo en movimiento.Creo que podrías construir una prueba basada en la paradoja del cumpleaños de que hay un número sorprendentemente bajo de iteraciones de hashing donde es probable que veas un resumen de hash de una entrada que coincida con el resumen de hash de una entrada diferente. Pero casi con certeza habrían ocurrido en diferentes pasos de la iteración. Y una vez que eso ocurre, nunca pueden tener el mismo resultado en la misma iteración porque el algoritmo hash en sí mismo es determinista.
El otro enfoque es darse cuenta de que la función hash en realidad agrega entropía mientras se ejecuta. Considere que una cadena vacía tiene un resumen de 128 bits como cualquier otra entrada; eso no puede ocurrir sin la incorporación de entropía durante los pasos del algoritmo. Esto es realmente una parte necesaria de una función hash criptográfica: los datos deben ser destruidos o la entrada puede ser recuperada del resumen. Para las entradas más largas que el resumen, sí, la entropía se pierde en general; tiene que ser para encajar en la longitud del resumen. Pero también se agrega algo de entropía.
No tengo los números exactos para otros algoritmos hash, pero creo que todos los puntos que he hecho se generalizan a otras funciones hash y funciones unidireccionales/de mapeo.
Reduce la entropía.
En un documento llamado Random Mapping Statistics por Flajolet y Odlyzko, un teorema (teorema 2) muestra que:
"Si un n -BIT función aleatoria se itera k veces, el número esperado de puntos de imagen es (1 - The Kid) * 2^n (para grandes n), donde The Kid satisface la relación de recurrencia t_0 = 0 y t_ {k + 1} = e^{- 1 + t_k}. De esto, se puede demostrar que el número esperado de puntos de imagen es 2^{n-i + 1} cuando una función aleatoria se itera k = 2^i veces."
Otras referencias son tan de la siguiente manera:...
Gligoroski, D. y Klima, V., 2010, septiembre de consecuencias prácticas de la aberración de diseños de hash estrecha tubería de funciones aleatorias ideales en la Conferencia Internacional sobre Innovaciones TIC (pp 81- 93). Springer Berlin Heidelberg.
Bhaum ik, R., Dutta, A., Guo, J., Jean, J., Mouha, N. y Nikolić, I., 2015. More Rounds, Less Security?
Dinur, I. y Leurent, G., 2014, Agosto. Se mejoraron los ataques genéricos contra los MAC basados en hash y HAIFA. En la Conferencia Internacional de Criptología (pp. 149-168). Springer Berlin Heidelberg.
Desde el último documento de referencia, uno encontrará los dos lemas siguientes: Two lemmas on entropy loss. Por lo tanto, la observación de la pérdida de entropía también se cumple si se usan k funciones independientes al azar, en lugar de una función aleatoria iterada k veces.
