Detalhes

Categoria: Funções Hash

Atualização: Terça, 14 Abril 2009 13:42

Autor: vovó Vicki

Acessos: 49692

Um hash, também chamado de "digesto", é uma espécie de "assinatura" ou "impressão digital" que representa o conteúdo de um fluxo de dados. Com certa frequência os hashes são chamados de checksum, o que provoca alguma confusão com os verdadeiros checksums, os quais têm aplicações e cálculos totalmente diferentes. Um hash pode ser comparado com um selo de embalagem que indica clara e inequivocamente se a embalagem já foi aberta ou violada.

Via de mão única

Hashes não são cifragens, são digestos! As cifragens transformam os dados do texto claro num criptograma e vice-versa, ou seja, é uma operação de duas mãos. Além disso, o tamanho do criptograma geralmente é igual ao comprimento do texto claro. Hashes, por sua vez, transformam os dados do texto (claro ou cifrado) num pequeno digesto, de tamanho fixo, numa operação de mão única. Uma operação de mão única não tem volta, ou seja, não é possível obter o texto claro a partir de um resultado hash.

Saída de comprimento fixo

Os hashes produzem "selos de segurança" de comprimento fixo, não importa o comprimento do fluxo de dados ou do arquivo que representem. Qualquer alteração efetuada no arquivo, por mínima que seja, altera substancialmente o resultado hash. Isto ocorre porque, mesmo se apenas um dos bits do arquivo for alterado, muitos bits do resultado serão afetados. Este comportamento é conhecido como efeito avalanche.

O efeito avalanche fica bastante claro quando observamos o impacto da mudança de apenas um bit no resultado hash. Para exemplificar, vamos usar os caracteres ASCII "A" e "a". Note que apenas o sexto bit (contando da direita para a esquerda e iniciando pelo bit zero) é diferente:

     Caracter     ASCII         ASCII
                (decimal)     (binário)
     ----------------------------------
        A          65         0100 0001
        a          97         0110 0001

Usando o algoritmo MD5, o resultado hash obtido para os textos "Aldeia NumaBoa" e "aldeia NumaBoa", cuja diferença reside num único bit, é completamente diferente:

     Aldeia NumaBoa     3cdb658425ee484e4bff3d4583f6f851
     aldeia NumaBoa     9c1f41ef263026b0283676d63df21fd1

Transformando o valor hexadecimal do hash dos dois textos nos seus correspondentes binários, o efeito avalanche fica evidente, pois a alteração de apenas um bit no texto ocasionou a alteração de 62 bits do resultado hash:

     3cdb6584     0011 1100 1101 1011 0110 0101 1000 0100
     9c1f41ef     1001 1100 0001 1111 0100 0001 1110 1111
                  x.x. .... xx.. .x.. ..x. .x.. .xx. x.xx     12 bits diferentes
     
     25ee484e     0010 0101 1110 1110 0100 1000 0100 1110
     263026b0     0010 0110 0011 0000 0010 0110 1011 0000
                  .... ..xx xx.x xxx. .xx. xxx. xxxx xxx.     20 bits diferentes
     
     4bff3d45     0100 1011 1111 1111 0011 1101 0100 0101
     283676d6     0010 1000 0011 0110 0111 0110 1101 0110
                  .xx. ..xx xx.. x..x .x.. x.xx x..x ..xx     16 bits diferentes
     
     83f6f851     1000 0011 1111 0110 1111 1000 0101 0001
     3df21fd1     0011 1101 1111 0010 0001 1111 1101 0001
                  x.xx xxx. .... .x.. xxx. .xxx x... ....     14 bits diferentes

Aplicações práticas do hash

Se os dados originais não podem ser recuperados a partir do hash gerado pelos mesmos, então para que servem os hashes? Apesar de parecer contraditório, é exatamente esta característica que possibilita o uso de algoritmos hash sempre que uma autenticação ou uma validação seja necessária. Dentre as inúmeras aplicações destacam-se as seguintes:

Integridade de arquivos

Qualquer tipo de arquivo, por exemplo um arquivo de texto ou um programa de computador, é um fluxo de dados que produz um resultado hash único. Quando um arquivo é disponibilizado para download, não existe a garantia de que o arquivo baixado seja idêntico ao original. Basta que ocorra um pequeno problema durante a transmissão que altere os dados recebidos para que a "cópia" não seja perfeita. Uma das maneiras de poder verificar se o arquivo baixado é idêntico ao disponibilizado é conhecer o hash do arquivo original. Após o download é possível calcular o hash do arquivo baixado e, se os dois hashes forem idênticos, a integridade da cópia é comprovada. É importante lembrar que hashes parecidos ou "quase iguais" indicam sempre que os dados que os produziram são diferentes, e nunca parecidos ou quase iguais!

Segurança de senhas

Guardar senhas em texto claro é dar chance para o azar. Se um arquivo de senhas for roubado ou um banco de dados com registros de senhas for hackeado, o estrago pode ser enorme. Como um hash não é reversível e, para serem usadas, as senhas precisam ser conferidas, é muito mais prudente armazenar os resultados hash das senhas do que as próprias senhas. O uso de uma senha pressupõe que um usuário a digite. Tendo a senha como entrada, é fácil e rápido calcular o resultado hash da senha fornecida e compará-lo com o valor arquivado. Se forem idênticos, a senha confere, mostrando que o usuário conhecia uma senha válida. Este procedimento reduz sensivelmente os riscos porque o único momento em que a senha pode ser roubada é enquanto está sendo digitada e antes de ser transformada em hash.

Assinaturas digitais

Para se obter uma assinatura digital válida são necessárias duas etapas. A primeira é criar um hash do documento. Este hash identifica unicamente e inequivocamente o documento do qual ele se originou. A seguir, o assinante submete o hash a um método criptográfico usando sua chave privada. Como o hash criptografado só pode ser recuperado usando a chave pública do assinante, isto comprova a identidade da pessoa que assinou - é a chamada assinatura digital - e como o hash recuperado identifica o documento, a assinatura está associada unicamente a este documento.

Vulnerabilidades

Pelo que foi visto até agora, o cenário parece perfeito: usando métodos que produzam hashes de 128 bits, o número de hashes possíveis atinge um valor astronômico. São, nada mais, nada menos do que 2¹²⁸ = 3,4 x 10³⁸ possíveis. Mais exatamente, as possibilidades somam

     340.282.366.920.938.463.463.374.607.431.768.211.456 hashes de 128 bits

Apesar deste valor enorme, como o número de conjuntos de dados é praticamente infinito, a possibilidade de que dois conjuntos de dados diferentes produzam o mesmo hash não pode ser ignorada. Esta coincidência de resultados é conhecida como colisão. Existem duas formas básicas de se diminuir a ocorrência de colisões: aumentando o número de bits do resultado hash e criando algoritmos que produzam hashes menos vulneráveis. Existem algumas medidas que avaliam as vulnerabilidades. As principais são mostradas a seguir.

Resistência a colisões

A resistência a colisões mede a dificuldade de encontrar duas entradas que produzam o mesmo resultado hash. O valor hash pode ser qualquer um, o objetivo é encontrar duas entradas diferentes que forneçam um resultado idêntico.

Se for possível obter o mesmo resultado hash para duas entradas diferentes, as assinaturas digitais deixam de ser confiáveis. Imagine um "compromisso de compra" que possa ser substituído por outro sem que o valor hash se modifique. Se os documentos forem trocados por alguém com más intenções poderemos ter surpresas bastante desagradáveis. Um dos ataques mais conhecidos para encontrar colisões é o ataque do aniversário. Se você estiver interessado, leia o texto Paradoxo do Aniversário que se encontra no Almanaque da Aldeia.

Colisão: procura de dois textos que produzam um mesmo hash qualquer

Neste caso, a assinatura digital também não pode garantir a autenticidade do documento. Pior do que isto, a assinatura digital coloca nossa anuência no documento! Como já foi visto, a alteração de um simples bit costuma alterar substancialmente o resultado hash. Vai aqui uma sugestão: antes de colocar a sua assinatura digital, faça uma pequena alteração "cosmética" no documento que será assinado. Basta adicionar um espaço ou retirar uma vírgula. Como os dois documentos, o correto e o fraudulento, precisam ser preparados com antecedência para produzirem o mesmo hash, pegamos o fraudador de calças curtas se alterarmos o documento e, consequentemente, seu valor hash no último instante

Resistência de pre-imagem

A resistência de pre-imagem mede a dificuldade de criar um conjunto de dados que resulte num determinado valor hash, sem conhecer o texto que o originou.

Pre-imagem: criação de determinado valor hash sem conhecer o texto original

Se a resistência de pre-imagem for pequena, será mais fácil criar um texto qualquer cujo hash seja igual a um conhecido. Imagine o caso das senhas. Se, conhecendo o valor hash de uma delas, for possível criar uma senha qualquer que resulte num hash idêntico, a segurança de um sistema que faça a autenticação exclusivamente com hashes de senhas estará seriamente comprometido. Mesmo digitando a senha "fabricada", o resultado será aceito.

Resistência de segunda pre-imagem

A resistência de segunda pre-imagem mede a dificuldade de criar um conjunto de dados que resulte num determinado valor hash, conhecendo o texto que o originou.

Segunda pre-imagem: criação de determinado valor hash conhecendo o texto original

Assim como a resistência de pre-imagem, se a resistência de segunda pre-imagem for baixa, a criação de um conjunto de dados que resulte num hash conhecido torna-se mais fácil. É comum encontrarmos software para download acompanhado de seus valores hash, portanto, é fácil obter a matéria prima que pode ser fraudada. Se alguém com más intenções alterar o software, mas conseguir preservar seu resultado hash, os usuários que fizerem o download do "safadoware" não terão como identificar o software adulterado e potencialmente perigoso!

Fontes

• Steve Friedl's Unixwiz.net