Quantos elementos aleatórios antes do MD5 produzem colisões?

164

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

Preciso me preocupar com colisões no valor do hash MD5 produzido?

Bônus: quantos arquivos eu poderia ter antes de começar a ver colisões no valor de hash que o MD5 produz?

random md5 hash Ben Throop
fonte
1
Relacionado: Existem duas seqüências conhecidas que possuem o mesmo valor de hash MD5?
kenorb
2
A resposta literal é que o segundo arquivo pode ter o mesmo MD5 que o primeiro. No entanto, as chances são extremamente pequenas.
21718 Rick Rick

Respostas:

307

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

No entanto, se você mantiver todos os hashes, a probabilidade será um pouco maior, graças ao paradoxo do aniversário . Para ter uma chance de 50% de qualquer hash colidir com qualquer outro hash, 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 .

Kornel
fonte
20
"probabilidade de colisão é 1/2 ^ 64" - o que? A probabilidade de colisão depende do número de itens já com hash, não é um número fixo. De fato, é igual a exatamente 1 - sPn/s^n, onde sestá o tamanho do espaço de pesquisa ( 2^128neste caso) e no número de itens com hash. O que você provavelmente está pensando é 2^64: qual é o número aproximado de itens necessários para o hash MD5 para ter 50% de chance de colisão.
BlueRaja - Danny Pflughoeft
19
+1 porque eu sempre quis saber como contar passado um lol 999 trilhões (e oh sim, sua resposta foi informativo)
Kmeixner
7
Infelizmente, você ainda não está correto. Você está assumindo que a função hash é verdadeiramente aleatória. Não é. Isso significa que a probabilidade de colisão é maior.
Jørgen Fogh
22
JørgenFogh: E todas as leis da física também "não estão corretas". Esse nível de pedantismo é desnecessário porque não altera a resposta de maneira significativa.
Kornel
20
Então você está dizendo que há uma chance!
vargonian
27

S3 pode ter subdiretórios. Basta colocar um "/" no nome da chave e você poderá 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 identificação 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 do S3 possui alguns recursos que permitem que ele funcione quase da mesma forma. Eu posso pedir para listar todos os arquivos que começam com "users / 1234 /" e ele me mostrará todos os arquivos desse "diretório".

davr
fonte
7
Este deve ser um conteúdo que eu acho que, como ele realmente não responder à pergunta sobre a probabilidade de uma colisão
Ian Clark
18

Então espere, é isso:

md5(filename) + timestamp

ou:

md5(filename + timestamp)

Se for o primeiro, você está na maior parte do caminho para um GUID, e eu não me preocuparia com isso. Se este for o caso, consulte o post de Karg sobre como você acabará colidindo.

Ryan
fonte
1
Por favor elaborar sobre como incluindo o timestamp aumenta a chance de colisão
Brad Thomas
14
@ BradThomas: Não. O risco de colisão do MD5 é o mesmo, seja no nome do arquivo ou na combinação de nome do arquivo + carimbo de data e hora. Mas, no primeiro cenário, você precisaria ter uma colisão MD5 e uma colisão de carimbo de data e hora.
68570 Vincent Vincent
2
Isso ainda deixa 2 ^ (128 ^ 60) de chance de colisão com dois usuários por minuto. Literalmente inutilizável.
Berry M.
2
@BradThomas Para ser mais claro: md5(filename) + timestampreduz massivamente o risco de colisão, porque você precisaria ter uma colisão md5 para exatamente o mesmo timestamp para ter uma colisão geral. md5(filename + timestamp)é o mesmo que md5(filename), assumindo que o nome do arquivo seja aleatório para começar (porque adicionar mais aleatoriedade a algo aleatório altera apenas o resultado individual do md5 e o problema de aniversário ainda existe em todos os hashes do md5).
robocat
10

Uma regra prática para colisões é a raiz quadrada do intervalo de valores. Seu MD5 provavelmente tem 128 bits, então é provável que você veja colisões acima e além de 2 ^ 64 imagens.

Will Dean
fonte
1
Você provavelmente quer dizer 128 bits, não 2 ^ 128. :-)
JesperE 14/10/08
5
en.wikipedia.org/wiki/Birthday_Problem Mais algumas informações sobre o problema.
Georg Schölly 14/10/08
7

