Quantos elementos aleatórios antes MD5 produz colisões?

Question

Eu tenho uma biblioteca de imagens no Amazon S3. Para cada imagem, eu md5 o URL de origem no meu servidor mais um timestamp para obter um nome de arquivo exclusivo. Desde S3 não pode ter subdiretórios, eu preciso armazenar todas essas imagens em uma única pasta lisa.

Do I precisa se preocupar com as colisões no valor de hash MD5 que é produzido?

Bonus:? Quantos arquivos eu poderia ter antes de eu começar a ver as colisões no valor de hash MD5 que produz

Answer 1

Probabilidade de apenas dois hashes acidentalmente colidir é 1/2 ¹²⁸ que é 1 em 340 undecillion 282 decillion 366 nonillion 920 octilhões 938 septillion 463 sextillion 463 quintillion 374 quatrilhões 607 trillion 431000000000 768000000 211000 456.

No entanto, se você manter todos os hashes então a probabilidade é um pouco mais elevados graças a aniversário paradoxo . Para ter uma chance de 50% de qualquer colisão de hash com qualquer outro de hash que você precisa 2 ⁶⁴ hashes. Isto significa que para obter uma colisão, em média, você vai precisar de hash 6 bilhões arquivos por segundo 100 anos .

Answer 2

S3 pode ter subdiretórios. Basta colocar um "/" no nome da chave, e você pode acessar os arquivos como se estivessem em diretórios separados. Eu uso isso para armazenar arquivos de usuário em pastas separadas com base em sua ID de usuário no S3.

Por exemplo: "mybucket / users / 1234 / somefile.jpg". Não é exatamente o mesmo que um diretório em um sistema de arquivos, mas a API S3 tem algumas características que deixá-lo trabalhar quase o mesmo. Posso pedir-lhe para listar todos os arquivos que começam com "utilizadores / 1234 /" e ele vai me mostrar todos os arquivos em que "diretório".

Answer 3

Assim, espera, é:

md5(filename) + timestamp

ou

md5(filename + timestamp)

No primeiro caso, você é mais do caminho para um GUID, e eu não me preocuparia com isso. Neste último caso, em seguida, veja o post de Karg sobre como você vai correr em colisões eventualmente.

Answer 4

Uma regra prática para colisões é a raiz quadrada do intervalo de valores. Sua sig MD5 é, presumivelmente, 128 bits de comprimento, assim você vai ser provável ver colisões acima e além de 2 ^ 64 imagens.

Answer 5

Apesar de colisões MD5 aleatórias são extremamente raros, se os usuários podem fornecer arquivos (que serão armazenados na íntegra), então eles podem projetar a ocorrência de colisões. Ou seja, eles podem deliberadamente criar dois arquivos com o mesmo MD5sum mas dados diferentes. Verifique se o seu aplicativo pode lidar com este caso de uma forma sensata, ou talvez usar um hash mais forte como SHA-256.

Answer 6

Embora tenha sido bem divulgado problemas com MD5 devido a colisões, colisões não intencionais entre dados aleatórios são extremamente raros. Por outro lado, se você estiver hash no nome do arquivo, isso não é de dados aleatórios, e eu esperaria colisões rapidamente.

Answer 7

MD5 colisão é extremamente improvável. Se você tem 9 trilhões MD5s, há apenas uma chance em 9 trilhões que haverá uma colisão.

Answer 8

Realmente não importa quão provável é; é possível. Poderia acontecer nas duas primeiras coisas que você de hash (muito improvável, mas possível), então você precisa para suportar colisões desde o início.