Apa yang Anda pikirkan ketika membaca istilah di atas? Masalah kelahirankah? Masalah yang timbul karena angka kelahiran yang besar di Indonesia? Atau masalah kelahiran terkait dengan tingkat kematian ibu yang tinggi karena resiko meninggal pada saat melahirkan? Ternyata istilah The Birthday Problem yang akan saya bahas berbeda jika anggapan Anda demikian. Masalah ini terkait masalah statistic yang nantinya bisa dimanfaatkan dalam melakukan serangan di kriptografi fungsi hash.
The Birthday Problem adalah masalah yang digunakan untuk melakukan brute force attack pada fungsi hash yang sama dengan exhaustive key search pada algoritma simetrik. Serangan ini juga dapat dibentuk sebagai serangan pada fungsi hash yang menggunakan struktur Merkle Damgard.
Ilustrasinya sebagai berikut : Trudy berada di ruangan yang terdiri dari N orang termasuk dirinya sendiri. Berapa probabilitas minimal satu orang dari N-1 orang selain Trudy mempunyai tanggal lahir yang sama dengan Trudy? Asumsi yang digunakan adalah probabilitas kelahiran dalam satu tahun merupakan probabilitas seragam. Karena asumsi itu, maka untuk menghitung pertanyaan sebelumnya tidak susah untuk dijawab. Seperti pada Discrete Probabiity Problems, lebih mudah untuk menghitung komplemen dan pengurangan dari Discrete Probabiity Problems. Pada kasus ini, komplemen berarti tidak ada diantara N-1 orang selain Trudy yang memiliki taggal lahir yang sama dengan Trudy. Untuk masing-masing orang probabilitasnya adalah jadi untuk N-1 orang, probabilitasnya adalah . Akibatnya, probabilitas yang diinginkan adalah .
Dengan menetapkan persamaan di atas adalah ½ dan menyelesaikan N, maka jumlah orang yang berada di dalam ruangan dapat dihitung sebelum menentukan jumlah orang yang punya tanggal lahir yang sama dengan Trudy. Jika N>253, maka probabilitasnya akan lebih dari ½. Dengan nilai N = 254 merupakan nilai yang beralasan karena nilai itu kurang dari 365. Pada versi ini yang dilakukan yaitu membandingkan tanggal kelahiran dengan satu tanggal kelahiran yakni milik Trudy. Dengan metode ini, maka jika ada M kemungkinan outcome, maka akan dilakukan M pembandingan sebelum menemukan kolisi.
Bagaimana jika yang ingin diketahui adalah probabilitas dalam suatu ruangan 2 orang memiliki tanggal lahir yang sama? Probabilitasnya adalah sebagai berikut : Probabilitas (dua orang dalam suatu ruangan memiliki tanggal lahir yang sama) = 1-(365/35.364/365.363/365. ….365-N+1/365). Nilai N kurang dari sama dengan 366.
Selain itu, dimisalkan bahwa kita akan mencari probabilitas P dimana terdapat dua atau lebih orang memiliki birthday yang sama pada suatu tempat yang di dalamnya terdapat N orang. Lebih mudah lagi menghitung probabilitas komplemennya dan nilai (1-Probabilitas). Komplemen disini maksudnya adalah jumlah orang yang memiliki birthday yang berbeda, maka probabilitas yang diharapkannya yaitu :
1 – 365/365 . 364/365 . 363/365 . . . (365 – N+1)/365 …………………….(1)
dimana N ≤ 366.
Pada kasus ini, untuk menemukan jumlah orang yang berada di tempat tersebut sebelum kita mengharapkan dua atau lebih orang memiliki birthday yang sama, kita tetapkan nilai untuk persamaan (1) menjadi ½ dan mencari solusi untuk N. Dengan begitu, kita temukan bahwa jika N ≥ 23, maka probabilitas persamaan (1) menjadi lebih besar dari ½ . Hal ini memberikan bahwa minimal terdapat 23 orang di sebuah tempat yang nantinya diharapkan terdapat dua atau lebih (orang) membagikan (share) birthday yang sama.
Fakta ini sering dikenal sebagai “birthday paradox” karena pada kilasan pertama, kelihatan paradox yang hanya 23 orang mencukupi selama 365 hari pertahun. Bagaimanapun, hasil ini tidak separadox seperti kelihatannya. Kita membandingkan setiap hari kelahiran dengan hari kelahiran yang lain, sehingga dengan N orang pada suatu ruangan, kita membuat (N/2) perbandingan, dan sewaktu kita telah membuat sekitar 365 perbandingan, kita berharap menemukan satu yang cocok. Dengan logika ini, solusi dari versi birthday problem adalah nilai yang paling kecil dari N seperti (N/2)>365, yang menghasilkan N = 28. ini mendekati nilai tepat N = 23. sebagaimana pendekatan yang sering kita gunakan √M, yang mana M adalah bilangan dari kemungkinan hasil. Untuk hari birthday nyatanya, M= 365 dan kita mempunyai √365 ≈ 19, yang tentu saja merupakan pendekatan yang baik untuk ketepatan hasil N =23.
Sumber : Low M Richard, Stamp Mark. 2007. Applli ed Cryptanalysis Breaking Ciphers in the Real World. A John Wiley & Sons, Inc., Publication. San Jose State University
