Födelsedagsattack

En födelsedagsattack är en kryptografisk attack som bygger på födelsedagsparadoxen, och utnyttjar den högre sannolikheten för kollisioner vid slumpmässiga attackförsök. Attacken kan användas för att lura en part i kommunikationen att signera ett illasinnat meddelande, till exempel inom PKI, där meddelandenas hashvärde signeras med en publik nyckel.

Attack mot digitala signaturer

Digitala signaturer kan vara föremål för en födelsedagsattack. Ett meddelande $m$ signeras typiskt genom att först beräkna $f(m)$, där $f$ är en kryptografisk hashfunktion, och sedan använda en hemlig nyckel för att signera $f(m)$. Anta att Mallory vill lura Alice att signera ett illasinnat kontrakt. Mallory förbereder ett schyst kontrakt $m$ och ett illasinnat kontrakt ${\textstyle m'}$, och letar därefter upp ställen i både $m$ och ${\textstyle m'}$ som kan ändras utan att innehållet ändras, exempelvis genom att variera skiljetecken, mellanslag och synonymer. Därefter skapar Mallory ett stort antal hashvärden från variationer av $m$ och ${\textstyle m'}$ tills han hittar en version av $m$ respektive ${\textstyle m'}$ som ger samma hashvärde. Mallory ger versionen av det schysta kontraktet $m$ till Alice för signering, och efter att hon signerat det sätter Mallory signaturen på det illasinnade kontraktet ${\textstyle m'}$. Den signaturen "bevisar" att Alice har signerat det illasinnade kontraktet.

För att undvika den här attacken behöver längden på hashvärdet från hashfunktionen vara så stort att födelsedagsattacken blir beräkningsmässigt omöjligt, dvs. ungefär två gånger fler bitar lång än som skulle behövas för att förhindra en vanlig brute force-attack.