Resistência à colisão

Na criptografia, a resistência à colisão representa uma propriedade fundamental das funções hash criptográficas. Uma função hash H é considerada resistente à colisão se for computacionalmente inviável encontrar duas entradas distintas que gerem o mesmo valor de hash, ou seja, duas entradas a e b onde a ≠ b, mas H(a) = H(b). O princípio da casa de pombos sugere que em funções hash com mais entradas do que saídas, colisões são inevitáveis. No entanto, a segurança da função aumenta à medida que encontrar tais colisões se torna mais desafiador.

O "paradoxo do aniversário" estabelece um limite superior para a resistência à colisão: se uma função hash produz N bits de saída, um atacante que execute apenas 2^N/2 (ou $\scriptstyle {\sqrt {2^{N}}}$) operações hash em entradas aleatórias tem uma alta probabilidade de encontrar duas saídas correspondentes. Se houver um método mais eficiente do que a força bruta para realizar essa tarefa, geralmente é considerado uma vulnerabilidade na função hash.

Embora as funções hash criptográficas sejam tipicamente projetadas com a intenção de serem resistentes a colisões, várias delas que anteriormente eram consideradas seguras foram subsequentemente comprometidas. Exemplos notáveis incluem o MD5 e o SHA-1, nos quais foram descobertas técnicas mais eficazes do que a abordagem de força bruta para encontrar colisões. No entanto, algumas funções hash possuem uma prova de que encontrar colisões é tão difícil quanto resolver um problema matemático extremamente desafiador, como a fatoração de inteiros ou o logaritmo discreto. Essas funções são denominadas "comprovadamente seguras".

Definição

Uma família de funções {h _k : {0, 1}^m(k) → {0, 1}^l(k)} é considerada uma família de funções hash resistentes a colisões se satisfazer as seguintes condições:

• Compressão de Entrada: A função h _k comprime a string de entrada de acordo com as especificações, onde |m(k)| representa o tamanho da entrada e |l(k)| representa o tamanho da saída para qualquer valor de k. Assim, é necessário que |m(k)| > |l(k)| para qualquer k.
• Eficiência Computacional: Cada h _k na família de funções pode ser calculado em tempo polinomial, levando em consideração o valor de k.
• Improbabilidade de Colisões: Para qualquer algoritmo polinomial probabilístico A, a probabilidade de encontrar um par de entradas distintas (x₁, x₂) produzindo o mesmo valor de hash h_k(x₁) = h_k(x₂), onde x₁é diferente de x₂, é extremamente baixa. É possível expressar matematicamente:

Prob [k ← G(1ⁿ), (x₁, x₂) ← A(k, 1ⁿ) st. x₁ ≠ x₂ porém h_k(x₁) = h_k(x₂)] < f(n),

Em que f(·) denota uma função que cresce de forma tão insignificante conforme o parâmetro de segurança n aumenta que pode ser considerada negligenciável.

Em resumo, essa definição estabelece que, para uma função hash ser considerada resistente a colisões, ela precisa comprimir eficientemente as entradas, ser calculável em tempo razoável e tornar praticamente improvável encontrar duas entradas diferentes que gerem o mesmo valor de hash.

Resistência à colisão fraca e forte

Existem dois principais tipos de resistência à colisão em funções hash.

Uma função hash é considerada ter resistência à colisão fraca quando, dado um valor específico x, não é possível encontrar outro valor x' de forma que a função hash H produza o mesmo resultado para ambos, ou seja, H(x) = H(x'). Em termos simples, a resistência à colisão fraca se concentra em encontrar colisões para um valor fixo de entrada.

Por outro lado, uma função hash demonstra resistência à colisão forte quando é impossível encontrar dois valores arbitrários distintos, x e x', que produzam o mesmo resultado de hash, ou seja, H(x) = H(x'). Em outras palavras, não é possível encontrar duas entradas diferentes que colidam, independentemente do par de valores escolhido.

A resistência à colisão forte vai além da resistência à colisão fraca, assegurando que não seja possível encontrar dois valores quaisquer que gerem o mesmo hash, garantindo assim a unicidade do hash para todos os possíveis pares de inputs.

Em resumo, a resistência à colisão fraca trata da impossibilidade de encontrar uma colisão para um valor fixo de entrada, enquanto a resistência à colisão forte vai além, impedindo a existência de colisões para quaisquer pares distintos de entradas.

Justificativa

A importância da resistência à colisão é fundamental em inúmeros contextos de segurança e integridade de dados. Suas aplicações abrangem uma variedade de sistemas e protocolos, e sua presença é crucial por várias razões, como:

• Assinaturas Digitais e Integridade de Documentos:

Em sistemas de assinatura digital, uma entidade autentica um documento ao publicar uma assinatura de public key em um hash do documento. Se torna possível produzir dois documentos diferentes com o mesmo hash, um intruso poderia manipular uma entidade a assinar um documento, enquanto alega que a assinatura foi feita em outro. A resistência à colisão impede essa possibilidade, garantindo a integridade dos dados assinados e a autenticidade das assinaturas.

• Verificação de Integridade em Sistemas Distribuídos:

Em sistemas de conteúdo distribuído, como redes peer-to-peer ou distribuição de arquivos, os usuários comparam hashes criptográficos de arquivos para garantir que possuam a mesma versão do conteúdo. Se um intruso conseguisse produzir dois arquivos distintos com o mesmo hash, seria possível induzir os usuários a acreditarem que possuem a mesma versão de um arquivo, quando, na realidade, não têm. A resistência à colisão é crucial para garantir a integridade e autenticidade dos arquivos distribuídos, evitando assim falsificações.

Ver também

• Ataque de pré-imagem
• Detecção e correção de erros