Como funciona o hashing?

As funções hash criptográficas são objetos matemáticos que podem ser descritos como “uma grande mistura e embaralhamento de alguns bits “. Eles tomam como entrada uma sequência de bits (possivelmente muito longa) e oferecem uma saída de tamanho fixo. A grosso modo, eles estão tão emaranhados que, embora não haja nenhum segredo sobre eles (isso é apenas código determinístico), ninguém consegue descobrir como “invertê-los” (encontrar uma entrada correspondente para uma determinada saída), exceto pelo método básico chamado “sorte”: tente entradas aleatórias até que uma correspondência seja encontrada.

Como pode acontecer, cientificamente, que funções hash possam existir é uma boa pergunta .

Hashing não é criptografia . Não há segredo nem chave no hash.

As funções de hash têm muitos usos; um deles é o “armazenamento de senha”. Uma função hash parece uma boa opção para armazenamento de senhas. Não queremos armazenar senhas diretamente (caso contrário, uma espiada ocasional em nossos bancos de dados pelo invasor forneceria muitas informações; consulte esta postagem do blog para ver uma discussão) ; queremos armazenar tokens de verificação de senha : algo que permite a verificação de uma senha (que o usuário apresenta), mas não revela a própria senha. Portanto, a ideia é: vamos armazenar o hash da senha. Quando uma senha deve ser verificada, nós apenas calculamos seu hash e vemos se ele corresponde ao valor armazenado. Mas adivinhar a senha apenas pelo valor do hash é difícil, já que a função hash é resiliente contra “inversão” (veja acima).

Visto que as senhas são um tipo especial de dados (são dados que os humanos podem lembrar), para a segurança adequada, precisamos de um “reforço” função hash:

• Queremos uma função hash muito lenta .
• Não queremos uma função hash, mas muitas funções hash distintas, de modo que cada senha será hash com sua própria função hash; trata-se de impedir ataques paralelos. Este processo de transformar uma única função hash em muitas variantes é chamado de salting .

Veja esta resposta para um tratamento completo do assunto hash de senhas.

Comentários

• Desculpe, mas sua resposta foi extremamente completa e bem elaborada, eu achei a outra resposta deve ser mais parecida com o que eu estava procurando.

O hash é uma função de alguns string de bits (geralmente de comprimento variável) para outra string de bits (geralmente menor e de comprimento fixo).

O hash é usado em bancos de dados para recuperação de dados e em estruturas de dados na memória chamadas tabelas de hash. Isso nos permite reduzir dados arbitrários, como uma sequência de caracteres ou um objeto complicado com muitos campos, a um número binário que pode então ser usado diretamente como um índice em uma matriz esparsa para buscar os dados associados (com alguns detalhes para lidar com o hash colisões).

As funções de hash usadas da maneira acima são “primas” das funções de hash criptográficas. Eles são projetados para diferentes requisitos. Eles devem ser rápidos para calcular e alcançar uma boa distribuição.

Na computação segura, os hashes criptográficos são usados para digerir os dados em algumas pequenas cadeias de bits representativas. As funções criptográficas têm requisitos diferentes. Eles são projetados para serem difíceis de reverter (para serem funções de “alçapão” ou “mão única”). Não apenas isso, mas um requisito importante é que deve ser difícil encontrar, para um determinado texto simples e valor de hash, outro texto simples que produza o mesmo hash.

O hash pode ser usado não apenas para senhas, mas como uma soma de verificação para verificar a integridade dos dados e como parte da implementação de assinaturas digitais. Para assinar digitalmente um documento grande, simplesmente temos que fazer o hash do documento para produzir um “resumo” (um nome usado para a saída de uma função de hash, quando algo muito longo é hash). Em seguida, apenas esse resumo é colocado no sistema de criptografia de chave pública para produzir uma assinatura. Você pode ver a fraqueza aí: e se um invasor conseguir produzir um documento com o mesmo resumo? Em seguida, parece que a assinatura original produzida sobre o documento genuíno é na verdade uma assinatura de um documento falsificado: uma falsificação de transplante de assinatura foi efetivamente perpetrada.

O hashing de senha permite que os sistemas não armazenem a versão em texto simples de uma senha, mas permite que eles verifiquem se o usuário que está tentando obter acesso conhece essa senha. O hashing não apenas permite que os sistemas não armazenem as senhas de texto simples (que teriam que ser protegidas com muito cuidado), mas também permite a possibilidade de que, mesmo que os hashes sejam expostos publicamente, as senhas ainda sejam seguras (de forma semelhante à criptografia de chave pública sistemas são capazes de revelar chaves públicas). Embora na prática, os hashes são protegidos do acesso público: por exemplo /etc/shadow arquivos em sistemas semelhantes ao Unix, complementando arquivos /etc/passwd legíveis por todos .

