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

https://stackoverflow.com/questions/330207

11-07-2019
|

Pergunta

Um conceito que eu sempre quis saber sobre o uso de funções hash criptográficas e valores. Eu entendo que essas funções podem gerar um valor de hash que é única e praticamente impossível reverter, mas aqui está o que eu sempre quis saber:

Se no meu servidor, em PHP Eu produtos:

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

Quando você executa essa mesma cadeia através de uma função MD5, você obter o mesmo resultado em sua instalação PHP. Um processo está a ser utilizado para a produção de algum valor, a partir de algum valor de partida.

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

O que é sobre estas funções que faz com que as cordas resultantes impossíveis para refazer?

Solução

O material de entrada pode ser um comprimento infinito, onde a saída é sempre 128 bits de comprimento. Isto significa que um número infinito de cadeias de entrada irá gerar a mesma saída.

Se você escolher um número aleatório e dividir por 2 mas apenas anote o restante, você vai ter um 0 ou 1 - par ou ímpar, respectivamente. É possível assumir que 0 ou 1 e obter o número original?

Outras dicas

Se as funções de hash, como MD5 foram reversíveis em seguida, ele teria sido um divisor de águas na história de algoritmos de compressão de dados! É fácil ver que, se MD5 foram pedaços, em seguida, arbitrárias reversíveis de dados de tamanho arbitrário poderia ser representado por um meros 128 bits sem qualquer perda de informação. Assim, você teria sido 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 upvoted aqui enfatizar, o não injectividade (ou seja, que há várias cadeias de hash para o mesmo valor) de uma função hash criptográfico causada pela diferença entre grande (potencialmente infinito) tamanho de entrada e saída fixa não é o ponto importante -., na verdade, nós preferimos funções hash onde essas colisões ocorrem mais raramente possível

Considere esta função (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 cadeia é muito curto, e em seguida, leva os primeiros 16 bytes da corda, em seguida, codifica como hexadecimal. Tem o mesmo tamanho de saída como um hash MD5 (32 caracteres hexadecimais ou 16 bytes se omitir a parte bin2hex).

print simple_hash("stackoverflow.com");

A saída será:

737461636b6f766572666c6f772e636f6d

Esta função também tem a mesma propriedade não-injectividade como destacado pela resposta de Cody para MD5: Podemos passar em cordas de qualquer tamanho (contanto que eles se encaixam em nosso computador), e vai de saída apenas 32 hex-dígitos. Claro que não pode ser injective.

Mas, neste caso, é trivial para encontrar uma string que mapeia para o mesmo hash (apenas aplicar hex2bin em seu hash e tiver). Se a sua seqüência original teve a duração de 16 (como o nosso exemplo), você ainda vai ter essa string original. Nada desse tipo deve ser possível para MD5, mesmo se você sabe o comprimento da entrada foi bastante curta (que não seja por tentar todas as entradas possíveis até encontrar um que corresponda, por exemplo, um de força bruta ataque).

As premissas importantes para uma função hash de criptografia são:

É difícil encontrar qualquer cadeia de produção de um dado de hash (resistência preimage)
É difícil encontrar qualquer cadeia diferente produzindo o mesmo hash como um dado string (segunda resistência preimage)
é difícil encontrar qualquer par de cordas com o mesmo hash (resistência colisão)

Obviamente minha função simple_hash cumpre nenhuma destas condições. (Na verdade, se restringir o espaço de entrada para "cordas" de 16 bytes, em seguida, a minha função torna-se injetivo, e, assim, é mesmo demonstrável segunda preimage resistente e resistente à colisão.)

Há já existem ataques de colisão contra MD5 (por exemplo, é possível produzir um par de cordas, mesmo com um dado mesmo prefixo, que têm o mesmo hash, com bastante trabalho, mas não impossível muito trabalho), então você não deve 't usar MD5 para qualquer coisa crítica. Ainda não existe um ataque preimage, mas os ataques vão melhorar.

Para responder a questão real:

O que é sobre estas funções que torna o resultando cordas impossíveis para refazer?

O MD5 (e outras funções hash construir sobre a construção Merkle-Damgard) efetivamente não está aplicando 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 é acolchoado e dividida em blocos, cada um destes blocos é utilizada para encriptar a saída do bloco anterior, XORed com a sua entrada para impedir os cálculos reversa.)

