APLICAÇÕES DE FUNÇÕES DE HASH CRIPTOGRÁFICAS

Uma função de hash aceita uma mensagem de tamanho variável M como entrada e produz um valor de hash de tamanho fixo h = H(M). Uma “boa” função de hash tem a propriedade de que os resultados da aplicação da função a um grande conjunto de entradas produzirá saídas que são distribuídas por igual e aparentemente de modo aleatório. Em termos gerais, o objeto principal de uma função de hash é a integridade de dados. Uma mudança em qualquer bit ou bits em M resulta, com alta probabilidade, em uma mudança no código de hash. O tipo de função de hash necessária para aplicações de segurança é conhecido como função de hash criptográfica. Ela é um algoritmo para o qual é computacionalmente inviável (pois nenhum ataque é de maneira significativa mais eficiente do que a força bruta) descobrir ou (a) um objeto de dados que seja mapeado para um resultado de hash pré-especificado (a propriedade de mão única) ou (b) dois objetos de dados que sejam mapeados para o mesmo resultado de hash (a propriedade livre de colisão). Por conta dessas características, as funções de hash são usadas com frequência para determinar se os dados mudaram ou não.

A figura “função de hash criptográfica”; h = H(M) representa a operação geral de uma função de hash criptográfica. Normalmente, a entrada é preenchida até um múltiplo inteiro de algum tamanho fixo (por exemplo, 1024 bits), e esse o preenchimento inclui o valor do tamanho da mensagem original em bits. O software de encriptação é relativamente lento. Embora a quantidade de dados a serem encriptados por mensagem seja pequena, pode haver um fluxo constante de mensagens entrando e saindo de um sistema. O software de encriptação é relativamente lento. Embora a quantidade de dados a serem encriptados por mensagem seja pequena, pode haver um fluxo constante de mensagens entrando e saindo de um sistema. O campo de tamanho é uma medida de segurança a fim de aumentar a dificuldade para um invasor produzir uma mensagem alternativa com o mesmo valor de hash.

Começaremos com uma discussão da grande variedade de aplicações para funções de hash criptográficas. Em seguida, examinaremos os requisitos de segurança a tais funções. Depois, verificaremos o uso do cipher block chaining para implementar uma função de hash criptográfica. 

APLICAÇÕES DE FUNÇÕES DE HASH CRIPTOGRÁFICAS

Talvez o algoritmo criptográfico mais versátil seja a função de hash criptográfica. Ela é usada em diversas aplicações de segurança e protocolos da Internet. Para entender melhor alguns dos  requisitos e implicações de segurança para as funções de hash criptográficas, é útil examinar a faixa de aplicações em que elas são empregadas.

Autenticação de mensagem

Autenticação de mensagem é um mecanismo ou serviço usado para verificar a integridade de uma mensagem. Ela garante que os dados recebidos estão exatamente como foram enviados (ou seja, não contêm modificação, inserção, exclusão ou repetição). Em muitos casos, há um requisito de que o mecanismo de autenticação garante que a identidade declarada do emissor é válida. Quando uma função de hash é usada para fornecer autenticação de mensagem, o valor dela é frequentemente chamado de resumo de mensagem.

A essência do uso de uma função de hash para autenticação de mensagem é o seguinte. O emissor calcula um valor de hash como uma função dos bits na mensagem e transmite o valor do hash e a mensagem. O receptor realiza o mesmo cálculo de hash sobre os bits da mensagem e compara esse valor com o valor de hash recebido. Se houver uma divergência, o receptor saberá que a mensagem (ou possivelmente o valor de hash) foi alterada (figura ataque contra função de hash a). A função de hash precisa ser transmitida de forma segura. Ou seja, precisa ser protegida de modo que, se um adversário alterar ou substituir a mensagem, não será viável para ele alterar também o valor de hash para enganar o receptor. Esse tipo de ataque é mostrado na figura ataque contra função de hash b. Neste exemplo, Alice transmite um bloco de dados e anexa um valor de hash. Darth intercepta a mensagem, altera ou substitui o bloco de dados e calcula e anexa um novo valor de hash. Bob recebe os dados alterados com o novo valor de hash e não detecta a mudança. Para impedir esse ataque, o valor de hash gerado por Alice precisa ser protegido.

A figura “Exemplos simplificados do uso de uma função de hash para autenticação de mensagem” ilustra diversas maneiras como um código de hash pode ser usado para fornecer autenticação de mensagem, como a seguir.