Embora colisões MD5 aleatórias sejam extremamente raras, se seus usuários puderem fornecer arquivos (que serão armazenados literalmente), eles poderão criar colisões para que ocorram. Ou seja, eles podem criar deliberadamente dois arquivos com o mesmo MD5sum, mas com dados diferentes. Verifique se o seu aplicativo pode lidar com esse caso de maneira sensata ou talvez use um hash mais forte como o SHA-256.

bdonlan
fonte
usar um sal resolveria o problema de engenharia do usuário, não?
StackOverflowed
Depende de como o sal é aplicado. Teria de ser um prefixo dos dados fornecidos pelo usuário ou, melhor ainda, a chave para um HMAC. Ainda é provavelmente uma boa idéia praticar a defesa em profundidade.
bdonlan
Observe que, embora o SHA256 tenha 256 bits, você pode reduzir o risco de colisões com o comprimento da chave que está armazenando, truncando o SHA256 para menos bits, por exemplo, use o SHA256, mas truncá-lo para 128 bits (o que é mais seguro do que usar o MD5 mesmo). embora eles tenham o mesmo número de bits).
robocat
5

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

acrrosman
fonte
O único problema que tenho com taylors exemplo é que, se alguém recebe uma cópia do seu banco de dados que provavelmente poderia descobrir os números de cartão de crédito usando uma tabela de arco-íris ...
Sam Saffron
1
Embora eu não tenha optado por usar o MD5 para cartões de crédito, uma tabela Rainbow de todos os números de cartão de crédito válidos entre 10.000.000 (8 dígitos é o menor cartão de crédito que já vi) e 9.999.999.999.999.999 (maior número de 16 dígitos) ainda é um grande tabela para gerar. Provavelmente, existem maneiras mais fáceis de roubar esses números.
Acrosman
1

Realmente não importa a probabilidade; é possível. Isso pode acontecer nas duas primeiras coisas que você faz o hash (muito improvável, mas possível); portanto, você precisará apoiar colisões desde o início.

Karg
fonte
36
É claro que pode haver muitas outras coisas ruins que podem acontecer com uma probabilidade de 1/2 ^ 128. Você pode não querer destacar este aqui para se preocupar.
Will Dean
2
A pior coisa que pode acontecer aqui é que você pode tirar uma foto. Para um número relativamente pequeno, não me preocuparia. Agora, se o seu software está controlando um piloto automático pousando uma aeronave, isso é outra história.
Jim C
9
Você não pode estar falando sério. Você precisará misturar 6 bilhões de arquivos por segundo, a cada segundo por 100 anos, para ter boas chances de colisão. Mesmo que você seja muito azarado, provavelmente levaria mais do que toda a capacidade do S3 usada por mais tempo que a vida humana.
Kornel
12
É bilhões de vezes mais provável que seu banco de dados e seus backups falhem. Não vale a pena se preocupar com colisões.
Artelius
5
Use o tempo de prevenção de colisões construindo um bunker para colocar seu servidor! Esses meteoros incômodos podem atingi-lo (muito improvável, mas possível), então você precisará apoiar o abrigo de meteoros desde o início.
Polvoazul
1

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

Rick James
fonte
1
Muitas das outras respostas falam sobre a probabilidade de uma colisão ao adicionar mais um item. Acho que minha resposta é mais útil porque fala sobre provavelmente a tabela inteira tendo um dup.
Rick James
1
Isso não tem nada a ver com o MD5 e não está correto. É como dizer que, se você tem 9 trilhões de gatos, existe uma chance de 1 em 9 trilhões de alguém ter um gato idêntico. O principal problema aqui é que você pode obter o mesmo hash com mais de um valor.
Joonas Alhonen
@JoonasAlhonen - Sim, isso é verdade. E muitas pessoas pobres usam isso como desculpa para comprar mais um bilhete de loteria que não podem pagar.
Rick James
Obrigado, esta é realmente uma estatística muito útil. As chances de ter tido uma colisão após a inserção de 9 trilhões de itens. Obrigado.
Tom P.