algoritmos de criptografia modernos (incluindo os usados ??em funções hash) são feitas de forma a torná-lo difícil de recuperar a chave, mesmo tendo em conta tanto texto simples e encriptado (ou mesmo quando o adversário escolhe um deles). Eles fazem isso geralmente fazendo muitas operações de baralhar bit de uma forma que cada bit de saída é determinada por cada bit de chave (várias vezes) e também cada bit de entrada. Dessa forma, você só pode facilmente refazer o que acontece dentro se você sabe a chave completa e entrada ou saída.

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

A resposta de Cody Brocious é o caminho certo. Estritamente falando, você não pode "invertido" uma função hash porque muitas cordas são mapeados para o mesmo hash. Note, no entanto, que seja descoberta um string que será mapeado para um determinado hash ou encontrar dois cordas que são mapeados para o mesmo hash (ou seja, um colisão ), seria grandes avanços para um criptoanalista. A grande dificuldade desses dois problemas é a razão pela qual boas funções são úteis em criptografia.

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

por exemplo.,

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

(Obviamente isso não é real criptografia MD5)

A maioria dos hashes (se não todos) são também não-exclusivo; 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 de um algoritmo de hash é pensar de redimensionar uma imagem no Photoshop ... dizer que você tem uma imagem que é 5000x5000 pixels e, em seguida, redimensioná-la para apenas 32x32. O que você tem ainda uma representação da imagem original, mas é muito, muito menor e tem efetivamente "jogado fora" certas partes dos dados de imagem para torná-lo caber no tamanho menor. Então, se você fosse para redimensionar que suportam a imagem 32x32 até 5000x5000 tudo o que você deseja obter é uma bagunça borrada. No entanto, porque uma imagem de 32x32 não é tão grande que seria teoricamente possível que uma outra imagem poderia ser reduzido para produzir exatamente o mesmo pixels!

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

Um hash colisão é muito mais provável do que você imagina. Dê uma olhada na aniversário paradoxo para obter uma maior compreensão de por que isso acontece.

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

funções hash criptográficas são usados ??para verificar a integridade dos dados ou assinaturas digitais (hash que está sendo assinado para a eficiência). Alterar o documento original deve, portanto, significa o hash original não coincidir com o documento alterado.

Estes critérios são por vezes utilizados:

resistência preimage:. Para uma determinada função hash e dado de hash, deve ser difícil encontrar uma entrada que tem o hash dada para essa função
Segundo resistência preimage:. Para uma determinada função hash e de entrada, deve ser difícil encontrar um segundo, diferente, entrada com o mesmo hash
resistência de colisão: para uma dada tem a função, deve ser difícil encontrar duas entradas diferentes com o mesmo hash.

Estes criterial são escolhidos para torná-lo difícil encontrar um documento que corresponde a um determinado haxixe, caso contrário, seria possível forjar documentos, substituindo o original com um que acompanhado por hash. (Mesmo que a substituição é conversa fiada, a mera substituição do original pode causar o rompimento.)

Número 3 implica o número 2.

Quanto MD5 em particular, tem sido mostrado para ser falho: Como quebrar MD5 e outras funções hash .

Mas isso é onde as tabelas do arco-íris entram em jogo. Basicamente é apenas uma grande quantidade de valores de hash separetely e, em seguida, o resultado é salvo em disco. Em seguida, o bit de inversã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 entrada, mas se você conhece os limites do valor de entrada que poderia ser possível calcular-lo.