A função de hashing é tudo menos aleatória. No entanto, a randomização é empregada para impedir invasores que criam grandes dicionários de senhas e hashes, que os permitem procurar um código hash e recuperar a senha correspondente.

Para fazer o hash de uma senha com mais segurança, podemos simplesmente adicionar alguns bits aleatórios a ele chamados de “sal”. Sais diferentes adicionados à mesma senha, é claro, levam a hashes diferentes (esperançosamente com poucas ou nenhuma colisão).

Se o sal aleatório tem, digamos, 32 bits de largura, isso significa que, em teoria, uma senha pode fazer hash de mais de quatro bilhões de maneiras diferentes, tornando muito impraticável ter um dicionário pré-computado de todos os hashes possíveis de um grande número de senhas.

Claro, quando o usuário está sendo autenticado, ele não sabe nada sobre esse sal. Tudo bem porque o salt é armazenado junto com o hash no perfil do usuário (geralmente, combinado com o hash em uma única bitstring compacta). Quando a entrada da senha do usuário está sendo validada, o salt é adicionado a qualquer senha ela entrou, para que o hashing seja feito com o sal correto. Se a senha estiver correta, o hash irá combinar, já que o salt que está sendo usado também é o certo, tendo sido retirado do perfil do usuário.

Então é assim que a aleatoriedade é incorporada ao hashing da senha, enquanto ainda permite que funcione.

O que torna os hashes difíceis de quebrar é que eles são construídos a partir de funções de “alçapão” ou “de mão única”. Em matemática, existem muitos exemplos dessas coisas. Por exemplo , a adição simples é uma armadilha. Se adicionarmos alguns inteiros para produzir uma soma, é impossível recuperar os números originais, sabendo apenas a soma.

Os hashes de senha não são senhas criptografadas. Se um invasor tiver o hash e o salt de uma senha, e por acaso adivinhar a senha, então ela pode confirmar isso facilmente, exatamente da mesma forma que o software autenticador de login faz: ela executa a senha mais o salt através da função de hashing e vê que o correto surge o hash.

Comentários

• Excelentes habilidades de escrita e uma facilidade real y para entender a resposta que é totalmente correta e factualmente correta, mas lida com todos os pontos e retém um fluxo natural que a torna muito mais abrangente. Isso ‘ não é uma tarefa fácil, muito obrigado por sua resposta!
• muito informativo. Você cobriu todos os aspectos.

Um dos segredos do hashing é que ele joga fora as informações. Você não pode reverter um hash porque o conhecimento necessário se foi. Aqui estão alguns exemplos de funções de hash viáveis (mas sem valor). Se você me der uma senha, eu poderia fazer algo como o seguinte:

• Contar o número de vogais
• Pegue o código ASCII para cada letra e XOR todos juntos
• Faça a soma de verificação CRC32 da representação binária da senha (esta é na verdade um hash real, mas não criptográfico)

Em cada uma dessas instâncias, não posso reverter o processo. Em vez disso, tenho que executar novamente o processo quando você me fornecer a senha novamente para ver se o cálculo que executei corresponde.

Para exemplo: Se você inicialmente me der a senha “macaco”, posso armazenar o número 3 (3 vogais). Depois, mais tarde, quando tento autenticar a senha “dragão”, faço a mesma verificação novamente e obtenho 2, que não corresponde a 3. Portanto, sei que você me deu a senha errada. Mas se você me der a senha “melissa”, presumirei incorretamente que você digitou a senha correta. Este é um hash colisão .

O conjunto de regras que você aplica para chegar ao número que representa uma determinada senha é a sua função hash . Estas são consideradas funções “unilaterais” porque você não deve ser capaz de revertê-las. As funções hash de alta qualidade são projetadas para limitar o número de colisões potenciais, para que você não precise se preocupar com esse problema. Um passo adiante, funções hash criptográficas são projetadas para dificultar a criação de uma string que possa corresponder a uma determinada saída ( e talvez criar colisões intencionalmente). Eles também são projetados para limitar a quantidade de informações que você pode obter sobre uma determinada entrada apenas da saída hash.

Portanto, a única maneira de saber qual senha corresponde a um determinado hash criptográfico é tentar todas as possibilidades até encontrar uma que funcione. Outras contramedidas (salt, BPKDF2, etc) tornam esse processo de adivinhação ainda mais difícil, fazendo com que a pessoa que adivinhe a senha passe por mais obstáculos a cada tentativa.

