Por que os valores de hash MD5 não são reversíveis?

91

Um conceito sobre o qual sempre me perguntei é o uso de funções e valores hash criptográficos. Eu entendo que essas funções podem gerar um valor hash único e praticamente impossível de reverter, mas aqui está o que sempre me perguntei:

Se no meu servidor, em PHP eu produzo:

md5("stackoverflow.com") = "d0cc85b26f2ceb8714b978e07def4f6e"

Quando você executa a mesma string por meio de uma função MD5, obtém o mesmo resultado na instalação do PHP. Um processo está sendo usado para produzir algum valor, a partir de algum valor inicial.

Isso não significa que há alguma maneira de desconstruir o que está acontecendo e reverter o valor do hash?

O que há com relação a essas funções que torna impossível reconstituir as strings resultantes?

barfoon
fonte
54
Um exemplo simples de valor não reversível, por exemplo, é o módulo. Por exemplo, 10% 3 = 1, mas você não pode reverter o 1 para 10, pois também poderia ser 4
Gab Royer
57
Se você pudesse reconstruir os dados, teria o algoritmo de compressão sem perdas mais eficiente de todos os tempos :)
Dan Diplo

Respostas:

204

O material de entrada pode ter um comprimento infinito, onde a saída é sempre de 128 bits. Isso significa que um número infinito de strings de entrada gerará a mesma saída.

Se você escolher um número aleatório e dividi-lo por 2, mas apenas anotar o restante, obterá 0 ou 1 - par ou ímpar, respectivamente. É possível pegar aquele 0 ou 1 e obter o número original?

Cody Brocious
fonte
4
Ou seja, nem número -> resto nem string -> md5 são "funções injetivas".
Federico A. Ramponi
Federico, com certeza você quer dizer que nenhuma das duas são funções bijetivas? Ambos são injetivos.
Mihai Limbășan
10
moocha: Injetivo significa 1 para 1. O MD5 certamente não é 1 para 1, pois o domínio é maior que o intervalo. Outro ponto digno de nota é que, dada uma soma de verificação MD5, é muito difícil encontrar até mesmo uma string que faça hash dela. Pode valer a pena acrescentar à resposta para esclarecimento.
biozinco
4
É impossível ter uma função hash que gere valores únicos. Você está mapeando um número infinito de valores em um número finito de valores, o que garante colisões.
Cody Brocious
4
Sugiro que sua resposta não aborda o ponto-chave. Como o biozinco mencionou, o que é importante para um hash de senha segura é que você não pode encontrar nenhuma entrada que crie a saída, não que você não consiga encontrar a entrada original. Por isso, o MD5 não é necessariamente tão seguro quanto poderia ser ( en.wikipedia.org/wiki/MD5#Collision_vulnerabilities ).
Mike Pelley
53

Se as funções hash, como MD5, fossem reversíveis, seria um divisor de águas na história dos algoritmos de compressão de dados! É fácil ver que, se MD5 fosse reversível, pedaços arbitrários de dados de tamanho arbitrário poderiam ser representados por meros 128 bits sem qualquer perda de informação. Assim, você seria capaz de reconstruir a mensagem original a partir de um número de 128 bits, independentemente do tamanho da mensagem original.

Autodidata
fonte
9
pense em como seria rápido baixar distros do Linux se você pudesse obter o md5 em vez disso :)
Colin Pickard
15
@Colin Pickard: não estaríamos mais baixando distros Linux, estaríamos anotando . :)
tzot
29

Ao contrário do que as respostas mais votadas aqui enfatizam, a não injetividade (ou seja, que existem várias strings hashing para o mesmo valor) de uma função hash criptográfica causada pela diferença entre o tamanho de entrada grande (potencialmente infinito) e o tamanho de saída fixo não é o ponto importante - na verdade, preferimos funções hash onde essas colisões acontecem tão raramente quanto possível.

Considere esta função (em notação PHP, como a pergunta):

function simple_hash($input) {
     return bin2hex(substr(str_pad($input, 16), 0, 16));
}

Isso acrescenta alguns espaços, se a string for muito curta, e então pega os primeiros 16 bytes da string e a codifica como hexadecimal. Ele tem o mesmo tamanho de saída de um hash MD5 (32 caracteres hexadecimais ou 16 bytes se omitirmos a parte bin2hex).

