8

Um colega de trabalho fez um Sistema em Java que encontra colisões em uma série de senhas de hash MD5. Porém ele não parou para analisar os resultados, fez apenas uma afirmação de que existem. Só que gostaria de tirar isso a prova, alguém por acaso sabe a existência de duas senhas diferentes que poderiam ter o mesmo hash MD5?

O Wikipedia fala mais sobre colisões e vulnerabilidades.

Para esclarecer o problema, algo que parece de simples compreensão, mas que parece não ter ficado muito claro, o que quero é os dois valores distintos que causaram o mesmo hash MD5, exemplo, digitando no Workbench:

set @valor1 := 'senha_distinta1????';
set @valor2 := 'senha_distinta2????';
SELECT MD5(@valor1) AS hashA, MD5(@valor2) AS hashB;

onde: hashA = hashB

Obs: Tentei colocar os seguintes valores de entrada para testar os exemplos sugeridos e ambos retornaram em valores diferentes de hash:

set @a:= "d131dd02c5e6eec4693d9a0698aff95c 2fcab58712467eab4004583eb8fb7f89
55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf280373c5b
d8823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080a80d1e c69821bcb6a8839396f9652b6ff72a70";

set @b:= "d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89
55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b
d8823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080280d1e c69821bcb6a8839396f965ab6ff72a70";

