Funções de hash criptográficas

Nesta lição vamos estudar as funções de hash criptográficas, que são amplamente utilizadas para validação rápida e autenticação.

Ao final da lição, teremos abordado:

• O que são funções de hash criptográficas
• Exemplos de código Python demonstrando o uso de funções de hash
• Uma análise das aplicações do hashing criptográfico
• A segurança do hashing criptográfico
• Ameaças a esses algoritmos tanto por computadores clássicos quanto quânticos

Introdução ao hashing criptográfico

As funções de hash representam uma construção valiosa na criptografia, pois ajudam a habilitar validação com confidencialidade. Como tal, as funções de hash formam um componente importante de mecanismos para autenticação e integridade de dados, como códigos de autenticação de mensagem baseados em hash (HMAC) e assinaturas digitais. Este artigo vai discutir as ideias básicas e considerações de segurança que fundamentam as funções de hash criptográficas e delinear possíveis vulnerabilidades decorrentes do advento da computação quântica.

Motivação básica e design das funções de hash

Existem muitas situações em que a autenticação e a verificação de integridade precisam ser realizadas de forma barata e sem revelar informações privadas à parte que realiza a validação.

Por exemplo, ao baixar software de um servidor remoto, é necessário um mecanismo eficiente para verificar se o software realmente baixado não foi modificado desde que foi criado pelo autor original do software. Da mesma forma, ao autenticar usuários de aplicações web, seria desejável usar um mecanismo que não envolva o armazenamento físico ou a transmissão das senhas reais, o que pode potencialmente comprometer sua confidencialidade.

As funções de hash criptográficas (CHFs) atendem a essas necessidades de forma eficiente e segura.

Fundamentalmente, uma função de hash criptográfica recebe uma entrada (ou mensagem) de comprimento arbitrário e retorna uma string de n bits de tamanho fixo como saída. A saída de uma CHF também é chamada de digest. Uma CHF útil deve satisfazer várias propriedades-chave:

1. Uniformidade: Os digests produzidos por uma CHF devem ser distribuídos uniformemente e devem parecer aleatórios. O objetivo é garantir que a saída não vaze informações sobre a entrada.
2. Determinismo: Para uma determinada entrada, uma CHF deve sempre produzir o mesmo digest, ou seja, deve ser determinística.
3. Irreversibilidade: Uma CHF é uma função unidirecional, no sentido de que, dado um digest, deve ser inviável inverter o hashing e obter a entrada.
4. Injetividade aproximada: Embora as CHFs sejam funções muitos-para-um, elas devem parecer funções um-para-um. Isso é alcançado combinando um enorme tamanho do espaço de saída com o efeito de avalanche, pelo qual pequenas mudanças na entrada levam a digests muito divergentes. Esta característica é conhecida como injetividade aproximada.

Dado isso, é possível validar um dado contra a instância original comparando um digest dos dados com um digest do original.

• Se os dois digests coincidirem, podemos ter alta confiança de que os dados são idênticos ao original.
• Se os digests diferirem, podemos ter certeza de que os dados foram adulterados ou são de outra forma inautênticos.

Como os próprios digests de CHF não revelam o conteúdo real dos dados ou do original, eles permitem validação enquanto preservam a privacidade.

Mathematical description

Uma função de hash $H$ pode ser definida como:

$H : Σ^* \rightarrow \{0,1\}^n$

onde $Σ^*$ é o conjunto de todas as strings possíveis que podemos considerar como strings binárias de qualquer comprimento.

O fato de que o tamanho do domínio de entrada $Σ^*$ de $H$ é ilimitado enquanto o do codomínio $\{0,1\}^n$ é limitado significa que $H$ é necessariamente um mapeamento muitos-para-um, mapeando infinitas entradas para qualquer string de n bits.

As propriedades de uniformidade e determinismo são bem encapsuladas dentro do modelo de oráculo aleatório do hashing criptográfico.

Exemplo de hashing criptográfico em Python com SHA-256

Este exemplo simples demonstra hashing criptográfico usando o popular algoritmo SHA-256 fornecido pela biblioteca Python cryptography. Primeiro mostramos como uma pequena diferença em textos simples leva a uma diferença muito grande nos digests de hash.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

# Begin by importing some necessary modules
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import hashes

# Helper function that returns the number of characters different in two strings
def char_diff(str1, str2):
    return sum(str1[i] != str2[i] for i in range(len(str1)))

# Messages to be hashed
message_1 = b"Buy 10000 shares of WXYZ stock now!"
message_2 = b"Buy 10000 shares of VXYZ stock now!"

print(f"The two messages differ by { char_diff(message_1, message_2)} characters")

The two messages differ by 1 characters

As duas mensagens diferem em exatamente um caractere.

Em seguida, instanciamos objetos hash para habilitar o processo de hashing, que envolve chamadas a dois métodos: update e finalize.

