Fungsi hash adalah fungsi yang memetakan dari suatu data (bisa string atau apapun) ke sebuah data lain yang ukurannya biasanya lebih kecil. Ada fungsi hash untuk dipakai di struktur data hash table (outputnya adalah integer) dan ada fungsi hash untuk kriptografi outputnya berupa string alfanumerik dengan panjang tertentu.
Hash Table
Sebelum menjelaskan fungsi hash kriptografi, saya jelaskan dulu contoh fungsi hash biasa karena lebih sederhana. Penggunaan fungsi hash dalam kasus ini adalah untuk menyimpan data ke hash table, supaya gampang diakses lagi.
Misalnya kita punya array yang bisa menyimpan 100 elemen. Kita ingin menyimpan sebuah string, lalu ingin bisa menemukan kembali string itu dengan cepat nantinya, tidak memulai membandingkan satu per satu dari elemen pertama. Untuk melakukan ini kita bisa memakan fungsi hash. Sebuah string akan dimasukkan ke sebuah fungsi hash, hasilnya adalah sebuah angka n dari 0-99, lalu kita masukkan string ke array di indeks itu.
Ketika kita ingin mencari apakah sebuah string ada di array atau tidak, kita hash string tersebut, lalu kita cek apakah di elemen ke-n hasil fungsi hash tersebut ada elemennya. Dalam kasus tertentu, setiap string bisa dipetakan ke slot array yang berbeda.
Tentunya ada kemungkinan lebih dari satu string dipetakan ke satu lokasi, istilahnya terjadi collision. Jika ini terjadi, maka kita bisa menyimpan elemen di indeks n+1, jika sudah ada isinya ke n+2, dst. Sebaliknya ketika mencari elemen, jika isi array di posisi itu kosong artinya elemen tidak ada. Tapi jika di posisi itu ada isinya, kita perlu mengecek elemen berikutnya, jika tidak ada maka cek n+1, n+2 dst. Kasus ini tidak ideal, tapi masih lebih baik daripada mencari dari awal sampai akhir array.
Fungsi Hash
Bagaimana mengubah sebuah string menjadi sebuah angka yang kecil (dalam range tertentu, misalnya dalam kasus di atas 0-99)? cara termudah adalah dengan melakukan sebuah operasi, misalnya penjumlahan terhadap masing-masing huruf, lalu hasilnya di-modulo 100.
Menjumlahkan string saja sangat mudah, tapi sangat mudah juga terjadi collision: dua string yang hurufnya sama tapi posisinya beda akan dihash ke nilai yang sama. Cara yang lebih baik adalah dengan menggunakan bobot, misalnya dalam Java caranya adalah dengan menggunakan formula ini:
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
Contohnya jika kita punya string ABC (panjangnya 3), maka hasilnya adalah A (65) * 31*31 + B (66)*31 + C (67) = 64578. Sekarang kebetulan 2 hash yang sama lebih kecil, tapi tetap cukup mudah jika dilakukan dengan sengaja. Contohnya string “B#C” akan memiki hash yang sama dengan “ABC”. Ini bisa dicari dengan mudah karena dengan rumus di atas, jika saya ubah A menjadi B (bergeser 1) maka nilai hash akan bertambah sebesar (1*31*31 = 961), dan ini bisa dikompensasi dengan mengurangi karakter kedua sebanyak 31 (dari B menjadi #).
Sebagai catatan: fungsi hash code Java hanya akan menghasilkan angka 32 bit (akan dilakukan modulo jika lebih). Artinya jika kita punya 2^32 + 1 string yang unik, maka pasti ada setidaknya sepasang yang hashnya sama.
Fungsi hash ini belum cukup aman untuk tujuan kriptografi. Saya pernah menemui aplikasi yang memakai ini untuk fungsi hash penting dan ini merupakan kesalahan fatal.
Fungsi Hash Kriptografi
Fungsi hash kriptografi berbeda dari fungsi hash biasa, tapi memiliki kesamaan. Di dalam keduanya kita ingin “mengkompress” data menjadi bilangan kecil. Dalam hash kriptografi, kita ingin agar:
- jika data diubah sedikit saja, hashnya akan berbeda
- dari sebuah nilai hash X, kita tidak bisa membentuk sebuah input sedemikian sehingga hashnya adalah X
Jika tiap kali diberikan sebuah hash X dan kita selalu bisa menemukan sebuah string sedemikian hingga hashnya X tertentu maka fungsi hash tersebut berhasi dipecahkan (broken).
Kegunaan hash ini:
- Untuk verifikasi data yang besar. Jika hashnya tidak berubah, berarti data tidak diutak-atik
- Untuk penyimpanan password
Untuk penyimpanan password, prinsipnya seperti ini:
- ketika password dibuat, password akan dihash dan hashnya yang disimpan
- ketika login, password yang dimasukkan akan dihash, dan nilai hashnya akan dibandingkan
Fungsi hash kriptografi biasanya minimal memiliki output 128 bit. Artinya jika kita mencoba 340282366920938463463374607431768211456 + 1 data yang unik, maka akan ada 1 yang hashnya sama. Sebagai latihan, cobalah membagi bilangan itu dengan jumlah detik dalam setahun, lalu asumsikan 1 detik bisa melakukan berapa operasi hash, dan kalikan dengan 1 milyar komputer di dunia, hasilnya merupakan bilangan tahun yang sangat besar.
Saat ini ada banyak fungsi hash dan biasanya akan menghasilkan string biner antara 128-512 bit. Atau jika dijadikan karakter heksa: antara 32 – 128 karakter heksa. Beberapa fungsi hash yang umum adalah MD5, SHA1, SHA256, SHA512.
Detail fungsi hash tidak saya bahas di sini, dan biasanya tidak penting detailnya bagi seorang programmer. Berbagai bahasa sudah memiliki library untuk melakukan hashing.Pemahaman diperlukan jika ingin mempelajari keamanannya atau ingin mengetahui bagaimana cara kerja berbagai serangan (seperti hash length extension attack).
Mari kita lakukan hal praktis saja, berikut ini contoh berbagai string yang dihash dan outputnya, perhatikan bahwa Perbedaan sedikit saja akan menghasilkan nilai hash yang sangat berbeda.
Cracking Hash
Cara cracking sebuah hash agar kembali menjadi passsword pada dasarnya ada dua:
- Dictionary attack
- Bruteforce attack
Jadi diberikan sebuah kamus kata, kita hash masing-masing kata dan cek apakah hashnya sama dengan yang kita cari. Dalam brute force, kita akan mencoba semua kemungkinan karakter seperti AAAA, AAAB, dst sampai semua simbol dicoba.
Beberapa situs sudah menyimpan hash dari database password yang umum, sehingga jika kita cari hashnya, maka kita akan mendapatkan passwordnya.
Tentunya menyimpan kombinasi hash dan password butuh penyimpanan yang besar, untuk mengatasi ini bisa digunakan Rainbow table.
Penutup
Topik hashing ini belum lengkap, dan masih akan diteruskan di bagian berikutnya. Topik yang belum dibahas antara lain:
- salting
- kesalahan pemakaian hash
- HMAC