¿Qué tan preciso es `md5sum`?

27

Cuando se utiliza md5sumpara verificar la integridad de un archivo, ¿qué tan preciso es el proceso?

¿Un MD5 verificado significa que CADA bit es exactamente el mismo, o hay un umbral que debe romperse antes de que la alteración binaria se refleje en el MD5?

También se agradecería cualquier documentación sobre cómo se genera un md5.

Konner Rasmussen
fuente
@choroba si estoy leyendo todo esto correctamente, entonces la probabilidad de alteración no detectada aumenta con el tamaño del archivo que se verifica. Sin embargo, todavía es una probabilidad y solo se puede tener una certeza del 100% con un archivo de 16 bytes. ¿Estoy en lo correcto?
Konner Rasmussen
@ Konner Leí tu pregunta sobre la transferencia de archivos. Para ese propósito, es seguro. Las posibilidades de que se corrompa un poco en una transferencia son pequeñas y es más probable que pierda parte del archivo copiado en la transferencia, suponiendo que haya entendido su situación anterior . MD5 es en esfuerzo equivalente a comparar ambos archivos, con alguna ventaja en el hecho de que no necesita acceder a ambos archivos al mismo tiempo.
Doktoro Reichard
15
"¿Un MD5 verificado significa que CADA bit es exactamente el mismo". Tenga en cuenta que esto es imposible, gracias al Principio de Pigeonhole. en.wikipedia.org/wiki/Pigeonhole_principle
Plutor
3
Tampoco creo que obtenga una garantía para los archivos de 16 bytes.
Mooing Duck

Respuestas:

65

MD5 está roto para este propósito contra un adversario inteligente. Es posible construir maliciosamente dos bloques diferentes de datos que producen el mismo hash MD5.

Sin embargo, es totalmente adecuado (aunque seguramente hay mejores formas) de usar MD5 para proteger contra la corrupción accidental de datos en tránsito o en almacenamiento. Si bien es concebible que tal evento pueda causar que el hash MD5 sea el mismo, la probabilidad es tan baja que es casi inimaginable que sería una probabilidad por la que vale la pena preocuparse. Las fallas causadas por radiación de fondo, túneles, estática y docenas de otras fuentes serían órdenes de magnitud más probables.

Incluso si tuviera un billón de unidades de datos, la probabilidad de que un MD5 no coincidente produzca un hash MD5 perteneciente a una de esas billones de unidades es mucho menor que uno en un billón.

David Schwartz
fuente
Si bien puede ser teóricamente posible generar dos archivos con el mismo hash, puede ser prácticamente inviable. Especialmente si el archivo de reemplazo también debería tener sentido. Si el archivo original era texto en inglés, por ejemplo, puede que no haya otra coincidencia que también sea inglés. O si se trata de una hoja de cálculo de Excel, ninguno de los otros archivos con el mismo hash serían hojas de cálculo válidas.
Barmar
1
@Barmar: win.tue.nl/hashclash/Nostradamus estos muchachos crearon una serie de archivos pdf con el mismo hash MD5 para demostrar que era prácticamente factible.
philfr
26

MD5 es un hash. Básicamente, asigna todo el contenido de un archivo en una pequeña cadena de 16 bytes de longitud IIRC.

Obviamente habrá varios archivos que se combinan con la misma suma MD5. Por lo tanto, una suma MD5 coincidente no es garantía de una coincidencia exacta entre archivos.

No existe un umbral como tal debido a la forma en que funcionan los hashes. Por lo tanto, una suma MD5 puede detectar incluso un solo cambio de bit. Sin embargo, muchos cambios de un solo bit juntos pueden hacer que el hash MD5 sea el mismo. Por lo tanto, es bastante razonable usar MD5 para validar la integridad del archivo contra la corrupción aleatoria, pero no si es posible una intención maliciosa ya que alguien podría modificar un archivo mientras se asegura de que el hash MD5 sea el mismo.

Itai
fuente
1
En resumen, un md5 no es más que una forma rápida y sucia de verificar la integridad del archivo, y solo debe usarse cuando un error no detectado no causaría repercusiones cataclísmicas ... ¿correcto?
Konner Rasmussen
3
el mejor uso es detectar corrupción durante la transferencia o copia. no realmente como una cosa de seguridad.
Michael Martinez
12
@KonnerRasmussen: no se trata del grado de repercusiones, es la naturaleza de la amenaza. Si le preocupa que dos documentos puedan tener accidentalmente el mismo MD5, deje de preocuparse: las probabilidades son considerablemente mayores de que sus computadoras exploten espontáneamente; si le preocupa que un atacante inteligente pueda producir un documento que coincida con uno que ya tiene, es una preocupación seria y debería obtener un mejor hash; si le preocupa que un atacante inteligente pueda producir dos documentos que coincidan entre sí, no se "preocupe": ciertamente sucederá.
Malvolio
55
Por supuesto, aunque generar una colisión hash MD5 es teóricamente posible, generar una colisión útil (como en, el archivo en colisión es el mismo tipo de archivo y su contenido es al menos plausiblemente auténtico) es mucho más difícil ...
Shadur
66
@Shadur: Ese solía ser el caso, pero la investigación de seguridad en curso ha descubierto nuevas formas de generar colisiones MD5 que lo hacen más fácil. En particular, si su formato de archivo permite fragmentos de datos de "comentario" de formato libre, es posible que coincida con cualquier hash MD5 insertando un comentario adecuado.
MSalters
17

Un MD5-Hash consta de 128 bits. Un solo bit invertido en la fuente voltea (en promedio) 64 bits en el hash.

La probabilidad de que dos hashes colisionen accidentalmente es 1/2 ^ 128, que es 1 en 340 undecillion 282 decillion 366 nonillion 920 octillion 938 septillion 463 sextillion 463 quintillion 374 quadrillion 607 trillion 431 billones 768 millones 211 mil 456.

Sin embargo, si mantiene todos los hash, entonces, gracias a la paradoja de cumpleaños, la probabilidad es un poco mayor. Para tener un 50% de posibilidades de que un hash choque, necesitas 2 ^ 64 hashes. Esto significa que para obtener una colisión, en promedio, necesitará hash 6 mil millones de archivos por segundo durante 100 años.

Fuente: porneL, /programming/201705/how-many-random-elements-before-md5-produces-collisions

Zsolt Szilagy
fuente
8
¿Entonces estás diciendo que todavía hay una posibilidad? : p
Holloway
1
El problema es que, aunque NECESITAS hacer hash 6 mil millones de archivos por segundo durante 100 años para asegurarte de encontrar una colisión; bien podría suceder en el primer segundo.
deroby
Es cierto que podría suceder el primer segundo. Pero como siempre se trata de equilibrar razones. Podría haber aplicaciones militares donde ese riesgo no es aceptable, pero alquilaría un automóvil sin pensarlo dos veces cuando los sensores de airbag usan md5. Recuerde, lo más probable es que reciba un rayo varias veces mientras espera una colisión md5.
Zsolt Szilagy
Lo siento, pero la mitad de 2 ^ 128 es 2 ^ 127, no 2 ^ 64.
fischi
2
@fischi, lea el enlace en la paradoja del cumpleaños y también en.wikipedia.org/wiki/Birthday_attack : no se trata simplemente de reducir a la mitad el número total de hashes. Dado el espacio de búsqueda H, el número de hashes que debe generar antes de obtener un 50% de posibilidades de colisión es aproximadamente sqrt ((pi / 2) * H). Si haces los cálculos con 2 ^ 128, obtendrás un número aproximadamente 2 ^ 64
Paul Dixon