Criptografia Numaboa

As funções hash

Ter

Set

2005

00:44

(34 votos, média 4.24 de 5)

Detalhes: Categoria: Funções Hash; Atualização: Quarta, 22 Abril 2009 11:05; Autor: vovó Vicki; Acessos: 26029

Funções hash são funções que recebem dados de comprimento arbitrário, comprimem estes dados e devolvem um número fixo de bits, o resultado hash. Se uma função deste tipo satisfizer requisitos adicionais, ela pode ser usada em aplicações criptográficas como, por exemplo, proteger a autenticidade de mensagens enviadas através de canais inseguros. A idéia básica é que o resultado hash forneça uma identidade única para uma mensagem e que a proteção de uma pequena identidade é mais fácil de ser obtida do que a proteção da mensagem como um todo.

Os códigos de autenticação de mensagens (MAC - message authentication codes) têm relação com as funções hash. Estes também são funções que comprimem uma entrada de comprimento arbitrário num número fixo de bits, mas o processo depende de uma entrada secundária de comprimento fixo, a chave. É por este motivo que os MACs também são chamados de funções hash com chave. Em aplicações práticas, a chave que orienta os cálculos de um MAC precisa ser mantida em segredo.

Funções hash criptográficas

Para uma função (sem chave) hash, o requisito para que o resultado hash sirva como identidade única para uma mensagem é que seja impossível ou impraticável encontrar pares de mensagens que colidam (isto é, mensagens que produzam hashs iguais). Em algumas aplicações, no entanto, é suficiente que, para cada resultado hash, seja impraticável encontrar a mensagem correspondente; ou que, dada uma mensagem, seja impraticável encontrar outra mensagem que produza o mesmo hash. De acordo com estas premissas, existem duas definições informais para dois tipos diferentes de funções hash.

Um hash de mão única (one way hash) é uma função que satisfaz as seguintes condições:

A entrada X pode ter um comprimento arbitrário e o resultado h(X) possui um número fixo de n bits.
Dados h e um input X, o cálculo de h(X) precisa ser 'fácil'.
A função precisa ser de mão única, ou seja, para um dado Y na imagem de h, seja 'difícil' achar uma mensagem X de modo que h(X) = Y (resistência de preimagem) e, dados X e h(X), seja 'difícil' encontrar uma mensagem X' diferente de X onde h(X') = h(X) (resistência da segunda preimagem).

Uma função hash resistente a colisões é uma função h que satisfaz as seguintes condições:

A entrada X pode ter um comprimento arbitrário e o resultado h(X) possui um número fixo de n bits.
Dados h e um input X, o cálculo de h(X) é 'fácil'.
A função é de mão única, isto é, é resistente à preimagem e à segunda preimagem.
A função precisa ser resistente a colisões: isto significa que é 'difícil' encontrar duas mensagens distintas que produzam o mesmo resultado hash.

Num código de autenticação de mensagem MAC, o cálculo (portanto, o resultado MAC) depende de uma entrada secundária, a chave secreta. O propósito principal é que o adversário, sem conhecer esta chave, não seja capaz de forjar o resultado MAC de qualquer mensagem, mesmo se muitas mensagens e seus MACs correspondentes forem conhecidos. Um código de autenticação de mensagem ou MAC é uma função h que satisfaz as seguintes condições:

A entrada X pode ter um comprimento arbitrário e o resultado h(K,X) possui um comprimento fixo de n bits. A função possui como entrada secundária uma chave K com um número fixo de k bits.
Dados h, K e uma entrada X, o cálculo de h(K,X) precisa ser 'fácil'.
Dada uma mensagem X (mas com K desconhecido), o cálculo de h(K,X) precisa ser 'difícil'.

Aplicações de funções hash e de MACs

Funções hash e MACs têm as mais diversas aplicações. Entre outras, podem ser utilizadas na autenticação de mensagens, assinaturas digitais, datação (timestamping) de documentos e sistemas de senhas.

Autenticação de mensagens com hash

O problema da proteção da autenticidade de informações tem dois aspectos: a integridade dos dados e a autenticação da origem dos dados. A integridade dos dados é a garantia de que os dados não tenham sido alterados, sem autorização, desde o momento em que foram criados, transmitidos ou armazenados por uma fonte autorizada. Já a autenticação da origem dos dados é um tipo de autenticação que garante a fonte (origem) dos dados. Por definição, a autenticação da origem dos dados inclui a integridade dos dados (informação que tenha sido modificada com autorização tem uma nova fonte).

Digamos que um remetente queira enviar uma mensagem para determinado destinatário através de um canal de comunicação inseguro. Para garantir que o destinatário esteja recebendo a mensagem da fonte correta e que a mensagem não foi modificada durante a transmissão, o remetente cria um hash da mensagem e transmite esta pequena sequência de bits através de um canal autêntico. Um canal autêntico não é necessariamente um canal seguro, ele pode ser interceptado e o segredo não é garantido. O telefone, por exemplo, é um canal deste tipo onde a autenticação é feita através do reconhecimento da voz. Depois disso, o remetente pode enviar a mensagem através de um canal inseguro. O destinatário, por sua vez, usando o mesmo algoritmo hash, cria um resultado hash para a mensagem recebida e o compara com o hash que lhe foi enviado. Se os dois hashes coincidirem, o destinatário tem a certeza de que a mensagem não foi alterada durante o trajeto.

Autenticação hash combinada com criptografia

