Fungsi Hash (Hash Functions)

Fungsi hash (bahasa Inggris: hash function) adalah sebarang algoritma atau subrutin yang memetakan data dengan ukuran sembarang (variabel) ke data dengan ukuran tetap. Nilai yang dikembalikan oleh fungsi hash disebut sebagai nilai hash, kode hash, digest, atau sederhananya hash. Nilai-nilai ini biasanya digunakan untuk mengindeks tabel hash berukuran tetap yang disebut tabel hash. Penggunaan fungsi ini sangat luas dalam bidang ilmu komputer, mulai dari pencarian data yang cepat hingga verifikasi integritas data.

Dalam penerapannya, fungsi hash bertindak sebagai fingerprint atau sidik jari digital dari sebuah data. Jika input mengalami perubahan sekecil apa pun, maka output yang dihasilkan oleh fungsi hash akan berubah secara drastis. Sifat ini sangat krusial dalam dunia kriptografi, di mana keamanan informasi bergantung pada kemampuan algoritma untuk mendeteksi perubahan atau manipulasi data yang tidak sah. Meskipun ada banyak jenis fungsi hash, semuanya berbagi tujuan matematis yang sama yaitu kompresi representasi data.

Definisi Matematis

Secara matematis, fungsi hash $h$ dapat didefinisikan sebagai pemetaan dari himpunan input $K$ (kunci) ke himpunan output $S$ (slot atau alamat), di mana ukuran himpunan output biasanya jauh lebih kecil daripada himpunan input. Notasi formalnya dapat dituliskan sebagai:

$h : K \to S$

Di mana $| K | > | S |$ . Karena ukuran domain (input) lebih besar daripada kodomain (output), maka berdasarkan prinsip sarang burung merpati, tabrakan hash (hash collision) tidak dapat dihindari sepenuhnya. Tabrakan terjadi ketika dua input berbeda, $x_{1}$ dan $x_{2}$ , menghasilkan nilai hash yang sama, yaitu $h (x_{1}) = h (x_{2})$ dengan $x_{1} \neq x_{2}$ .

Dalam konteks komputasi numerik, salah satu metode hashing yang paling sederhana adalah metode pembagian (division method). Metode ini memetakan sebuah kunci $k$ ke dalam salah satu dari $m$ slot dengan mengambil sisa pembagian kunci oleh ukuran tabel. Rumusnya dinyatakan sebagai:

$h (k) = k mod m$

Meskipun sederhana, pemilihan nilai $m$ sangat penting; biasanya dipilih bilangan prima yang tidak dekat dengan pangkat dua untuk meminimalkan pola tabrakan pada distribusi kunci tertentu.

Sifat-sifat Penting

Fungsi hash yang baik harus memenuhi beberapa kriteria utama untuk memastikan efisiensi dan keamanan. Salah satu sifat yang paling mendasar adalah determinisme. Artinya, untuk input yang sama, fungsi hash harus selalu menghasilkan nilai output yang sama persis, kapan pun dan di mana pun fungsi tersebut dijalankan. Tanpa sifat ini, fungsi hash tidak akan berguna untuk pengambilan data atau verifikasi.

Sifat selanjutnya adalah efisiensi komputasi. Sebuah algoritma hash harus mampu menghitung nilai hash dari sebuah input dengan cepat. Dalam aplikasi basis data atau sistem berkas, waktu yang dibutuhkan untuk menghasilkan hash tidak boleh menjadi bottleneck yang memperlambat kinerja sistem secara keseluruhan. Kompleksitas waktu ideal untuk menghitung hash adalah $O (1)$ jika panjang input dianggap konstan, atau $O (L)$ di mana $L$ adalah panjang input.

Efek longsoran (avalanche effect) juga merupakan karakteristik yang diinginkan, terutama dalam fungsi hash kriptografis. Sifat ini menjamin bahwa perubahan kecil pada input (misalnya, membalik satu bit) akan menyebabkan perubahan yang signifikan dan tidak dapat diprediksi pada output hash. Jika input "A" menghasilkan hash "123", maka input "B" (yang sangat mirip dengan "A") tidak boleh menghasilkan hash yang mirip seperti "124", melainkan sesuatu yang acak seperti "892".

Fungsi Hash Kriptografis

Fungsi hash kriptografis adalah kelas khusus dari fungsi hash yang memiliki properti keamanan tambahan. Fungsi ini dirancang untuk menahan serangan dari musuh yang mencoba menemukan dua input berbeda yang menghasilkan hash yang sama. Algoritma ini merupakan komponen fundamental dalam protokol keamanan modern seperti SSL/TLS, tanda tangan digital, dan teknologi blockchain.

Secara umum, fungsi hash kriptografis harus memenuhi tiga kriteria keamanan utama berikut:

Resistensi pra-peta (Pre-image resistance): Diberikan nilai hash $h (x)$ , haruslah sulit secara komputasi untuk menemukan nilai input asal $x$ . Ini sering disebut sebagai sifat satu arah (one-way).
Resistensi pra-peta kedua (Second pre-image resistance): Diberikan input $x_{1}$ , haruslah sulit untuk menemukan input lain $x_{2}$ di mana $x_{1} \neq x_{2}$ namun $h (x_{1}) = h (x_{2})$ .
Resistensi tabrakan (Collision resistance): Haruslah sulit untuk menemukan dua input sembarang $x_{1}$ dan $x_{2}$ yang berbeda sedemikian rupa sehingga menghasilkan nilai hash yang sama.

Contoh algoritma hash kriptografis yang populer meliputi keluarga SHA-2 (seperti SHA-256) dan SHA-3. Algoritma yang lebih tua seperti MD5 dan SHA-1 kini dianggap tidak aman untuk tujuan kriptografi karena kelemahan yang telah ditemukan, yang memungkinkan penyerang menemukan tabrakan dengan sumber daya komputasi yang wajar.

Aplikasi dan Kegunaan

Salah satu penggunaan paling umum dari fungsi hash adalah dalam struktur data yang dikenal sebagai tabel hash. Tabel hash menggunakan fungsi hash untuk menghitung indeks ke dalam array "bucket" atau slot. Dengan cara ini, komputer dapat menemukan lokasi penyimpanan nilai data berdasarkan kuncinya hampir secara instan, tanpa harus mencari melalui seluruh data satu per satu.

Dalam penyimpanan kata sandi (password), sistem yang aman tidak pernah menyimpan kata sandi pengguna dalam bentuk teks biasa (plaintext). Sebaliknya, sistem menyimpan nilai hash dari kata sandi tersebut, sering kali ditambahkan dengan data acak yang disebut salt. Ketika pengguna mencoba masuk, sistem akan menghitung hash dari kata sandi yang dimasukkan dan membandingkannya dengan hash yang tersimpan. Jika cocok, akses diberikan.

Fungsi hash juga digunakan untuk verifikasi integritas data, seperti checksum. Ketika sebuah berkas diunduh dari internet, pengguna dapat memverifikasi apakah berkas tersebut korup atau telah dimodifikasi dengan membandingkan hash berkas yang diunduh dengan hash asli yang disediakan oleh penerbit. Algoritma seperti CRC32 sering digunakan untuk deteksi kesalahan transmisi, meskipun bukan untuk tujuan keamanan.