1. A mensagem mais o código de hash concatenado são encriptados usando a encriptação simétrica. Como somente A e B compartilham a chave secreta, a mensagem deverá ter vindo de A e sem alteração. O código de hash oferece a estrutura ou redundância exigida para conseguir a autenticação. Como a encriptação é aplicada à mensagem inteira mais o código de hash, a confidencialidade também é fornecida.
2. Somente o código de hash é encriptado, usando a encriptação simétrica. Isso reduz o peso do processamento para as aplicações que não exigem confidencialidade.
3. É possível usar uma função de hash, mas não a encriptação para autenticação de mensagem. A técnica considera que as duas partes se comunicando compartilham um valor secreto comum, S. A calcula o valor de hash sobre a concatenação de M e S, e anexa o valor de hash resultante a M. Como B possui S, ele pode recalcular o valor de hash para verificar. Como o valor secreto em si não é enviado, um oponente não pode modificar uma mensagem interceptada e não pode gerar uma mensagem falsa.
4. A confidencialidade pode ser acrescentada à abordagem do método (c) encriptando a mensagem inteira mais o código de hash.

Quando a confidencialidade não é exigida, o método (b) tem uma vantagem sobre os métodos (a) e (d), que encripta a mensagem inteira, pois menos cálculos são envolvidos. Apesar disso, tem havido um interesse cada vez maior nas técnicas que evitam a encriptação (Figura exemplos simplificados do uso de uma função de hash para autenticação de mensagem c). Vários motivos para esse interesse são indicados em [TSUD92].

• O software de encriptação é relativamente lento. Embora a quantidade de dados a serem encriptados por mensagem seja pequena, pode haver um fluxo constante de mensagens entrando e saindo de um sistema.
• Os custos com hardware de encriptação não são poucos. Existem implementações do DES em chips de baixo custo, mas os custos aumentam se todos os nós em uma rede precisarem ter essa capacidade.
• O hardware de encriptação é otimizado para grandes tamanhos de dados. Para blocos de dados pequenos, uma alta proporção do tempo é gasta no overhead com inicialização/chamada.
• Os algoritmos de encriptação podem ser cobertos por patentes, e há um custo associado ao licenciamento do seu uso.

Normalmente, a autenticação de mensagem é alcançada usando um código de autenticação de mensagem (MAC, do acrônimo em inglês para message authentication code), também conhecido como função de hash chaveada. Normalmente, MACs são usados entre duas partes que compartilham uma chave secreta para autenticar informações trocadas entre elas. Uma função MAC toma como entrada uma chave secreta e um bloco de dados e produz um valor de hash, conhecido como MAC, que é associado à mensagem protegida. Se a integridade da mensagem tiver que ser verificada, a função MAC pode ser aplicada à mensagem e o resultado comparado com o valor MAC associado. Um invasor que altera a mensagem não poderá alterar o valor MAC associado sem conhecer a chave secreta. Observe que a parte que está verificando também sabe quem é a parte emissora, pois ninguém mais conhece a chave secreta.

Observe que a combinação de hashing e encriptação resulta em uma função geral que, na verdade, é um MAC (figura Exemplos simplificados do uso de uma função de hash para autenticação de mensagem b). Ou seja, E(K, H(M)) é uma função de uma mensagem de tamanho variável M e uma chave secreta K, e produz uma saída de tamanho fixo que é protegida contra um oponente que não conhece a chave secreta.

Na prática, são criados algoritmos MAC específicos, que geralmente são mais eficientes do que um algoritmo de encriptação.

Assinaturas Digitais

Outra aplicação importante, similar à aplicação de autenticação de mensagem, é a assinatura digital. A operação da assinatura digital é similar à do MAC. No caso da assinatura digital, o valor de hash da mensagem é encriptado com a chave privada do usuário. Qualquer um que conhecer a chave pública do usuário pode verificar a integridade da mensagem que está associada à assinatura digital. Nesse caso, um invasor que quisesse alterar a mensagem precisaria conhecer a chave privada do usuário.

A figura “Exemplos simplificados de assinaturas digitais” ilustra, de forma simplificada, como o código de hash é usado para oferecer uma assinatura digital.

 

O código de hash é encriptado usando encriptação de chave pública com a chave privada do emissor. Como mostra a figura “Exemplos simplificados de assinaturas digitais b”, isso permite a autenticação. Também oferece uma assinatura digital, porque somente o emissor poderia ter produzido o código de hash encriptado. De fato, essa é a essência da técnica de assinatura digital.

Se, além da assinatura digital, o que se procura é confidencialidade, então a mensagem mais o código hash encriptado com a chave privada pode ser encriptado usando uma chave secreta simétrica. Essa é uma técnica comum.

Outras aplicações

Funções de hash normalmente são usadas para criar um arquivo de senha de mão única. Desse modo, a senha real não pode ser recuperada pelo hacker que conseguir acesso ao arquivo de senhas. De uma forma simples, quando o usuário informa uma senha, por verificação, o hash dela é comparado com o valor do hash armazenado. Esse método de proteção de senha é usado na maioria dos sistemas operacionais.