Uma outra forma de enviar mensagens autenticadas é adicionar o hash à mensagem clara e cifrar o conjunto com algum método criptográfico cuja chave seja conhecida tanto pelo remetente quanto pelo destinatário. O destinatário decifra o conjunto, obtendo o hash e a mensagem. Este método precisa de um canal autêntico e com privacidade para poder transmitir a chave do método criptográfico.

Autenticação de mensagens com MAC

Neste caso, o remetente cria um resultado MAC usando uma chave. Depois, adiciona este MAC à mensagem e a envia através de um canal inseguro. Também aqui existe a necessidade de usar um canal autêntico e com privacidade para transmitir a chave do algoritmo MAC.

Otimização de assinaturas digitais

Esquemas de assinatura digital são um tipo diferente de primitivo criptográfico. São usados para a proteção da autenticidade, só que, adicionalmente, oferecem o serviço de não repúdio. Isto significa que é impossível para um remetente negar a autoria de uma mensagem autenticada. Assinaturas digitais baseiam-se em criptografia de chave pública.

Por exemplo, o usuário A possui o par de chaves SA e PA, onde SA é a chave privada (secreta) e PA é a chave pública. Inicialmente ele comprime sua mensagem M com a função hash h. O resultado hash h(M) é usado como entrada do algoritmo de assinatura. Este algoritmo depende da chave privada SA e calcula um valor assinatura_SA( h(M) ), que pode ser expresso como s(M). O usuário associa a assinatura s(M) à mensagem M e envia o conjunto através de um canal inseguro. O destinatário separa a assinatura s(M) e a usa como entrada do algoritmo de verificação. Este algoritmo depende da chave pública PA e calcula o valor ver_PA( s(M) ). A assinatura e o algoritmo de verificação são projetados de tal forma que, se o par de chaves PA e SA estiver correto, o resultado hash h(M) corresponde à mensagem M. O destinatário calcula o hash da mensagem, compara os dois hashes e, se coincidirem, tanto a assinatura, quanto a mensagem, são autênticas.

Aplicações como funções de mão única (one-way)

Funções de mão única são parecidas com as funções hash de mão única - a diferença é que a entrada tem um comprimento fixo. Estas funções podem ser obtidas de vários modos, por exemplo, a partir de funções hash criptográficas ou de cifras de bloco.

Nos sistemas de identificação baseados em senhas, ao invés de armazenar a senha, armazena-se para cada usuário o resultado de uma função de mão única. Para verificar se uma senha informada pelo usuário (identificação) está correta, o sistema aplica a função de mão única na senha fornecida e compara o resultado obtido com o resultado armazenado.

Uma outra aplicação, também muito útil para identificações, é a chamada confirmação de conhecimento. Neste caso, as partes provam que conhecem um segredo S sem revelar o segredo. Para isto, basta cada um enviar para o outro uma função de mão única de S.

Funções de mão única também podem ser aplicadas para calcular uma sequência de chaves que são usadas para proteger sessões de comunicação sucessivas. Começando com uma chave mestra K0, a chave da primeira sessão é calculada como K1 = f(K0), a da segunda sessão como K2 = f(K1) e assim sucessivamente. Um exemplo típico é a derivação de chaves usada em sistemas de pagamento em terminais de pontos de venda onde a divulgação de uma chave atualmente ativa não pode comprometer a segurança de transações anteriores. Esta propriedade é chamada de segurança futura. Outro exemplo é a geração de senhas num sistema de senhas de uso único. Neste caso, cria-se uma sequência de senhas que serão usadas na ordem inversa da criação. Aplicando-se a função de mão única a uma das senhas, o resultado precisa coincidir com a senha anterior. A propriedade de mão única impede que um adversário, que conheça a senha atual, possa calcular qualquer uma das senhas futuras.

Datação digital

A datação digital é um serviço que fornece uma autenticação temporal. Em particular, uma datação digital fornece provas da existência de certos fragmentos de informação antes da data e da hora indicada na datação. Isto tem aplicação na proteção de direitos de propriedade intelectual e em procedimentos seguros de auditoria. Por exemplo:

Um pesquisador que queira provar um "primeiro a inventar" ou "primeiro a informar".
Uma empresa que queira provar a integridade de seus registros eletrônicos, mostrando que estes não foram manipulados ou tiveram suas datas alteradas.

A datação também é vital para serviços de não-repúdio confiáveis. Em documentos assinados que tenham um ciclo de validade longo, várias verificações podem ser necessárias. Entretanto, o ciclo de validade de assinaturas digitais é limitado por várias razões:

A chave privada da assinatura pode se tornar comprometida.
O certificado que prova o elo entre o usuário e sua chave pública tem prazo de validade.
O algoritmo criptográfico usado no esquema da assinatura pode ser quebrado.

Estes problema pode ser contornado se um serviço seguro de datação for utilizado. Um usuário que cria uma assinatura num documento e requisita uma datação da informação assinada prova que a assinatura foi gerada antes da marca temporal indicada na datação, ou seja, antes de qualquer incidente eventualmente venha a invalidar a sua assinatura.

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 sad

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:

Gerar o valor hash de uma mensagem, usando uma função hash de mão única.
Concatenar a mensagem e o hash obtido.
Gerar um novo hash da mensagem com o hash concatenado.
Criar um valor hash maior que consiste da valor hash gerado na etapa 1 concatenado ao hash gerado na etapa 3.
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.