print simple_hash("stackoverflow.com");

Isso resultará em:

737461636b6f766572666c6f772e636f6d

Essa função também tem a mesma propriedade de não injetividade destacada pela resposta de Cody para MD5: Podemos passar strings de qualquer tamanho (desde que caibam em nosso computador), e ela produzirá apenas 32 dígitos hexadecimais. Claro que não pode ser injetivo.

Mas, neste caso, é trivial encontrar uma string que mapeie para o mesmo hash (apenas aplique hex2binem seu hash e você terá). Se sua string original tinha o comprimento 16 (como nosso exemplo), você ainda obterá esta string original. Nada desse tipo deve ser possível para MD5, mesmo se você souber que o comprimento da entrada foi bastante curto (exceto por tentar todas as entradas possíveis até encontrarmos uma que corresponda, por exemplo, um ataque de força bruta).

As suposições importantes para uma função hash criptográfica são:

  • é difícil encontrar qualquer string produzindo um determinado hash (resistência de pré-imagem)
  • é difícil encontrar qualquer string diferente produzindo o mesmo hash de uma determinada string (resistência de segunda pré-imagem)
  • é difícil encontrar qualquer par de cordas com o mesmo hash (resistência à colisão)

Obviamente, minha simple_hashfunção não cumpre nenhuma dessas condições. (Na verdade, se restringirmos o espaço de entrada a "strings de 16 bytes", minha função se torna injetiva e, portanto, é até resistente à segunda pré-imagem e à colisão.)

Agora existem ataques de colisão contra MD5 (por exemplo, é possível produzir um par de strings, mesmo com um determinado prefixo, que têm o mesmo hash, com bastante trabalho, mas não impossível muito trabalho), então você não deve usar MD5 para qualquer coisa crítica. Ainda não há um ataque de pré-imagem, mas os ataques ficarão melhores.

Para responder à pergunta real:

O que há com relação a essas funções que torna impossível reconstituir as strings resultantes?

O que o MD5 (e outras funções hash construídas na construção Merkle-Damgard) fazem efetivamente é aplicar um algoritmo de criptografia com a mensagem como a chave e algum valor fixo como o "texto simples", usando o texto cifrado resultante como o hash. (Antes disso, a entrada é preenchida e dividida em blocos, cada um desses blocos é usado para criptografar a saída do bloco anterior, XORed com sua entrada para evitar cálculos reversos.)

Os algoritmos de criptografia modernos (incluindo aqueles usados ​​em funções hash) são feitos de forma a dificultar a recuperação da chave, mesmo com texto simples e texto cifrado (ou mesmo quando o adversário escolhe um deles). Eles geralmente fazem isso realizando várias operações de embaralhamento de bits de forma que cada bit de saída seja determinado por cada bit chave (várias vezes) e também por cada bit de entrada. Dessa forma, você só pode reconstituir facilmente o que acontece internamente se souber a chave completa e a entrada ou saída.

Para funções hash do tipo MD5 e um ataque de pré-imagem (com uma string com hash de bloco único, para facilitar as coisas), você só tem entrada e saída de sua função de criptografia, mas não a chave (é isso que você está procurando).

Paŭlo Ebermann
fonte
4
Sim, eu sei que esta é uma resposta bastante tardia, mas a resposta aceita não deve ser deixada assim.
Paŭlo Ebermann
Acho que suas críticas têm algum mérito, mas você falhou em responder à pergunta real "O que há nessas funções que torna impossível reconstituir as strings resultantes?" Sua resposta se concentra nas qualidades que um hash criptográfico deve ter, mas não tem nenhuma explicação de como eles são implementados pelo MD5. Você poderia declarar o algoritmo exato para calcular somas MD5 aqui para mostrar como ele não é reversível, mas as outras respostas fornecem uma explicação mais simples, sem entrar em detalhes.
Autodidata
(cont ...) 2. Essas explicações usam "matemática" para mostrar um problema fundamental devido ao qual tais operações perdem informações e se tornam irreversíveis.
Autodidata de
1
@SandeepDatta Eu adicionei alguns parágrafos sobre isso.
Paŭlo Ebermann,
1
Embora outras respostas neste tópico sejam mais tecnicamente corretas, esta é a mais útil. A função não injetiva f (x) = 1 é não reversível, mas desinteressante. A utilidade do hashing reside na resistência de pré-imagem, onde é difícil encontrar qualquer entrada que produza uma saída específica.
Justin J Stark
18

