Qual é a precisão do `md5sum`?

27

Ao usar md5sumpara verificar a integridade de um arquivo, qual é a precisão do processo?

Um MD5 verificado significa que TODOS os bits são exatamente iguais ou existe um limite que deve ser quebrado antes que a alteração binária seja refletida no MD5?

Qualquer documentação sobre como um MD5 é gerado também seria apreciada.

Konner Rasmussen
fonte
12
en.wikipedia.org/wiki/MD5
choroba 14/04
@choroba Se estou lendo tudo isso corretamente, a probabilidade de alteração não detectada aumenta com o tamanho do arquivo que está sendo verificado. No entanto, ainda é uma probabilidade e 100% de certeza só pode ser obtida com um arquivo de 16 bytes. Estou correcto?
Konner Rasmussen
@ Konner Eu li sua pergunta que tratava da transferência de arquivos. Para esse efeito, é seguro. As chances de um pouco ser corrompido em uma transferência são pequenas e é mais provável que você perca parte do arquivo copiado na transferência, supondo que eu tenha entendido sua situação anterior . O MD5 é equivalente a comparar os dois arquivos, com alguma vantagem no fato de que você não precisa acessar os dois arquivos ao mesmo tempo.
Doktoro Reichard
15
"Um MD5 verificado significa que TODOS os bits são exatamente iguais." Note que isso é impossível, graças ao Princípio do Buraco de Buracos. en.wikipedia.org/wiki/Pigeonhole_principle
Professor
3
Também não acho que você tenha garantia de arquivos de 16 bytes.
achou do

Respostas:

65

O MD5 está quebrado para esse fim contra um adversário inteligente. É possível construir maliciosamente dois blocos diferentes de dados que produzem o mesmo hash MD5.

No entanto, é totalmente adequado (embora haja maneiras quase certamente melhores) usar o MD5 para proteger contra corrupção de dados inadvertida em trânsito ou armazenamento. Embora seja concebível que esse evento possa causar o mesmo hash MD5, a probabilidade é tão baixa que é quase inimaginável que seria uma probabilidade com a qual vale a pena se preocupar. Falhas causadas por radiação de fundo, tunelamento, estática e dezenas de outras fontes seriam ordens de magnitude mais prováveis.

Mesmo se você tivesse um quatrilhão de unidades de dados, a probabilidade de um MD5 incompatível produzir um hash MD5 pertencente a uma dessas unidades de quatrilhão é muito menor que uma em um quatrilhão.

David Schwartz
fonte
Embora possa ser teoricamente possível gerar dois arquivos com o mesmo hash, pode ser praticamente inviável. Especialmente se o arquivo de substituição também fizer sentido. Se o arquivo original era um texto em inglês, por exemplo, pode não haver outra correspondência que também seja em inglês. Ou, se for uma planilha do Excel, nenhum dos outros arquivos com o mesmo hash seria uma planilha válida.
Barmar
1
@ Barmar: win.tue.nl/hashclash/Nostradamus esses caras criaram vários arquivos pdf com o mesmo hash MD5 para provar que era praticamente viável.
philfr
26

MD5 é um hash. Basicamente, mapeia todo o conteúdo de um arquivo em uma pequena sequência com IIRC de 16 bytes.

Obviamente, haverá vários arquivos com hash na mesma soma MD5. Portanto, uma soma MD5 correspondente não é garantia de uma correspondência exata entre arquivos.

Não existe um limite como tal, porque o modo como os hashes funcionam. Portanto, uma soma MD5 pode detectar até uma única alteração de bit. No entanto, muitas alterações de bit único juntas podem fazer com que o hash MD5 seja o mesmo. Portanto, é bastante razoável usar o MD5 para validar a integridade do arquivo contra corrupção aleatória, mas não se a intenção maliciosa for possível, pois alguém poderá modificar um arquivo enquanto garante que o hash do MD5 seja o mesmo.

Itai
fonte
1
Para encurtar a história, um md5 nada mais é do que uma maneira rápida e suja de verificar a integridade do arquivo, e só deve ser usado quando um erro não detectado não causar repercussões cataclísmicas ... correto?
Konner Rasmussen
3
o melhor uso é detectar corrupção durante a transferência ou cópia. não é realmente uma coisa de segurança.
Michael Martinez
12
@ KonnerRasmussen - não é uma questão de grau de repercussão, é a natureza da ameaça. Se você está preocupado com o fato de dois documentos terem acidentalmente o mesmo MD5, pare de se preocupar: as chances são consideravelmente maiores de que seus computadores explodam espontaneamente em chamas; se você está preocupado que um invasor inteligente possa produzir um documento que corresponda ao que você já possui, isso é uma preocupação séria e você deve obter um hash melhor; se você está preocupado que um invasor inteligente possa produzir dois documentos que se encaixam, não se "preocupe": isso certamente acontecerá.
Malvolio
5
É claro que, embora seja teoricamente possível gerar uma colisão de hash MD5, gerar uma colisão útil (como em, o arquivo em colisão é o mesmo tipo de arquivo e seu conteúdo é pelo menos plausivelmente autêntico) é muito mais difícil ...
Shadur
6
@Shadur: Esse costumava ser o caso, mas a pesquisa de segurança em andamento descobriu novas maneiras de gerar colisões MD5 que facilitam isso. Em particular, se o seu formato de arquivo permitir pedaços de dados de "comentários" de formato livre, é possível corresponder a qualquer hash MD5 inserindo um comentário adequado.
MSalters
17

Um MD5-Hash consiste em 128 bits. Um único bit invertido na fonte inverte (em média) 64 bits no hash.

A probabilidade de dois hashes colidirem acidentalmente é 1/2 ^ 128, que é 1 em 340 undecilhões 282 decilhões 366 nonillion 920 octillion 938 septillion 463 sextillion 463 quintillion 374 quadrillion 607 trilhões 431 bilhões 768 milhões 211 mil 456.

No entanto, se você mantiver todos os hashes, graças ao paradoxo do aniversário, a probabilidade é um pouco maior. Para ter 50% de chance de qualquer hash colidir, você precisa de 2 ^ 64 hashes. Isso significa que, para obter uma colisão, em média, você precisará misturar 6 bilhões de arquivos por segundo por 100 anos.

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

Zsolt Szilagy
fonte
8
Então você está dizendo que ainda há uma chance? : p
Holloway
1
O problema é que, embora você precise misturar 6 bilhões de arquivos por segundo por 100 anos para ter certeza de que encontra uma colisão; isso poderia acontecer dentro do primeiro segundo.
deroby
É verdade que isso poderia acontecer no primeiro segundo. Mas como sempre, trata-se de equilibrar as razões. Pode haver aplicações militares onde esse risco não é aceitável, mas eu alugaria um carro sem pensar duas vezes onde os sensores do airbag usam o md5. Lembre-se, é provável que você seja atingido por um raio várias vezes enquanto aguarda uma colisão md5.
Zsolt Szilagy
Sinto muito, mas metade de 2 ^ 128 é 2 ^ 127, não 2 ^ 64.
fischi
2
@fischi, leia o link sobre o paradoxo do aniversário e também en.wikipedia.org/wiki/Birthday_attack - não se trata apenas de reduzir pela metade o número total de hashes. Dado o espaço de pesquisa H, o número de hashes que você precisa gerar antes de obter uma chance de 50% de uma colisão é de aproximadamente sqrt ((pi / 2) * H). Se você fizer isso a matemática com 2 ^ 128, você vai ter um número de cerca de 2 ^ 64
Paul Dixon