Memahami Serangan Hash table Collision Denial of Service

Pada Desember 2011 lalu, nRuns AG mempublikasikan kerentantan pada implementasi hash table yang bisa dieksploitasi untuk melakukan serangan denial of service. Karena hash table adalah struktur data dasar yang tersedia di hampir semua bahasa pemrograman, maka kerentanan ini bisa dieksploitasi di hampir semua bahasa pemrograman yang ada, termasuk PHP, ASP.NET, Java, Ruby dsb.

Sebagai tulisan pembuka di tahun 2012, saya akan membahas mengenai apa itu hash table, cara kerja hash table, di mana kerentanan implementasi hash table saat ini dan bagaimana cara mengeksploitasinya.

Associative array atau Map

Sebelum berbicara mengenai hash table, kita perlu tahu dulu bahwa associative array (disebut juga map atau dictionary) adalah abstract data type (ADT) yang terdiri dari pasangan kunci dan nilai dan dalam associative array tidak boleh ada kunci yang duplikat atau dobel (nilai boleh dobel, tapi kunci tidak boleh). Kunci ini bertindak seperti halnya nama dari data yang disimpan, sehingga dengan mengasosiasikan suatu data dengan kunci berupa nama atau identifier yang lain, data yang diinginkan bisa diambil dengan mudah dengan menyebutkan kuncinya.

Dalam contoh associative array di atas bila kita ingin tahu produsen mobil ini siapa, kita cukup mencari dengan kunci “make”, maka akan keluar datanya yaitu “Jeep”. Bila kita ingin tahu warna mobil ini apa, kita mencari dengan kunci “color”, maka akan keluar datanya “green”.

Lalu apa hubungannya associative array dengan hash table?

Associative array adalah abstract data type, artinya strutktur data yang masih berupa konsep atau spesifikasi saja. Hash table adalah salah satu (bukan satu-satunya) implementasi dari associative array, artinya hash table ini adalah concrete data type (sudah konkrit bukan lagi abstract/konseptual).

The basic idea of a hash table is that each item that might be stored in the table has a natural location in the table. This natural location can be computed as a function of the item itself. When searching for an item, it is not necessary to go through all the possible locations in the table; instead, you can go directly to the natural location of the item – Data Structures and Algorithms, David J. Eck

Kutipan di atas menggambarkan ide dasar dari hash table dengan baik. Bayangkan bila kita ingin mencari orang yang bernama Agus di sebuah desa yang terdiri dari 100 rumah dan kita harus mencarinya satu per satu dari rumah ke rumah, tentu akan memakan usaha dan waktu yang sangat lama. Hash table menghindari pencarian linear seperti ini. Daripada mencari satu per satu di semua rumah, dengan satu formula matematis tertentu, bisa diketahui bahwa berdasarkan namanya, Agus berada di rumah nomor XX (natural location), sehingga kita cukup mencari di satu rumah saja. Jauh lebih cepat dan efisien bukan?

Fungsi atau formula matematis yang digunakan untuk mencari lokasi data (natural location) dari suatu kunci dalam hash table adalah fungsi hash. Output dari fungsi hash ini disebut dengan hash code. Hash table pada dasarnya adalah sebuah array (setiap elemen array ini disebut dengan bucket), jadi fungsi hash ini akan menghasilkan index array berupa integer, dimana lokasi data disimpan.

Saya sudah membuat gambar animasi di bawah ini untuk memperlihatkan proses memasukkan data dalam hash table yang terdiri dari 6 bucket, data yang dimasukkan adalah nama sebagai key, dan tanggal lahir sebagai datanya.