Vemos que, devido ao efeito de avalanche na CHF SHA-256, uma diferença de um caractere nas mensagens de entrada produz dois digests muito diferentes.

# Create new SHA-256 hash objects, one for each message
chf_1 = hashes.Hash(hashes.SHA256(), backend=default_backend())
chf_2 = hashes.Hash(hashes.SHA256(), backend=default_backend())

# Update each hash object with the bytes of the corresponding message
chf_1.update(message_1)
chf_2.update(message_2)

# Finalize the hash process and obtain the digests
digest_1 = chf_1.finalize()
digest_2 = chf_2.finalize()

# Convert the resulting hash to hexadecimal strings for convenient printing
digest_1_str = digest_1.hex()
digest_2_str = digest_2.hex()

# Print out the digests as strings
print(f"digest-1: {digest_1_str}")
print(f"digest-2: {digest_2_str}")

print(f"The two digests differ by { char_diff(digest_1_str, digest_2_str)} characters")

digest-1: 6e0e6261b7131bd80ffdb2a4d42f9d042636350e45e184b92fcbcc9646eaf1e7
digest-2: 6b0abb368c3a1730f935b68105e3f3ae7fd43d7e786d3ed3503dbb45c74ada46
The two digests differ by 57 characters

Aplicações do hashing criptográfico

As propriedades únicas das CHFs as tornam adequadas para uma ampla gama de aplicações:

• Verificações de integridade de dados: As funções de hash podem ser usadas para criar um checksum para um conjunto de dados. Quaisquer modificações nos dados, intencionais ou não, resultarão em um checksum diferente, alertando sistemas ou usuários para a mudança. O checksum também é tipicamente muito mais compacto do que os dados originais, o que torna as comparações de checksum muito rápidas.

Figura 1. Hashing seguro para integridade de dados

• Assinaturas digitais: Os hashes criptográficos são essenciais para o funcionamento das assinaturas digitais, pois envolvem a comparação de mensagens com hash criptográfico para estabelecer autenticidade e integridade enquanto preservam a privacidade.

Figura 2. Assinaturas digitais

• Blockchain e criptomoedas: Criptomoedas como o Bitcoin dependem muito das CHFs, particularmente na criação de integridade de transações e na habilitação de mecanismos de consenso como a prova de trabalho.

Segurança do hashing criptográfico

A segurança de uma CHF é tipicamente avaliada com base na resistência a dois tipos de ataques: pré-imagem e colisão.

Resistência à pré-imagem

A resistência à pré-imagem significa que, dado um digest, deve ser inviável encontrar a entrada.

Isso está relacionado à propriedade unidirecional das CHFs.

Uma boa CHF é projetada de tal forma que uma parte que deseja conduzir um ataque de pré-imagem não tem opção melhor do que uma abordagem de força bruta, que tem complexidade de tempo $2^n$.

mathematical details

Dado uma CHF $H$ e um digest $g$, deve ser computacionalmente inviável encontrar qualquer entrada $m$ da pré-imagem de $g$ onde $H(m) = g$.

Resistência à colisão

A resistência à colisão significa que é difícil encontrar duas entradas diferentes que tenham hash para o mesmo digest.

Uma colisão de hash criptográfico ocorre quando duas entradas têm hash para o mesmo digest. Embora as colisões existam inevitavelmente dado a natureza muitos-para-um das CHFs, uma boa CHF torna inviável localizar uma deliberadamente.

A resistência à colisão é crucial para aplicações como assinaturas digitais e certificados, onde poderia ser desastroso se uma parte maliciosa fosse capaz de criar uma falsificação com hash para o mesmo valor.

mathematical details of hash collisions

$m_1, m_2$ podem ser encontrados de tal forma que $H(m_1) = H(m_2)$.

Comprimento do hash

A resistência à colisão é um requisito mais rigoroso do que a resistência à pré-imagem e necessita de comprimentos de saída duas vezes mais longos do que os necessários para a resistência à pré-imagem. Isso ocorre porque um ataque de força bruta conhecido como ataque de aniversário, que pode ser usado para identificar colisões de hash, tem complexidade de tempo $2^{n/2}$.

Na ausência de fraquezas criptanalíticas, a segurança de uma função de hash é portanto primariamente influenciada pelo seu comprimento de hash. Quanto mais longo o hash, mais seguro ele é, pois fica mais difícil montar ataques de força bruta.

Funções de hash criptográficas comumente usadas

A tabela a seguir lista algumas funções de hash criptográficas comumente usadas, juntamente com seus comprimentos de hash e domínios de aplicação primários:

Função de hash	Comprimento de saída (bits)	Aplicações comuns
MD5	128	Verificação de integridade de arquivos, sistemas legados, usos não criptográficos
SHA-1	160	Sistemas legados, Git para controle de versão
SHA-256	256	Criptomoeda (Bitcoin), assinaturas digitais, certificados
SHA-3	Variável (até 512)	Várias aplicações criptográficas, sucessor do SHA-2
Blake2	Variável (até 512)	Criptografia, substituindo MD5/SHA-1 em alguns sistemas
Blake3	Variável (até 256)	Criptografia, hash de arquivos, integridade de dados

• MD5 e SHA-1, embora ainda vistos em aplicações menos sensíveis, são considerados obsoletos em termos de resistência à colisão e não são recomendados para novos sistemas. O SHA-256, parte da família SHA-2, é amplamente usado e atualmente seguro para a maioria das aplicações.
• O SHA-3 é um padrão mais recente que foi selecionado pelo NIST em 2015 como vencedor da competição de funções de hash do NIST. Foi projetado para ser um substituto direto do SHA-2, mas também possui algumas características internas diferentes e é resistente a certos tipos de ataques que podem ser eficazes contra o SHA-2.
• Blake2 e Blake3 são funções de hash criptográficas mais rápidas do que MD5, SHA-1, SHA-2 e SHA-3, mas pelo menos tão seguras quanto o padrão mais recente, SHA-3. Estão sendo cada vez mais usados em novos sistemas, particularmente onde a velocidade é importante.

Riscos quânticos ao hashing criptográfico tradicional

A principal ameaça quântica ao hashing criptográfico é representada pelos ataques de força bruta.

Dado um digest específico, um atacante vai tentar entradas aleatórias até localizar uma que produza o mesmo digest.

Com $n$ bits na entrada, há $2^n$ valores possíveis. Portanto, o atacante precisa tentar cerca de $2^{n-1}$ entradas para ter uma chance maior que 50% de sucesso.

Algoritmo de Grover

Para tal contexto de busca não estruturada, o algoritmo de Grover pode fornecer uma aceleração quadrática usando uma técnica conhecida como amplificação de amplitude quântica, reduzindo a complexidade de tempo de um ataque de pré-imagem para $2^{n/2}$.

Em termos práticos, isso significa que uma CHF de 256 bits, que atualmente é considerada segura contra ataques de pré-imagem por computadores clássicos, forneceria o mesmo nível de segurança que uma CHF de 128 bits quando confrontada com um atacante quântico utilizando o algoritmo de Grover.

O algoritmo de Grover por si só não é conhecido por fornecer acelerações quânticas adicionais com relação a ataques de colisão além do limite estabelecido pelo ataque de aniversário, que pode ser realizado em computadores clássicos. Como o ataque de aniversário clássico já exige que as CHFs empregem comprimentos de hash que são duas vezes mais longos do que o necessário para resistência à pré-imagem, o fato de que a busca de Grover efetivamente reduz pela metade o comprimento do hash com relação a ataques de pré-imagem não representa uma ameaça prática.

Por exemplo, no caso do SHA-256, realizar na ordem de $2^{128}$ operações para executar um ataque de pré-imagem assistido por Grover ainda seria inviável no futuro previsível.

Algoritmo BHT

Um algoritmo quântico que combina aspectos do ataque de aniversário com a busca de Grover foi proposto em 1997 por Brassard, Høyer e Tapp (BHT) e proporciona um escalonamento teórico de $O(2^{n/3})$ para encontrar colisões de hash. No entanto, esse escalonamento melhorado é condicionado à existência de tecnologia de memória de acesso aleatório quântico QRAM, que atualmente não existe.

Sem QRAM, o escalonamento realizável é $\tilde{O}(2^{2n/5})$ e para os comprimentos de hash atualmente em uso, essa melhoria marginal na capacidade de encontrar colisões em relação ao ataque de aniversário não representa uma ameaça crítica.

Resumo

As funções de hash criptográficas são um componente essencial para garantir integridade de dados e privacidade em sistemas de informação digital, e encontram aplicação generalizada em muitos contextos.

Os requisitos de segurança das CHFs são principalmente entendidos em termos de sua resistência a ataques de pré-imagem e colisão. Para CHFs bem projetadas, o comprimento do hash é um bom indicador do nível de segurança.

Embora o advento de computadores quânticos executando os algoritmos de Grover e BHT afete teoricamente a resistência à pré-imagem e à colisão das CHFs tradicionais, os longos comprimentos de hash já em uso hoje significa que os algoritmos de hashing criptográfico modernos, como o SHA-3, provavelmente permanecerão seguros, salvo a descoberta de ataques criptanalíticos ainda desconhecidos.

A relevância das CHFs reside em seu papel como um bloco de construção fundamental para esquemas criptográficos resistentes a quantum, garantindo que as informações digitais permaneçam seguras mesmo diante de potenciais avanços futuros em algoritmos e tecnologias de computação quântica.