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).[1]:136 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.[1]:136 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 2N/2 (ou 
) 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.[2]
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.[3][4] 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".[2]
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 (x1, x2) produzindo o mesmo valor de hash hk(x1) = hk(x2), onde x1é diferente de x2, é extremamente baixa. É possível expressar matematicamente:
Prob [k ← G(1n), (x1, x2) ← A(k, 1n) st. x1 ≠ x2 porém hk(x1) = hk(x2)] < 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.[5]
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
Referências
