Resistência à colisão
De Wikipedia, a enciclopédia encyclopedia
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]