Funções de hash podem ser usadas para detecção de intrusão e detecção de vírus. Armazene H(F) para cada arquivo em um sistema e guarde de forma segura os valores de hash (por exemplo, em um CD-R mantido em segurança). Posteriormente, será possível determinar se um arquivo foi modificado, recalculando H(F). Um intruso precisaria alterar F sem alterar H(F). Uma função de hash criptográfica pode ser usada para construir uma função pseudoaleatória (PRF) ou gerador de número pseudoaleatório (PRNG). Uma aplicação comum para um PRF baseado em hash é a geração de chaves simétricas.

Duas funções de hash simples

Para ter uma ideia das considerações de segurança envolvidas nas funções de hash criptográficas, nesta seção apresentamos duas funções de hash simples, não seguras. Todas as funções de hash operam usando os seguintes princípios gerais. A entrada (mensagem, arquivo etc.) é vista como uma sequência de blocos de n bits. A entrada é processada um bloco de cada vez, em um padrão iterativo para produzir uma função de hash de n bits. Uma das funções de hash mais simples é o OR exclusivo (XOR) bit a bit de cada bloco. Isso pode ser expresso da seguinte forma:

C_i = b_i1⊕b_i2⊕…⊕b_im

onde:

C_i = i-ésimo bit do código de hash, 1 ≤ i ≤ n
m = número de blocos de n bits na entrada
b_ij = i-ésimo bit no j-ésimo bloco
⊕= operação XOR

Essa operação produz uma paridade simples para cada posição de bit e é conhecida como uma verificação de redundância longitudinal. Ela é razoavelmente eficaz para dados aleatórios como uma verificação de integridade de dados. Cada valor de hash de n bits é igualmente provável. Assim, a probabilidade de que um erro de dados resulte em um valor de hash inalterado é 2^–n. Com dados formatados mais previsivelmente, a função é menos eficaz. Por exemplo, na maioria dos arquivos de texto normais, o bit de alta ordem de cada octeto é sempre zero. Assim, se um valor de hash de 128 bits for usado, em vez de uma eficácia de 2^–128, a função de hash desse tipo de dado possui uma eficácia de 2^–112.

Um modo simples de melhorar as coisas é realizar um deslocamento circular de um bit, ou rotação, sobre o valor de hash após cada bloco ser processado. O procedimento pode ser resumido da seguinte forma:

1. Inicialmente, defina o valor de hash de n bits como zero.
2. Processe cada bloco sucessivo de n bits de dados da seguinte forma:
   1. Gire o valor de hash atual para a esquerda por um bit.
   2. Realize o XOR do bloco com o valor do hash.

Isso tem o efeito de tornar aleatória a entrada de forma mais completa e contornar quaisquer regularidades que apareçam nela. A figura “Duas funções de hash simples” ilustra esses dois tipos de funções de hash para valores de hash de 16 bits.

Embora o segundo procedimento ofereça uma boa medida de integridade de dados, ele é praticamente inútil para segurança de dados quando um código de hash encriptado é usado com uma mensagem de texto claro, como nas figuras Exemplos simplificados do uso de uma função de hash para autenticação de mensagem b e Exemplos simplificados de assinaturas digitais a. Dada uma mensagem, é uma questão fácil produzir uma nova mensagem que gere esse código de hash: simplesmente, prepare a mensagem alternativa desejada e depois anexe um bloco de n bits que force a nova mensagem mais o bloco a produzirem o código de hash desejado. Embora um simples XOR ou XOR relacionado (RXOR) seja insuficiente se somente o código de hash for encriptado, você ainda pode sentir que essa função simples poderia ser útil quando a mensagem e o código de hash estiverem encriptados. Mas é preciso ter cuidado. Uma técnica proposta originalmente pelo National Bureau of Standards usava o simples XOR aplicado a blocos de 64 bits da mensagem e depois uma encriptação da mensagem inteira, que usava o modo cipher block chaining (CBC). Podemos definir o esquema da seguinte forma: dada uma mensagem M consistindo em uma sequência de blocos de 64 bits X₁, X₂, …, X_N, defina o código de hash h = H(M) como o XOR bloco a bloco de todos os blocos e anexe o código de hash como o bloco final:

h = X_N+1 = X₁⊕X₂⊕ … ⊕X_N

Em seguida, encripte a mensagem inteira mais o código de hash, usando o modo CBC para produzir a mensagem encriptada Y₁, Y₂, …, Y_N+1. [JUEN85] aponta várias maneiras de o texto cifrado dessa mensagem ser manipulado de modo que não seja detectável pelo código de hash. Por exemplo, temos

X₁ = IV ⊕ D(K, Y₁)
X_i = Y_i–1 – D(K, Y_i)
X_N+1 = Y_N ⊕ D(K, Y_N+1)

Mas X_N+1 é o código de hash:

