Função hash

Uma função hash que mapeia nomes para inteiros de 0 a 15. Existe um colisão entre a chaves "John Smih" e "Sandra Dee".

Uma função hash é um algoritmo que mapeia dados de comprimento variável para dados de comprimento fixo. Os valores retornados por uma função hash são chamados valores hash, códigos hash, somas hash (hash sums), checksums ou simplesmente hashes. Um uso é uma estrutura de dados chamada de tabela hash, amplamente usada em software de computador para consulta de dados rápida. Funções hash aceleram consultas a tabelas ou bancos de dados por meio da detecção de registros duplicados em um arquivo grande. Um exemplo é encontrar trechos similares em sequências de DNA. Eles também são úteis em criptografia. Uma função hash criptográfica permite verificar facilmente alguns mapeamentos de dados de entrada para um valor hash fornecido, mas se os dados de entrada são desconhecidos, é deliberadamente difícil reconstruí-lo (ou alternativas equivalentes) conhecendo o valor do hash armazenado. Isto é usado para assegurar a integridade de dados transmitidos e é o bloco de construção para HMACs, que fornecem autenticação de mensagem.

Funções hash estão relacionadas a (e frequentemente confundidas com) somas de verificação (checksums), dígitos verificadores, impressões digitais, compressão com perdas, funções de aleatorização, códigos de correção de erros e cifras. Apesar desses conceitos se sobreporem até certo ponto, cada um tem seus próprios usos e requisitos e são projetados e otimizados de maneiras diferentes. O banco de dados HashKeeper, mantido pelo American National Drug Intelligence Center, por exemplo, é mais apropriadamente descrito como um catálogo de arquivos de impressões digitais do que de valores de hash.

Descrição

Um hash (ou escrutínio) é uma sequência de bits geradas por um algoritmo de dispersão, em geral representada em base hexadecimal, que permite a visualização em letras e números (0 a 9 e A a F), representando um nibble cada. O conceito teórico diz que "hash é a transformação de uma grande quantidade de dados em uma pequena quantidade de informações".

Essa sequência busca identificar um arquivo ou informação unicamente. Por exemplo, uma mensagem de correio eletrônico, uma senha, uma chave criptográfica ou mesmo um arquivo. É um método para transformar dados de tal forma que o resultado seja (quase) exclusivo. Além disso, funções usadas em criptografia garantem que não é possível a partir de um valor de hash retornar à informação original.

Como a sequência do hash é limitada, muitas vezes não passando de 512 bits, existem colisões (sequências iguais para dados diferentes). Quanto maior for a dificuldade de se criar colisões intencionais, melhor é o algoritmo.

Uma função de hash recebe um valor de um determinado tipo e retorna um código para ele. Enquanto o ideal seria gerar identificadores únicos para os valores de entrada, isso normalmente não é possível: na maioria dos casos, o contradomínio de nossa função é muito menor do que o seu domínio, ou seja, $x$ (o tipo de entrada) pode assumir uma gama muito maior de valores do que $\operatorname {hash} (x)$ (o resultado da função de hash).

Os algoritmos de hash mais usados são os de 16 bytes (ou 128 bits, tamanho do message digest) MD4 e MD5 ou o SHA-1, de 20 bytes (160 bits). Características de alguns algoritmos:

1. MD4: Desenvolvido em 1990/91 por Ron Rivest, vários ataques foram detectados, o que fez com que o algoritmo fosse considerado frágil. Descrito na RFC 1320^{[carece de fontes]}
2. MD5: O MD5 (Message-Digest algorithm 5) é um algoritmo de hash de 128 bits unidirecional desenvolvido pela RSA Data Security, Inc., descrito na RFC 1321, e muito utilizado por softwares com protocolo par a par (P2P, ou Peer-to-Peer, em inglês), verificação de integridade e logins. Existem alguns métodos de ataque divulgados para o MD5.
3. SHA-1 (Secure Hash Algorithm): Desenvolvido pelo NIST e NSA. Já foram exploradas falhas no SHA.
4. WHIRLPOOL: função criptográfica de hash desenvolvida por Paulo S. L. M. Barreto e por Vincent Rijmen (coautor do AES). A função foi recomendada pelo projeto NESSIE (Europeu). Foi também adotado pelo ISO e IEC como parte do padrão internacional ISO 10118-3.

O processo é unidirecional e impossibilita descobrir o conteúdo original a partir do hash. O valor de conferência ("soma de verificação") muda se um único bit for alterado, acrescentado ou retirado da mensagem.

Ver também

• Tabela de dispersão
• Tratamento de colisões através de encadeamento
• Criptografia de chave pública
• Chave privada
• Criptografia