Detalhes

Categoria: Funções Hash

Atualização: Quarta, 22 Abril 2009 11:05

Autor: vovó Vicki

Acessos: 26403

A segurança das funções hash

Em termos práticos, a segurança das funções criptográficas hash pode ser medida apenas em relação à sua resistência a ataques. Normalmente os adversários procuram uma preimagem, segunda preimagem ou colisão em funções hash ou produzem dados forjados para um MAC.

Ataque randômico

Este é o tipo de ataque mais óbvio. O adversário simplesmente seleciona uma entrada ao acaso e espera pelo resultado hash. Dado o hash de uma mensagem h(M), o adversário tenta criar um outro documento, M', de modo que h(M) = h(M'). Se a função hash possuir um comportamento 'randômico', sua probabilidade de sucesso é considerável (cerca de 50%). Na prática, o ataque pode ser efetuado em paralelo, usando a computação distribuída num grande número de máquinas com uma chance não desprezível de se obter uma preimagem ou uma segunda preimagem.

Ataque do aniversário

Este ataque se baseia na idéia de que num grupo de 23 pessoas a probabilidade de que, pelo menos, duas pessoas façam aniversário no mesmo dia é maior do que 50%. Intutitivamente, a impressão geral é que o grupo de pessoas deveria ser muito maior para que isto acontecesse, motivo pelo qual esta constatação é chamada de paradoxo do aniversário.

Este tipo de ataque é mais sutil do que o anterior e baseia-se num problema padrão da estatística. Quantas pessoas precisam estar numa sala para que a chance de uma delas fazer aniversário no mesmo dia que você seja maior do que 50%? A resposta é 253. Agora, se a pergunta for "Quantas pessoas precisam estar numa sala para que a chance de duas delas comemorarem aniversário no mesmo dia seja maior do que 50%?", o resultado é surpreendente baixo. Com apenas 23 pessoas na sala, a chance de que duas façam aniversário no mesmo dia é maior do que 50%. É que, apesar do número baixo de pessoas, existem mais de 500 pares diferentes de pessoas na sala. Caso você tenha interesse em saber como os cálculos são efetuados, visite o Almanaque da Aldeia.

Achar alguém com um aniversário específico é análogo ao primeiro ataque; achar duas pessoas com o mesmo aniversário randômico é análogo a este segundo ataque, também conhecido como ataque do aniversário.

Imagine que determinada função hash siga todas as propriedades citadas acima e que a melhor forma de atacá-la seja através da força bruta. Se esta função criar um resultado hash de m bits, encontrar uma mensagem que resulte no hash procurado requer 2^m mensagens randômicas. Agora, encontrar duas mensagens que produzam o mesmo hash requer apenas 2^m/2 mensagens randômicas. Um computador que seja capaz de processar um milhão de mensagens por segundo levaria 600.000 anos para encontrar uma segunda mensagem para determinado hash de 64 bits. A mesma máquina pode achar um par de mensagens que resultam num hash de 64 bits igual em cerca de uma hora!

Resta saber como um ataque do aniversário pode ser usado para fins escusos. Imagine que um safado prepare dois contratos, um favorável para o bonzinho e outro no qual o bonzinho transfere todos os seus bens para o safado. De posse destes dois documentos, o safado faz várias pequenas alterações nos dois documentos: troca espaço por espaço-backspace-espaço, insere um ou dois espaços antes das quebras de linha, etc. Introduzindo (ou não) estas pequenas alterações em cada uma de 32 linhas de texto, o safado consegue gerar 2³² documentos diferentes. Depois disto, o safado compara os hashes dos documentos até encontrar um par, tarefa perfeitamente possível de ser realizada se o resultado hash tiver apenas 64 bits. Encontrando estes dois documentos, um do contrato bom e outro do contrato alterado, o safado pede para o bonzinho assinar o documento bom usando um protocolo no qual ele apenas assina o valor hash. Quando lhe convier, o safado troca os contratos e não há cristão que possa provar que não seja o documento original assinado pelo bonzinho

Este cenário não tem nada de surreal, é perfeitamente possível de ocorrer. E tudo por conta do ataque do aniversário aplicado a funções hash de 64 bits. Por este motivo, a maioria das funções produzem hashes de pelo menos 128 bits. Isto força qualquer atacante a utilizar, no mínimo, 2⁶⁴ documentos randômicos para encontrar dois cujos hashes tenham o mesmo valor. Mas como é possível obter hashes com mais de 64 bits? Dentre os métodos propostos, o seguinte é bastante eficiente:

1. Gerar o valor hash de uma mensagem, usando uma função hash de mão única.
2. Concatenar a mensagem e o hash obtido.
3. Gerar um novo hash da mensagem com o hash concatenado.
4. Criar um valor hash maior que consiste da valor hash gerado na etapa 1 concatenado ao hash gerado na etapa 3.
5. Repetir as etapas 1 a 3 o quanto se desejar.

As funções hash mais conhecidas

• SNEFRU é uma função hash de mão única desenvolvida por Ralph Merkle que cria resultados hash de 128 ou de 256 bits.
• N-HASH é um algoritmo inventado por pesquisadores da Nippon Telephone and Telegraph, os mesmos que inventaram o FEAL. Usa blocos de 128 bits de mesnagem e produz um resultado hash também de 128 bits.
• MD4, onde MD vem de message digest, é uma função hash de mão única desenvolvida por Ron Rivest que também produz um valor hash de 128 bits.
• MD5 é uma versão melhorada do MD4. Também de Ron Rivest, produz um resultado hash de 128 bits.
• SHA, o Secure Hash Algorithm, foi desencolvido pelo NIST e pela NSA. Produz um hash de 160 bits, também chamado de message digest.
• RIPE-MD foi desenvolvido para o projeto RACE da Comunidade Européia. Seu algoritmo é uma variação do MD4.
• HAVAL é uma função hash de mão única de tamanho variável inventada por Yulian Zheng, Josef Pieprzyk e Jennifer Seberry. É uma modificação do MD5.

Fontes

• Schneier, Bruce - Applied Cryptography, 1994
• Van Rompay, Bart - Tese "Analysis and Design of Cryptographic Hash Functions, MAC Algorithms and Block Ciphers", Universidade Católica de Leuven.