X_N+1 = X₁ ⊕ X₂ ⊕ … ⊕ X_N= [IV ⊕ D(K, Y₁)] ⊕ [Y₁ ⊕ D(K, Y₂)] ⊕ … ⊕ [Y_N–1 ⊕ D(K, Y_N)]

Como os termos na equação anterior podem ser XOR dados em qualquer ordem, segue-se que o código de hash não mudaria se os blocos de texto cifrado fossem permutados.

Requisitos e segurança

Antes de continuarmos, precisamos definir dois termos. Para um valor de hash h = H(x), dizemos que x é a pré-imagem de h. Isso significa que x é um bloco de dados cuja função hash, usando a função H, é h. Como  H é um mapa de muitos-para-um, para qualquer valor de hash h informado, de forma geral existirão várias pré-imagens. Uma colisão ocorre se tivermos x ≠ y e H(x) = H(y). Como estamos usando funções de hash para integridade dos dados, as colisões claramente são indesejáveis.

Vamos considerar quantas pré-imagens existem para um dado valor de hash, o que nos indica a quantidade de potenciais colisões para um dado valor de hash. Suponha que o tamanho do código de hash é de n bits e a função H recebe como entrada mensagens ou blocos de dados com b bits de tamanho e b > n. O total de mensagens possíveis, então, é 2^b e o total de possíveis valores de hash é 2ⁿ. Em média, cada valor de hash corresponde a 2^b–n pré-imagens. Se H tende a distribuir de modo uniforme os valores de hash, então, de fato cada valor de hash possuirá um valor próximo de 2^b–n pré-imagens. Se permitirmos entradas de qualquer tamanho, e não apenas um comprimento fixo de um certo número de bits, então a variação no número de pré-imagens por valor de hash será grande. No entanto, os riscos de segurança no uso de funções de hash não são tão graves quanto aparentam ser a partir dessa análise. Para compreender melhor as implicações em termos de segurança das funções de hash criptográficas, precisamos definir precisamente seus requisitos de segurança.

Requisitos de segurança para funções de hash criptográficas

A tabela “Requisitos para função de hash criptográfica H” lista os requisitos geralmente aceitos para uma função de hash criptográfica. As primeiras três propriedades são requisitos para a aplicação prática de uma função de hash.

A quarta propriedade, resistência à pré-imagem, é a propriedade de mão única: é fácil gerar um código a partir da mensagem, mas é praticamente impossível gerar uma mensagem dado o seu código. Essa propriedade é importante se a técnica de autenticação envolve o uso de um valor secreto. O valor secreto em si não é enviado. No entanto, se uma função de hash não possui essa propriedade de mão única, um invasor pode facilmente descobrir o valor secreto: se o invasor pode observar ou interceptar uma transmissão, o invasor obtém a mensagem M e o código de hash h=H(S||M). O invasor então inverte a função de hash para obter S||M=H^–1 (MD_M). Como o invasor possui tanto M quanto S_AB|| M, torna-se fácil recuperar S_AB.

A quinta propriedade, resistência à segunda pré-imagem, garante que é impossível encontrar uma mensagem alternativa com o mesmo valor de hash de uma determinada mensagem. Funciona como prevenção contra a falsificação quando for usado um hash encriptado. Se essa propriedade não fosse verdadeira, um invasor seria capaz da seguinte sequência: inicialmente observar ou interceptar uma mensagem com seu código de hash encriptado. Em seguida, gerar um código de hash decriptado de uma mensagem e, finalmente, gerar outra mensagem diferente com o mesmo código de hash.

Uma função de hash que satisfaz as primeiras cinco propriedades da tabela “Requisitos para função de hash criptográfica H” é conhecida como uma função hash fraca. Se possuir também a sexta propriedade, resistência à colisão, então ela será chamada de uma função de hash forte, que protege contra um ataque onde uma terceira parte gera uma mensagem para outra parte assinar. Por exemplo, suponha que Bob escreve uma mensagem IOU, envia-a para Alice e ela a assina. Bob encontra duas mensagens com o mesmo hash, uma solicitando que Alice pague uma pequena quantia, e outra que ela pague uma quantia grande. Alice assina a primeira mensagem e Bob, então, pode alegar que a segunda mensagem é a autêntica.

A figura “Relação entre as propriedades das funções de hash” mostra o relacionamento entre as três propriedades de resistência. Uma função que é resistente à colisão também é resistente à segunda pré-imagem, mas o inverso não é necessariamente verdadeiro. Uma função pode ser resistente à colisão, mas não ser resistente à pré-imagem, e vice-versa. Uma função pode ser resistente à pré-imagem, mas não ser resistente à segunda pré-imagem e vice-versa. Veja uma discussão mais aprofundada a respeito em [MENE97].

