Duas strings diferentes podem gerar o mesmo código hash MD5?

Para cada um de nossos ativos binários, geramos um hash MD5. Isso é usado para verificar se um determinado ativo binário já está em nosso aplicativo. Mas é possível que dois ativos binários diferentes gerem o mesmo hash MD5. Portanto, é possível que duas strings diferentes gerem o mesmo hash MD5?

Para um conjunto de até bilhões de ativos, as chances de colisões aleatórias são desprezíveis - nada com que você deva se preocupar. Considerando o paradoxo do aniversário , dado um conjunto de 2 ^ 64 (ou 18.446.744.073.709.551.616) ativos, a probabilidade de uma única colisão MD5 dentro desse conjunto é de 50%. Nessa escala, você provavelmente venceria o Google em termos de capacidade de armazenamento.

No entanto, como a função hash MD5 foi quebrada (é vulnerável a um ataque de colisão ), qualquer invasor determinado pode produzir 2 ativos em colisão em questão de segundos de potência da CPU. Portanto, se você quiser usar o MD5, certifique-se de que esse invasor não comprometa a segurança do seu aplicativo!

Além disso, considere as ramificações se um invasor puder forjar uma colisão com um ativo existente em seu banco de dados. Embora não existam tais ataques conhecidos (ataques de pré-imagem ) contra MD5 (a partir de 2011), isso pode se tornar possível estendendo a pesquisa atual sobre ataques de colisão.

Se isso for um problema, sugiro olhar para a série SHA-2 de funções hash (SHA-256, SHA-384 e SHA-512). A desvantagem é que ele é um pouco mais lento e tem uma saída de hash mais longa.

MD5 é um função hash - então, sim, duas strings diferentes podem gerar códigos MD5 em conflito.

Em particular, observe que os códigos MD5 têm um comprimento fixo, portanto, o número possível de códigos MD5 é limitado. O número de strings (de qualquer comprimento), no entanto, é definitivamente ilimitado, portanto, logicamente, deve haver colisões.

Sim, é possível. Este é na verdade um problema de aniversário . No entanto, a probabilidade de duas strings escolhidas aleatoriamente terem o mesmo hash MD5 é muito baixa.

Veja esta e estas questões para exemplos.

Sim, claro: os hashes MD5 têm um comprimento finito, mas há um número infinito de cadeias de caracteres possíveis que podem ter o hash MD5.

Sim, é possível que duas strings diferentes possam gerar o mesmo código hash MD5.

Aqui está um teste simples usando uma mensagem binária muito semelhante em string hexadecimal:

$ echo '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
c6b384c4968b28812b676b49d40c09f8af4ed4cc  -
008ee33a9d58b51cfeb425b0959121c9

$ echo '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
c728d8d93091e9c7b87b43d9e33829379231d7ca  -
008ee33a9d58b51cfeb425b0959121c9

Eles geram soma SHA-1 diferente, mas o mesmo valor de hash MD5. Em segundo lugar, as cordas são muito semelhantes, por isso é difícil encontrar a diferença entre elas.

A diferença pode ser encontrada pelo seguinte comando:

$ diff -u <(echo 4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2 | fold -w2) <(echo 4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2 | fold -w2)
--- /dev/fd/63  2016-02-05 12:55:04.000000000 +0000
+++ /dev/fd/62  2016-02-05 12:55:04.000000000 +0000
@@ -33,7 +33,7 @@
 af
 bf
 a2
-00
+02
 a8
 28
 4b
@@ -53,7 +53,7 @@
 6d
 a0
 d1
-55
+d5
 5d
 83
 60

O exemplo de colisão acima foi tirado de Marc Stevens: Colisão de bloco único para MD5 , 2012; ele explica seu método, com o código-fonte ( link alternativo para o artigo ).

Outro teste:

$ echo '0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
756f3044edf52611a51a8fa7ec8f95e273f21f82  -
cee9a457e790cf20d4bdaa6d69f01e41

$ echo '0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
6d5294e385f50c12745a4d901285ddbffd3842cb  -
cee9a457e790cf20d4bdaa6d69f01e41

Soma diferente de SHA-1, o mesmo hash MD5.

A diferença está em um byte:

$ diff -u <(echo 0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef | fold -w2) <(echo 0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef | fold -w2)
--- /dev/fd/63  2016-02-05 12:56:43.000000000 +0000
+++ /dev/fd/62  2016-02-05 12:56:43.000000000 +0000
@@ -19,7 +19,7 @@
 03
 65
 9e
-70
+74
 4f
 85
 34
@@ -41,7 +41,7 @@
 a3
 f4
 15
-5c
+dc
 bb
 86
 07

