Kupas Tuntas Serangan MD5 dengan Collision Attack

Kupas Tuntas Serangan MD5 dengan Collision Attack Ginanjar Pramadita NIM 13506014 Teknik Informatika Institut Teknologi Bandung Jalan Ganesha10, Bandung 2008 e-mail: [email protected]

ABSTRAK Salah satu fungsi hash satu arah yang banyak digunakan adalah algoritma MD5 yang ditemukan oleh Ronald Rivest pada tahun 1991 namun telah berhasil di kriptanalisis oleh Arjen Lenstra, Xiaoyun Wang, dan Benne de Weger pada tahun 2005 dan beberapa waktu kemudian, Vlastimil Klima telah berhasil memperbaiki algoritma Arjen Lenstra dkk. sehingga mampu mengkriptanalisis MD5 lebih cepat. Pada makalah yang akan saya buat ini, saya akan mengupas dengan mendalam mengenai algoritma MD5 dan teknik-teknik kriptanalisis menggunakan algoritma Arjen Lenstra dkk. dan Vlastimil Klima beserta berbagai perbaikan terhadap algoritma-algoritma tersebut agar proses kriptanalisis menjadi lebih mangkus dan sangkil. Kata Kunci: MD5, collision attack, kriptografi, kriptanalisis, hash

1.

Pendahuluan

MD5 adalah salah satu fungsi has yang dapat mengkompresi keberagaman panjang message menjadi ukuran tertentu yang terdefinisi (misalnua 128 bit). Dalam fungsi hash digunakan XOR, rotasi bit, dan berbagai operasi lain yang ringan sehingga dapat dikakulasi dengan cepat. Salah satu hal yang sangat penting dalam fungsi hash adalah collision resistance. Misalnya p adalah plaintext dan h(p) adalah fungsi hash yang menghasilkan message digest v, maka collision resistance berarti kesulitan (bahkan tidak boleh) untuk menemukan pasaman message(p, q) dimana h(p) = h(q). Pada tahun 2005, Wang et all menemukan collision attack yang efisien untuk MD5. Teknik dalam serangan ini menggunakan differential attack. Umumnya, differential attack menggunakan operasi XOR namun Wang et al menggunakan modular substraction [2]. Dalam metoda Wang ini,

2.

Deskripsi MD5

MD5 adalah fungsi kompresi yang mengkalkulasikan 128 bit bilangan acak dari suatu message dengan berbagai panjang. Pada saat message M dimasukan, nilai hash dari M dihitung dengan cara di bawah ini: 1) Message M dibagi ke dalam 512-bit messag: 𝑀 = (𝑀0 , 𝑀1 , 𝑀2 , … 𝑀𝑛 ), 𝑀𝑖 = 512 2) Misalkan hi adalah keluaran dari operasi ke-i maka hI dihitung mungginakan fungsi kompresi MD5 dengan Mi-1 dan hi-1. Ulangi proses ini dari M0 hingga Mn. Nilai awal h0 didefinisikan sebagai berikut: h0 = (0x67452301; 0xefcdab89; 0x98badcfe; 0x10325476). 3) Keluaran dari operasi untuk message terakhir adalam nilai hash dari M Misalnya message Mj dikompresi dengan fungsi kompresi dan operasi ini disebit operasi blok (j + 1).d Setiap blok terdiri dari 64 langkah. 

Langkah ke-1 hingga ke-16 disebut putaran ke-1.

1

  

Langkah ke-17 hingga ke-32 disebut putaran ke-2, langkah ke-33 hingga ke-48 disebut putaran ke-3 dan Langkah ke-49 hingga langkah ke64 disebut putaran ke-4

3. 3.1

Dalam setiap langkah, salah satu rantai variable a, b, c, d dihitung dan urutan variable adalah a1, d1, c1, b1, a1, … . Keluaran dari setiap blok adalah ℎ𝑖 = (𝑎0 + 𝑎16 , 𝑏0 + 𝑏16 , 𝑐0 + 𝑐16 , 𝑑0 + 𝑑16 ) (1) Variable rantai dihitung dengan cara sebagai berikut. Pertama, Mj dibagi ke dalam 32 bit message m0, … m15. Selanjutnya fungsi 𝜓 didefinisikan sebagai berikut 𝜓 𝑥, 𝑦, 𝑧, 𝑤, 𝑚, 𝑠, 𝑡 =𝑦 + 𝑥 + 𝜙 𝑦, 𝑧, 𝑤 + 𝑚 + 𝑡 𝑚𝑜𝑑232

⋘𝑠 (2)

