MODIFIKASI ALGORITME FUNGSI HASH MD5 DIDASARKAN PADA ANALISIS SYARAT CUKUP SERANGAN DIFERENSIAL
AGUSTINUS SROYER
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2009
PERNYATAAN MENGENAI TESIS DAN SUMBER INFORMASI Dengan ini saya menyatakan bahwa tesis berjudul Modifikasi Algoritme Fungsi Hash MD5 didasarkan pada Analisis Syarat Cukup Serangan Diferensial adalah karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apapun kepada perguruan tinggi manapun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir tesis ini. Bogor,
Agustus 2009
Agustinus Sroyer NIM. G551060351
ABSTRACT AGUSTINUS SROYER. The Modification of MD5 Hash Function Algorithm Based on Sufficient Conditions of Analysis Differential Attack. Supervised by SUGI GURITMAN and NUR ALIATININGTYAS. MD5 (message digest five) is one of algorithms most widely used cryptographic hash functions nowadays. It was designed in 1992 as an improvement of MD4. On 2004, Wang found the weakness of the algorithm using differential attack, the collisions of MD5 could be found efficiently in two blocks. The first took about 239 MD5 operations, and the second block took about 232 MD5 operations. Based on these cases, it would be explained the weaknesses of the algorithm according to sufficient conditions analysis. The resulting analysis were used to modify the structure of MD5 hash function algorithm. The result was that there were four important components in MD5 algorithm which were changed, i.e addition constancy, cyclic constancy, message block permutation, and non-linearly boolean function. The value of addition constancy, cyclic constancy, message block permutation were changed from the value of fixed constancy into the value of a number of variable operation in the previous iteration, which was spread (depend on previous variable). In the meantime, the formula of non-linearly boolean function was changed. Modified MD5 algorithm was intended to be resistant to the differential attack of Wang version. Since the structure was not changed, this algorithm was also resistant to the other types or kinds of attack. The changing of some operations in MD5 algorithm caused the implementation to slow down. The results of the implementation showed that modified MD5 slower about three times from previous version. Keywords: hash function, MD5 algorithm, collision, differential attack, sufficient conditions.
RINGKASAN AGUSTINUS SROYER. Modifikasi Algoritme Fungsi Hash MD5 didasarkan pada Analisis Syarat Cukup Serangan Diferensial. Dibimbing oleh SUGI GURITMAN dan NUR ALIATININGTYAS. Salah satu primitif kriptografi modern adalah fungsi hash kriptografi, atau sering disebut fungsi hash satu-arah. Dari segi transformasinya, fungsi hash didefinisikan sebagai fungsi yang memetakan bitstring dengan panjang sebarang ke bitstring dengan panjang tetap. Output dari fungsi hash adalah nilai hash (hash value). Di samping itu, dari segi peranannya di dalam kriptografi, fungsi ini juga diharuskan memenuhi sifat satu arah dan tahan tumbukan. Fungsi hash h dikatakan bersifat satu arah apabila secara komputasi tak layak menentukan input x jika diketahui nilai hash y sehingga y = h(x). Di lain pihak, sifat tahan tumbukan dari h dimaknai secara komputasi tak layak menentukan pasangan input x dan x’ dengan x ≠ x’ sehingga outputnya sama, h(x) = h(x’) (terjadi tumbukan). Sifat satu arah dan tahan tumbukan menyebabkan fungsi hash salah satunya digunakan untuk melindungi integritas data dari pemalsuan. Sebagai ilustrasi, suatu pesan x dilabelkan dengan nilai hashnya y = h(x). Kita bisa memalsukan x apabila kita bisa menentukan pesan lain x’ ≠ x sehingga h(x’) = y (mempunyai label yang sama dengan x). Jika ini yang terjadi maka fungsi hash yang bersangkutan dikatakan tidak aman, dengan kata lain x’ bisa digunakan untuk memalsukan x. Dari makna fungsi hash yang telah diuraikan di atas, jelas bahwa menyerang suatu algoritme fungsi hash berarti mencari suatu metode untuk menentukan x dan x’, x ≠ x’, sehingga mempunyai peluang yang cukup tinggi terjadinya tumbukan, h(x) = h(x’). MD5 merupakan salah satu algoritme fungsi hash yang paling luas digunakan dalam kriptografi. Tahun 2004, Wang dan Yu (dalam How to Break MD5 and Other Hash Functions), selanjutnya disebut sebagai artikel Wang, berhasil mematahkan algoritme tersebut berdasarkan analisis syarat cukup serangan diferensial. Ide dasar serangan diferensial pada fungsi hash adalah memilih pasangan input x dan x’, x ≠ x’, dan mempunyai beda tertentu sehingga memperbesar peluang terjadinya tumbukan (h(x) = h(x’)). Pada proses serangan diferensial untuk MD5, pertama kali Wang dan Yu mendefinisikan diferensial karakteristik dalam bentuk Tabel Diferensial Karakteristik (Lampiran1 & Lampiran 3). Pendefinisian diferensial karakteristik ini dimaksudkan sebagai alur dalam proses algoritme MD5 jika diberi pasangan input x dan x’ dengan beda tertentu, diharapkan mempunyai peluang yang tinggi terjadinya tumbukan. Proses terjadinya tumbukan ditunjang dengan memodifikasi pesan melalui penentuan syarat cukup pada bit-bit tertentu. Syarat cukup diberikan dalam bentuk Tabel Syarat Cukup (Lampiran 2 & Lampiran 4). Dengan metode tersebut Wang dan Yu berhasil menentukan tumbukan pada MD5 secara efisien di mana blok pertama memerlukan sekitar 239 operasi MD5 dan blok kedua memerlukan sekitar 232 operasi MD5. Hasil tersebut diperkuat juga oleh Hawkes et al. (dalam Musings on the Wang et al. MD5 Collision, 2004).
Namun sayangnya, pendefinisian karakteristik diferensial pada artikel tersebut diberikan tanpa penjelasan dan hanya diberikan sedikit ilustrasi bagaimana menentukan syarat cukup. Pada penelitian ini dieksploitasi bagaimana menentukan syarat cukup penentuan nilai bit-bit tertentu untuk memodifikasi pesan sampai pada langkah ketujuh secara lengkap mengikuti Tabel Karakteristik Diferensial. Dengan kata lain, jika dilanjutkan maka akan diperoleh nilai-nilai syarat cukup (Lampiran 2 & Lampiran 4). Syarat cukup tersebut digunakan untuk memodifikasi pesan sehingga memperbesar peluang terjadinya tumbukan (collision). Berdasarkan syarat cukup tersebut maka digunakan untuk menarik kesimpulan dan selanjutnya memodifikasi MD5. Modifikasi MD5 hanya dilakukan pada komponen-komponen utama tanpa mengubah struktur besarnya. Komponen-komponen utama tersebut adalah konstanta putaran, konstanta jumlah, permutasi blok pesan dan fungsi boolean tak linear. Nilai konstanta jumlah, konstanta putaran, dan permutasi blok pesan diubah dari nilai konstanta tetap ke nilai hasil operasi beberapa variabel pada iterasi sebelumnya yang sifatnya merambat. Di lain pihak, fungsi boolean tak linear diubah rumusnya. Algoritma MD5 termodifikasi dimaksudkan agar tahan terhadap serangan diferensial, khususnya versi Wang. Karena strukturnya tidak berubah algoritme ini juga tahan terhadap tipe atau jenis serangan yang lain. Perubahan beberapa operasi di dalam algoritme MD5 menyebabkan kinerjanya menurun dibandingkan sebelumnya (MD5 asli). Hasil implementasi menunjukkan MD5 termodifikasi sepertiga kali lebih lambat dari MD5 sebelumnya. Kata kunci: fungsi hash, algoritme MD5, tumbukan, serangan diferensial, karakteristik diferensial, syarat cukup
© Hak Cipta milik Institut Pertanian Bogor, tahun 2009 Hak cipta dilindungi Undang-undang 1.
2.
Dilarang mengutip sebagian atau seluruh karya tulis ini tanpa mencantumkan atau menyebut sumber. a. Pengutipan hanya untuk kepentingan pendidikan, penelitian, penulisan karya ilmiah, penyusunan laporan, penulisan kritik, atau tinjauan suatu masalah. b. Pengutipan tidak merugikan kepentingan yang wajar Institut Pertanian Bogor. Dilarang mengumumkan dan memperbanyak sebagian atau seluruh karya tulis dalam bentuk apapun tanpa ijin Institut Pertanian Bogor.
MODIFIKASI ALGORITME FUNGSI HASH MD5 DIDASARKAN PADA ANALISIS SYARAT CUKUP SERANGAN DIFERENSIAL
AGUSTINUS SROYER
Tesis sebagai salah satu syarat untuk memperoleh gelar Magister Sains pada Departemen Matematika
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2009
Judul Tesis Nama NIM
: Modifikasi Algoritme Fungsi Hash MD5 didasarkan pada Analisis Syarat Cukup Serangan Diferensial : Agustinus Sroyer : G551060351
Disetujui Komisi Pembimbing
Dr. Sugi Guritman Ketua
Dra. Nur Aliatiningtyas, M.Si. Anggota
Diketahui
Ketua Program Studi
Dekan Sekolah Pascasarjana Matematika Terapan
Dr. Ir. Endar Nugrahani, M.S.
Tanggal Lulus: .................................
Prof. Dr. Ir. Khairil A. Notodiputro, M.S.
Tanggal Ujian: 18 Agustus 2009
Karyaku ini kupersembahkan untuk orang-orang yang kukasihi: Bapak Yeremias Sroyer (alm.) dan Ibu Yulita Reprep (alm.) Ibu Sugiyem Istriku terkasih Agnes Eri Maryuni beserta kedua buah hatiku Marchelino dan Amadhea Bapak Robert Masreng dan Mbak Endah Kakak-kakak, adik-adik, dan keponakan-keponakan di Papua beserta keluarga besar di Papua Keluarga besar yang ada di Gombong, Wonosobo, Tawangmangu, Tangerang, Bogor, Jambi Semoga karyaku yang kecil ini dapat bermakna bagi perkembangan ilmu pengetahuan di tanah Papua khususnya di Universitas Cenderawasih
PRAKATA Puji dan syukur penulis haturkan kepada Tuhan Yesus Kristus, karena atas berkat dan rahmat-Nya sehingga karya ilmiah ini bisa diselesaikan. Sembah syukur juga penulis panjatkan kepada Bunda Maria, atas terkabulnya Novena Salam Maria. Tema yang dipilih dalam penelitian yang dilaksanakan sejak Januari 2008 ini adalah bagaimana cara memodifikasi algoritme fungsi hash MD5 agar tahan terhadap serangan diferensial. Terima kasih penulis sampaikan kepada Bapak Dr. Sugi Guritman dan Ibu Dra. Nur Aliatiningtyas, M.Si. selaku pembimbing. Selain itu penulis ucapkan terima kasih juga kepada: 1. 2. 3.
Semua dosen dan staf Departemen Matematika IPB atas segala ilmu dan bantuannya. Bapak Festus Simbiak selaku Dekan FKIP Uncen yang telah memberikan kesempatan untuk studi serta bantuan dana maupun moril. Teman-teman seangkatan di Pascasarjana IPB: Sri Rosdiana, Is Esti Firmanesa, Sitta Alief Farihati, dan Asmara Iriani Tarigan yang telah memberi dorongan dalam penulisan tesis. Semoga karya ilmiah ini bermanfaat. Bogor,
Agustus 2009
Agustinus Sroyer
RIWAYAT HIDUP Penulis dilahirkan di Fakfak-Papua pada tanggal 15 Agustus 1980 dari ayah Yeremias Sroyer (alm.) dan Ibu Yulita Reprep (alm.). Penulis merupakan anak kedelapan dari duabelas bersaudara. Pada tahun 1998 penulis kuliah di Universitas Cenderawasih Jayapura lewat Seleksi Lokal Siswa Berpotensi (SLSB) dan lulus tahun 2003 dan langsung menjadi asisten dosen pada program studi Pendidikan Matematika FKIP Universitas Cenderawasih. Tahun 2003 juga penulis diangkat menjadi CPNS, pengangkatan sebagai PN pada tahun 2005 dan sampai sekarang penulis bekerja sebagai staf pengajar pada Program Studi Pendidikan Matematika FKIP Universitas Cenderawasih. Pada tahun 2006, atas inisiatif dan biaya sendiri penulis melanjutkan studi di Sekolah Pascasarjana Program Studi Matematika Terapan, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor.
DAFTAR ISI Halaman DAFTAR TABEL .............................................................................................. xiii DAFTAR GAMBAR ......................................................................................... xiv DAFTAR LAMPIRAN ...................................................................................... xv PENDAHULUAN ................................................................................................ 1 Latar Belakang ........................................................................................... 1 Tujuan Penelitian ....................................................................................... 4 Manfaat Penelitian ..................................................................................... 4 LANDASAN TEORI ............................................................................................ 5 Fungsi ........................................................................................................ 5 Fungsi Hash ............................................................................................... 7 Konstruksi Umum Fungsi Hash .............................................................. 11 Deskripsi Umum MD5 ............................................................................ 14 Modular dan Xor ..................................................................................... 19 Diferensial Modular dan Xor .................................................................. 20 Serangan Diferensial pada Fungsi Hash .................................................. 21 Penotasian Serangan Diferensial pada MD5 ........................................... 23 Diferensial Tumbukan untuk MD5 ......................................................... 23 Langkah-langkah Syarat Cukup Dipenuhinya Karakteristik Diferensial pada MD5 ................................................................. 24 Modifikasi Algoritme Fungsi Hash MD5 ............................................... 27 Jenis-jenis Serangan Fungsi Hash ........................................................... 27 HASIL DAN PEMBAHASAN .......................................................................... 32 Analisis Syarat Cukup Karakteristik Diferensial pada MD5 ................ 32 Modifikasi Algoritme MD5 dan Program MD5 beserta Implementasinya .............................................................. 46 SIMPULAN DAN SARAN ............................................................................... 51 Simpulan ................................................................................................. 51 Saran ....................................................................................................... 51 DAFTAR PUSTAKA ........................................................................................ 52 LAMPIRAN-LAMPIRAN ................................................................................ 53
DAFTAR TABEL Tabel 1 Tabel Xor Operasi Biner ........................................................................ 19 Tabel 2 Tabel Waktu Hashing Algoritme MD5 dalam Detik ............................. 49 Tabel 3 Tabel Waktu Hashing Algoritme MD5 dalam Menit ............................ 50
DAFTAR GAMBAR Gambar 1 Contoh Tumbukan Fungsi .................................................................... 7 Gambar 2 Klasifikasi Sederhana dari Kriptografi Fungsi Hash ......................... 11 Gambar 3 Model Umum Suatu Iterasi Fungsi Hash ........................................... 13 Gambar 4 Grafik Perbandingan Waktu antara MD5 Asli dan Modifikasi .......... 50
DAFTAR LAMPIRAN Lampiran 1 Tabel Karakteristik Diferensial Iterasi Pertama .............................. 53 Lampiran 2 Tabel Syarat Cukup Diferensial Iterasi Pertama ............................ 54 Lampiran 3 Tabel Karakteristik Diferensial Iterasi Kedua ................................ 55 Lampiran 4 Tabel Syarat Cukup Diferensial Iterasi Kedua ............................... 56 Lampiran 5 Program Hashing MD5 Asli ........................................................... 57 Lampiran 6 Program Hashing MD5 Modifikasi ................................................ 67
