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:

1. A entrada X pode ter um comprimento arbitrário e o resultado h(X) possui um número fixo de n bits.
2. Dados h e um input X, o cálculo de h(X) precisa ser 'fácil'.
3. 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:

1. A entrada X pode ter um comprimento arbitrário e o resultado h(X) possui um número fixo de n bits.
2. Dados h e um input X, o cálculo de h(X) é 'fácil'.
3. A função é de mão única, isto é, é resistente à preimagem e à segunda preimagem.
4. 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:

1. 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.
2. Dados h, K e uma entrada X, o cálculo de h(K,X) precisa ser 'fácil'.
3. Dada uma mensagem X (mas com K desconhecido), o cálculo de h(K,X) precisa ser 'difícil'.