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
I PENDAHULUAN 1.1 Latar Belakang Perkembangan dunia yang semakin maju dan modern ini tidak terlepas dari adanya peranan teknologi informasi. Berbagai bidang kehidupan pun tak luput dari penggunaan sarana informasi yang semakin canggih. Hal itu terlihat dengan adanya penggunaan komputer baik di rumah, sekolah, kantor, maupun jasa penyewaan (rental) komputer yang dengan mudahnya dapat kita temui di manapun kita berada. Pemakaian komputer pun tidak hanya sebatas mengetik tugas-tugas sekolah maupun tugas-tugas kantor, tetapi lebih dari pada itu digunakan untuk mengirim informasi/berita yang lebih kita kenal dengan surat elektronik atau electronic mail (email). Pengiriman email pun dapat dilakukan antar sahabat, antar dosen-mahasiswa, serta siapa saja baik dalam satu kota, antar kota, bahkan antar negara. Isi berita email pun tidak hanya sekedar mengetahui kabar masing-masing tetapi lebih dari itu, informasi atau dokumen paling rahasia pun dapat dikirim lewat email. Hal ini dikarenakan biaya pengiriman email yang sangat murah, mudah, dapat dikirim ke berbagai belahan dunia. Berkaitan dengan pengiriman informasi atau dokumen rahasia, apakah email dapat menjamin kerahasiaan? Untuk menjawab pertanyaan tersebut dibutuhkan suatu ilmu yang dapat menyembunyikan huruf atau tulisan sehingga tulisan tersebut tidak dapat dibaca oleh orang yang tidak berhak atau yang dikenal dengan ilmu kriptografi. Kriptografi adalah studi teknik matematika yang berkaitan dengan aspek keamanan informasi seperti kerahasiaan, integritas data, autentikasi entitas, dan autentikasi asal data (Menezes et al. 1996). Kerahasiaan berarti menjaga isi informasi dari semua yang tidak berwenang memilikinya. Integritas data berarti menjamin bahwa informasi yang dikirim tidak diganti oleh siapapun yang tidak berwenang. Autentikasi entitas berarti pembuktian yang kuat tentang identitas suatu entitas, yaitu unsur-unsur yang menjadi komponen dalam suatu transaksi informasi, bisa berupa orang, terminal komputer, kartu kredit, dan sebagainya. Autentikasi asal data (autentikasi pesan) berarti pembuktian yang kuat bahwa pesan benar-benar berasal dari sumber informasi. Salah satu primitif kriptografi modern adalah fungsi hash kriptografi, atau sering disebut fungsi hash satu-arah. Fungsi hash adalah suatu fungsi yang
mengambil input (bitstring) dengan panjang sebarang dan mentransformasikannya menjadi suatu output (bitstring) dengan panjang tetap, biasanya disebut dengan nilai-hash (hash-value). Sebagai ilustrasi, jika x → h(x) nilai sebelum dan sesudah dihashing sama, berarti pesan masih asli tetapi kalau beda berarti pesan sudah diubah. Kegunaan fungsi hash adalah untuk melindungi data. Dalam kriptografi dikenal dengan istilah integritas data (data integrity), maksudnya menjamin bahwa informasi yang dikirim tidak diganti oleh siapapun yang tidak berwenang. Secara umum fungsi hash mempunyai 3 (tiga) sifat utama, yaitu pertama bersifat kompresi dan memudahkan perhitungan di mana jika diketahui h dan suatu input x, maka h(x) mudah dihitung; kedua bersifat satu-arah (one-way) di mana fungsi hanya bekerja dalam satu arah, untuk setiap h yang dihasilkan adalah tak layak untuk mencari nilai x sedemikian sehingga H(x) = h, sehingga pesan yang sudah diubah menjadi nilai hash sulit dikembalikan lagi menjadi pesan semula; ketiga bersifat tahan tumbukan di mana secara perhitungan tak layak mencari dua input berbeda x, x’ dengan x≠ x’ sehingga h(x’) = h(x) (Menezes et al. 1996). Ketahanan tumbukan dibagi 2 (dua) yaitu ketahanan tumbukan lemah dan kuat (Menezes et al. 1996) . Ketahanan tumbukan lemah, jika diberikan x dan h(x), secara perhitungan infisibel untuk mencari sebarang x’, dengan x' x , sedemikian sehingga h( x ' ) h( x ) . Di lain pihak, ketahanan tumbukan kuat, secara perhitungan infisibel untuk mencari pasangan x dan x' , dengan x x' , sedemikian sehingga h( x ) h( x ' ) . Istilah lain dari ketahanan tumbukan adalah ketahanan tumbukan kuat. Tahan tumbukan ini bertujuan untuk mencegah pemalsuan, agar orang tidak bisa memperoleh input-input lain yang sama dengan nilai hash. Prinsip kerja fungsi hash melalui 3 (tiga) langkah yaitu pertama padding, input x dengan x = b dibagi menjadi t blok, di mana setiap blok mempunyai panjang r dan b bukan kelipatan dari r, sehingga dilakukan penambahan bit ekstra (padding) agar blok terakhir mempunyai panjang r. Langkah kedua kompresi, di mana setiap blok xi adalah input dari fungsi kompresi f dengan menggunakan
proses iterasi H0 = VI0 dan Hi = f(Hi-1, xi), 1 ≤ i ≤ t. Langkah ketiga finalisasi, Ht ditransformasikan dengan suatu fungsi g ke suatu bitstring dengan panjang m. Salah satu jenis fungsi hash adalah message digest five (MD5). Message digest bisa diartikan sebagai intisari pesan. MD5 didesain oleh Ron Rivest sebagai versi penguatan dari MD4. Secara umum, fungsi hash diiterasikan oleh fungsi kompresi X = f(Z) yang mengompres blok pesan Z berukuran l bit menjadi nilai hash X berukuran s bit, dengan s < l. Untuk MD5, nilai l = 512 bit dan s = 128 bit, dan metode iterasinya menggunakan Merkle-Damgard Meta Method. Untuk suatu pesan yang telah dilipatkan (padded message) M, berarti mempunyai panjang Hi+1 = f(Hi, Mi), 1 ≤ i ≤ t dengan M = M 0 , M 1 , ... , M t 1 dan H0 = a 0 , b0 , c0 , d 0 adalah nilai awal fungsi hash. MD5 memproses blok pesan Mi berukuran 512 bit, kemudian
dibagi
ke
dalam
16
kata
mj
berukuran
32
bit,
yaitu
M i m 0 , m1 , ... , m15 . Output dari MD5 berupa 4 buah blok pesan yang masingmasing berisi 32 bit yang mana akan menjadi 128 bit yang merupakan nilai hash. Sejak MD5 pertama kali dipublikasikan tahun 1992, telah ditemukan beberapa kelemahan. Kelemahan ini ditemukan oleh Xiaoyun Wang dan Hongbo Yu dalam (2004), di mana serangan yang dilakukan adalah tipe serangan diferensial. Inti dari serangan ini adalah mencari pasangan
M 0 , M 1
dan
M 0 ' , M 1 ' . Pada artikel itu diperoleh bahwa tumbukan pada MD5 dapat dicapai secara efisien, yaitu dengan pencarian tumbukan pada blok pertama memerlukan 239 operasi MD5 dan pada blok kedua memerlukan waktu sekitar 232 operasi MD5. Pada penelitian ini akan dimodifikasi algoritme dari fungsi hash MD5 yang didasarkan pada analisis syarat cukup serangan diferensial versi Wang. Pada algoritme ini terdapat 4 (empat) komponen utama yang sangat mempengaruhi tiap langkah pada proses iterasinya. Pertama, fungsi konstanta jumlah yaitu fungsi yang menghasilkan nilai-nilai konstanta pada tiap langkah dalam satu blok, t(i) = 232 abs (sin i) di mana i adalah sudut dalam radian. Kedua, konstanta putaran di mana konstanta ini mempunyai struktur yang teratur dan selalu tetap (berpengaruh pada kecepatan, semakin teratur maka semakin cepat). Ketiga, permutasi blok pesan. Keempat, fungsi ronde Boolean tak linear yaitu fungsi (X,Y,Z) di mana
yang berpengaruh adalah nilai X. Keempat komponen ini juga merupakan kelemahan dalam algoritme MD5. Pada penelitian ini akan dianalisis keempat kelemahan tersebut. Nilai konstanta jumlah, konstanta putaran, dan permutasi blok pesan diubah dari nilai konstanta bebas ke nilai hasil operasi beberapa variabel pada iterasi sebelumnya yang sifatnya merambat, dan fungsi boolean tak linear akan diubah rumusnya. Merambat berarti modifikasi tiap langkah berikutnya bergantung pada langkah sebelumnya. Inti dari modifikasi ini adalah bagaimana membaharui algoritme yang sudah ada agar lebih baik dari sebelumnya. Di dalam modifikasi ini akan dianalisis syarat cukup berdasarkan Tabel Karakteristik Diferensial (Lampiran 1 & Lampiran 3), di mana akan dianalisis sampai pada langkah ketujuh dan syarat cukup selanjutnya mengacu pada Tabel Syarat Cukup (Lampiran 2 & Lampiran 4) yang sudah diperoleh Wang. Dari syarat cukup tersebut akan dianalisis mengapa serangan diferensial berhasil untuk menyerang MD5. Penelitian yang dilakukan Wang, sudah dipertegas juga oleh Hawkes et al. (2004), di mana penelitian tersebut menjelaskan secara rinci langkah-langkah diperolehnya syarat cukup berdasarkan karakteristik diferensial. Dalam penelitian ini dilakukan penentuan syarat cukup setipe dengan Hawkes et al. tapi dengan pendekatan yang berbeda dan adanya penambahan dengan memodifikasi algoritme MD5. Implementasi dari penelitian ini adalah merekonstruksi algoritme MD5 menggunakan software maple dalam bentuk program hashing MD5 dan mengimplementasikan fungsi iterasi MD5 dan mengimplementasikan hasil modifikasi MD5. 1.2
Tujuan Penelitian
Penelitian ini bertujuan memodifikasi algoritme fungsi hash MD5 yang didasarkan pada analisis syarat cukup serangan diferensial yang diharapkan tahan terhadap serangan diferensial versi Wang. 1.3
Manfaat Penelitian
Hasil modifikasi dari algoritme fungsi hash MD5 ini diharapkan lebih baik dan lebih aman dari sebelumnya apabila digunakan untuk melindungi integritas data.
II LANDASAN TEORI Pada bagian ini akan dijelaskan mengenai fungsi secara umum, fungsi hash, deskripsi MD5 dan jenis-jenis serangan fungsi hash. 2.1
Fungsi Sebelum memberi definisi fungsi hash, akan dibahas dulu topik dasar matematika
yang melandasi fungsi hash yaitu fungsi (definisi fungsi) beserta sifat-sifatnya, dan fungsi satu-arah (one-way). 2.1.1
Definisi Fungsi
Definisi 1.1 (Menezes et al. 1996) Suatu fungsi f dari himpunan A ke himpunan B , dinotasikan f : A B , didefinisikan sebagai suatu aturan yang memetakan setiap anggota A ke tepat satu anggota B . Dalam hal ini, A disebut domain dan B disebut kodomain dari f . Jika a A dan b B adalah hasil pemetaan dari a oleh f , maka
b disebut imej dari a dan a disebut preimej dari b oleh f , dan dinotasikan b f a . Himpunan imej dari semua anggota A disebut imej dari f dan dinotasikan Im( f ). Jelas bahwa Im( f ) B . 2.1.2
Sifat-sifat fungsi
Ada 3 (tiga) sifat fungsi yang sangat penting, yaitu: injektif (satu-satu atau 1-1), surjektif (onto), dan bijektif (korespondensi satu-satu). a. Injektif Definisi 1.2 (Menezes et al. 1996) Suatu fungsi f : A B disebut fungsi satu-satu (1-1) jika setiap anggota dari B merupakan imej dari paling banyak satu anggota A . Dari definisi tersebut, jelas bahwa untuk fungsi f : A B yang injektif A B (kardinalitas A harus sama dengan B atau kardinalitas B melebihi A ). b. Surjektif (onto) Definisi 1.3 (Menezes et al. 1996) Suatu fungsi f : A B disebut fungsi onto jika setiap anggota dari B merupakan imej dari paling sedikit satu anggota A , atau Im( f )
=
B.
Dengan
kata
lain,
jika
f A B
y B x A, y f x atau b harus habis ( a sudah pasti) dan juga
artinya
B A
(kardinalitas B lebih kecil dari A ). c. Bijektif Definisi 1.4 (Menezes et al. 1996) Jika fungsi f : A B adalah fungsi satu-satu dan sekaligus fungsi onto, maka f disebut bijektif.
2.1.3
Fungsi satu arah (one-way)
Definisi 1.5 (Menezes et al. 1996) Suatu fungsi f : A B disebut dengan fungsi satuarah jika untuk setiap a A , f a adalah mudah dihitung, tetapi untuk ‘kebanyakan’
b Im f adalah secara perhitungan tak layak (computationally infeasible) dapat menentukan a A sehingga b f a . Istilah ’kebanyakan’ dalam definisi di atas mempunyai makna bahwa berdasarkan fakta bisa jadi masih ada sebagian kecil b Im f yang secara perhitungan dapat ditentukan
a A sehingga b f a . Jika dikaitkan dengan fungsi hash yang akan dibahas berikutnya, dari definisi surjektif di atas terlihat bahwa B A , b harus habis ( a sudah pasti). Ini mengandung arti bahwa berapapun banyaknya A harus dipasangkan ke B dan keduanya harus habis. Hal ini mengakibatkan a A bisa dipasangkan dengan berapapun banyaknya b B . Banyaknya pasangan inilah yang mengakibatkan adanya tumbukan (collision) (Ilustrasinya dapat dilihat pada Gambar 1). Sebelum fungsi hash dibahas secara detail dan mengacu pada pengertian-pengertian fungsi di atas maka secara umum sifat fungsi hash yaitu fungsi yang tidak bijektif tetapi surjektif, fungsi satu arah (one-way), dan tahan tumbukan.
A B 1. 2. 3. 4. 5. . . . 1000
.A .B .C . . . .Z
Terlihat bahwa ujung anak panah berhimpit menunjukkan terjadi tumbukan (collision).
Gambar 1 Contoh tumbukan (collision) dengan fungsi
A seribu bilangan asli pertama B dua puluh enam abjad inggris
2.2
f :AB
di mana dan
Fungsi Hash Salah satu primitif kriptografi modern adalah fungsi hash kriptografi, seringkali
disebut fungsi hash satu-arah. Berikut diberikan definisi sederhana fungsi hash (tidak harus satu-arah). Definisi 1.6 (Menezes et al. 1996) Fungsi hash adalah fungsi yang secara komputasi efisien memetakan bitstring dengan panjang sembarang ke bitstring dengan panjang tetap yang disebut nilai-hash (hash-value). Untuk fungsi hash dengan output nilai-hash n-bit (yaitu n = 128 atau 160), probabilitas pemilihan string secara random yang dipetakan ke nilai-hash n-bit adalah 2-n. Berdasarkan definisi di atas, ide dasar dari fungsi hash adalah membuat string input menjadi teratur rapat dengan panjang seragam. Terkait dengan kegunaan kriptografi, fungsi hash h dipilih sedemikian sehingga secara komputasi tak-layak (sulit) menentukan input berbeda x dan y sehingga h(x) = h(y). Secara umum fungsi hash dibagi menjadi dua kelas: fungsi hash tak berkunci (unkeyed hash function) dan fungsi hash berkunci (keyed hash function). Fungsi hash tak berkunci mempunyai spesifikasi mengatur parameter input tunggal (pesan). Fungsi hash berkunci mempunyai spesifikasi mengatur parameter dua input berbeda (pesan dan kunci). Terkait dengan klasifikasi tersebut, berikut didefinisikan fungsi hash yang lebih ditekankan pada sifat-sifatnya. Definisi 1.7 (Menezes et al. 1996) Fungsi hash adalah fungsi h yang mempunyai minimal dua sifat berikut:
1. kompresi (compression): h memetakan input x dengan sembarang panjang bit yang berhingga, ke output h(x) dengan panjang bit tetap n. 2. kemudahan komputasi (ease of computation): diketahui h dan suatu input x, h(x) mudah dihitung. Berdasarkan kegunaannya, fungsi hash dibedakan atas dua tipe: 1. MDC (manipulation detection code) atau message integrity code (MIC) merupakan subkelas dari fungsi hash tak berkunci. Tujuan dari MDC, dikaitkan dengan suatu mekanisme, adalah untuk memberikan jaminan integritas data sebagaimana diperlukan dalam suatu aplikasi khusus, khususnya dalam aplikasi skema digital signature. Pada MDC ini input dari fungsi hash hanyalah pesan yang akan dikirim dan tidak membutuhkan input kunci rahasia. Dua bahasan yang termasuk dalam MDC: (a).
fungsi hash satu-arah (one-way hash function - OWHF); fungsi hash ini mempunyai sifat bahwa diketahui suatu nilai-hash untuk menentukan sembarang inputnya adalah tak layak.
(b)
fungsi hash tahan tumbukan (collision resistant hash function - CRHF); fungsi hash ini mempunyai sifat bahwa diketahui suatu nilai-hash untuk menentukan sembarang dua inputnya adalah tak layak.
2. MAC (message authentication code) merupakan subkelas dari fungsi hash berkunci. MAC adalah fungsi hash untuk otentikasi data dengan teknik simetrik . MAC mempunyai dua parameter berbeda, yaitu: input pesan dan kunci rahasia. Sesuai dengan namanya, tujuan MAC (tanpa terkait dengan mekanisme yang lain) adalah untuk menjamin integritas pesan dan asal pesan. Menyambung dua sifat pada Definisi 1.2, berikut ini diberikan tiga sifat penting untuk fungsi hash tak berkunci h dengan input x, x’ dan output y, y’: 1. ketahanan preimej (preimage resistance): jika diketahui sembarang nilai-hash y, maka secara perhitungan tak layak mencari x’ sehingga h(x’) = y. Istilah lain untuk ketahanan preimej adalah satu-arah (one-way). 2. ketahanan preimej kedua (2nd-preimage resistance): jika diketahui x, maka secara perhitungan tak layak mencari x’ x sehingga h(x’) = h(x). Istilah lain untuk ketahanan preimej kedua adalah ketahanan tumbukan lemah (weak collision resistance). 3. ketahanan tumbukan (collision resistance): secara perhitungan tak layak mencari dua input berbeda x, x’ sehingga h(x’) = h(x). Istilah lain untuk ketahanan tumbukan adalah ketahanan tumbukan kuat (strong collision resistance).
Definisi 1.8 (Menezes et al. 1996) One Way Hash Function (OWHF) adalah fungsi hash dengan dua sifat pada Definisi 1.7 ditambah sifat ketahanan preimej dan ketahanan preimej kedua. Istilah lain untuk OWHF adalah fungsi hash satu-arah lemah. OWHF adalah fungsi hash yang bekerja dalam satu arah artinya pesan yang sudah diubah menjadi nilai hash sulit dikembalikan lagi menjadi pesan semula (irreversible). Definisi 1.9 (Tilborg 2005) One Way Hash function (OWHF) adalah suatu fungsi h yang memenuhi kondisi-kondisi sebagai berikut:
input x dengan panjang sembarang dan hasil h(x) mempunyai panjang n bit yang tetap,
fungsi hash menjadi satu arah (one way) jika diberikan suatu y dalam h, ini adalah komputasional yang tak layak untuk memperoleh x sehingga h(x)=y dan jika diberikan x dan h(x) maka secara perhitungan tak layak untuk memperoleh suatu pesan x x’ sehingga h(x) = h(x’).
Definisi 1.10 (Menezes et al. 1996) Collision Resistance Hash Function (CRHF) adalah fungsi hash dengan dua sifat pada Definisi 1.7 ditambah sifat ketahanan preimej kedua dan ketahanan tumbukan. Istilah lain untuk CRHF adalah fungsi hash satu-arah kuat. Definisi 1.11 (M. Stamp dan R. M. Low 2007) Suatu kriptografi fungsi hash, dinotasikan dengan h( x) , harus memenuhi semua yang berikut:
Kompresi (compression): untuk sebarang input x , output y h( x ) adalah kecil. Pada umumnya kriptografi fungsi hash menghasilkan suatu ukuran output yang tetap, bagaimanapun juga panjang input, dengan tipe panjang output 128 sampai 512 bit.
Efisiensi (efficiency): efisien menghitung h( x) untuk sebarang input x . Perhitungan bergantung pada panjang x .
Satu arah (one-way): Secara perhitungan infisibel menginverskan suatu hash. Diberikan y, tidak dapat mencari nilai x sedemikian sehingga h ( x ) y .
Tahan tumbukan lemah (weak collision resistance): diberikan x dan h( x) , secara perhitungan infisibel untuk mencari sebarang w , dengan w x , sedemikian sehingga h( w) h( x ) .
Tahan tumbukan kuat (strong collision resistance): secara perhitungan infisibel untuk mencari pasangan x dan w , dengan x w , sedemikian sehingga
h ( x ) h ( w) . Definisi 1.12 (ANSI X9.62, 1998) Cryptographic Hash Function. Suatu fungsi matematika yang memetakan nilai-nilai dari yang berukuran besar (large domain) ke
nilai-nilai yang berukuran lebih kecil (smaller range). Fungsi tersebut mempunyai sifatsifat sebagai berikut:
Secara komputasional yang tidak mungkin untuk memperoleh sembarang input yang dipetakan ke sembarang output yang ditentukan sebelumnya.
Secara komputasional yang tidak mungkin untuk memperoleh sembarang dua input yang berbeda yang dipetakan ke sembarang output yang sama. Secara umum, klasifikasi kriptografi fungsi hash adalah sebagai berikut: hash functions
unkeye d
modification detection (MDCs)
OWHF
other aplication
keyed
other aplication
message authenticati on (MACs)
CRHF
preimage 2nd preimage
collision
Gambar 2 Klasifikasi sederhana dari kriptografi fungsi hash dan aplikasinya (Gambar 9.1, Handbook Applied of Cryptographi, Halaman 324) 2.3
Konstruksi Umum Fungsi Hash Kebanyakan fungsi hash h didesain melalui proses iteratif yang menginputkan
bitstring dengan panjang sembarang dan mengoutputkan bitstring dengan panjang tetap. Misalkan x adalah bitstring dengan panjang sembarang |x| = b; nilai hash h(x) adalah bitstring dengan panjang tetap |h(x)| = m dihitung melalui tahapan proses berikut ini: 1. Proses Penambahan Bit Ekstra (padding). Input x dibagi menjadi t blok, x = x1x2x3…xt,
yang setiap blok xi mempunyai panjang |xi| = r. Dalam hal b bukan kelipatan dari r, dilakukan proses penambahan bit ekstra (padding) agar blok terakhir mempunyai panjang r: Sering juga ditambahkan blok ekstra xt+1 sebagai representasi biner rata kanan dari b. Blok ini menyimpan informasi panjang x yang asli. 2. Proses Kompresi. Setiap blok xi akan bertindak sebagai input dari fungsi kompresi f yang menghitung secara iteratif dengan rumusan H0 = V I; Hi = f(Hi-1,xi); 1 i t. H0 adalah vektor inisial yang nilainya didefinisikan sebelumnya, Hi adalah nilai berantai yang disebut variabel berantai (chainning variable) merupakan bitstring dengan panjang |Hi| = n. Output dari proses ini adalah Ht. Sebagai contoh: untuk t = 5, H1 = f(Ho, x1); H2 = f(H1, x2); H3 = f(H2, x3); H4 = f(H3, x4); dan H5 = f(H4, x5). 3. Proses Finalisasi. Proses ini sifatnya opsional, yaitu metransformasikan Ht oleh fungsi g ke bitstring dengan panjang m, h(x) = g(Ht); |h(x)| = m Jika proses ini tidak dilakukan berarti g adalah fungsi identitas, yaitu g(Ht) = Ht. Pendefinisian komponen-komponen proses di atas, harus dipertimbangkan sifat keamanan dari h, yaitu sebagai fungsi satu arah dan tahan tumbukan. Misalnya, agar tahan terhadap serangan hari lahir (birthday attack), dianjurkan m cukup besar. Hal ini bisa dilakukan dengan mendefinisikan h(x) = Ht-1||Ht.
Gambar berikut adalah model/konstruksi umum suatu iterasi fungsi hash: input x
fungsi hash h
Preprocessing (sebelum proses) menambahkan bit ekstra
menambahkan panjang blok
format input x = x1x2…xt
proses iterasi fungsi kompresi f xi
Hi-1 f
Hi
Ho = VI
Ht g
output h(x) = Gambar 3 Model umum suatu iterasi fungsi hash (Gambar 9.2.b, Handbook Applied of Cryptographi, Halaman 332) Suatu fakta menyatakan bahwa fungsi kompresi yang tahan tumbukan dapat digunakan untuk mengonstruksi fungsi hash tahan tumbukan. Fakta ini dirinci dalam algoritme berikut. Algoritme 1 (Merkle meta-method for hashing) (Menezes et al. 1996) INPUT: Fungsi kompresi tahan tumbukan f yang memetakan string (n+r)-bit ke string nbit. OUTPUT: Fungsi hash h yang tahan tumbukan. 1. Dipecah x menjadi x = x1x2x3…xt dengan |xi| = r. Jika r b; lakukan padding pada xt dengan bit-0 agar |xt| = r.
2. Definisikan blok ekstra xt+1 = (b)2 sebagai representasi biner rata kanan (anggap sebelumnya bahwa b < 2r). 3. Definisikan nilai hash n-bit sebagai h(x) = Ht+1 = f(Ht||xt+1) dihitung dari H0 = 0n; Hi = f(Hi-1||xi); 1 i t + 1. Catatan bahwa 0n adalah string n-bit yang semua simbolnya 0. Metode padding diberikan dalam dua algoritme berikut. Algoritme 2 (Metode Padding 1) (Menezes et al. 1996) INPUT: Bitstring x dengan panjang bebas. OUTPUT: Bitstring x’ dengan panjang kelipatan dari r. 1. Rangkaikan pada x dengan string bit-0 sehingga menjadi bitstring x’ dengan panjang kelipatan dari r. Algoritme 3 (Metode Padding 2) (Menezes et al. 1996) INPUT: Bitstring x dengan panjang bebas. OUTPUT: Bitstring x’ dengan panjang kelipatan dari r. 1. Rangkaikan pada x dengan satu bit-1. 2. Kemudian, rangkaikan dengan string bit-0 sehingga menjadi bitstring x’ dengan panjang kelipatan dari r. Metode padding 1 menimbulkan kerancuan karena batasan antara bitstring sebelum dan sesudah padding tidak bisa dibedakan kecuali kalau bitstring sebelum padding diketahui panjangnya. Hal ini tidak terjadi pada metode padding 2, bahkan ketika panjang dari x sudah merupakan kelipatan dari r, padding pada x menciptakan blok ekstra. 2.4. Deskripsi Umum MD5 MD5 (message digest five) adalah fungsi hash yang didesain oleh Ron Rivest sebagai versi penguatan dari MD4. Sejak pertama kali dipublikasikan telah ditemukan beberapa kelemahan. Pada penelitian ini akan dianalisis syarat cukup dipenuhinya karakteristik kriptanalisis diferensial dari salah satu serangan pada MD5 dari Artikel Xiaoyun Wang dan Hongbo Yu. Inti dari serangan ini adalah mencari pasangan (M0, M1) dan (M0’, M1’) sehingga:
(a, b, c, d ) MD5 (a 0 , b0 , c0 , d 0 , M 0 ) (a' , b' , c' , d ' ) MD5 (a 0 , b0 , c0 , d 0 , M 0 ' ) MD5 ( a, b, c, d , M 1 ) MD5 ( a' , b' , c' , d ' , M 1 ' )
Sebelum membahas bagaimana serangan diferensial dilakukan pada MD5, akan dijelaskan dulu struktur MD5. Secara umum, fungsi hash diiterasikan oleh fungsi kompresi X = f (Z) yang mengompres blok pesan Z berukuran l bit menjadi nilai hash X berukuran s bit, dengan s < l. Untuk MD5, nilai l = 512 bit dan s = 128 bit, dan metode iterasinya menggunakan MerkleDamgard Meta Method. Untuk suatu pesan yang telah dilipatkan (padded message) M, berarti mempunyai panjang kelipatan dari l, proses iterasinya dinyatakan sebagai:
H i 1 f H i , M i , 0 i t 1 Dengan
menggunakan
fungsi
H i 1 f H i , M i ; 0 i t 1 , maka proses
iterasinya:
H 1 f H o , M o H 2 f H 1 , M 1
H 3 f H 2 , M 2 : H t f H t 1 , M t 1 Dalam hal tersebut M M 0 , M 1 ,..., M t 1 dan H 0 adalah nilai awal fungsi. Catatan bahwa sebelum proses iterasi dilakukan, terlebih dahulu dilakukan proses padding, yang pada tulisan ini tidak diberikan karena tidak mempengaruhi serangan. Pada MD5, setiap blok pesan Mi berukuran 512 bit dibagi ke dalam 16 kata mj berukuran 32 bit, yaitu:
M i m0 , m1 ,..., m15 sehingga bisa ditulis sebagai berikut: 512 bit bit 512 bit 512 bit 512 M M o , M 1 , M 2 , ..., M t 1
mo , m1 , m2 ,..., m15 mo , m1 , m2 ,..., m15
mo , m 15 1 , m 2 ,..., m
1 kata ( 32 bit ) 1 kata ( 32 bit ) 1 kata( 32 bit )
1 kata ( 32 bit )
dst.
Output dari Mo adalah: a 16 , b16 , c16 , dan d 16 Untuk selanjutnya output ini adalah nilai dari H1. Analog juga untuk blok pesan M1 dikompres dengan a 16 , b16 , c16 , dan d 16 sebagai nilai awal, sehingga output dari komputasi 16 langkah pada ke-4 ronde untuk memproses M1 adalah a 32 , b 32 , c 32 , dan d 32 . Untuk selanjutnya output ini adalah nilai awal dari H2. Dan H2 ini adalah nilai awal dari H3. Demikian seterusnya untuk blok pesan M2, M3, ... , Mt-1. Algoritme kompresi untuk Mi dilakukan dalam 4 ronde, masing-masing melibatkan 16 operasi. Operasi yang dilibatkan: "+" (jumlah modulo 232), " " (disjungsi ekslusif atau Xor), operasi logika per bit ( "" adalah operasi konjungsi, "" adalah operasi disjungsi inklusif, dan "" adalah negasi), " " (rotasi geser kiri putar). Berikut ini diberikan deskripsi lengkap untuk memproses M0.
Diberikan nilai awal variabel rantai: a = 0x67452301, b = 0xefcdab89, c = 0x98badcfe, d = 0x10325476
Menggunakan fungsi ronde tak linear dengan rumus:
i X ,Y , Z
X Y X Z , 0 i 15 X Z Y Z , 16 i 31 X Y Z,
32 i 47
Y X Z ,
48 i 63
Ket.: Pada buku Applied Cryptanalysis (Mark Stamp dan Richard M. Low, 2007), fungsi ronde tak linear ditulis:
F X , Y , Z X Y X Z , 0 i 15 G X , Y , Z X Z Y Z , 16 i 31
H X ,Y , Z X Y Z ,
32 i 47
I X , Y , Z Y X Z ,
48 i 63
di mana: X , Y , Z adalah kata-kata 32 bit.
Komputasi 16 langkah pada Ronde-1:
a b a 0 b, c, d m0 0 xd 76aa 478 7
d a d 1 a, b, c m1 0 xe8c7b756 12
c d c 2 d , a, b m2 0 x 242070db 17
b c b 3 c, d , a m3 0 xc1bdceee 22
a b a 4 b, c, d m4 0 xf 57c0 faf 7
d a d 5 a, b, c m5 0 x 4787c62a 12
c d c 6 d , a, b m6 0 xa8304613 17
b c b 7 c, d , a m7 0 xfd 469501 22 a b a 8 b, c, d m8 0 x698098d 8 7
d a d 9 a, b, c m9 0 x8b44 f 7 af 12
c d c 10 d , a, b m10 0 xffff 5bb1 17
b c b 11 c, d , a m11 0 x895cd 7be 22 a b a 12 b, c, d m12 0 x6b901122 7
d a d 13 a, b, c m13 0 xfd 987193 12
c d c 14 d , a, b m14 0 xa679438e 17
b c b 15 c, d , a m15 0 x 49b40821 22
Komputasi 16 langkah pada Ronde-2:
a b a 16 b, c, d m1 0 xf 61e2562 5
d a d 17 a, b, c m6 0 xc040b340 9
c d c 18 d , a, b m11 0 x 265e5a51 14
b c b 19 c, d , a m0 0 xe9b6c7 aa 20 a b a 20 b, c, d m5 0 xd 62 f 105d 5
d a d 21 a, b, c m10 0 x02441453 9
c d c 22 d , a, b m15 0 xd 8a1e681 14
b c b 23 c, d , a m4 0 xe7d 3 fbc8 20 a b a 24 b, c, d m9 0 x 21e1cde6 5
d a d 25 a, b, c m14 0 xc33707 d 6 9
c d c 26 d , a, b m3 0 xf 4d 50d 87 14
b c b 27 c, d , a m8 0 x 455a14ed 20 a b a 28 b, c, d m13 0 xa9e3e905 5 d a d 29 a, b, c m2 0 xfcefa3 f 8 9
c d c 30 d , a, b m7 0 x676 f 02d 9 14
b c b 31 c, d , a m12 0 x8d 2a 4c8a 20
Komputasi 16 langkah pada Ronde-3:
a b a 32 b, c, d m5 0 xfff 23942 4
d a d 33 a, b, c m8 0 x8771 f 681 11
c d c 34 d , a, b m11 0 x 6d 9d 6122 16
b c b 35 c, d , a m14 0 xfde5380c 23 a b a 36 b, c, d m1 0 x 4abeea44 4
d a d 37 a, b, c m4 0 x 4bdecfa9 11
c d c 38 d , a, b m7 0 xf 6bb4b60 16
b c b 39 c, d , a m10 0 xbebfbc70 23 a b a 40 b, c, d m13 0 x 289b7ec6 4
d a d 41 a, b, c m0 0 xeaa127 fa 11
c d c 42 d , a, b m3 0 xd 4ef 3085 16
b c b 43 c, d , a m6 0 x04881d 05 23
a b a 44 b, c, d m8 0 xd 9d 4d 039 4
d a d 45 a, b, c m12 0 xe6db99e5 11
c d c 46 d , a, b m15 0 x1 fa 27cf 8 16
b c b 47 c, d , a m2 0 xc 4aac5665 23
Komputasi 16 langkah pada Ronde-4:
a b a 48 b, c, d m0 0 xf 4292244 6
d a d 49 a, b, c m7 0 x 432aff 97 10
c d c 50 d , a, b m14 0 xab9423a7 15
b c b 51 c, d , a m5 0 xfc93a039 21
a b a 52 b, c, d m12 0 x655b59c3 6
d a d 53 a, b, c m3 0 x8 f 0ccc92 10
c d c 54 d , a, b m10 0 xffeff 47d 15
b c b 55 c, d , a m1 0 x85845dd 21
a b a 56 b, c, d m8 0 x6 fa87e4 f 6
d a d 57 a, b, c m15 0 xfe2ce6e0 10
c d c 58 d , a, b m6 0 xa3014314 15
b c b 59 c, d , a m13 0 x 4e0811a1 21
a b a 60 b, c, d m4 0 xf 7537e82 6
d a d 61 a, b, c m11 0 xbd 3af 235 10
c d c 62 d , a, b m2 0 x 2ad 7 d 2bb 15
b c b 63 c, d , a m9 0 xeb86d 391 21
Secara sama, blok pesan M1 dikompres dengan nilai a, b, c, dan d adalah output dari kompresi blok pesan M0. Demikian seterusnya, untuk blok pesan M2, M3, ..., Mt-1. 2.5
Modular dan XOR Operasi modular adalah operasi dengan menggunakan perpangkatan 2 atau operasi
modulo. Di sisi lain untuk operasi exclusive or (Xor) atau biasa ditulis "" sama artinya dengan operasi modulo 2 , di mana bernilai 1 jika dan hanya jika tepat satu dari kedua operand bernilai 1. Tabel nilai Xor: A
B
A B
0
0
0
0
1
1
1
0
1
1
1
0
Tabel 1 Tabel Xor operasi biner 2.6
Diferensial Modular dan Xor Metode analisis terpenting untuk fungsi hash adalah serangan diferensial yang juga
merupakan salah suatu metode terpenting untuk serangan sandi blok. Serangan diferensial pertama kali diperkenalkan oleh E. Biham dan A. Shamir untuk menganalisis DES-like dengan mengesploitasi karakteristik operasi Xor. Definisi diferensial dalam tulisan ini adalah eksploitasi kombinasi dari beda (differences) dalam operasi substraksi intejer modular dan operasi Xor. Kombinasi yang demikian akan memberikan informasi lebih banyak dari pada eksploitasi yang dilakukan pada masing-masing operasi secara terpisah. Sebagai contoh, beda substraksi intejer modular X ' X 26 untuk suatu nilai X , maka beda Xor X ' X bisa mempunyai banyak kemungkinan yang dijelaskan sebagai berikut: 1. Beda 1 bit di posisi 7, berarti bit ke-7 dalam X ' adalah 1, bit ke-7 dalam X adalah 0, dan X ' X 26 . Dalam kasus modulo 232, banyaknya pasangan X , X ' yang memenuhi X ' X 26 mod 232 dan X ' X 26 adalah 231.
2. Beda 2 bit di posisi 7 dan 8, berarti bit ke-7 dan ke-8 dalam X ' adalah 01, bit ke-7 dan ke-8 dalam X adalah 10, dan X ' X 2 7 2 6 . Dalam kasus modulo 232, banyaknya
pasangan
X , X '
yang
X ' X 26 mod 232
memenuhi
dan
X ' X 27 26 adalah 230. 3. Beda 3 bit di posisi 7, 8, dan 9, berarti bit ke-7, ke-8 dan ke-9 dalam X ' adalah 001, bit ke-7, ke-8, dan ke-9 dalam X adalah 110, dan X ' X 28 27 26 . Dalam kasus
modulo
232,
banyaknya
pasangan
X , X '
yang
memenuhi
X ' X 26 mod 232 dan X ' X 28 27 26 adalah 229. 4. Secara umum, untuk beda s bit di posisi 7 sampai dengan 7 s 1 , berarti s bit dalam X ' adalah 000...01 dan s bit dalam X adalah 111...10. Dalam kasus modulo 232, banyaknya pasangan
X , X '
yang memenuhi
X ' X 26 mod 232 dan
X ' X 26 s 1 26 s 2 ... 27 26 adalah 232 s , untuk 1 s 26 . 5. Dalam kasus beda negatif, sebagai misal X ' X 26 , beda XOR X ' X mempunyai nilai pola yang sama, yaitu dengan menukar pengurangan X X ' 26 , dalam hal ini s bit dalam X ' adalah 111...10 dan s bit dalam X adalah 000...01. Perhatikan bahwa:
X ' X 2t mod 232 X ' X 231 230 ... 2t 1 2t Untuk menjelaskan serangan diferensial yang dilakukan pada MD5 mengacu pada beda modular di dalam jalur diferensial pada tabel.1. Tabel ini mendaftarkan kedua macam beda secara bersama-sama, menggunakan tanda positif dan negatif untuk intejer modulo 232 dan Xor. Beda Xor didaftarkan sebagai bit aktif beserta tandanya, bit-bit 0 dalam X diberikan tanpa tanda dan bit-bit 1 dalam X diberi tanda negatif. Sebagai contoh, beda:
26 , 7,8,9,...,22,23 Menandakan substraksi intejer modular X ' X 26 (dalam hal ini X X ' ) dengan beda XOR:
X ' X 2 22 2 21 ... 27 26 , posisi bit ke-7 sampai dengan ke-22 adalah 0 dan ke-23 adalah 1 dalam X , sedangkan dalam X ' posisi bit ke-7 sampai dengan ke-22 adalah 1 dan ke-23 adalah 0. 2.7
Serangan Diferensial pada Fungsi Hash
Beda (difference) parameter untuk dua parameter X dan X’ didefinisikan sebagai beda modular ∆X = X’ – X Sembarang dua pesan M dan M’ dengan panjang kelipatan l bit, dituliskan sebagai barisan blok dengan panjang l bit M = (M0, M1, M2, ..., Mk-1) M’ = (M0’, M1’, M2’, ..., Mk-1’) Diferensial penuh untuk suatu fungsi hash didefinisikan M 0 , M 0 ' M k 1 , M k 1 M1 ,M1 M 2 ,M 2 H 0 H1 H 2 ... H '
'
'
dimana ∆H0 adalah beda nilai awal yang jelas sama dengan nol. ∆H merupakan beda output dari dari dua pesan yang bersangkutan. ∆Hi = ∆VIi adalah beda output pada iterasi ke-i yang juga merupakan beda inisial untuk iterasi berikutnya. Jelas bahwa jika ∆H = 0 atau H i H i ' H i 0 , maka terjadi tumbukan antara M dan M’. Diferensial yang menghasilkan tumbukan disebut tumbukan diferensial (collision differential). Diberikan fungsi hash yang mempunyai 4 ronde, dan setiap ronde mempunyai 16
'
M i ,M i langkah, maka diferensial iterasi ke-i, H i H i 1 , dapat dirinci dalam 4
ronde sebagai berikut: P3 P1 P2 P4 H i Ri 1,1 Ri 1, 2 Ri 1,3 Ri 1, 4 H i 1
dengan 0 i 15 . Ri 1,1 adalah langkah ke-i+1 ronde pertama, dan seterusnya. P
j Diferensial ronde R j 1 R j , untuk j = 1,2,3,4, dengan probabilitas Pj , dapat
dirinci ke dalam karakteristik diferensial 16 langkah sebagai berikut: P
P
P
P
j1 j2 j3 j 16 R j 1 X 1 X 2 ... X 16 R j
P
jt X t , untuk t = 1,2,3,...,16, merupakan karakteristik diferensial di mana X t 1
dalam langkah ke-t pada ronde ke-j.
M
'
i Probabilitas P dari diferensial H i i H i 1 memenuhi:
,M
P j 1 Pj dan Pj t 1 Pjt 16
4
Ada dua macam modifikasi pesan untuk mengoptimalkan diferensial tumbukan: 1
'
Untuk sembarang pasangan blok pesan M i , M i dan diferensial tak nol pada ronde pertama:
M i ,M i H i Ri 1,1 '
M i dapat dengan mudah dimodifikasi untuk menjamin bahwa diferensial pada ronde pertama tersebut mempunyai probabilitas P1 1 . 2
Dengan menggunakan teknik modifikasi multi-pesan, diferensial pada ronde pertama tidak hanya mempunyai probabilitas 1, tetapi juga dapat memperbesar probabilitas diferensial pada ronde kedua. Untuk mengoptimalkan diferensial suatu fungsi hash, sebaiknya dipilih beda blok
pesan yang menghasilkan diferensial dua ronde terakhir mempunyai probabilitas yang tinggi. 2.8
Penotasian Serangan Diferensial pada MD5 Sebelum menjelaskan bagaimana serangan diferensial dilakukan pada MD5,
diperkenalkan terlebih dahulu notasi-notasi yang digunakan untuk memudahkan pembahasan. 1
M m0 , m1 ,..., m15 dan M ' m0 ' , m1 ' ,..., m15 ' merepresentasikan dua blok pesan 512 bit. M m0 , m1 ,..., m15 menotasikan beda dua blok pesan yang bersangkutan.
2
ai , bi , ci , d i secara berurutan menotasikan output langkah ke- 4i 3 , ke- 4i 2 , ke- 4i 1 dan ke- 4i untuk mengompresi M , di mana 1 i 16. ai ' , bi ' , ci ' , d i ' didefinisikan serupa.
3
ai , j , bi , j , ci , j , d i , j secara berurutan merepresentasikan bit ke- j dari ai , bi , ci , d i , di mana bit paling signifikan adalah bit ke-32 dan yang paling tidak signifikan adalah bit ke-1.
4
i , j adalah output bit ke- j dari fungsi i pada operasi langkah ke- i .
5
xi , j xi , j ' xi , j 1 adalah beda bit yang dihasilkan dengan mengubah bit ke- j dari xi . Notasi xi j dan xi j , x bisa berupa a, b, c, d atau , merupakan hasil dari perubahan bit ke- j tersebut dari kata xi .xi j diperoleh dari mengubah bit ke-
j untuk xi dari bit 0 ke bit 1, xi j diperoleh dari mengubah bit ke- j untuk xi dari bit 1 ke bit 0. 6.
xi j1 , j2 ,..., jt xi j1 , j2 ,..., jt xi adalah beda yang diperoleh dengan mengubah bit ke- j1 , ke- j2 , ..., ke- jt dari xi . Sedangkan, xi j1 , j2 ,..., jt adalah hasil dari
pengubahan tersebut. Tanda ”+” (biasanya tidak dituliskan) adalah pengubahan dari bit 0 ke 1, sebaliknya tanda ”-” adalah pengubahan dari bit 1 ke 0. 2.9
Diferensial Tumbukan untuk MD5 Dalam tulisan ini dipilih diferensial tumbukan dengan dua iterasi sebagai berikut: M 0 , M 0 ' M 1 , M 1 ' H 0 H1 H 0
di mana
M 0 M 0 ' M 0 0,0,0,0,231 ,0,0,0,0,0,0,215 ,0,0,231 ,0
M 1 M 1 ' M 1 0,0,0,0,231 ,0,0,0,0,0,0,215 ,0,0,231 ,0 H1 231 ,231 225 ,231 225 ,231 225 Isian tak-nol dari M 0 dan M1 dilokasikan pada posisi 5, 12 dan 15.
H1 a, b, c, d adalah beda 4 nilai berantai a, b, c, d setelah iterasi pertama. Dalam tulisan ini juga dipilih M 0 untuk menjamin bahwa diferensial pada ronde 3-4 terjadi dengan probabilitas tinggi. M1 dipilih tidak hanya untuk menjamin bahwa diferensial pada ronde 3-4 terjadi dengan probabilitas tinggi, tetapi juga menghasilkan beda output yang bisa dibatalkan dengan beda output H1 . 2.10 Langkah-langkah untuk Syarat Cukup Dipenuhinya Karakteristik Diferensial pada MD5 Pengerjaan langkah-langkah ini mengacu pada karakteristik diferensial iterasi pada Lampiran 1. Target hasil yang diharapkan seperti pada Lampiran 2 (bisa jadi nilainilainya berbeda). Sebagai contoh penentuan syarat cukup pada langkah ke-5, Lampiran 1. Diketahui
s4
=
7,
a2 [23, 22, ..., 7]
w4 m4 'm4 = 231, yang
menandakan
beda
a2 a2 'a2 tanda
perubahan
menggunakan iterasi langkah ke-2 pada ronde pertama, m4 R1 [a1 , b1 , c1 , d1 ] R2,1 [d1 , a 2 , b1 , c1 ] m4 ' R1 ' [a1 ' , b1 ' , c1 ' , d1 ' ] R2,1 ' [d1 ' , a 2 ' , b1 ' , c1 ' ]
dan
=
-26, bit.
dan Dengan
a 2 b1 a1 4 b1 , c1 , d1 m4 0 xf 57c0 faf 7 K4
dan W4 = a1 4 (b1 , c1 , d1 ) t 4 sehingga a2 dan a2’ dapat ditulis,
a 2 b1 ( K 4 7)
b1’ = b1
a 2 ' b1 ( K 4 ' 7)
Karena w4 2 31 maka w4,32 1 dan m 4,i m 4,i ' untuk 1 ≤ i ≤ 31. Syarat cukup agar a2 [23, 22, ..., 7] terjadi, maka a 2 b1 ( K 4 7) maka
a 2 (b1 ( K 4 7)) . Penentuan posisi bitnya, yaitu Posisi bit b1
32
...
24
23
22
...
8
7
6
...
1
Posisi bit K4 <<<7
25
...
17
16
15
...
1
32
31
...
26
sehingga, posisi bit a2 sama dengan b1 dan m4 sama dengan K4. Karena b1 = b1’ dan m4 = 231 menyebabkan K4, sebarang m4,
26-31
26-31
= K4’,26-31, maka pengambilan
dijamin tidak menyebabkan perubahan bit pada a2,
1-6.
Hasil
penghitungan ini mengandung nilai bawaan pada bit ke-7 untuk a2 dinotasikan dengan s7. Dalam kasus ini s7’ = s7.
Untuk pengambilan pasangan m 4,32 , m' 4,32
dengan
w4,32 1 dijamin menyebabkan
perubahan bit pada a2,7, karena b1 = b1’ dan w4,32 1 menyebabkan K 4 ,32 1 . Agar terjadi perubahan bit dari a2,7 = 0 ke a2,7’ = 1, maka b1, 7 K 4,32 s 7 0 . Dan disubstitusi s7 =0 dan s7 = 1 untuk memperoleh nilai s8 dan s8’. Kemudian penentuan posisi bit ke-8 sampai dengan ke-23 untuk a2, yaitu Posisi bit
23
22
21
…
8
a2’
0
1
1
…
1
a2
1
0
0
…
0
di mana syarat cukup terjadinya perubahan bit adalah
b1,8 23 K 4,116 s8 215 mod 216 dan
b '1,8 23 K ' 4,116 s8 ' ( 215 1) mod 216 Karena b '1,8 23 K ' 4,116 b1,8 23 K 4,116 , maka haruslah s8’ = s8 1 dan pada kondisi ini menghasilkan s24 = s24’. Perubahan posisi bit dijamin terpenuhi jika: 1). s 7 0, b1, 7 1, s 8 1, dan K 4,32 1 atau, 2). s 7 1, b1, 7 0, s 8 1, dan K 4,32 1 .
K 4 ,32 1
Dari
diperoleh
W4,32 m 4,32 r32 1
persamaan,
m 4,32 a1,32 4,32 t 4,32 r32 1 di mana r32 adalah simpanan dari penghitungan K4, 26-31. Dari
b1,8 23 K 4,116 s8 215 mod 216
persamaan
diperoleh
m4,116 [215 b1,823 W4,116 1] mod 216 . Karena s24 = s24’ dan b1’ = b1 dan semua operand penyusun K4,17-25 sama maka pada posisi bit ke-24 sampai bit ke-32 untuk a2 dijamin tidak terjadi perubahan bit apapun pilihan m4, 17-25. Secara umum langkah-langkah syarat cukupnya adalah sebagai berikut: m0 mt m1 m2 M m0 , m1 ,.... , mt → H 0 H 1 H 2 ... Ht m0 ' mt ' m1 ' m2 ' M ' m0 ' , m1 ' , ... , mt ' → H 0 H 0 ' H 1 ' H 2 ' ... Ht '
H 0 H 0 ' H 0 0, H 1 H 1 ' H 1 , H 2 H 2 ' H 2 , ... , H t H t ' H t Jelas bahwa jika ∆H = 0 atau H i H i ' H i 0 , maka terjadi tumbukan antara M dan M’. Langkah selanjutnya H0 diproses,
a0 , b0 , c0 , d 0
m0
d0 , a1 , b0 , c0
m1
m m m a1 , b1 , c1 , d1 d1 , a2 , b1 , c1 , ... Jadi, c0 , d1 , a1, b0 b0 , c1, d1, a1 3
2
4
H1 = a1 , b1 , c1 , d1 dan seterusnya. Untuk M0 dan M1, proses iterasinya: M1 0 H 0 M H1 H
Untuk m0, m1, m2, ..., m127, dengan proses iterasinya: m0 m1 m2 15 65 64 127 H0 H1 H2 ...m H15 ...m H65 H1 m ...m H127 H
Untuk m0’, m1’, m2’, ..., m127’, dengan proses iterasinya:
m0 ' m1 ' 2' 15 ' 16 ' 65 ' 64 ' 127' H0' H1' H2 ' m ...m H15' m ...m H65' H1' m ...m H127' H'
Sehingga:
H i H i ' H i , i 0,1,2,...,127 Untuk M0 dan M0’:
M 0 m0 , m1 ,..., m15 M 0 ' m0 ' , m1 ' ,..., m15 ' M 0 m0 'm0 , m1 'm1 ,..., m15 'm15
= 0,0,0,0,2 31 ,0,0,0,0,0,0,215 ,0,0,2 31 ,0
Untuk selanjutnya, penentuan syarat cukup ini mengikuti urutan pada tabel, seperti yang ditunjukkan pada Lampiran 1 dan Lampiran 2. Hal pertama yang dilakukan adalah menunjukkan jaminan bahwa R1 0 . Berikutnya, b1, a2, dan d2. Untuk syarat cukup selanjutnya mengacu pada syarat yang sudah diperoleh Wang. 2.11 Modifikasi Algoritme Fungsi Hash MD5 Pada modifikasi algoritme ini akan dianalisis syarat cukup sampai pada c2, selebihnya mengacu pada Lampiran 1 sampai dengan Lampiran 4. Berdasarkan syarat cukup tersebut, akan dianalisis mengapa serangan diferensial berhasil untuk menyerang MD5. Setelah analisis tersebut, konstanta jumlah akan dibuat merambat, fungsi boolean tak linear akan dimodifikasi, konstanta putaran akan dibuat merambat, dan permutasi pesan juga akan dimodifikasi. Keempat elemen inilah yang dianggap merupakan kelemahan dari algoritma fungsi hash MD5. Implementasi dari modifikasi ini adalah merekonstruksi algoritme MD5 (membaharui algoritme MD5), dengan kata lain mengimplementasikan fungsi iterasi dari MD5 dan hasil modifikasi MD5. 2.12 Jenis-jenis Serangan Fungsi Hash Untuk memahami keamanan fungsi hash lebih mendalam dapat diperoleh melalui beberapa strategi serangan umum. Ketahanan dari suatu fungsi hash khusus untuk mengetahui serangan umum memberikan suatu (bagian) ukuran dari keamanan. 1
Serangan ‘Birthday’ Serangan-serangan algoritme independen adalah yang dapat diaplikasikan ke
sebarang fungsi hash, yang diperlakukan sebagai sebuah kotak-hitam yang mempunyai karakteristik signifikan keluaran dengan panjang bit n (dan panjang bit kunci MAC untuk
MACs), dan running time untuk satu operasi hash. Tipe ini mengasumsikan aproksimasi output hash sebagai suatu variabel acak seragam. (i). Serangan ‘Yuval birthday’ pada fungsi hash Serangan ’Yuval birthday’ adalah satu dari bagian pertama (dan mungkin yang paling baik) dari banyak aplikasi kriptografi dari paradoks ’birthday’ distribusi klasik: ketika mengambil elemen-elemen secara random, dengan penempatan, dari suatu himpunan N elemen., dengan probabilitas tinggi suatu elemen bisa terambil berulang maka akan kembali lagi setelah pemilihan O( N ). Dengan demikian serangannya disebut serangan-serangan akar kuadrat. Relevansi ke fungsi hash adalah bahwa lebih mudah mencari tumbukan untuk fungsi hash satu-arah daripada mencari preimage atau second preimage untuk nilai-nilai hash spesifik. Sebagai hasilnya, skema tanda tangan yang mana bekerja untuk fungsi hash satu-arah yang mungkin diserang. Serangan dapat diaplikasikan ke semua fungsi hash tak berkunci, dengan running time O(2m/2) dengan panjang bit m untuk nilai hash. Algoritma 4. (Yuval birthday) (Menezes, 1996) INPUT: Pesan sah x1 ; pesan curang x2 ; fungsi hash h satu-arah m-bit. OUTPUT: x1 ' , x2 ' hasil dari modifikasi minor x1 , x2 dengan h x1 ' h x2 ' (jadi tanda tangan pada x1 ' memberikan tanda tangan yang sah pada x2 ' ). 1. Bangkitkan t 2 m / 2 modifikasi minor x1 ' dari x1 . 2. Hash yang lain sehingga pesan termodifikasi, dan simpan nilai hash (dikelompokkan dengan menghubungkan pesan) sedemikian sehingga dapat dicari pada nilai hash. 3. Bangkitkan modifikasi minor x2 ' dari x2 , menghitung h x2 ' untuk yang lain dan mengecek pasangan dengan sebarang x1 ' yang di atas; lanjutkan sampai pasangan didapat.
(ii). Variasi tanpa memori dari ‘birthday attack’). Untuk memindahkan memori dari Algoritme 4, suatu mapping deterministic bisa digunakan yang mana mengaproximasi suatu arah random melalui ruang nilai-hash. Dengan paradox birthday, dalam arah random melalui suatu ruang dari 2m titik, satu harapan untuk menghitung beberapa titik pada waktu kedua (yaitu: memperoleh suatu tumbukan) setelah O(2m/2) langkah, setelah berjalan akan berulang (membentuk circle). Teknik mencari circle tanpa memori umum dapat dipakai untuk mencari tumbukan ini. Algoritme 4 berikutnya, ambil g suatu fungsi sedemikian sehingga g(x1,H) = x1’ adalah
modifikasi minor, yang ditentukan dengan nilai-hash H, dari pesan x1. Jika x1 sudah fix, maka g memetakan hasil-hash ke suatu pesan dan tepat untuk menulis g x1 (H) = x1’. Misal g injektif sehingga hash-hash H menghasilkan perbedaan setiap x1’-nya. Maka, pesanpesan x1, x2 yang sudah fix dan menggunakan beberapa property mudah dibedakan. Definisikan suatu pemetaan hasil-hasil fungsi hash sebagai berikut:
h( g x1 ( H )) jika H genap …………………………………… r(H ) h( g x2 ( H )) jika H ganjil
(1)
Teknik pencarian tumbukan tanpa memori digunakan untuk mencari 2 input r yang mana peta ke output yang sama (yaitu: collide). (iii). Aplikasi ilustratif MD5 Aplikasi terbaru dari serangan umum di atas ke suatu fungsi hash meningkatkan teknik-teknik tambahan. Untuk mengilustrasikan bagaimana ini bisa dialamatkan, sehingga aplikasi sekarang diuji, dengan asumsi dan pilihan dibuat serinci mungkin. Misal h suatu iterasi fungsi hash memproses pesan dalam 512-bit blok dan menghasilkan 128-bit hash (yaitu: MD5, RIPEMD-128). Untuk meminimumkan biaya perhitungan, batasi r (seefektif g dan h) di persamaan (1) ke 512-bit blok tunggal dari xi, sedemikian sehingga iterasi yang lain dari r melibatkan hanya fungsi kompresi f pada input satu blok pesan dan variabel berantai yang sekarang. Fungsi untuk mencari tumbukan r untuk contoh spesifik ini (dihubungkan dengan persamaan umum (1)) maka:
f (c1, g ( H )) jika H genap …………………………………… r(H ) f (c 2 , g ( H )) jika H ganjil Tumbukan untuk MD5 (dan menyerupai fungsi hash) dapat dicari dalam operasi O(264) dan tanpa penyimpanan yang signifikan. 2
Serangan Pseudo-Collision dan Fungsi Kompresi Nama lain dari preimage atau 2nd-preimage serangan target; pseudo-preimage
serangan target free-start; tumbukan (fixed IV) serangan tumbukan; tumbukan (random IV) serangan tumbukan semi-free-start; pseudo-collision serangan tumbukan freestart. Mencari suatu tumbukan tidak lebih sulit dari suatu 2nd-preimage. Begitu juga untuk mencari suatu pseudo-collision tidak lebih sulit dari mencari (dua perbedaan) pseudopreimage.
(2)
Definisi 1.13. (Serangan pada fungsi kompresi) (Menezes, 1996) Serangan pada fungsi kompresi dari suatu iterasi fungsi hash adalah sebarang serangan dengan f ( H i 1 , xi ) ke
h(V0 , x) -fungsi kompresi f sebagai pengganti dari fungsi hash h, variabel brrantai Hi-1 sebagai pengganti nilai awal V, dan blok input single xi sebagai pengganti dari panjang pesan x. Serangan pada fungsi kompresi memfokuskan pada satu langkah tetap i dari fungsi iterasi. Pesan terdiri atas suatu blok single xi = x (tanpa kekuatan MD)., dan output hash memberikan output fungsi kompresi sehingga h x H i . 3
Serangan Berantai Serangan-serangan berantai berdasarkan pada iterasi alami dari fungsi hash,
menggunakan variabel berantai. Fokus variabel berantai pada fungsi kompresi f lebih baik daripada fungsi hash h secara keseluruhan. Sebagai contoh, suatu (kandidat) iterasi tahan tumbukan fungsi hash h menghasilkan nilai hash 128-bit, dengan fungsi kompresi f mengambil input 512-bit blok pesan xi dan 128-bit variabel berrantai H i dan menghasilkan output H i 1 f H i , xi . Untuk 10 blok pesan x yang tetap (640 byte), dengan menganggap H h x . Misalkan satu pilihan sebarang, dengan mengambil satu dari 10 blok, dan ingin menempatkannya dengan blok yang lain tanpa mempengaruhi hash H . Jika h bersifat seperti pemetaan acak, jumlah blok-blok 512-bit adalah kira-kira 2512/2128 = 2384. (i).
Serangan berantai correcting-block. Serangan correcting block dapat digunakan untuk mencari preimage dan collision. Jika blok tanpa kendala adalah blok pertama (terakhir) dalam pesan, maka disebut serangan blok correcting pertama (terakhir).
(ii). Serangan berantai meet-in-the-middle. Serangan ini adalah serangan-serangan ‘birthday’ hampir menyerupai Yuval (yang mana dapat dibuat kurangnya memori secara esensial) tetapi terdapat tumbukan pada hasil lanjutan (yaitu, variabel berantai) lebih baik dari semua hasil (nilai) hash. (iii). Serangan berantai titik tetap. Suatu titik tetap dari suatu fungsi kompresi adalah pasangan H i 1 , xi sedemikian sehingga f H i 1 , xi H i 1 . (iv). Serangan berantai diferensial. Kriptanalisis diferensial membuktikan suatu kekuatan untuk kriptanalisis tidak hanya blok ciphers tetapi juga fungsi hash (MACs). Untuk blok cipher yang
mempunyai banyak ronde, metode serangan ini memeriksa beda input (Xors) ke fungsi ronde dan menghubungkan beda output, mencari kekurangan/kelainan secara statistik. Untuk fungsi hash, pengujian adalah dari beda input ke fungsi kompresi dan menghubungkan beda output; tumbukan dihubungkan ke suatu beda output dari 0 (nol). 4
Serangan Berdasarkan Cipher (sandi)
1.
Sifat Komplemen: y = Ek (x) y E _ ( x) , di mana x menotasikan komplemen
_
_
k
bitwise. 2.
Weak keys: Ek ( Ek ( x)) x (untuk semua x)
3.
Titik-titik tetap: Ek ( x) x
4.
Tumbukan-tumbukan kunci: Ek ( x) Ek ' ( x)
_
III HASIL DAN PEMBAHASAN Seperti yang telah disebutkan di pendahuluan bahwa sejak MD5 pertama kali dipublikasikan tahun 1992, telah ditemukan beberapa kelemahan. Kelemahan ini ditemukan oleh Wang (2004), di mana serangan yang dilakukan adalah tipe serangan diferensial. Pada artikel itu diperoleh bahwa tumbukan pada MD5 dapat dicapai secara efisien, yaitu dengan pencarian tumbukan pada blok pertama memerlukan 239 operasi MD5 dan pada blok kedua memerlukan waktu sekitar 232 operasi MD5. Berdasarkan hal tersebut maka pada bab ini akan dibahas kelemahan-kelemahannya mengacu pada penentuan analisis syarat cukup. Selanjutnya, dari hasil analisis syarat cukup tersebut akan dimodifikasi struktur algoritme fungsi hash. A
Analisis Syarat Cukup Karakteristik Diferensial Pada MD5 Analisis syarat cukup ini dilakukan untuk memodifikasi pesan sehingga
memperbesar peluang terjadinya tumbukan (collision). Untuk mencapai hal tersebut mengikuti Lampiran 1, di mana Wang mendefinisikan secara mandiri tapi tanpa ada penjelasan yang mendetail. Dalam penelitian ini, penetapan syarat cukupnya hanya sampai pada c2 (langkah ketujuh). Untuk langkah selanjutnya secara lengkap mengikuti tabel yang telah diperoleh Wang (Lampiran 2). Dengan kata lain, jika dilanjutkan maka akan diperoleh seperti tabel pada Lampiran 1 sampai Lampiran 4. Berdasarkan penelitian Wang tersebut, dapat disimpulkan bahwa pemilihan M0 untuk menjamin bahwa diferensial pada ronde ketiga sampai ronde keempat terjadi dengan probabilitas tinggi. M1 dipilih tidak hanya untuk menjamin bahwa diferensial pada ronde ketiga sampai ronde keempat terjadi dengan probabilitas tinggi, tetapi juga menghasilkan beda output yang bisa dibatalkan dengan beda output H1. Di dalam penelitian ini akan ditelusuri hasil Wang dari b0 sampai dengan c2. Dari hasil analisis ini digunakan untuk memodifikasi fungsi konstanta jumlah, konstanta putaran, permutasi blok pesan dan fungsi boolean tak linear Pada bagian ini akan dibahas bagaimana mendapatkan nilai bit-bit tertentu sebagai input yang menjamin dipenuhinya karakteristik diferensial. Agar mudah dipahami, prosesnya akan dijelaskan langkah per langkah iterasi MD5 dengan menggunakan notasi yang sudah disebutkan pada Bab II (sub bab 2.8). Jaminan ΔR1 = 0 Penulisan ulang secara berantai deskripsi MD5. Pertama, nilai awal H0 = [a0,b0,c0,d0] diperbaharui nilainya menjadi R1,1 = [d0,a1,b0,c0] dengan menggunakan kata pesan pertama m0 dan konstanta jumlah t0, dituliskan:
H0 = [a0,b0,c0,d0] → R1,1 = [d0,a1,b0,c0], dengan a1 = b0 + ((a0 + Φ0(b0,c0,d0) + m0 + t0) ⋘ 7) Karena diberikan ΔH0 = 0 dan Δm0 = 0, maka m0 = m0′ dan a0′ = a0, b0′ = b0, c0′ = c0, d0 = d0′. Akibatnya: a1′ = b0′ + ((a0′ + Φ0(b0′,c0′,d0′) + m0′ + t0) ⋘ 7) = b0 + ((a0 + Φ0(b0,c0,d0) + m0 + t0) ⋘ 7) = a1 Nilai a1 hanya bergantung pada variabel m0 karena nilai b0, a0,
adalah konstanta yang
diperoleh dari konstanta-konstanta sebelumnya. Dengan demikian, jika a1 diketahui, maka m0 dapat dihitung m0 = ((a1 – b0) ⋙ 7) – a0 – t0 – Φ0(b0,c0,d0) Langkah kedua, m1 R1,1 = [d0,a1,b0,c0] R1,2 = [c0,d1,a1,b0], dengan
d1 = a1 + ((d0 + Φ1(a1,b0,c0) + m1 + t1) ⋘ 12) Seperti pada langkah pertama mudah diamati bahwa d1=d1′, dan mudah dirunut bahwa nilai d1 bergantung pada varibel m1 dan a1 (yang berarti juga m0). Dengan pengamatan yang sama, dua langkah berikutnya dapat ditulis m2 R1,2 = [c0,d1,a1,b0] R1,3 = [b0,c1,d1,a1], dengan
c1 = c1′ = d1 + ((c0 + Φ1(d1,a1,b0) + m1 + t1) ⋘ 17) m3 R1,3 = [b0,c1,d1,a1] R1,4 = [a1,b1,c1,d1], dengan
b1 = b1′ = c1 + ((b0 + Φ1(c1,d1,a1) + m1 + t1) ⋘ 22) Diperoleh output 4 langkah pertama R1 = R1,4 = [a1,b1,c1,d1] = R1′ = [a1′,b1′,c1′,d1′] ΔR1 = R1′-R1 = [0,0,0,0] = 0 dengan probabilitas terjadinya adalah 1, apapun nilai m0, m1, m2, dan m3. Syarat cukup bagi a2 = [-23,22,...,7] Pada langkah kelima, m4 R1 = [a1,b1,c1,d1] R2,1 = [d1,a2,b1,c1], m4 ' R2,1′ =[d1,a2′,b1,c1] R1′ = [a1,b1,c1,d1]
dengan
a2 = b1 + ((a1 + Φ4(b1,c1,d1) + m4 + t4) ⋘ 7) a2′ = b1 + ((a1 + Φ4(b1,c1,d1) + m4′ + t4) ⋘ 7) ditulis a2 = b1 + (K4 ⋘ 7) a2′ = b1 + (K4′ ⋘ 7) dimana K4 = W4 + m4 dan K4′ = W4 + m4′, dengan W4 = a1 + Φ4(b1,c1,d1) + t4 dan dari Tabel 1 disyaratkan bahwa Δm4 = m4′ - m4 = 2³¹, 6
Δa2 = a2′ - a2 = -2 , a2 = [-23,22,...,7] dimana menotasikan beda tanda perubahan bit. Catatan bahwa Δm4 = 2³¹ jika dan hanya jika Δm4,32 = 1 dan m4,i = m4,i′ untuk 1 ≤ i ≤ 31. Pada bagian ini akan ditentukan syarat cukup pemilihan pasangan (m4,m4′) dengan Δm4 = 2³¹ agar a2 = [-23,22,...,7] terjadi, berarti harus memenuhi persamaan
a2 = (b1 + (K4 ⋘ 7)) atau (b1 + (K4 ⋘ 7)) = [-23,22,...,7] Perhatikan dahulu posisi bit pada operasi (b1 + (K4 ⋘ 7)) Pos Bit b1
32
…
24
23
22
…
8
7
6
…
1
Pos Bit K4 <<< 7
25
…
17
16
15
…
1
32
31
…
26
posisi bit a2 sama dengan b1, posisi bit m4 sama dengan K4. Agar diperoleh a2 = [23,22,...,7], perhatikan penjelasan berikut ini. 1) Pengambilan sembarang m4,26-31 dijamin tidak menyebabkan perubahan bit pada a2,1-6. Hal ini karena b1=b1′ dan Δm4 = 2³¹ menyebabkan K4,26-31 =K4,26-31′. Namun demikian, hasil penghitungan ini mengandung nilai bawaan (carry) yang mempengaruhi penghitungan pada bit ke-7 untuk a2. Nilai bawaan untuk penghitungan bit ke-7 dinotasikan dengan s7, dalam kasus ini
(b1,1-6 + K4,26-31) < 26 s7 = 1 (b1,1-6+K4,26-31) ≥ 26
s7 = 0
juga jelas bahwa s7′ = s7. 2) Pengambilan pasangan (m4,32,m4,32′) dengan Δm4,32 = 1 dijamin menyebabkan perubahan bit pada a7. Hal ini karena b1 = b1′ dan Δm4,32 = 1 menyebabkan ΔK4,32 = 1. Untuk menjamin terjadinya perubahan bit dari a2,7 = 0 ke a2,7′ = 1 apabila
b1,7 K4,32 s7 = 0 Selanjutnya, i). Jika s7 = 0, maka b1,7 K4,32 = 0 dan ini memberikan dua kemungkinan: b1,7 = 1, K4,32 = 1, K4,32′ = 0, s8 =1, s8′ = 0 b1,7 = 0, K4,32 = 0, K4,32′ = 1, s8 =0, s8′=0 ii). Jika s7 = 1, maka b1,7 K4,32 =1 dan ini memberikan dua kemungkinan: b1,7 = 1, K4,32 = 0, K4,32′ = 1, s8 = 1, s8′ =1 b1,7 = 0, K4,32 = 1, K4,32′ = 0, s8 = 1, s8′ =0 3) Pada posisi bit ke-8 sampai dengan ke-23 untuk a2, perubahan bit yang dikehendaki adalah Pos Bit
23
22
21
…
8
a2’ :
0
1
1
…
1
a2 :
1
0
0
…
0
Dengan demikian, syarat cukup terjadinya perubahan bit tersebut adalah b1,8-23 + K4,1-16 + s8 = 215mod216 dan b1,8-23′ + K4,1-16′ + s8′ = (215-1)mod216 Karena b1,8-23′ + K4,1-16′ = b1,8-23 + K4,1-16, haruslah s8′ = s8
1. Perlu dicatat bahwa
pada kondisi ini akan menghasilkan nilai bawaan s24 = s24′ = 0. Dengan memandang dua kasus pada butir sebelum, perubahan posisi bit tersebut dijamin terpenuhi jika: i)
s7 = 0, b1,7 = 1, s8 = 1 dan K4,32 = 1, atau
ii) s7 = 1, b1,7 = 0, s8 = 1 dan K4,32 = 1. Dari K4,32 = 1 diperoleh persamaan: W4,32 m4,32 r32 = 1 m4,32 = a1,32 Φ4,32 t4,32 r32 1 dengan r32 adalah simpanan dari penghitungan K4,26-31. Dari Persamaan sebelumnya diperoleh b1,8-23 + K4,1-16 + 1 = 215mod216 K4,1-16 = (215-b1,8-23-1)mod216 m4,1-16 = [215-(b1,8-23 + W4,1-16 + 1)]mod216 4) Dari butir sebelumnya, karena s24′ = s24, b1′=b1 dan semua operan penyusun K4,17-25 sama, maka pada posisi bit ke-24 sampai dengan ke-32 untuk a2 dijamin tidak terjadi perubahan bit apapun pilihan m4,17-25. Syarat cukup bagi d2 = [32,24,-7] Pada langkah keenam,
m5 R2,1 = [d1,a2,b1,c1] R2,2 = [c1,d2,a2,b1], dengan m5 ' R2,2′ = [c1,d2′,a2′,b1] R2,1′ = [d1,a2′,b1,c1]
d2 = a2 + ((d1 + Φ5(a2,b1,c1) + m5 + t5)
12)
d2′ = a2′ + ((d1 +Φ5(a2′,b1,c1) + m5′ + t5)
12)
ditulis d2 = a2 + (K5
12)
d2′ = a2′ +(K5′
12)
Karena m5 = m5′, maka K5 = W5 + m5 dan K5′ = W5′ + m5, dengan W5 = d1 + Φ5 + t5 dan W5′ = d1 + Φ5′ + t5 Dari Tabel 1 disyaratkan bahwa Δd2 = -26 + 223 + 231, d2 = [32,24,-7] Φ5(a2,b1,c1) = (a2 b1) (¬a2 c1) Dengan demikian, pada bagian ini akan ditentukan syarat cukup terjadinya d2 = [32,22,7], dan dianalisis dari persamaan (a2 + (K5
12)) = [32,22,-7]
Perhatikan dahulu posisi bit pada operasi (a2 + (K5
12))
Pos Bit a2
32
…
24
23
…
13
12
…
7
6
…
1
Pos Bit K5
20
…
12
11
…
1
32
…
27
26
…
21
posisi bit d2 sama dengan a2, posisi bit W5 dan Φ5 sama dengan K5. Agar diperoleh d2 = [32,22,-7], perhatikan penjelasan berikut ini. 1) Agar tidak terjadi perubahan bit pada d2,1-3 disyaratkan bahwa a2,1-3 + K5,21-23 = a2,1-3′ + K5,21-23′ Karena a2,1-3 = a2,1-3′, maka disyaratkan K5,21-23 = K5,21-23′ W5,21-23 + m5,21-23 = W5,21-23 + m5,21-23′ Φ5,21-23 = Φ5,21-23′ 2
3
Karena a2,21-23 = 2 mod2 dan a2,21-23′ = (22-1)mod23 maka Φ5,21-22 = c1,21-22, Φ5,23 = b1,23, Φ5,21-22′ = b1,21-22 dan Φ5,23′ = c1,23. Jadi syarat bahwa tidak terjadi perubahan bit pada d2,1-3 jika c1,21-22 = b1,21-22 dan b1,23 = c1,23 dan syarat ini jelas memberikan nilai bawaan s4 = s4. 2) Agar tidak terjadi perubahan bit pada d2,4-6 disyaratkan bahwa
a2,4-6 + K5,24-26 + s4 = a2,4-6′ + K5,24-26′ + s4′ Karena a2,4-6 = a2,4-6′ dan s4 = s4′ maka disyaratkan K5,24-26 = K5,24-26′ W5,24-26 + m5,24-26 = W5,24-26 + m5,24-26′ Φ5,24-26 = Φ5,24-26′ Syarat tersebut pasti dipenuhi karena a2,24-26 = a2,24-26′, dan juga memberikan nilai bawaan s7 = s7′. 3) Agar terjadi perubahan bit dari d2,7 = 1 dan d2,7′ = 0 disyaratkan a2,7 K5,27 s7 =1 dan a2,7′ K5,27′ s7′ = 0 Karena a2,7 = 0 dan a2,7′ = 1, maka disyaratkan K5,27 s7 =1 dan 1 K5,27′ s7′ = 0 Karena a2,27 = a2,27′, maka K5,27 = K5,27′, sehingga syarat tersebut pasti dipenuhi dari fakta s7 = s7′. Jadi, jika diberikan d2,7 = 1, syarat terjadinya perubahan bit jika K5,27 s7= 1, dan ini memberikan nilai s8 = 0 dan s8′ = 1. Catatan kalkulasi, a2,1-7′ = 26 + a2,1-6 = 26 + a2,1-6 = 26 + a2,1-7
a2,1-7 < 26
Agar diperoleh d2,1-7 ≥ 26 dan d2,1-7′ < 26, maka 26 ≤ K5,21-27 + a2,1-7 < 27 sehingga 26-a2,1-7 ≤ K5,21-27 < 27-a2,1-7 dan dari K5,27 = K5,27′ (a2,27 = a2,27′) memberikan nilai r28 = r28′, dimana r28 adalah nilai bawaan W5,27 + m5,27 = K5,27 yang mempengaruhi nilai K5,28. 4) Agar tidak terjadi perubahan bit pada d2,8-12 disyaratkan a2,8-12 + K5,28-32 + s8 = a2,8-12′ + K5,28-32′ + s8′ Karena s8 = 0 dan s8′ =1, maka disyaratkan a2,8-12 + K5,28-32 = a2,8-12′ + K5,28-32′ + 1 Karena a2,28-32 = a2,28-32′ dan r28 = r28′, maka K5,28-32 = K5,28-32′, sehingga disyaratkan a2,8-12 = a2,8-12′ + 1 Di lain pihak a2,8-12 = 0mod25 dan a2,8-12′ = (25-1)mod25, maka disyaratkan 0 = 25mod25 Dengan demikian, syarat ini selalu dipenuhi, dan ini memberikan nilai s13 = 0 (karena s8 = 0 dan a2,8-12 = 0mod25) dan s13′ = 1 (karena a2,8-12′ = (25-1)mod25 dan s8′ = 1). Catatan kalkulasi, r33 dieliminasi. 5) Agar tidak terjadi perubahan bit pada d2,13-18 disyaratkan a2,13-18 + K5,1-6 + s13 = a2,13-18′ + K5,1-6′ + s13′ Karena s13 = 0 dan s13′ = 1, maka disyaratkan a2,13-18 + K5,1-6 = a2,13-18′ + K5,1-6′ + 1 Karena a2,1-6 = a2,1-6′, maka K5,1-6 = K5,1-6′, sehingga disyaratkan
a2,13-18 = a2,13-18′ + 1 Di lain pihak a2,13-18 = 0mod26 dan a2,13-18′ = (26-1)mod26, maka disyaratkan 0 = 26mod26 Dengan demikian, syarat ini selalu dipenuhi, dan ini memberikan nilai s19 = 0 dan s19′ = 1. Catatan kalkulasi r7 = r7′. 6) Agar tidak terjadi perubahan bit pada d2,19-23 disyaratkan bahwa a2,19-23 + K5,7-11 + s19 = a2,19-23′ + K5,7-11′ + s19′ Karena s19 = 0 dan s19′ = 1, maka disyaratkan a2,19-23 + K5,7-11 = a2,19-23′ + K5,7-11′ + 1 Karena a2,19-23 = 24mod25 dan a2,19-23′ = (24-1)mod25, maka disyaratkan K5,7-11 + 24 = (24-1) + K5,7-11′ + 1mod25 K5,7-11 = K5,7-11′mod25 Φ5,7-11 = Φ5,7-11′mod25 Di lain pihak, a2,7-11 = 0mod25 dan a2,7-11′ = -1mod25 menyebabkan Φ5,7-11 = c1,7-11 dan Φ5,7-11′ = b1,7-11. Jadi jaminan bahwa tidak terjadi perubahan bit pada d2,19-23 jika b1,7-11 = c1,7-11 dan ini memberikan nilai s24 = s24′, yaitu
2 4 K 5, 7 11 s 24 25
Catatan kalkulasi, r12 = r12′. 7) Agar terjadi perubahan bit dari d2,24 = 0 ke d2,24 = 1 disyaratkan bahwa a2,24 K5,12 s24 = 0 dan a2,24′ K5,12′ s24′ = 1 Karena a2,24 = a2,24′ dan s24 = s24′, maka disyaratkan K5,12′ = K5,12 1 Φ5,12′ = Φ5,12 1 Karena a2,12 = 0 dan a2,12′ = 1 dan r12 = r12′, maka Φ5,12 = c1,12 dan Φ5,12′ = b1,12, maka jaminan terjadinya perubahan bit pada dari d2,24 = 0 ke d2,24 = 1 adalah c1,12 = b1,12 1 dan a2,24 K5,12 s24 = 0 1. Jika s24 = s24′ = 0, maka a2,24 K5,12 = 0 dan ini menyebabkan s25 = s25′ = 0 jika dan hanya jika a2,24 = 0 dan K5,12 = 0 dan r13 = r13′. a2,24 = a2,24′ = 0, K5,12 = 0, K5,12′ = 1, s25 = 0, s25′ = 0 a2,24 = a2,24′ = 1, K5,12 = 1, K5,12′ = 0, s25 = 1, s25′ = 0 2. Jika s24 = s24′ = 1, maka a2,24 K5,12 = 1, dan ini menyebabkan s25 = s25′ = 1 jika dan hanya jika a2,24 = 1 dan K5,12 = 0 dan r13 = r13′. a2,24 = a2,24′ = 0, K5,12 = 1, K5,12′ = 0, s25 = 1, s25′ = 0
a2,24 = a2,24′ = 1, K5,12 = 0, K5,12′ = 1, s25 = 1, s25′ = 1 Dalam hal ini cukup dipilih untuk kasus s25 = s25′, berarti K5,12 = 0. Catatan kalkulasi: K5,12 = 0 W5,12 m5,12 = 0 Φ5,12 t5,12 d1,12 m5,12 = 0 c1,12 0 d1,12 m5,12 = 0 c1,12 d1,12 m5,12 = 0 Secara sama, K5,12′ =1 b1,12 d1,12 m5,12 = 1 (c1,12 1) d1,12 m5,12 = 1 Agar, r13 = r13′ cukup dipilih c1,12 = 0 8) Agar tidak terjadi perubahan bit pada d2,25-31 disyaratkan bahwa a2,25-31 + K5,13-19 + s25 = a2,25-31′ + K5,13-19′ + s25′ Karena a2,25-31 = a2,25-31′ dan s25 = s25′ maka K5,13-19 = K5,13-19′ Φ5,13-19 = Φ5,13-19′ Karena a2,13-19 = 0mod27 dan a2,13-19′ = -1mod27, maka Φ5,13-19 = c1,13-19 dan Φ5,13-19′ = b1,13-19, sehingga disyaratkan c1,13-19 = b1,13-19 dan menyebabkan s32 = s32′ 9) Agar terjadi perubahan bit dari d2,32 = 0 ke d2,32 = 1 disyaratkan bahwa a2,32 K5,20 s32 = 0 dan a2,32′ K5,20′ s32′ = 1 Karena a2,32 = a2,32′ dan s32 = s32′, maka disyaratkan K5,20 = K5,20′ 1 Φ5,20 = Φ5,20′ 1 Karena a2,20 = 0 dan a2,20′ = 1 maka Φ5,20 = c1,20 dan Φ5,20′ = b1,20, sehingga disyaratkan c1,20 = b1,20 1 dan a2,32 K5,20 s32 = 0 1. Jika s32 = 0, maka a2,32 K5,20 = 0 dan ini menyebabkan s1 =s1′ = 0 jika dan hanya jika a2,32 = 0 dan K5,20 = 0 dan r20 = r20′. 2. Jika s32 = 1, maka a2,32 K5,20 = 1, dan ini menyebabkan s1 = s1′ = 1 jika dan hanya jika a2,32 = 1 dan K5,20 = 0 dan r20 = r20′ Catatan kalkulasi: K5,20 = 0 W5,20 m5,20 = 0 Φ5,20 t5,20 d1,20 m5,20 = 0 c1,20 0 d1,20 m5,20 = 0 c1,20 d1,20 m5,20 = 0
Secara sama, K5,20′ = 1 b1,20 d1,20 m5,20 =1 (c1,20 1) d1,20 m5,20 = 1 Jadi, r20 = r20′ jika dan hanya jika c1,20 = 0. Syarat cukup bagi c2 = [32-27,-26,-25-24,-12,11-7,-6,5-1] Pada langkah ketujuh, m6 R2,2 = [c1,d2,a2,b1] R2,2 = [b1,c2,d2,a2], dengan m6 ' R2,2′ = [b1,c2′,d2′,a2′] R2,2′ = [c1,d2′,a2′,b1]
c2 = d2 + ((c1 + Φ6(d2,a2,b1) + m6 + t6)
17)
c2′ = d2′ + ((c1 + Φ6(d2′,a2′,b1) + m6 + t6)
17)
ditulis c2 = d2 + (K6 c2′ = d2′ + (K6′
17) 17)
Karena m =m ′, maka K6 = W6 + m6 dan K6′ = m6 + W6′, dengan W6 = c1 + Φ6 + t6 dan W6′ = c1 + Φ6′ + t6 Dari Tabel 1 disyaratkan bahwa Δc2 = -227 + 223 – 26 – 1, dan
c2 = [32-27,-26,-25-24,-12,11-7,-6,5-1] Φ6(d2,a2,b1) = (d2 a2) (¬d2 b1) Φ6′(d2′,a2′,b1) = (d2′ a2′) (¬d2′ b1) Dengan demikian, pada bagian ini akan ditentukan syarat cukup terjadinya c2, dan dianalisis dari persamaan
(d2 + (K6
17)) = c2
Perhatikan dahulu posisi bit pada operasi (d2 +(K6
17))
Pos Bit a2
32
…
24
23
…
18
17
…
7
6
…
1
Pos Bit K5
15
…
8
6
…
1
32
…
22
21
…
16
posisi bit c2 sama dengan d2, posisi bit W6 dan Φ6 sama dengan K6. 1) Agar terjadi perubahan bit dari c2,1-6 = 25mod26 ke c2,1-6′ = (25-1)mod26 disyaratkan bahwa d2,1-6 + K6,16-21 = 25mod26 dan d2,1-6′ + K6,16-21′ = 25-1mod26 Karena d2,1-6 = d2,1-6′, maka disyaratkan K6,16-21 = K6,16-21′ + 1mod26
Φ6,16-21 = Φ6,16-21′ + 1mod26 Dari rumus Φ6, perhatikan bahwa
' d ' ,1, b 6 d 2 ,0, b1 6
2
0, jika d 2 1
1, jika d 2 0
1
1, jika d 2 1 b1 , jika d 2 0
Dengan demikian, karena d2,16-21 = d2,16-21′, a2,16-21 = 0mod26, dan a2,16-21′ = (261)mod26, maka haruslah disyaratkan d2,16-21 = (26-1)mod26 sehingga Φ6,16-21 = 0 dan Φ6,16-21′ = (26-1)mod26 Jika 0 ≤ d2,1-6 < 25, maka s7 = s7′ = 0; jika 25 < d2,1-6 < 26, maka s7 = s7′ = 1; dan jika d2,1-6 = 25, maka s7 = 0 dan s7′ = 1. 2) Agar terjadi perubahan bit dari c2,7 = 0 ke c2,7′ = 1 disyaratkan bahwa d2,7 K6,22 s7 =0 dan d2,7′ K6,22′ s7′ = 1 Karena d2,7 = 1 dan d2,7′ = 0, maka disyaratkan 1 K6,22 s7 = 0 dan 0 K6,22′ s7′ =1 K6,22 s7 = K6,22′ s7′ =1 i)
Jika s7 = s7′ = 1, maka K6,22 = K6,22′ = 0 Φ6,22 = Φ6,22′ Dalam hal ini, karena d2,22 = d2,22′, a2,22 = 0, dan a2,22′ = 1, maka haruslah disyaratkan d2,22 = 0 sehingga Φ6,22 = Φ6,22′ = b1,22. Pada kasus ini, s8 = 1 dan s8′ = 0.
ii) Jika s7 = s7′ = 0, maka K6,22 = K6,22′ = 1 Φ6,22 = Φ6,22′ Dalam hal ini, karena d2,22 = d2,22′, a2,22 = 0, dan a2,22′ = 1, maka haruslah disyaratkan d2,22 = 0 sehingga Φ6,22 = Φ6,22′ = b1,22. Pada kasus ini, s8 = 1 dan s8′ = 0. iii) Jika s7 = 0 dan s7′ = 1, maka K6,22 = 1 dan K6,22′ = 0 Φ6,22 = Φ6,22′
1
Dalam hal ini, karena d2,22 = d2,22′, a2,22 = 0, dan a2,22′ = 1, maka haruslah disyaratkan
d2,22 = 1 sehingga Φ6,22 = 0 dan Φ6,22′ = 1. Pada kasus ini, s8 = 1 dan s8′ = 0. 3) Agar terjadi perubahan bit dari c2,8 = 0 ke c2,8′ = 1 disyaratkan bahwa d2,8 K6,23 s8 = 0 dan d2,8′ K6,23′ s8′ = 1 Karena d2,8 = d2,8′; s8 =1 dan s8′ = 0, maka disyaratkan K6,23 = K6,23′ Φ6,23 = Φ6,23′ Karena d2,23 = d2,23′, a2,23 = 1, dan a2,23′ = 0, maka haruslah disyaratkan d2,23 = 0 sehingga Φ6,23 = Φ6,23′ = b1,23 Dalam hal ini, s9 = 1 dan s9′ = 0. 4) Agar terjadi perubahan bit dari c2,9 = 0 ke c2,9′ = 1 disyaratkan bahwa d2,9 K6,24 s9 =0 dan d2,9′ K6,24′ s9′ = 1 Karena d2,9 = d2,9′ dan s9 = 1 dan s9′ = 0, maka disyaratkan K6,24 = K6,24′ Φ6,24 = Φ6,24′ Karena d2,24 = 0 dan d2,24′ = 1, a2,24 = a2,24′, maka haruslah disyaratkan b1,24 = a2,24′ = a2,24 Dalam hal ini, maka s10 = 1 dan s10′ = 0. 5) Agar terjadi perubahan bit dari c2,10-12 = 22mod23 ke c2,10-12′ = (22-1)mod23 disyaratkan bahwa d2,10-12 + K6,25-27 + s10 = 2²mod2³ dan d2,10-12′ + K6,25-27′ + s10′ = (2²-1)mod2³ Karena d2,10-12 = d2,10-12′, dan s10 = 1 dan s10′ = 0, maka disyaratkan K6,25-27 = K6,25-27′mod2³ Φ6,25-27 = Φ6,25-27′mod2³ Dengan demikian, karena d2,25-27 = d2,25-27′, a2,25-27 = a2,25-27′, maka persamaan tersebut dijamin terpenuhi. Jika 0 ≤ d2,10-12 < 2², maka s13 = s13′ = 0; jika 2² ≤ d2,10-12 < 2³, maka s13 = s13′ = 1. 6) Agar tidak terjadi perubahan bit pada c2,13-16 disyaratkan bahwa d2,13-16 + K6,28-31 + s13 = d2,13-16′ + K6,28-31′ + s13′mod24 Karena d2,13-16 = d2,13-16′, dan s13 = s13′, maka disyaratkan K6,28-31 = K6,28-31′mod24 Φ6,28-31 = Φ6,28-31′mod24 selanjutnya, karena d2,28-31 = d2,28-31′, a2,28-31 = a2,28-31′, maka persamaan tersebut dijamin terpenuhi dan mengakibatkan s17 = s17′. 7) Agar tidak terjadi perubahan bit pada c2,17 disyaratkan bahwa
d2,17 K6,32 s17 = d2,17′ K6,32′ s17′ Karena d2,17 = d2,17′ dan s17 = s17′, maka disyaratkan K6,32 = K6,32′ Φ6,32 = Φ6,32′ Karena d2,32 = 0 dan d2,32′ = 1, a2,32 = a2,32′, maka haruslah disyaratkan b1,32 = a2,32′ = a2,32 dan memberikan nilai s18 = s18′. 8) Agar tidak terjadi perubahan bit pada c2,18-23 disyaratkan bahwa d2,18-23 + K6,1-6 + s18 = d2,18-23′ + K6,1-6′ + s18′mod26 Karena d2,18-23 = d2,18-23′, dan s18 = s18′, maka disyaratkan K6,1-6 = K6,1-6′ Φ6,1-6 = Φ6,1-6′ selanjutnya, karena d2,1-6 = d2,1-6′, a2,1-6 = a2,1-6′, maka persamaan tersebut dijamin terpenuhi dan mengakibatkan s24 = s24′. 9) Agar terjadi perubahan bit dari c2,24=1 ke c2,24′=0 disyaratkan bahwa d2,24 K6,7 s24 =1 dan d2,24′ K6,7′ s24′ = 0 Karena d2,24 = 0, d2,24′ = 1, dan s24 = s24′, maka disyaratkan K6,7 = K6,7′ Φ6,7 = Φ6,7′ Karena d2,7 = 1, d2,7′ = 0 dan a2,7 = 0, a2,7′ = 1, maka Φ6,7 = 0 dan Φ6,7′ = b1,7 sehingga b1,7 = 0, berarti c1,7 = 0 Dalam hal ini, karena d2,24 = 0 dan d2,24′ = 1, maka s25 = 0, dan s25′ = 1. 10) Agar terjadi perubahan bit dari c2,25-26 = (2²-1)mod2² ke c2,25-26′ = 0mod2² disyaratkan bahwa d2,25-26 + K6,8-9 + s25 = (2²-1)mod2² dan d2,25-26′+K6,8-9′+s25′ = 0mod2² Karena d2,25-26 = d2,25-26′, dan s25 = 0 dan s25′=1, maka disyaratkan K6,8-9 = K6,8-9′ Φ6,8-9 = Φ6,8-9′ Karena d2,8-9 = d2,8-9′ dan a2,8-9 = a2,8-9′, maka persamaan di atas pasti dipenuhi. Dalam hal ini, s27 = 0 dan s27′ = 1. 11) Agar terjadi perubahan bit dari c2,27-31 = 0mod25 ke c2,27-31′ = (25-1)mod25 disyaratkan bahwa d2,27-31 + K6,10-14 + s27 =0mod25 dan d2,27-31′ + K6,10-14′ + s27′ = (25-1)mod25 Karena d2,27-31 = d2,27-31′, dan s27 = 0 dan s27′ = 1, maka disyaratkan K6,10-14 = K6,10-14′ + 2mod25 Φ6,10-14 = Φ6,10-14′ + 2mod25 Dengan demikian, karena d2,10-14 = d2,10-14′, a2,10-14 = 0mod25, dan a2,10-14′ = (251)mod26, maka haruslah disyaratkan d2,10-14 = (26-1)mod26 sehingga
Φ6,16-21 = 0 dan Φ6,16-21′ = (26-1)mod26 Jika 0 ≤ d2,1-6 < 25, maka s7 = s7′ = 0; jika 27 < d2,1-6 < 26, maka s7 = s7′ = 1; dan jika d2,1-6 = 25, maka s7 = 0 dan s7′ = 1.
B
Modifikasi Algoritme MD5 dan Program MD5 beserta Implementasinya Pada bagian ini dibahas modifikasi beberapa bagian dari algoritme MD5 tanpa
mengubah struktur secara signifikan. Pengubahannya dimaksudkan atas pertimbangan agar tahan terhadap serangan diferensial secara umum, khususnya terhadap versi Wang dan Yu. Cara pengubahannya merupakan hasil analisis dari proses penentuan syarat cukup modifikasi pesan. Ada 4 (empat) hal yang cukup signifikan dari pengubahan tersebut yang bisa memperkecil terjadinya tumbukan dalam serangan diferensial. Pertama, fungsi konstanta jumlah yaitu fungsi yang menghasilkan nilai-nilai konstanta pada tiap langkah dalam satu blok. Kedua, konstanta putaran di mana konstanta ini mempunyai struktur yang teratur dan selalu tetap (berpengaruh pada kecepatan, semakin teratur maka semakin cepat). Ketiga, permutasi blok pesan. Keempat, fungsi ronde Boolean tak linear. Karena pengubahan tersebut tidak mempengaruhi struktur besar MD5, penjelasan dari keempat hal tersebut akan dilakukan langsung melalui implementasi algoritme MD5 dengan menggunakan software maple. Format data yang digunakan adalah desimal. Hal ini dilakukan untuk mempermudah analisis secara matematis. 1
Modifikasi Algoritme MD5
1. Penentuan konstanta jumlah menggunakan rumus t(i). Kemudian konstantakonstanta tersebut disekat. Jadi, sekat yang pertama untuk 4 langkah pertama pada ronde kesatu. Sekat yang kedua untuk 4 langkah kedua pada ronde kesatu. Sekat yang kedua untuk 4 langkah kedua pada ronde kesatu. Sekat yang ketiga untuk 4 langkah ketiga pada ronde kesatu. Sekat yang keempat untuk 4 langkah keempat pada ronde kesatu. Untuk ronde kedua, menggunakan sekat kelima, keenam, ketujuh dan kedelapan. Demikian juga untuk ronde ketiga dan keempat. Pada MD5 yang sudah dimodifikasi, nilai ti (i = 1, 2, 3) diperoleh dengan cara dibuat merambat dengan menggunakan operasi dari
mod
. Konstanta , dan
diperoleh dari
diperoleh dari
mod mod
,
diperoleh
. Demikian juga untuk
langkah-langkah selanjutnya. Konstanta jumlah selalu bisa dinetralisir dengan cara memproses
, memproses t, lalu dioperasikan menggunakan
. Konstanta jumlah
dibuat merambat sehingga merumitkan penetuan syarat cukup sehingga modifikasinya tahan terhadap serangan diferensial. 2. Pada modifikasi konstanta putaran ini, p sulit dimodifikasi seperti yang terlihat pada algoritmenya, sehingga sulit menghasilkan tumbukan. Karena modifikasinya dirambatkan dengan cara mengoperasikan konstanta jumlah lalu dimodulokan
pada fungsi boolean tak linear dengan
. Hasilnya dimodulokan lagi dengan
. Jadi,
konstanta putaran bisa dihilangkan karena tidak bisa dilakukan analisis syarat cukup atau sangat tidak berpengaruh dalam analisis serangan diferensial. Konstanta putaran dibuat merambat berdasarkan konstanta sebelumnya, sehingga merumitkan penentuan syarat cukupnya. 3. Permutasi blok pesan dibuat agar sulit mendapatkan hasil pada jalur diferensial. Pada modifikasinya, dilakukan pada prosedur iterasi blok pesan di mana ada penambahan g=0 lalu g diiterasi lagi menjadi g = g + Hi yaitu operasi
dari H1, H2, H3, H4 secara
berulang-ulang. Selain itu juga terdapat s yaitu 9-2*i dan permutasinya adalah P:=[seq(((x+s*r) mod 16) + 1,r=1, 2, ..., 16)], sehingga P1 = [10, 1, 8, 15, 6, 13, 4, 11, 2, 9, 16, 7, 14, 5, 12, 3]; P2 = [8, 13, 2, 7, 12, 1, 6, 11, 16, 5, 10, 15, 4, 9, 14, 3]; P3 = [6, 9, 12, 15, 2, 5, 8, 11, 14, 1, 4, 7, 10, 13, 16, 3]; P = [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 1, 2, 3]. Permutasi blok pesan menentukan diferensial karakteristik secara keseluruhan. Jika permutasi tersebut dimodifikasi dengan kata lain diubah maka diferensial karakteristik secara keseluruhan berubah. Akibatnya penyerang harus mendefinisikan ulang diferensial karakteristiknya. Jika mendefinisikan ulang berarti membuat sulit iterasi secara keseluruhan Tujuan memodifikasi permutasi blok pesan ini adalah agar merumitkan terjadinya tumbukan pada serangan diferensial. 4. Fungsi ronde boolean tak linear. Fungsi ketiga pada MD5 asli adalah fungsi yang tahan tumbukan sedangkan fungsi yang lainnya lemah, sedangkan modifikasinya sebagai berikut,
i X ,Y , Z
X Z Y Y Z , 0 i 15 Z X Y X Y , 16 i 31 Y X Z X Z , 32 i 47 X Y Z Z Y , 48 i 63
Jika X = 0, maka F = Z dan jika X = 1, maka F = Y. Sebagai contoh, pada analisis syarat cukup untuk 5(a2, b1, c1),
... karena a2,13-19 = [0 0 0 0 0 0 0] dan a’2,13-19 = [1 1 1 1 1 1 1], maka 5,13-19 = c1,13-19 dan ’5,13-19 = b1,13-19, sehingga dapat disimpulkan c1,13-19 = b1,13-19 ... Tujuan modifikasi tersebut agar analisisnya menjadi sangat kompleks sehingga diferensial karakteristik sulit untuk dicapai sehingga peluangnya menjadi sangat kecil. 2
Program MD5 beserta implementasinya Program MD5 dengan software maple diberikan dengan 3 (tiga) prosedur yaitu
prosedur penunjang, prosedur inti, prosedur fungsi iterasi. 1. Prosedur Penunjang, terdapat 12 (dua belas) prosedur di antaranya bagaimana cara mengonversikan bilangan, membalik urutan vektor, memutar posisi bit vektor, mengoperasikan
pada
vektor,
menyekat
dan
membuka
vektor
serta
mempermutasikan blok pesan. 2. Prosedur Inti adalah prosedur penetapan konstanta. Terdapat 3 (tiga) konstanta yaitu konstanta nilai awal (a0,b0,c0,d0) dalam bentuk bilangan hexadesimal yang akan dikonversikan ke bilangan desimal, konstanta putaran yang sudah diberikan sebelumnya dan konstanta jumlah. 3. Prosedur Fungsi Iterasi, terdiri dari 3 (tiga) prosedur yaitu: (1). prosedur 4 (empat) fungsi tak linear F; (2). prosedur fungsi iterasi untuk satu langkah, misalkan langkah pertama
dari
ronde
kesatu,
a1 b0 a 0 0 b0 , c 0 , d 0 m 0 0 xd 76aa 478 7 . Dengan mengambil H 0 , nilai t dari konstanta jumlah, nilai p dari konstanta putaran dan menentukan bilangan acak dari 0 sampai (232 1) serta menentukan 4 (empat) bilangan acak M, maka bilangan pertama dari bilangan acak itu adalah m0 sehingga diperoleh G. (3). prosedur iterasi 4 (empat) langkah dalam ronde ke-k, di mana prosedur ini untuk mengiterasi 4 (empat) langkah sekaligus dalam suatu ronde. Prosedur ini digunakan pada prosedur iterasi per blok pesan, di mana setelah dibuat permutasi vektor, disekat, lalu dilakukan iterasi empat langkah. Di samping itu juga ada beberapa prosedur tambahan seperti membangkitkan 1 blok pesan 512 bit secara random, iterasi per blok pesan, membangkitkan n blok pesan 512 bit secara random dan prosedur fungsi hash MD5 untuk input M berukuran n blok pesan 512 bit. Modifikasi beberapa komponen algoritme MD5 yang telah disebutkan di atas diduga kuat mempengaruhi kecepatan implementasinya. Untuk memastikan hal itu dalam penelitian ini dilakukan perbandingan implementasi antara algoritme MD5 asli dan
modifikasinya. Cara membandingkannya yaitu menggunakan software maple, pengambilan input pesannya secara random, banyaknya blok pesan mengikuti 2n blok pesan (n = 1, 2, ..., 13) dengan anggapan bahwa n blok pesan ini dapat mewakili pengambilan blok pesan. Pada n blok pesan, 2 blok pesan = 1 KB (Kilo Byte), 4 blok pesan = 2 KB, 8 blok pesan = 4 KB, 16 blok pesan = 8 KB, ... , 512 blok pesan = 256 KB, 2*512 blok pesan = 512 KB, 4*512 blok pesan = 1024 KB (1 MB), 8*512 blok pesan = 2 MB, 16*512 blok pesan = 4 MB. Spesifikasi komputer yang digunakan adalah Pentium 4, processor Intel Core 2 Duo dan memori 2 GB. Implementasi MD5 asli dan modifikasinya menunjukkan perbedaan waktu yang cukup signifikan setiap kali penambahan blok pesan. Kecepatannya menurun kira-kira sepertiga, tapi mampu meng-hashing pesan berukuran 4 MB dalam waktu 31 menit sehingga masih layak dipergunakan. Waktu hashing algoritme MD5 (detik)
n Blok Pesan
2 4 8 16 32 64 128 256 512 2*512 4*512 8*512 16*512
Asli 0,1 0,29 0,55 1,12 2,08 4,16 8,41 17,02 34,3 70,47 147,98 314,39 695,11
Modifikasi 0,41 0,72 1,36 2,65 5,3 10,66 21,46 43,07 86,71 177,82 373,64 947,52 1882,27
Tabel 2 Tabel waktu hashing algoritme MD5 (detik) Waktu hashing algoritme MD5 (menit)
n Blok Pesan
2 4 8 16 32 64 128 256 512 2*512 4*512 8*512 16*512
Asli
Modifikasi
0,002 0,005 0,009 0,019 0,035 0,069 0,14 0,284 0,572 1,175 2,466 5,24 11,585
0,007 0,012 0,023 0,044 0,088 0,178 0,358 0,72 1,46 2,964 6,23 15,792 31,37
Tabel 3 Tabel waktu hashing algoritme MD5 (menit)
: waktu hashing MD5 modifikasi : waktu hashing MD5 asli
Gambar 4 Grafik perbandingan waktu antara algoritme MD5 asli dan modifikasi (detik) Dari Tabel 2 dan Tabel 3 terlihat bahwa untuk menghashing 2 blok pesan, MD5 asli membutuhkan waktu 0,1 detik sedangkan MD5 modifikasi membutuhkan waktu 0,41 detik. Pada 4 blok pesan, MD5 asli dan modifikasi masing-masing 0,29 dan 0,72 detik. Begitu juga seterusnya sampai pada 16*512 blok pesan, MD5 asli 695 detik (11 menit) dan MD5 modifikasi 1882 detik (31 menit).
IV SIMPULAN DAN SARAN 4.1
Simpulan
Berdasarkan penelitian yang telah dilakukan, maka dapat disimpulkan bahwa MD5 perlu dimodifikasi agar tahan terhadap serangan diferensial dan jenis-jenis serangan yang lain. Modifikasi tersebut didasarkan pada analisis syarat cukup. Hal ini dapat dirinci sebagai berikut: 1.
Modifikasi hanya dilakukan pada 4 (empat) komponen penting pada MD5 tanpa mengubah struktur besarnya. Komponen-komponen
tersebut yaitu konstanta jumlah, konstanta putaran, permutasi blok pesan, dan fungsi boolean tak linear. 2. Modifikasi konstanta jumlah, konstanta putaran, dan permutasi blok pesan dibuat merambat berdasarkan perhitungan nilai konstanta sebelumnya, hal ini dimaksudkan untuk merumitkan penentuan syarat cukup sehingga tahan terhadap serangan diferensial. 3. Modifikasi fungsi boolean tak linear dilakukan dengan mengubah rumusnya agar analisisnya menjadi sangat kompleks sehingga diferensial karakteristik sulit dicapai karena peluangnya menjadi sangat kecil. 4. Secara keseluruhan hasil modifikasi algoritme MD5 mempunyai ketahanan tumbukan terhadap serangan diferensial khususnya serangan diferensial tipe Wang. 5. Proses hashing hasil modifikasi menunjukkan waktu lebih lambat kirakira sepertiga dibanding aslinya atau terjadi perbedaan waktu yang cukup signifikan tetapi masih layak dipergunakan untuk meng-hashing pesan sampai 4 MB. 4.2
Saran
Perlunya modifikasi algoritme fungsi hash yang lainnya seperti MD4, HAVAL-128, RIPEMD, dan lain-lain, untuk melihat perbandingan di antaranya.
V DAFTAR PUSTAKA Menezes, A.J., v. Oorschot, P.C, Vanstone, S.A 1996. Handbook of Applied
Cryptography. United State of America: CRC Press. American National Standard Institute (ANSI) X9.62. 1998. Elliptic Curve
Digital Signature Algorithm (ECDSA)”. Henk C. A. van Tilborg. 2005. Encyclopedia of Cryptography and Security. New
York: Springer. M. Stamp and R. M. Low. 2007. Applied Cryptanalysis (breaking ciphers in the
real world). New Jersey: John Wiley & Sons, Inc, Hoboken.
P. Hawkes, M. Paddon, and G. G. Rose. 2004. Musings on the Wang et al. MD5
Collision. Xiaoyun Wang, D. Feng, X. Lai, Hongbo Yu. 2004. Collision for hash
Functions MD4, MD5, HAVAL-128 and RIPEMD. Cryptology ePrint Archive, Report 2004/199, see://httpeprint.iacr.org. Xiaoyun Wang, Hongbo Yu. 2004. How to Break MD5 and Other Hash
Functions, IEEE Trans. Inform. Theory, vol. 39, no. 2, pp. 677-680.
Lampiran 1 Tabel Karakteristik Diferensial pada Diferensial Iterasi Pertama (X. Wang dan H. Yu, 2004)
Lampiran 2 Tabel Syarat Cukup untuk Diferensial Iterasi Pertama (X. Wang dan H. Yu, 2004)
Lampiran 3 Tabel Karakteristik Diferensial pada Diferensial Iterasi Kedua (X. Wang dan H. Yu, 2004)
Lampiran 4 Tabel Syarat Cukup untuk Diferensial Iterasi Kedua (X. Wang dan H. Yu, 2004)
Lampiran 5 Program Hashing MD5 – Asli > restart:
Pendefinisian Prosedur yang digunakan CvrtDesBigend adalah Prosedur yang mengubah Vektor Biner ke Desimal dari Order Rendah ke Order Tinggi. > CvrtDesBigend := proc( N::list ) local D1, D2 :: list, Des::integer; D1:=map(x -> 2^x,[seq(i,i=0..(nops(N)-1))]): D2:=[seq(N[j]*D1[j],j=1..nops(N))]: Des:=add( i, i=D2 ); end proc: Contoh: input I := [0,1,1,0,1], output O = 0.2^0 + 1.2^1 + 1.2^2 + 0.2^3 + 1.2^4. > A:=[0,1,1,0,1]: > CvrtDesBigend(A); CvrtDesLitend adalah Prosedur yang mengubah Vektor Biner ke Desimal dari Order Tinggi ke Order Rendah. > CvrtDesLitend := proc( M::list ) local D1, D2 :: list, Des::integer; D1:=map(x -> 2^x,[seq(i,i=0..(nops(M)-1))]): D2:=[seq(M[nops(M)+1-j]*D1[j],j=1..nops(M))]: Des:=add( i, i=D2 ); end proc: Contoh: input I := [0,1,1,0,1], output O = 0.2^4 + 1.2^3 + 1.2^2 + 0.2^1 + 1.2^0. > A:=[0,1,1,0,1]: > CvrtDesLitend(A); UrutBalik adalah Prosedur yang mengubah membalik urutan Vektor Biner dari Order Rendah ke Order Tinggi atau sebaliknya. > UrutBalik:= proc( Cr::list) local Hsl::list, i,j, n::integer: Hsl:=[op(Cr)]: n := nops(Hsl): if (n mod 2 = 0) then for i from 1 to n/2 do Hsl[i] := op(n-i+1,Cr); Hsl[n-i+1] := op(i,Cr); end do: else for i from 1 to (n-1)/2 do Hsl[i] := op(n-i+1,Cr); Hsl[n-i+1] := op(i,Cr); end do: end if; Hsl; end proc: Contoh: input I := [0,1,1,0,1], output [1, 0, 1, 1, 0].
> A:=[0,1,1,0,1]: > UrutBalik(A); PtrLgkarBin adalah Prosedur yang memutar urutan posisi bit Vektor Biner secara melingkar sejauh p bit, nilai positif berarti putar kanan dan negatif berarti putar kiri. > PtrLgkarBin:= proc( Cr::list, p::integer) local Hsl::list, i, q, j, n::integer: Hsl:=[op(Cr)]: n := nops(Hsl): q := p mod n: for i from 1 to n do j := ((i+q-1) mod n) + 1: Hsl[i] := op(j,Cr); end do: Hsl; end proc: Contoh: > A:=[6,0,1,9,8]: > A1:=PtrLgkarBin(A,-1); > A2:=PtrLgkarBin(A,-3); > PtrLgkarBin(A1,-2); PtrLgkarInt adalah Prosedur yang memutar Intejer p secara melingkar sejauh Intejer q modulo 2^m ke kiri dalam format Little Endian. > PtrLgkarInt:= proc( p::integer, q::integer, m::integer) local temp, Hsl::integer: temp := q mod m: Hsl := ((p*2^temp) mod 2^m) + floor(p/(2^(mtemp))); end proc: Contoh: > B:=PtrLgkarInt(13,2,5); > B1:=PtrLgkarInt(13,-3,5); > B2:=PtrLgkarInt(B1,-2,5); CvrtDesVek adalah Prosedur yang mengubah Interjer Desimal ke Vektor Biner dengan panjang n. > CvrtDesVek := proc( B::integer, n::posint ) local K, KVekLitend,KVekBigend,Kv::list, i::integer: K := B mod 2^n; Kv:=convert(K,base,2): KVekBigend:=[op(Kv),seq(0*i,i=(nops(Kv)+1)..n)]: KVekLitend:=UrutBalik(KVekBigend);
end proc: Contoh: > CvrtDesVek(13,4); CvrtDesVek(75,4);
CvrtBinVek adalah Prosedur yang mengubah Interjer Biner dengan panjang n ke Vektor Biner. > CvrtBinVek := proc( K::integer, n::posint ) local KVekLitend,KVekBigend,Kv::list, i,KDesLitend::integer: KDesLitend:=convert(K,decimal,binary): CvrtDesVek(KDesLitend,n); end proc: Contoh: > CvrtBinVek(11001,7); CvrtBinVek(0011001,7);
XorV adalah Prosedur yang me-xor-kan dua Vektor Biner. > XorV:= proc( X::list, Y::list) local Z, Hsl::list, i, n, m::integer: m := nops(X): n := nops(Y): if m<>n then error end if: for i from 1 to m do Z[i] := (X[i]+Y[i]) mod 2: end do: Hsl:=[seq( Z[i], i=1..m )]; end proc: Contoh: > A:=[1,0,1,1,0,1,1]: B:=[1,0,1,0,0,0,1]: > XorV(A,B); XorD adalah Prosedur yang me-xor-kan dua Intejer Desimal modulo 2^n. > XorD:= proc( a::integer, b::integer, n::posint) local X, Y, Hv::list, Hsl::integer: X := CvrtDesVek(a,n): Y := CvrtDesVek(b,n): Hv := XorV(X,Y); Hsl := CvrtDesLitend(Hv); end proc: Contoh: > XorD(5,11,4); > XorD(12,1,4); SekatVek adalah Prosedur yang menyekat Vektor X dengan panjang n menjadi Y=[y1,y2,...,yr], dimana yi intejer positif dan y1+y2+...+yr=n. > SekatVek:=proc(X::list,Y::list) local L, K, M::list, n, m, l, i, j::integer:
l:=nops(Y): n:=add(i,i=Y): m:=nops(X): if n<>m then error end if: K:=[seq([seq(op(j,X),j=(op(i,Y))*(i1)+1..(op(i,Y))*i)],i=1..l)]; end proc: Contoh: > C := [15,5,14,2,3,16,12,9,4,11,7,13,6,10,1,8]: > R:=[8,4,4]: > SekatVek(C,R); BukaSekatVek adalah prosedur yang menbuka sekat dari ouput prosedur SekatVek. > BukaSekatVek:=proc(X::list) local K::list, n, m, l, i, j::integer: m:=nops(X): K:=[seq(seq(op(j,op(i,X)),j=1..nops(op(i,X))),i=1..m)]; end proc: Contoh: > U:=SekatVek(C,R); > BukaSekatVek(U); PrmtsVek adalah Prosedur yang mempermutasikan vektor X oleh suatu permutasi Y pada [1,2,...,n]. > PrmtsVek:= proc(X::list, Y::list) local i::integer: if nops(X)<>nops(Y) then error end if: [seq(op(i,X),i=Y)]; end proc: Contoh: > X:=[a,gus,ti,nus]: Y:=[4,1,3,2]: > PrmtsVek(X,Y);
Penetapan Konstanta Konstanta Nilai Awal > A0Dec:=convert(67452301, decimal, hex); B0Dec:=convert(EFCDAB89, decimal, hex); D0Dec:=convert(10325476, decimal, hex);
> ##C0DecErr:=convert(98BADCFE, decimal, hex); > C0Dec:=convert(10011000101110101101110011111110, decimal, binary);
> A0hex:=convert(A0Dec, hexadecimal); B0hex:=convert(B0Dec, hexadecimal); C0hex:=convert(C0Dec, hexadecimal); D0hex:=convert(D0Dec, hexadecimal);
> H0:=[A0Dec,B0Dec,C0Dec,D0Dec]; Konstanta Putaran > Pt1:=[7,12,17,22]: Pt2:=[5,9,14,20]: Pt3:=[4,11,16,23]: Pt4:=[6,10,15,21]: > Pt:=[Pt1,Pt2,Pt3,Pt4]; Konstanta Jumlah > C:=[seq(floor(evalf((2^32)*abs(sin(i)))),i=1..64)]: > S:=[4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4]: S1:=[4,4,4,4]: > C1:=SekatVek(C,S): > T:=SekatVek(C1,S1): Konstanta Permutasi Pesan > Pr1:=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]: Pr2:=[2,7,12,1,6,11,16,5,10,15,4,9,14,3,8,13]: Pr3:=[6,9,12,15,2,5,8,11,14,1,4,7,10,13,16,3]: Pr4:=[1,8,15,6,13,4,11,2,9,16,7,14,5,12,3,10]: > Pr:=[Pr1,Pr2,Pr3,Pr4]:
Pembangkitan Subblok Pesan Program Fungsi Iterasi
F adalah Prosedur fungsi non-linear F. > F1:= proc( X::list, Y::list, Z::list) local K,Hsl,S,T::list, i,m::integer: m:=nops(X): for i from 1 to m do S[i]:=(X[i])*(Y[i]): T[i]:=((X[i])+1)*(Z[i]) mod 2: if (S[i]=1 or T[i]=1) then K[i]:=1 else K[i]:=0 end if: end do: Hsl:=[seq( K[i], i=1..m )]; end proc: Contoh: > A:=[0,0,0,0,1,1,1,1]; B:=[0,0,1,1,0,0,1,1]; C:=[0,1,0,1,0,1,0,1];
> F1(A,B,C); > F2:= proc( X::list, Y::list, Z::list) local K,S,T,Hsl::list, i,m::integer: m := nops(X): for i from 1 to m do S[i]:=(X[i])*(Z[i]): T[i]:=((Z[i])+1)*(Y[i]) mod 2: if (S[i]=1 or T[i]=1) then K[i]:=1 else K[i]:=0 end if: end do: Hsl:=[seq( K[i], i=1..m )]; end proc: Contoh: > A:=[0,0,0,0,1,1,1,1]; B:=[0,0,1,1,0,0,1,1]; C:=[0,1,0,1,0,1,0,1];
> F2(A,B,C); > F3:= proc( X::list, Y::list, Z::list) local K,Hsl::list, m,i::integer: m := nops(X): for i from 1 to m do K[i]:=(X[i]+Y[i]+Z[i]) mod 2: end do: Hsl:=[seq( K[i], i=1..m )]; end proc: Contoh: > A:=[0,0,0,0,1,1,1,1]; B:=[0,0,1,1,0,0,1,1]; C:=[0,1,0,1,0,1,0,1];
> F3(A,B,C); > F4:= proc( X::list, Y::list, Z::list) local K, H, T, Hsl::list, i, m::integer: m := nops(X): for i from 1 to m do T[i]:=(Z[i]+1) mod 2: if (X[i]=1 or T[i]=1) then
H[i]:=1 else H[i]:=0 end if: K[i]:=((Y[i]+H[i]) mod 2): end do: Hsl:=[seq( K[i], i=1..m )]; end proc: Contoh: > A:=[0,0,0,0,1,1,1,1]; B:=[0,0,1,1,0,0,1,1]; C:=[0,1,0,1,0,1,0,1];
> F4(A,B,C); > F:=proc(X::list,Y::list,Z::list,n::integer[1..4]) local K::list: if n=1 then F1(A,B,C); elif n=2 then F2(A,B,C); elif n=3 then F3(A,B,C); else F4(A,B,C); end if: end proc: Contoh: > A:=[0,0,0,0,1,1,1,1]; B:=[0,0,1,1,0,0,1,1]; C:=[0,1,0,1,0,1,0,1];
> F(A,B,C,4); Kesimpulan: Jika
, maka dan jika , maka Program Fungsi iterasi > FIt:=proc(R::list,m::integer,t::integer, p::integer,k::integer[1..4]) local bvek, cvek, dvek, Fs::list, FsD, S, B, Hsl::integer: bvek:=CvrtDesVek(R[2],32): cvek:=CvrtDesVek(R[3],32): dvek:=CvrtDesVek(R[4],32): Fs := F(bvek,cvek,dvek,k): FsD := CvrtDesLitend(Fs): S := (R[1] + FsD + m + t) mod 2^32: B := PtrLgkarInt(S,p,32): Hsl:= (R[2] + B) mod 2^32; end proc:
Contoh: > Acak:=rand(2^32): M:=[seq(Acak(),i=1..4)]; > r:=1: > m:=op(1,M[1]); t:=op(1,op(1,T[r])); p:=op(1,Pt[r]);
> G:=FIt(H0,m,t,p,1); Prosedur iterasi 4 langkah dalam Ronde ke-k. > ItF:= proc(H::list, M::list, L::list, P::list,k::integer[1..4]) local S, Hsl::list, m, l, p, i, n::integer: Hsl:=H: for i from 1 to 4 do m:=M[i]: l:=L[i]: p:=P[i]: n:=FIt(Hsl,m,l,p,k): S:=subsop(1=n,Hsl): Hsl:=PtrLgkarBin(S,-1): end do: Hsl; end proc: Contoh: > M1:=[seq(Acak(),i=1..4)]; > r:=1: > T1:=op(1,T[r]);
> P1:=Pt[r]; > H1:=ItF(H0,M1,T1,P1,r);
Prosedur membangkitkan 1 blok pesan 512 bit secara acak. > GenPsn1:=proc() local K,X::list, i,j::posint, AcIn::procedure: AcIn:=rand(2^32): X:=[seq(Acak(),k=1..16)]; return(X); end proc: Contoh: > M:=GenPsn1();
Prosedur iterasi per blok pesan. > FBlok:=proc(H0::list,Mx::list) local H,M,Mi,Tt,Mt,Ps,P,C::list, i,j::posint: H:=H0: for i from 1 to 4 do P:=Pr[i]: M:=PrmtsVek(Mx,P): C:=[4,4,4,4]: Mi:=SekatVek(M,C): for j from 1 to 4 do Tt:=op(j,T[i]): Mt:=op(j,Mi); Ps:=Pt[i]; H:=ItF(H,Mt,Tt,Ps,i); end do: end do: return(H); end proc: Contoh: > FBlok(H0,M); Prosedur membangkitkan n blok pesan 512 bit secara acak. > GenPsn:=proc(n::posint) local K,X::list, i::posint: K:=[]: for i from 1 to n do X:=GenPsn1(): K:=[op(K),X]; end do: return(K); end proc: Contoh: > nB:=16: > MB:=GenPsn(nB): Prosedur Fungsi Hash MD5 untuk input M berukuran n blok pesan 512. > HashMD5:=proc(M::list) local H::list, i,n::posint: n:=nops(M): H:=H0: for i from 1 to n do H:=FBlok(H,M[i]): end do: return(H); end proc: Contoh: > xM:=MB: > HashMD5(MB);
> HashMD5(xM);
Lampiran 6 Program Hashing MD5 – Modifikasi > restart:
Pendefinisian Prosedur yang digunakan CvrtDesBigend adalah Prosedur yang mengubah Vektor Biner ke Desimal dari Order Rendah ke Order Tinggi. > CvrtDesBigend := proc( N::list ) local D1, D2 :: list, Des::integer; D1:=map(x -> 2^x,[seq(i,i=0..(nops(N)-1))]): D2:=[seq(N[j]*D1[j],j=1..nops(N))]: Des:=add( i, i=D2 ); end proc: Contoh: input I := [0,1,1,0,1], output O = 0.2^0 + 1.2^1 + 1.2^2 + 0.2^3 + 1.2^4. > A:=[0,1,1,0,1]: > CvrtDesBigend(A); CvrtDesLitend adalah Prosedur yang mengubah Vektor Biner ke Desimal dari Order Tinggi ke Order Rendah. > CvrtDesLitend := proc( M::list ) local D1, D2 :: list, Des::integer; D1:=map(x -> 2^x,[seq(i,i=0..(nops(M)-1))]): D2:=[seq(M[nops(M)+1-j]*D1[j],j=1..nops(M))]: Des:=add( i, i=D2 ); end proc: Contoh: input I := [0,1,1,0,1], output O = 0.2^4 + 1.2^3 + 1.2^2 + 0.2^1 + 1.2^0. > A:=[0,1,1,0,1]: > CvrtDesLitend(A); UrutBalik adalah Prosedur yang mengubah membalik urutan Vektor Biner dari Order Rendah ke Order Tinggi atau sebaliknya. > UrutBalik:= proc( Cr::list) local Hsl::list, i,j, n::integer: Hsl:=[op(Cr)]: n := nops(Hsl): if (n mod 2 = 0) then for i from 1 to n/2 do Hsl[i] := op(n-i+1,Cr); Hsl[n-i+1] := op(i,Cr); end do: else for i from 1 to (n-1)/2 do Hsl[i] := op(n-i+1,Cr); Hsl[n-i+1] := op(i,Cr); end do: end if; Hsl; end proc: Contoh: input I := [0,1,1,0,1], output [1, 0, 1, 1, 0].
> A:=[0,1,1,0,1]: > UrutBalik(A); PtrLgkarBin adalah Prosedur yang memutar urutan posisi bit Vektor Biner secara melingkar sejauh p bit, nilai positif berarti putar kanan dan negatif berarti putar kiri. > PtrLgkarBin:= proc( Cr::list, p::integer) local Hsl::list, i, q, j, n::integer: Hsl:=[op(Cr)]: n := nops(Hsl): q := p mod n: for i from 1 to n do j := ((i+q-1) mod n) + 1: Hsl[i] := op(j,Cr); end do: Hsl; end proc: Contoh: > A:=[6,0,1,9,8]: > A1:=PtrLgkarBin(A,-1); > A2:=PtrLgkarBin(A,-3); > PtrLgkarBin(A1,-2); PtrLgkarInt adalah Prosedur yang memutar Intejer p secara melingkar sejauh Intejer q modulo 2^m ke kiri dalam format Little Endian. > PtrLgkarInt:= proc( p::integer, q::integer, m::integer) local temp, Hsl::integer: temp := q mod m: Hsl := ((p*2^temp) mod 2^m) + floor(p/(2^(mtemp))); end proc: Contoh: > B:=PtrLgkarInt(13,2,5); > B1:=PtrLgkarInt(13,-3,5); > B2:=PtrLgkarInt(B1,-2,5); CvrtDesVek adalah Prosedur yang mengubah Interjer Desimal ke Vektor Biner dengan panjang n. > CvrtDesVek := proc( B::integer, n::posint ) local K, KVekLitend,KVekBigend,Kv::list, i::integer: K := B mod 2^n; Kv:=convert(K,base,2): KVekBigend:=[op(Kv),seq(0*i,i=(nops(Kv)+1)..n)]: KVekLitend:=UrutBalik(KVekBigend);
end proc: Contoh: > CvrtDesVek(13,4); CvrtDesVek(75,4);
CvrtBinVek adalah Prosedur yang mengubah Interjer Biner dengan panjang n ke Vektor Biner. > CvrtBinVek := proc( K::integer, n::posint ) local KVekLitend,KVekBigend,Kv::list, i,KDesLitend::integer: KDesLitend:=convert(K,decimal,binary): CvrtDesVek(KDesLitend,n); end proc: Contoh: > CvrtBinVek(11001,7); CvrtBinVek(0011001,7);
XorV adalah Prosedur yang me-xor-kan dua Vektor Biner. > XorV:= proc( X::list, Y::list) local Z, Hsl::list, i, n, m::integer: m := nops(X): n := nops(Y): if m<>n then error end if: for i from 1 to m do Z[i] := (X[i]+Y[i]) mod 2: end do: Hsl:=[seq( Z[i], i=1..m )]; end proc: Contoh: > A:=[1,0,1,1,0,1,1]: B:=[1,0,1,0,0,0,1]: > XorV(A,B); XorD adalah Prosedur yang me-xor-kan dua Intejer Desimal modulo 2^n. > XorD:= proc( a::integer, b::integer, n::posint) local X, Y, Hv::list, Hsl::integer: X := CvrtDesVek(a,n): Y := CvrtDesVek(b,n): Hv := XorV(X,Y); Hsl := CvrtDesLitend(Hv); end proc: Contoh: > XorD(5,11,4); > XorD(12,1,4); SekatVek adalah Prosedur yang menyekat Vektor X dengan panjang n menjadi Y=[y1,y2,...,yr], dimana yi intejer positif dan y1+y2+...+yr=n. > SekatVek:=proc(X::list,Y::list) local L, K, M::list, n, m, l, i, j::integer:
l:=nops(Y): n:=add(i,i=Y): m:=nops(X): if n<>m then error end if: K:=[seq([seq(op(j,X),j=(op(i,Y))*(i1)+1..(op(i,Y))*i)],i=1..l)]; end proc: Contoh: > C := [15,5,14,2,3,16,12,9,4,11,7,13,6,10,1,8]: > R:=[8,4,4]: > SekatVek(C,R); BukaSekatVek adalah prosedur yang menbuka sekat dari ouput prosedur SekatVek. > BukaSekatVek:=proc(X::list) local K::list, n, m, l, i, j::integer: m:=nops(X): K:=[seq(seq(op(j,op(i,X)),j=1..nops(op(i,X))),i=1..m)]; end proc: Contoh: > U:=SekatVek(C,R); > BukaSekatVek(U); PrmtsVek adalah Prosedur yang mempermutasikan vektor X oleh suatu permutasi Y pada [1,2,...,n]. > PrmtsVek:= proc(X::list, Y::list) local i::integer: if nops(X)<>nops(Y) then error end if: [seq(op(i,X),i=Y)]; end proc: Contoh: > X:=[a,gus,ti,nus]: Y:=[4,1,3,2]: > PrmtsVek(X,Y);
Penetapan Konstanta Konstanta Nilai Awal > A0Dec:=convert(67452301, decimal, hex); B0Dec:=convert(EFCDAB89, decimal, hex); D0Dec:=convert(10325476, decimal, hex);
> ##C0DecErr:=convert(98BADCFE, decimal, hex); > C0Dec:=convert(10011000101110101101110011111110, decimal, binary);
> A0hex:=convert(A0Dec, hexadecimal); B0hex:=convert(B0Dec, hexadecimal); C0hex:=convert(C0Dec, hexadecimal); D0hex:=convert(D0Dec, hexadecimal);
> H0:=[A0Dec,B0Dec,C0Dec,D0Dec];
Konstanta Jumlah > C:=[seq(floor(evalf((2^32)*abs(sin(i)))),i=1..64)]: > S:=[4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4]: S1:=[4,4,4,4]: > C1:=SekatVek(C,S): > T:=SekatVek(C1,S1): Konstanta Permutasi Pesan > Pr1:=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]: Pr2:=[2,7,12,1,6,11,16,5,10,15,4,9,14,3,8,13]: Pr3:=[6,9,12,15,2,5,8,11,14,1,4,7,10,13,16,3]: Pr4:=[1,8,15,6,13,4,11,2,9,16,7,14,5,12,3,10]: > Pr:=[Pr1,Pr2,Pr3,Pr4]:
Pembangkitan Subblok Pesan Program Fungsi Iterasi
F adalah Prosedur fungsi non-linear F. > F1:=proc( X::list, Y::list, Z::list) local nY,nZ,K,H,L,Hsl::list, i,m::integer: m := nops(X): for i from 1 to m do nY[i]:=(Y[i]+1) mod 2: if (nY[i]=1 or Z[i]=1) then H[i]:=1 else H[i]:=0 end if: nZ[i]:=(Z[i]+1) mod 2: if (nZ[i]=1 or Y[i]=1) then L[i]:=1 else L[i]:=0 end if: K[i]:=((X[i]+H[i]) mod 2)*L[i]: end do: Hsl:=[seq( K[i], i=1..m )]; end proc: Contoh: > A:=[0,0,0,0,1,1,1,1]; B:=[0,0,1,1,0,0,1,1]; C:=[0,1,0,1,0,1,0,1];
> F1(A,B,C); F1(A,C,B); F1(B,A,C); F1(C,A,B); F1(B,C,A); F1(C,B,A);
> F3:= proc( X::list, Y::list, Z::list) local nX,K,H,Hsl::list, i,m::integer: m := nops(X): for i from 1 to m do nX[i]:=(X[i]+1) mod 2: if (nX[i]=1 or Z[i]=1) then H[i]:=1 else H[i]:=0 end if: K[i]:=(((Y[i]+1)+(nX[i]*Z[i])) mod 2)*H[i]: end do: Hsl:=[seq( K[i], i=1..m )]; end proc: Contoh: > A:=[0,0,0,0,1,1,1,1]; B:=[0,0,1,1,0,0,1,1]; C:=[0,1,0,1,0,1,0,1];
> F3(A,B,C); F3(A,C,B); F3(B,A,C); F3(C,A,B); F3(B,C,A); F3(C,B,A);
> F2:= proc( X::list, Y::list, Z::list)
local K,L,H,nX,nY,Hsl::list, i,m::integer: m := nops(X): for i from 1 to m do nX[i]:=(X[i]+1) mod 2: nY[i]:=(Y[i]+1) mod 2: H[i]:=(Z[i]+(nX[i]*Y[i])) mod 2: L[i]:=X[i]*nY[i]: if (H[i]=1 or L[i]=1) then K[i]:=1 else K[i]:=0 end if: end do: Hsl:=[seq( K[i], i=1..m )]; end proc: Contoh: > A:=[0,0,0,0,1,1,1,1]; B:=[0,0,1,1,0,0,1,1]; C:=[0,1,0,1,0,1,0,1];
> F2(A,B,C); F2(A,C,B); F2(B,A,C); F2(C,A,B); F2(B,C,A); F2(C,B,A);
> F4:=proc( X::list, Y::list, Z::list) local nZ,K,H,Hsl::list, i,m::integer: m := nops(X): for i from 1 to m do nZ[i]:=(Z[i]+1) mod 2: if (nZ[i]=1 or Y[i]=1) then H[i]:=1 else H[i]:=0 end if: K[i]:=((X[i]+1)+(Y[i]*nZ[i])+H[i]) mod 2: end do: Hsl:=[seq( K[i], i=1..m )]; end proc: Contoh: > A:=[0,0,0,0,1,1,1,1]; B:=[0,0,1,1,0,0,1,1]; C:=[0,1,0,1,0,1,0,1];
> F4(A,B,C); F4(A,C,B); F4(B,A,C); F4(C,A,B); F4(B,C,A); F4(C,B,A);
> F:=proc(X::list,Y::list,Z::list,n::integer[1..4]) local K::list: if n=1 then F1(A,B,C); elif n=2 then F2(A,B,C); elif n=3 then F3(A,B,C); else F4(A,B,C); end if: end proc: Contoh: > A:=[0,0,0,0,1,1,1,1]; B:=[0,0,1,1,0,0,1,1]; C:=[0,1,0,1,0,1,0,1];
> F(A,B,C,4); , maka dan jika , maka Program Fungsi iterasi > FIt:=proc(R::list,m::integer,t::integer,k::integer[1..4]) local bvek, cvek, dvek, Fs::list, FsD, S, B, Hsl,p::integer: bvek:=CvrtDesVek(R[2],32): cvek:=CvrtDesVek(R[3],32): dvek:=CvrtDesVek(R[4],32): Fs := F(bvek,cvek,dvek,k): FsD := CvrtDesLitend(Fs): S := (R[1] + FsD + m + t) mod 2^32: p:=XorD(FsD,t,32) mod 2^5; #konstanta putar diubah merambat. Kesimpulan: Jika
B := PtrLgkarInt(S,p,32): Hsl:= (R[2] + B) mod 2^32; end proc: Contoh: > Acak:=rand(2^32): M:=[seq(Acak(),i=1..4)]; > r:=1: > m:=op(1,M[1]); t:=op(1,op(1,T[r]));
> G:=FIt(H0,m,t,1); Prosedur iterasi 4 langkah dalam Ronde ke-k. > ItF:= proc(H::list, M::list, T::list, k::integer[1..4]) local S, Hsl::list, m, t, i, n::integer: Hsl:=H: t:=H[4]: for i from 1 to 4 do m:=M[i]: t:=XorD(t,T[i],32): #Konstanta Jumlah dibuat merambat. n:=FIt(Hsl,m,t,k): S:=subsop(1=n,Hsl): Hsl:=PtrLgkarBin(S,-1): end do: Hsl; end proc: Contoh: > M1:=[seq(Acak(),i=1..4)]; > r:=1: > T1:=op(1,T[r]);
> H1:=ItF(H0,M1,T1,r);
Prosedur membangkitkan 1 blok pesan 512 bit secara acak. > GenPsn1:=proc() local K,X::list, i,j::posint, AcIn::procedure: AcIn:=rand(2^32): X:=[seq(Acak(),k=1..16)]; return(X); end proc: Contoh: > M:=GenPsn1();
Prosedur iterasi per blok pesan. > FBlok:=proc(H0::list,Mx::list) local H,M,Mi,Tt,Mt,Ps,P,C::list, i,j::posint: H:=H0: for i from 1 to 4 do P:=Pr[i]: M:=PrmtsVek(Mx,P): C:=[4,4,4,4]: Mi:=SekatVek(M,C): for j from 1 to 4 do Tt:=op(j,T[i]): Mt:=op(j,Mi); H:=ItF(H,Mt,Tt,i); end do: end do: return(H); end proc: Contoh: > FBlok(H0,M); Prosedur membangkitkan n blok pesan 512 bit secara acak. > GenPsn:=proc(n::posint) local K,X::list, i::posint: K:=[]: for i from 1 to n do X:=GenPsn1(): K:=[op(K),X]; end do: return(K); end proc: Contoh: > nB:=16: > MB:=GenPsn(nB): Prosedur Fungsi Hash MD5 untuk input M berukuran n blok pesan 512. > HashMD5:=proc(M::list) local H::list, i,n::posint: n:=nops(M): H:=H0: for i from 1 to n do H:=FBlok(H,M[i]): end do: return(H); end proc: Contoh: > xM:=MB: > HashMD5(MB);
> HashMD5(xM);