cientista chinês ter encontrado uma maneira chamados de "colisões de prefixo escolhido" para fazer um conflito entre duas cadeias 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 MD5 foi projetado para dados de comprimento variável córregos para ser hash para um pedaço de comprimento fixo de dados, portanto, um único hash é compartilhada por muitos fluxos de dados de entrada.

No entanto, se você nunca tinha necessidade de encontrar os dados originais do checksum, por exemplo, se você tem o hash de uma senha e necessidade de descobrir a senha original, muitas vezes é mais rápido para apenas google (ou qualquer pesquisador sua preferência ) o hash para a resposta do que a força bruta-lo. Eu descobri com sucesso algumas senhas usando este método.

A melhor maneira de entender o que todos o mais votado respostas quis dizer é que realmente tentar reverter o algoritmo MD5. Lembro-me que tentou reverter o md5crypt algoritmo há alguns anos, não recuperar a mensagem original, porque é claramente impossível, mas apenas para gerar uma mensagem de que iria produzir o mesmo hash como o hash originais. Esta, pelo menos teoricamente, poderia me fornecer uma maneira para acessar um dispositivo Linux que armazenou o usuário: senha no arquivo / etc / passwd usando a mensagem gerada (password) em vez de usar o original. Desde as duas mensagens que têm o mesmo hash resultante, o sistema iria reconhecer minha senha (gerada a partir do hash original) como válido. Isso não funciona em todos. Depois de várias semanas, se bem me lembro, o uso de sal na mensagem inicial me matou. Eu tinha que produzir não apenas uma mensagem inicial válida, mas uma mensagem inicial válida salgada, que eu nunca fui capaz de fazer. Mas o conhecimento que eu tenho a partir desta experiência foi bom.

função

por Hash definição (Hash criptográfico.): não deve ser invertida; não deve ter colisões (menos possível)

Regd sua pergunta: é uma maneira hash. entrada (independentemente de comprimento) vai gerar uma saída de tamanho fixo. (ele será preenchido com base em algo (512 limite de bits para MD5)). A informação é comprimido (perdido) e praticamente não é possível gerar a partir de transformações inversas.

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

abre o código-fonte para implementações de hash de criptografia (MD5 e SHA) podem ser encontrados no código Mozilla. (Biblioteca freebl).

Agora, um dia hashes MD5 ou quaisquer outros hashes para que o assunto são pré calculado para todas as seqüências possíveis e armazenados para fácil acesso. Embora, em teoria, MD5 não é reversível, mas usando esses bancos de dados você pode descobrir qual o texto resultou em um valor de hash particular.

Por exemplo tente o seguinte código hash em http://gdataonline.com/seekhash.php para descobrir o que o texto i usado para calcular o hash

aea23489ce3aa9b6406ebb28e0cda430

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

Esta é realmente required para que eles cumpram a sua missão de determinar se alguém possui uma cópia não corrompida dos dados hash. Isso traz suscetibilidade a ataques de força bruta, que são bastante poderosos estes dias, particularmente contra MD5.

Há também confusão aqui e em outros lugares entre pessoas que têm conhecimento matemático, mas pouco conhecimento cipherbreaking. Vários cifras simplesmente XOR os dados com o keystream, e assim pode-se dizer que um texto cifrado corresponde a todas plaintexts de que o comprimento porque você poderia ter usado qualquer keystream.

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

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

Eu gosto de todos os vários argumentos. É óbvio que o valor real de valores hash é simplesmente fornecer espaços reservados humano-ilegível para cordas, como senhas. Ele não tem nenhum benefício de segurança específico reforçada. Assumindo um acesso ganhou atacante para uma tabela com senhas hash, ele / ela pode:

Hash uma senha de seu / sua própria escolha e colocar os resultados dentro de tabela de senha, se ele / ela tem de escrever / editar direitos para a mesa.
Gerar valores de hash de senhas comuns e testar a existência de valores hash semelhantes na tabela de senha.

Neste caso senhas fracas não podem ser protegidos pelo simples fato de que eles estão em hash.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow