terça-feira, 3 de julho de 2007

Nosso Amigo Hash - Parte I

Uma das ferramentas mais úteis para o Investigador/Perito Computacional é o hash. Há diversas situações onde podemos aplicá-lo. Mas o que seria exatamente um hash ???

Hash é uma função matemática com algumas propriedades interessantes. Duas propriedades das mais importantes são:
- Essa função deve ser capaz de receber como entrada um grupo de bits e mapear em um grupo de bits menor
- Deve ter a capacidade de fornecer sempre a mesma saída para a mesma entrada, e uma saída diferente mesmo que apenas um bit seja modificado na entrada
- Não deve ser possível obter a entrada a partir da saída.

Na prática, são usadas funções matemáticas que usem, para qualquer conjunto de bits na entrada, uma quantidade fixa de bits na saída e que, conforme a função, pode ser de 128-bit, 160-bit, 256-bit, 512-bit e 1024-bit. Essa saída é chamada comumente de digest ou resumo.

Os algoritmos de Hash

Há inúmeros algoritmos de hash disponíveis. Cada um implementa uma função matemática com as características acima. Alguns conseguem ter melhor performance, outros oferecem mais segurança ou menos colisão. Falaremos nisso adiante.

MD5 - Ainda é o algoritmo mais usado em Forense Computacional. Tem saída de 128 bits, ou seja, para qualquer entrada ele calcula e retorna uma sequência de 128 bits que "resume" a entrada. Essa entrada pode ser desde um numero, uma letra, uma frase, até arquivos imensos de vários gigabytes.

SHA-1 - É o segundo algoritmo mais utilizado na área de Forense Computacional, e tudo leva a crer que estará substituindo o MD5 no coração dos Investigadores e Peritos Computacionais. Ele fornece uma saída de 160 bits.

Colisão ????

Calma ! Ninguém vai sair machucado dessa colisão !
Como expliquei acima, o hash mapeia uma entrada de qualquer tamanho em uma saída de tamanho fixo, geralmente muitas vezes menor que a entrada. Dessa forma, é possível imaginar que várias possíveis entradas sejam mapeadas para a mesma saída. Por exemplo, se definíssemos uma função de hash chamada A, com finalidade de mapear saídas de, digamos, 4 letras, sendo que o universo de entradas possíveis seriam palavras de 10 letras, com certeza teríamos situações onde a saída abcd seria resultado de entradas como hdjsdteysd, uriwjkdrty e wjdgaalsttd. Ou seja,

A(hdjsdteysd) = abcd
A(uriwjkdrty) = abcd
A(wjdgaalstt) = abcd

Compreendeu ? Várias entradas acarretaram na mesma saída. Isso é uma colisão em um hash.
O algoritmo de hash é melhor quanto menor o número de colisões que ele gera. Gerar um número pequeno de colisões não é algo trivial, já que, diferentemente do nosso exemplo, em funções reais de hash não temos limitação do tamanho da entrada. Ainda assim, colisões em algoritmos profissionais de hash tem baixa frequência.

Aplicações mais comuns de hash

Integridade de arquivos: O hash é comumente usado para constatar que um arquivo está integro. Para isso, usa-se o arquivo como entrada de um algoritmo de hash, e a saída é armazenada. Para testar a integridade do mesmo, basta passar novamente o arquivo pelo algoritmo. A saída deverá ser a mesma, se o arquivo continua inalterado.

Uma variação desse item também frequentemente usada é a comparação de integridade de ambientes. Algumas ferramentas montam um baseline de um grupo de arquivos, registrando em uma base o hash de cada arquivo desse grupo. Periodicamente, esse grupo de arquivos passa novamente pelo algoritmo de hash, e o resultado é comparado com o baseline. Se diferir, houve alteração no grupo. Essa é uma das técnicas usadas por ferramentas de detecção de intrusão em servidores e estações.

Sistemas de autenticação: Quando um sistema precisa autenticar um usuário, ele pede uma conta e uma senha associada. Para evitar trafegar a senha pela rede, a senha original é passada em uma função de hash e esse hash, junto com a conta, é transmitido para o servidor de autenticação, que vai comparar as informações recebidas com as cadastradas em sua base de usuários. Se o hash for o mesmo, é porque a senha digitada pelo usuário é a mesma cadastrada.

Hash é seguro ??? O que é Birthday Attack, ou Ataque do Aniversário ?

Acima comentamos que o hash garante a integridade de um arquivo porque qualquer alteração no mesmo fará com que o hash também seja alterado. Porém, como sabemos que nenhuma função de hash é totalmente desprovida de colisões, o seguinte ataque a essa técnica é realizável:
1) João está celebrando um contrato com José. Ele manda o contrato final para José, onde indica em uma das cláusulas o pagamento combinado de 10000 (dez mil) Reais. Ele manda o resultado do hash do documento, indicando também o algoritmo usado, para Maria, que guarda o hash e atua como uma autenticadora dos contratos.
2) José recebe o documento. Maria executa sobre ele o mesmo algoritmo indicado por João e verifica o resultado, que confere.
3) João, um indivíduo muito mal intencionado, vai no contrato e acrescenta um 0 no valor, ficando com um pagamento de 100000 (cem mil).
4) Logicamente, o hash do documento não vai mais coincidir. O que faz João ? Monta um procedimento automatizado que acrescenta sucessivamente caracteres de espaço no fim do documento. A cada espaço acrescentado, um hash é obtido.
5) Esse processo continua indefinidamente, até que o hash crie uma colisão.
6) Feliz com o resultado, João guarda sua versão do documento, que é diferente mas tem o mesmo hash do documento de José. Agora ele pode reclamar e contar com Maria, que vai autenticar o documento fornecido por ele, pois os hashes coincidem.

Essa técnica de ataque é chamada Ataque do Aniversário por conta de um exercício clássico de análise combinatória e probabilidade, que diz que a probabilidade de haver duas pessoas com a mesma data de aniversário em um universo de 50 pessoas beira 100%, ou seja, é praticamente certo de acontecer.

No próximo post, vamos falar do uso de hashes especificamente em Forense Computacional.

Aguardo comentários e dúvidas,

Até o próximo post !

3 comentários:

Tony Rodrigues disse...

Um amigo observou bem que, logo no início do texto, eu disse algo sobre duas propriedades importantes do hash, mas acabei falando três ...

Foi mal ... ;)

Long Dong disse...

Utilizei um documento simples e um script simples para o "Ataque do Aniversário". Criei o documento.txt somente com a string R$ 10.000,00 e salvei seu Hash MD5. Modifiquei o arquivo para conter R$ 100.000,00 e criei o seguinte script simples:

#!/bin/bash

MD5=$(cat documento.txt.md5 | cut -d " " -f 1)

COUNT=0
DATAHORA=$(date +%d/%m/%Y\ %H:%M:%S)

while [ $MD5 != $(md5sum documento.txt | cut -d " " -f 1 | tee testes.txt) ] ; do
COUNT=$COUNT+1
echo -n " " >> documento.txt
done

DHFIM=$(date +%d/%m/%Y\ %H:%M:%S)
echo "MD5 bate. Necessárias $COUNT tentativas. Inicio as $DATAHORA - Fim as $DHF

Está rodando a 14 horas e ainda não gerou uma colisão, mas o ataque é, realmente, bastante simples de se fazer.

Tony Rodrigues disse...

Excelente, Long Dong.

Por favor, compartilhe aqui os resultados finais !

Obrigado,

Tony