A resposta de Cody Brocious é a certa. Estritamente falando, você não pode "inverter" uma função hash porque muitas strings são mapeadas para o mesmo hash. Observe, entretanto, que encontrar uma string mapeada para um determinado hash ou encontrar duas strings mapeadas para o mesmo hash (ou seja, uma colisão ) seria uma grande descoberta para um criptanalista. A grande dificuldade de ambos os problemas é a razão pela qual boas funções hash são úteis na criptografia.

Federico A. Ramponi
fonte
12

MD5 não cria um valor hash exclusivo; o objetivo do MD5 é produzir rapidamente um valor que muda significativamente com base em uma pequena alteração na fonte.

Por exemplo,

"hello" -> "1ab53"
"Hello" -> "993LB"
"ZR#!RELSIEKF" -> "1ab53"

(Obviamente, essa não é a criptografia MD5 real)

A maioria dos hashes (se não todos) também não são exclusivos; em vez disso, eles são únicos o suficiente , então uma colisão é altamente improvável, mas ainda possível.

Trevel
fonte
8

Uma boa maneira de pensar em um algoritmo de hash é pensar em redimensionar uma imagem no Photoshop ... digamos que você tenha uma imagem com 5000x5000 pixels e depois a redimensione para apenas 32x32. O que você tem ainda é uma representação da imagem original, mas é muito menor e efetivamente "jogou fora" certas partes dos dados da imagem para fazê-la caber no tamanho menor. Portanto, se você redimensionar a imagem de 32x32 de volta para 5000x5000, tudo o que obterá será uma bagunça borrada. No entanto, como uma imagem de 32x32 não é tão grande, seria teoricamente concebível que outra imagem pudesse ser reduzida para produzir exatamente os mesmos pixels!

Isso é apenas uma analogia, mas ajuda a entender o que um hash está fazendo.

nbevans
fonte
3
Embora o redimensionamento da imagem seja um processo com perdas, ainda é muito fácil produzir uma imagem no tamanho original de 5000 × 5000 que (ao aplicar a função de redução novamente) reduzirá para a mesma imagem de 32 × 32. Encontrar essa pré-imagem deve ser difícil para uma boa função de hash.
Paŭlo Ebermann
4

Uma colisão de hash é muito mais provável do que você imagina. Dê uma olhada no paradoxo do aniversário para entender melhor por que isso acontece.

Gamic
fonte
1
Existem 365 valores de aniversário possíveis, que estão entre 2 ^ 8 e 2 ^ 9. Um hash de 128 bits tem 2 ^ 128 valores possíveis - 2 ^ 120 vezes mais. Sim, as colisões são mais prováveis ​​do que você imagina, mas ainda são astronomicamente improváveis.
Tim Keating,
Você precisará de cerca de 2 ^ 64 valores diferentes para ter uma boa chance de uma colisão de hash. Ainda alguns.
Paŭlo Ebermann
4

Como o número de arquivos de entrada possíveis é maior do que o número de saídas de 128 bits, é impossível atribuir exclusivamente um hash MD5 a cada possível.

As funções criptográficas de hash são usadas para verificar a integridade dos dados ou assinaturas digitais (o hash sendo assinado para eficiência). Alterar o documento original deve, portanto, significar que o hash original não corresponde ao documento alterado.

Esses critérios às vezes são usados:

  1. Resistência de pré-imagem: para uma determinada função hash e determinado hash, deve ser difícil encontrar uma entrada que tenha o hash fornecido para essa função.
  2. Resistência de segunda pré-imagem: para uma determinada função de hash e entrada, deve ser difícil encontrar uma segunda entrada diferente com o mesmo hash.
  3. Resistência à colisão: para um determinado hash, deve ser difícil encontrar duas entradas diferentes com o mesmo hash.

