O que torna um algoritmo de hash "seguro"?

19

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?

CodexArcanum
fonte
8
Esta pergunta é mais adequada para o site do IT Security SE.
Bernard
@ Bernard Se esse for o caso, estou bem com isso, mas minha pergunta não era realmente sobre como ou quando usar um hash seguro, mas o que distingue um algoritmo de hash seguro de um inseguro. Isso me parece mais uma pergunta de programação, mas eu não navego no IT Security SE, então talvez isso funcione também.
CodexArcanum
2
Uma pergunta muito semelhante já foi feita sobre Segurança de TI
ChrisF

Respostas:

34

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.

Paŭlo Ebermann
fonte
3

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)

AProgrammer
fonte
3

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.

Jerry Coffin
fonte
3
No domínio das funções de hash criptográfico, existem dois subgrupos importantes: os mais rápidos (usados ​​para autenticação de mensagens, assinatura e similares) e os mais lentos - usados ​​para derivação de chave e hash de senha. Não misture isso, existem aplicativos para ambos.
Paŭlo Ebermann
Na verdade, também existem funções de hash projetadas para maximizar colisões: o Soundex é um exemplo. Obviamente, isso a torna uma função hash segura muito ruim.
21812 Jörg W Mittag
@ JörgWMittag: Não apenas ruim como um hash seguro, mas também seria bastante ruim para uso com uma tabela de hash. Por outro lado, embora certamente pareça um hash, eu hesitaria em chamar o Soundex de função hash, simplesmente porque sua intenção e uso são muito diferentes das funções hash normais.
Jerry Coffin
@JerryCoffin: Eu acho que depende da definição. Por exemplo, a página da Wikipedia em inglês simplesmente diz que uma função hash é qualquer algoritmo ou sub-rotina que mapeia um conjunto maior (potencialmente infinito) de valores arbitrários em um conjunto menor e finito de valores (geralmente escalares). Enquanto a página alemã da Wikipedia diz que o "hash" (alemão: "zerhacken") é parte integrante, ou seja, é essencial evitar a colisão e distribuir os valores mapeados. O Soundex cumpre muito a primeira definição, mas não a segunda.
Jörg W Mittag
3

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.

Nate
fonte
4
Jeff está errado aqui no segundo ponto ... enquanto, para alguns usos (como hash de senha e derivação de chave de uma senha), você quer ser lento, para outros usos (como autenticação de mensagens, assinaturas etc.) rápido (seguro) funções de hash são boas.
23812 Paolo Ebermann
Você está correto Paŭlo. O desempenho do hash depende da aplicação do hash. No entanto, os hashes lentos são sempre mais seguros que os rápidos. O motivo pelo qual você usaria um hash rápido é se você está bem sacrificando a segurança pelo desempenho.
Nate
2
@Nate “Mais seguro” é sempre ambíguo, mas mesmo sob o aplicativo mais caridoso, “hashes lentos são sempre mais seguros que os rápidos” estão definitivamente errados. Existem muitas aplicações em que a velocidade de um hash é irrelevante.
Gilles 'SO- stop be evil'
@Gilles você pode dar um exemplo? Isso realmente soa verdadeiro para mim, mas mais detalhes seriam úteis.
Nate
2
@Nate A aplicação mais óbvia de hashes é verificar a integridade de um dado: transmitir o hash por um canal seguro, mas possivelmente com largura de banda baixa, transmitir a carga útil possivelmente grande por um canal inseguro e verificar se a carga recebida tem a expectativa cerquilha. Os hashes também aparecem com destaque nos métodos de assinatura (onde você não apenas verifica a integridade, mas também quem enviou os dados). Hashing senhas é bastante a exceção.
Gilles 'SO- stop be evil'
2

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 2 diferente, de tal modo que o hash (M 2 ) == H. (resistência à colisão fraca)
  • Dado o hash (), produza qualquer M 1 e M 2 tal que o hash (M 1 ) == hash (M 2 ). (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 34 ).

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.

KeithS
fonte
0

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

Erwan Legrand
fonte