O exemplo acima foi adaptado de Tao Xie e Dengguo Feng: Construct MD5 Collisions Using Just A Single Block Of Message , 2010.

Relacionado:

• Existem duas strings conhecidas com o mesmo valor de hash MD5? em Crypto.SE

Sim, é possível. É chamado de colisão de Hash .

Dito isso, algoritmos como o MD5 são projetados para minimizar a probabilidade de uma colisão.

A entrada da Wikipedia no MD5 explica algumas vulnerabilidades no MD5, das quais você deve estar ciente.

Só para ser mais informativo. Do ponto de vista matemático, as funções Hash não são injetivas .
Isso significa que não há uma relação de 1 para 1 (mas de uma maneira) entre o conjunto inicial e o resultante.

Bijeção na wikipedia

EDITAR: para ser completo, existem funções de hash injetivo: é chamado de hash perfeito .

Sim, ele é! A colisão será uma possibilidade (embora o risco seja muito pequeno). Do contrário, você teria um método de compressão bastante eficaz!

EDIT : Como Konrad Rudolph diz: Um conjunto potencialmente ilimitada de entrada convertido para um conjunto finito de saída (32 caracteres hexadecimais) vontade resulta num sem número de colisões.

Como outras pessoas disseram, sim, pode haver colisões entre duas entradas diferentes. No entanto, em seu caso de uso, não vejo isso sendo um problema. Eu duvido muito que você vá se deparar com colisões - Eu usei MD5 para tirar impressões digitais de centenas de milhares de arquivos de imagem de vários formatos (JPG, bitmap, PNG, raw) em um trabalho anterior e não tive uma colisão .

No entanto, se você estiver tentando obter uma impressão digital de algum tipo de dado, talvez possa usar dois algoritmos de hash - a probabilidade de uma entrada resultar na mesma saída de dois algoritmos diferentes é quase impossível.

Sei que isso é antigo, mas pensei em contribuir com minha solução. Existem 2 ^ 128 combinações de hash possíveis. E, portanto, uma probabilidade de 2 ^ 64 de um paradoxo de aniversário. Embora a solução abaixo não elimine a possibilidade de colisões, ela certamente reduzirá o risco em uma quantidade muito significativa.

2^64 = 18,446,744,073,709,500,000 possible combinations

O que fiz foi juntar alguns hashes com base na string de entrada para obter uma string resultante muito mais longa que você considera seu hash ...

Portanto, meu pseudocódigo para isso é:

Result = Hash(string) & Hash(Reverse(string)) & Hash(Length(string))

Isso é a improbabilidade prática de uma colisão. Mas se você quer ser superparanóico e não pode deixar que isso aconteça, e espaço de armazenamento não é um problema (nem os ciclos de computação) ...

Result = Hash(string) & Hash(Reverse(string)) & Hash(Length(string)) 
         & Hash(Reverse(SpellOutLengthWithWords(Length(string)))) 
         & Hash(Rotate13(string)) Hash(Hash(string)) & Hash(Reverse(Hash(string)))

Ok, não é a solução mais limpa, mas agora você pode brincar muito mais com a infrequência de colidir. Até o ponto, posso assumir a impossibilidade em todos os sentidos realistas do termo.

Para o meu bem, acho que a possibilidade de uma colisão é rara o suficiente para que eu não considere isso "infalível", mas é tão improvável de acontecer que se adapta à necessidade.

Agora, as combinações possíveis aumentam significativamente. Embora você possa gastar muito tempo pensando em quantas combinações isso pode lhe render, eu direi que, em teoria, você ganha SIGNIFICAMENTE mais do que o número citado acima de

2^64 (or 18,446,744,073,709,551,616) 

Provavelmente por mais cem dígitos ou mais. O máximo teórico que isso poderia dar a você seria

Número possível de strings resultantes:

528294531135665246352339784916516606518847326036121522127960709026673902556724859474417255887657187894674394993257128678882347559502685537250538978462939576908386683999005084168731517676426441053024232908211188404148028292751561738838396898767036476489538580897737998336

Acho que precisamos ter cuidado ao escolher o algoritmo de hash de acordo com nossos requisitos, já que as colisões de hash não são tão raras quanto eu esperava. Recentemente, encontrei um caso muito simples de colisão de hash em meu projeto. Estou usando o wrapper Python de xxhash para hash. Link: https://github.com/ewencp/pyhashxx

s1 = 'mdsAnalysisResult105588'
s2 = 'mdsAlertCompleteResult360224'
pyhashxx.hashxx(s1) # Out: 2535747266
pyhashxx.hashxx(s2) # Out: 2535747266

Isso causou um problema de cache muito complicado no sistema, então finalmente descobri que é uma colisão de hash.