Rođendanski napad

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

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.[2]

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 2l, 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.[1]

Izvori

uredi
  1. a b Nacionalni repozitorij završnih i diplomskih radova ZIR - Nacionalna i sveučilišna knjižnica u Zagrebu Mirjana Horvat / Dugine tablice / Prirodoslovno-matematički fakultet u Zagrebu / Zagreb / 2018.
  2. Portal hrvatskih znanstvenih i stručnih časopisa - Hrčak Josipa Matotek, Ivanka Stipančić-Klaić / Rođendanski paradoks / Poučak, 18 (2017), 70