O que torna um algoritmo de hash "seguro"?

Depois de ler essa pergunta interessante, senti que tinha uma boa idéia de qual algoritmo de hash inseguro usaria se precisasse de um, mas não faço ideia do porquê de usar um algoritmo seguro.

Então, qual é a distinção? A saída não é apenas um número aleatório representando a coisa com hash? O que torna alguns algoritmos de hash seguros?

Há três propriedades que se deseja de cada função hash criptográfica H:

• resistência à pré-imagem : Dado h, deve ser difícil encontrar algum valor xcom h = H(x).

• segundo resistência preimage : Dado x1, deve ser difícil de encontrar x2 != x1com H(x1) = H(x2).

• resistência à colisão : deve ser difícil encontrar dois valores x1 != x2com H(x1) = H(x2).

Com funções hash usadas em linguagens de programação comuns para tabelas hash (de strings), geralmente nenhuma delas é fornecida, elas fornecem apenas:

• resistência à colisão fraca : para valores selecionados aleatoriamente (ou "normalmente") do domínio, a chance de colisão é pequena. Isso não diz nada sobre um invasor intencionalmente tentando criar colisões ou tentar encontrar pré-imagens.

As três propriedades acima são (entre) as metas de design para todas as funções de hash criptográfico. Para algumas funções (como MD4, SHA-0, MD5), sabe-se que isso falhou (pelo menos parcialmente). A geração atual (SHA-2) é considerada segura e a próxima ("Secure Hash Algorithm 3") está atualmente em processo de padronização , após uma competição .

Para alguns usos (como hash de senha e derivação de chave de senhas), o domínio dos valores realmente usados xé tão pequeno que forçar esse espaço com força bruta se torna viável com funções normais (rápidas) de hash seguro, e é nesse momento que também queremos:

• execução lenta : Dado x, são necessários alguns recursos mínimos (de preferência configuráveis) para calcular o valor H(x).

Mas para a maioria dos outros usos, isso não é desejado, é preciso:

• execução rápida : dado x, calcular o valor de H(x)é o mais rápido possível (ainda seguro).

Existem algumas construções (como PBKDF2 e scrypt) para criar uma função hash lenta a partir de uma rápida, iterando-a frequentemente.

Para obter mais detalhes, consulte a tag hash em nosso site irmão, Cryptography Stack Exchange.

Seguro significa que alguém que deseja induzi-lo a erro usando uma colisão (ou seja, o fato de duas fontes serem hash com o mesmo valor) terá dificuldades.

Algumas características:

• conhecer o hash, criar um arquivo com hash para esse valor é difícil (variante, parte do novo arquivo é fornecida e o hash desejado)

• criar dois arquivos diferentes com hash com o mesmo valor é difícil (variante, parte dos arquivos é fornecida)

A principal diferença é bem simples: um hash normal visa minimizar o número de colisões acidentais, na medida do possível, sem abrandar muito o processo.

Um hash seguro, destinado a evitar colisões, mesmo quando alguém está fazendo o possível para causar uma. Geralmente, você não deseja trocar nenhuma possibilidade de colisão para uma operação mais rápida. De fato, tornar a operação intencionalmente lenta possui alguns benefícios de segurança, mesmo que não dificulte a localização de colisões.

Para um exemplo deste último: se a computação de um hash demorar 50 ms, isso não afetará materialmente o login de um usuário normal (ou seja, a maioria dos usuários não notará uma diferença de 50ms ao efetuar o login). Ao mesmo tempo, se um invasor quiser fazer um ataque de dicionário, ser capaz de produzir apenas 20 hashes por segundo é uma desvantagem séria . Em outras palavras, dentro de algum tipo de razão, para um hash seguro, mais lento é melhor.

Leia este http://www.codinghorror.com/blog/2012/04/speed-hashing.html que explica tudo muito melhor do que eu jamais poderia explicar. Aqui estão os dois cabeçalhos mais importantes do artigo que abordam diretamente sua pergunta:

• Os hashes seguros são projetados para serem invioláveis
  • muda sua saída radicalmente com pequenas alterações de bit único nos dados de entrada
• Os hashes seguros são projetados para serem lentos

Sua seção TL; DR no final:

Se você é um usuário:

Verifique se todas as suas senhas têm 12 caracteres ou mais, idealmente muito mais. Eu recomendo a adoção de frases secretas, que não são apenas muito mais fáceis de lembrar do que as senhas (se não forem do tipo), mas também são ridiculamente seguras contra a força bruta devido ao seu comprimento.

Se você é um desenvolvedor:

Use bcrypt ou PBKDF2 exclusivamente para fazer o hash de qualquer coisa que você precise para estar seguro. Esses novos hashes foram projetados especificamente para serem difíceis de implementar nas GPUs. Não use nenhuma outra forma de hash. Quase todos os outros esquemas de hash populares são vulneráveis ​​à força bruta por matrizes de GPUs de commodities, que só ficam mais rápidas, paralelas e fáceis de programar a cada ano.

Um hash "seguro" é um hash que se acredita ser difícil de "falsificar" de uma maneira reproduzível e de fórmula, sem o conhecimento prévio da mensagem usada para criar o hash. Como essas informações geralmente são secretas, daí a necessidade de um hash, essa é uma boa propriedade de uma função de hash destinada ao uso na autenticação.

Um hash é geralmente considerado "seguro" se, dada uma mensagem M, uma função de hash hash () e um valor de hash H produzido por hash (M) com um comprimento em bits L, nenhum dos seguintes itens puder ser executado em menos de Tempo O (2 ^L ):

• Dado o hash () e o H, produza M. (resistência à pré-imagem)
• Dado o hash () e o M, produza um M ₂ diferente, _de tal modo que o hash (M ₂ ) == H. (resistência à colisão fraca)
• Dado o hash (), produza qualquer M ₁ e M ₂ tal que o hash (M ₁ ) == hash (M ₂ ). (forte resistência à colisão)

Além disso, um hash "seguro" deve ter um comprimento de hash L tal que 2 ^Lnão é um número possível de etapas para um computador executar o hardware atual fornecido. Um hash inteiro de 32 bits pode ter apenas 2,1 bilhões de valores; enquanto um ataque de pré-imagem (encontrar uma mensagem que produz um hash específico H) levasse um tempo, não é inviável para muitos computadores, especialmente aqueles nas mãos de agências governamentais fretadas com quebra de código. Além disso, um algoritmo que cria e armazena mensagens aleatórias e seus hashes teria, de acordo com a probabilidade, 50% de chance de encontrar um hash duplicado com cada nova mensagem após tentar apenas 77.000 mensagens, e teria 75% de chance de atingir um duplicar depois de apenas 110.000. Até os hashes de 64 bits ainda têm 50% de chance de colidir depois de tentar apenas cerca de 5 bilhões de valores. Tal é o poder do ataque de aniversário em pequenos hashes. Por contraste,decilhões de números (1,5 * 10 ³⁴ ).

Os ataques mais demonstrados aos hashes criptográficos foram ataques de colisão e demonstraram a capacidade de gerar mensagens de colisão em menos de 2 ^{L de} tempo (a maioria ainda tem tempo exponencial, mas reduzir o expoente pela metade é uma redução significativa na complexidade, pois um hash de 256 bits tão fácil de resolver quanto um de 128 bits, um 128 bits tão fácil de resolver quanto um de 64 bits, etc.).

Além do tamanho pequeno do hash, outros fatores que podem tornar um hash comprovadamente inseguro são:

Pouco trabalho - um hash projetado para uso por uma hashtable ou para outros fins do tipo "soma de verificação" geralmente é projetado para ser computacionalmente barato. Isso facilita muito o ataque de força bruta.

"Sticky State" - A função de hash é propensa a padrões de entrada em que o valor atual de hash de todas as entradas até agora não muda quando é fornecido um byte adicional específico de entrada. Ter "estado de aderência" facilita a localização de colisões, pois depois de identificar uma mensagem que produz um hash de "estado de aderência", é trivial gerar outras mensagens com o mesmo hash, acrescentando bytes de entrada que mantêm o hash em seu "estado de aderência" "

Difusão - Cada byte de entrada da mensagem deve ser distribuído entre os bytes do valor do hash de maneira igualmente complexa. Certas funções de hash criam alterações previsíveis em certos bits no hash. Isso novamente torna a criação de colisões trivial; dada uma mensagem que produz um hash, as colisões podem ser facilmente criadas introduzindo novos valores à mensagem que afetam apenas os bits que mudam previsivelmente.

Use o algoritmo certo para a tarefa em questão.

Os CRCs são usados ​​para detecção / correção de erros.

Os resumos de mensagens criptográficas, como SHA2, são usados ​​como um bloco de construção para construções criptográficas (assinaturas digitais, MACs, funções de derivação de chave / hash de senha) e protocolos de segurança.

Nas tabelas de hash / dicionários / mapas, use o SipHash .

O que você chama de algoritmos de hash inseguros não deve ser usado em tabelas de hash , como comprovado pelas seguintes entradas do CVE: CVE-2003-0364, CVE-2011-4461, CVE-2011-4838, CVE-2011-4885, CVE-2011- 4462, CVE-2011-4815, CVE-2012-0840, CVE-2012-5371 , CVE-2012-5374, CVE-2012-5375