Dimana m adalah message input dalam langkah. S adalah banyaknya left siklik sift yang didefiniskan untuk setiap langkah. t adalah kostanta yang didefiniskan pada setiap langkah. ϕ adalah fungsi nonlinear yang didefinisikan pada setiap putaran. Rincian fungsi ϕ adalah sebagai berikut:    

1R 2R 3R 4R

:𝜙 :𝜙 :𝜙 :𝜙

𝑦, 𝑧, 𝑤 𝑦, 𝑧, 𝑤 𝑦, 𝑧, 𝑤 𝑦, 𝑧, 𝑤

(3) Variable berantai ai, bi, ci, di didefinisikan sebagai berikut    

𝑎𝑖 = 𝜓 𝑎𝑖−1 , 𝑏𝑖−1 , 𝑐𝑖−1 , 𝑑𝑖−1 , 𝑚, 𝑠, 𝑡 𝑏𝑖 = 𝜓 𝑏𝑖−1 , 𝑐𝑖 , 𝑑𝑖 , 𝑎𝑖 , 𝑚, 𝑠, 𝑡 𝑐𝑖 = 𝜓 𝑐𝑖−1 , 𝑑𝑖 , 𝑎𝑖 , 𝑏𝑖−1 , 𝑚, 𝑠, 𝑡 𝑑𝑖 = 𝜓 𝑑𝑖−1 , 𝑎𝑖 , 𝑏𝑖−1 , 𝑐𝑖−1 , 𝑚, 𝑠, 𝑡

Kondisi Tambahan

Untuk memperbaiki kondisi di putaran kedua, diperlukan untuk membuat “kondisi tambahan”. Tujuan untuk menset kondisi tambahan adalah untuk menjamin bahwa kondisi putaran kedua dapat diperbaiki. Kondisi tambahan pada putaran pertama diset bersama dengan kondisi uang memenuhi untuk putaran pertama dengan modifikasi message tunggal. Kondisi tambahan pada putaran kedua diset dengan modifikasi multi-message. Algoritma pencarian collision untuk blok pertama termasuk kondisi tambahan, adalah sebagai berikut 1) Mengenerate random message 2) Modifikasi message untuk memenuhi kondisi wajib dan pada putaran pertama dengan modifikasi message tunggal. 3) Jika kondisi wajib dan kondisi tambahan pada putaran kedua tidak terpenuhi, maka dapat diperbaiki dengan modifikasi multi-message. 4) Jika modifikasi message tidak memenuhi semua kondisi wajib, pilih m14 dan m15 lagi dan kembali ke 2). Algoritma pencarian collision untuk blok kedua hampir sama dengan blok pertama. 3.2

= 𝑦 ∧ 𝑧 ∨ (~𝑦 ∧ 𝑤) = 𝑦 ∧ 𝑤 ∨ (𝑧 ∧ ~𝑤) =𝑦⊕𝑧⊕ w = 𝑧 ⊕ (𝑦 ∨ ~𝑤)

Modifikasi Multi-Message

Rincian Modifikasi Multi-Messsage

Terdapat 14 kondisi pada putaran pertama yang dapat diperbaiki, yaitu: a5;4, a5;16, a5;18, a5;32, d5;18, d5;30, d5;32; c5;18, c5;32, b5;32, a6;18, a6;32, d6;32 and c6;32. 3.2.1 Perbaikan untuk a5,i (i =4, 16, 18, 32) a5 dihitung dengan ekspresi berikut 𝑎5 = 𝑏4 + (𝑎4 + 𝜙 𝑏4 , 𝑐4 , 𝑑4 + 𝑚1 + 𝑡) ⋘ 5 (5)

(4)

Bit ke-i pada a5 dapat diberpaiki dengan modifikasi message yang ditunjukan pada tabel 1

2

Tabel 1: Modifikasi message untuk memperbaiki a5,i

3.2.2 Perbaikan untuk d5,i (i = 18, 30) d5 dihitung dengan ekspresi sebagai berikut 𝑑5 = 𝑎5 + (𝑑4 + 𝜙 𝑎4 , 𝑏4 , 𝑐4 + 𝑚6 + 𝑡) ⋘ 9 (6) Bit ke-i pada d5 dapat diperbaiki dengan modifikasi message pada Table 2.

Tabel 2: Modifikasi message untuk memperbaiki d5,i

Tabel 3: Modifikasi message untuk memperbaiki d5,32

Pada Tabel 3, tujuan menset c1,23 = 0 adalam untuk membatasi arah perubahan karena kondisi wajib b1,23 = c1,23 telah ada. Terdapat perbaikan nilai untuk b1,23 setelah adanya modifikasi m2.

