STUDI MENGENAI KRIPTANALISIS UNTUK BLOCK CIPHER DES DENGAN TEKNIK DIFFERENTIAL DAN LINEAR CRYPTANALYSIS Luqman Abdul Mushawwir – NIM 13507029 Program Studi Teknik Informatika Sekolah Teknik Elektro dan Informatika Institut Teknologi Bandung Jalan Ganesha 10 Bandung E-Mail:
[email protected]
ABSTRAK Salah satu metode kriptografi yang pernah sangat populer saat ini adalah DES, yaitu Data Encryption Standard, yang merupakan salah satu terapan dari block cipher. Block cipher sendiri adalah satu metode kriptografi yang masih sering digunakan, bahkan dalam pengembangan DES sendiri, seperti Triple DES, DES-X, AES dan lain-lain. DES sendiri dikembangkan karena seiring perkembangan zaman, DES diketahui memiliki kelemahan-kelemahan. Beberapa teknik yang dipakai untuk menyerang DES dan membuktikan DES sudah tidak aman lagi, di antaranya adalah differential cryptanalyisis dan linear cryptanalysis. Differential cryptanalysis menyerang DES dengan memanfaatkan pola perbedaan antara masukan dan keluaran. Linear cryptanalysis menyerang DES dengan memanfaatkan keuntungan tingginya kemunculan ekspresi linear yang melibatkan bit dari plainteks, cipherteks dan upakunci (subkey). Makalah ini akan menggali dan menerapkan metode kriptanalisis differential cryptanalysis dan linear cryptanalysis pada DES. Di sini akan dijelaskan mengenai langkah-langkah yang digunakan pada pembuatan DES, masingmasing metode kriptanalisis, serta akan dipaparkan mengenai perbandingan dari kedua serangan dalam menyerang algoritma DES. Kata Kunci: Block cipher, DES, differential cryptanalysis, linear cryptanalysis
1. PENDAHULUAN 1.1 Block Cipher Sebuah block cipher n-bit adalah sebuah cipher yang beroperasi di sebuah plainteks yang telah dibagi menjadi beberapa blok bit dengan panjang satu blok adalah n bit. Blok-blok plainteks tersebut dienkripsi dengan kunci yang mempunyai panjang sama dengan blok plainteksnya. Block cipher mempunyai beberapa skema, yaitu: - Electronic Code Book (ECB) - Cipher Block Chaining (CBC) - Cipher Feedback (CFB) - Output Feedback (OFB) ECB mempunyai skema sebagai berikut:
Gambar 1. Skema ECB CBC mempunyai skema sebagai berikut:
2. Pada hasil permutasi awal kemudian dilakukan proses enkripsi sebanyak 16 kali (16 putaran). Setiap putaran menggunakan kunci internal yang berbeda. 3. Hasil proses enciphering kemudian dipermutasi dengan matriks permutasi balikan (invers initial permutation atau IP-1 ) menjadi blok cipherteks.
Gambar 2. Skema CBC CFB mempunyai skema sebagai berikut:
Gambar 3. Skema CFB OFB mempunyai skema sebagai berikut:
Gambar 5. Skema umum DES
1.2 Kriptanalisis Gambar 4. Skema OFB
Kriptanalisis yang akan mengkriptanalisis DES dan kriptanalisis sebagai berikut.
dipakai FEAL
untuk adalah
Data Encryption Standard (DES) DES merupakan block cipher kunci-simetri yang paling diketahui di seluruh dunia. DES beroperasi pada ukuran blok 64 bit. DES mengenkripsikan 64 bit plainteks menjadi 64 bit cipherteks dengan 56 bit kunci internal yang dibangkitkan oleh 64 bit kunci eksternal.
1. Linear Cryptanalysis Linear Cryptanalysis adalah sebuah chosen-plaintext attack yang dibuat oleh Matsui dan Yamagashi yang pertama kali dibuat untuk menyerang algoritma FEAL. Setelah sukses menyerang FEAL, metode ini digunakan oleh Matsui untuk menyerang algoritma DES.
Skema umum DES adalah sebagai berikut: 1. Blok plainteks dipermutasi dengan matriks permutasi awal (initial permutation atau IP).
Serangan ini memerlukan 243 plainteks yang diketahui dan cipherteks yang berkoresponden dengannya.
Linear Cryptanalysis bekerja dengan memodelkan komponen non-linear pada sebuah cipher dengan aproksimasi mendekati linear. Dengan aproksimasi yang baik, sebuah fungsi mendekati linear mengaproksimasi fungsi orijinal dengan probabilitas p = 0.5 + ε dengan | ε | sebesar mungkin. Jika (a, b) 𝜖 GF(2)n x GF(2)n adalah sebuah pasangan dengan a ≠ 0 sebagai input mask dan b sebagai output mask. Probabilitas linear (LP) untuk (a, b) adalah sebagai berikut: LP (a, b) = (2 . PrX {(a, X) = (b, ρ(X))} – 1)2 ...(1) Vektor dari mask A = (a1, ..., ar+1) dengan ai ≠ 0 dan 1 ≤ i ≤ r disebut karakterisitik linear dari sebuah cipher. Matsui kemudian membuat sebuah Lemma, yang disebut Piling-Up Lemma. Asumsikan X1, ..., Xn variabel random yang merepresentasikan bit dan ε1, ..., εn adalah simpangannya. Kemudian, simpangan tersebut bisa kita hitung dengan berikut:
(2) Dengan menggunakan Piling-Up Lemma, kita dapat mengestimasi kemungkinan suksesnya serangan dengan linear cryptanalysis. Jika kemungkinan untuk setiap aproksimasinya diketahui. 2. Differential Cryptanalysis Differential cryptanalysis merupakan sebuah chosenplaintext attack yang pertama kali dibuat untuk menyerang block cipher FEAL. Dengan mengenkripsi sepasang plainteks yang dipilih secara hati-hati kepada cipherteks dengan kunci yang sama, penyerang dapat memprediksi apakah bit-bit dari input sampai akhir sama atau tidak. Ini didapat dengan menggunakan pola diferensiasi pada input. Dengan persamaan f : GF(2)n -> GF(2)n yang merupakan fungsi vectorial boolean, pola diferensiasi adalah sebagai berikut: Sebuah pola diferensiasi untuk f adalah sebuah tuple (∆I, ∆O), yang untuk sebuah input ∆I diferensiasi output f(x) + f(x + ∆I) mungkin dapat mempunyai nilai ∆O. Biasanya, pola diferensiasi hanya didefinisikan pada lingkaran transformasi. Untuk mengikuti jalur dari pola diferensiasi, sebuah “karakteristik” didefinisikan sebagai berikut:
Sebuah karakteristik r-putaran adalah sebuah tuple (r + 1) dari pola differensiasi (Λ1, ... ,Λr+1). Untuk karakteristik satu putaran, probabilitas sebuah diferensiasi di input dari putaran menghasilkan diferensiasi output yang telah dijelaskan sebelumnya disebut probabilitas dari karakteristik, untuk sebuah fungsi f : GF(2)n -> GF(2)n. Jika X menotasikan sebuah variabel random yang terdistribusi dalam GF(2)n, probabilitas diferensial untuk pasangan (∆I, ∆O) 𝜖 GF(2)n x GF (2)n dengan ∆I ≠ 0, didefinisikan sebagai berikut: DP(∆I, ∆O) = PrX {ρ(X) + ρ(X + ∆I) = ∆O} ...(3) Dengan asumsi nilai input untuk setiap putaran terdistribusi secara acak dan independen satu sama lain, probabilitas untuk karakteristik r-putaran sama dengan probabilitas untuk karakteristik satu putaran. Diferensial didefinisikan sebagai berikut. Sebuah diferensial r-putaran adalah sebuah tuple (∆I, ∆O) dengan ∆I adalah perbedaan input dan ∆O adalah perbedaan output setelah r putaran. Setelah mendapatkan diferensial dari cipherteks dan plainteks yang dipilih, kita menganggap diferensial tersebut adalah perbedaan di dalam S-Box untuk mendapatkan bit-bit kunci.
2. PEMBAHASAN 2.1 DES yang Digunakan DES yang digunakan pada pembahasan kali ini adalah DES dengan mode penerapan ECB, karena penerapan DES dengan mode ECB lebih sederhana. Pengenkripsian plainteks dengan DES dengan langkah-langkah sebagai berikut: - Kunci ditentukan oleh pengguna - Pembangkitan matriks initial permutation (IP) dan invers initial permutation (IP-1) - Melakukan permutasi kepada plainteks dengan menggunakan IP - Enciphering plainteks dengan 16 putaran jaringan feistel dengan fungsi: Li = R –1 dan Ri = Li–1 f(Ri–1, Ki) dengan pembangkitan kunci internal di setiap putarannya dengan matriks-matriks permutasi kompresi - Melakukan permutasi lagi pada hasil enciphering dengan menggunakan IP-1 menghasilkan cipherteks yang diinginkan Sedangkan fungsi f pada jaringan feistel adalah sebagai berikut: - Ri-1 diekspansi menjadi 48 bit dengan matriks permutasi ekspansi. - Hasil ekspansi di-XOR-kan dengan kunci internal yang dibangkitkan pada putaran itu, menghasilkan vektor A. - Vektor A dibagi menjadi 8 bagian, masingmasing 6 bit, dan menjadi masukan untuk matriks substitusi menjadi vektor B. - Hasil substitusi tersebut dipermutasi oleh sebuah matriks P menjadi vektor P(B). - P(B) di-XOR-kan dengan Li–1 menghasilkan Ri: Ri = Li-1 P(B) Setelah semua proses di atas, didapatkan cipherteks yang diinginkan.
2.2 Penerapan Linear Cryptanalysis pada Algoritma DES Penerapan Linear Cryptanalysis Linear Cryptanalysis yang dilakukan pada DES yang telah dibuat dilakukan dengan langkah-langkah sebagai berikut: 1. Melakukan aproksimasi linear sebanyak r-1 putaran pada r putaran cipher dengan bagan sebagai berikut:
Gambar 6. Satu putaran aproksimasi linear dari S-Box Dari aproksimasi linear di atas didapat: (4) dimana (5) ΣK adalah 0 atau 1, tergantung dari kunci pada tiaptiap putarannya. Dengan menggunakan Piling-Up Lemma, didapat probabilitas untuk ekspresi di atas adalah ½ + 23(3/4 – 1/2)(1/4-1/2)3 = 15/32 Ketika ΣK sudah diketahui, kita mengetahui bahwa (6)
harus mempunyai probabilitas sebesar 15/32 atau (115/32) = 17/32, tergantung dari nilai ΣK adalah 0 atau 1. 2. Mengekstrak bit-bit kunci dari cipherteks dan plainteks yang sudah diketahui sebelumnya, yaitu dengan mengetahui bit-bit subkunci terakhir. Ekspresi linear (6) mempengaruhi masukan dari S42 dan S44 di putaran terakhir. Untuk setiap sampel plainteks dan cipherteks, kita mencoba semua dari 256 nilai dari subkey parsial [K5,5...K5,8, K5,13...K5,16]. Untuk setiap nilai subkunci, kita akan menginkremen hitungan setiap persamaan (6) bernilai true, dimana kita menentukan nilai dari [U4,5...U4,8, U4,13...U4,16] dengan menjalankan data mundur melalui subkunci parsial target dan kotak-S S42 dan S44. Setelah menyimulasikan penyerangan dengan membangkitkan 10000 nilai plainteks/cipherteks yang diketahui, dan dari proses kriptanalisis sebelumnya, didapat nilai subkunci parsial [K5,5...K5,8] adalah [0010] dan [K5,13...K5,16] adalah [0100], dengan perhitungan simpangan sebagai berikut: (7) Nilai subkunci tadi didapat dengan membandingkan setiap nilai simpangan (bias) dengan simpangan yang sebenarnya, yaitu 1/32 (didapat dari ½ - 15/32). Dari hasil kriptanalisis, didapat tabel nilai bias sebagai berikut:
Tabel 1. Nilai simpangan pada masing-masing subkunci yang dihitung Nilai simpangan dari [2,4], yaitu 0.0336 sangat dekat dengan nilai simpangan sesungguhnya yaitu 1/32 atau 0.03125, oleh karena itu disimpulkan bahwa nilai subkunci parsial di atas adalah [2,4] Kemudian hal ini dilakukan untuk setiap putaran, sehingga akan didapat 26 bit subkunci, sedangkan untuk 30 bit sisanya, harus dilakukan exhaustive search.
2.3 Penerapan Differential Cryptanalysis pada Algoritma DES Penerapan Differential Cryptanalysis Dengan cipher yang sama dengan penerapan linear cryptanalysis, pertama-tama kita menganalisis komponen dari cipher dengan cara sebagai berikut: Anggap sebuah S-box dengan input X = [X1, X2, X3, X4] dan output Y = [Y1, Y2, Y3, Y4]. Semua pasangan perbedaan dari sebuah S-box, (∆X, ∆Y), dapat diketahui dan probabilitas dari ∆Y didapat dari ∆X dengan ∆X = X’ X’’. Setelah dihitung semua ∆X dan ∆Y, bisa didapat tabel distribusi perbedaan dan pasangan perbedaan dari S-box.
Anggap sebuah karakteristik diferensial melibatkan S12, S23, S32, S33. Kita menggunakan pasangan ini pada S-box:
Perbedaan input dalam cipher sama perbedaan input pada putaran pertama: Tabel 2. Pasangan Perbedaan pada S-box
dengan
(9) Maka, karakteristik diferensial pada S-box dapat dimodelkan sebagai berikut:
Tabel 3. Distribusi perbedaan Perhitungan di atas adalah perhitungan pada S-box yang belum diberi kunci. Pada S-box yang sudah diberi kunci, anggap semua masukan adalah W = [W1, W2, W3, W4]. Skema masukan-keluarannya adalah sebagai berikut:
Gambar 7. Skema masukan-keluaran pada S-box yang telah diberi kunci Cara mencari Wi adalah sebagai berikut: (8) Dapat disimpulkan, S-box yang berkunci mempunyai distribusi perbedaan yang sama dengan S-box yang tidak berkunci.
Gambar 8. Sampel karakteristik diferensial Pada ekstraksi kunci, hampir sama dengan penyerangan linear, namun di sini digunakan
probabilitas dari perbedaan yang muncul. Probabilitas tersebut dihitung dengan persamaan sebagai berikut: (10) Dengan 5000 didapat dari jumlah pembangkitan known ciphertext. Count akan bertambah jika perbedaan dari input sampai ke putaran terakhir sama dengan nilai yang diharapkan pada karakteristik diferensial. Pada S-box ini, didapat PD = 27/1024 atau kira-kira 0.0264, dan pada tabel berikut ini didapat [2,4] mempunyai nilai probabilitas 0.0244, atau mendekati nilai PD.
Untuk selanjutnya, dilakukan hal yang sama sampai semua S-box dieksplor. Untuk subkunci yang belum ditemukan, dilakukan cara exhaustive search.
3. KESIMPULAN Algoritma DES dapat diserang dengan cara-cara selain cara brute force, di antaranya adalah dengan cara Linear Cryptanalysis dan Differential Cryptanalysis. Jika dibandingkan antara kedua metode kriptanalisis tersebut, keduanya memiliki persamaan yaitu merupakan sebuah known-plaintext attack. Namun, keduanya memiliki pendekatan yang berbeda, dimana pada linear cryptanalysis menggunakan pendekatan linear, sedangkan pada differential cryptanalysis menggunakan pendekatan perbedaan antara input dan outputnya.
DAFTAR PUSTAKA [1] Bruce Schneier, “Applied Cryptography - Second Edition”. John Wiley & Sons, Inc, 1996 [2] Menezes, P. Van Oorschot, S. Vanstone, “Handbook of Applied Cryptography”. CRC Press, Inc, 1997 [3] Pascal Junod, “Linear Cryptanalysis of DES, Diploma Thesis”. Technische Hochschule Zurich. [4] Bruce Schneier, “A Self-Study Course in BlockCipher Cryptanalysis”. [5] Ralf Philipp Weinmann, “Algebraic Methods in Block Cipher Cryptanalysis”. Department of Computer Science, Technischen Universität Darmstadt [6] Howard M. Heys, “A Tutorial on Linear and Differential Cryptanalysis”. Electrical and Computer Engineering, Faculty of Engineering and Applied Science, Memorial University of Foundland. [7] “Basic Cryptanalisis”. FIELD MANUAL NO 3440-2, HEADQUARTERS DEPARTMENT OF THE ARMY. Washington, DC, 13 September 1990
Tabel 4. Hasil untuk serangan diferensial
