Serangan Ulang Tahun dalam Kriptografi
Apa itu Kriptografi?
Kriptografi adalah metodologi di mana kita mengubah informasi menjadi kode khusus yang hanya dapat dipahami oleh pengirim dan penerima. Alasan penggunaan kriptografi adalah untuk melindungi data dari serangan keamanan siber.
Kriptografi terdiri dari dua kata: ‘crypt’, yang berarti tersembunyi, dan ‘graphy’ yang berarti tulisan. Jadi, kita menulis informasi dalam bentuk tersembunyi untuk melindunginya dari kerentanan dan serangan.
Ada berbagai jenis serangan keamanan siber, dan serangan brute force adalah salah satu serangan keamanan siber yang umum.
Apa itu Serangan Brute Force?
Serangan brute force adalah serangan di mana peretas mencoba mendapatkan email, kata sandi, dan kunci enkripsi melalui berbagai metode.
Apa itu Serangan Ulang Tahun?
Serangan ulang tahun adalah jenis serangan kriptografi yang termasuk dalam kategori serangan brute force. Serangan ini digunakan untuk mengeksploitasi matematika dari masalah teori probabilitas standar yang disebut masalah paradoks ulang tahun. Keberhasilan serangan ini berbanding lurus dengan jumlah tabrakan antara serangan-serangan tersebut, yang bersifat acak dan derajat permutasi.
Masalah Paradoks Ulang Tahun
Pernyataan masalahnya mengatakan, misalnya kita memiliki kelas dengan N siswa dan satu guru di kelas. Guru ingin mengetahui jumlah pasangan siswa yang memiliki ulang tahun pada tanggal yang sama. Untuk mendapatkan solusi ini, dia meminta tanggal lahir dari setiap siswa dan menemukan jumlah pasangannya.
Misalkan dia memilih satu tanggal acak, seperti 5 November, dan ingin mengetahui probabilitas bahwa setidaknya satu siswa memiliki ulang tahun pada tanggal 5 November. Untuk ini, dia akan menggunakan teori probabilitas, dan dia akan mendapatkan probabilitas bahwa tidak ada siswa yang memiliki ulang tahun pada tanggal 5 November, lalu menguranginya dari 1 untuk mendapatkan hasil yang diinginkan.
Misalkan jumlah siswa adalah 30, jadi N = 30
Probabilitas setidaknya satu siswa memiliki ulang tahun pada 5 November = 1 – (364/365)³⁰ = 0,079 atau 7,9%.
Probabilitas bahwa setidaknya satu siswa memiliki ulang tahun pada tanggal yang sama dengan siswa lain = 1 – 365! / ((365-n!)*(365)ⁿ) di mana n = 30 dan nilainya akan sekitar 0,7 atau 70%.
Penjelasan
Dalam solusi di atas, kita menurunkan rumus untuk N siswa bahwa setidaknya dua siswa memiliki ulang tahun pada tanggal yang sama.
Kita bisa menurunkannya dengan mencatat bahwa tidak ada yang memiliki ulang tahun pada tanggal yang sama dan menguranginya dari 1 untuk mendapatkan hasil yang diinginkan.
(365/365) * (364/365) * (363/365) * … * (365-n+1)/365 = 365! / ((365-n!)*(365)ⁿ)
Dan hasil yang diinginkan = 1 – 365! / ((365-n!)*(365)ⁿ)
Fungsi Hash
Fungsi hash dalam kriptografi adalah fungsi yang mengambil input dengan ukuran variabel dan mengembalikan hasil sebagai string yang memiliki panjang tetap. String output disebut nilai hash dari input.
Itu diwakili oleh H.
Hasil h = H(X) di mana x adalah input.
Dalam kriptografi, fungsi hash harus memenuhi batasan berikut:
- Variabel input dari fungsi harus berukuran variabel.
- Variabel output selalu berukuran tetap.
- Untuk setiap input X, H(X) mudah dihitung.
- H(X) harus bebas tabrakan.
- H(X) adalah fungsi satu arah.
Fungsi Hash Satu Arah
Untuk setiap input X, kita mendapatkan nilai output Y melalui fungsi H(X).
Jadi Y = H(X).
Jika kita diberikan Y, dan kita dapat menemukan fungsi hash H di mana H(X) = Y, maka fungsi ini disebut dua arah atau dapat dibalik. Jadi, dalam kriptografi, fungsi hash kita harus non-dapat dibalik, yang berarti tidak mungkin mendapatkan fungsi hash H dengan output Y. Fungsi ini harus sulit untuk dibalik.
Fungsi Hash Bebas Tabrakan
Jika untuk input X, output dari fungsi hash adalah H(X) dan jika memungkinkan bahwa X tidak sama dengan Y tetapi H(X) = H(Y), maka fungsi hash saat ini disebut fungsi hash lemah bebas tabrakan.
Jika untuk setiap input X, tidak mungkin menemukan Y sehingga X tidak sama dengan Y dan H(X) = H(Y), maka ini disebut fungsi kuat bebas tabrakan.
Kita bisa memahaminya dengan contoh:
Contoh:
Misalkan fungsi hash H: M = {0,1}ⁿ untuk |M| >> 2ⁿ
Jadi, kita akan menggunakan langkah-langkah berikut untuk menemukan tabrakan:
- Kita akan memilih pesan acak sebagai input m1, m2, …
- Untuk setiap mi, hitung output ti di mana i = 1, 2, 3, …
- Kita akan memeriksa tabrakan jika ti = tj, dan jika tidak ditemukan, kita akan mengulangi proses ini.
Kompleksitas Waktu:
Kompleksitas waktu dari algoritma di atas adalah O(2ⁿ/2).
//TC