3.2.3 Perbaikan Kondisi Lainnya Perbaikan kondisi-kondisi lainnya ditunjukan pada Tabel 4 hingga 10.

Tabel 4: Modifikasi message untuk memperbaiki c5,18

Tabel 5: Modifikasi message untuk memperbaiki c5,32

3

Tabel 6: Modifikasi message untuk memperbaiki b5,32

Tabel 7: Modifikasi message untuk memperbaiki a6,18

Tabel 8: Modifikasi message untuk memperbaiki c6,32

Tabel 9: Modifikasi message untuk memperbaiki d6,32

Tabel 10: Modifikasi message untuk memperbaiki c6,32

4

4.

Aplikasi Pencarian Collision MD5

Misalnya terdapat dua vektor vec1 dan vec2 yang yang memiliki message digest MD5 yang sama. (sumber: http://www.doxpara.com/md5_someday.pdf) static byte[] vec1 = { 0xd1, 0x31, 0xdd, 0x02, 0xc5, 0xe6 , 0xee , 0xc4 , 0x69 , 0x3d, 0x9a , 0x06 , 0x98 , 0xaf , 0xf9 , 0x5c , 0x2f , 0xca , 0xb5 , /**/0x87 , 0x12 , 0x46 , 0x7e , 0xab , 0x40 , 0x04 , 0x58 , 0x3e , 0xb8 , 0xfb , 0x7f , 0x89 , 0x55 , 0xad , 0x34 , 0x06 , 0x09 , 0xf4 , 0xb3 , 0x02 , 0x83 , 0xe4 , 0x88 , 0x83 , 0x25 , 0x71 , 0x41 , 0x5a, 0x08 , 0x51 , 0x25 , 0xe8 , 0xf7 , 0xcd , 0xc9 , 0x9f , 0xd9 , 0x1d , 0xbd , 0xf2 , 0x80 , 0x37 , 0x3c , 0x5b , 0xd8 , 0x82 , 0x3e , 0x31 , 0x56 , 0x34 , 0x8f , 0x5b , 0xae , 0x6d , 0xac , 0xd4 , 0x36 , 0xc9 , 0x19 , 0xc6 , 0xdd , 0x53 , 0xe2 , 0xb4 , 0x87 , 0xda , 0x03 , 0xfd , 0x02 , 0x39 , 0x63 , 0x06 , 0xd2 , 0x48 , 0xcd , 0xa0 , 0xe9 , 0x9f , 0x33 , 0x42 , 0x0f , 0x57 , 0x7e , 0xe8 , 0xce , 0x54 , 0xb6 , 0x70 , 0x80 , 0xa8 , 0x0d , 0x1e , 0xc6 , 0x98 , 0x21 , 0xbc , 0xb6 , 0xa8 , 0x83 , 0x93 , 0x96 , 0xf9 , 0x65 , 0x2b , 0x6f , 0xf7 , 0x2a , 0x70 }; static byte[] vec2 = { 0xd1 , 0x31, 0xdd , 0x02 , 0xc5 , 0xe6 , 0xee , 0xc4 , 0x69 , 0x3d , 0x9a , 0x06 , 0x98 , 0xaf , 0xf9 , 0x5c, 0x2f , 0xca , 0xb5 , /**/0x07 , 0x12 , 0x46 , 0x7e , 0xab , 0x40 , 0x04 , 0x58 , 0x3e , 0xb8 , 0xfb , 0x7f , 0x89 , 0x55 , 0xad , 0x34 , 0x06 , 0x09 , 0xf4 , 0xb3 , 0x02 , 0x83 , 0xe4 , 0x88 , 0x83 , 0x25 ,/**/ 0xf1 , 0x41 , 0x5a , 0x08 , 0x51 , 0x25 , 0xe8 , 0xf7 , 0xcd , 0xc9 , 0x9f , 0xd9 , 0x1d , 0xbd , /**/0x72 , 0x80 , 0x37 , 0x3c , 0x5b, 0xd8 , 0x82 , 0x3e , 0x31 , 0x56 , 0x34 , 0x8f , 0x5b , 0xae , 0x6d , 0xac , 0xd4 , 0x36 , 0xc9 , 0x19 , 0xc6 , 0xdd , 0x53 , 0xe2 , /**/0x34 , 0x87 , 0xda , 0x03 , 0xfd , 0x02 , 0x39 , 0x63 , 0x06 , 0xd2 , 0x48 , 0xcd , 0xa0, 0xe9 , 0x9f , 0x33 , 0x42 , 0x0f , 0x57 , 0x7e , 0xe8 , 0xce , 0x54 , 0xb6 , 0x70 , 0x80 , /**/ 0x28 , 0x0d , 0x1e, 0xc6 , 0x98 , 0x21 , 0xbc , 0xb6 , 0xa8 , 0x83 , 0x93 , 0x96 , 0xf9 , 0x65 , /* flag byte*/0xab , 0x6f , 0xf7 , 0x2a , 0x70 };

berikut: MD5(vec1 + data) = MD5(vec2 + data). Data dibangun dengan:    

Panjang message 1 Panjang message 2 Isi message 1 Isi message 2

Program untuk mengenerate adalah sebagai berikut static void Main(string[] args) { if (args.Length != 2) Usage(); byte[] goodFile=ReadBinaryFile(args[0]); byte[] evilFile=ReadBinaryFile(args[1]); WriteBinary("good.bin", vec1, goodFile, evilFile); WriteBinary("evil.bin", vec2, goodFile, evilFile); ShowMD5("good.bin"); ShowMD5("evil.bin"); } private static void Usage () { Console.WriteLine("Usage: md5gen good_file evil_file"); Environment.Exit (-1); } private static void WriteBinary (string sOutFileName, byte[] prefix, byte[] goodFile, byte[] evilFile) { using (FileStream fs = File.OpenWrite (sOutFileName)) { using (BinaryWriter writer = new BinaryWriter(fs)) { writer.Write(prefix); writer.Write ( goodFile.Length ); writer.Write ( evilFile.Length ); fs.Write (goodFile, 0, goodFile.Length); fs.Write (evilFile, 0, evilFile.Length); fs.Close (); } } }

Dengan adanya pasanyan ini, maka sembarang data dengan sembarang ukuran akan memenuhi aturan

5

else { byte[] good = reader.ReadBytes (goodSize); using (BinaryWriter writer = new BinaryWriter( File.OpenWrite (soutputfile))) { writer.Write (good); writer.Close (); } } Console.WriteLine ("File written on {0}", soutputfile);

Program mengextraksi [STAThread] static void Main(string[] args) { if (args.Length == 0) Usage(); ExtractFile(args[0], args[1]); } private static void ExtractFile ( string sfilename, string soutputfile) { using (BinaryReader reader = new BinaryReader( File.OpenRead (sfilename))) { byte[] vec = reader.ReadBytes (128); int goodSize = reader.ReadInt32 (); int evilSize = reader.ReadInt32 (); /// open evil file if (vec[123] == 0xab) { reader.ReadBytes (goodSize); byte[] evil = reader.ReadBytes (evilSize); using (BinaryWriter writer = new BinaryWriter( File.OpenWrite (soutputfile))) { writer.Write (evil); writer.Close (); } }

} } private static void Usage () { Console.WriteLine( "Usage: md5extract file.bin output_file.exe"); Environment.Exit (-1); }

Gambar 1: Mengenerate Collision Modus penggunaan (Lihat Gambar 1) Misal goodFile adalah prorgam yang tidak berbahaya dan telah ditandatangani digital. Selanjutnya, program dengan tanda tangan yang sama dapat dikirim misalnya evilFile.bin yang

merupakan malware yang akan menimpa program goodFile.bin. Hal ini dapat dilakukan karena kedua file tersebut memiliki hash yang sama. Pada Gambar 1 goodexe.exe dan evilexe.exe dibuat pasangan collisionnya menggunakan fungsi dan 6

menghasilkan good.bin dan evil.bin yang memiliki MD5 hash yang sama. Selanjutnya kedua file ini dapat saling menggantikan. DAFTAR PUSTAKA [1] Rinaldi Munir. Diktat Kuliah Kriptografi Program Studi Teknik Informatika Institut Teknologi Bandung. 2006 [2] X. Wang, X. Lai, D. Feng, H. Chen, X. Yu: Cryptanalysis of the Hash Functions MD4 and RIPEMD, Advances in EUROCRYPT2005, LNCS 3494, pp. 1–18, 2005. [3] R.L. Rivest. The MD5 Message-Digest algorithm. Internet RFC, April 1992. RFC 1321. [4] V. Klima: Finding MD5 Collisions on a Notebook PC Using Multi-message Modifications. 2005 [5] H. Dobbertin: The status of MD5 after a recent attack, CryptoBytes 2 (2), 1996 [6] Jie Liang and Xuejia Lai. Improved Collision Attack on Hash Function MD5. 2005

7