Rođendanski napad

Rođendanski napad je vrsta kriptografskog napada koji pronalazi kolizije u svakoj hash-funkciji.

Proizašao je iz problema rođendana, problema koji se pojavljuje u teoriji vjerojatnosti, gdje u nasumično odabranoj skupini od n ljudi postoje bar dvoje kojima je rođendan istoga dana. Rođendanski problem, odnosno rođendanski paradoks osnova je proučavanju hash funkcije kojom se definira podudaranje u nekom podatkovnom skupu. Najmanje jednom paru analogna je vjerojatnost poklapanja rođendana vjerojatnosti poklapanja podataka. U ovom problem broj ljudi u skupini predstavlja broj hash elemenata, a broj dana analogan je veličini hash prostora, mjereno u bitovima.

Postoje općeniti i poboljšani rođendanski napad. Općeniti napad pronalazi kolizije u svakoj hash-funkciji, premda u vremenu koje je eksponencijalno duljini ulaznog stringa. Posredno daje minimalnu duljinu ulaza potrebnog da hash-funkcija potencijalno bude sigurna protiv protivnika koji napada kroz odredeno vrijeme. Ovaj napad ne ovisi o ključu. Rođendanski napad radi samo za hash-funkcije otporne na kolizije i nema općenitih napada na hash-funkcije za drugu otpornost na prasliku ili otpornost na prasliku koji imaju vrijeme izvršavanju bolju od 2^l, pri čemu je l duljina u bitovima izlazne duljine stringa hash-funkcije. Mana općenitog rođendanskog napada je što mu treba velika količina memorije i pruža vrlo malo kontrole oko vrijednosti kolizija. Budući da je memorija općenito slabiji resurs od vremena, pa treba vrlo veliki broj računala i dugo vremena za izračunavanje. Napad postaje izvedljiviji ako se smanje zahtjevi za memorijom.

Vidi

• Replay napad
• Pharming