Funções hash ou hashing
Continuando a série sobre criptografia (pode ler a primeira parte aqui), este artigo vai mostrar o que são funções hash e suas principais aplicações.
As funções hash são um dos pilares da criptografia moderna e largamente usada hoje em dia. Como o exato modo de funcionamento de um hash é muito complexo, vamos mostrar aqui apenas uma parte para que você possa compreender melhor essa funcionalidade e suas aplicações no mundo real.
Definição
Uma função hash é um algoritmo que mapeia dados de entrada de comprimento variável para dados de comprimento fixo. Os valores retornados por uma função hash são chamados de valores hash ou simplesmente hash.
A função hash é usada para resolver o princípio de integridade da criptografia, garantindo que a mensagem não foi alterada durante a transmissão.
Caso você queira enviar uma mensagem para outra pessoa, uma comunicação com problemas pode causar com que a mensagem não chegue à outra pessoa na sua forma correta, ou seja, ela foi corrompida. Então como garantimos que todos os 0 e 1 sejam recebidos na ordem correta? É aqui que a função hash entra. Ela garante que a mensagem está íntegra e na ordem correta.
Características
As principais características de uma função hash são:
- Saída (hash) de tamanho fixo: as funções hash recebem uma mensagem (entrada) de qualquer tamanho e sempre produzem o mesmo tamanho de saída. Geralmente são de tamanho menor que o dado de entrada, sendo uma representação do dado original (também conhecido como digest).
- Eficiência da operação: as funções hash devem ser eficientes na sua computação, já que são normalmente usadas para verificação de dados.
- Determinística: uma mensagem sempre vai gerar o mesmo valor de hash.
Propriedades
Para que seja usada no ramo da criptografia, uma função hash deve possuir algumas propriedades:
- Resistência à pré-imagem: significa que é inviável computacionalmente reverter um hash. Ou seja, se uma função hash produziu um valor z, deve ser um processo muito árduo achar uma entrada x que contenha o hash valor z. Esta propriedade protege contra um alguém que tenha somente o valor do hash e está tentando encontrar o valor de entrada.
- Resistência à segunda pré-imagem: dado uma entrada x e um hash z, deve ser difícil achar uma segunda entrada que produza o mesmo hash z. Também conhecido como resistência fraca à colisão. Esta propriedade protege contra o ataque de alguém que tenha o valor de entrada e o seu hash e que queira substituir a entrada como uma mensagem válida.
- Resistência à colisão: significa que deve ser difícil achar duas entradas diferentes de qualquer tamanho que resultem no mesmo hash. Também conhecido como resistência forte à colisão. Desde que uma função hash tem um valor fixo de saída, é impossível não haver uma colisão. Esta propriedade garante apenas que é muito difícil de achar. Se uma função possui essa propriedade, automaticamente possui a resistência à segunda pre-imagem.
Algoritmos de checksum, tais como CRC32, não possuem essas propriedades e portanto não são consideradas como funções hash criptográficas.
Como funciona?
Uma função hash é uma função matemática que opera em dois blocos de tamanhos fixos de dados para criar um hash. Esta função forma uma parte do algoritmo de hash.
O tamanho de cada bloco varia de acordo com o algoritmo. Geralmente, entre 128 a 512 bits.
O algortimo de hash envolve diversas rodadas dessa função em cadeia. Cada rodada pega uma entrada de tamanho fixo, normalmente uma combinação de uma parte da mensagem mais recente e a saída da última rodada. Este processo é repetido quantas vezes for necessário para que toda a mensagem tenha sido processada.
Dessa forma, o hash do primeiro bloco se torna uma entrada para a segunda operação de hash, cuja saída se torna uma entrada para a terceira e assim sucessivamente, até o término da mensagem. Este efeito é conhecido como efeito avalanche e resulta em valores totalmente diferentes de hash para duas mensagens que variam por apenas um bit de dado.
Funções populares
Vamos falar rapidamente sobre algumas funções de hash mais usadas.
Message Digest (MD)
Foi uma das funções mais usadas por vários anos (e ainda é em alguns casos). A família MD possui as funções MD2, MD4, MD5 e MD6, tendo sido adotada como um padrão da internet por muito tempo. Possui um hash de 128 bits.
A função MD5 foi muito utilizada no mundo de software para garantir a integridade de arquivos. Por exemplo, um servidor pode prover um valor hash MD5 de um arquivo já pré-calculado para o usuário possa comparar quando tiver realizado o download dele.
Em 2004 foram achadas vulnerabilidades nesse algoritmo e ele não é mais recomendado.
Secure Hash Function (SHA)
A família do SHA consiste em quatro algoritmos: SHA-0, SHA-1, SHA-2 e SHA-3. Embora sejam da mesma família, são estruturalmente diferentes.
A versão original do SHA-0, de 160 bits, foi publicada em 1993. Por ter algumas falhas, não se tornou popular.
A versão SHA-1 foi amplamente utilizada na internet em aplicações e protocolos como o SSL durante muito tempo (em 2016, o SHA-2 se tornou o padrão SSL).
A família do SHA-2 contém quatro variações: SHA-224, SHA-256, SHA-384 e SHA-512, dependendo do número final de bits do hash.
Em 2012, o algoritmo Keccak foi escolhido como o novo padrão SHA-3.
RIPEMD
O algoritmo RIPEMD é um acrônimo para “RACE Integrity Primitives Evaluation Message Digest”. Esta família de funções foi projetada por uma comunidade de pesquisadores e inclui hashes de tamanhos 128, 160, 256 e 320 bits, sendo a versão RIPEMD-160 a mais comum.
A versão RIPEMD original e também RIPEMD-128 são consideradas não seguras devido ao tamanho e ao design.
Whirpool
Projetado por um co-criador do AES, é uma versão derivada do próprio AES (algoritmo de encriptação).
Tem três versões lançadas, conhecidas como WHIRLPOOL-0, WHIRLPOOL-T e WHIRPOOL, todas contendo um hash de 512 bits.
Aplicações
As funções hash são usadas em diversos cenários diferentes. Vamos falar de alguns deles aqui.
Integridade de documentos
Verificar a integridade de documentos / arquivos / mensagens. Você já deve ter visto em alguns sites de downloads que contém um valor de hash ao lado do arquivo (MD5 ou SHA-2, por exemplo).
A imagem abaixo mostra o SHA-2 do arquivo do sistema operacional Rasbian (mais aqui).
Assim que baixar o arquivo, você pode comparar o seu hash original com o hash do arquivo que você baixou. Nesse caso, por exemplo, você pode usar o comando sha256sum no Ubuntu para verificar o hash de um arquivo.
Salvar senhas
Salvamento e verificação de senhas é outra das aplicações. Ao invés de guardar a senha em claro em um banco de dados, os desenvolvedores normalmente salvam os hashes das senhas ou um valor mais complexo derivado da senha (usando salt ou outros passos).
O exemplo acima vem do arquivo /etc/shadow, que está em um Ubuntu. A senha acima está salva como uma rodada múltipla de SHA-512 com salt.
Gerar um ID único
Gerar um ID (quase) único de certo documento ou mensagem, já que uma função hash criptográfica conseguem gerar um único valor a partir do conteúdo de um documento. Na teoria, as colisões são possíveis em qualquer função hash, mas é bem improvável de acontecer, então a maioria dos sistemas assumem que o hash que eles utilizam seja livre de colisão.
Por exemplo, o Git usa um hash (SHA-1) para identificar cada commit que é feito no repositório. Depois, caso você queira ir para um commit específico ou referenciar ele de algum modo, você pode usar esse valor para identificar ele no sistema.
Gerador de número pseudo-aleatório
Hashes podem ser usados como geradores de números pseudo-aleatórios ou derivação de chaves. Um modo simples de gerar uma sequência aleatória é assim:
- Comece de uma fonte aleatória (coletada de um evento aleatório, como cliques do mouse ou do teclado).
- Adicione “1” e calcule o hash para se obter o primeiro número.
- Adicione “2” e calcule o hash para se obter o segundo número.
- E assim sucessivamente.
Algoritmos de provas-de-trabalho (Proof-of-Work)
Protocolo utilizado para a prevenção de ataques cibernéticos como o DDoS e Spams. Para que um usuário realize uma ação, ele deve ser capaz de provar que realizou uma tarefa. Essa prova é a garantia que o usuário gastou tempo para gerar uma resposta que satisfaça uma condição do avaliador. Outro uso bastante conhecido desse sistema é em blockchains.
A maioria dos algoritmos usados calculam um valor de hash que é maior que um certo valor definido (conhecido como dificuldade de mineração). Para encontrar esse valor hash, os mineradores devem calcular bilhões de diferentes hashes até encontrar aquele que satisfaz a condição. Por exemplo, um protocolo pode definir que só aceita um número p tal que o hash(x+p) contenha os 10 primeiros bits como zero.
Conclusão
Este artigo mostrou um pouco sobre as funções hash e suas aplicações no mundo real.
Na próxima parte, vamos falar um pouco mais sobre criptografia de chave simétrica.
