# 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).$^{: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.$^{: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 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$_1$, x$_2$) produzindo o mesmo valor de hash h$_k$(x$_1$) = h$_k$(x$_2$), onde x$_1$é diferente de x$_2$, é extremamente baixa. É possível expressar matematicamente:
Prob [k ← G(1$^n$), (x$_1$, x$_2$) ← A(k, 1$^n$) st. x$_1$ ≠ x$_2$ porém h$_k$(x$_1$) = h$_k$(x$_2$)] < 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.