¿Es posible crear un archivo falsificado que tenga las mismas sumas de comprobación utilizando dos algoritmos diferentes?

Question

que estaba un poco inspirado en esta entrada del blog http://blogs.technet.com/dmelanchthon/archive/2009/07/23/windows-7-rtm.aspx (alemán)

La idea actual es que MD5 y SHA1 son a la vez un poco roto. No es fácil y rápido, pero al menos para md5 en el rango de una posibilidad práctica. (No soy en absoluto un experto en criptografía, así que tal vez estoy equivocado en cosas como esa).

Así que me pregunté si sería posible crear un archivo de A' que tiene el mismo tamaño , la misma suma md5 , y la suma misma sha1 que el archivo original A.

Primero, ¿sería posible?

En segundo lugar, ¿sería posible en la realidad, con el hardware/software actual?

Si no, ¿no sería la forma más fácil de proporcionar la seguridad de la integridad de un archivo utilizar siempre dos algoritmos diferentes, incluso si tienen algún tipo de debilidad?

Actualizado:

Solo para aclarar: la idea es tener un archivo A y un archivo de A', que quedan satisfechas las condiciones:

size(A) == size(A') && md5sum(A) == md5sum(A') && sha1sum(A) == sha1sum(A')

Answer 1

"¿Sería posible?" - Sí, si el tamaño total de las sumas de comprobación es menor que el tamaño total del archivo, es imposible evitar las colisiones.

"¿Sería posible en la realidad, con el hardware/software actual?" - si es factible construir un texto para que coincida con una suma de comprobación dada para cada una de las sumas de comprobación en uso, entonces sí.

Ver wikipedia on concatenation of cryptographic hash functions, que también es un término útil para google.

Desde esa página:.

"Sin embargo, para Merkle-Damgard de hash funciones, la función concatenada es sólo tan fuerte como el mejor componente , no más fuerte de Joux señaló que el 2-colisiones conducen a n-colisiones: si es factible encontrar dos mensajes con el mismo MD5 de hash, es efectivamente no más difícil encontrar tantos mensajes como el atacante desea con idénticos hash MD5 Entre el. n mensajes con el mismo hash MD5, es probable que una colisión en SHA-1. El trabajo adicional necesario para encontrar el colisión SHA-1 (más allá de la búsqueda de cumpleaños exponencial) es polinomio. Este argumento es resumido por Finney."

Answer 2

En teoría se podría hacer esto. En la práctica, si comenzó con las dos sumas de comprobación proporcionadas por MD5 y SHA1 e intentó crear un archivo que produjera las mismas dos sumas de comprobación, sería muy difícil (muchas veces más difícil que crear un archivo que produjera la misma suma de comprobación MD5, o Suma de comprobación SHA1 aisladamente).

Answer 3

Así que me pregunté si sería posible crear un archivo de A' que tiene el mismo tamaño, la misma suma MD5 y la misma suma SHA1 que el archivo original A.

Sí, hacer una copia del archivo.

Aparte de eso, no sin grandes cantidades de recursos informáticos para comprobar toneladas de permutaciones (suponiendo que el tamaño del archivo no es trivial).

Se puede pensar en ello como esto:

Si tamaño de archivo aumenta n, la probabilidad de un posible aumento de falsos, pero los costes informáticos necesarios para probar las combinaciones aumenta exponencialmente por 2^n.

Cuanto más grande sea su archivo, más probable es que sea un trucado, pero es menos probable que lo encuentre.

Answer 4

En teoría, sí puede tenerlo, en la práctica es una gran colusión. En la práctica, nadie puede crear una colusión SHA1 y mucho menos MD5 + SHA1 + Size al mismo tiempo. Esta combinación es simplemente imposible en este momento sin tener toda la potencia de la computadora en el mundo y ejecutarla por un tiempo.

Aunque en un futuro cercano podríamos ver más vulnerabilidades en SHA1 y MD5. Y con el apoyo de un mejor hardware (especialmente GPU), por qué no.

Answer 5

Para una respuesta ingenua, tendríamos que hacer algunas suposiciones (incorrectos):

• Tanto el SHA1 y MD5 algoritmos hash dar lugar a una distribución uniforme de los valores hash para un conjunto de entradas aleatorias
• algoritmo detalles a un lado - una cadena de entrada al azar tiene la misma probabilidad de una oportunidad de producir cualquier valor hash

(dominios Básicamente, sin la formación de grumos y muy bien distribuida.)

Si la probabilidad de descubrir una cadena que colisiona con el hash SHA1 de otro es p1, y de manera similar p2 para MD5, la respuesta ingenua es la probabilidad de encontrar uno que colisione con ambos es p1 * p2.

Sin embargo, los valores hash están rotos, por lo que sabemos que nuestras suposiciones son incorrectas.

Los valores hash se agrupan, son más sensibles a los cambios con algunos datos que otros, y en otras palabras, no son perfectos. Por otro lado, un algoritmo de hash perfecto, no roto tendrá las propiedades anteriores, y eso es exactamente lo que hace que sea difícil encontrar colisiones. Ellos son aleatorios.

La probabilidad depende intrínsecamente de las propiedades del algoritmo; básicamente, dado que nuestras suposiciones no son válidas, no podemos determinar "fácilmente" qué tan difícil es. De hecho, la dificultad de encontrar información que colisiona probablemente dependa fuertemente de las características de la cadena de entrada en sí. Algunos pueden ser relativamente fáciles (pero probablemente poco prácticos en el hardware actual), y debido a la naturaleza diferente de los dos algoritmos, algunos pueden ser imposibles.