Hash Collision

Apa itu Hash Collision?

Hash Collision adalah ketika dua input berbeda menghasilkan output hash yang persis sama. Bayangkan dua kunci berbeda yang entah bagaimana membuka kunci digital yang sama. Jarang terjadi, tetapi jika itu terjadi pada algoritma yang salah, bisa berbahaya.

Bagaimana Hash Collision bekerja

Anggap hash sebagai label kecil untuk data besar. Berikut ringkasan singkat dari input sampai masalah.

1. Input: Anda mulai dengan pesan, berkas, atau transaksi apa pun.
2. Hash: Fungsi dari keluarga fungsi hash kriptografi mengubah input itu menjadi string dengan panjang tetap.
3. Clash: Karena output terbatas sementara input tidak terbatas, dua input berbeda dapat memetakan ke output yang sama.
4. Attack: Ancaman serius muncul jika seseorang dapat sengaja membuat dua input berbeda yang saling bertabrakan, lalu menukar satu dengan yang lain.
5. Defense: Algoritma yang baik membuat pencarian itu sangat mahal secara komputasi, sehingga menebak secara acak menghabiskan waktu dan uang.

Ya, begitulah idenya.

Mengapa Hash Collision penting

Mengapa Anda harus memperhatikan sudut tenang matematika dan kode ini?

• Manfaat: Ketahanan yang kuat menjaga label data tetap unik, sehingga menyulitkan trik licik.
• Perspektif: Collision mengancam integritas untuk hal seperti teknologi blockchain, pembaruan perangkat lunak, dan verifikasi berkas.
• Relevansi: Anda akan menemukannya di dompet, bursa, bukti, dan alat audit yang mempercayai kesetaraan hash.

Ciri Utama Hash Collision

Apa yang membuat fenomena ini istimewa dan layak dicatat:

• Inevitable: Dengan output terbatas dan input tanpa batas, beberapa pasangan akan bertabrakan karena prinsip pigeonhole.
• Hard: Untuk hash modern, menemukan collision secara sengaja dirancang agar sangat sulit secara komputasi.
• Signatures: Banyak tanda tangan digital menandatangani hash, jadi ketahanan terhadap collision melindungi penandatangan dari pesan tipuan.

Bagaimana Hash Collision dihitung?

Anda dapat memperkirakan usaha dengan konsep birthday. Untuk hash k bit, jumlah percobaan acak yang dibutuhkan agar peluang sekitar lima puluh persen terjadi collision kira kira adalah akar kuadrat dari dua pangkat k, dikalikan sekitar 1,1774.

n_fifty_percent ≈ 1.1774 * sqrt(2^k)

Contoh: dengan k sama dengan 256, jumlah percobaan yang diperlukan sangat besar, itulah mengapa mencoba memaksa collision melalui brute force bukanlah pekerjaan akhir pekan.

Variasi

Berbagai varian muncul dalam riset dan serangan:

• Collision: Dua input berbeda berbagi hash yang sama.
• Second: Diberi satu input, temukan input lain yang menghasilkan hash yang sama.
• Preimage: Diberi sebuah hash, temukan input apa pun yang memetakannya.
• Prefix: Chosen prefix collision membuat dua pesan dengan awalan terpilih berbeda yang berakhir dengan hash yang sama.

Contoh

Jika penyerang bisa membuat dua transaksi berbeda dengan txid yang sama, mereka mungkin mencoba trik Double Spending dengan menukar duplikat setelah Anda menandatangani.

Fakta Menarik

Collision pada MD5 sudah ditunjukkan puluhan tahun lalu, dan proyek SHAttered menghasilkan collision publik untuk SHA1 dengan dua PDF berbeda, sebuah momen yang mendorong industri untuk menghentikan penggunaannya.

Kesimpulan

Singkatnya, Hash Collision adalah kasus langka di mana dua input berbeda berbagi satu sidik digital, dan kripto modern bekerja keras agar itu tetap sekadar informasi sepele.