Sifat dan Fungsi Hash
Seperti yang sudah disinggung sebelumnya, bahwa fungsi hash kriptografi ini sudah lama ada dan dianggap sebagai kriptografi primitif. Untuk itu, yang perlu pertama kali kita ketahui adalah tentang Fungsi Hash Kriptografi. Fungsi Hash adalah fungsi matematika dengan tiga sifat berikut ini:
⦁ Input bisa dari berbagai macam ukuran string.
⦁ Menghasilkan output dengan ukuran yang tetap
⦁ Efisien dalam komputansi. Hal ini berarti, setiap ada masukan input string, bisa mengkonfigurasi output fungsi hash dalam jumlah waktu yang wajar. Teknisnya, komputasi hash pada sebuah string n-bit harus mempunyai timing waktu, yakni O (n) (Notasi big 0 ).
Sifat-sifat tersebut menggambarkan fungsi hash secara umum. Dan bisa digunakan untuk membangun struktur data seperti halnya tabel hash. Agar Fungsi hash bisa menjadi kriptografi yang aman, maka perlu ditambahkan beberapa sifat tambahan, yakni:
Sifat 1: collision‐resistance
Sifat 2: hiding
Sifat 3: puzzle‐friendliness.
Lebih jauh, kita akan melihat detail masing-masing sifat tambahan tersebut untuk mengetahui mengapa itu diperlukan. Bagi yang sudah mempelajari kriptografi, perlu memperhatikan dan menyadari bahwa penerapan fungsi hash ini sedikit berbeda dari teks kriptografi yang ada pada umumnya. Misalkan pada sifat puzzle-friendliness, tidak menjadi persyaratan umum dalam fungsi hash kriptografi. Namun itu diperlukan untuk cryptocurrency tertentu.
Sifat 1: Collision‐resistance.
Sifat pertama yang dibutuhkan adalah Collision-Resistance. Secara harfiah, collision-resistance ini berarti resistansi saat terjadi benturan atau bertabrakan. Collision atau benturan ini terjadi jika dua input yang berbeda dan terpisah menghasilkan output yang sama. Fungsi hash H (.) menjadi collision-resistance, jika tidak ada yang menemukan collision (baca lebih lanjut untuk penjelasan tentang ini).
Collision-resistance: Sebuah fungsi hash H dikatakan collision resistant, jika tidak bisa untuk menemukan dua nilai, x dan y, sehingga x ≠ y, namun H (x) = H (y).
![kolusi hash](http://bitcoinmedia.id/wp-content/uploads/kolusi-hash-300x93.png)
Pada gambar tersebut kita lihat, x dan y adalah nilai yang berbeda dan terpisah, namun ketika dimasukkan kedalam fungsi hash H, mereka menghasilkan output yang sama.
Pada dasarnya, collision ini terjadi dan memang ada. Hal ini bisa dibuktikan dengan melakukan perhitungan argumen secara sederhana. Karena ruang input lebih besar daripada ruang output. Dan kenyataannya, memang ruang input ini tidak terbatas, sedangkan ruang output terbatas. Sehingga harus ada input string yang memetakan kedalam output dengan string yang sama.
![output](http://bitcoinmedia.id/wp-content/uploads/output-300x104.png)
Jumlah input melebihi jumlah output, oleh karena itu bisa dilogikakan setidaknya ada satu output fungsi hash yang memetakan lebih dari satu input.
Ada sebuah metode yang bisa menjamin untuk bisa menemukan collision. Metode sederhana yang bisa digunakan untuk menemukan collision fungsi hash dengan ukuran 256-bit, ukuran output 2256 + 1 nilai yang berbeda. Lalu komputasi masing-masing, kemudian cek apakah ada output yang sama. Ketika kita memilih input yang lebih besar daripada output, maka beberapa pasangan pasti bertabrakan ketika menerapkan fungsi hash.
Selanjutnya, jika kita memilih input secara acak dan kemudaian mengkomputasi nilai hash. Maka kita akan menemukan sebuah collision dengan probabilitas yang tinggi sebelum menguji input 2256 + 1. Bahkan. Jika kita secara acak memilih hanya input 2130 + 1, ada 99,8% kemungkinan bahwa dua dari itu akan bertabrakan.
Kenyataan bahwa kita bisa menemukan collision hanya dengan memeriksa kurang lebih akar pangkat dua jumlah kemungkinan hasil output pada fenomena probabilitas ini, disebut dengan istilah birthday paradox.
Algoritma pendeteksi collision ini bekerja pada setiap fungsi hash. Namun, membutuhkan waktu yang cukup lama. Untuk fungsi hash dengan output 256-bit, harus dikomputasi fungsi hash input 2256 +1 kali dalam kondisi yang buruk, dan sekitar 2128 kali pada kondisi rata-rata. Jumlah tersebut adalah jumlah yang besar. Jika sebuah komputer mengkalkulasi 10.000 hash per detik, akan membutuhkan waktu kurang lebih satu octillion (1027) tahun untuk mengkalkulasi 2128 hash.
Sebuah analogi untuk hal ini, misalkan jika setiap komputer yang pernah dibuat manusia digunakan untuk mengkomputasi seluruh alam semesta hingga sampai saat ini, maka kemungkinan untuk menemukan collision cukup kecil. Saking kecilnya kemungkinan tersebut, ibarat kemungkinan bahwa bumi akan hancur oleh meteor besar selang dua detik berikutnya.
Jadi, kita telah melihat algoritma pendeteksi collision tersebut, meskipun secara teknis cukup sulit untuk dipraktekkan karena waktu yang dibutuhkan cukup lama. Ada sebuah pertannyaan lanjutan, masih adakah algoritma lain yang lebih efisien untuk menemukan collision fungsi hash tertentu?
Coba kita melihat sebuah fungsi hash berikut:
h(x) = x mod 2256
Fungsi tersebut memenuhi persyaratan fungsi hash karena bisa menerima input berbagai ukuran, kemudian menghasilkan sebuah output dengan ukuran yang tetap, yakni 256 bit, dan lebih efisien. Fungsi tersebut hanya menghasilkan output 256 bit. Satu collision maka akan menjadi nilai 3, dan 3+2256. Meskipun tidak bisa dipraktekkan, setidaknya ada beberapa fungsi hash yang bisa mendeteksi collision. Dalam beberapa kasus, seperti pada fungsi hash MD5 yang lama, collision akhirnya ditemukan setelah beberapa tahun kemudian.
Setelah mengetahui apa yang dimaksud dengan collision-resistance, pertanyaan selanjutnya adalah, apa fungsi dan kegunaan collision-resistance itu? Ada sebuah aplikasi yang jika kita mengetahui ada dua input, yakni input x, dan input y untuk fungsi hash H adalah berbeda. Maka, cukup aman untuk mengambil asumsi, bahwa hash H(x) dan H(y) berbeda. Sementara jika seseorang mengetahui bahwa x dan y tersebut berbeda namun memiliki hash yang sama, maka akan melanggar asumsi bahwa H adalah collision resistant.
Sehingga dalam argumen ini, kita bisa menggunakan output hash tersebut sebagai message digest. Message digest ini merupakan angka yang dikalkulasi dari sistem informasi lewat fungsi kriptografi. Selanjutnya, angka ini digunakan untuk memverifikasi integritas data informasi. Segala perubahan pada informasi meskipun kecil akan menghasilkan message digest yang jauh berbeda.
Coba kita perhatikan dalam sebuah securebox, sebuah penyimpanan file online yang memungkinkan penggunanya untuk bisa mengupload file dan memastikan integritas filenya saat file tersebut di download. Misalnya Nita mengupload sebuah file dengan ukuran yang cukup besar, kemudian hendak memferifikasi file tersebut. Sehingga ketika Nita ingin mendownload file tersebut, sama persis ketika file tersebut dia upload. Untuk bisa melakukannya, dengan menyimpan file berukuran bersar tersebut, kemudian membandingkannya pada saat Nita mendownload. Jika Nita ingin untuk mempunyai akses ke local untuk memastikan integritas filenya, Nita bisa secara langsung mengcopy file itu.
Hash collision-free memberikan efisiensi pemecahan masalah ini secara elegan. Nita hanya perlu untuk mengingat hash dari file aslinya itu. Saat ia mendownload, Nita mengkomputasi hash file lantas membandingkannya pada saat ia menaruh file itu. Jika hash sama, maka Nita bisa menyimpulkan bahwa file itu adalah file yang sama. Namun jika hasilnya berbeda, maka Nita menyiimpulkan bahwa file miliknya telah dirusak.
Yang perlu diingat bahwa hash tersebut memungkinkan Nita untuk mendeteksi file corrupt yang terjadi secara sengaja selama proses transmisi atau pada server securebox. Tapi bisa juga karena dimodifikasi secara sengaja oleh server untuk melindungi dari adanya malicious.
Dalam hal ini, server hash berfungsi sebagai panjang digest, atau ringkasan pesan yang tidak ambigu. Memberikan cara yang efisien atas beberapa hal yang kita lihat sebelumnya. Keseluruhan ukuran file bisa mencapai gigabyte, sedangkan panjang hash tetap 256-bit. Sehingga bisa mengurangi kebutuhan penyimpanan file.