Como 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 criptocharts de hash. Eu entendo que essas funções podem gerar um valor de hash que é único e praticamente impossível de reverter, mas aqui está o que eu sempre imaginei:

Se no meu servidor, em PHP eu produzo:

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

Quando você executa essa mesma string através de uma function MD5, você obtém o mesmo resultado em sua 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 de hash?

O que há nessas funções que impossibilitam o rastreamento das sequências resultantes?

O material de input pode ser um comprimento infinito, em que a saída tem sempre 128 bits de comprimento. Isso significa que um número infinito de strings de input irá gerar a mesma saída.

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

Se as funções hash, como o MD5, fossem reversíveis, então seria um evento divisor de águas na história dos algoritmos de compression de dados! É fácil ver que, se o MD5 fosse reversível, então, 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ê poderia reconstruir a mensagem original 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 sequências de hashing com o mesmo valor) de uma function hash criptográfica causada pela diferença entre tamanho de input grande (potencialmente infinito) e tamanho de saída fixo não é o ponto importante – na verdade, nós preferimos funções hash onde essas colisões acontecem o mais raramente possível.

Considere esta function (em notação PHP, como a questão):

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

Isso acrescenta alguns espaços, se a seqüência de caracteres for muito curta e, em seguida, pega os primeiros 16 bytes da seqüência de caracteres e, em seguida, 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"); 

Isto irá produzir:

 737461636b6f766572666c6f772e636f6d 

Esta function também tem a mesma propriedade de não-injetividade como destacada pela resposta de Cody para o MD5: Podemos passar strings de qualquer tamanho (desde que elas caibam em nosso computador), e ele 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 hex2bin em seu hash e você o terá). Se a sua string original tiver o tamanho 16 (como nosso exemplo), você até terá essa string original. Nada deste tipo deve ser possível para o MD5, mesmo se você souber que o comprimento da input foi bem curto (a não ser tentando todas as inputs possíveis até encontrarmos uma que corresponda, por exemplo, um ataque de força bruta).

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

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

Obviamente minha function simple_hash não preenche nenhuma dessas condições. (Na verdade, se restringirmos o espaço de input para “strings de 16 bytes”, então minha function torna-se injetiva e, portanto, é até mesmo comprovável como segunda pré-imagem e resistente à colisão.)

Agora existem ataques de colisão contra o MD5 (por exemplo, é possível produzir um par de strings, mesmo com um mesmo prefixo, que tem 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 vão melhorar.

Para responder a pergunta real:

O que há nessas funções que impossibilitam o rastreamento das sequências resultantes?

O que MD5 (e outras funções de hash constroem na construção de Merkle-Damgard) 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 input é preenchida e dividida em blocos, cada um desses blocos é usado para criptografar a saída do bloco anterior, XORed com sua input para evitar cálculos reversos.)

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

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

A resposta de Cody Brocious é a correta. Estritamente falando, você não pode “inverter” uma function hash porque muitas strings são mapeadas para o mesmo hash. Observe, no entanto, que encontrar uma string que é mapeada para um dado hash, ou encontrar duas strings que são mapeadas para o mesmo hash (isto é, uma colisão ), seria um grande avanço para um criptoanalista. A grande dificuldade de ambos os problemas é a razão pela qual boas funções hash são úteis na criptografia.

O MD5 não cria um valor de hash exclusivo; O objective do MD5 é produzir rapidamente um valor que mude significativamente com base em uma pequena alteração na origem.

Por exemplo,

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