Esses critérios são escolhidos para dificultar a localização de um documento que corresponda a um determinado hash, caso contrário, seria possível falsificar documentos substituindo o original por um que corresponda por hash. (Mesmo se a substituição for algo sem sentido, a mera substituição do original pode causar interrupções.)

O número 3 implica o número 2.

Quanto ao MD5 em particular, ele tem se mostrado defeituoso: como quebrar o MD5 e outras funções hash .

Geoglifo
fonte
2

Mas é aqui que entram em jogo as tabelas rainbow. Basicamente, é apenas uma grande quantidade de valores separados por hash e, em seguida, o resultado é salvo no disco. Então, o bit de reversão é "apenas" fazer uma pesquisa em uma tabela muito grande.

Obviamente, isso só é viável para um subconjunto de todos os valores de entrada possíveis, mas se você conhece os limites do valor de entrada, pode ser possível computá-lo.

Martinlund
fonte
Ahh sim. Gostei de ler a postagem de Jeff sobre tabelas de hash ( codinghorror.com/blog/archives/000949.html ), e esse tópico ajudou na compreensão do conceito.
barfoon
1

Como a maioria já disse, o MD5 foi projetado para fluxos de dados de comprimento variável com hash em um bloco de dados de comprimento fixo, de modo que um único hash é compartilhado por muitos fluxos de dados de entrada.

No entanto, se você alguma vez precisou descobrir os dados originais da soma de verificação, por exemplo, se você tem o hash de uma senha e precisa descobrir a senha original, geralmente é mais rápido apenas pesquisar no Google (ou qualquer pesquisador de sua preferência) o hash para a resposta do que para força bruta. Eu descobri com sucesso algumas senhas usando este método.

Tim Matthews
fonte
1

A melhor maneira de entender o que significam todas as respostas mais votadas é tentar realmente reverter o algoritmo MD5. Lembro que tentei reverter o algoritmo MD5crypt há alguns anos, não para recuperar a mensagem original porque é claramente impossível, mas apenas para gerar uma mensagem que produziria o mesmo hash do hash original. Isso, pelo menos teoricamente, me forneceria uma maneira de fazer o login em um dispositivo Linux que armazenou o usuário: senha no arquivo / etc / passwd usando a mensagem gerada (senha) em vez de usar a original. Como as duas mensagens teriam o mesmo hash resultante, o sistema reconheceria minha senha (gerada a partir do hash original) como válida. Isso não funcionou de todo. Depois de várias semanas, se bem me lembro, o uso de salna mensagem inicial me matou. Tive de produzir não apenas uma mensagem inicial válida, mas uma mensagem inicial válida com sal, o que nunca fui capaz de fazer. Mas o conhecimento que obtive com esse experimento foi bom.

Vinicius
fonte
Se você pudesse gerar uma entrada que produzisse o valor de hash MD5 fornecido de qualquer maneira razoavelmente eficiente, isso seria um grande problema para a comunidade de criptografia e deveria ser publicado. Isso é completamente independente de um determinado insumo ser salgado.
Dave L.
0

por definição Função Hash (Hash criptográfico): não deve ser invertível; não deve haver colisões (o mínimo possível).

regd sua pergunta: é uma forma de hash. a entrada (independentemente do comprimento) irá gerar uma saída de tamanho fixo (ela será preenchida com base em algo (limite de 512 bits para MD5)). A informação é comprimida (perdida) e praticamente não é possível gerar a partir de transformações reversas.

informações adicionais sobre MD5: é vulnerável a colisões. leu este artigo recentemente, http://www.win.tue.nl/hashclash/Nostradamus/

O código-fonte aberto para implementações de hash criptográfico (MD5 e SHA) pode ser encontrado no código Mozilla. (biblioteca freebl).

FL4SOF
fonte
0

Hoje em dia, os hashes MD5 ou quaisquer outros hashes são pré-calculados para todas as strings possíveis e armazenados para fácil acesso. Embora em teoria o MD5 não seja reversível, usando esses bancos de dados, você pode descobrir qual texto resultou em um determinado valor de hash.

Por exemplo, tente o seguinte código hash em http://gdataonline.com/seekhash.php para descobrir qual texto eu usei para calcular o hash

