Serangan Ulang Tahun & Tumbukan

Dalam kelompok yang terdiri dari 23 orang, probabilitas bahwa dua orang memiliki tanggal ulang tahun yang sama melebihi 50%. Dengan 70 orang, probabilitasnya melebihi 99,9%. Secara matematis: dalam himpunan berukuran N, probabilitas tabrakan melebihi 50% setelah sekitar √N sampel. Inilah batas ulang tahun.

Untuk fungsi hash n-bit: tabrakan (H(m1) = H(m2), m1 ≠ m2) dapat ditemukan dengan sekitar 2^{n/2} percobaan acak. Untuk SHA-256 (256-bit), tabrakan memerlukan sekitar 2^{128} usaha — tidak layak secara komputasi. Untuk MD5 (128-bit), diperlukan sekitar 2^{64} usaha — hampir layak.

Pencarian tabrakan umum: buat 2^{n/2} pesan acak, hitung hash, urutkan berdasarkan nilai hash, lalu cari duplikat. Memori O(2^{n/2}). Algoritme Rho (pencarian siklus Floyd) mengurangi kebutuhan memori menjadi O(1) dengan biaya waktu yang sama. Pencarian tabrakan paralel van Oorschot-Wiener mengurangi waktu dengan bantuan perangkat keras.

Tabrakan praktis MD5 ditemukan oleh Wang dan rekan-rekannya (2004) menggunakan kriptanalisis diferensial — bukan serangan ulang tahun. Dua pesan 1024-bit berbeda dengan hash MD5 identik dapat dibuat dalam hitungan detik. Tabrakan dengan awalan pilihan Hertzbleed memungkinkan terjadinya tabrakan sertifikat. MD5 sepenuhnya tidak aman untuk ketahanan terhadap tabrakan.

Lebih kuat: dengan diberikan dua awalan sembarang P1, P2, temukan akhiran S1, S2 sedemikian rupa sehingga H(P1||S1) = H(P2||S2). Stevens dan rekan-rekannya (2017) menemukan tabrakan MD5 dengan awalan pilihan. Teknik ini digunakan untuk membuat sertifikat CA berbahaya dengan tanda tangan MD5 yang valid. MD5 tidak lagi digunakan untuk sertifikat.

SHAttered milik Google (2017): tabrakan SHA-1 praktis pertama. Dua file PDF berbeda dengan hash SHA-1 yang sama. Diperlukan 2^{63.1} kompresi SHA-1 — setara dengan 6.500 tahun CPU dan 110 tahun GPU. Biayanya sekitar $110.000. Peramban menghentikan dukungan terhadap sertifikat SHA-1 pada 2017.

Untuk fungsi pencincangan Merkle-Damgard (MD5, SHA-1, SHA-2): jika Anda mengetahui H(m), Anda dapat menghitung H(m||padding||m') tanpa mengetahui m. Ini mematahkan konstruksi MAC seperti H(secret||message). Perbaikannya: gunakan HMAC (yang menggunakan pengisi bagian dalam dan luar) atau SHA-3 (konstruksi spons, kebal terhadap perluasan panjang).

Ketahanan terhadap kolisi: menemukan dua pesan berbeda yang memiliki nilai pencincangan sama (usaha 2^{n/2}). Ketahanan terhadap prapeta kedua: dengan m yang diberikan, menemukan m' ≠ m dengan nilai pencincangan sama (usaha 2^n). Ketahanan terhadap prapeta: menemukan pesan apa pun untuk nilai pencincangan tertentu (usaha 2^n). Kolisi selalu merupakan yang paling lemah.

Jika MAC menggunakan fungsi pencincangan yang rentan terhadap kolisi: penyerang yang dapat menemukan kolisi dalam H mungkin dapat memalsukan MAC. HMAC-MD5 dianggap aman meskipun terdapat kolisi MD5 karena konstruksi HMAC memerlukan serangan prapeta, bukan sekadar kolisi. Namun, untuk sistem baru, lakukan migrasi dari HMAC-MD5.

Joux (2004): untuk pencincangan Merkle-Damgard, menemukan kolisi 2^k-arah (2^k pesan dengan nilai pencincangan sama) hanya memerlukan usaha k kali lipat dari menemukan satu kolisi, bukan k kali lipat untuk setiap kolisi. Hal ini memperparah kerentanan pada pencincangan yang digabungkan (H1(m)||H2(m) tidak sekuat yang Anda kira).

Gunakan SHA-256 atau SHA-3 untuk pencincangan yang tahan terhadap kolisi. Hindari MD5 dan SHA-1 untuk tujuan keamanan apa pun. Untuk MAC: HMAC-SHA-256 atau HMAC-SHA-3. Untuk pencincangan kata sandi: Argon2 (bukan SHA-2 secara langsung). Selalu gunakan SHA-3 jika diperlukan ketahanan terhadap perluasan panjang.

Kira-kira berapa banyak evaluasi nilai pencincangan yang diperlukan untuk menemukan kolisi dalam fungsi pencincangan n-bit?

Serangan ulang tahun menemukan kolisi nilai pencincangan dengan usaha 2^{n/2}. MD5 memiliki kolisi awalan pilihan yang praktis; SHA-1 dipatahkan pada 2017. Serangan perluasan panjang mematahkan MAC H(key||msg) yang naif. Gunakan SHA-256 atau SHA-3; gunakan HMAC untuk autentikasi pesan. Berikutnya: serangan temu-di-tengah.