set @a:=Replace(@a," ","");
set @a:=Replace(@a,"
","");
set @b:=Replace(@b,"
","");
set @b:=Replace(@b," ","");

SELECT  MD5(@a) as hashA, MD5(@b) as hashB, @a as valorA, @b as valorB;
13
  • 2
    Possível duplicata de Como funciona o algoritmo de hash MD5? Commented 19/11/2015 às 13:17
  • 3
    Olha eu acho que a pergunta não responde diretamente isto, mas afirma e forneça os links sobre o assunto, realmente não é uma duplicata, mas te digo uma coisa, o sha1 que também apresentou o mesmo problema posteriormente, sendo agora recomendado o sha-2, que "talvez" possa a ter o mesmo problema, mas não sei em que frequencia. Votei por deixar em aberto pois apesar da outra pergunta ser praticamente a mesma que a sua a resposta lá pouco fala do problema de segurança. Vamos ver o que os demais acham.
    – Syzoth
    Commented 19/11/2015 às 14:29
  • 2
    @mgibsonbr, realmente, ao citar salt tornei-me alheio à conversa, quando a problema em causa é outro.
    – Edilson
    Commented 19/11/2015 às 15:36
  • 2
    A resposta para a pergunta é simples. SIM. Matematicamente é comprovado que qq hash possui colisões. Agora ter senhas com o mesmo hash de saída é muito dificil. Mais comum que uma cadeia longa de bits gere uma colisão para uma cadeia curta. Commented 23/11/2015 às 13:46
  • 2
    no seu exemplo usando o Workbench, tente fazer um UNHEX da sua string hexdecimal: SELECT MD5(UNHEX(@a)) as hashA, MD5(UNHEX(@b)) as hashB, UNHEX(@a) as valorA, UNHEX(@b) as valorB; Commented 23/11/2015 às 14:01

1 Resposta 1

13

Há não só exemplos mas também um site que gera colisões pra você:

os dois blocos

d131dd02c5e6eec4693d9a0698aff95c 2fcab58712467eab4004583eb8fb7f89
55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf280373c5b
d8823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080a80d1e c69821bcb6a8839396f9652b6ff72a70

e

d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89
55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b
d8823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080280d1e c69821bcb6a8839396f965ab6ff72a70

produzem uma colisão MD5.

Cada um desses blocos possui o hash MD5 79054025255fb1a26e4bc422aef54eb4.

Fonte

Exemplo no ideone

Se você se refere a duas strings curtas com o mesmo MD5, acho bastante improvável que exista. A saída do MD5 é de 128 bits. Isso significa que se você gerar 2128 + 1 strings distintas então garantidamente você terá uma colisão (princípio da casa dos pombos). Mas o conjunto de strings Unicode no BMP de tamanho até 7, juntas, dão menos que 2128 - 1, de modo que é possível que nesse conjunto não exista uma única colisão.

De todo modo, o problema de usar MD5 para proteger senhas não é sua vulnerabilidade a colisões (pois pra senhas o que importa é a resistência à segunda pré-imagem, e nisso o MD5 ainda não foi quebrado), e sim o fato dele ser muito rápido (um bom hash pra proteger senhas precisa necessariamente ser lento).


Atualização: um ponto que parece estar causando confusão é que a entrada que um hash MD5 espera é uma sequência binária, e não uma sequência de caracteres. De modo que, mesmo que sua entrada seja uma string, primeiro ela teria que ser convertida em uma sequência binária (via uma codificação ou encoding) antes de ser enviada como entrada para o algoritmo MD5. Muitas bibliotecas e funções fazem isso automaticamente pra você, por isso parece que o MD5 aceita entradas strings, quando na verdade não aceita.

Os exemplos citados são duas sequências binárias, expressas em hexadecimal. não é uma simples questão de usar o texto acima como entrada para o hash, é preciso interpretá-lo da forma correta:

0xd1 == 209 == 1101 0001

O que é diferente da string "d1":

"d1" == 0x64 0x31 == 0110 0100 0011 0001

Note como as saídas são diferentes. Feito dessa forma, os hashes também serão diferentes...

Se você quiser/precisar colocar o exemplo acima numa string, o jeito é usar um código hexadecimal para cada par de caracteres. Você não disse qual plataforma está usando, mas um exemplo em Python seria: (Edit: foi mal, eu é que não sabia o que era esse Workbench... veja o comentário do TobyMosque para um exemplo)

a = "\xd1\x31\xdd\x02\xc5...\x70\x80\xa8\x0d...\x70"
print(hashlib.md5(a).hexdigest())

b = "\xd1\x31\xdd\x02\xc5...\x70\x80\x28\x0d...\x70"
print(hashlib.md5(b).hexdigest())

Ou, mais fácil, é converter os dados acima de hexadecimal para binário e testar direto no binário (como eu fiz no exemplo do ideone mencionado anteriormente).

13
  • Eu não entendi onde está a senha que gerou esses blocos que foram colididos. E como você chegou nesse hash: 79054025255fb1a26e4bc422aef54eb4 ? E qual seria as duas senhas diferentes geradas com 2 elevado a 128 + 'string qualquer' que deu em uma colisão? Commented 19/11/2015 às 17:11
  • @IvanFerrer Os blocos são a entrada, não a saída. Repare que eles não são iguais (o primeiro link que eu passei mostra realçado as diferenças). O hash é o MD5 de um ou outro par de blocos (binário, representado acima como hexadecimal). Eles são bem grandinhos, mas como eu falei não se conhece uma colisão com entradas curtas, tipicamente o que se usa numa senha (mas não é garantido que elas não existam). Testar isso é complicado num computador comum, veja esse post no crypto.SE para mais detalhes.
    – mgibsonbr
    Commented 19/11/2015 às 17:16
  • não entendi, pois a entrada do primeiro hash convertido em md5 foi 'f52a2ca211111dc63ea4b50e5854bf0a'; Commented 19/11/2015 às 17:19
  • Isso que eu falei do 2 elevado a 128 é que se você sair gerando strings distintas (ex.: a, b, c, ..., z, aa, ab, ac, ..., zz, aaa`, ...) e o número de strings for maior que 2^128 então garantidamente você encontrará uma colisão, pois existem apenas 2^128 saídas distintas pro MD5.
    – mgibsonbr
    Commented 19/11/2015 às 17:20
  • 1
    @mgibsonbr, Workbench é uma GUI para gestão de SGBD, no caso o MySQL, outros exemplos de ferramentas para este fim, são o SQL Server Management Studio e o pgAdmin. Commented 23/11/2015 às 14:25

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .