KRIPTANALISIS CIPHER BLOK BERDASARKAN PERMAINAN KAOTIK
DISERTASI Karya tulis sebagai salah satu syarat untuk memperoleh gelar Doktor dari Institut Teknologi Bandung
Oleh
BUDI SULISTYO NIM : 33204013 (Program Studi Teknik Elektro dan Informatika)
INSTITUT TEKNOLOGI BANDUNG 2009
KRIPTANALISIS CIPHER BLOK BERDASARKAN PERMAINAN KAOTIK Oleh Budi Sulistyo NIM: 33204013 (Program Studi Teknik Elektro dan Informatika) Institut Teknologi Bandung
Menyetujui Tim Pembimbing Tanggal
16 November 2009 Promotor
Prof. Dr. Ir. Carmadi Machbub Ko-Promotor 1
Ko-Promotor 2
Ir. Budi Rahardjo, M.Sc., Ph.D.
Dr. Ir. Dimitri Mahayana, M.Sc.
ii
ABSTRAK KRIPTANALISIS CIPHER BLOK BERDASARKAN PERMAINAN KAOTIK Oleh Budi Sulistyo NIM : 33204013 Disertasi ini mengusulkan penggunaan metode analisis berdasarkan permainan kaotik untuk analisis keacakan dan kriptanalisis cipher blok. Metode analisis ini dilakukan berdasarkan kerangka analisis sistem dinamik waktu diskrit. Dalam kerangka ini, cipher blok akan diperlakukan sebagai fungsi pemetaan dari sistem dinamik waktu diskrit yang dinyatakan dalam persamaan diferens. Analisis keacakan dilakukan dengan cara menganalisis trayektori sistem dinamik tersebut. Dengan menerapkan metode dinamika simbolik, trayektori tersebut dikonversi menjadi deret acak yang selanjutnya dipergunakan sebagai masukan skema permainan kaotik. Metode ini akan menghasilkan himpunan titik-titik koordinat X dalam bidang tertentu. Konsep ukuran selanjutnya digunakan untuk menghitung distribusi titik-titik tersebut. Analisis keacakan merupakan langkah awal kriptanalisis. Analisis keacakan ini digunakan untuk membedakan dua cipher blok dengan jumlah ronde yang berbeda. Jika metode analisis berdasarkan permainan kaotik dapat berfungsi sebagai pembeda, maka metode tersebut berpeluang untuk dikembangkan menjadi metode kriptanalisis. Skema permainan kaotik merupakan metode yang pada mulanya dikembangkan untuk membangkitkan gambar fraktal. Skema permainan kaotik diturunkan dari sistem iterasi fungsi tertentu yang berkaitan dengan obyek fraktal tertentu. Agar dapat membangkitkan gambar fraktal, masukan skema permainan kaotik harus merupakan deret yang menyerupai deret acak ideal. Karakteristik terpenting inilah yang digunakan dalam analisis keacakan. Diusulkan skema permainan kaotik baru yang dapat digunakan untuk menganalisis deret acak s = l0 , l1 , l2 . . . dengan li ∈ {0, 1}m . Diusulkan juga penggunaan konsep ukuran, yang lazim digunakan untuk mengukur gambar fraktal yang dihasilkan oleh metode permainan kaotik, untuk menganalisis deret acak yang dihasilkan cipher
iii
blok. Berikutnya, metode permainan kaotik dan konsep ukuran ini dikembangkan menjadi metode kriptanalisis terhadap cipher blok. Untuk eksperimen dalam disertasi ini, digunakan cipher blok berstruktur SPN, yang biasa digunakan dalam studi kriptanalisis linear dan diferensial, sebagai obyek kriptanalisis. Dilakukan dua jenis eksperimen, yaitu (1) analisis keacakan terhadap cipher blok dan (2) kriptanalisis terhadap cipher blok. Untuk melakukan dua hal tersebut, dibutuhkan sejumlah data yang dihasilkan dari iterasi cipher blok dengan menggunakan beberapa nilai awal yang dipilih secara acak. Eksperimen analisis keacakan berhasil membedakan dua cipher blok yang masing-masing memiliki jumlah ronde yang berbeda. Hasil ini merupakan indikasi bahwa metode ini memiliki peluang untuk dikembangkan menjadi metode kriptanalisis. Berikutnya, eksperimen kriptanalisis berhasil menemukan seluruh subkunci terakhir dari cipher blok tersebut. Kriptanalisis dengan metode permainan kaotik tidak memerlukan analisis terhadap kotak subtitusi. Hal ini yang membedakannya dengan kriptanalisis linear dan diferensial. Dalam langkah awal kriptanalisis untuk menentukan bit-bit yang akan dianalisis dalam serangan nyata, metode permainan kaotik menghasilkan pilihan bit yang berbeda dengan metode kriptanalisis linear dan diferensial. Hal ini menunjukkan bahwa metode ini mengeksploitasi aspek yang berbeda dari yang dieksploitasi oleh metode kriptanalisis linear dan diferensial. Perbandingan kinerja antara metode permainan kaotik dan kriptanalisis linear juga telah dilakukan. Aspek pertama adalah kompleksitas komputasi. Metode kriptanalisis berbasis permainan kaotik harus menjalankan algoritma permainan kaotik untuk membangkitkan himpunan titik-titik dan memerlukan algoritma lain untuk menghitung distribusi titik-titik tersebut. Sedangkan, algoritma kriptanalisis linear hanya memerlukan implementasi penghitung atau kounter dan fungsi EX-OR. Aspek kedua yang dibandingkan adalah kompleksitas data. Berdasarkan eksperimen yang dilakukan dengan cipher blok, untuk bagian subkunci ronde terakhir tertentu, metode kriptanalisis berdasarkan permainan kaotik memerlukan data yang lebih sedikit dibandingkan dengan metode kriptanalisis linear. Meskipun demikian, metode kriptanalisis berdasarkan permainan kaotik menghasilkan pilihan bit-bit yang berbeda dari metode kriptanalisis linear dan diferensial. Hal ini menunjukkan bahwa kriptanalisis berdasarkan permainan kaotik mengeksploitasi jenis kerawanan yang berbeda sehingga dapat diajukan sebagai kandidat baru metode kriptanalisis.
iv
Kata kunci: Kriptografi, kriptanalisis, analisis keacakan, deret acak, cipher blok, SPN, permainan kaotik, fraktal, dinamika simbolik, ukuran
v
ABSTRACT CHAOS GAME BASED BLOCK CIPHER CRYPTANALYSIS By Budi Sulistyo NIM : 33204013 This dissertation proposes a chaos game based analysis method for randomness analysis and cryptanalysis of block cipher. This analysis method is performed based on discrete time dynamical system analysis framework. In this framework, block cipher is treated as a mapping function of a discrete time dynamical system expressed in a difference equation. The randomness analysis is performed by analyzing the trajectory of the dynamical system. By using symbolic dynamic method, the trajectory is converted to a random sequence which is used further as an input to a chaos game scheme. This method will produce a set of points denoted by X in a plane. Next, the measure concept is used to calculate distribution of those points. Randomness analysis is the first step toward cryptanalysis. The randomness analysis is used to distinguish two block cipher with different number of rounds from each other. If this chaos game analysis method could perform as a distinguisher, then potentially with further improvement it could be used as a cryptanalysis method. The chaos game method is a scheme originally developed for generating fractal images. A chaos game scheme is derived from a certain IFS associated to a certain fractal object. To generate a fractal image successfully, the scheme must be driven by a sequence which is closed to a true random sequence. This is the most important characteristic of the scheme which makes it possible to use for randomness analysis. A chaos game scheme which can be used to analyze a random sequence s = l0 , l1 , l2 . . . with li ∈ {0, 1}m is proposed. This dissertation proposes a measure concept, originally used to measure a fractal images generated by an associated chaos game algorithm, to analyze a random sequence produced by a block cipher. Both the chaos game scheme and the measure concept are developed further to build a block cipher cryptanalysis method.
vi
The cryptanalysis work uses an SPN (substitution and permutation network) block cipher, which is commonly used in linear and differential cryptanalysis study, as a cryptanalysis object. Two kind experiments has been performed, they are (1) block cipher randomness analysis and (2) block cipher cryptanalysis. Those experiments need a set of data generated by iterating the block cipher with several initial condition which are randomly chosen. Randomness analysis experiment has distinguished successfully two block ciphers with different number of round from each other. By considering that result, we can expect that the method can be used further as a cryptanalysis method. Next, a cryptanalysis experiment has been done and has found all last round subkeys of the block cipher successfully. Chaos game based cryptanalysis method does not need an analysis of substitution box. This fact differs the method from linear and differential cryptanalysis. In the earlier stage for determining which bit can be used in further analysis, the chaos game based cryptanalysis method deduces chosen bits which are different from the ones deduced by linear and differential cryptanalysis. Performance comparison between chaos game based cryptanalysis and linear cryptanalysis has been done. The first aspect is computational complexity. The chaos game based cryptanalysis method must execute a chaos game scheme to generate a set of points and a process used to calculate the distribution of those points. The linear cryptanalysis only needs to implement a set of counters and an exclusiveor function. The second aspect is data complexity. Based on the experiment, for the same part of last round subkeys, the chaos game based method needs a slightly smaller amount of data than linear cryptanalysis method. Despite of those, the chaos game based cryptanalysis method uses different chosen bits from the ones used by linear and differential cryptanalysis. This fact indicates that, the chaos game based cryptanalysis method exploits different kind of block cipher vulnerabilities and thus it is promising to be a new candidate of cryptanalysis method. Keywords: Cryptography, cryptanalysis, randomness analysis, random sequence, block cipher, SPN, chaos game, fractal, symbolic dynamic, measure.
vii
PEDOMAN PENGGUNAAN DISERTASI Disertasi Doktor yang tidak dipublikasikan terdaftar dan tersedia di Perpustakaan Institut Teknologi Bandung, dan terbuka untuk umum dengan ketentuan bahwa hak cipta ada pada pengarang dengan mengikuti aturan HaKI yang berlaku di Institut Teknologi Bandung. Referensi kepustakaan diperkenankan dicatat, tetapi pengutipan atau peringkasan hanya dapat dilakukan seizin pengarang dan harus disertai dengan kebiasaan ilmiah untuk menyebutkan sumbernya. Memperbanyak atau menerbitkan sebagian atau seluruh tesis haruslah seizin Direktur Program Pascasarjana Institut Teknologi Bandung.
viii
Untuk Dwi, Ala dan Miqdada
ix
KATA PENGANTAR Puji syukur penulis panjatkan ke hadirat Allah SWT, yang dengan rahmat dan karunia-Nya penulis dapat menyelesaikan Disertasi ini. Shalawat serta salam senantiasa tercurah kepada Rasulullah SAW beserta keluarganya yang suci. Dalam penyusunan Disertasi ini, penulis mendapat bantuan dan dukungan dari banyak pihak. Untuk itu, penulis ingin memberikan terima kasih kepada: 1. Prof. Dr. Ir. Carmadi Machbub, selaku Promotor, untuk semua bimbingan dan dukungannya dan khususnya untuk kesabaran beliau dalam membimbing penulis selama penulisan Disertasi ini; 2. Ir. Budi Rahardjo, M.Sc., Ph.D., dan Dr.Ir. Dimitri Mahayana, M.Sc., selaku Ko-Promotor I dan II, untuk semua bimbingan dan dukungan yang diberikan kepada penulis; 3. Ir. Hendrawan, M.Sc., Ph.D., untuk semua bimbingan dan arahan bagi penulis terutama di akhir masa studi penulis; 4. Prof. Dr. Ir. Suhono H. Supangkat dan Dr. Sarwono Sutikno selaku penelaah draft Disertasi dan Dr. Ahmad Muchlis selaku penelaah draft disertasi serta penguji dalam Sidang Tertutup untuk seluruh masukan yang membantu penulis dalam menyempurnakan Disertasi ini; 5. Prof. Dr. Ir. Kuspriyanto, Dr. dr. Oerip S. Santoso, M. Sc. dan Dr. Ir. Ari Musriami Barmawi selaku penguji dalam Sidang Tertutup untuk semua kritik dan masukan demi perbaikan Buku Disertasi ini; 6. Ibu Lia yang telah mendukung dan membantu semua persyaratan administrasi; 7. Istriku Dwi untuk doa, dukungan dan segala pengorbanan yang tulus selama masa studi penulis; 8. Putriku Alfia dan Miqdada yang selalu memberi semangat dan inspirasi kepada penulis; 9. Ibu dan kakak-kakakku yang telah berdoa, mendukung dan memberi semangat; 10. Keluarga Bapak Sunarno yang telah mendoakan dan mendukung penulis ;
x
11. Semua teman-teman di kantor Sharing Vision yang telah mendukung dan merelakan penulis untuk cuti kerja di masa akhir studi dan khususnya Ali Akbar yang memberikan template Latex kepada penulis; 12. Serta semua teman-teman serta berbagai pihak lainnya yang membantu dalam pengerjaan Disertasi ini, yang tidak dapat penulis sebutkan satu persatu. Semoga Allah SWT membalas budi baik semua pihak tersebut dengan kebaikan dan pahala yang berlipat ganda. Akhir kata, penulis menyadari bahwa Disertasi ini bukanlah tanpa kelemahan, untuk itu kritik dan saran sangat diharapkan.
Bandung, Oktober 2009
Penulis
xi
DAFTAR ISI Daftar Isi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
xii
Daftar Lampiran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
xv
Daftar Gambar dan Ilustrasi . . . . . . . . . . . . . . . . . . . . . . .
xvi
Daftar Tabel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
xxi
Bab I I.1 I.2 I.3 I.4 I.5 I.6 I.7
. . . . . . . .
I–1 I–1 I–4 I–7 I–7 I–8 I–9 I–9
Bab II Penggunaan Dinamika Kaotik dalam Algoritma Enkripsi . . II.1 Pengenalan Kriptografi dan Algoritma Enkripsi . . . . . . . . . II.1.1 Definisi Algoritma Enkripsi . . . . . . . . . . . . . . . II.1.2 Keamanan Algoritma Enkripsi . . . . . . . . . . . . . . II.1.3 Definisi Cipher Blok . . . . . . . . . . . . . . . . . . . II.2 Penggunaan Dinamika Kaotik untuk Membangun Algoritma Enkripsi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . II.2.1 Klasifikasi Dinamika Kaotik . . . . . . . . . . . . . . . II.2.2 Pendekatan Analog dalam Enkripsi Berbasis Dinamika Kaotik . . . . . . . . . . . . . . . . . . . . . . . . . . . II.2.3 Pengembangan Cipher Kaotik Dijital (Digital Chaotic Cipher atau DCC) . . . . . . . . . . . . . . . . . . . . . II.2.4 Permasalahan Mendasar Cipher Kaotik Dijital . . . . . . II.3 Pengembangan Teori Dinamika Kaotik Diskrit . . . . . . . . . .
II–1 II–1 II–3 II–4 II–9 II–15 II–15
Bab III Dinamika Kaotik dan Permainan Kaotik III.1 Karakteristik Dinamika Kaotik . . . . . . . III.1.1 Pemetaan Satu Dimensi . . . . . . . III.1.2 Stabilitas Titik Tetap . . . . . . . .
III–1 III–1 III–2 III–2
Pendahuluan . . . . . . . . . Latar Belakang . . . . . . . . Identifikasi Masalah Penelitian Tujuan Penelitian . . . . . . . Ruang Lingkup Penelitian . . . Metodologi Penelitian . . . . . Hipotesis . . . . . . . . . . . . Sistematika Pembahasan . . .
. . . . . . . .
xii
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . .
II–17 II–18 II–19 II–20
III.1.3 Karakteristik Titik Periodik . . . . . . . . . . . . . . . . III.1.4 Sensitifitas terhadap Kondisi Mula . . . . . . . . . . . . III.1.5 Analisis dengan Kode Simbol . . . . . . . . . . . . . . III.1.6 Definisi Dinamika Kaotik . . . . . . . . . . . . . . . . . III.2 Pengenalan Permainan Kaotik . . . . . . . . . . . . . . . . . . III.2.1 Pengenalan Fraktal dan Sistem Fungsi Iteratif . . . . . . III.2.2 Membangkitkan Fraktal dengan Algoritma Deterministik III.2.3 Membangkitkan Fraktal dengan Permainan Kaotik . . . III.2.4 Penggunaan Ukuran dalam Fraktal . . . . . . . . . . . .
III–3 III–5 III–6 III–8 III–10 III–10 III–13 III–14 III–15
Bab IV Usulan Skema Permainan Kaotik untuk Analisis Cipher Blok IV.1 Definisi Deret Acak Ideal . . . . . . . . . . . . . . . . . . . . . IV.2 Kerangka Sistem Dinamik untuk Analisis Keacakan . . . . . . . IV.2.1 Penerapan Kerangka Analisis Sistem Dinamik . . . . . . IV.2.2 Analisis Simbolik terhadap Fungsi Kuadratik . . . . . . IV.2.3 Analisis Simbolik terhadap Cipher Blok . . . . . . . . . IV.2.4 Perbandingan Keacakan Cipher Blok untuk Jumlah Ronde yang Berbeda . . . . . . . . . . . . . . . . . . . IV.3 Konstruksi Skema Permainan Kaotik . . . . . . . . . . . . . . . IV.3.1 Skema Permainan Kaotik untuk Analisis Keacakan . . . IV.3.2 Konsep ukuran pada XN . . . . . . . . . . . . . . . . . IV.4 Prosedur Analisis Cipher Blok Berdasarkan Permainan Kaotik . IV.5 Rangkuman . . . . . . . . . . . . . . . . . . . . . . . . . . . .
IV–1 IV–1 IV–4 IV–7 IV–11 IV–15
Bab V Analisis Keacakan Cipher Blok dengan Metode Kaotik . . . . . . . . . . . . . . . . . . . . . . . . . . . V.1 Skenario Analisis Keacakan . . . . . . . . . . . . . V.1.1 Skenario Pengambilan Data . . . . . . . . V.1.2 Skenario Analisis Data . . . . . . . . . . . V.2 Menetapkan Parameter Skema Permainan Kaotik . V.3 Membangkitkan Deret Acak . . . . . . . . . . . . V.4 Analisis Keacakan Cipher Blok . . . . . . . . . . . V.5 Rangkuman . . . . . . . . . . . . . . . . . . . . .
IV–16 IV–17 IV–20 IV–21 IV–24 IV–24
Permainan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
V–1 V–2 V–2 V–3 V–5 V–6 V–6 V–10
Bab VI Kriptanalisis Cipher Blok dengan Metode Permainan Kaotik VI.1 Batasan Masalah . . . . . . . . . . . . . . . . . . . . . . . . . VI.2 Skenario Kriptanalisis Menggunakan Permainan Kaotik . . . . . VI.2.1 Metode Umum Kriptanalisis . . . . . . . . . . . . . . .
VI–1 VI–2 VI–3 VI–3
xiii
VI.3 VI.4
VI.5 VI.6 VI.7
VI.2.2 Skenario Pengambilan Data . . . . . . . . . . . . . . VI.2.3 Skenario Pengaturan Data . . . . . . . . . . . . . . . VI.2.4 Skenario Analisis Data . . . . . . . . . . . . . . . . . Penetapan Parameter Skema Permainan Kaotik . . . . . . . . Kriptanalisis Cipher Blok Berstruktur SPN . . . . . . . . . . . VI.4.1 Pemilihan Bit-Bit untuk Analisis . . . . . . . . . . . . VI.4.2 Mengidentifikasi Subkunci Rahasia . . . . . . . . . . Perbandingan Kompleksitas Data terhadap Kriptanalisis Linear Permasalahan Keacakan dan Kunci Lemah dalam Eksperimen Rangkuman . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . .
VI–4 VI–6 VI–7 VI–9 VI–10 VI–10 VI–20 VI–23 VI–25 VI–25
Bab VII Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . . . . . . VII–1 Publikasi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . PUB–1 Daftar Pustaka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . PUST–1
xiv
DAFTAR LAMPIRAN Lampiran A Cobweb Plot . . . . . . . . . . . . . . . . . . . . . . . . .
A–1
Lampiran B
Contoh Cipher Blok SPN . . . . . . . . . . . . . . . . . .
B–1
Lampiran C
Pilihan Bit-Bit dalam Kriptanalisis Linear dan Diferensial .
C–1
Lampiran D Lingkungan Eksperimen . . . . . . . . . . . . . . . . . . .
D–1
Baris Program . . . . . . . . . . . . . . . . . . . . . . . .
E–1
Lampiran E
xv
DAFTAR GAMBAR DAN ILUSTRASI Gambar I.1 Gambar I.2
Gambar II.1 Gambar II.2 Gambar II.3
Gambar II.4 Gambar II.5 Gambar II.6 Gambar II.7
Ilustrasi analisis keacakan untuk membedakan cipher blok 1 dari cipher blok 2 . . . . . . . . . . . . . . . . Ilustrasi kriptanalisis untuk memilih subkunci yang benar dari sejumlah K alternatif subkunci . . . . . . . . Jenis-jenis primitif (Menezes dkk., 1996) . . . . . . . . Ilustrasi fungsi algoritma enkripsi . . . . . . . . . . . . Ilustrasi penentuan serangan paling efisien diantara n serangan yang diketahui terhadap A dan m serangan yang diketahui terhadap B . . . . . . . . . . . . . . . Cipher blok teriterasi dengan r jumlah ronde . . . . . . Subtitution and permutation network . . . . . . . . . . Dinamika kaotik waktu kontinyu, x dan t didefinisikan dalam himpunan bilangan real . . . . . . . . . . . . . Dinamika kaotik waktu diskrit, x didefinisikan dalam himpunan bilangan real dan n dalam bilangan integer .
Gambar III.1 Contoh cobweb plot untuk fungsi kuadratik (logistik) g (x) = 2x (1 − x) . . . . . . . . . . . . . . . . . . . Gambar III.2 Orbit periodik . . . . . . . . . . . . . . . . . . . . . . Gambar III.3 Pemetaan f (x) = 3x mod 1 . . . . . . . . . . . . . . Gambar III.4 Pemetaan G (x) = 4x (1 − x) dengan contoh subinterval yang diberi nama sesuai dengan kode simbol yang dihasilkan oleh titik mula yang berada dalam interval tersebut. . . . . . . . . . . . . . . . . . . . . . . . . . Gambar III.5 Perilaku kaotik dari fungsi pemetaan G (x) = 4x (1 − x). Dua titik awal yang sangat berdekatan menghasilkan orbit yang semakin menjauh seiring bertambahnya iterasi (Kathleen T. Alligood, 2000). . . Gambar III.6 Fraktal pentagram (http://en.wikipedia.org/wiki/Fractal) Gambar III.7 Ilustrasi IFS . . . . . . . . . . . . . . . . . . . . . . . Gambar III.8 Atraktor (segitiga Sierpinski) yang dihasilkan oleh algoritma deterministik. Dari kiri atas ke kanan bawah berturut-turut adalah nilai awal dan iterasi ke-1, 2, . . . , 8 Gambar III.9 Permainan kaotik dengan tiga transformasi . . . . . . .
xvi
I–6 I–6 II–3 II–4
II–8 II–12 II–14 II–16 II–16
III–4 III–4 III–5
III–7
III–9 III–11 III–11
III–13 III–14
Gambar III.10 Atraktor (fraktal Sierpinski triangle) yang dihasilkan oleh algoritma permainan kaotik . . . . . . . . . . . . III–15 Analisis grafik orbit x untuk µ = 3 . . . . . . . . . . . Analisis grafik orbit x untuk µ = 4 . . . . . . . . . . . Grafik Ek (p) terhadap p . . . . . . . . . . . . . . . . . Orbit pdec dan grafik Ek (p) terhadap pdec . . . . . . . . CGR kombinasi simbol ATGCGAGTGT (Sumber: Digital Search Trees and Chaos Game Representation, presentasi dari Peggy Cenac) . . . . . . . . . . . . . . . . . . Gambar IV.6 Representasi permainan kaotik (CGR) dari rantai genetik bakteri E. coli K12. (http://insilico.ehu.es/oligoweb/info/CGR.php?ZCGR) Gambar IV.7 Ilustrasi skema permainan kaotik untuk menganalisis n = 3-bit data dengan menggunakan m = 23 simbol . . Gambar IV.8 Prosedur analisis keacakan dan kriptanalisis . . . . . .
IV–8 IV–9 IV–10 IV–11
Ilustrasi pemetaaan w10 dalam IFS 16 simbol . . . . . 4-bit msb dari SPN . . . . . . . . . . . . . . . . . . . Keluaran algoritma permainan kaotik untuk semua sampel dengan Nr = 1 dengan urutan bit [1, 2, 3, 4] . . . . Keluaran algoritma permainan kaotik untuk semua sampel dengan Nr = 2 dengan urutan bit [1, 2, 3, 4] . . . . Keluaran algoritma permainan kaotik untuk semua sampel dengan Nr = 3 dengan urutan bit [1, 2, 3, 4] . . . . Keluaran algoritma permainan kaotik untuk semua sampel dengan Nr = 4 dengan urutan bit [1, 2, 3, 4] . . . . Hasil analisis one-way-anova untuk data statistik dalam Tabel V.1. Kelompok sampel yang sebelah kiri dihasilkan oleh Nr = 4, yang disebelah kanan dihasilkan oleh Nr = 3 . . . . . . . . . . . . . . . . . . . . . . . Keluaran algoritma permainan kaotik untuk semua sampel dengan Nr = 3 dengan urutan bit [13, 14, 15, 16] . . Keluaran algoritma permainan kaotik untuk semua sampel dengan Nr = 4 dengan urutan bit [13, 14, 15, 16] . .
V–6 V–7
Gambar IV.1 Gambar IV.2 Gambar IV.3 Gambar IV.4 Gambar IV.5
Gambar V.1 Gambar V.2 Gambar V.3 Gambar V.4 Gambar V.5 Gambar V.6 Gambar V.7
Gambar V.8 Gambar V.9
xvii
IV–19
IV–19 IV–21 IV–25
V–8 V–8 V–8 V–9
V–10 V–11 V–11
Gambar V.10 Hasil analisis one-way-anova untuk data statistik dalam Tabel V.2. Kelompok sampel yang sebelah atas dihasilkan oleh Nr = 4, yang bawah dihasilkan oleh Nr = 3 . . . . . . . . . . . . . . . . . . . . . . . . . . Gambar VI.1 Serangan akan dilakukan terhadap subkunci ronde terakhir, ks (5), yang mengacak keluaran ronde keempat cipher . . . . . . . . . . . . . . . . . . . . . . . . . . Gambar VI.2 Ilustrasi pengambilan data untuk keperluan kriptanalisis cipher blok. Matrik yang menghimpun plaintextplaintext hasil iterasi cipher blok dengan kunci k adalah datak . Matrik yang menghimpun hasil invers-rondeterakhir terhadap sebagian bit dari datak dengan menggunakan bagian dari subkunci terakhir adalah invdataUkx1 h i
V–12
VI–2
VI–5
U |V
Gambar VI.3 RMS bias ternormalisasi dari X rkx1 1 untuk nilai kx di sekitar nilai (ksU1 (5) = 11010011). Sampel yang ditandai dengan kotak merupakan sampel dari kunci yang benar . . . . . . . . . . . . . . . . . . . . . . . . . . Gambar VI.4 Hasil analisis statistik antara sampel-sampel h perbedaan i U1 |V1 dalam X rkx dengan mengambil nilai kunci kx di U1 sekitar (ks (5) = 11010011 . . . . . . . . . . . . . . Gambar VI.5 Hasil analisis statistik antara sampel-sampel h perbedaan i U1 |V2 dalam X rkx dengan mengambil nilai kunci kx di U1 sekitar (ks (5) = 11010011 . . . . . . . . . . . . . . Gambar VI.6 Hasil analisis statistik antara sampel-sampel h perbedaan i U1 |V4 dalam X rkx dengan mengambil nilai kunci kx di sekitar (ksU1 (5) = 11010011 . .h . . . i. . . . . . . . . U |V Gambar VI.7 RMS bias ternormalisasi dari X rkx1 3 untuk nilai kx di sekitar nilai (ksU1 (5) = 11010011). Sampel yang ditandai dengan kotak merupakan sampel dari kunci yang benar. . . . . . . . . . . . . . . . . . . . . . . . . . . Gambar VI.8 Hasil analisis statistik antara sampel-sampel h perbedaan i U1 |V3 dalam X rkx dengan mengambil nilai kunci kx di U1 sekitar (ks (5) = 11010011 . . . . . . . . . . . . . .
xviii
VI–12
VI–12
VI–13
VI–13
VI–14
VI–14
Gambar VI.9 Lingkaran menunjukkan bit-bit yang dipilih, Vattack 1 = [9, 10, 11, 12] dan Uattack 1 = [1, 2, 3, 9, 10, 11]. Segi empat menunjukkan bagian dari subkunci yang akan diidentifikasi menggunakan bit-bit tersebut, yaitu iksU1 (5). h U |V Gambar VI.10 RMS bias ternormalisasi dari X rkxattack 1 attack 1 untuk nilai kx di sekitar nilai (ksU1 (5) = 11010011). Sampel yang ditandai dengan kotak merupakan sampel dari kunci yang benar. . . . . . . . . . . . . . . . . . . . . Gambar VI.11 Hasil analisis perbedaan statistik antara sampel-sampel U |V dalam Xrkxattack 1 attack 1 dengan mengambil nilai kunci kx di sekitar ksU1 (5) = 11010011 . . . . . . . . . . . . . . Gambar VI.12 Hasil analisis perbedaan statistik antara sampel-sampel U |V dalam Xrkx2 1 dengan mengambil nilai kunci kx di sekitar ksU2 (5) = 11100100 . . . . . . . . . . . . . . . . . Gambar VI.13 Hasil analisis perbedaan statistik antara sampel-sampel U |V dalam Xrkx2 2 dengan mengambil nilai kunci kx di sekitar ksU2 (5) = 11100100 . . . . . . . . . . . . . . . . . Gambar VI.14 Hasil analisis perbedaan statistik antara sampel-sampel U |V dalam Xrkx2 3 dengan mengambil nilai kunci kx di sekitar ksU2 (5) = 11100100 . . . . . . . . . . . . . . . . . Gambar VI.15 Hasil analisis perbedaan statistik antara sampel-sampel U |V dalam Xrkx2 4 dengan mengambil nilai kunci kx di sekitar ksU2 (5) = 11100100 . . . . . . . . . . . . . . . . . Gambar VI.16 Lingkaran menunjukkan bit-bit yang dipilih, Vattack 2 = [5, 6, 7, 8] dan Uattack 2 = [6, 8, 14, 16]. Segi empat menunjukkan bagian dari subkunci yang akan diidentiU2 fikasi menggunakan bit-bit tersebut, h yaitu ks (5). i . . . Uattack 2 |Vattack 2 Gambar VI.17 RMS bias ternormalisasi dari X rkx untuk U2 nilai kx di sekitar nilai (ks (5) = 11010011). Sampel yang ditandai dengan kotak merupakan sampel dari kunci yang benar. . . . . . . . . . . . . . . . . . . . . Gambar VI.18 Hasil analisis h perbedaan i statistik antara sampel-sampel Uattack 2 |Vattack 2 dalam X rkx dengan mengambil nilai kunci U2 kx di sekitar ks (5) = 11100100 . . . . . . . . . . . . Gambar VI.19 Hasil identifikasi ks (5) urutan bit [1, 2, 3, 4, 9, 10, 11, 12] = U1 . Kunci yang dihasilkan adalah 10100110 . . . . . . . . . . . . . . . . . . . . .
xix
VI–16
VI–17
VI–17
VI–18
VI–18
VI–19
VI–19
VI–20
VI–21
VI–21
VI–22
Gambar VI.20 Hasil identifikasi ks (5) urutan bit [5, 6, 7, 8, 13, 14, 15, 16] = U2 . Kunci yang dihasilkan adalah 10011010 . . . . . . . . . h. . . . . . . i. . . . . VI–23 U |V Gambar VI.21 RMS bias ternormalisasi dari X rkxattack 2 attack 2 untuk nilai kx di sekitar nilai (ksU2 (5) = 10011010). Sampel yang ditandai dengan kotak merupakan sampel dari kunci yang benar. . . . . . . . . . . . . . . . . . . . . VI–24 Gambar VI.22 Hasil identifikasi ks (5) dengan urutan bit [5, 6, 7, 8, 13, 14, 15, 16] = U2 dan dengan 7503 data . . . . . . . . . . . . . . . . . . . . . . . . . . . VI–24 Gambar A.1
Contoh cobweb plot untuk f = 2x . . . . . . . . . . .
A–1
Gambar B.1
Cipher blok jaringan subtitusi dan permutasi (SPN) dasar . . . . . . . . . . . . . . . . . . . . . . . . . .
B–2
Gambar C.1 Gambar C.2
Aproksimasi linear dan pilihan bit-bit yang dihasilkan . Karakteristik diferensial dan pilihan bit-bit yang dihasilkan . . . . . . . . . . . . . . . . . . . . . . . . .
xx
C–2 C–3
DAFTAR TABEL Tabel III.1 Pasangan orbit yang dihasilkan oleh pemetaan f (x) = 3x mod 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . Pengujian keacakan satu simbol untuk Q3 . . . . . . . . . Pengujian keacakan satu suku untuk Q4 dengan m = 2 . . Pengujian keacakan dua-suku untuk Q4 dengan m = 2 . . Pegujian keacakan tiga-suku untuk Q4 dengan m = 2 . . Tabel pengujian satu-suku untuk sQ4 dengan m = 3 . . . Tabel pengujian dua-suku untuk sQ4 dengan m = 3 . . . Pengujian keacakan tiga simbol untuk Ek dengan jumlah ronde Nr = 4 . . . . . . . . . . . . . . . . . . . . . . . . Tabel IV.8 Pengujian keacakan tiga suku untuk Ek dengan jumlah ronde Nr = 1 . . . . . . . . . . . . . . . . . . . . . . . . Tabel IV.9 Pengujian keacakan tiga suku untuk Ek dengan jumlah ronde Nr = 2 . . . . . . . . . . . . . . . . . . . . . . . . Tabel IV.10 Pengujian keacakan tiga suku untuk Ek dengan jumlah ronde Nr = 3 . . . . . . . . . . . . . . . . . . . . . . . .
Tabel IV.1 Tabel IV.2 Tabel IV.3 Tabel IV.4 Tabel IV.5 Tabel IV.6 Tabel IV.7
Tabel V.1
Tabel V.2
Tabel yang menampilkan RMS (biasnormal ) dengan Bi=1,2,...,400 untuk beberapa Nr . Kelompok bit yang dianalisis adalah [1, 2, 3, 4] . . . . . . . . . . . . . . . . . Tabel yang menampilkan RMS (biasnormal ) dengan Bi=1,2,...,400 untuk beberapa Nr . Kelompok bit yang dianalisis adalah [13, 14, 15, 16] . . . . . . . . . . . . . .
III–6 IV–12 IV–13 IV–13 IV–13 IV–14 IV–14 IV–16 IV–17 IV–17 IV–17
V–9
V–11
Tabel VI.1 Perbandingan kriptanalisis berdasarkan permainan kaotik dengan kriptanalisis linear . . . . . . . . . . . . . . . . . VI–27 Tabel VII.1 Perbandingan kriptanalisis berdasarkan permainan kaotik dengan kriptanalisis linear . . . . . . . . . . . . . . . . . VII–2 Tabel B.1 Tabel B.2
Representasi S-Box dalam heksadesimal . . . . . . . . . Tabel permutasi . . . . . . . . . . . . . . . . . . . . . .
xxi
B–1 B–3
KRIPTANALISIS CIPHER BLOK BERDASARKAN PERMAINAN KAOTIK
DISERTASI Karya tulis sebagai salah satu syarat untuk memperoleh gelar Doktor dari Institut Teknologi Bandung
Oleh
BUDI SULISTYO NIM : 33204013 (Program Studi Teknik Elektro dan Informatika)
INSTITUT TEKNOLOGI BANDUNG 2009 1
BAB I PENDAHULUAN I.1
Latar Belakang
Algoritma enkripsi atau algoritma cipher yang merupakan bagian dari sistem kriptografi, menjadi salah satu elemen fundamental dalam keamanan sistem informasi dijital. Algoritma enkripsi ini digunakan untuk mengacak atau menyandikan data sehingga data tidak dapat dibaca atau dimengerti oleh pihak lain yang tidak memiliki otoritas. Proses pengacakan atau penyandian ini disebut sebagai enkripsi. Data masukan untuk proses enkripsi disebut sebagai teks-plain sedangkan keluarannya disebut sebagai teks-cipher. Proses untuk mendapatkan teks-plain dari teks-cipher kembali disebut sebagai dekripsi. Dinamika kaotik sering digunakan untuk membangun algoritma enkripsi karena dua karakteristik terpenting dari dinamika kaotik, yaitu sifat percampuran (mixing property) dan sensitifitas terhadap kondisi mula diduga memiliki kaitan erat dengan dua karakteristik utama dari algoritma enkripsi yaitu konfusi dan difusi. Berikut adalah deskripsi umum dari beberapa karakteristik yang disebutkan di atas: Sifat percampuran Jika sebuah dinamika kaotik yang dihasilkan oleh suatu pemetaan kaotik memiliki sifat percampuran, maka himpunan seluruh kondisi awal yang berada dalam suatu selang tertentu yang kontinyu dalam domain pemetaan kaotik tersebut akan dipetakan ke seluruh ruang kodomain dari dari dinamika kaotik tersebut. Sensitifitas terhadap kondisi mula Iterasi terhadap pemetaan kaotik dengan menggunakan dua kondisi mula yang berdekatan akan menghasilkan keluaran yang berbeda jauh atau dengan kata lain perbedaan kecil antara dua kondisi mula tidak mengimplikasikan perbedaan yang kecil antara dua kondisi akhir yang dihasilkan. Konfusi Algoritma enkripsi modern menerapkan prinsip ini untuk menyembunyikan hubungan antara teks-plain dan teks-cipher. Prinsip konfusi mengharuskan hubungan ini harus cukup kompleks sehingga penyerang sangat sulit menemukan sifat-sifat teks-plain (misalnya sifat statistik) berdasarkan analisis terhadap teks-cipher.
I–2
Difusi Penerapan prinsip ini pada algoritma enkripsi menyebabkan perubahan sejumlah kecil bit dari teks-plain akan menghasilkan perubahan besar pada bit-bit teks-cipher sehingga penyerang tidak dapat mengidentifikasi atau melokalisasi efek perubahan bit teks-plain terhadap teks-cipher. Algoritma enkripsi dan dinamika kaotik masing-masing merupakan bidang penelitian yang pada awalnya terpisah satu dengan yang lain, yang pertama lebih banyak dikaji dalam bidang penelitian teori informasi maupun keamanan sistem informasi sedangkan yang terakhir banyak dikaji dalam bidang sistem dinamik. Paper pertama yang menghubungkan sistem dinamik dengan algoritma enkripsi dipublikasikan oleh Wolfram (1986) yang menggunakan cellular automata untuk membangun cipher. Penggunaan sistem kaotik untuk membangun cipher pertama kali dilakukan oleh Matthews (1984). Dalam rentang waktu tahun 1989-1993, cukup banyak paper yang membahas penggunaan dinamika kaotik dalam algoritma enkripsi, diantaranya adalah (Habutsu dkk., 1991; Biham, 1991) dan beberapa paper lain (Wheeler, 1991; Wheeler dan Matthews, 1991; Anderson, 1992). Dalam rentang waktu antara 1993-1996, jumlah publikasi ilmiah mengenai topik ini sangat berkurang dibandingkan dengan periode sebelumnya. Hal ini diantaranya disebabkan karena berbagai algoritma enkripsi berbasis dinamika kaotik masih memiliki banyak kelemahan dibandingkan dengan algoritma non kaotik yang telah lazim digunakan. Dalam periode berikutnya (1997-2003) muncul kembali cukup banyak paper yang mengusulkan berbagai skema baru algoritma enkripsi berbasis dinamika kaotik, diantaranya adalah tiga seri paper (Gotz dkk., 1997; Kelber dkk., 1998; Dachselt dkk., 1998) yang mengusulkan skema algoritma enkripsi berbasis dinamika kaotik dan kriptanalisisnya, dan beberapa paper lain yaitu (Jakimoski dan Kocarev, 2001a) dan (Kocarev, 2001) yang berupa tinjauan pustaka dan usulan skema baru dan kriptanalisis. Karena sifat-sifatnya, dinamika kaotik banyak digunakan untuk membangun algoritma enkripsi. Pengembangan metode desain algoritma enkripsi berbasis dinamika kaotik dapat memperjelas keterkaitan antar keduanya dan sebaliknya hasil-hasil penelitian mengenai hubungan antara algoritma enkripsi dan dinamika kaotik juga dapat dipergunakan sebagai dasar untuk membangun skema enkripsi berbasis dinamika kaotik yang baru yang memiliki kriteria keamanan yang setara dengan algoritma enkripsi modern. Kaitan antara algoritma enkripsi dan dinamika kaotik diantaranya dijelaskan oleh Kocarev (2001). Cipher blok yang merupakan salah satu jenis algoritma enkripsi modern, menggunakan proses subtitusi, permutasi dan pengacakan dengan kunci
I–3
secara berulang dalam beberapa ronde. Proses subtitusi dan pengacakan dengan kunci dipergunakan untuk menghasilkan efek konfusi sedangkan proses permutasi dipergunakan untuk menghasilkan efek difusi. Algoritma tersebut mengulang proses-proses ini dalam beberapa ronde. Struktur yang umum digunakan untuk cipher blok adalah struktur Feistel dan jaringan subtitusi dan permutasi (SPN: Subtitution and Permutation Network) . Sebaliknya, desain algoritma enkripsi berbasis dinamika kaotik menggunakan sifat percampuran dan sensitifitas terhadap kondisi mula untuk menghasilkan efek yang setara dengan difusi dan konfusi. Algoritma ini mengiterasi pemetaan kaotik secara berulang untuk menghasilkan teks-cipher. Berbagai metode desain algoritma enkripsi berbasis dinamika kaotik yang diimplementasikan secara digital dijelaskan secara komprehensif oleh Li dkk. (2003). Sedangkan survei mengenai algoritma enkripsi berbasis dinamika kaotik yang diimplementasikan secara analog dibahas di (Li dkk., 2007). Shujun Li mempublikasikan beberapa paper yang mengungkapkan kelemahan mendasar dari algoritma enkripsi berbasis dinamika kaotik khususnya yang menggunakan pemetaan linear kaotik yang terpotong (PWLCM: Piece-Wise Linear chaotic Map). Kelemahan ini, yaitu adanya degradasi dinamik dari pemetaan kaotik dijital, dapat dieksploitasi lebih jauh untuk membangun metode kriptanalisis terhadap algoritma enkripsi berbasis dinamika kaotik (Shujun dkk., 2001; Li dkk., 2003, 2007). Hingga saat ini permasalahan degradasi dinamik ini belum memiliki solusi yang memuaskan. Lebih jauh lagi, Curiac dkk. (2007) mempertanyakan prospek penggunaan dinamika kaotik dalam enkripsi dengan menggunakan argumen-argumen yang agak mirip dengan masalah degradasi dinamik yang telah dikemukakan oleh Shujun Li. Sebagai respon terhadap berbagai kelemahan tersebut, beberapa peneliti selanjutnya berusaha mengkaji ulang landasan teoritis dari dinamika kaotik dijital (Kocarev dan Szczepanski, 2004; Amigó dkk., 2007; Jakimoski dan Subbalakshmi, 2007). Kocarev dan Szczepanski (2004) dan Amigó dkk. (2007) mengusulkan konsep eksponen Lyapunov diskrit untuk diterapkan pada pemetaan kaotik yang beroperasi dalam domain diskrit atau ruang finit. Kemudian, pemetaan kaotik didefinisikan ulang dalam domain diskrit atau ruang finit. Peneliti yang lain menggunakan teori-teori dasar yang diusulkan Kocarev tersebut untuk mengungkap kembali hubungan antara dinamika kaotik dengan algoritma enkripsi secara lebih mendasar. Dalam (Jakimoski dan Subbalakshmi, 2007)
I–4
dan (Amigó dkk., 2007), konsep eksponen Lyapunov diskrit dipergunakan sebagai metrik untuk menganalisa kekuatan atau keamanan algoritma enkripsi non dinamika kaotik terhadap serangan kriptanalisis diferensial. Berdasarkan penjelasan di atas, setidaknya ada empat tema besar dalam bidang enkripsi berbasis dinamika kaotik ini, yaitu: 1. Desain dan usulan skema baru 2. Kriptanalisis 3. Landasan teoritis enkripsi berbasis dinamika kaotik dan dinamika kaotik dijital 4. Menggunakan metodologi sistem dinamik dan dinamika kaotik untuk menganalisa skema enkripsi non-dinamika kaotik. Penelitian dalam disertasi ini adalah pengembangan metode permainan kaotik sebagai sarana kriptanalisis terhadap cipher blok non dinamika kaotik. Jadi penelitian ini termasuk dalam kategori nomor empat. Dengan penelitian ini, penulis berharap dapat berkontribusi dalam mengungkap keterkaitan antara ranah sistem dinamik, khususnya dinamika kaotik, dengan kriptografi. Selain itu, hasil penelitian ini juga berpeluang memperkaya berbagai teknik kriptanalisis yang telah ada saat ini. Penemuan teknik kriptanalisis sangat penting sebagai sarana untuk mengungkap kelemahan dari algoritma enkripsi. Teknik ini selanjutnya juga dipergunakan sebagai dasar dalam mengembangkan algoritma yang lebih aman. Sejauh ini, metode permainan kaotik lebih banyak dipergunakan untuk membangkitkan gambar fraktal. Penerapan lain yang telah ada adalah untuk merepresentasikan urutan rantai DNA. Penggunaan metode permainan kaotik dalam kriptanalisis adalah hal yang baru karenanya penelitian ini berpeluang untuk menghasilkan temuan yang orijinal.
I.2
Identifikasi Masalah Penelitian
Cipher blok dapat dimodelkan sebagai suatu permutasi acak. Setiap serangan yang sukses terhadap sebuah cipher blok pada dasarnya merupakan metode untuk membedakan cipher blok tersebut dari permutasi acak. Sebagai catatan, tidak semua metode yang berhasil membedakan cipher blok dari permutasi acak selalu menghasilkan serangan yang sukses terhadap cipher blok tersebut. Jika Fn melambangkan himpunan semua permutasi dari suatu domain himpunan terbatas yang
I–5
berukuran n ke kodomain himpunan terbatas yang berukuran n. Jika anggotaanggota Fn diambil secara acak, maka proses pengambilan ini disebut sebagai model permutasi acak. Langkah awal untuk membangun metode kriptanalisis terhadap cipher adalah dengan membangun sebuah pembeda (distinguisher) yang merupakan perangkat yang dapat digunakan untuk menetapkan apakah sebuah sistem berperilaku sebagai model permutasi acak. Jika berhasil maka pembeda ini memiliki peluang untuk dikembangkan menjadi metode kriptanalisis. Pembeda ini juga dapat digunakan untuk membedakan keacakan satu cipher blok dari cipher blok lainnya, misalnya untuk membedakan dua cipher blok dengan struktur yang sama namun dengan jumlah ronde yang berbeda. Dalam disertasi ini, pembeda digunakan untuk keperluan yang terakhir. Di sisi lain, skema permainan kaotik dapat membangkitkan gambar fraktal yang lengkap hanya jika inputnya merupakan deret acak yang karakteristiknya mendekati deret acak ideal. Jadi, kita dapat memeriksa karakteristik suatu deret acak s = l0 l1 . . . lN dengan menggunakannya sebagai input suatu skema permainan kaotik dan kemudian memeriksa kelengkapan gambar fraktal XN yang dihasilkannya. Jika deret acak ini dihasilkan oleh sebuah cipher blok, maka memeriksa kelengkapan gambar fraktal sama artinya dengan memeriksa tingkat keacakan cipher blok. Permasalahan utama yang dibahas dalam disertasi ini adalah: Apakah metode permainan kaotik dapat digunakan untuk menganalisis keacakan cipher blok (lihat Gambar I.1)? Jika metode analisis keacakan ini dapat dibangun, apakah metode ini dapat dikembangkan lebih lanjut menjadi metode kriptanalisis cipher blok (lihat Gambar I.2)? Cipher blok memiliki dua alternatif struktur utama yaitu struktur Feistel dan jaringan subtitusi dan permutasi. Proses enkripsi kedua struktur tersebut dilakukan dengan melakukan transformasi tertentu secara berulang. Jumlah pengulangan disebut ronde. Setiap ronde diacak dengan menggunakan subkunci, yaitu kunci yang merupakan turunan dari kunci master. Kriptanalisis terhadap cipher blok pada dasarnya adalah teknik untuk menemukan subkunci. Dalam kasus cipher blok, permasalahan kriptanalisis adalah bagaimana cara untuk mengidentifikasi semua atau sebagian subkunci. Kerangka kerja utama untuk menganalisis cipher blok yang digunakan dalam disertasi ini adalah dengan cara menempatkan cipher blok sebagai sebuah pemetaan
I–6
Gambar I.1. Ilustrasi analisis keacakan untuk membedakan cipher blok 1 dari cipher blok 2
Gambar I.2. Ilustrasi kriptanalisis untuk memilih subkunci yang benar dari sejumlah K alternatif subkunci
I–7
kaotik yang menjadi bagian dari sistem dinamik yang dinyatakan dalam persamaan diferens waktu diskrit yang dinyatakan sebagai berikut: pn+1 = Ek (pn ) dengan n = 0, 1, . . . merupakan indeks iterasi, p ∈ {0, 1}m merupakan peubah status dari sistem dan Ek : {0, 1}m → {0, 1}m merupakan fungsi enkripsi dengan kunci k yang memetakan himpunan bilangan bilangan biner m-bit ke dirinya sendiri. Seluruh analisis terhadap cipher blok yang dilakukan dalam disertasi ini akan menggunakan model sistem dinamik di atas.
I.3
Tujuan Penelitian
Tujuan penelitian dalam disertasi ini adalah adalah: 1. Menggunakan teknik atau metodologi yang dikembangkan dalam bidang keilmuan sistem dinamik untuk menganalisis algoritma enkripsi. 2. Menghasilkan skema permainan kaotik yang dapat dipergunakan untuk menganalisa teks-plain dan teks-cipher dari sebuah cipher blok. Metode analisis ini dapat dipergunakan untuk membedakan tingkat kompleksitas cipher blok. 3. Menghasilkan usulan kerangka dan teknik kriptanalisis baru terhadap cipher blok
I.4
Ruang Lingkup Penelitian
Disertasi ini mengambil fokus dalam pengembangan metode kriptanalisis terhadap cipher blok dengan menggunakan metodologi yang dikembangkan dalam bidang keilmuan sistem dinamik. Berikut adalah ruang lingkup penelitian dalam disertasi ini: 1. Teknik kriptanalisis yang dikembangkan hanya akan diujikan terhadap cipher blok dengan struktur SPN. 2. Penelitian ini akan menggunakan algoritma cipher blok yang umum digunakan untuk mendemonstrasikan metode kriptanalisis linear dan diferensial. Algoritma ini tidak terlalu kompleks, dalam arti panjang bit data dan panjang kunci tidak terlampau besar. Hal ini sangat berguna untuk menguji aplika-
I–8
bilitas dan metode baru yang dikembangkan. Untuk cipher blok ini, diambil beberapa batasan: (a) Semua kotak subtitusi diasumsikan sama (b) Pemetaan kota subititusi tidak berubah.
I.5
Metodologi Penelitian
Berikut adalah langkah-langkah yang dilakukan dalam penelitian ini: 1. Melakukan studi literatur tentang penerapan dinamika kaotik dalam kriptografi. Studi ini terutama menghasilkan fokus dan hipotesis penelitian. Berdasarkan langkah ini, fokus yang diambil adalah mengembangkan metode kriptanalisis yang berbasis sistem dinamik untuk diterapkan terhadap algoritma enkripsi non dinamika kaotik. Hipotesis penelitian akan dibahas dalam subbab berikutnya. 2. Melakukan studi lebih dalam mengenai beberapa teknik kriptanalisis yang standar khususnya kriptanalisis linear dan kriptanalisis diferensial. 3. Mengkonstruksi skema permainan kaotik yang dapat digunakan untuk menganalisis cipher blok. Beberapa kriteria yang dalam konstruksi ini adalah: (a) Skema permainan kaotik dapat menganalisis deret yang tiap sukunya merupakan bilangan biner sepanjang n-bit. Nilai n harus dapat diubahubah sesuai dengan keperluan analisis. (b) Skema permainan kaotik memiliki atraktor yang mudah untuk dianalisis. Analisis dalam konteks ini adalah membedakan atraktor yang lengkap atau ideal dari yang tidak lengkap atau dapat juga berarti mengukur kedekatan suatu atraktor aktual yang dianalisis dari atraktor ideal. 4. Membuat skenario analisis keacakan dan melakukan eksperimen analisis keacakan terhadap cipher blok. 5. Membuat skenario kriptanalisis dan melakukan eksperimen kriptanalisis terhadap cipher blok. 6. Menganalisis hasil eksperimen Analisis terhadap cipher blok dilakukan dengan cara membangkitkan sejumlah data dengan cipher tersebut berdasarkan model serangan tertentu dengan menggunakan
I–9
kunci tertentu. Analisis keacakan dan kriptanalisis dilakukan berikutnya dengan cara menganalisis data yang dibangkitkan tersebut.
I.6
Hipotesis
Berikut ini adalah tiga hipotesis yang diajukan dalam disertasi ini: Hipotesis 1 (Skema Permainan Kaotik sebagai Pembeda). Skema permainan kaotik dapat digunakan untuk menganalisis keacakan cipher blok. Skema ini dapat digunakan untuk membedakan keacakan suatu cipher blok secara relatif dari cipher blok yang lain. Hipotesis 2 (Kriptanalisis Cipher Blok dengan Data Inversi Ronde Terakhir). Kriptanalisis dapat dilakukan hanya dengan menggunakan data-data inversi ronde terakhir dari hasil iterasi cipher blok. Hipotesis 3 (Keberhasilan Metode Kriptanalisis Cipher Blok Berdasarkan Permainan Kaotik). Skema permainan kaotik dapat digunakan untuk mengkriptanalisis cipher blok. Skema ini dapat digunakan untuk membedakan sampel statistik yang berkaitan dengan subkunci yang benar dari sampel statistik lain yang berkaitan dengan subkunci yang salah.
I.7
Sistematika Pembahasan
Sistematika pembahasan dalam disertasi ini adalah sebagai berikut: • Bab I menjelaskan latar belakang, identifikasi masalah, tujuan penelitian, ruang lingkup penelitian, metodologi penelitian, hipotesis, kontribusi ilmiah dan sistematika pembahasan disertasi. • Bab II menjelaskan algoritma enkripsi dan juga penggunaan dinamika kaotik dalam algoritma enkripsi. • Bab III menjelaskan definisi dinamika kaotik dan permainan kaotik. • Bab IV menjelaskan kerangka kerja sistem dinamik untuk analisis cipher blok, analisis dengan dinamika simbolik, konstruksi skema permainan kaotik dan penggunaan konsep ukuran untuk mengukur himpunan titik yang merupakan keluaran skema permainan kaotik. • Bab V menjelaskan penerapan metode permainan kaotik untuk membedakan keacakan cipher blok yang memiliki jumlah ronde yang berbeda.
I–10
• Bab VI menjelaskan penerapan metode permainan kaotik untuk melakukan kriptanalisis terhadap cipher blok • Ban VII berisi kesimpulan dari penelitian ini
BAB II PENGGUNAAN DINAMIKA KAOTIK DALAM ALGORITMA ENKRIPSI Bab ini akan membahas beberapa aspek penting dari cipher blok, penerapan dinamika kaotik dalam algoritma enkripsi dan pengembangan teori dinamika kaotik diskrit untuk analisis dan pengembangan algoritma enkripsi. Subbab II.1 membahas fungsi kriptografi secara umum, kriteria keamanan algoritma enkripsi dan karakteristik cipher blok. Berikutnya, Subbab II.2 akan membahas berbagai penelitian yang telah dilakukan untuk membangun algoritma enkripsi berbasis dinamika kaotik. Terdapat dua jenis dinamika kaotik yang digunakan yaitu dinamika kaotik waktu kontinyu dan dinamika kaotik waktu diskrit. Algoritma enkripsi berbasis dinamika kaotik waktu diskrit dianggap memiliki kemungkinan aplikasi yang lebih luas terutama karena kesetaraan fungsinya dengan algoritma enkripsi standar. Subbab II.3 membahas mengenai berbagai penelitian untuk mengembangkan teori dinamika kaotik diskrit dan penerapannya dalam kriptografi. Tujuan pengembangan teori ini terutama adalah untuk mengatasi permasalahan degradasi dinamik dalam cipher kaotik dijital (DCC: Digital Chaotic Cipher). Teori ini juga digunakan untuk mengungkap lebih jauh keterkaitan antara kriptografi dan dinamika kaotik.
II.1
Pengenalan Kriptografi dan Algoritma Enkripsi
Algoritma enkripsi (cipher) merupakan salah satu bagian dalam sistem kriptografi. Schneier (1996) mendefinisikan kriptografi sebagai ilmu dan seni untuk menjaga pesan agar aman . Definisi lain adalah studi mengenai teknik matematik yang berhubungan dengan aspek keamanan informasi yang mencakup diantaranya, kerahasiaan, integritas data, otentikasi entitas (entity authentication) dan otentikasi sumber data (data origin authentication). Berikut ini adalah tujuan utama dari kriptografi. 1. Kerahasiaan (confidentiality) merupakan layanan untuk mencegah akses terhadap informasi oleh pihak manapun kecuali pihak yang memiliki otoritas akses. Terminologi kerahasiaan seringkali digunakan dalam arti yang sama dengan privasi. Terdapat bermacam-macam cara untuk merealisasikan kerahasiaan, mulai dari perlindungan fisik hingga penerapan metode matematik untuk mengacak data.
II–1
II–2
2. Integritas data (data integrity) merupakan layanan untuk mencegah pengubahan data oleh pihak yang tidak memiliki otoritas. Untuk menjamin integritas data, kita harus memiliki mekanisme untuk mendeteksi terjadinya manipulasi data oleh pihak yang tidak memiliki otoritas. Manipulasi data mencakup penambahan, penghapusan dan penggantian atau penukaran. 3. Otentikasi (authentication) merupakan layanan yang berhubungan dengan identifikasi. Layanan ini berlaku baik untuk entitas maupun informasi. Dua pihak yang berkomunikasi harus dapat saling mengidentifikasi. Hal-hal yang harus diotentikasi diantaranya adalah asal data, isi data dan waktu pengiriman. 4. Non-repudiasi (non repudiation) merupakan layanan yang dapat mencegah suatu entitas untuk mengingkari tindakan atau komitmen yang telah diberikan. Tujuan-tujuan kriptografi di atas direalisasikan dengan setidaknya dua perangkat utama yaitu primitif kriptografi (cryptographic primitives) dan protokol. Protokol merupakan serangkaian langkah-langkah yang didesain untuk mencapai tujuan tertentu, yang dilakukan oleh atau melibatkan lebih dari satu pihak (Schneier, 1996). Primitif merupakan algoritma yang menjadi bagian utama dari protokol kriptografi. Jenis-jenis primitif dapat dilihat dalam Gambar II.1. Algoritma enkripsi mencakup primitif kunci simetri (symmetric key primitives) dan primitif kunci asimetri (asymmetric key primitives). Tujuan utama dari algoritma enkripsi adalah untuk merealisasikan aspek kerahasiaan data. Algoritma enkripsi memungkinkan dua orang, yaitu pengirim dan penerima, untuk berkomunikasi melalui saluran komunikasi yang bersifat publik sedemikian sehingga pihak ketiga yang dapat mengakses saluran komunikasi tersebut, tidak dapat memahami informasi yang terkandung dalam data yang dikomunikasikan (lihat Gambar II.2). Data yang dikirimkan disebut teks-plain sedangkan data telah dienkripsi disebut tekscipher. Proses enkripsi dan dekripsi membutuhkan kunci rahasia (K). Pengirim menyampaikan K kepada penerima melalui saluran komunikasi non publik atau yang dapat dijamin keamanannya. Untuk kasus algoritma enkripsi simetrik, kunci enkripsi identik dengan kunci dekripsi. Algoritma enkripsi asimetrik menggunakan kunci enkripsi yang berbeda dengan kunci dekripsi.
II–3
Gambar II.1. Jenis-jenis primitif (Menezes dkk., 1996)
II.1.1
Definisi Algoritma Enkripsi
Tujuan utama dari algoritma enkripsi adalah untuk merealisasikan aspek kerahasiaan data. Algoritma enkripsi mengacak data sedemikian sehingga data tersebut tidak dapat dibaca atau dimengerti oleh pihak lain yang tidak berhak. Berikut ini adalah beberapa terminologi penting yang menjelaskan algoritma enkripsi. • P melambangkan ruang teks-plain. Setiap anggota dari himpunan P disebut sebagai teks-plain. Sebagai contoh, anggota P dapat berupa bilangan biner, teks dalam bahasa inggris dan sebagainya • C melambangkan ruang teks-cipher. Setiap anggota dari himpunan C disebut sebagai teks-cipher. • K melambangkan ruang kunci. Setiap anggota dari himpunan K disebut sebagai kunci.
II–4
Gambar II.2. Ilustrasi fungsi algoritma enkripsi • Setiap elemen e ∈ K menentukan secara unik sebuah transformasi satu ke satu bijection dari P ke K yang dilambangkan dengan Ee (yaitu, Ee : P → C). Ee disebut sebagai fungsi enkripsi atau transformasi enkripsi. Ee harus sebuah bijection agar transformasi tersebut dapat dibalikkan sehingga setiap teks-cipher tertentu dapat dibalikkan ke satu teks-plain yang unik. • Untuk setiap d ∈ K, Dd melambangkan bijection dari C ke P (yaitu, Dd : C → P). Dd disebut sebagai fungsi dekripsi atau transformasi dekripsi. • Algoritma enkripsi sering disebut sebagai cipher sehingga proses enkripsi dan dekripsi sering disebut sebagai proses ciphering dan deciphering. • Kunci e dan d dalam definisi di atas disebut sebagai pasangan kunci dan dilambangkan dengan (e, d), dengan catatan e dan d mungkin bernilai sama. Definisi II.1 (Algoritma enkripsi (cipher)). Algoritma enkripsi terdiri dari himpunan transformasi enkripsi {Ee : e ∈ K} dan himpunan transformasi dekripsi {Dd : d ∈ K} dengan sifat yaitu untuk setiap kunci enkripsi e ∈ K selalu terdapat kunci dekripsi yang unik d ∈ K sedemikian sehingga Dd = Ee −1 ; yaitu Dd (Ee (p)) = p untuk semua p ∈ P.
II.1.2
Keamanan Algoritma Enkripsi
Kriptanalisis merupakan teknik yang digunakan untuk mematahkan keamanan primitif kriptografi. Sejarah kriptanalisis sudah dimulai sejak tahun 850 Masehi ketika Al-Kindi merumuskan metode analisis frekuensi dan menuangkannya dalam buku A Manuscript on Deciphering Cryptographic Messages. Metode analisis
II–5
frekuensi ini merupakan temuan yang revolusioner saat itu, meskipun merupakan hal yang biasa menurut sudut pandang ilmu kriptografi modern. (Singh, 2002) Tujuan utama serangan terhadap algoritma enkripsi adalah untuk mendapatkan kembali (me-recover) teks-plain dari teks-cipher atau untuk mendapatkan kunci secara sistematis sehingga setiap teks-cipher dapat didekripsi menjadi teks-plain. Berikut adalah beberapa jenis serangan terhadap cipher: 1. Serangan hanya dengan teks-cipher (ciphertext-only attack) adalah serangan untuk mendapatkan kunci dekripsi atau teks-plain hanya berdasarkan observasi terhadap teks-cipher. Algoritma enkripsi yang memiliki kerawanan terhadap jenis serangan ini dianggap tidak aman. 2. Serangan dengan teks-lain yang diketahui (known-plaintext attack) adalah serangan yang dilakukan dengan menggunakan sejumlah teks-plain dan pasangan teks-cipher-nya. Prasyarat kebutuhan data serangan jenis ini lebih sulit dipenuhi secara praktis dibanding serangan jenis pertama. 3. Serangan dengan teks-plain yang dipilih (chosen-plaintext attack) adalah serangan yang dilakukan dengan menggunakan teks-plain yang dipilih dan pasangan teks-cipher-nya. Prasyarat kebutuhan data serangan jenis ini lebih sulit dipenuhi secara praktis dibanding serangan jenis kedua. 4. Serangan dengan teks-plain yang dipilih secara adaptif (adaptive chosenplaintext attack) adalah varian serangan dengan teks-plain yang dipilih dengan pemilihan teks-plain berdasarkan teks-cipher yang diperoleh sebelumnya. 5. Serangan dengan teks cipher yang dipilih (chosen-ciphertext attack) adalah serangan yang dilakukan oleh penyerang dengan memilih sejumlah tekscipher dan mendapatkan pasangan teks-plain-nya. Prasyarat kebutuhan data serangan jenis ini lebih sulit dipenuhi secara praktis dibanding seranganserangan yang lainnya. Kapan sebuah algoritma enkripsi dikatakan aman? Apakah algoritma enkripsi yang aman berarti tidak terpecahkan (unbreakable)? Shannon (1949) mendefinisikan tiga kategori keamanan algoritma enkripsi: 1. Keamanan bersyarat (conditional security) yaitu klaim keamanan algoritma enkripsi yang menyertakan kondisi-kondisi yang menjadi batas keberlakukannya. Kondisi-kondisi ini diantaranya mencakup:
II–6
• kompleksitas data, yaitu: berapa jumlah data minimal yang diperlukan untuk mematahkan algoritma enkripsi. Kompleksitas data seringkali juga mempertimbangkan aspek skenario untuk mendapatkan data. Beberapa jenis serangan berdasarkan data yang dibutuhkan telah dijelaskan dalam subbab sebelumnya. • kompleksitas komputasi, yaitu: berapa besar beban komputasi atau berapa jumlah operasi yang dibutuhkan untuk mematahkan algoritma enkripsi. • kompleksitas waktu, yaitu: berapa lama waktu yang diperlukan untuk mematahkan algoritma enkripsi. Kompleksitas komputasi hampir selalu terkait dengan kompleksitas waktu. 2. Keamanan tanpa syarat (unconditional security) yaitu klaim keamanan yang menyatakan bahwa algoritma enkripsi tidak dapat dipatahkan dalam kondisi apapun meskipun dengan mengerahkan sumber daya yang tidak terbatas. Kategori ini dapat dipandang sebagai klaim keamanan yang bersifat absolut. 3. Keamanan yang dapat dibuktikan (provable security) yaitu klaim keamanan dengan cara mereduksinya menjadi permasalahan lain yang secara ilmiah telah dinyatakan sebagai masalah sulit (hard problem). Masalah sulit adalah permasalahan yang secara matematis sulit dipecahkan atau yang memerlukan upaya sangat besar untuk memecahkannya. Keamanan yang dapat dibuktikan merupakan kasus khusus dari keamanan bersyarat karena klaim keamanan bersyarat biasanya juga terkait dengan masalah sulit. Namun tidak seperti keamanan yang dapat dibuktikan, klaim keamanan bersyarat tidak menggunakan pembuktian ekuivalensi permasalahan klaim keamanan dengan suatu masalah sulit yang telah diketahui.
II.1.2.1
Klaim Keamanan Bersyarat
Bagian ini akan menjelaskan prinsip dasar dari klaim dan pembuktian keamanan bersyarat algoritma enkripsi. Sebagian besar algoritma enkripsi kunci simetrik dan kunci asimetrik mendasarkan klaim keamanannya dengan pembuktian keamanan bersyarat. Prinsip klaim keamanan bersyarat ini menyatakan bahwa suatu algoritma enkripsi hanya dapat dibuktikan aman secara relatif terhadap sejumlah teknik serangan yang sudah diketahui. Klaim keamanan tidak menjamin bahwa algoritma enkripsi tersebut juga tahan terhadap semua kemungkinan teknik serangan lain.
II–7
Berdasarkan prinsip ini, keamanan algoritma enkripsi tidak dapat dibuktikan. Di sisi lain, selalu terbuka peluang bagi para ahli untuk menemukan atau membuktikan kelemahan algoritma enkripsi. Berikut ini kita akan mendefinisikan terlebih dahulu dua hal, yaitu mengenai keamanan dan ukuran keamanan algoritma enkripsi (Ritter, Ritter). Definisi II.2 (Keamanan algoritma enkripsi). Keamanan atau kekuatan algoritma enkripsi adalah: kemampuan algoritma enkripsi tersebut untuk menanggulangi berbagai serangan terhadapnya agar tujuan pengamanan (misalnya: menjaga kerahasiaan) dapat tercapai. Definisi II.3 (Ukuran keamanan algoritma enkripsi). Ukuran keamanan atau kekuatan algoritma enkripsi adalah: upaya dan sumber daya minimum yang diperlukan untuk mematahkan keamanan algoritma enkripsi tersebut. Jadi, jika terdapat dua algoritma enkripsi, sebut saja A dan B, bagaimana cara kita menentukan algoritma enkripsi mana yg lebih aman/kuat? Dari definisi II.3, kita harus menentukan algoritma enkripsi mana yg membutuhkan upaya atau sumber daya minimum yang paling besar untuk membongkarnya. Contoh: jika kita membutuhkan waktu minimum 5 tahun untuk membongkar algoritma enkripsi A dan minimal 3 tahun untuk membongkar algoritma enkripsi B, maka algoritma enkripsi A lebih kuat dari algoritma enkripsi B. Jadi, bagaimana cara kita menentukan sumber daya minimum yang dibutuhkan untuk membongkar algoritma enkripsi A? Karena kita menggunakan nilai sumber daya minimum untuk menyerang algoritma enkripsi sebagai ukuran, maka, sebelumnya kita harus menemukan teknik atau cara serangan yang paling efisien, yaitu yang membutuhkan sumber daya minimum, diantara seluruh serangan yang mungkin dilakukan terhadap A. Kita sebut saja serangan paling efisien terhadap A ini sebagai Attack A ult (yang berarti dari ultimate attack terhadap A). Selanjutnya, kita tetapkan kebutuhan sumber daya untuk melakukan Attack A ult tersebut sebagai ukuran kekuatan algoritma enkripsi A. Hal yg sama kita lakukan jg terhadap algoritma enkripsi B sehingga kita memperoleh sumber daya yang dibutuhkan untuk melakukan Attack B ult . Selanjutnya kita dapat membandingkan kekuatan dua algoritma enkripsi tersebut berdasarkan perbandingan kebutuhan sumber daya serangan paling efisien untuk masing-masing algoritma enkripsi. B Untuk menemukan Attack A ult dan Attack ult kita harus mengetahui semua teknik serangan yang mungkin dilakukan terhadap A dan B. Apakah hal ini mungkin? Dengan cara lain, mungkinkah kita membuktikan bahwa suatu teknik serangan ter-
II–8
A hadap A atau B ekivalen dengan Attack A ult atau Attack ult ? Secara teoritis, hingga saat ini, jawaban untuk dua pertanyaan tersebut adalah negatif.
Jadi apa yang dapat kita lakukan untuk mengukur serta membandingkan keamanan algoritma enkripsi? Kegiatan atau upaya untuk mematahkan keamanan algoritma enkripsi disebut sebagai kriptanalisis. Sangat banyak teknik kriptanalisis yang telah dikembangkan oleh para kriptanalis1 . Kita ambil contoh, bahwa sekelompok kriptanalis telah menemukan n buah teknik serangan terhadap cipher A. Teknik seranA A gan ini kita namakan Attack A 1 , Attack 2 ,. . ., dan Attack n . Berdasarkan informasi tersebut, kita tentukan serangan paling efisien terhadap A dari n jenis serangan yang telah diketahui tersebut. Serangan ini kita beri nama Attack A ultrelatif . Untuk cipher B, jika terdapat m jenis serangan yang telah diketahui kita juga dapat menentukan Attack B ultrelatif (lihat Gambar II.3).
Gambar II.3. Ilustrasi penentuan serangan paling efisien diantara n serangan yang diketahui terhadap A dan m serangan yang diketahui terhadap B Pertanyaan yang penting untuk kita ajukan saat ini adalah: • Apakah tidak ada teknik serangan lain terhadap A yang lebih efisien dibandingkan n teknik serangan terhadap A yang telah diketahui? • Apakah tidak ada teknik serangan lain terhadap B yang lebih efisien selain m teknik serangan terhadap B yang telah diketahui? Berdasarkan penjelasan sebelumnya, pertanyaan-pertanyaan tersebut belum dapat dijawab. Singkatnya, para ahli hanya dapat mengatakan bahwa mereka telah menemukan n jenis serangan terhadap A dan m jenis serangan terhadap B dan 1
Kriptanalis adalah orang yang memiliki keahlian di bidang kriptanalisis
II–9
berdasarkan hal itu mereka dapat menentukan batas bawah kebutuhan sumber daya untuk melakukan serangan terhadap A dan B. Jadi, bukti formal yang diajukan para ahli untuk menyatakan bahwa cipher A lebih aman daripada cipher B (atau sebaliknya) hanya berlaku selama syarat tertentu dapat terpenuhi (conditional), yaitu belum ditemukannya serangan baru terhadap A (atau B) yang membutuhkan B sumber daya yang lebih kecil dibandingkan Attack A ultrelatif (atau Attack ultrelatif ). (Sulistyo, 2009)
II.1.3
Definisi Cipher Blok
Algoritma enkripsi simetrik terdiri dari dua jenis, yaitu: cipher blok cipher blok dan cipher alir (stream cipher). Perbedaan utama antara keduanya adalah cipher alir mengenkripsi karakter per karakter dengan menggunakan transformasi yang berubah terhadap waktu sedangkan cipher blok menggunakan satu transformasi yang tetap untuk mengenkripsi satu kelompok (blok) karakter. Karakter umumnya berupa bit atau byte.
II.1.3.1
Definisi Cipher Blok
Cipher blok adalah fungsi yang memetakan n-bit blok teks-plain ke n-bit blok tekscipher; n disebut sebagai panjang blok. Cipher blok dapat dipandang sebagai algoritma enkripsi subtitusi sederhana dengan panjang karakter cukup besar. Fungsi ini diparameterisasi dengan m-bit kunci k yang diambil dari himpunan K yang merupakan subset dari himpunan seluruh m-bit vektor Vm . Dalam cipher blok, ruang teks-cipher C dan teks-plain P memiliki jumlah elemen yang sama dan terbatas (lihat kembali definisi II.1). Misalkan, jika panjang karakter dari teks-plain dan teks-cipher adalah n bit, maka setiap teks-plain dan tekscipher dapat dinyatakan secara unik sebagai anggota dari himpungan {0, 1}n . Sebuah cipher blok n-bit adalah algoritma enkripsi simetrik dengan P = {0, 1}n dan C = {0, 1}n . Definisi II.4. Ambil P = C = {0, 1}n merupakan ruang teks-plain dan teks-cipher dan K = {0, 1}k merupakan ruang kunci. Definisikan sebuah fungsi E : P × K → C. Maka E merupakan cipher blok n-bit jika untuk setiap K ∈ K, E (., K) = EK (.) selalu memiliki invers. Invers dari EK (.) dilambangkan dengan D (K, .) = DK (.). n merupakan panjang blok dan k merupakan panjang kunci (Borst, 2001).
II–10
Setiap anggota dari P disebut sebagai blok teks-plain dan setiap anggota dari C disebut sebagai blok teks-cipher. Di bagian selanjutnya dari dokumen ini dua hal tersebut cukup disebut sebagai teks-plain dan teks-cipher saja. Berdasarkan definisi II.4, cipher blok merupakan fungsi pemetaan yang bersifat deterministik dan tidak bermemori.
II.1.3.2
Karakteristik Cipher Blok
Berdasarkan definisi II.4, cipher blok merupakan fungsi pemetaan yang bersifat deterministik dan tidak bermemori. Terdapat sebuah kriteria utama yang menjadi dasar perancangan algoritma cipher blok yang sangat menentukan karakteristiknya. Definisi II.5. Ambil Fm untuk melambangkan himpunan semua permutasi dari suatu domain himpunan terbatas yang memiliki jumlah anggota sebanyak m ke kodomain himpunan terbatas yang juga memiliki jumlah anggota m. Fungsi yang mengambil anggota-anggota Fm secara acak disebut sebagai fungsi permutasi acak (Borst, 2001). Kriteria utama cipher blok adalah sebagai berikut: Kriteria II.1. Cipher blok, secara praktis, harus tidak dapat atau sulit dibedakan dari fungsi permutasi acak (Borst, 2001). Sebagai contoh, jika P = C = Vn , proses enkripsi dengan cipher blok n-bit yang diparameterisasi oleh kunci k ∈ K dapat dipandang sebagai permutasi Ek : Vn → Vn . Karena Vn merupakan himpunan seluruh vektor n-bit, maka jumlah anggota Vn adalah 2n . Jika himpunan seluruh permutasi yang mungkin ada untuk kasus tersebut kita lambangkan dengan F2n , maka Ek merupakan elemen dari F2n . Jumlah anggota dari F2n yang menyatakan jumlah seluruh permutasi yang mungkin adalah 2n !. Cipher blok n-bit memetakan blok teks-plain sepanjang n-bit ke blok teks-cipher dengan panjang yang sama. Ruang teks-plain yang menjadi domain cipher blok ini memiliki 2n anggota, demikian pula ruang teks-cipher-nya. Berikut ini adalah definisi dari cipher blok n-bit ideal: Definisi II.6. Cipher blok n-bit ideal adalah fungsi permutasi acak yang dapat memilih secara acak satu permutasi bijections dari himpunan yang memuat 2n ! permutasi atau dari himpunan F[2n ] . Tiap fungsi permutasi tersebut memetakan himpunan Vn ke Vn yang memiliki 2n anggota. Jika setiap permutasi tersebut diparameterisasi dengan sebuah kunci, maka setiap anggota F[2n ] dapat dilambangkan dengan Ek . Karena jumlah anggota F[2n ] adalah 2n !, maka cipher blok
II–11
ini harus memiliki 2n ! kunci yang menspesifikasikan tiap-tiap permutasi (Menezes dkk., 1996). Cipher blok ideal ini memiliki tingkat keamanan maksimum. Hal ini mirip dengan keamanan sempurna one time pad untuk kasus stream cipher. Namun, untuk merealisasikannya kita membutuhkan bilangan log2 (2n !)-bit untuk mengkodekan setiap kunci dari seluruh 2n ! kunci. Berdasarkan formula Stirling, log2 (2n !) ≈ (n − 1.44) 2n . Angka ini sangat besar dan tidak feasible. Sebagai contoh, cipher blok 64-bit memerlukan 267 -byte alokasi memori hanya untuk menyimpan satu kunci. Cipher blok dalam aplikasi nyata hanya menggunakan sebagian kecil kunci dan hanya memilih permutasi enkripsi Ek dari himpunan 2r permutasi yang jauh lebih kecil dari F[2n ] , dengan nilai r antara 56 hingga 256. Cipher blok ini tetap didesain untuk mendekati karakteristik cipher blok ideal, yaitu dengan membuat skema enkripsi atau cipher yang dapat memilih fungsi permutasi secara acak dari himpunan fungsi permutasi yang cukup besar.
II.1.3.3
Cipher Blok Iterasi
Cipher blok teriterasi adalah cipher blok yang tersusun dari pengulangan fungsi tertentu. Fungsi ini disebut fungsi ronde (round function) (Menezes dkk., 1996). Tujuan penggunaan struktur ini adalah agar implementasinya lebih efisien. Transformasi atau fungsi untuk tiap-tiap ronde diparameterisasi dengan kunci yang berbedabeda. Kunci-kunci ini disebut sebagai kunci ronde (round key) atau subkunci. Seluruh kunci ronde ini diturunkan dari kunci utama yang disebut kunci master (master key) dengan menggunakan suatu algoritma penurunan kunci ronde (key schedulling algorithm). Ambil E untuk melambangkan cipher blok, F melambangkan fungsi tiap ronde, K melambangkan kunci master, K1 , . . . , Kr melambangkan kunci ronde untuk sejumlah r-ronde, dan FKi melambangkan fungsi F yang diparameterisasi dengan kunci ronde Ki . Enkripsi terhadap teks-plain p dapat dinyatakan sebagai berikut: Ek (p) = FKr FKr−1 (. . . (FK1 (p)))
(II.1)
Proses enkripsi ini diilustrasikan dalam Gambar II.4 Beberapa jenis cipher blok menggunakan fungsi F yang berbeda untuk ronde yang berbeda. Terdapat juga jenis cipher blok yang menggunakan fungsi F yang berbeda hanya untuk iterasi pertama dan terakhir.
II–12
Gambar II.4. Cipher blok teriterasi dengan r jumlah ronde Jumlah ronde dipilih dengan mempertimbangkan faktor keamanan dan efisiensi. Semakin banyak jumlah ronde maka cipher blok akan semakin aman dan semakin sedikit jumlah ronde maka cipher semakin efisien. Jumlah ronde minimum biasanya dipilih untuk mengatasi berbagai jenis serangan yang sudah diketahui, dan beberapa ronde lagi masih ditambahkan untuk mengantisipasi serangan yang belum diketahui atau ketidakakuratan analisis. Tiap-tiap fungsi ronde ini harus bersifat non-idempotent2 (Stinson, 2002) agar pengulangan ronde dapat meningkatkan keamanan cipher. Pada umumnya, pengulangan jumlah ronde ini dapat meningkatkan ketahanan cipher terhadap shortcut attack. Semakin banyak jumlah ronde, cipher menjadi semakin aman, namun di sisi lain efisiensinya menurun (Borst, 2001).
II.1.3.4
Pemilihan Panjang Blok dan Panjang Kunci
Karena tujuan utama cipher blok adalah untuk merealisasikan aspek kerahasiaan data, maka cipher blok harus didesain sehingga berbagai metode serangan yang mungkin dilakukan terhadapnya menjadi tidak feasible. Pemilihan panjang blok 2
Ambil S untuk melambangkan suatu jenis algoritma enkripsi (misalnya: algoritma enkripsi affine, algoritma enkripsi permutasi atau algoritma enkripsi subtitusi), maka algoritma enkripsi S bersifat idempotent jika iterasi terhadap S menghasilkan S, atau S × S = S 2 = S. Algoritma enkripsi iterasi yang dibentuk oleh algoritma enkripsi idempotent tidak memiliki tingkat keamanan yang lebih tinggi meskipun kompleksitasnya meningkat
II–13
dan panjang kunci yang cukup besar menjadi syarat perlu (necesary condition) keamanan cipher blok. Ambil sebuah cipher blok dengan panjang blok n-bit dan panjang kunci m-bit. Cipher blok tersebut memiliki |P| = |C| = |{0, 1}n | = 2n dan |K| = |{0, 1}m | = 2m . Asumsikan juga bahwa pengguna cipher telah memilih kunci k1 untuk melakukan enkripsi sehingga permutasi enkripsi yang digunakan adalah Ek1 . Jika penyerang dapat memperoleh seluruh pasangan teks-plain dan teks-cipher sejumlah 2n dari Ek1 , maka penyerang dapat mengkarakterisasi Ek1 secara lengkap. Setiap teks-cipher dari pengguna yang dapat dibaca oleh penyerang dapat langsung didekripsikan dengan melihat tabel pasangan teks-plain dan teks-cipher yang telah dibuat sebelumnya. Jika penyerang dapat melakukan serangkaian proses dekripsi dengan menggunakan seluruh kunci yang mungkin, yaitu K = {ki | i = 1, 2, . . . , 2m }, maka penyerang dapat melakukan pencarian kunci secara exhaustive dengan menggunakan sejumlah kecil pasangan teks-plain dan teks-cipher. Jadi panjang kunci m harus cukup besar untuk mencegah pencarian kunci secara exhaustive dan panjang blok juga harus cukup besar untuk mencegah analisis data secara exhaustive. DES memiliki panjang kunci 56-bit dan panjang blok 64-bit sedangkan AES memiliki panjang kunci 128, 198 dan 256-bit dan panjang blok 128-bit.
II.1.3.5
Skema Cipher Blok SPN (Substitution Permutation Network (SPN) Structure)
Berikut ini adalah contoh skema cipher blok dengan struktur SPN. Cipher ini terdiri dari empat ronde. Semua ronde memiliki fungsi transformasi yang identik. Tiap ronde mengimplementasikan tiga operasi dasar yaitu (1) subtitusi, yaitu mengganti nilai sekelompok bit, (2) permutasi, yaitu penukaran posisi bit, dan (3) pengacakan kunci, yaitu melakukan pengacakan terhadap bit dengan menggunakan subkunci yang merupakan turunan dari kunci master. Ini dilakukan melalui operasi exclusiveor. Gambar B.1 adalah contoh cipher blok SPN dengan 16-bit blok data and 32-bit kunci.
II–14
Gambar II.5. Subtitution and permutation network
II–15
II.2
Penggunaan Dinamika Kaotik untuk Membangun Algoritma Enkripsi
Para peneliti menduga bahwa algoritma enkripsi memiliki kaitan erat dengan dinamika kaotik. Dua karakteristik terpenting dari dinamika kaotik, yaitu sifat pencampuran dan sensitifitas terhadap kondisi mula, sering dihubungkan dengan dua karakteristik utama dari algoritma enkripsi yaitu konfusi dan difusi. Seluruh penelitian yang telah dilakukan mengenai keterkaitan algoritma enkripsi dengan dinamika kaotik ini dapat dibagi menjadi dua, yaitus: 1. Penggunaan dinamika kaotik untuk membangun algoritma enkripsi. Tujuannya adalah untuk menjadikan dinamika kaotik beserta seperangkat landasan teoritisnya sebagai metodologi alternatif untuk membangun algoritma enkripsi. 2. Eksplorasi hubungan antara dinamika kaotik dan algoritma enkripsi, yaitu menggunakan perangkat teoritis dalam bidang yang satu (misalnya teori dinamika kaotik) untuk menganalisis bidang yang lain (algoritma enkripsi). Sejak tahun 90-an hingga awal dekade ini, penelitian di bidang ini lebih banyak mengkaji penggunaan dinamika kaotik untuk membangun algoritma enkripsi. Dalam lima tahun terakhir, beberapa peneliti mengambil fokus pada kaitan fundamental antara dinamika kaotik dan algoritma enkripsi. Dachselt dan Schwarz (2001) menjelaskan bahwa enkripsi berbasis dinamika kaotik, antara tahun 1990 sampai dengan 1995 , telah banyak dipublikasikan dalam jurnal-jurnal komunitas kriptografi dan karena itu mendorong terjadinya diskusi lintas disiplin antara komunitas ilmiah sistem nonlinear dengan kriptografi. Namun, sejak tahun 2000-an, pembahasan lintas disiplin ini mulai menghilang dan topik ini hanya dibahas secara eksklusif dalam komunitas ilmiah sistem nonlinear. Menurut Dachselt, hal ini disebabkan karena sebagian besar sistem enkripsi berbasis dinamika kaotik yang diajukan, pada awal mula perkembangannya, menunjukkan banyak kelemahan sehingga dapat dipecahkan bahkan hanya dengan teknik-teknik sederhana.
II.2.1
Klasifikasi Dinamika Kaotik
Menurut domain waktu yg dipergunakan, dinamika kaotik secara umum dibagi menjadi dua yaitu:
II–16
1. Dinamika kaotik dengan domain waktu kontinyu. Representasi matematiknya biasa disebut sebagai aliran kaotik (chaotic flows) dan dinyatakan dalam persamaan diferensial. (Lihat Gambar II.6)
x
t
Gambar II.6. Dinamika kaotik waktu kontinyu, x dan t didefinisikan dalam himpunan bilangan real
2. Dinamika kaotik dengan domain waktu diskrit. Representasi matematiknya biasa disebut sebagai pemetaan kaotik (chaotic maps) dan dinyatakan dalam persamaan perbedaan persamaan diferens. (Lihat Gambar II.7)
x
n
Gambar II.7. Dinamika kaotik waktu diskrit, x didefinisikan dalam himpunan bilangan real dan n dalam bilangan integer Dinamika kaotik waktu kontinyu banyak dipergunakan untuk membangun sistem komunikasi analog yang aman. Sistem ini diimplementasikan secara analog dan sering disebut sebagai komunikasi aman dengan dinamika kaotik (chaotic secure communication). Teknik yang banyak digunakan adalah sinkronisasi kaotik. Tao Yang telah menulis survei lengkap mengenai metode ini (Yang, 2003). Namun, dinamika kaotik ini tidak digunakan untuk membangun algoritma enkripsi untuk keamanan data dijital .
II–17
Algoritma enkripsi standar yang umum digunakan saat ini dirancang untuk keperluan pengamanan data dijital. Untuk menghasilkan algoritma yang memiliki fungsi yang sama dengan algoritma enkripsi standar, digunakan dinamika kaotik domain waktu diskrit. Algoritma yang dihasilkan biasa disebut sebagai DCC (digital chaotic cipher). DCC merupakan algoritma enkripsi yang berpotensi diterapkan di area yang sama dengan algoritma enkripsi standar.
II.2.2
Pendekatan Analog dalam Enkripsi Berbasis Dinamika Kaotik
Pendekatan ini berbasis pada konsep sinkronisasi kaotik. Sistem kripto kaotik yang berbasis sinkronisasi kaotik pada umumnya didesain untuk komunikasi yang aman melewati jalur (channel) yang terkena gangguan (noise). Dalam sinkronisasi kaotik, informasi ditransmisikan melalui beberapa cara: • Penyembunyian kaotik (chaotic masking), yaitu dengan menjumlahkan sinyal pesan m (t) yang analog dengan output c (t) dari pembangkit sinyal kaotik. Terdiri dari dua sistem kaotik yang identik pada sisi transmitter dan receiver. Sinyal pengacak kaotik c (t) merupakan salah satu variabel status dari sistem kaotik pada pengirim (transmitter). Skema ini menjumlahkan sinyal pesan m (t) yang bernergi 20 dB hingga 30 dB lebih kecil daripada c (t) dengan sinyal pengacak kaotik untuk menghasilkan sinyal s (t). • Pemindahan sistem kaotik (chaotic switching atau chaos shift keying) yaitu dengan mempergunakan sinyal pesan biner untuk memilih atraktor kaotik yang berbeda. Dalam skema ini, sinyal pesan m (t) yang berbentuk sinyal dijital memilih sinyal kaotik yang ditransmisikan yaitu c0 (t) atau c1 (t). Kedua sinyal ini dihasilkan oleh dua atraktor kaotik yang mirip yaitu memiliki struktur yang sama namun parameter yang berbeda. • Modulasi kaotik yang terdiri dari dua teknik yaitu: modulasi parameter kaotik dan modulasi kaotik non-otonomus. Dalam modulasi parameter kaotik, sinyal pesan m (t) digunakan untuk mengubah parameter dari pengirim kaotik (chaotic transmitter). Skema modulasi kaotik non-otonomus mempergunakan sinyal pesan m (t) untuk mengubah ruang fasa dari pengirim kaotik. Dalam modulasi parameter kaotik, transmiter diubah-ubah untuk menghasilkan trayektori yang berbeda dalam atraktor yang berbeda. Skema modulasi kaotik non-otonomus mengubah-ubah pengirim untuk menghasilkan trayektori yang berbeda dalam atraktor yang sama.
II–18
• Kombinasi teknik kriptografi klasik dengan dan sinkronisasi kaotik. Skema ini mengenkripsi sinyal pesan p (t) dengan menggunakan sinyal kunci k (t) yang dibangkitkan oleh sistem kaotik di sisi pengirim. Sinyal yang teracak selanjutnya digunakan sebagai masukan bagi sistem kaotik sehingga dinamika kaotik terus menerus berubah secara komplek. • Pendekatan sistem invers (Inverse system approach). Pendekatan ini sebenarnya adalah pendekatan umum yang dapat digunakan baik pada sistem dijital maupun analog. Pada sisi enkoder sinyal pesan p (t) dienkripsi oleh operasi ϕ (p (t) , k (t)) dengan menggunakan sinyal kunci k (t) untuk menghasilkan sinyal terenkripsi s (t). Pada sisi dekoder, sinyal terenkripsi akan melalui operasi ϕ (s (t) , k (t)) untuk memperoleh kembali sinyal pesan p (t). Sinyal pesan p (t) dapat diperoleh kembali jika sistem invers ϕ (s (t) , k (t)) dapat mereproduksi kembali sinyal input sistem ϕ (p (t) , k (t)) secara asimtotis dalam waktu yang terbatas. Sebagai catatan, kedua sistem secara simetrik merupakan invers satu dengan yang lain, namun tidak selalu secara simetrik mensinkronisasi satu dengan yang lain.
II.2.3
Pengembangan Cipher Kaotik Dijital (Digital Chaotic Cipher atau DCC)
Mengenai DCC, Kocarev menyatakan hal yang senada dengan Dachselt yaitu bahwa meskipun cukup banyak paper yang mengajukan berbagai metode untuk membangun DCC, dampak berbagai penelitian mengenai DCC dalam komunitas kriptografi ternyata masih kecil. Menurut Kocarev (2001), hal ini disebabkan oleh dua hal: • Pertama, Sebagian besar algoritma enkripsi berbasis dinamika kaotik menggunakan sistem dinamik yang didefinisikan dalam domain himpunan bilangan real, sehingga menyulitkan dalam realisasi atau implementasi dijital. • Kedua, keamanan dan kinerja sebagian besar metode berbasis dinamika kaotik yang diajukan tidak diukur dengan menggunakan teknik dan kriteria yang umum digunakan oleh komunitas kriptografi. Jakimoski dan Kocarev (2001a) melakukan analisis terhadap dua algoritma DCC dan menghasilkan kesimpulan bahwa kecepatan enkripsi dua algoritma tersebut lebih rendah dibandingkan algoritma enkripsi standar. Selain itu, dua algoritma
II–19
tersebut dapat dipecahkan dengan menggunakan teknik serangan dengan teks-plain yang diketahui. Sebagaimana dalam algoritma enkripsi standar, Li dkk. (2003) membagi algoritma DCC menjadi dua, yaitu: cipher alir dan cipher blok. Ada dua jenis cipher alir, yaitu: jenis pertama yang menggunakan pembangkit bilangan acak pseudo (pseudo random number generator atau PRNG) berbasis dinamika kaotik dan jenis kedua yang menggunakan sistem dinamika kaotik yang memiliki invers. Dalam cipher alir jenis pertama, dinamika kaotik akan membangkitkan rangkaian bilangan acak yang selanjutnya digunakan untuk mengacak setiap karakter teks-plain. Untuk melakukan enkripsi dalam cipher alir jenis kedua, teks-plain diperlakukan sebagai sinyal input dari suatu sistem dinamik yang dapat dinyatakan dalam persamaan diferens nonlinear. Dekripsi dilakukan dengan cara yang sama dengan menggunakan sistem dinamik yang merupakan invers dari sistem yang pertama (Gotz dkk., 1997; Kelber dkk., 1998). Shujun Li juga membagi metode untuk membangun cipher blok menjadi dua, yaitu: jenis pertama, yang menggunakan iterasi terbalik pemetaan kaotik, dan jenis kedua yang menggunakan iterasi maju pemetaan kaotik. Jenis pertama melakukan enkripsi dengan menggunakan pemetaan kaotik linear/nonlinear terpotong (piecewise linear/nonlinear chaotic map) yang diiterasi secara terbalik dan menggunakan bilangan acak untuk memilih bagian/segmen dari pemetaan kaotik untuk setiap satu iterasi terbalik. Jenis kedua menggunakan pemetaan kaotik dua dimensi dan mengiterasinya dalam arah maju. Selain metode-metode tersebut, Kocarev (Jakimoski dan Kocarev, 2001b) menggunakan chaotic map untuk membangkitkan fungsi F dari struktur Feistel. Struktur Feistel merupakan salah satu jenis struktur algoritma enkripsi standar. F bergantung pada kunci dan terdiri dari bagian linear dan non-linear. Bagian non-linear pada umumnya diimplementasikan sebagai fungsi subtitusi, sehingga sering disebut sebagai S-Box (subtitution box) yang merupakan bagian dari cipher blok standar.
II.2.4
Permasalahan Mendasar Cipher Kaotik Dijital
Implementasi numerik menjadi isu yang sangat penting dalam DCC. Seperti telah dijelaskan di bagian sebelumnya, pemetaan kaotik beroperasi dalam domain waktu t diskrit dengan nilai variabel x dalam domain kontinyu. Di sisi lain, komputer dan sistem dijital hanya dapat menyatakan bilangan dengan presisi yang terbatas. Jadi, dalam DCC, orbit dari pemetaan kaotik harus dinyatakan dalam bilangan de-
II–20
ngan presisi yang terbatas sehingga orbit yang dihasilkan menjadi berbeda dari orbit yang seharusnya secara teoritis. Lebih jauh lagi, karena jumlah status terbatas, maka implementasi dijital dari pemetaan kaotik akan selalu menghasilkan orbit yang periodik! (Curiac dkk., 2007). Dengan kata lain, dinamika yang seharusnya bersifat kaotik menjadi tidak kaotik. Implementasi pemetaan kaotik secara dijital mendegradasi sifat-sifat kaotik dari sistem. Shujun Li mengembangkan metode untuk mengukur tingkat degradasi dinamik dan menggunakannya untuk menyerang DCC. Hingga saat ini belum terdapat metode sistematis untuk mengatasi permasalahan degradasi dinamik ini. Yang ada adalah beberapa teknik heuristik diantaranya dengan meningkatkan kepresisian representasi numerik atau dengan menggunakan beberapa jenis pemetaan kaotik sekaligus dalam satu DCC. (Shujun dkk., 2001)
II.3
Pengembangan Teori Dinamika Kaotik Diskrit
Salah satu isu penting dalam algoritma enkripsi berbasis dinamika kaotik adalah masalah implementasi numerik seperti telah dijelaskan dalam subbab sebelumnya. Secara fundamental, seluruh orbit dalam ruang fasa finit (finite state phase space) selalu periodik dengan kata lain tidak ada dinamika kaotik dalam sistem dengan ruang fasa finit (finite-state system). Untuk mengatasi permasalahan ini, para praktisi kriptografi kaotik pada umumnya berusaha meningkatkan ketelitian representasi aritmatik. Kocarev tidak menyarankan penggunaan aritmatika floating point karena beberapa sebab berikut: 1. Bilangan floating point tidak terdistribusi secara seragam (uniform) untuk setiap interval dalam garis bilangan real sehingga menyebabkan terdapatnya representasi bilangan yang redundan atau mendua. 2. Belum ada perangkat analisis yang dapat digunakan untuk memahami struktur orbit dari pemetaan kaotik yang diimplementasikan dalam aritmatika floating point. Berdasarkan dua hal tersebut, Kocarev menyarankan implementasi dinamika kaotik diskrit dalam bilangan integer. Amigo dkk. (2007) memformulasikan konsep kriptografi kaotik dengan cara membangun teori dinamika kaotik diskrit. Untuk mendefinisikan dinamika kaotik diskrit, paper ini merumuskan terlebih dahulu definisi eksponen Lyapunov diskrit dan kemudian mendefinisikan syarat untuk permutasi diskrit agar dapat dikatakan memiliki sifat kaotik diskrit. Paper ini me-
II–21
max nunjukkan terdapatnya sebuah fungsi permutasi FM yang menghasilkan nilai eksponen Lyapunov diskrit λFMmax maksimum yaitu ∞. Kemudian dibuktikan bahwa semua fungsi permutasi kaotik F selalu memiliki nilai eksponen Lyapunov diskrit λF yang positif dan lebih kecil dari ∞. Dalam paper ini, Kocarev juga mengusulkan definisi formal primitif kriptografi kaotik dan algoritma kriptografi kaotik. Kocarev dan Szczepanski (2004) menggunakan terminologi eksponen Lyapunov dalam ruang finit untuk Lyapunov eksponen diskrit dan dinamika kaotik pseudo (pseudochaos) untuk dinamika kaotik diskrit. Tujuan utamanya adalah untuk mengambangkan algoritma enkripsi berbasis dinamika kaotik diskrit.
Jakimoski menggunakan hasil dari Kocarev untuk tujuan yang berbeda. Dalam (Jakimoski dan Subbalakshmi, 2007), λF dari cipher digunakan untuk memeriksa ketahanannya dari kriptanalisis diferensial. Jakimoski memberikan batas bawah dan batas atas λF untuk pemetaan enkripsi yang optimal. Paper ini menunjukkan bahwa pemetaan enkripsi yang baik akan selalu menghasilkan λF yang mendekati nilai λF dari pemetaan nonlinear sempurna (perfectly nonlinear map). Pemetaan nonlinear sempurna didefinisikan dalam (Kocarev dkk., 2005). Namun implikasi dalam arah sebaliknya belum dapat dibuktikan, yaitu apakah pemetaan yang memiliki λF yang mendekati λF pemetaan nonlinear sempurna akan selalu menghasilkan pemetaan enkripsi yang baik. Batas atas λF pemetaan enkripsi optimal dioptimalisasi dalam (Amigó dkk., 2007). Amigó dkk. juga menyatakan bahwa, untuk pemetaan F tertentu, keterkaitan antara λF dengan probabilitas diferensial maksimum (DP F ) sangat penting karena penghitungan λF membutuhkan kompleksitas komputasi yang lebih kecil daripada penghitungan DP F .
BAB III DINAMIKA KAOTIK DAN PERMAINAN KAOTIK Kerangka sistem dinamik, khususnya sistem dinamika kaotik (chaos dynamic), akan digunakan sebagai dasar pengembangan metode analisis cipher blok dalam disertasi ini. Subbab III.1 membahas tentang karakteristik dinamika kaotik. Subbab III.2 akan membahas tentang penggunaan metode permainan kaotik untuk membangkitkan gambar fraktal. Dalam bab berikutnya akan dibahas usulan skema permainan kaotik baru yang akan digunakan dalam analisis cipher blok.
III.1
Karakteristik Dinamika Kaotik
Subbab ini akan membahas definisi dan karakteristik dari dinamika kaotik. Yang akan dibahas lebih dahulu adalah batasan sistem dinamik deterministik, beberapa karakteristik dasar sistem dinamik di sekitar titik tetapnya yang mencakup titik tetap penarik, titik tetap periodik dan kestabilan titik tetap. Di bagian akhir baru kita akan mendefinisikan dinamika kaotik. Sistem dinamik terdiri dari himpunan peubah status (states variable) dan aturan (persamaan) yang menetapkan atau menghubungkan peubah status saat ini berdasarkan status-status waktu lampau. Aturan ini juga dapat menyatakan hubungan antara satu peubah status dengan peubah status yang lain. Sebagai contoh, sistem dinamik sederhana dengan peubah status yang mewakili tingkat populasi, yang berubah terhadap waktu berdasarkan aturan xn = f (xn−1 ) = 2xn−1 , dengan n menyatakan waktu dan xn menyatakan tingkat populasi pada waktu n. Aturan dari sistem harus bersifat deterministik, artinya kita dapat menentukan status saat ini secara unik berdasarkan pengetahuan terhadap status waktu lampau. Sistem seperti ini disebut sebagai sistem dinamik deterministik (deterministic dynamical system). Tidak ada keacakan yang diperkenankan memasuki model ini. Jenis sistem lain yang melibatkan keacakan disebut proses stokastik (stochastic proccess). Seluruh pembahasan dalam subbab ini hanya mencakup sistem dinamik deterministik, bukan proses stokastik. Terdapat dua jenis sistem dinamik berdasarkan domain waktu yang digunakan: • Jika persamaan sistem berlaku dalam waktu diskrit, maka sistem ini disebut sistem dinamik waktu-diskrit (discrete-time dynamical system) atau pemeta-
III–1
III–2
an (maps). Persamaan sistem disebut persamaan diferens (difference equation). Sistem dinamik waktu diskrit menggunakan status saat ini sebagai masukan untuk mendapatkan status waktu berikutnya. • Sistem yang dibentuk dari limit sistem dinamik waktu-diskrit jika selang waktu pembaruan (updating times) peubah status dibuat sekecil mungkin mendekati nol . Persamaan sistem yang dihasilkan disebut persamaan diferensial (differential equation) dan sistem yang dihasilkan disebut sistem dinamik waktu-kontinyu (continuous-time dynamical system). Sistem dinamik waktu diskrit yang memiliki satu peubah status atau pemetaan satu dimensi (one-dimensional maps) akan dibahas lebih dalam di subbab ini karena disertasi ini akan menggunakan sistem jenis ini sebagai dasar pengembangan metode analisis cipher blok. Berbagai konsep dalam pembahasan pemetaan satu dimensi tetap berlaku untuk kasus pemetaan dengan dimensi lebih dari satu.
III.1.1
Pemetaan Satu Dimensi
Evolusi pemetaan satu dimensi dihasilkan oleh komposisi dari suatu fungsi f . Definisikan f 2 (x) = f (f (x)) atau secara umum definisikan f k (x) sebagai hasil pemetaan berulang fungsi f sebanyak k-kali terhadap kondisi awal tertentu. Definisi III.1. Suatu fungsi yang memiliki ruang domain (domain space atau input space) dan ruang range (range space atau output space) yang sama disebut sebagai pemetaan (map). Ambil sebuah titik x dan sebuah pemetaan f , orbit dari pemetaan f terhadap x adalah himpunan titik {x, f (x) , f 2 (x) , . . .}. Titik peratama dari orbit tersebut disebut sebagai titik mula orbit. Sebuah titik p disebut sebagai titik tetap (fixed point) dari orbit jika f (p) = p (Kathleen T. Alligood, 2000). Sebagai contoh, fungsi g (x) = 2x (1 − x) yang memetakan bilangan real ke dirinya sendiri merupakan suatu pemetaan. Orbit dari g terhadap 0.01 adalah {0.01, 0.0198, 0.0388, . . .} dan titik tetap dari g adalah x = 0 dan x = 1/2 (lihat Gambar III.1).
III.1.2
Stabilitas Titik Tetap
Sebuah sistem dinamik dapat memiliki lebih dari satu titik tetap yang memiliki karakteristik yang berbeda-beda. Titik tetap stabil memiliki karakteristik semua titik mula yang "cukup dekat" dengannya akan menghasilkan orbit yang semakin
III–3
mendekati titik tetap stabil tersebut. Titik mula di sekitar titik tetap tak-stabil menghasilkan orbit yang menjauhinya. Dalam Gambar III.1 terlihat bahwa x = 0 merupakan titik tetap tak-stabil sedangkan x = 1/2 merupakan titik tetap stabil. Nilai awal yang "cukup dekat" yang bagaimanakah yang mengkarakterisasi suatu titik tetap? Konsep ini dijelaskan dengan melihat seluruh titik dalam radius dari titik tetap p yang dilambangkan dengan N (p). Lambangkan garis bilangan real dengan R, maka N (p) dinyatakan sebagai himpunan bilangan dalam iterval tertentu {x ∈ R : |x − p| < }, dengan merupakan bilangan positif yang kecil. Definisi III.2. Ambil f sebagai pemetaan dalam R dan p adalah titik yang memenuhi f (p) = p. Jika seluruh nilai awal yang cukup dekat dengan p semuanya menghasilkan orbit yang semakin mendekati p, maka p disebut titik tetap penarik (attracting fixed point atau sink). Secara formal, jika terdapat suatu > 0 sedemikian sehingga untuk seluruh x di dalam N (p), limk→∞ f k (x) = p, maka p merupakan titik tetap penarik. Jika seluruh nilai awal yang cukup dekat dengan p semuanya menghasilkan orbit yang semakin menjauhi p, maka p disebut titik tetap penolak (repelling fixed point atau source). Secara formal, jika terdapat suatu > 0 sedemikian sehingga untuk seluruh x di dalam N (p) kecuali p, akhirnya akan dipetakan ke luar dari N (p), maka p merupakan titik tetap penolak (Kathleen T. Alligood, 2000)(Gulick, 1992).
III.1.3
Karakteristik Titik Periodik
Persamaan umum dari pemetaan kuadratik yang diparameterisasi oleh a dinyatakan sebagai ga (x) = ax (1 − x). Nilai parameter a yang berbeda menghasilkan dinamika yang sama sekali berbeda. Untuk a = 3.3, titik tetap adalah x = 0 dan x = 23/33, dengan keduanya merupakan titik tetap penolak. Karena kedua titik tetap merupakan titik tetap penolak, maka kedua orbit tersebut akan mendekati titik periodik p1 = 0.4794 dan p2 = 0.8236. Orbit yang dihasilkan oleh titik mula x = 0.2 dapat dilihat dalam Gambar III.2. Gambar III.2 menunjukkan perilaku suatu orbit yang konvergen ke penarik periode2. Orbit akan berpindah secara bolak-balik dari p1 ke p2 dan sebaliknya. Terdapat beberapa fakta menarik terkait g3.3 , yaitu: 2 1. g3.3 (p1 ) = p2 dan g3.3 (p2 ) = p1 . Dapat diperlihatkan juga bahwa g3.3 (p1 ) = 2 2 p1 dan g3.3 (p2 ) = p2 sehingga p1 dan p2 merupakan titik tetap untuk g3.3 .
2. Osilasi orbit antara p1 dan p2 bersifat stabil sehingga menarik orbit.
III–4
Gambar III.1. Contoh cobweb plot untuk fungsi kuadratik (logistik) g (x) = 2x (1 − x)
Gambar III.2. Orbit periodik
III–5
Berikut ini adalah definisi titik periodik: Definisi III.3. Ambil f sebagai pemetaan dalam R. p disebut sebagai titik periodik dengan periode k jika k merupakan bilangan positif integer terkecil sehingga f k (p) = p. Orbit dengan nilai awal p yang terdiri dari sejumlah k-titik disebut sebagai orbit periodik dengan periode k (periodic orbit of period k) atau dapat disebut sebagai titik periode k (periode-k point) atau orbit periode k (period-k orbit) (Kathleen T. Alligood, 2000)(Gulick, 1992). Sebagaimana titik tetap, titik atau orbit periode k dapat memiliki karakteristik yang berbeda-beda. Hal ini dijelaskandalam definisi berikut: Definisi III.4. Ambil f sebagai suatu pemetaan dan p sebagai suatu titik periode k. Orbit periode k dari p merupakan suatu penarik periodik (periodic sink) jika p merupakan titik tetap penarik untuk f k . Orbit dari p adalah suatu penolak periodik (periodic source) jika p merupakan suatu titik tetap penolak untuk pemetaan f k (Kathleen T. Alligood, 2000)(Gulick, 1992).
III.1.4
Sensitifitas terhadap Kondisi Mula
Kita ambil pemetaan f (x) = 3x mod 1, dengan domain {x ∈ R : 0 ≤ x ≤ 1}, sebagai contoh kasus sensitifitas terhadap kondisi mula (lihat Gambar III.3). Dalam
Gambar III.3. Pemetaan f (x) = 3x mod 1 pemetaan ini, sepasang titik mula atau kondisi mula yang dipilih sedekat mungkin akhirnya akan menghasilkan orbit yang terpisah. Tabel III.1 memperlihatkan pasangan orbit dengan kondisi mula yang berbeda 0.001. Dalam kasus ini, sedekat apapun pasangan kondisi mula, maka jarak antara pasangan orbit yang dihasilkan akan dikalikan tiga untuk setiap langkah iterasi. Berikut ini definisi sensitifitas terhadap kondisi mula.
III–6
n 0 1 2 3 4 5 6 7 8 9 10
f n (x0 ) 0.25 0.75 0.25 0.75 0.25 0.75 0.25 0.75 0.25 0.75 0.25
f n (y0 ) 0.2501 0.7503 0.2509 0.7527 0.2581 0.7743 0.3229 0.9687 0.9061 0.7183 0.1549
Tabel III.1. Pasangan orbit yang dihasilkan oleh pemetaan f (x) = 3x mod 1 Definisi III.5. Ambil f sebagai fungsi pemetaan dalam R. Suatu titik x0 disebut memiliki ketergantungan yang sensitif terhadap kondisi mula jika terdapat selang (jarak) d yang tidak nol sedemikian sehingga sedekat apapun dari x0 akan selalu terdapat beberapa titik yang akhirnya akan dipetakan dengan jarak sedikitnya d dari peta x0 . Secara lebih formal, terdapat d > 0 sedemikian sehingga semua lingkungan N di sekitar x0 selalu memiliki titik x yang memenuhi k f (x) − f k (x0 ) ≥ d untuk nilai integer k tertentu yang tidak negatif. Kita dapat menyebut x0 sebagai titik sensitif (Kathleen T. Alligood, 2000)(Gulick, 1992). Semakin dekat x dari x0 maka semakin besar nilai k yang dibutuhkan.
III.1.5
Analisis dengan Kode Simbol
Teknik ini digunakan untuk mengkodekan suatu orbit ke dalam simbol-simbol diskrit sehingga analisis terhadap orbit tersebut dapat dilakukan selanjutnya dengan mengamati dinamika kode-kode simbol tersebut. Rangkaian simbol yang dihasilkan untuk suatu orbit disebut kode simbol atau itinerary dari orbit tersebut. Analisis orbit dengan menggunakan teknik ini disebut sebagai analisis dengan analisis dengan dinamika simbolik (symbolic dynamic analysis). Kita ambil fungsi G (x) = g4 (x) = 4x (1 − x) sebagai contoh. Untuk fungsi ini tetapkan simbol L untuk sub-interval sebelah kiri [0, 1/2] dan R untuk sub-interval sebelah kanan [1/2, 1]. Dengan kondisi awal tertentu, x0 , kita menyusun kode simbol dari orbit yang dihasilkan dengan menuliskan interval L atau R yang memuat x0 dan titik-titik orbit dalam iterasi selanjutnya. Sebagai contoh, x0 = 13 akan meng hasilkan orbit 31 , 98 , 32 , . . . , sehingga kita mendapatkan kode simbol LRL . . .. Un81
III–7
tuk kondisi awal x0 = 1/4 didapat orbit 14 , 34 , 43 , . . . yang berakhir di titik tetap x = 34 . Kode simbol dari orbit ini adalah LRR . . . yang dapat disingkat dengan LR. Dengan teknik ini kita dapat mencari interval yang memuat titik mula x0 dengan kode simbol tertentu. Secara umum, kode simbol untuk suatu orbit merupakan deret dengan panjang tak terhingga. Meskipun demikian kita dapat mencari subinterval yang memuat titik mula x0 yang memiliki kode simbol yang diawali, misalnya, dengan LR. Berdasarkan kode simbol tersebut, titik mula ini akan berawal dari subinterval L dan dipetakan ke subinterval R. Himpunan titik awal ini, yang kita sebut sebagai himpunan LR diperlihatkan dalam Gambar III.4. Gambar tersebut juga menunjukkan contoh subinterval lain yang memuat titik awal dengan kode simbol yang lain. Sebagai contoh, titik mula x = 13 berada di interval LRL karena orbit yang dihasilkan bermula di L = [0, 1/2], iterasi pertama jatuh pada interval R = [1/2, 1] dan iterasi kedua jatuh pada interval L = [0, 1/2]. Titik mula x = 41 berada di interval LRR karena iterasi ketiga jatuh pada interval R = [1/2, 1] (Kathleen T. Alligood, 2000)(Peitgen dkk., 1992)(Barnsley, 1988)(Gulick, 1992).
Gambar III.4. Pemetaan G (x) = 4x (1 − x) dengan contoh subinterval yang diberi nama sesuai dengan kode simbol yang dihasilkan oleh titik mula yang berada dalam interval tersebut.
III–8
III.1.6
Definisi Dinamika Kaotik
Titik mula yang dekat dengan suatu titik tetap penolak p dari fungsi pemetaan f akan menghasilkan perilaku tak-stabil terhadap titik mula tersebut. Pemisahan secara eksponensial berarti jarak antara titik orbit dengan titik tetap penolak semakin besar secara eksponensial dengan faktor pengali jarak sebesar f 0 (p) > 1. Pada awalnya, orbit akan semakin menjauh dari p, dan setelah sejumlah iterasi, orbit mungkin akan tertarik ke titik tetap penarik q. Di sekitar titik penarik q ini, orbit akan berperilaku konvergen, yaitu jarak antara titik orbit dengan titik tetap penarik q akan mengecil dengan faktor f 0 (p) < 1. Perilaku tersebut ditunjukkan oleh sistem dinamik yang tak-kaotik. Untuk sistem dinamik yang kaotik, orbit tak stabil di sekitar suatu titik tetap penolak tidak harus berakhir atau konvergen menuju ke suatu titik tetap penarik. Sebagai contoh, bahkan pemetaan G (x) = 4x (1 − x) tidak memiliki orbit yang berperilaku stabil (Kathleen T. Alligood, 2000). Orbit kaotik adalah orbit yang selamanya menunjukkan perilaku tak-stabil sebagaimana yang ditunjukkan oleh suatu orbit yang berada di sekitar titik tetap penolak dan bukan merupakan titik tetap maupun orbit periodik. Orbit kaotik tidak pernah mendekati atau konvergen menuju titik tetap penarik. Dalam jarak yang sedekat apapun dari titik orbit kaotik, selalu ada titik yang akan bergerak menjauhi titik orbit kaotik ini dalam iterasi selanjutnya. Gambar III.5 menunjukkan dua titik mula yang berdekatan yang menghasilkan dua orbit dengan jarak yang semakin besar seiring bertambahnya. Perilaku ketidakteraturan yang menetap dari orbit kaotik ini akan dikuantifikasi dengan bilangan Lyapunov (Lyapunov number) dan eksponen Lyapunov (Lyapunov exponent). Bilangan Lyapunov didefinisikan sebagai kecepatan rata-rata divergensi atau pemisahan orbit yang dihasilkan oleh (atau dimulai dari)titik-titik yang berdekatan dalam tiap langkah (atau tiap iterasi). Eksponen Lyapunov merupakan logaritma natural dari bilangan lyapunov. Berdasarkan hal ini, orbit kaotik didefinisikan sebagai orbit yang memiliki eksponen Lyapunov lebih besar dari nol. Definisi III.6. Ambil f sebagai pemetaan yang mulus dalam garis bilangan R. Bilangan Lyapunov L (x1 ) dari orbit {x1 , x2 , x3 , . . .} didefinisikan sebagai L (x1 ) = lim (|f 0 (x1 )| . . . |f 0 (xn |), n→∞
jika limit ini ada. Eksponen Lyapunov h (x1 ) didefinisikan sebagai 1 (ln |f 0 (x1 )| . . . ln |f 0 (xn |), n→∞ n
h (x1 ) = lim
III–9
Gambar III.5. Perilaku kaotik dari fungsi pemetaan G (x) = 4x (1 − x). Dua titik awal yang sangat berdekatan menghasilkan orbit yang semakin menjauh seiring bertambahnya iterasi (Kathleen T. Alligood, 2000). jika limit ini ada. Perhatikan bahwa h ada jika dan hanya jika L ada dan tidak nol, dan ln L = h (Kathleen T. Alligood, 2000)(Gulick, 1992). Bilangan Lyapunov dan eksponen Lyapunov dapat tidak terdefinisi untuk orbit tertentu. Sebagai contoh, suatu orbit yang memiliki titik xi dengan f 0 (xi ) = 0 menyebabkan eksponen Lyapunov tidak terdefinisi. Berdasarkan definisi di atas, untuk titik tetap x1 dari pemetaan satu dimensi f kita peroleh L (x1 ) = |f 0 (x1 )| dan ekivalen dengan itu h (x1 ) = ln |f 0 (x1 )| . Jika x1 merupakan titik periodik dengan periode k, maka eksponen Lyapunov yang dihasilkan adalah h (x1 ) =
ln |f 0 (x1 )| + . . . + ln |f 0 (xk )| k
Berikut ini adalah definisi orbit periodik asimtotik: Definisi III.7. Ambil f sebagai pemetaan yang mulus. Suatu orbit {x1 , x2 , . . . , xn , . . .} disebut periodik asimtotik jika orbit tersebut konvergen ke suatu orbit periodik untuk n → ∞, ini berarti bahwa terdapat orbit periodik
III–10
{y1 , y2 , . . . , yk , y1 , y2 , . . .} sedemikian sehingga lim |xn − yn | = 0.
n→∞
(Kathleen T. Alligood, 2000) Berikut adalah definisi dari orbit kaotik: Definisi III.8. Ambil f sebagai pemetaaan dalam garis bilangan real R, dan ambil {x1 , x2 , . . .} sebagai orbit terbatas (bounded orbit) dari f . Orbit tersebut chaotic jika (1) {x1 , x2 , . . .} tidak asimtotik periodik dan memiliki (2) eksponen Lyapunov h (x1 ) lebih besar dari nol (Kathleen T. Alligood, 2000).
III.2
Pengenalan Permainan Kaotik
Permainan kaotik adalah metode yang digunakan untuk membangkitkan gambar fraktal. Pada dasarnya terdapat dua metode utama untuk menghasilkan gambar fraktal, yaitu algoritma deterministik dan permainan kaotik . Dalam algoritma deterministik, beberapa fungsi pemetaan yang yang membangun IFS digunakan untuk melakukan iterasi terhadap himpunan titik sehingga hasil iterasi tersebut akhirnya akan mencapai sebuah atraktor yang berupa gambar fraktal. Metode permainan kaotik menghasilkan gambar fraktal dengan menggunakan deret acak sebagai input untuk memilih satu diantara himpunan fungsi pemetaan dalam setiap langkah iterasi terhadap satu titik awal yang telah dipilih sebelumnya.
III.2.1
Pengenalan Fraktal dan Sistem Fungsi Iteratif
Agak sulit untuk membahas permainan kaotik tanpa membahas fraktal terlebih dahulu. Fraktal adalah obyek geometri yang dapat dibagi-bagi menjadi bagianbagian dengan masing-masing bagian merupakan salinan dari keseluruhan (lihat Gambar III.6). Sifat ini sering disebut sebagai kesamaan dengan diri sendiri (selfsimilarity). Terminologi fraktal peratama kali diusulkan oleh Benoit Mandelbrot. Penelitian mengenai fraktal mulai muncul pada abad ke-19. Fraktal matematis merupakan fraktal yang dibuat berdasarkan persamaan matematik tertentu yang mengandung umpan balik dan rekursi. Di bidang matematika , terminologi permainan kaotik, sebagaimana yang dijelaskan oleh Michael Barnsley (Barnsley, 1988) , merujuk pada metode pembentukan fraktal dengan menggunakan bidang poligon dan titik-titik acak di dalam-
III–11
Gambar III.6. Fraktal pentagram (http://en.wikipedia.org/wiki/Fractal) nya. Fraktal dibentuk dengan cara mem-plot sebuah titik yang berada, dengan perbandingan tertentu, diantara titik sebelumnya dan titik sudut poligon dan mengulang proses tersebut dalam sejumlah besar iterasi. Sebagai contoh, jika poligon yang digunakan adalah segitiga dan perbandingan jarak yang digunakan adalah 12 maka akan diperoleh segitiga Sirpienski. Sistem fungsi iteratif (selanjutnya disingkat dengan IFS:iterated function system) merupakan sistem yang digunakan untuk membangkitkan gambar fraktal. Gambar fraktal pada dasarnya merupakan himpunan titik yang bersifat invarian terhadap IFS. Iterasi terhadap gambar fraktal dengan menggunakan IFS yang bersesuaian dengannya akan menghasilkan kembali gambar fraktal yang identik. IFS terdiri dari sekumpulan transformasi atau fungsi pemetaan yang mengiterasi himpunan titik, bidang atau bentuk geometri lainnya (lihat Gambar III.7).
Gambar III.7. Ilustrasi IFS Bagian ini menjelaskan hal-hal yang relevan mengenai fraktal dan IFS. Definisi III.9. Suatu transformasi f : X → X terhadap sebuah ruang metrik (metric space) disebut sebagai contraction mappings jika terdapat sebuah konstan-
III–12
ta 0 ≤ s < 1 sedemikian sehingga d (f (x) , f (y)) ≤ s.d (x, y) ∀x, y ∈ X
(III.1)
Nilai s disebut sebagai contractivity factor dari f (Barnsley, 1988). Transformasi dalam definisi III.9 tersebut merupakan fungsi pemetaan yang selanjutnya menjadi bagian dari IFS. Definisi III.10. Suatu IFS terdiri dari sebuah metric space yang komplet (X, d) dan himpunan sejumlah contraction mappings wn : X → X, yang memiliki faktor kontraksi sn , dengan n = 1, 2, . . . N . IFS dapat dilambangkan sebagai berikut: {X : wn , n = 1, 2, . . . N } dengan faktor kontraktifitasnya adalah s = M ax {sn : n = 1, 2, . . . N } (Barnsley, 1988). Atraktor yang dihasilkan oleh iterasi IFS terhadap himpunan titik dalam ruang metrik (X, d) dijelaskan dalam teorema berikut ini. Teorema III.1. Ambil {X; wn , n = 1, 2, . . . , N } sebagai IFS dengan faktor kontraktifitas s. Maka transformasi W : H (X) → H (X) yang didefinisikan sebagai W (B) =
N [
wn (B)
(III.2)
n=1
untuk semua B ∈ H (X) merupakan contraction mapping terhadap ruang metrik yang komplet (H (X) , h (d)) dengan faktor kontraktifitas s. Sehingga berlaku h (W (B) , W (C)) ≤ s.h (B, C)
(III.3)
untuk semua B, C ∈ H (X). Fixed point yang unik dari IFS tersebut adalah A ∈ H (X) yang memenuhi A = W (A) =
N [
wn (A)
(III.4)
n=1
dan diperoleh dari A = limn→∞ W on (B) untuk setiap B ∈ H (X) (Barnsley, 1988) Dalam teorema III.1 terlihat bahwa iterasi IFS terhadap himpunan B ∈ H (X) konvergen menghasilkan A. Definisi III.11. Fixed point A ∈ H (X) yang seperti dijelaskan dalam teorema III.1 disebut sebagai atraktor IFS
III–13
Gambar III.8. Atraktor (segitiga Sierpinski) yang dihasilkan oleh algoritma deterministik. Dari kiri atas ke kanan bawah berturut-turut adalah nilai awal dan iterasi ke-1, 2, . . . , 8
III.2.2
Membangkitkan Fraktal dengan Algoritma Deterministik
Algoritma deterministik menggunakan teorema III.1 secara langsung untuk membangkitkan Gambar fraktal. Algoritma ini melakukan iterasi dengan menghitung {An = W on (A0 )} dengan memilih A0 sebagai himpunan awal tertentu (berupa himpunan titik). Berikut adalah ilustrasi penggunaan algoritma deterministik dengan IFS yang dinyatakan sebagai {R; wn : n = 1, 2, 3}, dengan wn dinyatakan dalam persamaan: " # " #" # " # x1 0.5 0 x1 1 w1 = + x2 0 0.5 x2 1 " # " #" # " # x1 0.5 0 x1 1 w2 = + x2 0 0.5 x2 50 " # " #" # " # x1 0.5 0 x1 50 w3 = + x2 0 0.5 x2 50
(III.5)
Atraktor atau fraktal yang dihasilkan oleh algoritma deterministik untuk IFS di atas dapat dilihat dalam Gambar III.8
III–14
III.2.3
Membangkitkan Fraktal dengan Permainan Kaotik
Berbeda dengan algoritma sebelumnya, algoritma ini memerlukan himpunan probabilitas untuk menghasilkan atraktor berupa gambar fraktal. Definisi III.12. Suatu IFS dengan probabilitas terdiri dari sebuah IFS yang dinyatakan sebagai {X; w1 , w2 , . . . , wn } dan himpunan angka p1 , p2 , . . . , pN sedemikian sehingga p1 + p2 + p3 + · · · + pN = 1 dan pi > 0 untuk i = 1, 2, . . . , N dengan tiap-tiap nilai probabilitas pi bersesuaian dengan wi . IFS dengan probabilitas dilambangkan secara lengkap sebagai {X; w1 , w2 , . . . , wN ; p1 , p2 , . . . , pN } (Barnsley, 1988). Langkah-langkah dalam algoritma ini adalah sebagai berikut: ambil {X; w1 , w2 , . . . , wN } sebagai IFS dengan menetapkan probabilitas pi > 0 P pada wi untuk i = 1, 2, . . . , N , dengan N i=1 pi = 1. Kemudian pilih titik x0 ∈ X sebagai nilai awal . Untuk setiap langkah iterasi, xn dapat dinyatakan sebagai berikut: xn ∈ {w1 (xn − 1) , w2 (xn − 1) , . . . , wN (xn − 1)} untuk n = 1, 2, 3, . . . dengan probabilitas bagi kejadian (event) xn = wi (xn − 1) adalah pi . Iterasi tersebut akan menghasilkan deret {xn : n = 0, 1, 2, 3, . . .} ⊂ X. Jika probabilitas pemilihan himpunan transformasi {w1 , w2 , . . . , wN } terdistribusi secara uniform untuk setiap wi dan independen untuk setiap langkah iterasi, maka deret {xn }∞ n=0 akan konvergen ke atraktor dari IFS. Ilustrasi dari algoritma permainan kaotik dapat dilihat di Gambar III.9
Gambar III.9. Permainan kaotik dengan tiga transformasi
III–15
Gambar III.10. Atraktor (fraktal Sierpinski triangle) yang dihasilkan oleh algoritma permainan kaotik Atraktor (fraktal) yang dihasilkan oleh metode permainan kaotik, dengan IFS yang sama dengan yang telah digunakan pada contoh sebelumnya, dapat dilihat dalam Gambar III.10.
III.2.4
Penggunaan Ukuran dalam Fraktal
Dalam disertasi ini, konsep ukuran akan digunakan untuk menghitung distribusi titik, yang dihasilkan oleh skema permainan kaotik, dalam area tertentu. Jika proses pemilihan transformasi wi dari himpunan {w1 , w2 , . . . , wN } benar-benar acak 1 , maka titik-titik yang dihasilkan akan terdistribusi merata di dekat atraktor A. Fakta ini akan dipergunakan untuk memeriksa keacakan cipher blok yaitu dengan urutan langkah sebagai berikut • melakukan iterasi terhadap cipher blok, • menggunakan keluarannya untuk membangkitkan deret acak, • menggunakan deret acak tersebut sebagai input suatu skema permainan kaotik dengan IFS tertentu • menganalisis distribusi titik dari gambar fraktal yang dihasilkan Berikut ini adalah penjelasan konsep ukuran. Ambil {X; w1 , . . . , wN ; p1 , . . . , pN } sebagai IFS dengan probabilitas. Ambil A untuk melambangkan atraktor dari IFS 1
memiliki probabilitas yang sama (uniform)
iterasi sebelumnya
dan independen terhadap pilihan dalam
III–16
tersebut. Ukuran invarian (Invariant measure) dari IFS yang dilambangkan dengan µ menyatakan kepadatan gambar fraktal (atraktor) A untuk setiap himpunan bagian dari X. Sebagai contoh, µ (A) = 1 dan µ (φ) yang berarti kepadatan dari atraktor A adalah 1 dan kepadatan himpunan kosong adalah 0. Definisi III.13. Ambil X sebagai sebuah ruang (space). Ambil F untuk melambangkan himpunan yang beranggotakan himpunan-himpunan bagian dari X, sedemikian sehingga A, B ∈ F ⇒ A ∪ B ∈ F dan A ∈ F ⇒ X\A ∈ F Maka F disebut sebagai field (Barnsley, 1988). Berikut ini adalah definisi ukuran dalam suatu field Definisi III.14. Sebuah ukuran yang diterapkan pada sebuah field F adalah sebuah fungsi real non-negatif yang memetakan F ke himpunan bilangan real, µ : F → [0, ∞) ⊂ R, sedemikian sehingga apabila Ai ∈ F untuk i = 1, 2, 3, . . ., dengan Ai ∩ Aj = φ untuk i 6= j dan ∪∞ i=1 ∈ F, maka berlaku µ
∞ [
! Ai
=
∞ X
i=1
µ (Ai )
i=1
(Barnsley, 1988) Ambil B untuk melambangkan suatu lingkaran tertutup di X. Berikut ini adalah langkah-langkah untuk menghitung ”massa” dari lingkaran tersebut, µ (B). Jalankanlah algoritma permainan kaotik berdasarkan IFS-dengan-probabilitas tertentu sehingga menghasilkan deretan titik {xn }0∞ . Kemudian nyatakan N (B, n) = jumlah titik dalam himpunan {{x0 , x1 , x2 , . . . , xn } ∩ B} .
(III.6)
dengan n = 0, 1, 2, . . .. Kemudian, µ (B) dapat dinyatakan sebagai berikut : µ (B) = lim
n→∞
N (B, n) (n + 1)
(III.7)
”Massa” dari lingkaran B merupakan proporsi titik yang dihasilkan oleh algoritma permainan kaotik yang berada di dalam B.
BAB IV USULAN SKEMA PERMAINAN KAOTIK UNTUK ANALISIS CIPHER BLOK Bab ini membahas usulan skema permainan kaotik yang akan digunakan dalam bab selanjutnya untuk melakukan analisis keacakan dan kriptanalisis cipher blok. Subbab IV.1 akan menjelaskan definisi deret acak ideal. Konsep deret acak ideal ini akan dipergunakan sebagai referensi untuk menghitung bias suatu deret acak tertentu terhadap deret acak ideal. Subbab IV.2 membahas penerapan kerangka sistem dinamik dalam analisis cipher blok. Penggunaan kerangka ini bertujuan untuk memungkinkan penggunaan teknik-teknik analisis sistem dinamik dalam analisis cipher blok. Berikutnya, teknik analisis simbolik dinamik akan digunakan untuk membangkitkan deret acak. Perbandingan keacakan cipher blok selanjutnya dapat dilakukan dengan melihat bias deret acak yang dibangkitkannya terhadap deret acak ideal. Subbab IV.3 membahas usulan skema permainan kaotik baru sebagai perangkat analisis keacakan cipher blok. Skema permainan kaotik selanjutnya akan membangkitkan atraktor dengan menggunakan deret acak sebagai input.
IV.1
Definisi Deret Acak Ideal
Anggap terdapat suatu deret acak s = l0 l1 l2 . . . lN , yaitu deret acak yang memiliki jumlah suku N + 1. Setiap suku menyatakan simbol tertentu dari sejumlah M alternatif simbol atau dapat kita nyatakan ln ∈ {α1 , α2 , . . . αM } untuk n = 0, 1, 2, . . . , N . Probabilitas kemunculan tiap simbol dilambangkan dengan {pα1 , pα2 , . . . , pαM }. Ambil ∆K = δ1 δ2 . . . δK untuk menyatakan deret dengan jumlah suku K < N , yang memiliki alternatif simbol yang sama dengan sebelumnya, δk ∈ {α1 , α2 , . . . αM } untuk k = 1, . . . , K. Ambil nilai indeks i tertentu dan tunjuk subderet s dengan panjang K suku yang dimulai dari indeks ke-i tersebut sehingga kita memperoleh subderet berikut: s = l0 l1 . . . li l(i+1) . . . l(i+K−2) l(i+K−1) . . . l(N −1) lN {z } | (i+K−1)
si
(i+K−1)
Untuk beberapa nilai indeks i, mungkin terjadi si akan mendefinisikan deret acak ideal:
IV–1
= ∆K . Berikutnya kita
IV–2
Definisi IV.1. Ambil s = l0 l1 l2 . . . lN sebagai suatu deret dengan ln adalah suku ke n dengan ln ∈ {α1 , α2 , . . . αM } untuk n = 0, 1, 2, . . . , N . Deret s tersebut disebut deret acak ideal (dilambangkan dengan sideal ) jika untuk setiap n, seluruh simbol {α1 , α2 , . . . αM } memiliki probabilitas yang sama (equally probable) untuk muncul dalam ln dan kemunculan simbol dalam ln1 independen dari kemunculan simbol dalam ln2 untuk semua n1 6= n2 . Karena probabilitas kemunculan simbol sama untuk sideal , maka pα1 = pα2 = . . . = pαM = M1 Kemudian kita nyatakan permasalahan berikut untuk sideal : Untuk setiap nilai indeks i yang dipilih secara acak, berapa probabili(i+K−1) tas kejadian (event) sideal i = ∆K atau dengan kata lain berapa probabilitas munculnya simbol tertentu sepanjang K dalam deret sideal dimulai dari indeks ke-i yang dipilih secara acak? Untuk kasus sideal , karena indeks ke-i dipilih secara acak, maka probabiltas munculnya δ1 dalam li adalah pδ1 atau P r {li = δ1 } = pδ1 . Untuk kasus sideal , pα1 = pα2 = . . . = pαM = M1 , sehingga P r {li = δ1 } = pδ1 = M1 . Selanjutnya, berdasarkan independensi kemunculan simbol dalam suku yang berbeda dari sideal , maka probabiltas munculnya δ2 dalam li+1 adalah p2 = M1 dan juga 2 berdasarkan independensi kita memperoleh P r {li li+1 = δ1 δ2 } = M1 . Demikian seterusnya hingga indeks ke-(i + K − 1). Maka untuk setiap nilai indeks i yang dipilih secara acak, kita mendapatkan simbol ∆K dalam n probabilitas munculnya o K K (i+K−1) (i+K−1) = ∆K = M1 . sideal i adalah M1 atau P r sideal i Berikut ini adalah lemma mengenai nilai probabilitas kemunculan tiap kombinasi simbol dengan panjang k dalam deret acak ideal sideal Lemma 1. Ambil sideal = l0 . . . lN sebagai deret acak ideal dengan panjang N + 1 seperti yang didefinisikan dalam Definisi IV.1 dan ambil ∆K = δ1 . . . δ K untuk melambangkan deret dengan panjang K ≤ (N + 1). Probabilitas munculnya sub(i+K−1) deret ∆K dalam sideal i dengan indeks-i dipilih secara acak adalah: n o 1 K (i+K−1) K P r sideal i = =∆ M
(IV.1)
Bukti. Sudah jelas berdasarkan penjelasan sebelumnya Berdasarkan lemma 1 di atas, jika kita memilih indeks i secara acak, maka probaK bilitas munculnya ∆K dalam deret sideal dimulai dari indeks ke-i adalah M1 .
IV–3
Definisi IV.2. Ambil s = l0 l1 . . . lN untuk melambangkan deret acak dengan ln ∈ {α1 , α2 , . . . αM } untuk n = 0, 1, 2, . . . , N . Frekuensi relatif kemunculan deret tertentu ∆K dalam suatu deret acak s adalah frekuensi harapan kemunculan ∆K di sepanjang deret acak s dibagi dengan jumlah total subderet dengan panjang K dalam deret s. Berikut ini adalah teorema mengenai frekuensi relatif kemunculan simbol tertentu dalam deret acak sideal Teorema IV.1. Frekuensi relatif kemunculan simbol tertentu ∆K dalam deret acak K ideal sideal yang didefinisikan dalam definisi IV.1 adalah M1 . Bukti. Untuk deret acak sideal = l0 l1 . . . lN , terdapat sejumlah (N − K + 2) alternatif posisi untuk kemunculan deret tertentu ∆K . Alternatif posisi ini merupakan alternatif nilai indeks i yaitu i = 0, 1, . . . , (N − K + 1), yang merupakan indeks di mana deret ∆K dimulai. Karena terdapat (N − K + 2) alternatif posisi dan karena, berdasarkan Lemma 1 untuk tiap alternatif posisi yang dipilih secara acak, probaK bilitas kemunculan ∆K adalah M1 , maka frekuensi harapan kemunculan ∆K K dalam (N − K + 2) alternatif posisi yang acak adalah (N − K + 2) × M1 . Sehingga kita dapatkan frekuensi relatif kemunculan deret ∆K dalam deret acak sideal adalah K 1 (N − K + 2) × (1/M )K = (N − K + 2) M
Kita dapat menghitung frekuensi relatif aktual kemunculan deret ∆K di sepanjang deret Θ tertentu. Berikut ini adalah definisi frekuensi relatif aktual kemunculan subderet ∆K di sepanjang deret Θ. Definisi IV.3. Ambil Θ = θ0 , θ1 . . . θN untuk melambangkan suatu deret tertentu yang merupakan realisasi dari deret acak s seperti yang dijelaskan di bagian sebelumnya dan ∆K = δ1 δ2 . . . δK untuk melambangkan deret tertentu dengan panK jang K yang memenuhi NM+1 << 1. Jumlah kemunculan deret ∆K dalam deret Θ dilambangkan dengan ∆K [Θ] . Frekuensi relatif aktual kemunculan deret tertentu ∆k dalam deret tertentu Θ adalah K ∆ [Θ] F raktual kemunculan ∆K dalam Θ = (IV.2) N −K +2
IV–4
Berikut ini adalah definisi penyimpangan atau bias frekuensi relatif aktual kemunculan deret tertentu ∆K dalam suatu deret tertentu Θ terhadap frekuensi relatif kemunculan ∆K dalam deret acak ideal sideal . Definisi IV.4. Bias frekuensi relatif aktual kemunculan deret tertentu ∆K = δ1 δ2 . . . δK dalam deret Θ = θ0 , θ1 . . . θN yang merupakan realisasi dari deret acak s didefinisikan dalam persamaan berikut: bias frekuensi relatif aktual kemunculan ∆K dalam Θ = F raktual kemunculan ∆K dalam Θ − F r kemunculan ∆K dalam sideal (IV.3) dengan panjang dari deret ∆K adalah K yang memenuhi
MK N +1
<< 1,
Berdasarkan Teorema IV.1 maka kita dapatkan bias frekuensi relatif aktual kemunculan ∆K dalam Θ = K 1 K F raktual kemunculan ∆ dalam Θ − M
(IV.4)
Analisis terhadap deret acak dalam bagian-bagian selanjutnya akan merujuk pada konsep-konsep yang dijelaskan pada bagian ini.
IV.2
Kerangka Sistem Dinamik untuk Analisis Keacakan
Analisis keacakan merupakan hal yang penting dalam ranah kriptografi karena menjadi satu pendekatan untuk menguji kekuatan atau keamanan suatu algoritma enkripsi. Analisis keacakan ini banyak digunakan dalam proses desain dan uji keamanan cipher alir. Cipher alir bekerja dengan cara membangkitkan deretan bit acak (random bit sequence) dan kemudian menggunakannya untuk mengacak teks-plain dengan menggunakan fungsi sederhana (misalnya exclusive-or atau penjumlahan modulo-2). Analisis keacakan dapat digunakan untuk menguji kekuatan cipher alir dengan cara mengukur kualitas deretan bit acak yang dihasilkannya (Katos, 2005). Dalam konteks cipher alir dan pembangkit bilangan acak pseudo (PRNG), analisis keacakan bertujuan menguji apakah deretan bit yang dihasilkan dapat dibedakan secara statistik dengan deret yang dihasilkan oleh pembangkit bilangan acak ideal (Menezes dkk., 1996). Dalam konteks cipher blok, analisis keacakan digunakan secara lebih khusus untuk mengidentifikasi adanya keteraturan dalam algoritma cipher blok tersebut. Katos
IV–5
(2005) melakukan analisis keacakan terhadap cipher blok dengan cara mengubah 1 bit input input cipher blok secara sistematis. Kegagalan sebuah cipher blok dalam uji ini menandakan terdapatnya hubungan tertentu antara masukan dan keluaran. Namun demikian, metode yang diusulkan oleh Katos tersebut tidak dapat mengungkapkan bagaimana bentuk hubungan tersebut. Hernandez dkk. (2001) menyatakan bahwa uji keacakan terhadap cipher blok tidak dapat dilakukan dengan menggunakan data input yang acak (high-entropy-feeding). Paper tersebut mengusulkan untuk melakukan low-entropy-feeding dengan cara memberikan nilai yang tetap untuk beberapa bit dari blok masukan cipher. Paper tersebut juga mengusulkan algoritma genetik untuk memilih bit-bit yang akan dijaga tetap. Hernández, Sierra, Ribagorda, Ramos, dan Mex-Perera juga telah menganalisis keacakan TEA dan berhasil membedakan algoritma TEA (Tiny Encryption Algorithm), yang tereduksi jumlah rondenya, dari permutasi acak. Bab IV.2 ini akan membahas kerangka analisis keacakan cipher blok berdasarkan permainan kaotik yaitu dengan memandangnya sebagai bagian dari sistem dinamik yang direpresentasikan dalam persamaan diferens waktu diskrit. Kerangka yang dibangun dalam bab ini akan menjadi dasar bagi penggunaan skema permainan kaotik untuk analisis cipher blok. Salah satu tujuan disertasi ini adalah mengembangkan metode kriptanalisis yang baru sehingga metode analisis keacakan juga dikembangkan dalam konteks tersebut. Untuk keperluan kriptanalisis, analisis keacakan biasanya didahului dengan analisis awal terhadap struktur serta elemen pembangun cipher blok untuk untuk menemukan kelemahannya. Hasil analisis awal ini selanjutnya digunakan untuk membangun metode yang dapat mengidentifikasi penyimpangan perilaku cipher blok dari model permutasi acak (Stinson, 2002). Upaya identifikasi subkunci dilakukan berdasarkan hasil analisis penyimpangan yang telah dilakukan sebelumnya. Berikut ini adalah kerangka analisis keacakan yang diusulkan dalam Disertasi ini: 1. Cipher blok ditempatkan sebagai fungsi pemetaan dalam sebuah sistem dinamik. Sistem dinamik tersebut direpresentasikan dalam persamaan diferens waktu diskrit. Dalam kerangka ini, bekerjanya sistem dinamik identik dengan iterasi terhadap cipher blok. Trayektori atau orbit dari sistem ini identik dengan hasil iterasi cipher blok. Tujuan penggunaan kerangka ini adalah agar analisis terhadap cipher blok dapat dilakukan dengan menggunakan metodologi yang dikembangkan dalam ranah sistem dinamik.
IV–6
2. Orbit dari sistem dianlisis dengna menggunakan metode dinamika simbolik (Peitgen dkk., 1992) (Gulick, 1992). Metode ini membagi range sistem menjadi n bagian dan mengamati perpindahan orbit dari bagian satu ke bagian yang lain. Definisi IV.5. (Kocarev dkk., 1998), (Gulick, 1992) Persamaan berikut ini merupakan representasi matematis dari sistem dinamik waktu diskrit: x (n + 1) = fk (x (n))
(IV.5)
dengan x ∈ Rm dan fk : S ∈ Rm → Rm merupakan fungsi nonlinear dengan k menyatakan parameter fungsi tersebut. S merupakan domain fungsi fk . Deretan x, yaitu {x (0) , x (1) , x (2) , . . .} = {x (0) , fk (x (0)) , fk (fk (x (0))) , . . .} disebut sebagai orbit dari x. Kocarev menggunakan pemetaan kaotik dalam persamaan diferens tersebut untuk menghasilkan dinamika kaotik diskrit (Kocarev dkk., 1998). Kocarev menjelaskan bahwa iterasi terhadap cipher blok dapat dimodelkan dalam persamaan diferens waktu diskrit dan jika domainnya diperluas menjadi domain kontinyu maka sistem yang dihasilkan berperilaku kaotik sehingga cipher blok yang digunakan dapat dianggap sebagai pemetaan kaotik. Persamaan diferens merupakan model dinamika sistem kaotik yang banyak digunakan dalam desain cipher kaotik dijital (Jakimoski dan Kocarev, 2001a,b; Kocarev dan Szczepanski, 2004; Kocarev dkk., 1998; Amigo dkk., 2007; Li dan Chen, 2004). Persamaan IV.5 merupakan persamaan diferens orde-m. Analisis keacakan terhadap cipher blok akan menggunakan persamaan diferens orde-1 dengan fk merupakan fungsi dengan parameter k yang memetakan domain S ke dirinya sendiri. Berdasarkan kerangka analisis yang telah dinyatakan sebelumnya, cipher blok akan ditempatkan sebagai fungsi pemetaan. Dalam kasus ini, fk merupakan fungsi enkripsi dengan kunci k atau fk = Ek . Dengan p adalah teks-plain, c adalah tekscipher, n = 0, 1, . . ., dan p(0) adalah kondisi mula sistem, kita dapat menyatakan kembali persamaan IV.5 sebagai berikut: p (i + 1) = Ek (p (i))
(IV.6)
c (i) = p (i + 1) dengan i menyatakan indeks iterasi, Ek merupakan fungsi pemetaan enkripsi dengan parameter k, p melambangkan teks-plain, c melambangkan teks-cipher, p ∈
IV–7
{0, 1}l dan c ∈ {0, 1}l dengan l merupakan bilangan integer yang menyatakan panjang bilangan biner p dan c. Merujuk kembali pada definisi IV.5, fungsi fk merupakan fungsi nonlinear. Dengan mengetahui persamaan matematis fk sebagai fungsi dari x, kita dapat membangkitkan grafik fk (x) untuk semua x ∈ S ∈ R. Hal ini dapat kita lakukan dengan mudah terutama jika fk (x) merupakan fungsi yang mulus atau setidaknya kontinyu. Untuk kasus Ek hal ini menjadi tidak mudah, mengingat karakteristik cipher blok yang menyerupai dengan model permutasi acak sehingga nilai p1 yang berdekatan dengan p2 tidak mengimplikasikan Ek (p1 ) yang berdekatan dengan Ek (p2 ). Agar iterasi terhadap cipher blok dapat dipahami dengan lebih baik kita akan membahas lebih dahulu iterasi terhadap pemetaan kaotik.
IV.2.1
Penerapan Kerangka Analisis Sistem Dinamik
Subbab ini akan membahas penerapan usulan kerangka analisis sistem dinamik terhadap cipher blok. Untuk memperjelas pembahasan, bab ini juga akan menjelaskan iterasi terhadap fungsi kuadratik yang telah dikenal sebagai sebuah pemetaan kaotik.
IV.2.1.1
Iterasi Fungsi Kuadratik
Jika iterasi terhadap suatu fungsi pemetaan menghasilkan dinamika kaotik maka fungsi pemetaan tersebut dapat disebut sebagai pemetaan kaotik. Subbab ini akan menjelaskan iterasi terhadap fungsi pemetaan berupa fungsi kuadratik. Fungsi kuadratik merupakan salah satu fungsi dasar yang banyak dibahas dalam berbagai literatur mengenai dinamika kaotik. Fungsi ini dapat bersifat asimtotik, periodik, maupun kaotik bergantung pada nilai parameternya (Peitgen dkk., 1992) (Barnsley, 1988). Fungsi kuadratik secara umum dinyatakan sebagai Qµ (x) = µx − µx2 dengan domain SQ = {x | 0 ≤ x ≤ 1, x ∈ R}. Agar Qµ memetakan domain SQ ke SQ , maka 0 ≤ µ ≤ 4.
IV.2.1.2
Fungsi Kuadratik dengan µ = 3
Iterasi terhadap fungsi kuadratik dapat dinyatakn dalam persamaan berikut ini: x(n + 1) = µxn − µxn 2
(IV.7)
IV–8
Untuk nilai 0 ≤ µ ≤ 3, Qµ memiliki satu buah titik tetap penarik dan satu titik √ penarik dua siklus untuk 3 < µ ≤ 1+ 6 (Gulick, 1992). Jadi, secara teoritis untuk µ = 3 orbit sistem akan konvergen menuju siklus dua titik. Ambil x(0) = 0.1 dan µ = 3, maka berdasarkan persamaan IV.7, kita mendapatkan orbit dari x sebagai berikut: 0.1000, 0.2700, 0.5913, 0.7250, 0.5981, 0.7211, 0.6033, 0.7180, 0.6075, . . . Gambar IV.1 berikut ini adalah grafik Qµ (x) terhadap x dan orbit x untuk µ = 3 : 1
0.9
0.8
0.7
Qu(x)
0.6
0.5
0.4
0.3
0.2
0.1
0
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
x
Gambar IV.1. Analisis grafik orbit x untuk µ = 3
IV.2.1.3
Fungsi Kuadratik dengan µ = 4
Untuk x(0) = 0.1 dan µ = 4, orbit dari x adalah: 0.1000, 0.3600, 0.9216, 0.2890, 0.8219, 0.5854, 0.9708, 0.1133, 0.4020, . . . Untuk µ = 4, orbit-x tidak periodik, tidak konvergen ke satu titik tertentu dan tampak memenuhi seluruh domainnya.
IV.2.1.4
Iterasi Cipher Blok Berstruktur SPN
Cipher blok yang akan dianalisis dalam disertasi ini memiliki struktur jaringan subtitusi dan permutasi (SPN) seperti yang dijelaskan di Lampiran B. Skema ini merupakan bentuk dasar dari SPN yang memproses blok data dalam empat ronde. Setiap ronde mengimplementasikan tiga operasi dasar, yaitu (1) subtitusi, yaitu penukaran
IV–9
1
0.9
0.8
0.7
Qu(x)
0.6
0.5
0.4
0.3
0.2
0.1
0
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
x
Gambar IV.2. Analisis grafik orbit x untuk µ = 4 nilai sekelompok bit dengan kelompok bit lain, (2) permutasi, yaitu penukaran posisi bit dan (3) pengacakan kunci, yaitu melakukan perubahan terhadap bit dengan menggunakan kunci enkripsi (Heys, 2001; Stinson, 2002). Cipher blok tersebut memiliki blok data berukuran 16-bit dan kunci berukuran 32-bit. Seluruh parameter contoh cipher blok yang dipergunakan dalam disertasi ini merujuk dari (Stinson, 2002) (lihat Lampiran B). IV.2.1.4.1
Fungsi Ek Terhadap p
Karena memiliki ukuran blok sebesar 16-bit maka domain cipher ini dapat dinyatakan sebagai himpunan SE = {0, 1, 2, . . . , 216 − 1}. Fungsi enkripsi dengan kunci k kita lambangkan dengan Ek . Karena panjang kunci adalah 32-bit, maka himpunan semua kunci dapat dinyatakan dalam K = {0, 1, 2, . . . , 232 − 1}. Untuk setiap nilai k, Ek merupakan fungsi permutasi yang memetakan himpunan SE ke dirinya sendiri. Berdasarkan karakteristik dasar dari cipher blok maka setiap pemilihan kunci k merupakan proses pemilihan fungsi permutasi secara acak, . Untuk kasus dalam disertasi ini, panjang blok adalah 16-bit, sehingga diperlukan 216 proses enkripsi untuk mendapatkan seluruh pasangan teks-plain dan teks-cipher. Hal ini masih feasible untuk dilakukan. Namun, berdasarkan penjelasan pada bagian II.1.3.4, untuk cipher blok yang sesungguhnya, panjang blok dipilih
IV–10
sedemikian rupa sehingga pencarian seluruh pasangan teks-plain dan teks-cipher untuk kunci tertentu menjadi tidak feasible. Grafik Ek (p) terhadap p, untuk k = 11010111001110101000110101101110, dengan hanya mengambil sebagian sampel p dari himpunan SE {0, 1, 2, . . . , 216 − 1} ditampilkan dalam Gambar IV.3.
=
4
x 10
6
5
Ek(p)
4
3
2
1
0
0
1
2
3
4
5
p
6 4
x 10
Gambar IV.3. Grafik Ek (p) terhadap p Dari Gambar IV.3 terlihat bahwa untuk nilai p1 dan p2 yang berdekatan, fungsi pemetaan enkripsi menghasilkan Ek (p1 ) dan Ek (p2 ) yang tidak selalu berdekatan. Dapat diperlihatkan pula bahwa setiap pilihan nilai kunci k yang berbeda akan menghasilkan fungsi permutasi Ek secara acak. IV.2.1.4.2
Orbit Iterasi Cipher Blok
Nilai awal iterasi ini adalah p (0) = 0110111001010001. Sistem dinamik diskrit yang digunakan dalam iterasi ini dinyatakan dalam persamaan IV.2.1.4. Iterasi ini menghasilkan deret berikut ini: p (0) = 0110111001010001 p (1) = 0001101100011101 p (2) = 0101111010000100 p (3) = 1010110001000110
IV–11
p (4) = 0010111001010011 .. . p (49) = 0010011110101101 Jika kita menyatakan kembali orbit p (n) dari biner ke bentuk desimal yang dilambangkan dengan pdec (n) maka orbit pdec (n) untuk n = 0, 1, 2, . . . , 49 beserta plot grafik Ek (p) terhadap pdec untuk beberapa sampel dari domain Ek diperlihatkan dalam Gambar IV.4. 4
x 10
6
5
Ek(p)
4
3
2
1
0
0
1
2
3
4
p
5
6 4
x 10
Gambar IV.4. Orbit pdec dan grafik Ek (p) terhadap pdec
IV.2.2
Analisis Simbolik terhadap Fungsi Kuadratik
Analisis keacakan dalam bab ini dilakukan terhadap suatu deret s = l0 l1 l2 . . . dengan setiap komponen deret memiliki m alternatif simbol. Misalkan, untuk m = 2 maka ln memiliki alternatif simbol 0 dan 1, atau kita dapat juga menggunakan simbol lain, misalnya L dan R, sehingga deret s misalnya dinyatakan sebagai berikut: s = LRRRLRRRRRLLLRLRL . . .. Setiap deret bilangan yang dihasilkan oleh sistem dinamik waktu diskrit dalam bagian sebelumnya akan dipetakan menjadi deret s. Selanjutnya, analisis keacakan terhadap keluaran dari sistem dinamik diskrit akan dilakukan dengan cara menganalisis deret s tersebut. Dinamika dari deret s disebut sebagai dinamika simbolik dan lazim digunakan sebagai perangkat analisis dinamika kaotik (Gulick, 1992; Peitgen dkk., 1992).
IV–12
IV.2.2.1
Analisis Keacakan Fungsi Kuadratik dengan µ = 3
Analisis ini akan menggunakan dua alternatif simbol L dan R. Analisis akan dilakukan terhadap hasil iterasi fungsi kuadratik dari bagian IV.2.1.1. Deret sQ dibentuk dengan cara membagi domain x menjadi dua bagian dan membentuk deret dengan persamaan berikut berikut: ( ln =
L jika 0 ≤ x (n) < 0.5 R jika 0.5 ≤ x (n) ≤ 1
(IV.8)
Berikut ini adalah hasil iterasi hingga n = 1000: sQ3 = LLRRRRRRRRRRRRRRRRRR . . . RRRRR Berdasarkan pengamatan terhadap Gambar IV.1, terlihat bahwa orbit x akan terus berada di setengah bagian kanan domain x setelah iterasi ke dua. Hal ini juga terlihat dari deret sQ3 di atas. Iterasi terhadap Q3 merupakan contoh sistem dinamik diskrit yang tidak menghasilkan deret sQ3 yang bersifat acak. Pengujian satu-suku 1 terhadap sQ3 dapat dilihat dalam Tabel IV.1. Berikut adalahnTabelofrekuensi o n relatif setiap kemungkinan kombinasi simbol dalam satu suku, fr L1sQ dan fr R1sQ . 3 3 Probabilitas deret acak ideal sideal bernilai sama untuk dua alternatif kombinasi tersebut, yaitu 12 . Simbol L R
fr 0.002 0.998
Probabilitas ideal 0.5 0.5
bias -0.4980 0.4980
Tabel IV.1. Pengujian keacakan satu simbol untuk Q3
IV.2.2.2
Analisis Keacakan Fungsi Kuadratik dengan µ = 4
Untuk nilai µ = 4 analisis keacakan terhadap fungsi kuadratik dengan menggunakan dua alternatif simbol, m = 2 akan menunjukkan hasil yang sangat berbeda dengan jika menggunakan tiga alternatif simbol, m = 3 (Peitgen dkk., 1992). Berbeda dengan kasus Q3 , iterasi terhadap Q4 menghasilkan deret bilangan x (n) yang tidak periodik dan tidak konvergen ke satu titik sebagaimana ditunjukkan pada Gambar IV.2. 1
biasanya disebut sebagai Mono-symbol test atau mono-bit test merupakan pengujian keacakan yang dilakukan dengan cara menganalisis jumlah munculnya simbol dalam sebuah suku dalam suatu deret. Kita menggunakna kata ’suku’ untuk membedakannya dari simbol
IV–13
Deret dengan dua alternatif simbol dibangkitkan berdasarkan persamaan IV.8. Sedangkan deret dengan tiga alternatif simbol dibangkitkan dengan cara membagi domain fungsi kuadratik menjadi tiga bagian berdasarkan persamaan berikut 1 L jika 0 ≤ x (n) < 3 ln = M jika 13 ≤ x (n) < 32 R jika 23 ≤ x (n) ≤ 1
(IV.9)
1. Analisis dengan dua alternatif simbol (m = 2) Iterasi terhadap fungsi kuadrat dengan µ = 4 menghasilkan sQ4 sebagai berikut sQ4 = LLRLRRRLLRLRRLLLLLLRRRRLLRLLRRLRLR . . . Pengujian satu-suku terhadap sQ4 dapat dilihat dalam Tabel IV.2. Kita juga dapat melakukan pengujian dua-suku dan tiga-suku terhadap deret tersebut. Hasil pengujian diperlihatkan dalam Tabel IV.3 dan Tabel IV.4. Simbol L R
fr 0.496 0.504
Probabilitas ideal 0.5 0.5
bias -0.0040 0.0040
Tabel IV.2. Pengujian keacakan satu suku untuk Q4 dengan m = 2 Simbol LL LR RL RR
fr 0.2292 0.2663 0.2663 0.2382
Probabilitas ideal 0.25 0.25 0.25 0.25
bias -0.0208 0.0163 0.0163 -0.0118
Tabel IV.3. Pengujian keacakan dua-suku untuk Q4 dengan m = 2 Simbol LLL LLR LRL LRR RLL RLR RRL RRR
fr 0.0982 0.1303 0.1413 0.1253 0.1303 0.1363 0.1251 0.1132
Probabilitas ideal 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125
bias -0.0268 0.0053 0.0163 0.0003 0.0053 0.0113 0.0001 -0.0118
Tabel IV.4. Pegujian keacakan tiga-suku untuk Q4 dengan m = 2
IV–14
Karena frekuensi relatif untuk beberapa pengujian terhadap Q4 mendekati probabilitas idealnya, maka dapat dikatakan sistem dinamik diskrit yang dibentuk oleh Q4 dapat membangkitkan deret yang menyerupai deret acak. 2. Analisis dengan tiga alternatif simbol (m = 3) Pada bagian ini, pengujian akan dilakukan dengan menggunakan tiga alternatif simbol. Probabilitas ideal adalah 31 . Berikut adalah deret yang dihasilkan sQ4 = RMRLRMRLMRLMRLLLLLLRRMRLMRLLMRLRMR . . . Tabel IV.5 menampilkan hasil pengujian dengan satu suku: simbol L M R
fr 0.3990 0.2158 0.3852
probabilitas ideal 1/3 1/3 1/3
bias 0.0657 -0.1175 0.0519
Tabel IV.5. Tabel pengujian satu-suku untuk sQ4 dengan m = 3 Untuk pengujian dua-suku, probabilitas ideal adalah menampilkan hasil pengujian dengan dua suku: simbol LL LM LR ML MM MR RL RM RR
fr 0.2038 0.1070 0.0882 0 0 0.2156 0.1952 0.1088 0.0812
probabilitas ideal 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1/9
1 2 . 3
Tabel IV.6
bias 0.0927 -0.0041 -0.0229 -0.1111 -0.1111 0.1045 0.0841 -0.0023 -0.0299
Tabel IV.6. Tabel pengujian dua-suku untuk sQ4 dengan m = 3 Tampak bahwa kombinasi simbol ML dan MM memiliki frekuensi relatif 0. Analisis dengan tiga alternatif simbol menghasilkan bias yang relatif lebih besar daripada dengan dua alternatif simbol. Ini menunjukkan bahwa keacakan suatu deret yang dihasilkan oleh suatu sistem dinamik sangat bergantung pada metode pembangkitan deret tersebut. Satu metode mungkin menghasilkan deret s1 yang acak, sedangkan metode lain mungkin menghasilkan deret s2 yang menunjukkan keteraturan.
IV–15
IV.2.3
Analisis Simbolik terhadap Cipher Blok
Analisis dilakukan terhadap hasil iterasi terhadap fungsi enkripsi Ek dengan 4 ronde (lihat bagian IV.2.1.4.2). Analisis akan menggunakan dua alternatif simbol, m = 2. Deret sE = k1 k2 . . . dibentuk dengan cara membagi domain pdec menjadi dua bagian dengan persamaan berikut: ( kn =
L jika 0 ≤ pdec (n) ≤ 215 − 1 R jika 215 ≤ pdec (n) ≤ 216
(IV.10)
Pembagian yang dinyatakan dalam persamaan IV.10 identik dengan membagi domain p (n) (yang berbentuk biner) menjadi dua kelompok berdasarkan nilai bit paling kiri (the most significant bit). Jadi kita dapat menyatakan kembali persamaan IV.10 sebagai berikut: ( kn =
L jika msb p (n) = 0 R jika msb p (n) = 1
(IV.11)
Iterasi dilakukan dengan nilai awal: p (0) = 0110111001010001 dan kunci K = 11010111001110101000110101101110 Iterasi dilakukan hingga n = 10000 menghasilkan deret sEk berikut ini sEk = LLLRLRLRLLRLLLRRLLRLR . . . Bagian ini hanya akan melakukan pengujian keacakan tiga-suku terhadap deret tersebut. Hasil pengujian dinyatakan dalam Tabel IV.7. Dengan kolom bias menyatakan selisih antara frekuensi relatif dengan probabilitas ideal. Berdasarkan Tabel IV.7 di atas, frekuensi relatif yang dihasilkan memiliki bias yang relatif kecil. Hal ini menunjukkan bahwa iterasi terhadap fungsi enkripsi Ek dengan 4-ronde mampu menghasilkan deret yang mendekati deret acak. Khusus untuk iterasi terhadap cipher blok, pembagian domain p menjadi dua bagian dapat dilakukan dengan memilih bit manapun dari p (tidak harus MSB). Jadi, analisis keacakan dapat dilakukan dengan mengambil bit manapun dari p. Dengan langkah-langkah analisis yang sama, dapat ditunjukkan bahwa deret s yang dihasilkan menyerupai deret acak.
IV–16
Simbol LLL LLR LRL LRR RLL RLR RRL RRR
fr 0.1375 0.1267 0.1214 0.1251 0.1265 0.1198 0.1248 0.1182
Probabilitas ideal 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125
bias 0.0125 0.0017 -0.0036 0.0001 0.0015 -0.0052 -0.0002 -0.0068
Tabel IV.7. Pengujian keacakan tiga simbol untuk Ek dengan jumlah ronde Nr = 4
IV.2.4
Perbandingan Keacakan Cipher Blok untuk Jumlah Ronde yang Berbeda
Dalam subbab ini, kita akan membandingkan tingkat keacakan keluaran cipher blok untuk jumlah ronde (Nr ) yang berbeda dengan jumlah iterasi, kunci dan nilai awal yang sama dengan yang digunakan pada bagian sebelumnya. Hasil pengujian untuk Nr = 1, 2 dan 3 dapat dilihat dalam Tabel IV.8, IV.9 dan IV.10. Sedangkan hasil pengujian untuk Nr = 4 dapat dilihat pada Tabel IV.7. Besar bias dinyatakan sebagai root-mean-square dari bias seluruh kombinasi yang mungkin muncul. Jika bias seluruh kombinasi dinyatakan sebagai vektor, maka besar bias dinyatakan sebagai berikut v u u ~ t bias =
~ T · bias ~ bias ~ jumlah komponen bias
(IV.12)
Berdasarkan persamaan IV.12 kita memperoleh |biasNr =1 | = 0.0867, |biasNr =2 | = 0.0170, |biasNr =3 | = 0.0053 dan |biasNr =4 | = 0.0055. Dalam kasus ini terlihat bahwa cipher yang memiliki jumlah ronde yang semakin besar menghasilkan besar bias yang semakin kecil sehingga semakin mendekati deret acak ideal. Namun untuk jumlah ronde 3 dan 4 perubahan besar bias tidak siginifikan. Sehingga dapat kita simpulkan bahwa analisis keacakan dengan dua alternatif simbol (m = 2) yang di bahas di sini hanya dapat membedakan tingkat keacakan deret yang dibangkitkan oleh cipher blok dengan jumlah ronde 1, 2, dan 3, namun tidak dapat membedakan tingkat keacakan antara jumlah ronde 3 dan 4.
Simbol LLL LLR LRL LRR RLL RLR RRL RRR
Prosentase Frekuensi 0.3331 0.1110 0.1110 0.1112 0.1112 0.1110 0.1112 0
Probabilitas Harapan 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125
Bias 0.2081 -0.0140 -0.0140 -0.0140 -0.0140 -0.0140 -0.0140 -0.1250
Tabel IV.8. Pengujian keacakan tiga suku untuk Ek dengan jumlah ronde Nr = 1 Simbol LLL LLR LRL LRR RLL RLR RRL RRR
Prosentase Frekuensi 0.1084 0.1349 0.1517 0.1198 0.1347 0.1367 0.1198 0.0940
Probabilitas Harapan 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125
Bias -0.0166 0.0099 0.0267 -0.0052 0.0097 0.0117 -0.0052 -0.0310
Tabel IV.9. Pengujian keacakan tiga suku untuk Ek dengan jumlah ronde Nr = 2 Simbol LLL LLR LRL LRR RLL RLR RRL RRR
Prosentase Frekuensi 0.1110 0.1265 0.1265 0.1269 0.1265 0.1267 0.1269 0.1293
Probabilitas Harapan 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125
Bias -0.0140 0.0015 0.0015 0.0019 0.0015 0.0017 0.0019 0.0043
Tabel IV.10. Pengujian keacakan tiga suku untuk Ek dengan jumlah ronde Nr = 3
IV.3
Konstruksi Skema Permainan Kaotik
Dalam disertasi ini, skema permainan kaotik akan digunakan sebagai perangkat analisis cipher blok. Cipher blok akan membangkitkan deret acak yang kemudian menjadi input . Metode ini diharapkan dapat menampakkan keteraturan dari cipher blok dan membedakannya dari fungsi permutasi acak. Selanjutnya, metode ini juga akan digunakan untuk membangun metode kriptanalisis terhadap cipher blok.
IV–18
Bagian ini akan menjelaskan konsep-konsep terpenting dari fraktal dan skema permainan kaotik yang akan dipergunakan untuk menganalisis keacakan cipher blok. Contoh penerapan skema permainan kaotik di bidang lain yang terpenting adalah penggunaannya sebagai perangkat analisis rantai DNA (Jeffrey, 1990) (Jeffrey, 1992) (Yang dkk., 2008). Jeffrey mengusulkan metode CGR (chaos game representation atau representasi permainan kaotik) untuk menganalisis rantai DNA dan berhasil mengungkapkan beberapa karakteristik penting dari Human Beta Globin. Skema Jeffrey ini menggunakan empat simbol, yaitu A, C, G, T, menyesuaikan dengan rantai DNA yang dianalisisnya. Berikut adalah prosedur analisis dari skema Jeffrey 1. Bangkitkan deret U empat simbol berdasarkan rantai DNA, U = (ui )i=1,...,n , dengan ui ∈ {A, C, G, T}. 2. Representasi permainan kaotik (CGR) dari U dalam bujur sangkar satuan F adalah deret {x0 , x1 , . . . , xn } yang didefinisikan sebagai berikut: xi+1 = xi + lui+1 dengan x (0) =
1 1 , 2 2
(IV.13)
, lA = (0, 0), lC = (0, 1), lG = (1, 1) dan lT = (1, 0).
Skema Jeffrey dapat diperluas untuk menganalisis sejumlah m-simbol dengan menggunakan poligon segi-m sebagai bidang S. Namun skema ini tidak dapat menghasilkan titik-titik yang tersebar merata ke seluruh bidang ketika menerima masukan deret acak yang mendekati deret acak ideal. Ilustrasi penentuan titik-titik dari CGR dapat dilihat dalam Gambar IV.5. Contoh CGR dapat dilihat dalam Gambar IV.6. Metode CGR menggunakan empat simbol yang menyatakan empat jenis nukleotida yaitu A, G, C dan T. Dalam Bab ini, diusulkan skema permainan kaotik baru yang dapat dipergunakan untuk menganalisis keacakan deret n-bit bilangan biner. Jika input yang digunakan adalah deret acak biner yang mendekati deret acak ideal, maka skema permainan kaotik akan menghasilkan himpunan titik yang tersebar secara merata dalam bidang bujur sangkar. Skema baru ini diharapkan dapat berfungsi sebagai pembeda yang dapat membedakan deret acak dari model permutasi acak. Skema ini juga berpotensi untuk digunakan sebagai perangkat kriptanalisis khususnya terhadap cipher blok. Skema permainan kaotik yang diusulkan dalam disertasi ini merupakan modifikasi dari skema yang digunakan oleh Jeffrey dalam analisis DNA. Beberapa karakter-
IV–19
Gambar IV.5. CGR kombinasi simbol ATGCGAGTGT (Sumber: Digital Search Trees and Chaos Game Representation, presentasi dari Peggy Cenac)
Gambar IV.6. Representasi permainan kaotik (CGR) dari rantai genetik bakteri E. coli K12. (http://insilico.ehu.es/oligoweb/info/CGR.php?ZCGR)
IV–20
istik yang diinginkan dari skema permainan kaotik yang diusulkan adalah sebagai berikut: 1. Skema dapat digunakan untuk menganalisis data-data yang dihasilkan oleh cipher blok sehingga skema ini diharapkan dapat menganalisis sejumlah nbit data. Untuk keperluan tersebut, skema harus menggunakan 2n -simbol. 2. Jika deret acak yang digunakan sebagai masukan memiliki karakteristik yang mendekati deret acak ideal, maka skema ini harus menghasilkan titik-titik yang terdistribusi merata ke seluruh bidang tertentu. Tujuannya adalah untuk memudahkan teknik analisis keacakan.
IV.3.1
Skema Permainan Kaotik untuk Analisis Keacakan
Skema ini tetap menggunakan F yang berbentuk bujur sangkar sebagai bidang tempat titik-titik keluaran permainan kaotik berada. Jumlah simbol tidak bergantung pada jumlah titik sudut bidang F , yang dalam kasus ini adalah 4. Tidak seperti skema Jeffrey, dalam skema ini keempat titik sudut bujursangkar tidak mewakili simbol. Berikut ini adalah persamaan sistem dari skema permainan kaotik yang diusulkan dalam disertasi ini (Sulistyo dkk., 2009a): "
# " # " # x1 (i + 1) c1 0 x1 (i) = · + x2 (i + 1) 0 c2 x2 (i) # " # " (li+1 jmodk2p1 ) · c1 0 + length · · li+1 0 c2 2p1
(IV.14)
dengan • i = 0, 1, 2, . . . adalah indeks yang menyatakan langkah iterasi, h iT • ~x (i) = x1 (i) x2 (i) menyatakan variabel sistem berupa koordinat titik. h iT • ~x (0) = x1 (0) x2 (0) adalah nilai awal sistem, • input dari sistem adalah deret s = l1 , l2 , . . ., • n adalah jumlah bit yang dianalisis, • m = 2n merupakan jumlah simbol yang digunakan, • li merupakan suku deret s dengan li ∈ {0, 1, 2, . . . , m − 1} untuk semua i = 1, 2, . . .
IV–21
Gambar IV.7. Ilustrasi skema permainan kaotik untuk menganalisis n = 3-bit data dengan menggunakan m = 23 simbol h i h • c1 c2 = • p1 = n2 ,
1 p1 2
1 p2 2
i ,
• p2 = n − p1 , • length adalah panjang sisi bidang F , • Bidang F dapat dinyatakan sebagai himpunan titik koordinat F = {(x, y) ∈ R2 } dengan k1 ≤ x1 ≤ (k1 + length) dan k2 ≤ x2 ≤ (k2 + length). Selanjutnya kita nyatakan himpunan seluruh titik keluaran dari skema permainan kaotik hingga iterasi ke-N sebagai XN = {~x (0) , ~x (1) , . . . , ~x (N )} ∈ F . Untuk setiap iterasi, skema ini menggunakan satu pemetaan kontraksi dan sejumlah m pemetaan translasi. Ilustrasi algoritma ini dapat dilihat pada Gambar IV.7. Himpunan XN selanjutnya akan dianalisis dengan menggunakan konsep ukuran seperti yang telah dijelaskan pada subbab III.2.4.(Sulistyo dkk., 2009a)
IV.3.2
Konsep ukuran pada XN
Ambil Bi dengan i = 1, 2, . . . , nrect untuk melambangkan area-area bujur sangkar kecil yang dibentuk dalam bidang F . Untuk menyederhanakan, dipilih bilangan kuadrat untuk nrect yang menyatakan jumlah bujur sangkar. Masing-masing bujur sangkar memiliki luas yang sama dan tidak beririsan satu dengan yang lain atau
IV–22
secara matematis dapat dinyatakan Luas (B1 ) = Luas (B2 ) = . . . = Luas (Bnrect ) dan Bi ∩ Bj = φ untuk setiap i 6= j. Berikut ini adalah definisi dari ukuran terhadap XN dengan Bi , i = 1, . . . , nrect sebagai area-area yang diukur (Sulistyo dkk., 2009a). Definisi IV.6. Ambil XN = {~x (0) , ~x (1) , . . . , ~x (N )} untuk menyatakan titik-titik keluaran dari algoritma permainan kaotik dan N (Bi , XN ) menyatakan jumlah titik XN yang berada dalam area Bi . Massa XN = {~x (0) , ~x (1) , . . . , ~x (N )} dalam area-area Bi=1,2,...,nrect didefinisikan sebagai berikut: µ (Bi=1,...,nrect , XN ) =
IV.3.2.1
N(B1 ,XN ) N +1 N(B2 ,XN ) N +1
.. .
N(Bnrect ,XN ) N +1
(IV.15)
Bias XN terhadap XN ideal
Berikut ini adalah sebuah teorema mengenai ukuran keluaran skema permainan kaotik apabila masukannya berupa deret acak ideal (Sulistyo dkk., 2009a). Teorema IV.2. Ambil XN ideal untuk melambangkan keluaran skema permainan kaotik jika inputnya merupakan deret acak ideal sideal dengan m simbol, F merupakan bidang bujur sangkar seperti yang dijelaskan dalam persamaan IV.14, Bi=1,2,...,nrect merupakan bidang untuk pengukuran yang berbentuk bujur sangkar, dengan luas yang sama yaitu luas (Bi ) = luas (Bj ) untuk semua i, j ∈ 1, . . . , nrect , dengan nrect merupakan bilangan kuadrat dan Bi ∩ Bj = Φ untuk semua i 6= j, maka luas Bi 1 = µ Bi , XN ideal = luas F nrect
(IV.16)
Bukti. Berdasarkan teorema IV.1 deret acak ideal dengan m-simbol memiliki nilai probabilitas kemunculan yang sama (1/m)k untuk tiap kombinasi simbol dengan panjang k-suku. Berdasarkan penjelasan dalam referensi (Peitgen dkk., 1992) dan (Barnsley, 1988) setiap kombinasi k-suku dengan m-simbol dapat digunakan untuk menyatakan alamat (address) dari gambar fraktal yang dibangkitkan oleh algoritma permainan kaotik tertentu yang digunakan untuk membangkitkan XN . Untuk kasus IFS dari persamaan IV.14, setiap alamat akan menunjuk pada bidang berbentuk segi empat yang merupakan himpunan bagian dari F . Karena IFS yang bersesuaian dengan algoritma persamaan IV.14 menghasilkan himpunan titik yang bersifat
IV–23
non-touching dan memenuhi seluruh bidang F maka seluruh bagian dari himpunan F dapat diwakili atau ditunjuk dengan alamat tertentu berupa kombinasi k-suku dengan m-simbol. Karena semua alamat dengan panjang suku yang sama, misal k1 , memiliki probabilitas kemunculan yang sama dalam deret sideal , maka, untuk N → ∞, setiap kombinasi simbol dengan panjang k1 memiliki frekuensi relatif dalam deret sideal yang mendekati probabilitas idealnya, sehingga setiap bagian dari F yang dinyatakan oleh alamat k-simbol memiliki jumlah titik XN ideal yang relatif sama, sehingga XN ideal tersebar merata ke seluruh bagian dari F . Maka untuk seti ap Bx yang merupakan area yang dibentuk sebagai bidang ukuran, µ Bx , XN ideal akan mendekati luas Bx / (luas F ). Bias deret XN terhadap XN ideal , dengan bidang ukuran Bi=1,...,nrect , dinyatakan dalam persamaan berikut ini (Sulistyo dkk., 2009a) bias (XN , Bi=1,...,nrect ) = µ (Bi=1,...,nrect , XN ) − µ Bi=1,...,nrect , XN ideal =
N(B1 ,N ) N +1 N(B2 ,N ) N +1
.. .
N(Bnrect ,N ) N +1
1
nrect 1 nrect − . ..
(IV.17)
1 nrect
Kita juga dapat menyatakan normalisasi bias yaitu bias yang dinormalisasi terhadap ukuran keluaran skema permainan kaotik apabila masukannya berupa deret acak idea dengan persamaan berikut ini (Sulistyo dkk., 2009a) biasnorm (XN , Bi=1,...,nrect ) =
bias (XN , Bi=1,...,nrect ) 1/nrect
(IV.18)
Tujuan normalisasi ini adalah untuk mengetahui rasio antara bias suatu deret acak dengan probabilitas deret idealnya Untuk menghitung biasnorm total, kita akan menggunakan konsep RMS (root mean square) yang dinyatakan dalam persamaan berikut: RMS (biasnorm (XN , Bi=1,...,nrect )) = s
biasnorm (XN , Bi=1,...,nrect )T · biasnorm (XN , Bi=1,...,nrect ) nrect
(IV.19)
IV–24
IV.4
Prosedur Analisis Cipher Blok Berdasarkan Permainan Kaotik
Berikut ini adalah prosedur analisis keacakan dan kriptanalisis cipher blok yang diusulkan dalam disertasi ini. Prosedur ini akan menggunakan perangkat analisis yang dikembangkan dalam bab ini (lihat Gambar IV.8). 1. Iterasikan cipher blok untuk membangkitkan rangkaian pasangan teks-plain dan teks-cipher. Iterasi ini dapat dilakukan dengan menggunakan beberapa sampel nilai awal yang dipilih secara acak. 2. Lakukan analisis simbolik terhadap hasil iterasi tersebut. Cara membagi domain pemetaaan cipher blok ini dilakukan dengan cara memilih bit-bit yang akan dianalisis. Teknik heuristik untuk memilih bit-bit ini akan dijelaskan dengan lebih rinci di Bab V dan VI. Tahap ini menghasilkan deret s dengan masing-masing sukunya menyatakan simbol tertentu. Kita dapat memilih simbol berupa bilangan bulat atau integer. 3. Gunakan deret s tadi sebagai input skema permainan kaotik. 4. Kuantifikasi keluaran dari skema permainan kaotik tersebut dengan konsep ukuran. Penerapan konsep ukuran bertujuan untuk mengukur kerapatan dari atraktor permainan kaotik yang dihasilkan. 5. Dalam kasus analisis keacakan cipher blok, gunakan hasil ukuran tersebut untuk membedakan keacakan antara satu cipher blok dengan cipher blok lainnya. Untuk kasus kriptanalisis, gunakan hasil pengukuran tersebut untuk mengidentifikasi kunci yang benar diantara sehimpunan alternatif kunci yang mungkin.
IV.5
Rangkuman
Analisis keacakan cipher blok dapat dilakukan dengan menganggap cipher blok sebagai fungsi pemetaan dalam suatu sistem dinamik waktu diskrit yang mengiterasi cipher blok tersebut. Metode dinamika simbolik berikutnya dipergunakan untuk membangkitkan deret acak dengan jumlah simbol m tertentu. Analisis keacakan dilakukan terhadap deret tersebut dengan menghitung frekuensi relatif aktual dan bias kemunculan rangkaian simbol tertentu. Bias di sini adalah bias terhadap probabilitas deret acak ideal sebagaimana yang dibahas dalam subbab IV.1.
IV–25
Gambar IV.8. Prosedur analisis keacakan dan kriptanalisis Berdasarkan pembahasan pada bagian IV.2.1.1 dan IV.2.1.4, terlihat bahwa fungsi pemetaan kuadratik bersifat kontinyu dan mulus sedangkan fungsi pemetaan cipher blok bersifat diskontinyu. Iterasi terhadap fungsi kuadratik dengan µ = 4 dan terhadap fungsi cipher blok masing-masing dapat menghasilkan deret simbol yang menyerupai deret acak. Dalam Subbab IV.2.4 juga dibahas analisis simbolik untuk membedakan keacakan dengan menggunakan dua alternatif simbol. Analisis menghasilkan bias yang semakin kecil untuk jumlah ronde cipher blok yang semakin besar. Namun metode ini tidak dapat membedakan cipher blok 3 ronde dengan cipher blok 4 ronde. Pembedaan keacakan 3 dengan 4 ronde ini mungkin dapat dilakukan dengan menambah jumlah alternatif simbol. Penggunaan metode analisis keacakan dengan skema permainan kaotik untuk membedakan keacakan cipher blok 4 ronde dari cipher blok 3 ronde dibahas di Bab V Skema permainan kaotik yang diusulkan dalam bab ini merupakan pengembangan dari skema yang digunakan Jeffrey untuk analisis DNA (Jeffrey, 1990). Dalam setiap iterasi skema ini menggunakan satu pemetaan kontraksi dan m pemetaan translasi. Skema ini dapat digunakan untuk menganalisis deret acak yang tiap
IV–26
sukunya direpresentasikan dalam bilangan biner n-bit. Skema yang dinyatakan dalam persamaan sistem IV.14 akan menghasilkan himpunan titik XN . Berikutnya, konsep ukuran dan bias digunakan untuk menganalisis XN yang merupakan keluaran dari skema permainan kaotik. Konsep bias yang dibahas dalam subbab IV.3.2.1 merupakan perluasan dari konsep bias yang dibahas di subbab IV.1. Berbeda dengan yang dinyatakan dalam persamaan III.7, ukuran dalam persamaan IV.15 dinyatakan dalam bentuk matrik karena bidang ukuran memiliki lebih dari satu area (Bi=1,...,nrect ). Dalam bab berikutnya, metode ini akan digunakan untuk menganalisis keacakan cipher blok. Metode ini juga memiliki peluang untuk dikembangkan menjadi metode kriptanalisis terhadap cipher blok.
BAB V ANALISIS KEACAKAN CIPHER BLOK DENGAN METODE PERMAINAN KAOTIK Bab ini akan membahas penerapan metode permainan kaotik, yang telah dibahas dalam bab IV, untuk menganalisis keacakan cipher blok. Analisis akan dilakukan dengan menggunakan kerangka kerja yang telah dibangun dalam bab IV, yaitu dengan menempatkan cipher blok sebagai fungsi pemetaan dalam sistem dinamik waktu diskrit, menerapkan metode dinamika simbolik untuk membangkitkan deret s dan kemudian menganalisis deret tersebut dengan skema permainan kaotik dan konsep ukuran. Eksperimen analisis keacakan yang dijelaskan dalam bab ini adalah membandingkan tingkat keacakan cipher blok dengan jumlah ronde yang berbeda. Analisis dengan 2-simbol, yaitu dengan mengambil 1-bit data, seperti yang dibahas dalam subbab IV.2.4 dapat membedakan keacakan antara 1, 2, dan 3-ronde cipher blok namun tidak dapat membedakan keacakan antara 3 dan 4-ronde cipher blok. Dengan metode permainan kaotik, analisis yang dilakukan terhadap n-bit data cipher blok dengan m = 2n -simbol diharapkan dapat membedakan jumlah ronde cipher blok dengan lebih baik. Tingkat keamanan algoritma cipher blok berkaitan dengan kedekatan perilakunya dengan model permutasi acak. Semakin tinggi tingkat keamanannya maka semakin tinggi pula kedekatan cipher blok tersebut dengan model permutasi acak. Tingkat keamanan sebuah cipher blok diantaranya ditentukan oleh jumlah ronde yang digunakan. Semakin banyak jumlah ronde maka semakin tinggi pula tingkat keamanannya. Pembahasan dalam bab ini juga dimaksudkan untuk mengeksplorasi aplikabilitas metode permainan kaotik sebagai metrik analisis cipher blok. Metrik analisis yang diusulkan tidak diterapkan terhadap suatu cipher blok secara mandiri, melainkan digunakan untuk membandingkan secara relatif satu cipher blok dari cipher blok yang lain. Model cipher blok SPN yang digunakan dalam disertasi ini memiliki panjang blok data 16-bit dan panjang kunci 32-bit. Seluruh parameter contoh cipher blok yang dipergunakan dalam disertasi ini merujuk dari referensi (Stinson, 2002).
V–2
V.1
Skenario Analisis Keacakan
Bagian ini akan menjelaskan langkah-langkah analisis keacakan, yang secara garis besar terdiri dari: 1. pembangkitan data dengan menggunakan cipher blok, 2. pembangkitan deret acak aktual, 3. membangkitkan himpunan koordinat titik dengan persamaan sistem permainan kaotik, 4. menghitung ukuran, bias, bias ternormalisasi dan RMS bias ternormalisasi, 5. membandingkan keacakan berdasarkan RMS bias ternormalisasi.
V.1.1
Skenario Pengambilan Data
Analisis ini memerlukan sejumlah besar pasangan teks-plain teks-cipher. Data yang dipergunakan dalam analisis di subbab IV.2.3 diperoleh dengan meng-iterasi cipher blok, dengan kunci k yang dipilih secara acak dan dengan menggunakan satu nilai awal. Analisis yang dilakukan dalam bab ini akan menggunakan beberapa nilai awal yang dipilih secara acak sebagai sampel. Tujuannya adalah untuk mengidentifikasi perilaku cipher blok secara statistik. Data yang digunakan dalam analisis ini dinyatakan sebagai berikut: p1 (0) p2 (0) . . . pI (0) p1 (1) p2 (1) . . . pI (1) datak = .. .. .. .. . .... . . p1 (J) p2 (J) . . . pI (J)
(V.1)
dengan • datak melambangkan matriks data yang dihasilkan oleh cipher blok dengan menggunakan kunci k, • pi (j) melambangkan data sampel ke-i iterasi ke-j dengan i ∈ {1, 2, . . . , I} dan j ∈ {0, 1, . . . , K}, dengan I melambangkan jumlah sampel dan J melambangkan jumlah iterasi. • pi (j) ∈ {0, 1}16 yaitu merupakan data biner 16-bit.
V–3
• p1 (0) , p2 (0) , . . . , pI (0) merupakan nilai awal iterasi untuk masing-masing sampel data. Seluruh nilai awal ini dipilih secara acak. Berikut adalah prosedur pembangkitan data: 1. Pilih nilai kunci k 32-bit secara acak 2. Pilih sejumlah I nilai awal secara acak. Masing-masing nilai awal merupakan data 16-bit. Dalam langkah ini diperoleh p1 (0) , p2 (0) , . . . , pI (0) 3. Iterasikan masing-masing nilai awal dengan menggunakan persamaan IV.6. Setiap nilai awal diiterasi sebanyak J kali, sehingga diperoleh datak
V.1.2
Skenario Analisis Data
Deret acak si adalah deret yang disusun dengan cara melakukan subtitusi simbolik terhadap hasil iterasi nilai awal pi (0). Deret acak ini dapat dinyatakan sebagai vektor si = [simb (pi (0)) simb (pi (1)) . . . simb (pi (J))]T . Vektor si ini diperoleh dengan mengambil kolom ke-i dari matrik datak dan mensubtitusi elemen-elemennya dengan simbol berdasarkan aturan tertentu. Langkah subtitusi simbol ini merupakan bagian dari proses analisis simbolik. Jika simbol-simbol yang digunakan merupakan bilangan asli, maka deret acak si yang dihasilkan dapat digunakan sebagai input skema permainan kaotik (yang dinyatakan dalam persamaan IV.14) untuk menghasilkan X=
h
XJ1
XJ2
. . . XJI
i
x~1 (0) x~2 (0) . . . x~I (0) x~1 (1) x~2 (1) . . . x~I (1) = .. .. .. .. . . . . . . . x~1 (J) x~2 (J) . . . x~I (J)
(V.2)
dengan k menyatakan kunci enkripsi cipher blok. Berikut ini adalah prosedur analisis datak 1. Tetapkan mekanisme subtitusi simbolik. Dalam disertasi ini, subtitusi simbolik dilakukan dengan memilih bit-bit tertentu dari data biner dan kemudian mengkonversinya ke dalam bilangan asli.
V–4
2. Ambil vektor data kolom ke-i dari matrik datak dan lakukan subtitusi simbolik sehingga diperoleh deret si = T [simb (pi (0)) simb (pi (1)) . . . simb (pi (J))] untuk semua i = 1, . . . , I. 3. Iterasikan skema permainan kaotik (Persamaan IV.14) dengan menggunakan si sebagai input, sehingga untuk setiap deret si akan diperoleh XJi . 4. Tetapkan himpunan bujur sangkar {Bk |k=1,2,...,nrect } sebagai bidang ukuran. 5. Hitung ukuran µi (Bi=1,...,nrect , XJi ) atau, agar lebih sederhana, bisa kita lambangkan dengan µi saja, untuk i = 1, 2, . . . , I, sehingga kita peroleh h i µ = µ1 µ2 . . . µI N B ,X 1 N(B1 ,XJ2 ) ( 1 J) ··· J+1 J+1 N B ,X 1 2 N(B2 ,XJ ) ( 2 J) ··· J+1 J+1 = . .. N(Bnrect ,XJ1 ) N(Bnrect ,XJ2 ) ··· J+1 J+1
N(B1 ,XJI ) J+1 N(B2 ,XJI ) J+1
N(Bnrect ,XJI ) J+1
(V.3)
6. Hitung bias biasi (Bi=1,...,nrect , XJi ), atau agar lebih sederhana, bisa kita lambangkan dengan biasi , untuk i = 1, 2, . . . , I, sehingga kita peroleh
=
N(B1 ,XJ1 ) J+1 N(B2 ,XJ1 ) J+1
−
1 nrect
−
1 nrect
.. .
N(Bnrect ,XJ1 ) J+1
−
1 nrect
h i bias = bias1 bias2 . . . biasI N(B1 ,XJ2 ) N(B1 ,XJI ) 1 1 − · · · − J+1 nrect J+1 nrect N(B2 ,XJ2 ) N(B2 ,XJI ) 1 1 − − · · · J+1 nrect J+1 nrect N(Bnrect ,XJ2 ) N(Bnrect ,XJ2 ) 1 1 − nrect · · · − nrect J+1 J+1 (V.4)
7. Hitung bias ternormalisasi dengan persamaan berikut: biasnorm =
bias 1/nrect
(V.5)
8. Menghitung RMS dari biasnorm dengan persamaan s RMS (biasnorm ) =
diag biasnorm T · biasnorm nrect
(V.6)
V–5
V.2
Menetapkan Parameter Skema Permainan Kaotik
Metode permainan kaotik akan digunakan untuk menganalisis sebagian bit dari data-data iterasi cipher blok (datak ). Jumlah bit yang dipilih adalah n = 4, sehingga jumlah simbol adalah m = 24 . Panjang sisi bidang F yang digunakan dapat dipilih sembarang tanpa mempengaruhi hasil analisis. Di sini kita pilih length = 100. Dengan merujuk kembali persamaan IV.14 maka dihasilkan persamaan sistem berikut: " # " 2 # " # 1 0 x1 (i + 1) x (i) 1 · = 2 1 2 0 x2 (i + 1) x2 (i) 2 # # " " 2 (V.7) 2 1 (l i+1 mod 2 ) · 0 j k · + 100 · 2 li+1 1 2 0 22 2 dengan li ∈ {0, 1, 2, . . . , 15} untuk semua i ∈ integer. IFS dari sistem yang dinyatakan dalam persamaan V.7 dapat dituliskan kembali sebagai berikut: " # " 2 1 x1 wk = 2 x2 0
# " # " 2 1 x1 0 2 · + 100 · 1 2 x 0 2 2
# " # (k mod 22 ) · 0 · k (V.8) 1 2 2
22
dengan k = 0, 1, 2, . . . , 15. IFS tersebut memetakan area bujur sangkar kembali ke bujur sangkar sedemikian sehingga jika A0 = {(x, y) ; 0 < x < 100 dan 0 < y < 100} ⊂ R2 maka algoritma deterministik akan menghasilkan An = A0 untuk n = 1, 2, . . .. Jika merujuk pada definisi bahwa fraktal adalah bentuk geometri yang memiliki dimensi bukan integer, maka IFS ini tidak menghasilkan atraktor berupa fraktal. IFS dalam persamaan V.8 memiliki kemiripan dengan IFS yang menghasilkan sierpinski triangle namun dengan jumlah pemetaan yang berbeda, yang pertama 3 dan yang kedua 16. Faktanya, kita selalu dapat membuat IFS yang memetakan A0 = {(x, y) ; 0 < x < 100 dan 0 < y < 100} ⊂ R2 kembali ke A0 dengan menggunakan sejumlah {w0 , w1 , . . . , wK−1 } dengan K merupakan bilangan integer. Ilustrasi pemetaan w10 dapat dilihat dalam Gambar V.1.
V–6
Gambar V.1. Ilustrasi pemetaaan w10 dalam IFS 16 simbol
V.3
Membangkitkan Deret Acak
Algoritma permainan kaotik yang dinyatakan dalam persamaan V.7 memerlukan deret s = l0 , l1 , . . ., dengan li ∈ {0, . . . , 15} untuk semua i ∈ integer, sebagai inputnya. Setiap suku dari deret s tersebut digunakan untuk memilih satu transformasi dari himpunan {wi : i = 0, 2, . . . , 15}. Cipher blok yang diuji memiliki panjang blok sebesar 16-bit. Analisis ini akan menggunakan pengujian dengan 16 simbol atau menggunakan 4 bit data sebagai suku-suku deret s. Nilai tiap suku li dari deret acak s ditentukan dengan cara memilih 4-bit dari 16-bit data keluaran cipher blok dan memetakannya menjadi bilangan integer bernilai 0, 1 . . . , 15. Dalam analisis berikut ini kita akan membandingkan keacakan cipher blok dengan 1,2,3 dan 4-ronde dengan cara menguji sekelompok bit dari data cipher blok. Ambil [i1 , i2 , i3 , i4 ], dengan setiap i ∈ integer, untuk menandakan sekelompok bit dengan urutan ke i1 , i2 , i3 , dan i4 . Nomor urutan dari kecil ke besar menyatakan urutan bit dari kiri ke kanan (dari msb ke lsb). Ilustrasi pembangkitan bilangan acak dengan memilih 4-bit msb dari cipher blok, atau [1, 2, 3, 4], dapat dilihat di Gambar V.2.
V.4
Analisis Keacakan Cipher Blok
Pengujian ini menggunakan I = 10 sampel nilai awal yang dipilih secara acak dan J = 1000 iterasi untuk setiap nilai awal. Karena kita akan membandingkan cipher blok untuk jumlah ronde yang berbeda, maka pembangkitan data ini harus dilakukan untuk masing-masing jumlah ronde tersebut. Kunci yang digunakan sama untuk semua jumlah ronde, yaitu
V–7
Gambar V.2. 4-bit msb dari SPN k = 01011010111101001010010010010000. Untuk kelompok bit data [1, 2, 3, 4], penggunaan setiap deret sNr sebagai masukan algoritma permainan kaotik akan menghasilkan himpunan koordinat titik yang dapat dilihat dalam Gambar V.3, V.4, V.5 dan V.6. Dari gambar tersebut terlihat bahwa untuk nilai Nr yang semakin tinggi XNr akan tersebar semakin merata ke seluruh bidang F . Di akhir proses analisis terdapat kebutuhan untuk membedakan sekumpulan sampel statistik dari sekumpulan sampel statistik yang lain. Untuk keperluan itu, akan digunakan metode one-way-anova. Berikut ini adalah tabel yang memperlihatkan hasil perhitungan RMS (biasnormal ), untuk urutan bit [1, 2, 3, 4] dengan masing-masing kolom menyatakan jumlah ronde yang berbeda. Jumlah bujur sangkar Bi yang digunakan sebagai bidang ukuran adalah nrect = 400. Tabel tersebut menampilkan hasil penerapan ukuran terhadap XNr =1,2,3,4 . Setiap kolom berisi RMS (biasnormal ) dari 10-sampel data untuk jumlah ronde tertentu. Terlihat dalam Gambar V.7 bahwa, dengan bantuan perangkat one-way-anova, data
V–8
Gambar V.3. Keluaran algoritma permainan kaotik untuk semua sampel dengan Nr = 1 dengan urutan bit [1, 2, 3, 4]
Gambar V.4. Keluaran algoritma permainan kaotik untuk semua sampel dengan Nr = 2 dengan urutan bit [1, 2, 3, 4]
Gambar V.5. Keluaran algoritma permainan kaotik untuk semua sampel dengan Nr = 3 dengan urutan bit [1, 2, 3, 4]
V–9
Gambar V.6. Keluaran algoritma permainan kaotik untuk semua sampel dengan Nr = 4 dengan urutan bit [1, 2, 3, 4]
Nr = 4 0.6312 0.6067 0.6120 0.6028 0.6578 0.6462 0.6449 0.6171 0.6897 0.6287
Nr = 3 0.7553 0.7372 0.7328 0.7323 0.7490 0.7828 0.7797 0.7543 0.7484 0.7426
Nr = 2 0.9160 0.9451 0.9535 1.0115 0.9766 0.9843 0.9281 0.9388 0.9251 0.9774
Nr = 1 5.9286 19.4418 19.4418 5.9346 19.4418 11.4690 11.4805 5.9286 5.9286 5.9286
Tabel V.1. Tabel yang menampilkan RMS (biasnormal ) dengan Bi=1,2,...,400 untuk beberapa Nr . Kelompok bit yang dianalisis adalah [1, 2, 3, 4]
V–10
himpunan data statistik untuk Nr = 3 dapat dibedakan dari Nr = 4. Tampak pula bahwa jumlah Nr = 4 menghasilkan keacakan yang lebih tinggi daripada Nr = 3.
Gambar V.7. Hasil analisis one-way-anova untuk data statistik dalam Tabel V.1. Kelompok sampel yang sebelah kiri dihasilkan oleh Nr = 4, yang disebelah kanan dihasilkan oleh Nr = 3 Analisis terhadap kelompok bit yang lain, [5, 6, 7, 8] dan [9, 10, 11, 12] memperlihatkan hasil yang serupa. Namun, analisis untuk kelompok bit [13, 14, 15, 16] memperlihatkan bahwa XNr =3 tidak dapat dibedakan dari XNr =4 . Himpunan titik XNr , dengan kelompok bit [13, 14, 15, 16], untuk Nr = 3 dan Nr = 4, diperlihatkan dalam Gambar V.8 dan V.9. Tabel V.2 dan Gambar V.10 memperlihatkan hasil perhitungan RMS (biasnormal ), untuk urutan bit [13, 14, 15, 16] dan Bi=1,2,...,400 . Berdasarkan Gambar V.10, tampak bahwa kumpulan data statistik untuk Nr = 3 tidak dapat dibedakan dari Nr = 4 Nilai RMS (biasnormal ) yang lebih kecil menandakan keacakan deret s yang lebih tinggi. Analisis di atas menunjukkan bahwa cipher blok dengan jumlah ronde yang lebih tinggi akan menghasilkan deret s dengan tingkat keacakan lebih tinggi.
V.5
Rangkuman
Dalam disertasi ini, analisis keacakan terhadap cipher blok dilakukan dengan mengiterasi cipher blok dan kemudian menggunakan bit-bit keluaran yang dipilih untuk membangkitkan deret acak. Deret acak ini selanjutnya menjadi input bagi skema permainan kaotik untuk membangkitkan himpunan titik X.
V–11
Gambar V.8. Keluaran algoritma permainan kaotik untuk semua sampel dengan Nr = 3 dengan urutan bit [13, 14, 15, 16]
Gambar V.9. Keluaran algoritma permainan kaotik untuk semua sampel dengan Nr = 4 dengan urutan bit [13, 14, 15, 16] Nr = 4 0.6191 0.6210 0.6547 0.6080 0.6261 0.5921 0.6492 0.6312 0.6343 0.6578
Nr = 3 0.6331 1.6566 0.6722 0.6074 0.6216 0.6197 0.6126 0.6418 0.6486 0.6356
Nr = 2 0.9354 0.9742 0.9514 0.9510 1.0028 1.0252 1.0182 1.0083 1.0052 1.0275
Nr = 1 7.4701 7.4777 19.9350 7.4777 7.4701 7.4777 7.4777 7.4701 7.4626 7.4701
Tabel V.2. Tabel yang menampilkan RMS (biasnormal ) dengan Bi=1,2,...,400 untuk beberapa Nr . Kelompok bit yang dianalisis adalah [13, 14, 15, 16]
V–12
Gambar V.10. Hasil analisis one-way-anova untuk data statistik dalam Tabel V.2. Kelompok sampel yang sebelah atas dihasilkan oleh Nr = 4, yang bawah dihasilkan oleh Nr = 3 Bab ini juga telah membahas skenario pegambilan data yang digunakan dalam analisis yaitu dengan mengambil sejumlah I-sampel nilai awal secara acak dan mengiterasinya sejumlah J-iterasi. Setiap rangkaian data dalam satu iterasi digunakan sebagai input persamaan dinamik permainan kaotik untuk menghasilkan himpunan titik X. Selanjutnya, konsep ukuran dan bias diterapkan pada X untuk mengukur tingkat keacakan. Pengujian telah dilakukan untuk membedakan keacakan cipher blok dengan jumlah ronde yang berbeda. Dalam pengujian ini terlihat bahwa semakin tinggi jumlah ronde cipher blok maka deret yang dihasilkan akan memiliki bias yang semakin kecil terhadap deret acak ideal. Kemampuan metode ini untuk membedakan keacakan cipher blok dapat dieksplorasi lebih lanjut untuk dikembangkan menjadi metode serangan terhadap cipher blok (Sulistyo dkk., 2009) (Sulistyo dkk., 2009b). Penelitian lebih lanjut juga diperlukan untuk memeriksa penggunaan metode ini untuk menganalisis algoritma cipher blok yang standar yang pada umumnya memiliki tingkat difusi dan konfusi yang tinggi untuk setiap ronde yang dimilikinya. Kebutuhan sumber daya komputasi metode pengujian ini juga masih perlu diteliti lebih jauh lagi untuk mengetahui kemungkinan penerapannya dalam analisis cipher blok dengan panjang blok data yang standar.
BAB VI KRIPTANALISIS CIPHER BLOK DENGAN METODE PERMAINAN KAOTIK Bab ini membahas penerapan metode permainan kaotik untuk kriptanalisis cipher blok. Metode yang dikembangkan di sini tetap menggunakan kerangka yang telah dibangun dalam Bab IV. Kriptanalisis bertujuan untuk mematahkan keamanan cipher blok. Mematahkan keamanan cipher blok tidak selalu berarti menemukan metode yang secara praktis memungkinkan penyerang (eavesdropper) untuk mendapatkan kembali (me-recover) teks-plain hanya dengan memanfaatkan data teks-cipher. Dalam lingkup akademis, dengan definisi yang agak diperlunak, mematahkan keamanan cipher blok berarti menemukan kelemahannya untuk dieksploitasi lebih lanjut dengan kompleksitas yang lebih rendah dari metode serangan brute-force. Misalnya, anggap saja metode brute-force memerlukan 2128 enkripsi, maka sebuah metode serangan yang hanya memerlukan 2110 enkripsi dapat dianggap upaya yang sukses dalam mematahkan keamanan cipher blok meskipun hanya secara teoritis. (Schneier, 2000) Cipher yang akan dianalisis adalah cipher blok berstruktur SPN yang telah dianalisis keacakannya pada bab-bab sebelumnya. Cipher ini memiliki empat ronde, dengan masing-masing ronde menerapkan fungsi permutasi, subtitusi dan pengacakan kunci. Sebagaimana yang dilakukan dalam metode kriptanalisis linear dan diferensial, metode serangan tidak secara langsung me-recover kunci enkripsi. Metodemetode tersebut berupaya mendapatkan kunci-kunci turunan (subkunci) yang digunakan untuk mengacak tiap-tiap ronde. Penyerangan subkunci pada umumnya dilakukan secara berurutan mulai dari ronde terakhir ke ronde awal. Bab ini hanya akan membahas eksperimen penyerangan terhadap subkunci pada ronde terakhir (lihat Gambar VI.1), karena penyerangan terhadap subkunci yang lain dianggap dapat dilakukan dengan cara yang sama. Secara umum, kriptanalisis akan melakukan hal-hal berikut: membangkitkan sejumlah besar data iterasi terhadap cipher (datak ), melakukan invers ronde terakhir terhadap data dengan menggunakan seluruh alternatif subkunci dan kemudian membedakan subkunci yang benar dari subkunci yang salah.
VI–2
Gambar VI.1. Serangan akan dilakukan terhadap subkunci ronde terakhir, ks (5), yang mengacak keluaran ronde keempat cipher
VI.1
Batasan Masalah
Berikut ini beberapa batasan masalah yang digunakan di bab ini 1. Obyek kriptanalisis adalah cipher blok yang digunakan sebagai contoh kasus dalam studi kriptanalisis linear dan diferensial (Heys, 2001). 2. Cipher blok memiliki 4-ronde, panjang blok 16-bit dan panjang kunci 32-bit. 3. Kotak subtitusi (s-box) yang digunakan dianggap tetap. Penelitian ini tidak melakukan analisis terhadap kasus struktur cipher blok yang sama dengan kotak subtitusi yang berbeda. 4. Fungsi permutasi dalam setiap ronde dianggap tetap.
VI–3
Batasan nomor 2 dibuat untuk mengurangi kebutuhan data dalam proses kriptanalisis. Namun demikian batasan ini tidak mengurangi keumuman dari eksperimen yang dilakukan karena untuk cipher blok yang lebih kompleks pengujian tetap dapat dilakukan dengan jumlah data yang lebih besar. Batasan nomor 3 dan 4 tidak mengurangi keumuman dari eksperimen karena langkah-langkah kriptanalisis yang sama tetap dapat dilakukan untuk kotak subtitusi dan fungsi permutasi yang berbeda.
VI.2
Skenario Kaotik
Kriptanalisis
Menggunakan
Permainan
Analisis ini akan menggunakan himpunanan data awal yang sama dengan yang digunakan dalam subbab V.1.1. Disertasi ini merupakan kajian awal mengenai aplikabilitas dari metode permainan kaotik, sehingga berapa jumlah data minimal yang cukup untuk melakukan serangan terhadap cipher belum diketahui. Di sini kita akan menggunakan sejumlah I = 8 dan J = 3000 sehingga secara keseluruhan diperlukan I × (J + 1) = 8 × 3001 = 24008 data. Lambang I menyatakan jumlah nilai awal yang digunakan dengan masing-masing nilai awal tersebut dipilih secara acak. Lambang J menyatakan jumlah iterasi yang dilakukan untuk setiap nilai awal tersebut. Seluruh alternatif blok data yang mungkin adalah 216 = 65536 data karena cipher blok memiliki panjang blok 16-bit. Jadi jumlah data yang digunakan di sini masih diperbolehkan secara teoritis. Skenario analisis data yang digunakan dalam bab ini akan melibatkan bit-bit data input dan inversi ronde terakhir. Tahap pertama kriptanalisis adalah proses pemilihan bit-bit yang dapat digunakan untuk analisis selanjutnya. Hasil pilihan bit-bit tahap pertama ini akan sekaligus membuktikan kebenaran atau kesalahan dari salah satu hipotesis disertasi yang menyatakan bahwa kriptanalisis dapat dilakukan hanya dengan menggunakan bit-bit hasil proses inversi ronde terakhir saja.
VI.2.1
Metode Umum Kriptanalisis
Langkah kriptanalisis secara garis besar dibagi menjadi dua 1. Mengidentifikasi bit-bit mana saja yang dapat digunakan dalam analisis untuk menemukan kunci. Langkah pertama kita lakukan secara offline yaitu sebelum serangan sesungguhnya terhadap cipher dilakukan. Langkah pertama ini merupakan upaya untuk menemukan kelemahan cipher blok.
VI–4
2. Langkah kedua adalah melakukan analisis (seringkali perlu menggunakan analisis statistik) berdasarkan temuan dalam langkah pertama. Penerapan metode permainan kaotik dalam langkah pertama masih berupa studi awal dan agak bersifat heuristik. Namun terdapat indikasi bahwa terdapat beberapa panduan yang dapat diikuti untuk menemukan urutan bit tersebut.
VI.2.2
Skenario Pengambilan Data
Berikut ini adalah langkah-langkah dalam pengambilan data. 1. Bangkitkan data dengan menggunakan I = 8 sampel nilai awal dan J = 3001 iterasi dengan menggunakan kunci k-tertentu sehingga diperoleh datak =
p1 (0) p1 (1) .. .
p2 (0) p2 (1) .. .
p1 (3001) p2 (3001)
... ... .. .... ...
p8 (0) p8 (1) .. .
p8 (3001)
(VI.1)
2. Lakukan inversi-ronde-terakhir terhadap bagian dari blok data datak dengan menggunakan semua alternatif kunci yang mungkin. Blok data mana yang akan diinvers bergantung pada bit-bit mana yang akan digunakan dalam analisis. Berikut ini adalah contoh untuk mengilustrasikan proses tersebut. Diinginkan untuk melakukan inversi-ronde-terakhir terhadap kelompok bit [1, 2, 3, 4], maka proses invers akan diterapkan untuk setiap elemen datak , kecuali nilai awal {p1 (0) , p2 (0) , . . . , pI (0)}, dengan menggunakan semua alternatif kunci. Karena kelompok bit yang dipilih terdiri dari 4-bit, maka panjang bagian subkunci yang digunakan juga 4-bit, sehingga terdapat 24 alternatif kunci. Ambil U1 untuk melambangkan matrik indeks sebagai pe1 nunjuk kelompok bit [1, 2, 3, 4] dan ambil dataUskey=k untuk melambangkan x inversi-ronde-terakhir dari datak dengan urutan bit yang ditunjuk oleh U1 , dengan menggunakan kx sebagai kunci inversi-ronde-terakhir. Berikut ini adalah matrik inv dataUkx1 :
(p1 (1))Ukx1 (p1 (2))Ukx1 .. .
(p2 (1))Ukx1 (p2 (2))Ukx1 .. .
U1 inv datakx = inv (p1 (3001))Ukx1 (p2 (3001))Ukx1
... ... .. .... ...
(p8 (1))Ukx1 (p8 (1))Ukx1 .. .
(p8 (3001))Ukx1 (VI.2)
VI–5
dengan fungsi invers menyatakan proses inversi-ronde-terakhir yang diterapkan terhadap setiap elemen matrik di atas untuk seluruh kunci enkripsi kx ∈ {0, 1}4 . Proses inversi-ronde-terakhir ini menghasilkan matrik invdataUkx1 sebanyak seluruh alterhatif bagian subkunci yang digunakan yaitu 24 buah. Angka-angka yang muncul dalam bagian ini hanya digunakan sebagai contoh saja. Ilustrasi grafis dari proses ini dapat dilihat dalam Gambar VI.2
Gambar VI.2. Ilustrasi pengambilan data untuk keperluan kriptanalisis cipher blok. Matrik yang menghimpun plaintext-plaintext hasil iterasi cipher blok dengan kunci k adalah datak . Matrik yang menghimpun hasil invers-ronde-terakhir terhadap sebagian bit dari datak dengan menggunakan bagian dari subkunci terakhir adalah invdataUkx1
VI–6
VI.2.3
Skenario Pengaturan Data
Skema permainan kaotik nantinya akan menggunakan deret yang dibentuk dari data-data di atas sebagai input. Sebelum analisis dilakukan, kita akan mengatur data dengan cara berikut ini: 1. Ambil Skx untuk melambangkan matrik yang merupakan gabungan dari datak dan inv dataUkx . Maka setiap elemen dari Skx dapat dinyatakan sebagai berikut: (VI.3) Skx (j, i) = datak (j, i) |inv dataUkx1 (j, i) untuk semua kx ∈ {0, 1}n , j = 1, 2, . . . , J, i = 1, 2, . . . , I dengan • n merupakan panjang subkunci yang berhubungan dengan blok data yang dipilih dalam analisis, • Skx (j, i) menyatakan elemen baris ke-j kolom ke-i dari matrik hasil pengaturan data untuk subkunci kx , • datak (j, i) menyatakan elemen baris ke-j kolom ke-i dari matrik hasil iterasi cipher blok, • invdataUkx1 (j, i) menyatakan elemen baris ke j kolom ke-i dari matrik inversi-ronde-terakhir dengan blok data yang dipilih adalah U1 dan • dengan kx menyatakan bagian dari subkunci yang bersesuaian dengan blok data yang digunakan dalam analisis. Subkunci ini yang digunakan untuk melakukan proses inversi-ronde-terakhir, dan • dengan lambang a|b menyatakan penggabungan rangkaian bilangan (word) biner a dan b. 2. Tentukan bit-bit mana saja yang akan diambil untuk kriptanalisis, kemudian untuk tiap-tiap elemen dari Skx ambil bit-bit tersebut untuk ditata dalam matrik lain yang dilambangkan dengan Tkx yang dinyatakan sebagai: Tkx (j, i) = Skx (j, i) |dengan memilih sebagian bit
(VI.4)
untuk semua kx ∈ {0, 1}n , dengan n melambangkan panjang subkunci yang bersesuaian. Matrik Tkx inilah yang akan digunakan untuk membangkitkan deret acak dan kemudian digunakan sebagai input metode permainan kaotik.
VI–7
VI.2.4
Skenario Analisis Data
Subbab ini membahas dua langkah analisis yang digunakan, yaitu: menentukan bit-bit yang akan dianalisis dan berikutnya adalah menggunakan hasil langkah sebelumnya untuk melakukan serangan nyata terhadap cipher blok. Berikut ini adalah prosedur umum yang akan digunakan untuk dua langkah utama tersebut. Untuk setiap nilai kx , terapkan konsep ukuran terhadap matrik Tkx . Karena tujuan utama analisis adalah untuk mengidentifikasi subkunci, maka analisis yang dilakukan di bagian ini harus dapat membedakan kunci yang benar dari kunci yang salah. Bab ini akan menggunakan parameter algoritma permainan kaotik yang sama dengan yang digunakan dalam bagian sebelumnya kecuali untuk pemilihan jumlah simbol m. Langkah-langkah dalam analisis data adalah sebagai berikut: 1. Untuk setiap alternatif kx , definisikan deret ski x yaitu deret yang dibentuk dari data matrik Tkx kolom ke-i. Sehingga untuk setiap nilai kx kita memiliki Ibuah deret, yaitu ski x |i=1,...,I . Seperti yang dijelaskan dalam bagian sebelumnya I menyatakan jumlah sampel. 2. Hitung Xikx , yaitu titik-titik keluaran dari persamaan permainan kaotik (persamaan V.7), untuk setiap nilai bagian subkunci kx dan setiap nilai awal i. 3. Tetapkan himpunan bujur sangkar {Bk |k=1,2,...,nrect } sebagai bidang ukuran. 4. Hitung ukuran terhadap Xikx untuk setiap nilai kx dan i, sehingga diperoleh matrik kolom µki x µki x = µ Bk=1,2,...,nrect , Xikx (VI.5) sehingga untuk setiap nilai kx , kita akan memiliki matrik µkx sebagai berikut h i µkx = µk1x µk2x . . . µkI x
(VI.6)
5. Hitung bias sebagai berikut biaskx = bias µkx
(VI.7)
untuk semua nilai kx sebagaimana yang dilakukan dalam subbab V.1.2 x 6. Hitung bias ternormalisasi biasknorm untuk semua nilai kx sebagaimana sebagaimana yang dilakukan dalam subbab V.1.2 x 7. Hitung RMS dari bias ternormalisasi RMS biasknorm
VI–8
Dalam disertasi ini, analisis akan dilakukan terhadap sebagian bit data yang diambil dari gabungan matrik datak dan dataUkx untuk semua kx ∈ {0, 1}n , dengan n menyatakan panjang bagian subkunci yang digunakan dalam invers-ronde-terakhir. Subbab ini akan menjelaskan langkah-langkah dalam analisis data untuk keperluan kriptanalisis.
VI.2.4.1
Penentuan bit-bit yg dianalisis
Permasalahan yang akan diselesaikan dalam langkah ini dapat dinyatakan secara ringkas sebagai berikut: Dengan kunci k yang diketahui, tentukan bit-bit dari cipher blok yang membentuk matrik Tpart[ks (5)]guess dan deret spart[ks (5)]guess (lihat persamaan (VI.4)), untuk semua alternatif kunci tebakan part [ks (5)]guess yang mungkin, sedemikian sehingga deret Xpart[ks (5)]true dapat dibedakan secara statistik dari semua Xpart[ks (5)]guess , untuk semua part [ks (5)]guess ) 6= part [ks (5)]true . dengan • Tpart[ks (5)]guess merupakan matrik T yang dinyatakan dalam persamaan (VI.4), dengan menggunakan part [ks (5)]guess untuk menginvers bagian dari datak • spart[ks (5)]guess merupakan deret yang dibentuk setiap baris dari Tpart[ks (5)]guess ke bentuk desimal, • Xpart[ks (5)]guess merupakan keluaran metode permainan kaotik dengan input spart[ks (5)]guess , • part [ks (5)]guess ) merupakan nilai tebakan untuk bagian dari subkunci ke-5 yang merupakan subkunci terakhir dari cipher blok, • part [ks (5)]true ) merupakan nilai yang benar untuk bagian dari subkunci ke-5, Disertasi ini belum menghasilkan algoritma yang secara sistematis dapat mengidentifikasi bit-bit mana saja yang harus dianalisis sehingga langkah-langkah identifikasi masih dilakukan dengan teknik yang semi-heuristic. Namun demikian, terdapat beberapa karakteristik dari metode permainan kaotik yang dapat digunakan sebagai langkah awal untuk menemukan metode yang lebih sistematis. Hal ini akan dijelaskan lebih detil dalam subbab VI.4.
VI–9
VI.2.4.2
Membedakan subkunci yang benar dari subkunci yang salah
Subbab VI.2.4.1 menghasilkan pilihan bit yang akan digunakan dalam analisis berikutnya yaitu untuk membedakan subkunci yang benar dari subkunci yang salah. Anggap kita memiliki dataksecret yaitu data yang dihasilkan oleh cipher blok dengan menggunakan skenario yang dijelaskan dalam subbab VI.2.2 dan dengan menggunakan kunci rahasia ksecret . Berdasarkan pilihan-pilihan bit yang telah dihasilkan dalam langkah sebelumnya, berikut ini adalah langkah-langkah untuk membedakan kunci yang benar dari kunci yang salah: 1. Bentuk matrik Tpart[ks (5)]guess untuk semua alternatif part [ks (5)]guess . 2. Gunakan Tpart[ks (5)]guess sebagai input metode permainan kaotik untuk menghasilkan Xpart[ks (5)]guess untuk semua alternatif part [ks (5)]guess . 3. Hitung RMS biasnormal |part[ks (5)]guess untuk semua kunci part [ks (5)]guess . 4. Temukan kunci tebakan yang menghasilkan RMS biasnormal |part[ks (5)]guess yang berbeda secara statistik dari kunci-kunci lain. 5. Tetapkan kunci tersebut sebagai kunci yang benar, yang dilambangkan dengan part [ks (5)]true .
VI.3
Penetapan Parameter Skema Permainan Kaotik
Seperti yang dijelaskan dalam subbab VI.2.1, kriptanalisis akan diawali dengan analisis awal, yang dilakukan secara offline, untuk menentukan bit-bit mana saja yang harus dianalisis. Dalam langkah ini, kita tidak menggunakan parameter n, yaitu parameter yang menyatakan panjang bit yang akan dianalisis, yang tetap. Hal ini karena, dalam tahap ini kita belum mengetahui bit-bit mana saja yang harus dianalisis dan juga berapa panjangnya. Bidang F kita tetapkan sama, sehingga length = 100. Jadi, merujuk kembali ke persamaan (IV.14) kita mendapatkan persamaan dinamika kaotik sebagai berikut: "
# " p 1 1 x1 (i + 1) 2 = x2 (i + 1) 0
dengan p1 =
# " # 0 x1 (i) · + 1 p2 x2 (i) 2 " p # " # p1 1 1 (l i+1 mod 2 ) · 0 j k + length · 2 · li+1 1 p2 0 2p1 2
n 2
dan p2 = n − p1 .
(VI.8)
VI–10
VI.4
Kriptanalisis Cipher Blok Berstruktur SPN
Subbab ini akan membahas hasil kriptanalisis terhadap cipher blok SPN1 . Subbab ini membahas hasil dari dua langkah analisis yang telah dilakukan dalam penelitian ini, yaitu: langkah pemilihan bit-bit yang akan dianalisis dan langkah kriptanalisis dengan kunci yang tidak diketahui.
VI.4.1
Pemilihan Bit-Bit untuk Analisis
Tahap ini menggunakan kunci enkripsi yang dipilih secara acak sebagai berikut k = 01011110100100101101111000110100, Analisis ini menggunakan 8-sampel nilai awal dan 3000-iterasi. Berdasarkan kunci k tersebut, algoritma key schedulling cipher menghasilkan 5-buah subkunci ks (i) |i = 1, 2 . . . , 5 berturut-turut sebagai berikut: 0101111010010010 1110100100101101 1001001011011110.
(VI.9)
0010110111100011 1101111000110100 Subkunci yang akan diidentifikasi di sini adalah subkunci yang terakhir yaitu ks (5). Bagian ini membahas langkah-langkah untuk menentukan bit-bit mana saja yang dianalisis. Metode yang digunakan dalam tahap inimasih bersifat heuristic. Sebagian bit kunci dapat diidentifikasi secara terpisah dari bit-bit yang lain. Identifikasi pertama dilakukan untuk mendapatkan kunci ks (5) urutan bit ke [1, 2, 3, 4, 9, 10, 11, 12] = U1 dan yang berikutnya adalah untuk urutan bit ke [5, 6, 7, 8, 13, 14, 15, 16] = U2 . Untuk membantu analisis, dalam subbab ini, kita akan menggunakan metode statistik one-way-annova untuk membedakan suatu himpunan sampel terhadap himpunan sampel lainnya. 1
Analisis ini menggunakan cipher blok yang sama dengan yang digunakan dalam analisis keacakan di bab V
VI–11
VI.4.1.1
Menentukan pilihan bit-bit untuk mengidentifikasi ks (5) urutan bit ke-[1, 2, 3, 4, 9, 10, 11, 12]
Karena terdapat 8-bit kunci, maka, dengan mengikuti penjelasan bab VI.2.2, kita harus melakukan inversi-ronde-terakhir terhadap datak dengan menggunakan selu ruh 28 -alternatif kunci untuk mendapatkan inv dataUkx1 untuk seluruh alternatif kx . Dalam subbab VI.2.3, matrik Skx dibentuk dengan menggabungkan datak dengan dataUkx1 . Di sini kita hanya akan mengambil beberapa kelompok bit dari datak , yang masing-masing terdiri dari 4-bit, yaitu kelompok V1 = [1, 2, 3, 4], V2 = [5, 6, 7, 8], V3 = [9, 10, 11, 12] dan V4 = [13, 14, 15, 16]. Gabungan antara V1 dengan dataUkx1 U |V dilambangkan dengan Skx1 1 , gabungan antara V2 dengan inv dataUkx1 dilamU |V bangkan dengan Skx1 2 dan seterusnya. Untuk urutan bit U1 bagian subkunci yang benar adalah (lihat VI.9): kxtrue = ksU1 (5) = 11010011 Berikutnya kita membentuk deret bilangan integer dengan mengubah bentuk biner U |V dalam Skx1 i untuk i = 1, 2, 3, 4 menjadi bentuk desimal. Deret yang dihasilkan U |V kita lambangkan dengan rkx1 i . Deret tersebut digunakan sebagai input metode permainan h i kaotik untuk menghasilkan himpunan titik yang dilambangkan dengan U1 |Vi X rkx . Kita akan menggunakan konsep ukuran untuk menghitung RMS bias h i h i U |V U |V ternormalisasi dari X rkx1 i . Karena, untuk setiap nilai i, X rkx1 i berisi beberapa rangkaian data yang berasal dari sampel nilai awal yang dipilih secara acak, maka akan dihasilkan juga beberapa sampel nilai RMS. Untuk membedakan himpunan sampel dalam satu populasi dengan populasi lainnya secara statistik, kita akan memanfaatkan tool one-way-anova dan multiple comparison procedure2 . Dalam bagian ini, kita hanya akan menentukan bit-bit data mana yang harus dinalisis sedemikian sehingga himpunan data yang dihasilkan oleh kx yang benar dapat dibedakan secara statistik dari himpunan data yang dihasilkan oleh nilai kx yang h i U1 |Vi lain, karena itu, kita cukup membandingkan X rkx untuk kunci-kunci di sekUi itar bagian subkunci yanghbenar i(ks (5) = 11010011). Hasil perhitungan RMS U |V bias ternormalisasi dari X rkx1 1 untuk beberapa nilai kx dapat dilihat di Gambar VI.3. Setiap kolom berisi sampel yang mewakili satu kunci tertentu. Tampak bahwa nilai RMS bias ternormalisasi untuk beberapa kunci tidak menunjukkan perbedaan 2
Eksperimen dalam disertasi ini menggunakan paket one-way-anova dan multiple comparison procedure dari Matlab
VI–12
i h U1 |V1 untuk nilai kx di sekitar Gambar VI.3. RMS bias ternormalisasi dari X rkx nilai (ksU1 (5) = 11010011). Sampel yang ditandai dengan kotak merupakan sampel dari kunci yang benar yang signifikan. Hal ini dapat dikonfirmasi dengan menggunakan metode one-wayanova dan multiple comparison yang ditunjukkan dalam Gambar VI.4
Gambar h iVI.4. Hasil analisis perbedaan statistik antara sampel-sampel dalam U1 |V1 X rkx dengan mengambil nilai kunci kx di sekitar (ksU1 (5) = 11010011 h i U |V Analisis terhadap X rkx1 i untuk i = 2 dan i = 4 juga menunjukkan hasil yang sama, yaitu tidak adanya perbedaan yang signifikan antara data yang mewakili kunci yang benar dan kunci yang salah (lihat keluaran di Gambar VI.5 dan VI.6).
VI–13
Gambar h iVI.5. Hasil analisis perbedaan statistik antara sampel-sampel dalam U1 |V2 X rkx dengan mengambil nilai kunci kx di sekitar (ksU1 (5) = 11010011
Gambar h iVI.6. Hasil analisis perbedaan statistik antara sampel-sampel dalam U1 |V4 X rkx dengan mengambil nilai kunci kx di sekitar (ksU1 (5) = 11010011 h i U |V Analisis terhadap X rkx1 3 menunjukkan hasil yang sedikit berbeda. Tampakh bahwa i sampel-sampel hasil perhitungan RMS bias ternormalisasi terhadap U1 |V3 X rkx mulai menunjukkan perbedaan statistik antara kunci yang benar dengan kunci yang salah. Perhitungan RMS bias ternormalisasi untuk beberapa kunci di sekitar kunci yang benar ditampilkan dalam Gambar VI.7. Analisis perbedaan antara populasi sampel dapat dilihat di Gambar VI.8.
VI–14
i h U |V Gambar VI.7. RMS bias ternormalisasi dari X rkx1 3 untuk nilai kx di sekitar nilai (ksU1 (5) = 11010011). Sampel yang ditandai dengan kotak merupakan sampel dari kunci yang benar.
Gambar h iVI.8. Hasil analisis perbedaan statistik antara sampel-sampel dalam U1 |V3 X rkx dengan mengambil nilai kunci kx di sekitar (ksU1 (5) = 11010011 Berdasarkan analisis di atas kita dapat menduga bahwa analisis untuk mencari subkunci dalam kelimpok bit U1 harus menggunakan urutan bit V3 dari datak , sehingga U |V kita memiliki matrik Skx1 3 yang dapat digunakan untuk analisis selanjutnya. PanU |V jang setiap elemen dari matrik Skx1 3 adalah 12-bit. Sekarang kita dapat mencari kandidat matrik T , yaitu matrik yang dibentuk dari S dengan menghilangkan beberapa bit yang tidak dapat dipergunakan dalam kriptanalisis, dengan langkah-langkah berikut:
VI–15
U |V
1. Pilih satu bit dari Skx1 3 dan hilangkan untuk mendapatkan matrik baru U |V S [hilang 1-bit]kx1 3 |urutan bit hilang=t . Bangkitkan koordinat dengan metode permainan kaotik dan hitung RMS bias ternormalisasi untuk semua alternatif urutan bit ke-t dan untuk semua alternatif subkunci kx . 2. Bandingkan hasil perhitungan RMS bias ternormalisasi antar nilai t yang berbeda. Urutan bit ke-tx yang menghasilkan perbedaan yang paling signifikan antara kunci yang benar dengan kunci yang salah harus dihilangkan, U |V sehingga didapat matrik baru Skx1 3 |urutan bit hilang=tx . 3. Lakukan kembali langkah 1 dengan menggunakan matrik U1 |V3 Jika ada penghilangan bit berikutnya (misSkx |urutan bit hilang=tx . al ty ) maka matrik yang dihasilkan berikutnya dilambangkan dengan U |V Skx1 3 |urutan bit hilang=tx ,ty dan seterusnya. Langkah-langkah tersebut diulang hingga tidak ditemukan lagi bit untuk dihilangkan yang menyebabkan perbedaan statistik antara kunci yang benar dan kunci yang salah menjadi lebih signifikan. Dengan mengikuti langkah-langkah yang bersifat heuristik di atas, dihasilkan pilihan urutan bit sebagai berikut: 1. Urutan bit dari datak yang akan digunakan untuk analisis selanjutnya adalah Vattack 1 = [9, 10, 11, 12] 2. Urutan bit untuk memilih matrik inv dataUkx1 adalah Uattack 1 = [1, 2, 3, 9, 10, 11] Bit-bit yang digunakan dalam analisis dapat dilihat lebih jelas di Gambar VI.9. U
|V
Selanjutnya kita dapat membentuk matrik Tkxattack 1 attack 1 , membentuk deret U |V skxattack 1 attack 1 dan menggunakan deret tersebut isebagai input bagi metode permainan h U
|V
kaotik untuk menghasilkan X skxattack 1 attack 1 . Perhitungan RMS ternormalisasi menghasilkan matrik berikut ini (lihat Gambar VI.10).
Terlihat bahwa nilai RMS bias ternormalisasi untuk kunci yang benar menunjukkan perbedaan yang signifikan dengan kunci-kunci yang lainnya. Konfirmasi pembedaan himpunan sampel kunci yang benar dari kunci lainnya dengan menggunakan metode one-way-anova dan multiple comparison dapat dilihat dalam Gambar VI.11
VI–16
Gambar VI.9. Lingkaran menunjukkan bit-bit yang dipilih, Vattack 1 = [9, 10, 11, 12] dan Uattack 1 = [1, 2, 3, 9, 10, 11]. Segi empat menunjukkan bagian dari subkunci yang akan diidentifikasi menggunakan bit-bit tersebut, yaitu ksU1 (5). VI.4.1.2
Menentukan pilihan bit-bit untuk mengidentifikasi ks (5) urutan bit ke-[5, 6, 7, 8, 13, 14, 15, 16]
Bagian ini akan mengidentifikasi bagian subkunci ksU2 [5] dengan U2 [5, 6, 7, 8, 13, 14, 15, 16]. Bagian subkunci yang benar adalah:
=
ky t rue = ksU2 (5) = 11100100 Dengan menggunakan metode yang sama dengan yang telah dilakukan pada subbab sebelumnya, kita akan memeriksa RMS bias ternormalisasi yang dihasilkan oleh U |V i Sky2 untuk i = 1, 2, 3, 4 dan untuk semua alternatif kunci ky . Hasilnya dapat dilihat dalam Gambar VI.12, VI.13, VI.14 dan VI.15.
VI–17
i h U |V Gambar VI.10. RMS bias ternormalisasi dari X rkxattack 1 attack 1 untuk nilai kx di sekitar nilai (ksU1 (5) = 11010011). Sampel yang ditandai dengan kotak merupakan sampel dari kunci yang benar.
Gambar VI.11. Hasil analisis perbedaan statistik antara sampel-sampel dalam U |V Xrkxattack 1 attack 1 dengan mengambil nilai kunci kx di sekitar ksU1 (5) = 11010011 Berbeda dengan kasus sebelumnya, dari keempat gambar tersebut, kunci yang benar tidak memperlihatkan perbedaan statisitik yang signifikan dari kunci-kunci yang lain. Namun, Gambar VI.13 memperlihatkan nilai RMS bias ternormalisasi yang lebih U |V besar dari yang lain. Di sini dapat kita simpulkan bahwa deret rkx2 2 memperliU |V hatkan keacakan yang lebih rendah dibandingkan dengan rkx2 i , untuk i = 1, 3, 4. U |V Jadi kita dapat memilih Skx2 2 sebagai kandidat awal pilihan bit untuk kriptanalisis.
VI–18
Gambar VI.12. Hasil analisis perbedaan statistik antara sampel-sampel dalam U |V Xrkx2 1 dengan mengambil nilai kunci kx di sekitar ksU2 (5) = 11100100
Gambar VI.13. Hasil analisis perbedaan statistik antara sampel-sampel dalam U |V Xrkx2 2 dengan mengambil nilai kunci kx di sekitar ksU2 (5) = 11100100 U |V
Dengan menghilangkan satu demi satu bit dalam Skx2 2 dan memeriksa RMS bias ternormalisasinya sebagaimana yang dilakukan dalam subbab VI.4.1.1, maka kiU |V ta memperoleh matrik Tkxattack 2 attack 2 dengan Uattack 2 = [6, 8, 14, 16] dan Vattack 2 = [5, 6, 7, 8]. Ilustrasi pilihan bit-bit yang akan dianalisis dapat dilihat di Gambar VI.16. U
|V
U
|V
Tkxattack 2 attack 2 akan digunakan untuk membentuk deret skxattack 2 attack 2 , kemudian deret inihdigunakan sebagai input metode permainan kaotik dan menghasilkan matrik i Uattack 2 |Vattack 2 X sk x . RMS bias ternormalisasi untuk setiap himpunan sampel dari
VI–19
Gambar VI.14. Hasil analisis perbedaan statistik antara sampel-sampel dalam U |V Xrkx2 3 dengan mengambil nilai kunci kx di sekitar ksU2 (5) = 11100100
Gambar VI.15. Hasil analisis perbedaan statistik antara sampel-sampel dalam U |V Xrkx2 4 dengan mengambil nilai kunci kx di sekitar ksU2 (5) = 11100100 matrik X VI.17.
h
U |V skxattack 2 attack 2
i
dengan kunci-kunci yang berbeda dapat dilihat di Gambar
Tampak bahwa nilai RMS bias ternormalisasi untuk kunci yang benar berbeda secara signifikan dengan kunci-kunci lainnya. Untuk mengkonfirmasi hal ini, Gambar VI.18 menampilkan hasil analisis pembedaan sampel dengan one-way-anova dan multiple comparison. Eksperimen yang dijelaskan dalam subbab ini menghasilkan pilihan bit-bit yang mencakup bit-bit hasil inversi ronde terakhir maupun bit-bit input. Hal ini tentu
VI–20
Gambar VI.16. Lingkaran menunjukkan bit-bit yang dipilih, Vattack 2 = [5, 6, 7, 8] dan Uattack 2 = [6, 8, 14, 16]. Segi empat menunjukkan bagian dari subkunci yang akan diidentifikasi menggunakan bit-bit tersebut, yaitu ksU2 (5). saja membuktikan kesalahan salah satu hipotesis disertasi yang menyatakan bahwa kriptanalisis berdasarkan permainan kaotik dapat dilakukan hanya dengan menggunakan bit-bit hasil inversi ronde terakhir.
VI.4.2
Mengidentifikasi Subkunci Rahasia
Dalam subbab sebelumnya kita sudah mendapatkan pilihan bit-bit yang akan digunakan untuk mengidentifikasi subkunci rahasia sebagai berikut: 1. Untuk mengidentifikasi ks (5) urutan bit [1, 2, 3, 4, 9, 10, 11, 12] kita menggunakan bit Uattack 1 = [1, 2, 3, 9, 10, 11] dan Vattack 1 = [9, 10, 11, 12]. 2. Untuk mengidentifikasi ks (5) urutan bit [5, 6, 7, 8, 13, 14, 15, 16] kita menggunakan bit Uattack 2 = [6, 8, 14, 16] dan Vattack 1 = [5, 6, 7, 8].
VI–21
h i U |V Gambar VI.17. RMS bias ternormalisasi dari X rkxattack 2 attack 2 untuk nilai kx di sekitar nilai (ksU2 (5) = 11010011). Sampel yang ditandai dengan kotak merupakan sampel dari kunci yang benar.
Gambar VI.18.i Hasil analisis perbedaan statistik antara sampel-sampel dalam h Uattack 2 |Vattack 2 X rkx dengan mengambil nilai kunci kx di sekitar ksU2 (5) = 11100100 Dalam bagian ini, anggap kita memiliki himpunan data, dengan struktur yang sama dengan yang dibahas dalam subbab sebelumnya, yang dihasilkan oleh cipher blok dengan kunci ksecret tertentu. Yang akan dilakukan dalam subbab ini adalah: Dengan menggunakan pilihan-pilihan bit yang telah ditemukan dalam subbab VI.4.1 maka kita akan mengidentifikasi ks (5) dengan menggunakan metode permainan kaotik. Kunci rahasia yang digunakan adalah:
VI–22
ksecret = 10100100101110101010100101011010 sehingga kita memperoleh subkunci 1010010010111010 0100101110101010 ks = 1011101010101001 1010101010010101 1010100101011010 Karena kita mengasumsikan bahwa kunci di atas tidak diketahui, maka tidak seperti pada bagian sebelumnya, perhitungan RMS bias ternormalisasi akan dilakukan untuk seluruh alternatif kunci yang mungkin. Himpunan sampel data dari kunci tertentu yang menunjukkan perbedaan secara statistik dari himpunan sampel kunci yang lain akan diambil sebagai kandidat kunci yang benar. Gambar VI.19 menampilkan hasil identifikasi terhadap ks (5) urutan bit [1, 2, 3, 4, 9, 10, 11, 12] = U1 . Yang dilingkari merupakan sampel yang dihasilkan oleh kandidat dari kunci yang benar. Didapatkan kunci berikut ksU1 = 10100110
Gambar VI.19. Hasil identifikasi ks (5) urutan bit [1, 2, 3, 4, 9, 10, 11, 12] = U1 . Kunci yang dihasilkan adalah 10100110 Gambar VI.20 menampilkan hasil identifikasi terhadap ks (5) urutan bit [5, 6, 7, 8, 13, 14, 15, 16] = U2 . Yang dilingkari merupakan sampel yang dihasilkan oleh kandidat dari kunci yang benar. Didapatkan kunci berikut
VI–23
ksU2 = 10011010
Gambar VI.20. Hasil identifikasi ks (5) urutan bit [5, 6, 7, 8, 13, 14, 15, 16] = U2 . Kunci yang dihasilkan adalah 10011010
VI.5
Perbandingan Kompleksitas Data terhadap Kriptanalisis Linear
Eksperimen di bagian ini akan membandingkan kebutuhan kompleksitas data kriptanalisis berdasarka permainan kaotik terhadap kriptanalisis linear. Bagian subkunci yang akan diidentifikasi adalah ks (5) dengan urutan bit [5, 6, 7, 8, 13, 14, 15, 16]. Dalam (Stinson, 2002), identifikasi bagian sub kunci ini membutuhkan sejumlah 8000 pasangan teks-plain dan teks-cipher. Dalam subbab ini, kriptanalisis berdasarkan permainan kaotik akan menggunakan sejumlah I = 3 sampel nilai awal dan J = 2500 iterasi, sehingga secara keseluruhan dibutuhkan I × (J + 1) = 3 × 2501 = 7503 data. Eksperimen ini akan menggunakan kunci rahasia yang sama dengan yang digunakan pada subbab sebelumnya, yaitu ksecret = 10100100101110101010100101011010 sehingga didapatkan subkunci
VI–24
1010010010111010 0100101110101010 ks = 1011101010101001 1010101010010101 1010100101011010 Sebagian nilai-nilai bias ternormalisasi yang dihasilkan dari analisis terhadap sejumlah 3 sampel nilai awal dan 2500 iterasi untuk masing-masing nilai awal tersebut dapat dilihat dalam Gambar VI.21
Gambar VI.21. RMS bias ternormalisasi dari X
h
U |V rkxattack 2 attack 2
i
untuk nilai kx di
(ksU2
sekitar nilai (5) = 10011010). Sampel yang ditandai dengan kotak merupakan sampel dari kunci yang benar. Gambar VI.22 menampilkan hasil identifikasi terhadap ks (5) dengan urutan bit [5, 6, 7, 8, 13, 14, 15, 16] = U2 . Tanda lingkaran menunjukkan sampel yang dihasilkan oleh kandidat subkunci yang benar. Dari analisis ini didapatkan kunci ksU2 = 10011010 yang sesuai dengan nilai subkunci rahasia untuk ronde dan bagian yang sama. ss Gambar VI.22. Hasil identifikasi ks (5) [5, 6, 7, 8, 13, 14, 15, 16] = U2 dan dengan 7503 data
dengan
urutan
bit
Eksperimen yang dilakukan dalam subbab ini telah menunjukkan bahwa, untuk cipher blok yang dibahas dalam disertasi ini, dalam proses identifikasi terhadap bagian subkunci ks (5) dengan urutan bit [5, 6, 7, 8, 13, 14, 15, 16] = U2 , kriptanalisis berdasarkan permainan kaotik membutuhkan jumlah data yang sedikit lebih kecil dari kriptanalisis linear.
VI–25
VI.6
Permasalahan Keacakan dan Kunci Lemah dalam Eksperimen
Eksperimen yang dilakukan dalam disertasi ini melibatkan penggunaan fungsi acak (permutasi acak ataupun pembangkit bilangan acak) untuk membangkitkan kunci enkripsi dan nilai awal iterasi. Implementasi fungsi acak, yang dilakukan dalam lingkungan Matlab, menggunakan perintah >>randperm(n) yang melakukan permutasi terhadap bilangan integer i = 1, 2, . . . , n. Eksperimen menggunakan dua kunci acak yang berbeda, yaitu: (1) kunci enkripsi untuk menentukan bit-bit yang dapat digunakan dalam serangan nyata, dan (2) kunci enkripsi rahasia yang diidentifikasi dalam serangan nyata. Sejumlah nilai awal iterasi juga dibangkitkan secara acak untuk setiap himpunan data yang digunakan dalam analisis. Kunci lemah dari suatu cipher blok adalah kunci rahasia dengan nilai tertentu yang menyebabkan cipher blok menghasilkan perilaku yang tidak diinginkan termasuk menghasilkan keamanan enkripsi yang sangat buruk/lemah (Mollin, 2001, hal. 112). Sebagai contoh, DES memiliki dua jenis kunci lemah, yaitu (1) kunci lemah k1 yang menghasilkan Ek1 (Ek1 (x)) = x untuk semua x, dan (2) kunci lemah k2 dan k3 yang menghasilkan Ek2 (Ek3 (x)) = x untuk semua x (Menezes dkk., 1996, hal. 257). Eksperimen kriptanalisis yang dilakukan menghindari penggunaan kunci lemah dengan beberapa cara berikut ini: • Membangkitkan kunci enkripsi secara acak seperti yang dijelaskan di atas • Mengamati distribusi himpunan titik X keluaran skema permainan kaotik. Kunci enkripsi merupakan kunci lemah jika banyak bagian dari atraktor ideal skema permainan kaotik yang tidak terwakili oleh X.
VI.7
Rangkuman
Bab ini telah menjelaskan langkah-langkah kriptanalisis cipher blok dengan menggunakan metode permainan kaotik. Analisis ini secara umum dibagi menjadi dua tahap utama yaitu (1) tahap penentuan pilihan bit secara offline dan berikutnya adalah (2) tahap identifikasi kunci rahasia. Prinsip utama yang digunakan adalah
VI–26
pembedaan RMS bias ternormalisasi himpunan sampel kunci yang benar dari kunci yang salah. Analisis yang dilakukan telah berhasil menemukan semua subkunci ronde terakhir dari cipher blok. Karena data yang digunakan dalam kriptanalisis dibangkitkan dengan cara melakukan iterasi terhadap cipher blok, maka jenis serangan yang dilakukan di bab ini dapat digolongkan dalam serangan dengan teks-plain yang dipilih secara adaptif. Dalam tahap (1), metode permainan kaotik menghasilkan pilihan bit-bit yang berbeda dari yang digunakan oleh metode kriptanalisis linear dan diferensial 3 . Jika pilihan bit ini diubah (baik ditambah ataupun dikurangi), maka kompleksitas data akan meningkat atau bahkan subkunci yang benar menjadi tidak terbedakan dari subkunci yang salah. Salah satu hipotesis dalam disertasi ini menyatakan bahwa kriptanalisis terhadap cipher blok dapat dilakukan hanya dengan menggunakan bit-bit data yang dihasilkan dari proses inversi satu ronde dengan menggunakan seluruh kandidat bagian subkunci. Berdasarkan eksperimen yang telah dilakukan, hal ini tidak terbukti. Kriptanalisis dengan skenario pengambilan data yang hanya menggunakan bit-bit data hasil proses inversi satu ronde gagal untuk membedakan kandidat subkunci yang benar dari kandidat subkunci yang salah. Kriptanalisis yang dilakukan dengan menggunakan sejumlah I = 8 nilai awal dan J = 3000 iterasi berhasil menemukan seluruh subkunci terakhir dari cipher blok yang menjadi obyek kriptanalisis dalam disertasi ini. Pada bagian akhir bab ini, juga dibahas mengenai eksperimen yang dilakukan untuk membandingkan kriptanalisis berdasarkan permainan kaotik terhadap kriptanalisis linear dari aspek kompleksitas data. Eksperimen ini menunjukkan bahwa untuk bagian subkunci tertentu, yaitu subkunci ks (5) dengan urutan bit [5, 6, 7, 8, 13, 14, 15, 16] = U2 , kriptanalisis berdasarkan permainan kaotik memerlukan kompleksitas data yang sedikit lebih rendah dari kriptanalisis linear. Dalam disertasi ini, deskripsi matematis untuk menghitung jumlah data minimal yang diperlukan untuk kriptanalisis belum dapat dirumuskan secara eksplisit. Eksperimen awal kriptanalisis dengan metode permainan kaotik menggunakan jumlah data yang relatif besar yaitu 24000 data atau 24000 proses enkripsi. Sebagai perbandingan, metode kriptanalisis linear memerlukan kurang lebih 8000 pasang teksplain dan teks-cipher atau 8000 proses enkripsi untuk mendapatkan bagian subkunci yang sama. 3
bandingkan gambar Gambar VI.16 dengan Gambar C.1 dan Gambar C.2 dalam Lampiran C
VI–27
Kriptanalisis dengan metode permainan kaotik tidak memerlukan analisis terhadap kotak subtitusi. Hal ini yang membedakannya dengan kriptanalisis linear dan diferensial. Dalam kriptanalisis linear dan diferensial, analisis terhadap kotak subtitusi ini diperlukan untuk memilih bit-bit yang akan digunakan dalam serangan nyata dan untuk menghitung bias probabilitas yang diperkirakan akan dimunculkan oleh subkunci yang benar. Dalam metode kriptanalisis dengan permainan kaotik, langkah analisis ini digantikan oleh langkah komputasi pra-serangan. Dari sisi kompleksitas komputasi, tentu saja hal ini akan meningkatkan kompleksitas komputasional serangan. Namun, komputasi pra-serangan tersebut hanya perlu dilakukan satu kali untuk cipher blok tertentu. Setelah pilihan bit-bit diperoleh, serangan nyata terhadap subkunci dapat langsung dilakukan tanpa melakukan ulang langkah komputasi pra-serangan tersebut. Perbandingan antara metode kriptanalisis- berdasarkan-permainan-kaotik dengan metode kriptanalisis linear dapat dilihat dalam Tabel VII.1
Aspek
Penentuan bit untuk serangan nyata Kompleksitas komputasi
Kompleksitas data
Skenario umum serangan
Kriptanalisis permainan kaotik Komputasi pra-serangan dengan metode heuristik Tambahan komputasi untuk membangkitkan himpunan titik koordinat XN dengan skema permainan kaotik dan perhitungan dengan konsep ukuran Identifikasi masih berhasil dengan menggunakan 7503 data Serangan dengan teks-plain yang dipilih secara adaptif
Kriptanalisis linear
Aproksimasi linear terhadap kotak subtitusi Implementasi penghitung (counter) dan fungsi EX-OR
Identifikasi berhasil dengan menggunakan 8000 data Serangan dengan teks-plain yang diketahui
Tabel VI.1. Perbandingan kriptanalisis berdasarkan permainan kaotik dengan kriptanalisis linear
BAB VII KESIMPULAN Beberapa poin yang menjadi kesimpulan dari disertasi ini adalah sebagai berikut: 1. Dalam disertasi ini diusulkan skema permainan kaotik baru yang memiliki karakteristik sebagai berikut: • Skema ini dapat digunakan untuk menganalisis deret acak s = l0 l1 l2 . . . lN , yang tiap sukunya memiliki M = 2n buah alternatif simbol. Dengan demikian, skema permainan kaotik ini dapat digunakan untuk menganalisis deret dengan suku-suku bilangan biner n-bit, atau li ∈ {0, 1}n untuk i = 0, 1, . . . , N . • Skema ini menghasilkan atraktor berupa fraktal bujur sangkar dengan titik-titik (X) yang tersebar merata jika inputnya mendekati deret acak ideal. Dengan demikian, pengukuran penyimpangan atraktor yang dihasilkan dari atraktor ideal menjadi mudah dilakukan. • Penyimpangan distribusi titik-titik X tersebut dari titik-titik yang dihasilkan oleh deret acak ideal diukur dengan menggunakan konsep ukuran. 2. Eksperimen yang telah dilakukan dalam disertasi ini menghasilkan hal-hal berikut: • Analisis keacakan yang telah dilakukan berhasil membedakan dua cipher blok yang sama yang memiliki jumlah ronde yang berbeda. • Kriptanalisis tidak dapat dilakukan hanya dengan menggunakan bit-bit data invers satu ronde terakhir. Dengan cara ini, tidak terdapat perbedaan statistik yang signifikan antara sampel data terkait subkunci yang benar dengan sampel data terkait subkunci yang salah. • Kriptanalisis yang dilakukan dengan mengkombinasikan bit-bit input dan data invers satu ronde terakhir berhasil mengidentifikasi seluruh subkunci terakhir dari cipher blok. 3. Eksperimen yang telah dilakukan berhasil membuktikan kebenaran hipotesis 1 dan hipotesis 3. Hipotesis 2 tidak dapat dibuktikan kebenarannya.
VII–2
4. Dalam disertasi ini, deskripsi matematis untuk menghitung jumlah data minimal yang diperlukan untuk kriptanalisis belum dapat dirumuskan secara eksplisit. 5. Tabel VII.1 berikut ini menampilkan perbandingan kinerja antara metode kriptanalisis berdasarkan permainan kaotik dengan metode kriptanalisis linear dalam serangan terhadap cipher blok yang menjadi obyek kriptanalisis dalam disertasi ini. Metode kriptanalisis berdasarkan permainan kaotik tetap dapat diajukan sebagai kandidat metode kriptanalisis baru karena metode ini mengekploitasi aspek kerawanan yang berbeda dibandingkan dengan kriptanalisis linear dan diferensial. Aspek
Kriptanalisis permainan kaotik
Kompleksitas komputasi Kompleksitas data Skenario pengambilan data
Kriptanalisis linear
++ + +
Tabel VII.1. Perbandingan kriptanalisis berdasarkan permainan kaotik dengan kriptanalisis linear
6. Beberapa hal yang merupakan kontribusi utama dalam penelitian ini adalah sebagai berikut: • Konstruksi skema permainan kaotik baru yang dapat digunakan untuk menganalisa keacakan deret. Skema ini dapat digunakan untuk menganalisis keacakan sebuah deret acak s = l1 , l2 , . . . , lN dengan li ∈ {0, 1}n , dengan n menyatakan panjang bit data yang dianalisis. Hal ini dibahas dalam subbab IV.3.1. • Pengembangan konsep ukuran untuk mengkuantifikasi keluaran dari skema permainan kaotik. Dalam disertasi ini, yang dianalisis adalah distribusi titik keluaran skema permainan kaotik. Hal ini dibahas dalam subbab IV.3.2. Konsep deret acak ideal sebagai dasar pengembangan
VII–3
konsep ukuran ini juga dirumuskan dalam disertasi ini. Hal ini dibahas dalam subbab IV.1. • Pengembangan metode analisis keacakan berdasarkan permainan kaotik untuk membandingkan keacakan dua cipher blok secara relatif. Dalam disertasi ini, yang dianalisis atau dibandingkan adalah cipher blok jenis yang sama yang memiliki jumlah ronde yang berbeda. Hal ini dibahas dalam bab V. • Pengembangan metode kriptanalisis berdasarkan permainan kaotik untuk mengidentifikasi subkunci terakhir cipher blok dengan tipe SPN. Disertasi ini telah menghasilkan metode kriptanalisis dengan memanfaatkan skema permainan kaotik yang dikembangkan dalam ranah keilmuan sistem dinamik khususnya dinamika kaotik. Hal ini dibahas dalam bab VI. 7. Berdasarkan hasil-hasil yang telah dijelaskan sebelumnya, penulis menyarankan dilakukannya beberapa beberapa penelitian sebagai tindak lanjut temuan dalam disertasi ini: • Penelitian untuk menerapkan metode kriptanalisis yang dikembangkan dalam disertasi ini terhadap cipher blok standar, misalnya DES, SERPENT, AES dan BC2. Ujicoba metode kriptanalisis ini pada umumnya dilakukan terhadap versi ronde yang tereduksi dari cipher blok standar tersebut. • Penelitian untuk merumuskan kaitan antara struktur cipher blok dengan batas bawah jumlah data yang dibutuhkan agar kriptanalisis yang dilakukan berhasil. • Penelitian untuk membandingkan secara lebih komprehensif metode kriptanalisis ini terhadap metode-metode lain dari berbagai aspek khususnya dari kompleksitas data dan kompleksitas komputasi. • Penelitian untuk mencari karakteristik matematis dari cipher blok yang rawan terhadap metode kriptanalisis yang dikembangkan dalam disertasi ini. • Penelitian untuk mengembangkan kriptanalisis dengan metode kaotik, antara lain mencoba beberapa alternatif konsep ukuran untuk mengukur keluaran dari skema permainan kaotik. Beberapa teknik yang
VII–4
mungkin diterapkan untuk menganalisis titik-titik yang merupakan keluaran dari skema permainan kaotik adalah – Melihat dinamika penyimpangan jumlah titik dalam bidang B tertentu seiring bertambahnya jumlah data. – Menerapkan teknik matematik supremum ataupun infimum untuk mengkuantifikasi jatuhnya titik-titik keluaran skema permainan kaotik dalam bidang B
PUBLIKASI Penelitian dalam disertasi ini telah dipublikasikan dalam konferensi dan jurnal internasional, yaitu: 1. Randomness Analysis of Block Cipher, diterima dengan revisi minor di International Journal of Secure Digital Information (IJSDIA) Age, Volume I, Issue II, Desember 2009. 2. On Applicability of Chaos Game Method for Block Cipher Randomness Analysis, dimuat di Proceeding of the 2009 International Conference on Electrical Engineering and Informatics, Volume II, Agustus 2009, Selangor, Malaysia. 3. Randomness Analysis of Block Cipher using Chaos Game Method, dimuat di Proceedings International Conference on Rural Information and Communication Technology 2009, Juni 2009, Bandung, Indonesia. 4. New Methodology of Block Cipher Analysis Using Chaos Game, Submitted to ICT Journal, ITB, October 2009).
PUB–1
DAFTAR PUSTAKA Amigó, J. M., Kocarev, L., dan Szczepanski, J. (2007, Oktober). Discrete Lyapunov Exponent and Resistance to Differential Cryptanalysis. IEEE Transactions on Circuits and Systems 54. Amigo, J., Kocarev, L., dan Szczepanski, J. (2007). Theory and Practice of Chaotic Cryptography. Physics Letters A. Anderson, R. (1992). Letter to the editor: Chaos and random numbers. Cryptologia XVI(3), 226. Barnsley, M. (1988). Fractals everywhere. San Diego, CA, USA: Academic Press Professional, Inc. Biham, E. (1991). Cryptoanalysis of the Chaotic-Map Cryptosystem Suggested at EUROCRYPT’91. In EUROCRYPT, pp. 532–534. Borst, J. (2001). Block Ciphers: Design, Analysis and Side-Channel Analysis Kasteelpark Arenberg 1, B-3001 leuven-Haverlee (Belgium). Ph. D. thesis, Katholieke Universiteit Leuven-Faculteit Toegepaste Wetenschappen. Curiac, D.-I., Iercan, D., Dranga, O., Dragan, F., dan Banias, O. (2007). ChaosBased Cryptography: End of the Road? In SECUREWARE ’07: Proceedings of the The International Conference on Emerging Security Information, Systems, and Technologies, Washington, DC, USA, pp. 71–76. IEEE Computer Society. Dachselt, F., Kelber, K., dan Schwarz, W. (1998). Discrete-time chaotic encryption systems. III. Cryptographicalanalysis. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 45, 983 – 988. Dachselt, F. dan Schwarz, W. (2001, Desember). Chaos and Cryptography. IEEE Transactions on Circuits and Systems I: FUNDAMENTAL THEORY AND APPLICATIONS 48(12). Gotz, M., Kelber, K., dan Schwarz, W. (1997). DISCRETE-TIME CHAOTIC ENCRYPTION SYSTEMS Part I: Statistical Design Approach. IEEE Transactions on Circuits and Systems 44(10). Gulick, D. (1992). Encounter with Chaos. McGraw Hill.
PUST–1
PUST–2
Habutsu, T., Nishio, Y., Sasase, I., dan Mori, S. (1991). A Secret Key Cryptosystem by Iterating a Chaotic Map. In EUROCRYPT, pp. 127–140. Hernandez, J. C., Isasi, P., Sierra, J. M., dan Tablas, A. G. (2001). How to distinguish between a block cipher and a random permutation by lowering the input entropy. In IEEE 35th International Carnahan Conference on Security Technology. Hernández, J. C., Sierra, J. M., Ribagorda, A., Ramos, B., dan Mex-Perera, J. C. (2001). Distinguishing TEA from a Random Permutation: Reduced Round Versions of TEA Do Not Have the SAC or Do Not Generate Random Numbers. In Proceedings of the 8th IMA International Conference on Cryptography and Coding, London, UK, pp. 374–377. Springer-Verlag. Heys, H. M. (2001). A Tutorial on Linear and Differential Cryptanalysis. Technical report. Jakimoski, G. dan Kocarev, L. (2001a). Analysis of some recently proposed chaos˝ based encryption algorithms. Physics Letters A, 381U384. Jakimoski, G. dan Kocarev, L. (2001b, Februari). Chaos and Cryptography: Block Encryption Ciphers Based on Chaotic Maps. IEEE Transactions on Circuits and Systems I: FUNDAMENTAL THEORY AND APPLICATIONS 48(2). Jakimoski, G. dan Subbalakshmi, K. (2007). Discrete Lyapunov Exponent and Differential Cryptanalysis. IEEE. Jeffrey, H. (1990). Chaos games representation of genetic sequences. Nucleic Acids Research 18(8), 2163–2170. Jeffrey, H. (1992). Chaos game visualization of sequences. Computer & Graphics 16(1), 25–33. Kathleen T. Alligood, Tim D. Sauer, J. A. Y. (2000). Chaos: An Introduction to Dynamical Systems. Springer. Katos, V. (2005). A randomness test for block ciphers. Science Direct: Applied Mathematics and Computation 162, 29–35. Kelber, K., Falk, T., Gotz, M., Schwarz, W., dan Kilias, T. (1998). DISCRETETIME CHAOTIC CODERS FOR INFORMATION ENCRYPTION Part II: Continuous and Discrete Value Realisation. Kocarev, L. (2001). Chaos-Based Cryptography: A Brief Overview. IEEE.
PUST–3
Kocarev, L., Jakimoski, G., Stojanovski, T., dan Parlitz, U. (1998). From chaotic maps to encryption schemes. In Proceedings of the 1998 IEEE International Symposium on Circuits and Systems. ISCAS ’98., Volume 4, pp. 514–517. Kocarev, L. dan Szczepanski, J. (2004). Finite-Space Lyapunov Exponents and Pseudo Chaos. Physical Review Letter. Kocarev, L., Szczepanski, J., Amigó, J. M., Tomovski, I., Operativa, C. D. I., Elche, H., Kocarev, L., Szczepanski, J., Amigó, J. M., dan Tomovski, I. (2005). ˝ Part I: Theory. Discrete Chaos U Li, S. dan Chen, G. (2004). ON THE DYNAMICAL DEGRADATION OF DIGITAL PIECEWISE LINEAR CHAOTIC MAPS. International Journal of Bifurcation and Chaos. Li, S., gonzalo Alvarez, Li, Z., dan Halang, W. A. (2007). Analog Chaos-Based Secure Communications and Cryptanalysis. Li, S., Mou, X., dan Cai, Y. (2003). Chaotic Cryptography in Digital World: Stateof-The-Art, Problems and Solutions. Matthews, R. (1984). On the derivation of a “Chaotic” encryption algorithm. Cryptologia 8(1), 29–41. Menezes, A. J., Vanstone, S. A., dan Oorschot, P. C. V. (1996). Handbook of Applied Cryptography. Boca Raton, FL, USA: CRC Press, Inc. Mollin, R. A. (2001). An Introduction to Cryptography. The CRC Press series on discrete mathematics and its applications. Peitgen, H.-O., Jürgens, H., dan Saupe, D. (1992). Fractals for the classroom. Part 1: Introduction to fractals and chaos. New York, NY, USA: Springer-Verlag New York, Inc. Ritter, T. Ritter’s Crypto Glossary and Dictionary of Technical Cryptography. Schneier, B. (1996, Oktober). Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition (2nd ed.). Wiley. Schneier, B. (2000). A self-study course in block-cipher cryptanalysis. Cryptologia 24(1), 18–33. Shannon, C. (1949). Communication theory of secrecy systems.
PUST–4
Shujun, L., Qi, L., Wenmin, L., Xuanqin, M., dan Yuanlong, C. (2001, Desember). Statistical Properties of Digital Piecewise Linear Chaotic Maps and Their Roles in Cryptography and Pseudo-Random Coding. Lecture Notes in Computer Science 2260, 205–221. Singh, S. (2002). The Code Book. City: Harpercollins Pub Ltd. Stinson, D. R. (2002, Februari). Cryptography: Theory and Practice, Second Edition. Chapman & Hall/CRC. Sulistyo, B. (2009). Falsifikasi Karl Popper dalam Pembuktian Keamanan Cipher. Diajukan ke majalah KK Kendali ITB. Sulistyo, B., Rahardjo, B., dan Mahayana, D. (2009, Agustus). On Applicability of Chaos Game Method for Block Cipher Randomness Analysis. In International Conference on Electrical Engineering and Informatics, Volume I, Selangor, Malaysia. IEEE Computer Society: IEEE. Sulistyo, B., Rahardjo, B., Mahayana, D., dan Machbub, C. (2009a, Oktober). New Methodology of Block Cipher Analysis Using Chaos Game. Submitted to ICT Journal, ITB. Sulistyo, B., Rahardjo, B., Mahayana, D., dan Machbub, C. (2009b, Juni). Randomness Analysis of Block Cipher using Chaos Game Method. In Proceedings International Conference on r-ICT. Wheeler, D. D. (1991). Problems with Mitchell’s nonlinear key generators. Cryptologia 15(4), 355–363. Wheeler, D. D. dan Matthews, R. A. J. (1991). Supercomputer investigations of a chaotic encryption algorithm. Cryptologia 15(2), 140–152. Wikipedia (2009, Agustus). Fractal. online. Wolfram, S. (1986). Cryptography with cellular automata. In Lecture notes in computer sciences; 218 on Advances in cryptology—CRYPTO 85, New York, NY, USA, pp. 429–432. Springer-Verlag New York, Inc. Yang, J.-Y., Yu, Z.-G., dan Anh, V. (2008). Protein Structure Classification Based on Chaos Game Representation and Multifractal Analysis. International Conference on Natural Computation 4, 665–669. Yang, T. (2003). A SURVEY OF CHAOTIC SECURE COMMUNICATION SYSTEMS. International Journal of Computational Cognition.
RIWAYAT HIDUP Penulis dilahirkan pada tanggal 24 Januari 1976 di Kendal, Jawa Tengah. Ia lulus dari SMA Negeri 3 Semarang pada tahun 1994. Selanjutnya penulis berhasil memperoleh gelar Sarjana di bidang Teknik Elektro pada tahun 2000 dan Magister di bidang Teknik Elektro pada tahun 2002, keduanya di Institut Teknologi Bandung. Penulis bergabung dengan lembaga riset Sharing Vision pada tahun 2003. Di lembaga ini, penulis berperan dalam penyelenggaraan workshop di bidang Teknologi Informasi dan juga berperan sebagai pembicara dalam beberapa workshop tersebut sejak tahun 2003 hingga sekarang. Penulis juga aktif dalam beberapa kegiatan profesional di bidang Keamanan Teknologi Informasi khususnya dalam Perancangan Arsitektur Keamanan Sistem Pembayaran Elektronik dan Pembuatan Prototipe Sistem Pembayaran Elektronik (2006-2007). Penulis menikah dengan Dwi Endang Murdaningsih pada tahun 2005 dan telah dikaruniai dua orang anak, Alfia Fathima 3.5 tahun dan Miqdada Shafiya 1.5 tahun.
RH–1
LAMPIRAN
LAMPIRAN A COBWEB PLOT Cobweb plot merupakan teknik ilustrasi grafis yang dapat menggambarkan perilaku pemetaan satu dimensi dengan mudah. Berikut ini adalah langkah-langkah penggambaran cobweb plot dengan mengambil xn = f (xn−1 ) = 2 (xn−1 ), dengan nilai awal x = 0.01: 1. Gambarkan fungsi f = 2x dan garis diagonal y = x. Fixed point dari sistem dapat ditentukan dengan mudah yaitu dengan mencari titik perpotongan antara grafik f dengan garis diagonal y = x. Untuk kasus ini fixed point adalah x = 0.
Gambar A.1. Contoh cobweb plot untuk f = 2x 2. Dengan memulai dari titik awal x = 0.01, tariklah garis vertikal dari titik koordinat (x, y) = (0.01, 0) hingga memotong fungsi f = 2x. Nilai koordinat y koordinat titik perpotongan ini sama dengan f (0.01) = 0.02. Dalama langkah ini kita mendapatkan titik koordinat (0.01, 0.02) 3. Berikutnya, kita akan menggunakan f (0.01) = 0.02 sebagai input baru dengan cara menarik garis horisontal dari titik koordinat (0.01, 0.02) hing-
A–1
A–2
ga berpotongan dengan y = x. Kita peroleh titik koordinat berikutnya (0.02, 0.02). 4. Berikutnya kita mencari f (0.02) dengan cara menarik garis vertikal hingga memotong fungsi f = 2x seperti yang dilakukan pada langkah pertama. 5. Langkah-langkah ini dilakukan seterusnya secara berulang hingga sejumlah iterasi tertentu yang diinginkan.
LAMPIRAN B CONTOH CIPHER BLOK SPN Cipher blok yang digunakan dalam disertasi ini memiliki struktur jaringan subtitusi dan permutasi (subtitution and permutation network yang disingkat sebagai SPN). Cipher blok ini (lihat Gambar B.1) memiliki blok input dengan panjang 16-bit dan 4-ronde. Setiap ronde terdiri dari tiga operasi dasar yaitu (1) subtitusi, (2) permutasi dan (3) pengacakan dengan kunci. Operasi-operasi dasar ini telah diusulkan oleh Feistel pada tahun 1973 dan memiliki kemiripan dengan operasi-operasi yang digunakan dalam DES dan beberapa cipher blok modern, misalnya AES (Rinjdael). Jadi, meskipun cipher blok yang digunakan dalam disertasi ini merupakan versi yang disederhanakan dari cipher blok standar, namun teknik analisis terhadap cipher sederhana ini tetap dapat diterapkan terhadap cipher yang lebih kompleks1 (Heys, 2001).
Deskripsi Fungsi Subtitusi Dalam cipher ini, blok data sepanjang 16-bit akan dibagi lagi menjadi 4 sub-blok yang masing-masing memilik panjang 4-bit. Setiap sub-blok ini akan menjadi input S-Box yang berukuran 4 × 4 yang diimplemetasikan dengan lookup table yang berisi sejumlah 16 nilai-nilai 4-bit. Karakteristik dasar dari S-Box adalah pemetaan nonlinear, artinya keluaran S-Box tidak dapat direpresentasikan sebagai operasi linear dari bit-bit input. Cipher ini menggunakan pemetaan yang sama untuk seluruh S-Box. Pemetaan yang dipilih untuk cipher ini , yang diperlihatkan dalam Tabel B.1, diambil dari S-Box DES (yaitu baris pertama dari S-Box pertama). Berdasarkan tabel ini, bit paling signifikan (msb) dari notasi heksadesimal merepresentasikan bit paling kiri S-Box dalam Gambar B.1). masukan keluaran
0 E
1 4
2 D
3 1
4 2
5 F
6 B
7 8
8 3
9 A
A 6
B C
C 5
D 9
E 0
F 7
Tabel B.1. Representasi S-Box dalam heksadesimal 1
Analisis terhadap cipher yang lebih kompleks tentu membutuhkan sumber daya yang lebih tinggi
B–1
B–2
Gambar B.1. Cipher blok jaringan subtitusi dan permutasi (SPN) dasar
B–3
Deskripsi Fungsi Permutasi Operasi permutasi merupakan operasi transposisi bit atau pertukaran posisi bit. Permutasi dari Gambar B.1) dapat diberikan dalam Tabel B.2. Angka dalam tabel menyatakan posisi bit dalam cipher blok dengan 1 merupakan posisi bit paling kiri dan 16 merupakan posisi bit paling kanan. masukan keluaran
1 1
2 5
3 9
4 13
5 2
6 6
7 10
8 14
9 3
10 7
11 11
12 15
13 4
14 8
15 12
16 16
Tabel B.2. Tabel permutasi
Deskripsi Pengacakan dengan Kunci Pengacakan dengan kunci dilakukan dengan menggunakan fungsi sederhana exclusive-OR bit per bit antara bit-bit kunci untuk ronde tertentu dengan masukan data blok untuk ronde tersebut. Sebuah sub-kunci ditambahkan setelah ronde terakhir untuk menjamin agar subtitusi pada ronde terakhir tidak dapat diabaikan oleh penyerang. Semua subkunci diturunkan dari kunci utama (master key) dengan menggunakan algoritma penjadwalan kunci (key schedulling algorithm). Kunci utama yang digunakan memiliki panjang 32-bit, sehingga dapat kita nyatakan sebagai K = (k1 , k − 2, . . . , k3 2) ∈ {0, 1}32 . Algoritma penjadwalan kunci adalah sebagai berikut (Stinson, 2002): untuk 1 ≤ r ≤ 5 definisikan subkunci ke-r atau K r terdiri dari 16-bit yang berurutan dari kunci utama K, dimulai dari k4r−3 . Sebagai contoh, untuk K = 0011 1010 1001 0100 1101 0110 0011 1111 akan diperoleh subkunci K 1 = 0011 1010 1001 0100 K 2 = 1010 1001 0100 1101 K 3 = 1001 0100 1101 0110 K 4 = 0100 1101 0110 0011 K 5 = 1101 0110 0011 1111.
B–4
Algoritma penjadwalan kunci ini bukan merupakan algoritma yang aman. Namun karena tujuan dari penggunakan cipher blok dalam disertasi ini adalah untuk mengidentifikasi subkunci terakhir dengan mengasumsikan subkunci-subkunci yang lain dapat diidentifikasi dengan teknik kriptanalisis yang sama, maka algoritma ini tetap dapat digunakan.
Proses Dekripsi Dekripsi dilakukan dengan cara memproses ciphertext dalam arah yang berlawanan dengan proses enkripsi sehingga proses dekripsi juga melewati struktur berbentuk SPN. Pemetaan S-Box yang digunakan dalam jaringan dekripsi merupakan invers dari pemetaan S-Box proses enkripsi. Karena itu, agar jaringan SPN dapat melakukan proses dekripsi, seluruh S-Box harus merupakan pemetaan bijektif yaitu pemetaaan satu ke satu dengan jumlah bit yang sama antara masukan dengan keluaran. Dalam proses dekripsi, subkunci digunakan dalam urutan yang terbalik.
LAMPIRAN C PILIHAN BIT-BIT DALAM KRIPTANALISIS LINEAR DAN DIFERENSIAL Penjelasan mengenai kriptanalisis linear dan diferensial secara lengkap dapat dilihat di Heys (2001). Langkah awal kriptanalisis sebagaimana yang dijelaskan dalam peper tersebut adalah mendapatkan aproksimasi linear (untuk kriptanalisis linear) dan karakteristik diferensial (untuk kriptanalisis diferensial). Gambar C.1 menunjukkan aproksimasi linear dan pilihan bit-bit yang dihasilkan. Gambar C.2 menunjukkan karakteristik diferensial dan pilihan bit-bit yang dihasilkan.
C–1
C–2
Gambar C.1. Aproksimasi linear dan pilihan bit-bit yang dihasilkan
C–3
Gambar C.2. Karakteristik diferensial dan pilihan bit-bit yang dihasilkan
LAMPIRAN D LINGKUNGAN EKSPERIMEN Eksperimen analisis keacakan (Bab V) dan kriptanalisis (Bab VI) dilakukan dalam lingkungan pemrograman sebagai berikut: • Seluruh implementasi program dilakukan dalam lingkungan Matlab dan terdiri dari – implementasi cipher blok SPN – implementasi algoritma analisis keacakan dan kriptanalisis • Beberapa instruksi bawaan (built-in) dari Matlab yang digunakan dalam eksperimen diantaranya (yang terpenting) adalah – instruksi >>q=randperm(n) dengan n merupakan bilangan integer dan q adalah matrik baris dengan komponen-komponennya merupakan bilangan integer. Instruksi ini digunakan untuk melakukan permutasi deret bilangan integer 1, 2, . . . , n. Dalam disertasi ini, instruksi tersebut digunakan untuk memilih nilai awal iterasi secara acak sebagaimana yang dijelaskan di bagian skenario pengambilan data di Bab ... dan Bab .... Instruksi tersebut menjalankan instruksi lain yaitu >>rand(1,n) sehingga karakteristik keacakan instruksi yang pertama tergantung dari instruksi yang terakhir. Instruksi yang terakhir menggunakan algoritma pembangkit bilangan acak Marsenne Twister (oleh Nishimura and Matsumoto) yang membangkitkan nilai-nilai double-precision dalam 19937 interval tertutup [2−53 , 1 − 2−53 ] dengan periode 2 2 −1 . – instruksi >>[p,table,stats] = anova1(X) >>[c,m] = multcompare(stats)
D–1
D–2
Perintah ini memperlakukan kolom-kolom yang berbeda dari matrik X sebagai himpunan-himpunan data yang berbeda. Dua perintah ini digunakan untuk melakukan uji perbandingan jamak (multiple comparison test) yaitu untuk menentukan himpunan data yang mana saja yang memiliki mean yang berbeda secara signifikan. Dalam eksperimen analisis keacakan, perintah ini digunakan untuk membedakan kelompok-kelompok data RMS bias ternormalisasi yang dihasilkan oleh cipher blok dengan jumlah ronde yang berbeda. Dalam eksperimen kriptanalisis, perintah ini digunakan untuk membedakan data RMS bias ternormalisasi yang dihasilkan oleh beberapa alternatif nilai yang berbeda dari bagian subkunci tertentu.
LAMPIRAN E BARIS PROGRAM Lampiran ini memuat baris-baris program terpenting yang digunakan sebagai saranan eksperimen dalam disertasi ini.
Fungsi Cipher Blok SPN Keterangan: y untuk teks-cipher, x untuk teks-plain, K untuk kunci master dan Nr untuk jumlah ronde f u n c t i o n [ y ] = b i t S P N ( x , K, Nr ) % K dalam b i n e r % x dalam b i n e r l =4; m= 4 ; f u n c t i o n y= p i _ s ( x ) % i n i adalah f u n g s i s u b t i t u s i % i n i adalah f u n g s i s u b t i t u s i switch x (1) case ’0 ’ switch x (2) case ’0 ’ switch x (3) case ’0 ’ switch x (4) case ’0 ’ y = [ ’ 1110 ’ ] ; case ’1 ’ y = [ ’ 0100 ’ ] ; end case ’1 ’ switch x (4) case ’0 ’ y = [ ’ 1101 ’ ] ; case ’1 ’ y = [ ’ 0001 ’ ] ; end end case ’1 ’ switch x (3) case ’0 ’
E–1
E–2
switch x (4) case ’0 ’ y = [ ’ 0010 ’ ] ; case ’1 ’ y = [ ’ 1111 ’ ] ; end case ’1 ’ switch x (4) case ’0 ’ y = [ ’ 1011 ’ ] ; case ’1 ’ y = [ ’ 1000 ’ ] ; end end end case ’1 ’ switch x (2) case ’0 ’ switch x (3) case ’0 ’ switch x (4) case ’0 ’ y = [ ’ 0011 ’ ] ; case ’1 ’ y = [ ’ 1010 ’ ] ; end case ’1 ’ switch x (4) case ’0 ’ y = [ ’ 0110 ’ ] ; case ’1 ’ y = [ ’ 1100 ’ ] ; end end case ’1 ’ switch x (3) case ’0 ’ switch x (4) case ’0 ’ y = [ ’ 0101 ’ ] ; case ’1 ’ y = [ ’ 1001 ’ ] ;
E–3
end case ’1 ’ switch x (4) case ’0 ’ y = [ ’ 0000 ’ ] ; case ’1 ’ y = [ ’ 0111 ’ ] ; end end end end end f u n c t i o n y= p i _ p ( x ) % i n i adalah f u n g s i permutasi y = [ x ( 1 ) x ( 5 ) x ( 9 ) x ( 1 3 ) x ( 2 ) x ( 6 ) x ( 1 0 ) x ( 1 4 ) x ( 3 ) x ( 7 ) ...ke-baris-berikutnya x (11) x (15) x (4) x (8) x (12) x (16) ] ; end f u n c t i o n K_r= s c h e d u l e (K, Nr ) % i n i a d a l a h b a g i a n yg m e l a k u k a n key s c h e d u l l i n g % p a n j a n g k u n c i K a d a l a h 32 b i t f o r i = 1 : Nr+1 K_r ( i , : ) =K ( ( i −1) ∗ 4 + 1 : ( i −1) ∗ 4 + 1 6 ) ; end end % f u n g s i SPN K_r= s c h e d u l e (K, Nr ) ; w= ( x ) ; f o r r = 1 : Nr−1 u= d e c 2 b i n ( b i t x o r ( b i n 2 d e c (w) , b i n 2 d e c ( K_r ( r , : ) ) ) , 1 6 ) ; f o r i = 1 :m v ( 1 + l ∗ ( i −1) : l ∗ ( i ) ) = p i _ s ( u ( 1 + l ∗ ( i −1) : l ∗ ( i ) ) ) ; end w= p i _ p ( v ) ; end u= d e c 2 b i n ( b i t x o r ( b i n 2 d e c (w) , b i n 2 d e c ( K_r ( Nr , : ) ) ) , 1 6 ) ; f o r i = 1 :m v ( 1 + l ∗ ( i −1) : l ∗ ( i ) ) = p i _ s ( u ( 1 + l ∗ ( i −1) : l ∗ ( i ) ) ) ; end y= d e c 2 b i n ( b i t x o r ( b i n 2 d e c ( v ) ,
E–4
b i n 2 d e c ( K_r ( Nr + 1 , : ) ) ) , 1 6 ) ; end
Pembangkitan dan Pengaturan Data Bagian ini berisi baris-baris program yang digunakan untuk membangkitkan data eksperimen, memilih bit-bit tertentu dari data eksperimen hingga membangkitkan deret acak aktual. 1. Fungsi Pembangkit Data Eksperimen Keterangan: y untuk data yang dibangkitkan, initial untuk jumlah nilai awal, K untuk nilai kunci master, Nr untuk jumlah ronde dan num_data untuk jumlah iterasi. f u n c t i o n [ y ] = g e n e r a t e _ S P N ( i n i t i a l , K, Nr , num_data ) %a=randperm ( 2 ^ 1 6 ) ; a1=d e c 2 b i n ( a ( 1 ) , 1 6 ) ; y(1 ,:)= initial ; %% ITERASI DENGAN FEEDBACK i t e r a s i = num_data ; for i =1: i t e r a s i y ( i + 1 , : ) = b i t S P N ( y ( i , : ) ,K, Nr ) ; end
2. Bagian Program Pembangkit Data Eksperimen Bagian program ini membangkitkan data eksperimen datak dengan menggunakan kunci K dan jumlah ronde Nr yang ditentukan. Banyaknya nilai awal adalah num_initial dengan tiap-tiap nilai awal dibangkitkan secara acak menggunakan fungsi randperm. for i =1: n u m _ i n i t i a l aperm =randperm ( 2 ^ 1 6 ) ; a= d e c 2 b i n ( aperm ( 1 ) , 1 6 ) ; i n i t i a l ( i , : ) =a ; end %% %% Membangkitkan d a t a dengan s k e n a r i o a d a p t i v e ...ke-baris-berikutnya chosen p l a i n t e x t a t t a c k for i =1: n u m _ i n i t i a l y ( : , : , i ) = g e n e r a t e _ S P N ( i n i t i a l ( i , : ) ,K, Nr , ...ke-baris-berikutnya data_length ) ; end
E–5
3. Bagian Program Penginversi Satu Ronde Baris-baris program berikut ini digunakan untuk melakukan inversi satu ronde terakhir dari cipher blok. Masukan dari proses ini adalah matrik datak dan keluarannya adalah matrik inv dataUkx1 sebagaimana yang dijelaskan dalam Subbab VI.2.2. Selanjut nya datak dan inv dataUkx1 akan ditata untuk menghasilkan matrik Skx . Keterangan: bit_chosen adalah urutan bit dari teks-cipher yang akan diinvers satu ronde. b i t _ c h o s e n = [ [ 1 2 3 4 9 10 11 1 2 ] ] ; K _ l a s t r o u n d _ t r u e =K_r ( Nr +1 , b i t _ c h o s e n ) ; ukur_key= s i z e ( b i t _ c h o s e n ) ; u k u r _ k e y _ a n a l y s i s =ukur_key ( 2 ) ; %%Membangkitkan s e l u r u h a l t e r n a t i f k u n c i n u m _ k e y _ a n a l y s i s =2^ u k u r _ k e y _ a n a l y s i s ; for i =1: num_key_analysis K _ l a s t r o u n d _ g u e s s ( i , : ) = [ d e c 2 b i n ( i −1 , ...ke-baris-berikutnya ukur_key_analysis ) ] ; end %−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− %I n v e r s dengan menggunakan k u n c i t e b a k a n y 4 _ l a s t r o u n d =y4 ( : , b i t _ c h o s e n , : ) ; u k u r _ y 4 = s i z e ( y4 ) ; for k =1: num_key_analysis for i =1: n u m _ i n i t i a l for j =1: ukur_y4 ( 1 ) y 4 2 _ b e f o r e _ l a s t r o u n d ( j , : , i , k ) =...ke-baris-berikutnya a n a l i s i s _ i n v e r s _ s u b b i t ( y 4 _ l a s t r o u n d ...ke-baris-berikutnya ( j , : , i ) , K_lastround_guess (k , : ) ) ; end end k end %−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Baris program fungsi analisis_invers_subbit dapat dilihat di bawah ini. Keterangan: Ksubbit adalah subkunci yang digunakan untuk menginvers satu ronde dan y adalah teks-cipher. f u n c t i o n y _ i n v e r s = a n a l i s i s _ i n v e r s _ s u b b i t ( y , K s u b b i t ...ke-baris-berikutnya )
E–6
ukury= s i z e ( y ) ; f u n c t i o n y= i n v _ p i _ s ( x ) % i n i adalah i n v e r s f u n g s i s u b t i t u s i switch x (1) case ’0 ’ switch x (2) case ’0 ’ switch x (3) case ’0 ’ switch x (4) case ’0 ’ y = [ ’ 1110 ’ ...ke-baris-berikutnya ]; case ’1 ’ y = [ ’ 0011 ’ ...ke-baris-berikutnya ]; end case ’1 ’ switch x (4) case ’0 ’ y = [ ’ 0100 ’ ...ke-baris-berikutnya ]; case ’1 ’ y = [ ’ 1000 ’ ...ke-baris-berikutnya ]; end end case ’1 ’ switch x (3) case ’0 ’ switch x (4) case ’0 ’ y = [ ’ 0001 ’ ...ke-baris-berikutnya ]; case ’1 ’ y = [ ’ 1100 ’ ...ke-baris-berikutnya ]; end case ’1 ’ switch x (4) case ’0 ’ y = [ ’ 1010 ’ ...ke-baris-berikutnya ]; case ’1 ’
E–7
y = [ ’ 1111 ’ ...ke-baris-berikutnya ]; end end end case ’1 ’ switch x (2) case ’0 ’ switch x (3) case ’0 ’ switch x (4) case ’0 ’ y = [ ’ 0111 ’ ...ke-baris-berikutnya ]; case ’1 ’ y = [ ’ 1101 ’ ...ke-baris-berikutnya ]; end case ’1 ’ switch x (4) case ’0 ’ y = [ ’ 1001 ’ ...ke-baris-berikutnya ]; case ’1 ’ y = [ ’ 0110 ’ ...ke-baris-berikutnya ]; end end case ’1 ’ switch x (3) case ’0 ’ switch x (4) case ’0 ’ y = [ ’ 1011 ’ ...ke-baris-berikutnya ]; case ’1 ’ y = [ ’ 0010 ’ ...ke-baris-berikutnya ]; end case ’1 ’ switch x (4) case ’0 ’ y = [ ’ 0000 ’ ...ke-baris-berikutnya ];
E–8
case ’1 ’ y = [ ’ 0101 ’ ...ke-baris-berikutnya ]; end end end end end m= 4 ; l = 4 ; for i =1: ukury ( 1 ) v= d e c 2 b i n ( b i t x o r ( b i n 2 d e c ( y ) , b i n 2 d e c ( K s u b b i t ) ) , ...ke-baris-berikutnya ukury ( 2 ) ) ; end for i =1: ukury ( 2 ) / l y _ i n v e r s ( 1 + l ∗ ( i −1) : l ∗ ( i ) ) = i n v _ p i _ s ( v ( 1 + l ∗ ( i −1) ...ke-baris-berikutnya : l ∗( i ) ) ) ; end end
4. Bagian Program Pengambil Bit-Bit yang akan Digunakan untuk Kriptanalisis Berikut ini adalah contoh bagian program yang digunakan untuk mengambil bit-bit tertentu dari matrik Skx dalam Subbab VI.2.3. Proses ini akan menghasilkan matrik Tkx yang dijelaskan dalam Subbab yang sama. Bit-bit yang dipilih dapat dilihat di Gambar VI.16. Keterangan: num_key_analysis adalah banyaknya kandidat bagian subkunci yang akan dianalisis, num_initial adalah banyaknya kondisi awal. for i =1: num_key_analysis for k =1: n u m _ i n i t i a l f o r j = 1 : u k u r _ y 4 ( 1 ) −1 d a t a _ a n a l i s i s ( j , : , k , i ) = [ y4 ( j , 5 : 6 , k ) y4 ...ke-baris-berikutnya ( j , 7 : 8 , k ) y 4 2 _ b e f o r e _ l a s t r o u n d ( j ...ke-baris-berikutnya + 1 , 2 , k , i ) y 4 2 _ b e f o r e _ l a s t r o u n d ( j ...ke-baris-berikutnya + 1 , 4 , k , i ) y 4 2 _ b e f o r e _ l a s t r o u n d ( j ...ke-baris-berikutnya + 1 , 6 , k , i ) y 4 2 _ b e f o r e _ l a s t r o u n d ( j ...ke-baris-berikutnya +1 ,8 ,k , i ) ] ; %d a t a _ a n a l i s i s ( j , : , k , i ) =[ ...ke-baris-berikutnya y 4 _ b e f o r e _ l a s t r o u n d ( j + 1 , 1 : 4 , k , i ) ...ke-baris-berikutnya y4_before_lastround ( j +1 ,5:8 , k , i ) ] ; end end end
E–9
5. Fungsi Pembangkit Deret Acak Aktual Fungsi ini membangkitkan deret acak aktual berdasarkan data eksperimen. Masukan dari fungsi ini adalah matrik Tkx seperti yang dijelaskan dalam Subbab VI.2.4. Keterangan: stream adalah matrik yang berisi beberapa deret acak aktual, y adalah data eksperimen yang dibangkitkan cipher blok. f u n c t i o n [ s t r e a m ]= s t r e a m _ g e n _ b i t _ k r i p t ( y ) ukur_y= s i z e ( y ) ; for i =1: ukur_y ( 1 ) stream ( i )=bin2dec ( y ( i , : ) ) ; end
Proses Analisis Bagian ini memuat baris-baris program skema permainan kaotik, pengukuran keluaran skema permainan kaotik, hingga pembedaan RMS bias ternormalisasi yang dihasilkan. 1. Fungsi Permainan Kaotik Fungsi ini membangkitkan himpunan titik X dengan menggunakan skema permainan kaotik. Keterangan: x untuk himpunan titik keluaran permainan kaotik, x_0 untuk nilai koordinat awal, stream untuk beberapa deret acak yang menjadi inpun permainan kaotik dan num_state untuk jumlah simbol yang digunakan oleh permainan kaotik. f u n c t i o n [ x ] = f r a k t a l _ r e c t a n g l e ( x0 , s t r e a m , n u m _ s t a t e ...ke-baris-berikutnya ) K= [ 0 ; 0 ] ; pojok =100; ukur_stream= size ( stream ) ; pangkat2=log2 ( num_state ) ; pangkat2_1= fl oo r ( pangkat2 / 2 ) ; p a n g k a t 2 _ 2 = p a n g k a t 2 −p a n g k a t 2 _ 1 ; sk al a =[1/2^ pangkat2_1 ; 1 / 2 ^ pangkat2_2 ] ; x ( : , 1 ) =x0 ; for i =1: ukur_stream ( 2 ) g e s e r _ x =mod ( s t r e a m ( i ) , 2 ^ p a n g k a t 2 _ 1 ) ∗ p o j o k ∗ ...ke-baris-berikutnya skala (1) ;
E–10
g e s e r _ y = f l o o r ( s t r e a m ( i ) / 2 ^ p a n g k a t 2 _ 1 ) ∗ p o j o k ∗ ...ke-baris-berikutnya skala (2) ; s k a l i n g _ k o o r d i n a t = [ s k a l a ( 1 ) ∗ ( x ( 1 , i ) +K( 1 ) ) ; s k a l a ( 2 ) ∗ ( x ( 2 , i ) +K( 2 ) ) ] ; x ( : , i +1)= s k a l i n g _ k o o r d i n a t +[ g e s e r _ x ; g e s e r _ y ] ; end
2. Fungsi Penghitung Distribusi Titik Keluaran Permainan Kaotik Fungsi ini mengimplementasikan konsep perhitungan ukuran terhadap himpunan titik X keluaran permainan kaotik dengan menggunakan bidangbidang bujur sangkar Bi . Keterangan: x adalah himpunan titik keluaran skema permainan kaotik, counter adalah vektor dengan setiap komponennya menyatakan jumlah titik dalam setiap bujur sangkar Bi , measure adalah vektor dengan setiap komponennya menyatakan proporsi titik dalam setiap bujur sangkar Bi , normal_bias f u n c t i o n [ c o u n t e r , measure , n o r m a l _ b i a s ] = ...ke-baris-berikutnya circle_count100_9_kript_rev (x) ukur_x= s i z e ( x ) ; s i s i =35; expected_prob_konstanta =(100/ s i s i ) ^2/10000; counter =zeros ( s i s i ^2 ,1) ; measure= zeros ( s i s i ^2 ,1) ; for i =1: ukur_x ( 2 ) koord_x= f l o o r ( x ( 1 , i ) / ( 1 0 0 / s i s i ) ) ; koord_y= f l o o r ( x ( 2 , i ) / ( 1 0 0 / s i s i ) ) ; u r u t a n =koord_y ∗ s i s i +koord_x +1; c o u n t e r ( u r u t a n ) = c o u n t e r ( u r u t a n ) +1; end ukur_counter= size ( counter ) ; ukur_measure= s i z e ( measure ) ; f o r k = 1 : s i s i ^2 measure ( k ) = c o u n t e r ( k ) / ukur_x ( 2 ) ; end e x p e c t e d _ p r o b = o n e s ( u k u r _ m e a s u r e ) ∗ ...ke-baris-berikutnya expected_prob_konstanta ; n o r m a l _ b i a s = ( measure −e x p e c t e d _ p r o b ) / ...ke-baris-berikutnya expected_prob_konstanta ; end
E–11
3. Fungsi Penganalisis Cipher Blok Fungsi ini digunakan dalam analisis cipher blok dan menghasilkan RMS bias ternormalisasi dengan matrik data Tkx (lihat skenario pengaturan data di Subbab VI.2.3) sebagai input. Keterangan: kunci-kunci kandidat yang akan dianalisis berada diantara nilai keystart dan keyend, data_analisis adalah bit-bit tertentu himpunan data teks-cipher dan teks-plain yang telah dipilih dan digunakan dalam proses kriptanalisis selanjutnya. f u n c t i o n [ x _ d a t a _ a n a l i s i s , m e a s u r e _ d a t a _ a n a l i s i s , ...ke-baris-berikutnya n o r m a l _ b i a s _ d a t a _ a n a l i s i s , ...ke-baris-berikutnya r m s _ n o r m a l _ b i a s _ d a t a _ a n a l i s i s ] = ...ke-baris-berikutnya b l o c k _ c i p h e r _ k r i p t a n a l i s i s 2 ( k e y s t a r t , keyend , ...ke-baris-berikutnya data_analisis ) x0 = [ 3 0 ; 3 0 ] ; ukur_data_analisis=size ( data_analisis ) ; n u m _ s t a t e =2^ u k u r _ d a t a _ a n a l i s i s ( 2 ) ; for j = k e y s t a r t : keyend for i =1: u k u r _ d a t a _ a n a l i s i s ( 3 ) [ s t r e a m _ d a t a _ a n a l i s i s ( i , : , j ) ] = ...ke-baris-berikutnya s t r e a m _ g e n _ b i t _ k r i p t ( d a t a _ a n a l i s i s ( : , : , ...ke-baris-berikutnya i ,j)); [ x _ d a t a _ a n a l i s i s ( : , : , i , j ) ] = ...ke-baris-berikutnya f r a k t a l _ r e c t a n g l e ( x0 , ...ke-baris-berikutnya s t r e a m _ d a t a _ a n a l i s i s ( i , : , j ) , num_state ) ; [ c o u n t e r _ d a t a _ a n a l i s i s ( : , i , j ) , ...ke-baris-berikutnya m e a s u r e _ d a t a _ a n a l i s i s ( : , i , j ) , ...ke-baris-berikutnya n o r m a l _ b i a s _ d a t a _ a n a l i s i s ( : , i , j ) ] = ...ke-baris-berikutnya c i r c l e _ c o u n t 1 0 0 _ 9 _ k r i p t _ r e v ( ...ke-baris-berikutnya x_data_analisis (: ,: , i , j ) ) ; end ukur_rms= s i z e ( n o r m a l _ b i a s _ d a t a _ a n a l i s i s ) ; for i =1: u k u r _ d a t a _ a n a l i s i s ( 3 ) r m s _ n o r m a l _ b i a s _ d a t a _ a n a l i s i s ( i , 1 , j ) = s q r t ...ke-baris-berikutnya ( ( n o r m a l _ b i a s _ d a t a _ a n a l i s i s ( : , i , j ) ’∗ ...ke-baris-berikutnya n o r m a l _ b i a s _ d a t a _ a n a l i s i s ( : , i , j ) ) / ...ke-baris-berikutnya ukur_rms ( 1 ) ) ; end j
E–12
end end
4. Bagian Program Penghasil Matrik RMS Bias Ternormalisasi Bagian program ini menghasilkan matrik RMS bias ternormalisasi dengan menggunakan fungsi block_cipher_kriptanalisis2. Bagian pro x seperti yang dijelaskan di Subbab gram ini menghasilkan RM S biasknorm kx VI.2.4. Matrik RM S biasnorm ini dimuat dalam data_buffer_test arrange_data ; [ x _ d a t a _ a n a l i s i s , m e a s u r e _ d a t a _ a n a l i s i s , ...ke-baris-berikutnya n o r m a l _ b i a s _ d a t a _ a n a l i s i s , ...ke-baris-berikutnya r m s _ n o r m a l _ b i a s _ d a t a _ a n a l i s i s ] = ...ke-baris-berikutnya b l o c k _ c i p h e r _ k r i p t a n a l i s i s 2 ( k e y s t a r t , keyend , ...ke-baris-berikutnya data_analisis ) ; data=rms_normal_bias_data_analisis ( : , : , keystart ) ; for i = k e y s t a r t +1: keyend d a t a = [ d a t a r m s _ n o r m a l _ b i a s _ d a t a _ a n a l i s i s ( : , : , i ...ke-baris-berikutnya ) ]; end data_buffer_test =data
5. Bagian Program Pembeda Himpunan Data dari Matrik RMS Bias Ternormalisasi Bagian program ini menggunakan paket perintah anova1 dan multcompare yang disediakan oleh toolboxes analisis statistik yang x dimiliki Matlab. Masukan dari program ini adalah matrik RM S biasknorm yang dimuat dalam data_buffer_test. [ p , t b l , s t a t s ] = anova1 ( d a t a _ b u f f e r _ t e s t ) ; figure statsdata_buffer_test=stats ; [ c ,m] = m u l t c o m p a r e ( s t a t s ) ;