Från Rilpedia

En födelsedagsattack är en kryptografisk attack som bygger på födelsedagsparadoxen. Typiska tillämpningar är inom PKI, där meddelandenas hashvärde signeras med en publik nyckel.

Attackens struktur

Hashfunktioner är i praktiken envägsfunktioner som tar ett meddelande av godtycklig längd och beräknar ett kondenserat värde, en identitet, utifrån N möjliga värden. Attacken går ut på att ersätta det ursprungliga signerade meddelandet med ett illasinnat meddelande som attackeraren väljer fritt. Om dessa två meddelanden har samma kondensvärde, så kommer en kryptografisk signatur för originalmeddelandet vara giltigt även för det illasinnade meddelandet.

Envägsnaturen hos hashfunktioner leder till attackeraren behöver variera det illasinnade meddelandet ett stort antal gånger för att få samma kondensvärde för båda meddelandena. Skiljetecken, mellanslag och variationer i formuleringar kan varieras in absurdum. Attackeraren behöver göra maximalt N variationer, men i genomsnitt räcker det med N/2 st.

Födelsedagsattacken består i att attackeraren kan modifiera båda meddelandena. I så fall kommer attackeraren att hitta meddelanden med samma hashvärde inom ca N^0.5 variationer. Han låter sedan offret signera det oskyldiga meddelandet och tar tillvara på offrets signatur av det. Han kan sedan använda samma signatur på det illasinnade meddelandet, och få det att se ut som om offret har signerat det. Detta med en betydligt lägre arbetsinsats än vad offret har förväntat sig.