A tabela “Propriedades de resistência necessárias para várias aplicações de integridade de dados” mostra as propriedades de resistência necessárias para várias aplicações de funções de hash. O requisito final na tabela “Requisitos para função de hash criptográfica H”, a pseudoaleatoriedade, não tem sido tradicionalmente citado como um requisito de funções de hash criptográficas, porém ela fica mais ou menos implícita. [JOHN05] aponta que funções de hash criptográficas normalmente são usadas para derivação de chave e geração de número pseudoaleatório e, além disso, aponta também que, nas aplicações de integridade de mensagens, as três propriedades de resistência dependem da saída da função de hash aparentar ser aleatória. Sendo assim, faz sentido dizer que uma função de hash produz uma saída pseudoaleatória.

Ataques de força bruta

Como nos algoritmos de encriptação, existem duas categorias de ataques em funções de hash: ataques de força bruta e criptoanálises. Um ataque de força bruta não depende do algoritmo específico, mas somente do tamanho em bits. No caso de uma função de hash, um ataque de força bruta depende somente do tamanho do valor de hash em bits. Uma criptoanálise, ao contrário, é um ataque baseado nos pontos fracos de um algoritmo criptográfico em particular. Primeiro, vejamos os ataques de força bruta.

A taques de pré – imagem e segunda pré – imagem

Para um ataque de pré-imagem ou segunda pré-imagem, um adversário deseja achar um valor y tal que H(y) seja igual a um dado valor de hash h. O método da força bruta é apanhar valores de y aleatoriamente e experimentar cada um deles até que haja uma colisão. Para um valor de hash de m bits, o nível de esforço é proporcional a 2^m. Especificamente, o adversário teria que experimentar, na média, 2^m–1 valores de y para achar um que gere determinado valor de hash h.

A taques resistentes à colisão

Para um ataque resistente à colisão, um adversário deseja encontrar duas mensagens ou blocos de dados, x e y, que geram a mesma função de hash: H(x) = H(y). Acontece que isso gera muito menos esforço do que um ataque de pré-imagem ou segunda pré-imagem. O esforço exigido é explicado por um resultado matemático conhecido como paradoxo do dia do aniversário. Basicamente, se escolhermos variáveis aleatórias a partir de uma distribuição uniforme no intervalo de 0 a N–1, então a probabilidade de que um elemento repetido seja encontrado é superior a 0,5 após √N escolhas terem sido feitas. Assim, para um valor de hash de m bits, se escolhermos blocos de dados aleatoriamente, poderemos descobrir dois blocos de dados com o mesmo valor de hash dentro de √2^m = 2^m/2 tentativas.

Yuval propôs a seguinte estratégia para explorar o paradoxo do dia do aniversário em um ataque resistente à colisão [YUVA79].

1. A origem, A, é preparada para assinar uma mensagem legítima x anexando o código de hash apropriado de m bits e encriptando esse código de hash com a chave privada de A (figura “exemplos simplificados de assinaturas digitais a”).
2. O oponente gera 2^m/2 variações x’ de x, todas transmitindo basicamente o mesmo significado, e armazena as mensagens e seus valores de hash.
3. O oponente prepara uma mensagem fraudulenta y para a qual a assinatura de A é desejada.
4. O oponente gera pequenas variações y’ de y, todas transmitindo basicamente o mesmo significado. Para cada y’, o oponente calcula H(y’), verifica as combinações com qualquer um dos valores de H(x’) e continua até que seja encontrada uma correspondência. Ou seja, o processo continua até que um y’ seja gerado com um valor de hash igual ao valor de hash de um dos valores x’.
5. O oponente oferece a variação válida de A para assinatura. Essa assinatura pode então ser anexada à variação fraudulenta para transmissão ao destinatário intencionado. Como as duas variações têm o mesmo código de hash, elas produzirão a mesma assinatura; o oponente tem garantia de sucesso, embora a chave de encriptação não seja conhecida.

Assim, se for usado um código de hash de 64 bits, o nível de esforço exigido é apenas algo na ordem de 2³².

A criação de muitas variações que transmitem o mesmo significado não é difícil. Por exemplo, o oponente poderia inserir uma série de pares de caracteres “espaço-espaço-retrocesso” entre as palavras por todo o documento. As variações poderiam então ser geradas substituindo “espaço-retrocesso-espaço” em ocorrências selecionadas. Como alternativa, o oponente poderia simplesmente reescrever a mensagem, mas retendo o mesmo significado. A figura “uma carta em 2³⁸ variações” contém um exemplo. Resumindo, para um código de hash de tamanho m, o nível de esforço exigido, conforme vimos, é proporcional ao seguinte:

Se a resistência à colisão for exigida (e isso é desejável para um código de hash seguro de uso geral), então o valor 2^m/2 determina a força do código de hash contra os ataques por força bruta. Van Oorschot e Wiener [VANO94] apresentaram um projeto para uma máquina de busca de colisão de US$ 10 milhões para MD5, que tem um tamanho de hash de 128 bits, que poderia encontrar uma colisão em 24 dias. Assim, um código de 128 bits pode ser visto como inadequado. O próximo passo à frente, se um código de hash for tratado como uma sequência de 32 bits, é um tamanho de hash de 160 bits. Com um tamanho de hash de 160 bits, a mesma máquina de busca exigiria mais de quatro mil anos para encontrar uma colisão. Com a tecnologia atual, o tempo seria muito mais curto, de modo que 160 bits agora parece ser suspeito.

Criptoanálise

Assim como nos algoritmos de encriptação, os ataques criptoanalíticos sobre funções de hash e algoritmos MAC buscam explorar alguma propriedade do algoritmo para realizar algum ataque diferente de uma busca por exaustão. A maneira de medir a resistência de um hash ou algoritmo MAC à criptoanálise é comparar sua força com o esforço exigido para um ataque por força bruta. Ou seja, um algoritmo de hash ou MAC ideal exigirá um esforço criptoanalítico maior ou igual ao esforço por força bruta.

Nos últimos anos, tem havido um esforço considerável, e alguns sucessos, no desenvolvimento de ataques criptoanalíticos sobre funções de hash. Para entendê-los, precisamos examinar a estrutura geral de uma típica função de hash segura, indicada na figura “Estrutura geral do código de hash seguro”. Essa estrutura, conhecida como função de hash iterativa, foi proposta por Merkle [MERK79, MERK89] e é a estrutura da maioria das funções de hash em uso atualmente, incluindo SHA. A função de hash recebe uma mensagem de entrada e a divide em L blocos de tamanho fixo com b bits cada. Se for preciso, o bloco final é preenchido para ter b bits. O bloco final também inclui o valor do tamanho total da entrada para a função de hash. A inclusão do tamanho torna o trabalho do oponente mais difícil. Ou o oponente precisa encontrar duas mensagens de mesmo tamanho que gerem um hash com o mesmo valor ou duas mensagens de tamanhos diferentes que, junto com seus valores de tamanho, gerem um hash com o mesmo valor.

O algoritmo de hash envolve o uso repetido de uma função de compactação, f, que utiliza duas entradas (uma entrada de n bits da etapa anterior, chamada variável de encadeamento, e um bloco de b bits), e produz uma saída de n bits. No início do hashing, a variável de encadeamento tem um valor inicial que é especificado como parte do algoritmo. O valor final da variável de encadeamento é o valor de hash. Normalmente, b > n; daí o termo compactação. A função de hash pode ser resumida da seguinte forma:

CV₀ = IV = valor inicial de n bits
CV_i = f(CV_i–1, Y_i–1)1 ≤ i ≤ L
H(M) = CV_L

onde a entrada da função de hash é uma mensagem M consistindo nos blocos Y₀, Y₁, …, Y_L–1.

A motivação para essa estrutura iterativa vem da observação por Merkle [MERK89] e Damgard [DAMG89] de que, se a função de compactação for à prova de colisão, então o mesmo acontece com a função de hash iterativa resultante (A recíproca não é necessariamente verdadeira).  Portanto, a estrutura pode ser usada para produzir uma função de hash segura para operar sobre uma mensagem de qualquer tamanho. O problema de projetar uma função de hash segura se reduz a projetar uma função de compactação à prova de colisão que opere sobre entradas de algum tamanho fixo.

A criptoanálise de funções de hash focaliza a estrutura interna de f e é baseada nas tentativas de encontrar técnicas eficientes para produzir colisões para uma única execução de f. Quando isso for feito, o ataque deverá levar em consideração o valor fixo do IV. O ataque sobre f depende da exploração de sua estrutura interna. Normalmente, assim como para cifras de bloco simétricas, f consiste em uma série de rodadas de processamento, de modo que o ataque envolve a análise do padrão de mudanças de bit de uma rodada para outra.

Lembre-se de que, para qualquer função de hash, é preciso haver colisões, pois estamos relacionando uma mensagem de tamanho pelo menos igual ao dobro do tamanho de bloco b (porque precisamos anexar um campo contendo o tamanho) a um código de hash de tamanho n, onde b ≥ n. O que é preciso é que seja computacionalmente inviável encontrar colisões.

Os ataques que foram montados sobre funções de hash são um tanto complexos e além do nosso escopo aqui. Para o leitor interessado, [DOBB96] e [BELL97] são recomendados.

Funções de Hash Baseadas em Cipher Block Chaining

Diversas propostas foram feitas para as funções de hash com base no uso de uma técnica de cipher block chaining, mas sem a chave secreta. Uma dessas primeiras propostas foi a de Rabin [RABI78]. Divida uma mensagem M em blocos de tamanho fixo M₁, M₂, …, M_N e use um sistema de encriptação simétrica, como DES, para calcular o código de hash G da seguinte forma:

H₀ = valor inicial
H_i = E(M_i, H_i–1)
G = H_N

Isso é semelhante à técnica CBC, mas neste caso não existe chave secreta. Assim como em qualquer código de hash, esse esquema está sujeito ao ataque de dia do aniversário, e se o algoritmo de encriptação for o DES e apenas um código de hash de 64 bits for produzido, então o sistema é vulnerável.

Além disso, outra versão do ataque de dia do aniversário pode ser usada mesmo que o oponente tenha acesso a apenas uma mensagem e sua assinatura válida, e não possa obter várias assinaturas. Aqui está o cenário; consideramos que o oponente intercepte uma mensagem com uma assinatura na forma de um código de hash encriptado e que o código de hash não encriptado tenha m bits de extensão:

1. Use o algoritmo definido no início desta subseção para calcular o código de hash não encriptado G.
2. Construa qualquer mensagem desejada na forma Q₁, Q₂, …, Q_N–2.
3. Calcule H_i = E(Q_i, H_i–1) para 1 ≤ i ≤ (N–2).
4. Gere 2^m/2 blocos aleatórios; para cada bloco X, calcule E(X, H_N-2). Gere 2^m/2 blocos aleatórios adicionais; para cada bloco Y, calcule D(Y, G), onde D é a função de decriptação correspondente a E.
5. Com base no paradoxo do dia do aniversário, com alta probabilidade, haverá um X e Y tais que E(X, H_N–2) = D(Y, G).
6. Forme a mensagem Q₁, Q₂, …, Q_N–2, X, Y. Essa mensagem tem o código de hash G e, portanto, pode ser usada com a assinatura encriptada interceptada.

Essa forma de ataque é conhecida como ataque meet-in-the-middle. Diversos pesquisadores propuseram melhorias com a finalidade de fortalecer a técnica básica de cipher block chaining. Por exemplo, Davies e Price [DAVI89] descrevem a seguinte variação:

Hi = E(M_i, H_i–1) ⊕ H_i–1

Outra variação, proposta em [MEYE88], é

H_i = E(H_i–1, M_i) ⊕ M_i

Porém esses dois esquemas têm se mostrado vulneráveis a uma série de ataques [MIYA90]. Em geral, pode-se mostrar que alguma forma de ataque de dia do aniversário terá sucesso contra qualquer esquema de hash envolvendo o uso de cipher block chaining sem uma chave secreta, desde que o código de hash resultante seja pequeno o suficiente (por exemplo, 64 bits ou menos) ou que um código de hash maior possa ser decomposto em subcódigos independentes [JUEN87].

Assim, é preciso dar atenção à descoberta de outras técnicas para o hashing. Muitas delas também possuem pontos fracos [MITC92].

Secure Hash Algorithm (SHA)

Em anos recentes, a função de hash mais utilizada tem sido o Secure Hash Algorithm (SHA). Na realidade, como praticamente todas as outras funções de hash mais usadas tiveram vulnerabilidades criptoanalíticas substanciais, SHA era mais ou menos o último algoritmo de hash padronizado restante em 2005. O SHA foi desenvolvido pelo National Institute of Standards and Technology (NIST) e publicado como um padrão de processamento de informações federais (FIPS 180) em 1993. Quando foram descobertos pontos fracos no SHA, agora conhecido como SHA-0, uma versão revisada foi lançada como FIPS 180-1 em 1995 e geralmente é chamada de SHA-1. O documento de padrões real é intitulado Secure Hash Standard. SHA é baseado na função de hash MD4 e seu projeto modela de perto a MD4.

SHA-1 produz um valor de hash de 160 bits. Em 2002, o NIST produziu uma versão revisada do padrão, FIPS 180-2, que definiu três novas versões do SHA, com tamanhos de valor de hash de 256, 384 e 512 bits, conhecidas como SHA-256, SHA-384 e SHA-512, respectivamente. Coletivamente, esses algoritmos de hash são conhecidos como SHA-2. Essas novas versões têm a mesma estrutura básica e usam os mesmos tipos de aritmética modular e operações binárias lógicas do SHA-1. Um documento revisado foi emitido como FIP PUB 180-3 em 2008, acrescentando uma versão de 224 bits (tabela “Comparação de parâmetros do SHa”). SHA-1 e SHA-2 também são especificados no RFC 6234, que basicamente duplica o material no FIPS 180-3, mas acrescenta uma implementação em código C.

Em 2005, o NIST anunciou a intenção de retirar a aprovação do SHA-1 e passar a contar com o SHA-2 por volta de 2010. Pouco tempo depois, uma equipe de pesquisa descreveu um ataque em que duas mensagens separadas poderiam oferecer o mesmo hash SHA-1 usando 2⁶⁹ operações, muito menos do que as 2⁸⁰ operações que anteriormente se achou necessárias para encontrar uma colisão com um hash SHA-1 [WANG05]. Esse resultado deverá apressar a transição para o SHA-2. Nesta seção, oferecemos uma descrição do SHA-512. As outras versões são muito semelhantes.

Lógica do SHA-512

O algoritmo recebe como entrada uma mensagem com um tamanho máximo de menos de 2¹²⁸ bits e produz como saída um resumo da mensagem de 512 bits. A entrada é processada em blocos de 1024 bits. A figura “geração de resumo da mensagem usando SHA-512” representa o processamento geral de uma mensagem para produzir um resumo. Este segue a estrutura geral representada na figura “Estrutura geral do código de hash seguro.”. O processamento consiste nas seguintes etapas:

Etapa 1 – Anexar bits de preenchimento. A mensagem é preenchida de modo que seu tamanho seja congruente a 896 módulo 1024 [tamanho ≡ 896 (mod 1024)]. O preenchimento sempre é acrescentado, mesmo que a mensagem já tenha o tamanho desejado. Assim, o número de bits de preenchimento está no intervalo de 1 a 1024. O preenchimento consiste em um único bit 1 seguido pelo número necessário de bits 0.

Etapa 2 – Anexar tamanho. Um bloco de 128 bits é anexado à mensagem. Esse bloco é tratado como um inteiro de 128 bits não sinalizado (byte mais significativo primeiro) e contém o tamanho da mensagem original (antes do preenchimento).

O resultado das duas primeiras etapas produz uma mensagem que é um múltiplo inteiro de 1024 bits de extensão. Na figura Geração de resumo da mensagem usando SHA-512., a mensagem expandida é representada como uma sequência de blocos de 1024 bits M₁, M₂, …, M_N, de modo que o tamanho total da mensagem expandida é N × 1024 bits.

Etapa 3 – Inicializar buffer de hash. Um buffer de 512 bits é usado para manter resultados intermediários e finais da função de hash. O buffer pode ser representado como oito registradores de 64 bits (a, b, c, d, e, f, g, h). Esses registradores são inicializados com os seguintes inteiros de 64 bits (valores hexadecimais):

Esses valores são armazenados no formato big-endian, que é o byte mais significativo de uma word na posição de byte de endereço baixo (mais à esquerda). Essas words foram obtidas apanhando- se os primeiros sessenta e quatro bits das partes fracionárias das raízes quadradas dos oito primeiros números primos.

Etapa 4 – Processar mensagem em blocos de 1024 bits (128 word). O núcleo do algoritmo é um módulo que consiste em 80 rodadas; esse módulo é rotulado com F na figura “Geração de resumo da mensagem usando SHA-512”. A lógica é ilustrada na figura “Processamento SHa-512 de um único bloco de 1024 bits”. Cada rodada recebe como entrada o buffer de 512 bits abcdefgh, e atualiza o conteúdo do buffer. Na entrada da primeira rodada, o buffer contém o valor do hash intermediário, H_i–1. Cada rodada t utiliza um valor de 64 bits W_t, derivado do bloco atual de 1024 bits sendo processado (M_i). Esses valores são derivados usando-se um schedule de mensagem descrito mais adiante. Cada rodada também utiliza uma constante aditiva K_t, onde 0 ≤ t ≤ 79 indica uma das 80 rodadas. Essas words representam os primeiros 64 bits das partes fracionárias das raízes cúbicas dos 80 primeiros números primos. As constantes oferecem um conjunto de padrões de 64 bits aleatórios, o que deverá eliminar quaisquer regularidades nos dados da entrada. A tabela “Constantes do SHa-512” mostra essas constantes em formato hexadecimal (da esquerda para a direita).

A saída da octogésima rodada é somada à entrada da primeira rodada (H_i–1) para produzir H_i. A adição é feita independentemente para cada uma das oito words no buffer com cada uma das words correspondentes em H_i–1, usando a adição módulo 2⁶⁴.

Etapa 5 – Saída. Depois que todos os N blocos de 1024 bits tiverem sido processados, a saída do estágio N é o resumo de mensagem de 512 bits.

Podemos resumir o comportamento do SHA-512 da seguinte forma:

H₀ = IV
H_i = SUM₆₄(H_i–1, abcdefgh_i)
MD = H_N

onde:

IV = valor inicial do buffer abcdefgh, definido na etapa 3

abcdefgh_i = a saída da última rodada de processamento do i-ésimo bloco de mensagem

N = o número de blocos na mensagem (incluindo campos de preenchimento e tamanho)

SUM₆₄ = adição módulo 2⁶⁴ realizada separadamente em cada word do par de entradas

MD = valor final do resumo da mensagem

Fim da aula