Collisionresistentie

Collisionresistentie is een eigenschap van een cryptografische hashfunctie. Het beschrijft hoe moeilijk het is om twee verschillende invoerberichten x en y te vinden waarvoor x ≠ y en H(x) = H(y). Voor een hashfunctie met outputlengte n bits geldt in de praktijk dat de kans op een gevonden collisie ongeveer 1 op 2^(n/2) is, en dat er, volgens de Birthday paradox, ongeveer 2^(n/2) berekeningen nodig zijn om een collisie te vinden bij een idealiter ontworpen functie.

Collisionresistentie is een van de kernprincipes naast preimage-resistentie en tweede-preimage-resistentie. Preimage-resistentie betekent dat het moeilijk is om een invoer te vinden die correspondeert met een gegeven hashwaarde; tweede-preimage-resistentie houdt in dat het moeilijk is om een tweede invoer te vinden met dezelfde hash als een opgegeven invoer. In de praktijk vertrouwen digitale handtekeningen, integriteitscontroles en vele beveiligingsprotocollen op collisionresistente hashfuncties om voor te planten dat hashwaarden uniek zijn voor verschillende berichten.

Historisch gezien zijn MD5 en SHA-1 kwetsbaar gebleken voor collisiemethoden; MD5 wordt als onveilig beschouwd en SHA-1 wordt voor nieuwe toepassingen niet langer als collision-resistent gezien. Voor moderne toepassingen worden doorgaans hashfuncties uit de SHA-2-familie (bijv. SHA-256, SHA-512) of SHA-3 aanbevolen, omdat daarvoor geen praktische collisiemethoden bekend zijn. Desondanks blijft collisionresistentie sterk afhankelijk van het ontwerp van de hashfunctie; geen enkele methode is volledig onwrikbaar, maar voldoende lange outputlengtes maken collisies zeer onwaarschijnlijk in de praktijk.