Saltar para o conteúdo

Resistência à colisão

Origem: Wikipédia, a enciclopédia livre.

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]

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 [kG(1n), (x1, x2) ← A(k, 1n) st. x1x2 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

[editar | editar código-fonte]

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

[editar | editar código-fonte]

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.

Referências

  1. a b Goldwasser, S.; Bellare, M. "Lecture Notes on Cryptography". Summer course on cryptography, MIT, 1996-2001
  2. a b Pass, R. "Lecture 21: Collision-Resistant Hash Functions and General Digital Signature Scheme". Course on Cryptography, Cornell University, 2009
  3. Xiaoyun Wang; Hongbo Yu. «How to Break MD5 and Other Hash Functions» (PDF). Consultado em 21 de dezembro de 2009. Arquivado do original (PDF) em 21 de maio de 2009 
  4. Xiaoyun Wang; Yiqun Lisa Yin; Hongobo Yu. Finding Collisions in the Full SHA-1 (PDF). CRYPTO 2005. doi:10.1007/11535218_2 
  5. Dodis, Yevgeniy. «Lecture 12 of Introduction to Cryptography» (PDF). Consultado em 3 de janeiro de 2016 , def 1.