aea23489ce3aa9b6406ebb28e0cda430
Babar
fonte
Ah, sim, o hash de uma palavra comum de 7 letras. Agora use-o para descobrir esta letra de música de 11 palavras com espaço em branco e pontuação: 9f2c08d4e6158bd4854b15be50c8daa8. Vejo você em vários milênios.
Tim Keating,
6fba2bbab8a8366309bf67c7df12c622? Dica: pode ser a versão OEM de uma versão específica do Mac OS X!
scherand
@Tim Keating, @scherand: Apenas apontando a fraqueza dos algoritmos de hash, porque o hash de uma string é sempre o mesmo, não precisamos necessariamente quebrar o algoritmo para descobrir a string real.
Babar,
2
Mas não foi isso que você disse. Você disse que os hashes são "pré-computados para todas as strings possíveis e armazenados para fácil acesso", o que é patentemente falso (o conjunto de "todas as strings possíveis" é infinito ... e até mesmo o conjunto de "todas as strings plausíveis" é muito, muito grande ) IMHO isso representa erroneamente como é fácil fazer um ataque de dicionário contra uma frase-senha razoável.
Tim Keating,
0

f (x) = 1 é irreversível. As funções de hash não são irreversíveis.

Isso é realmente necessário para que cumpram sua função de determinar se alguém possui uma cópia não corrompida dos dados com hash. Isso traz suscetibilidade a ataques de força bruta, que são bastante poderosos atualmente, particularmente contra MD5.

Também há confusão aqui e em outros lugares entre as pessoas que têm conhecimento matemático, mas pouco conhecimento de decifragem. Várias cifras simplesmente executam um XOR dos dados com o fluxo de chave, então você poderia dizer que um texto cifrado corresponde a todos os textos simples desse comprimento porque você poderia ter usado qualquer fluxo de chave.

No entanto, isso ignora que um texto simples razoável produzido a partir da semente passwordé muito, muito mais provável do que outro produzido pela semente, Wsg5Nm^bkI4EgxUOhpAjTmTjO0F!VkWvysS6EEMsIJiTZcvsh@WI$IH$TYqiWvK!%&Ue&nk55ak%BX%9!NnG%32ftud%YkBO$U6oa ponto de rir de qualquer pessoa que alegue que o segundo era uma possibilidade.

Da mesma forma, se você está tentando decidir entre as duas possíveis senhas passworde Wsg5Nm^bkI4EgxUO, não é tão difícil como alguns matemáticos querem que você acredite.

Olathe
fonte
De onde você obtém suas cifras mais simplesmente XOR os dados com o conhecimento de fluxo principal ? Isso é verdadeiro para cifras de fluxo, mas também existem cifras de bloco e não funcionam dessa maneira.
Paŭlo Ebermann
-5

Gosto de todos os vários argumentos. É óbvio que o valor real dos valores em hash é simplesmente fornecer marcadores de posição ilegíveis para cadeias de caracteres, como senhas. Não tem nenhum benefício de segurança aprimorado específico. Presumindo que um invasor obteve acesso a uma tabela com senhas em hash, ele pode:

  • Hash uma senha de sua própria escolha e coloque os resultados dentro da tabela de senhas se ele / ela tiver direitos de escrever / editar na tabela.
  • Gere valores hash de senhas comuns e teste a existência de valores hash semelhantes na tabela de senha.

Nesse caso, as senhas fracas não podem ser protegidas pelo simples fato de serem hash.

webi
fonte
O valor real dos "valores hash" não é fornecer marcadores de posição ilegíveis para humanos. Se 'password1' for hash para 'newval', isso ainda não oculta o valor de maneira semelhante, embora o hash seja legível e significativo? Além disso, as senhas são um exemplo RUIM, porque NUNCA deve ser hash. Supondo que o invasor tenha acesso de gravação ao referido banco de dados, isso é definitivamente uma possibilidade. No entanto, parece que você está apenas descartando o uso adequado para tais funções de hashing, um exemplo é descrito nas muitas respostas acima - integridade da mensagem. É a razão pela qual estou neste tópico hoje, na verdade.
Shane