Observe que eu encobri completamente como uma função de hash criptográfica a torna difícil de encontrar uma senha funcional (mesmo que não seja a original). Isso é chamado de “ ataque de pré-imagem “. No exemplo trivial acima, sugerir” melissa “como uma senha candidata contendo 3 vogais é um exemplo desse tipo de ataque.

As funções hash criptográficas normalmente fazem isso executando a entrada através de vários” rodadas “de um determinado processo, em que a saída de cada rodada torna-se parte da entrada para a próxima.Para descobrir a entrada da primeira rodada, você teria que descobrir a entrada da segunda rodada, que por sua vez requer que você descubra a entrada da terceira rodada, etc., o que significa que cada estimativa de cada componente deve ser verificado por meio de um longo e complexo conjunto de cálculos. Thomas Pornin tem uma bela explicação exaustiva de como essa resistência funciona; uma leitura muito útil se você realmente quiser entenda-o.

1. Determine o valor constante de z satisfazendo esta equação: xy ^ 7 + yz ^ 5 + x ^ 3z = 0. Precisa de ajuda? OK, x = 32. Ainda não consegue resolver? Então você não deve saber a resposta em primeiro lugar.

   O valor de y, o que irá reduzir isso a uma única equação de variável, tornando a solução para aquela única variável trivial para qualquer aluno do 6º ano (possivelmente precisando de uma calculadora), é um segredo que compartilhei apenas com pessoas em quem confio. Sem ele, z poderia ser qualquer coisa; seu valor depende de y e, portanto, não pode ser resolvido satisfatoriamente sem uma constante, conhecida y. Se você não fizer isso. Não sei seu valor, é porque não confiei em você o suficiente para fornecê-lo em particular.

   Este é o princípio básico da criptografia; a fórmula matemática ou outro processo determinístico é bom -documentada, e uma ou mais das variáveis possíveis da fórmula também podem ser conhecidas publicamente, permitindo que as duas partes concordem sobre uma forma de configurar suas cifras de modo que cada uma possa descriptografar o que a outra criptografa. No entanto, duas variáveis permanecer em segredo; se você conhece um, pode descobrir o outro. Aquele que você deve saber é a chave, e aquele que você pode descobrir com a chave é a mensagem.

   Para um hash, é um pouco diferente. Um hash não exige que um segredo seja mantido para manter outro. Em vez disso, os hashes funcionam com base em uma transformação matemática irreversível; para qualquer H (x) = y, não há H ^{-1 (y) = x exceto para tentar H (x) para todos os x possíveis até obter y. Normalmente, isso ocorre porque vários resultados intermediários da equação são ambíguos; por exemplo, calcular a raiz quadrada de um número positivo produz tecnicamente ambos um resultado positivo e negativo, uma vez que qualquer um dos números pode ser multiplicado por si mesmo para produzir o resultado. O inverso de um módulo é igualmente ambíguo; o número 1, produzido por x mod 3, poderia ter sido produzido por qualquer x = 3k + 1. Esses tipos de transformações “unidirecionais” são combinados de tal forma que tentar calcular a função hash inversa gera possibilidades infinitas; a maneira mais fácil (mais fácil) de resolvê-los é, portanto, simplesmente tentar todas as entradas possíveis até que uma saída corresponda. ainda leva muito tempo.}

2. Hashes não são aleatórios. Como afirmei anteriormente, os hashes são o resultado de uma operação matemática irreversível. Essa operação ainda deve ser determinística; dada uma entrada constante, a saída é constante, independentemente de quantas vezes você execute a operação. Não há componente aleatório.

   Onde você pode ter ficado confuso é no termo para o que um hash simula, que é um oráculo aleatório . Imagine uma caixa preta, dentro da qual está um homenzinho com memória fotográfica e algum método místico de gerar números perfeitamente aleatórios. Você escreve algo em um pedaço de papel e o empurra por uma fenda onde o homem o pega. Ele o lê e uma de duas coisas acontece. Ou ele não o leu antes, caso em que irá gerar um novo número aleatório e dar a você, gravando sua mensagem e o número na memória dele. Ou ele leu exatamente isso mensagem anterior, caso em que ele se lembra do número que gerou na primeira vez que a leu e lhe dá o número. O gerador de números aleatórios nunca irá gerar um número que já gerou, tem magnitude possível infinita, e o homenzinho a memória é ilimitada e infalível. Portanto, o homenzinho nunca pensará que leu uma mensagem antes, se não, nunca se esqueça que leu uma mensagem antes, e então nunca, jamais, produzirá dois números diferentes para a mesma mensagem exata ou a mesma número para duas mensagens diferentes.

   Isso é o que as funções hash tentam simular. Eles não podem modelar este homenzinho com a memória fotográfica, porque isso exigiria espaço de armazenamento infinito e disponibilidade universal ilimitada, até mesmo para dispositivos que não estão conectados a nenhum outro dispositivo de nenhuma outra maneira. Em vez disso, eles dependem de um cálculo determinístico, mas de aparência aleatória que “digere” a mensagem em seu valor hash. A mesma função hash, dada a mesma mensagem, produzirá o mesmo resumo; no entanto, essas funções são limitadas no número de valores de hash que podem retornar. Isso cria a possibilidade do que chamamos de colisões de hash; há mais mensagens possíveis do que valores de hash, então mais cedo ou mais tarde (espero mais tarde), dois eu diferente ssages produzirão o mesmo hash.

