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

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?

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?

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.

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).

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.

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.

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.

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.

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 .

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.

Cientistas chineses descobriram uma maneira chamada "colisões de prefixo escolhido" para criar um conflito entre duas strings diferentes.

Aqui está um exemplo: http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5.exe.zip
O código-fonte: http://www.win.tue.nl/hashclash/fastcoll_v1.0.0. 5_source.zip

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.

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.

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).

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

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.

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.