Una pregunta que he querido responder durante mucho tiempo: ¿Cuál sería la complejidad temporal de encontrar un MD5sum de un binario compilado que contenga el mismo MD5 estático incrustado en él? , por ejemplo, como una cadena?Complejidad del tiempo de un MD5sum incrustado de fuerza bruta
Editar: Si esto no estaba claro. Estoy buscando una respuesta con el complejidad de tiempo y una explicación de él.
Más o menos lo mismo que fuerza bruta: calcular un md5sum es trivial, pero hacer un archivo que coincida con un md5sum conocido es difícil.
Usted está, en el mejor de los casos, buscando una preimagen que le dará un hash conocido (posiblemente agregando datos en el binario).
Es realmente difícil ya que MD5 tiene una buena distribución. Su mejor apuesta por fuerza bruta es agregar algo de hash a su archivo y agregar datos sin sentido al final del binario hasta que el binario tenga el mismo hash que el que está incrustado.
Por otro lado, si quiere comprobar si su binario está intacto y sin modificar, sería mejor dividir el binario en 3 partes: La parte del binario antes del hash, el hash en sí y la parte posterior el hash. Concatenar la primera y la última parte, calcular el hash md5 e incrustarlo en el binario.
gusta esta (ejemplo):
foo098f6bcd4621d373cade4e832627b4f6bar
foo | 098f6bcd4621d373cade4e832627b4f6 | bar
md5(foo+bar) = 3858f62230ac3c915f300c664312c63f
foo3858f62230ac3c915f300c664312c63fbar
Lo que se quiere hacer requeriría un error en el algoritmo hash. Y, de hecho, MD5 isn't very secure, por lo que podría ser posible. Pero no veo cómo cualquiera de las debilidades conocidas podría ayudar en lo que quiere hacer. Incluso un ataque de preimagen no ayudaría, necesitaría ser un "ataque de preimagen de prefijo elegido".
Así que supongo que la única forma posible (hoy) sería utilizar la fuerza bruta.
Si está buscando una manera de 'agregar seguridad' a un archivo binario, truncar el hash, y luego usar fuerza bruta.
Esto es incorrecto. – rook
@Rook: ¿qué es exactamente incorrecto y por qué? –
Eso también depende de las circunstancias. Si el binario es dado, y solo el md5 debe ser insertado en algún lugar, la respuesta puede ser: 0. Debido a que es posible (y lo asumiría quizás en casi todos los casos como este) que no hay un md5 que inserte produce el mismo md5.
En caso de que tenga la posibilidad de modificar más del binario (por ejemplo, teniendo espacio de relleno que puede llenar con números arbitrarios), el único enfoque viable es la fuerza bruta.
Para lograr esto debe encontrar un collision. Esto se puede hacer usando the prefixing attack against md5. Tenga en cuenta que esto solo es posible porque md5 está muy roto. Este ataque tiene un time complexity of 2^24.1, que está al alcance de un escritorio moderno.
Debería encontrar una colisión, pero no una colisión típica (hashes MD5 idénticos), sino una colisión de código hash y (elegida) parte del mensaje. Eso es mucho más difícil. –
Esto se puede resolver en tiempo constante.
El archivo que contiene todos los resúmenes de MD5 posibles contiene el resumen de ese archivo.
Aunque, eso supone que MD5 está bien definido para mensajes de más de 2^64, que es el tamaño del relleno de longitud. –
RFC 1321 no menciona un límite. :) http://tools.ietf.org/html/rfc1321 –
Creo que este es un punto interesante a tener en cuenta, pero digamos que su archivo no puede incluir todos los hash MD5 posibles. – atx
+1 buena pregunta. – rook
Pregunta relacionada: http://stackoverflow.com/questions/235785/is-there-an-md5-fixed-point-where-md5x-x –