3. Hashes podem ser quebrados por três razões básicas.Primeiro, porque eles são uma derivação matemática determinística de sua mensagem, os matemáticos (e, portanto, os invasores) acabam descobrindo uma relação matemática entre uma mensagem e seu hash, ou entre duas mensagens e seus hashes resultantes. O que antes parecia aleatório não é mais. Isso permitiria uma série de ataques com base na natureza da fraqueza encontrada; se houver uma maneira algorítmica, dada uma mensagem e seu hash, para gerar uma mensagem colidindo, isso é um problema. Se houver uma maneira de manipular uma mensagem e prever o hash resultante, o problema será diferente. Se houver de fato uma maneira de reverter o hash, produzindo uma mensagem a partir do hash que, quando refeito, produz o mesmo hash, isso “é um problema sério .

   Em segundo lugar, como os hashes têm um tamanho de resumo limitado, mais cedo ou mais tarde, duas mensagens produzirão o mesmo hash. Isso significa que um invasor não precisa encontrar a mensagem que você usa para produzir um determinado hash ; tudo o que ele precisa fazer é encontrar uma mensagem que produza o mesmo hash. As chances disso são mínimas, teoricamente uma chance de quantos hashes possíveis existem, mas ainda melhor do que uma no infinito.

   Por último, embora existam muitas mensagens possíveis, há uma muito menor número de mensagens prováveis . As mensagens que normalmente enviamos para funções hash geralmente têm alguma estrutura (com base no idioma, assunto, formatação eletrônica e propósito), o que significa que, dada alguma parte da mensagem, podemos adivinhar com mais precisão outras partes da mensagem. Isso significa, em termos de ciência da informação, que as mensagens que são convertidas em hashes geralmente têm entropia menor do que a própria função de hash; em poucas palavras, uma função hash que produz resumos de 256 bits pode teoricamente produzir qualquer permutação desses bits, 2 ^ 256. No entanto, se houver, digamos, apenas 10.000 mensagens possíveis que possam ser inseridas nesta função de hash por um sistema que está sendo estudado para ataque, então apenas 10.000 dos 2 ^ 256 valores de hash possíveis serão vistos e, mais importante, um o invasor, na pior das hipóteses, teria apenas que tentar todas as 10.000 entradas possíveis para encontrar aquela que produz o valor de hash que ele está procurando.

Comentários

• E é por isso … que adoro a segurança de TI ‘ uma coisa do site de troca de pilha.
• Também sua explicação de # 1 é exatamente o que eu precisava. No entanto, tenho uma pergunta. Parece que ” hashes ” são como versões numéricas para uma determinada coisa (senhas, neste caso). Então, se eu tiver um site e 100.000 pessoas se inscreverem. Então 50% usam a senha ” senha ” Consigo economizar muito espaço apenas armazenando o valor hash de ” senha ” em vez de senha uma tonelada de vezes?
• Bem, se você ‘ está usando um hash seguro (> = tamanho do resumo de 256 bits), em seguida, armazenando o valor hash de ” senha ” vai aumentar o tamanho do seu armazenamento. Além disso, se um invasor visse que 50% das contas de usuário tinham o mesmo hash de senha, ele ‘ d saberia que todos ele ‘ d tem que fazer é quebrar uma senha e ele terá acesso a 50% das contas de usuário. Você deve ” salting ” seus hashes de senha; há uma variedade de métodos, mas o resultado final é que a mesma senha com hash pelo mesmo algoritmo produz um resumo diferente, por causa de um valor salt exclusivo adicional para cada conta.