(Obviamente, isso não é 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 resize uma imagem no Photoshop … digamos que você tenha uma imagem de 5000×5000 pixels e redimensioná-la para apenas 32×32. 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 ajustá-la ao tamanho menor. Então, se você resize a imagem 32×32 para 5000×5000, tudo o que você terá é uma bagunça borrada. No entanto, como uma imagem 32×32 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 input possíveis é maior que o número de saídas de 128 bits, é impossível atribuir exclusivamente um hash MD5 a cada um deles.

As funções hash criptográficas 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.

Estes critérios são por vezes utilizados:

  1. Resistência de pré-imagem: para uma dada function hash e dado hash, deve ser difícil encontrar uma input que tenha o hash dado para aquela function.
  2. Segunda resistência de pré-imagem: para uma dada function hash e input, deve ser difícil encontrar uma segunda input diferente com o mesmo hash.
  3. Resistência à colisão: para uma dada function, deve ser difícil encontrar duas inputs 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 correspondesse ao hash. (Mesmo se a substituição for sem sentido, a mera substituição do original pode causar ruptura.)

Número 3 implica o número 2.

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

Mas é aqui que entram as mesas de arco-íris. Basicamente, é apenas uma grande quantidade de valores divididos separadamente e, em seguida, o resultado é salvo em disco. Em seguida, o bit de reversão é “apenas” para fazer uma pesquisa em uma tabela muito grande.

Obviamente, isso só é viável para um subconjunto de todos os possíveis valores de input, mas se você souber os limites do valor de input, poderá ser possível calculá-lo.

Cientistas chineses encontraram um caminho chamado “colisões de prefixo escolhido” para criar um conflito entre duas sequências 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 streams de dados de comprimento variável a serem divididos em hash para um bloco de dados de comprimento fixo, de modo que um único hash é compartilhado por muitos streams de dados de input.

No entanto, se você já precisou descobrir os dados originais da sum de verificação, por exemplo, se você tiver o hash de uma senha e precisar descobrir a senha original, é mais rápido usar apenas o google (ou qualquer pesquisador de sua preferência) para a resposta do que para força bruta. Eu descobri com sucesso algumas senhas usando este método.

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

regd sua pergunta: é uma forma de hash. input (independentemente do comprimento) gerará uma saída de tamanho fixo (será preenchida com base no algoritmo (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 o MD5: é vulnerável a colisões. passou por este artigo recentemente, http://www.win.tue.nl/hashclash/Nostradamus/

abre código-fonte para implementações de hash de criptografia (MD5 e SHA) pode ser encontrado no código do Mozilla. (biblioteca freebl).

Agora, um dia os hashes MD5 ou quaisquer outros hashes são pré-calculados para todas as sequências possíveis e armazenados para facilitar o access. Embora, em teoria, o MD5 não seja reversível, mas 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. Funções hash não são irreversíveis.

Isso é realmente necessário para que eles cumpram sua function 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 nos dias de hoje, particularmente contra o MD5.

Há também confusão aqui e em outros lugares entre pessoas que têm conhecimento matemático, mas pouco conhecimento de cifragem. Várias cifras simplesmente XOR os dados com o stream de chaves, e assim você poderia dizer que um texto cifrado corresponde a todos os textos simples desse comprimento, porque você poderia ter usado qualquer stream de chaves.

No entanto, isso ignora que um texto simples produzido a partir da password semente é muito, muito mais provável do que outro produzido pela semente Wsg5Nm^bkI4EgxUOhpAjTmTjO0F!VkWvysS6EEMsIJiTZcvsh@WI$IH$TYqiWvK!%&Ue&nk55ak%BX%9!NnG%32ftud%YkBO$U6o na medida em que qualquer um alegando que o segundo era uma possibilidade seria ridicularizado.

Da mesma forma, se você está tentando decidir entre as duas senhas de password potenciais e Wsg5Nm^bkI4EgxUO , não é tão difícil fazer como alguns matemáticos Wsg5Nm^bkI4EgxUO que você acredite.

A melhor maneira de entender o que todas as respostas mais votadas significam é realmente tentar 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 produzisse o mesmo hash que o hash original. Isso, pelo menos teoricamente, me forneceria uma maneira de acessar um dispositivo Linux que armazenava o usuário: password 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 sal na mensagem inicial me matou. Eu tive que produzir não apenas uma mensagem inicial válida, mas uma mensagem inicial válida e salgada, que eu nunca consegui fazer. Mas o conhecimento que recebi dessa experiência foi bom.

Eu gosto de todos os vários argumentos. É óbvio que o valor real dos valores com hash é simplesmente fornecer marcadores de posição ilegíveis para as cadeias de caracteres, como senhas. Não possui nenhum benefício de segurança aprimorado específico. Supondo que um invasor tenha access a uma tabela com senhas criptografadas, ele poderá:

  • Hash uma senha de sua escolha e coloque os resultados dentro da tabela de senha, se ele / ela tem direitos de escrita / edição para a tabela.
  • Gere valores com hash de senhas comuns e teste a existência de valores com hash semelhantes na tabela de senha.

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