Analisis Sandi Linear Terhadap Ciphertext Dengan menggunakan arsitektur SPN

Abstrak

Analisis sandi linear merupakan seranga (attack) yang paling penting untuk digunakan pada kode blok kunci simetri modern yang berbasis komputer. Analisis ini didasarkan pada analisis kode jaringan Subtitusi-Permutasi dasar yang sederhana dan terstruktur.

Memahami serangan (attack) dengan jenis ini sangat penting, karena kode Rijndael yang dijadikan standar enkripsi terbaru Amerika Serikat, AES yang merupakan pelanjut DES yang menjadi standar enkripsi

BAB

PENDAHULUAN

Analisis Sandi Linear diperkenalkan oleh Matsui pada Eurocrypt tahun 1993 sebagai attact teoritis pada Data Encryption Standard (DES) dan kemudian cukup berhasil secara aplikatif pada DES, DES adalah suatu algoritma enkripsi block cipher yang didefinisikan dan didukung oleh pemerintah Amerika Serikat, dan pada tahun 1977 dijadikan standar resmi, DES menggunakan kunci 56-bit untuk me-enkripsi blok data 64-bit.

Analisis sandi linear ini merupakan attack yang paling penting, yang digunakan pada kode blok kunci simetri modern yang berbasis komputer. Memahami attack jenis ini sangat penting karena kode Rijndael yang dijadikan standar enkripsi terbaru Amerika Serikat, Advanced Encryption Standard (AES) yang merupakan pelanjut DES yang menjadi standar de-facto enkripsi di dunia, menggunakan arsitektur Subtitution-Permutation Network (SPN) ini. Oleh karena itu analisis sandi linear, pengkajiannya didasarkan pada analisis kode jaringan Subtitusi-Permutasi dasar yang sederhana dan terstruktur.

Meskipun pada awalnya anailsis sandi ini digunakan untuk menyerang DES (karena menjadi standar internasional), anailsis sandi ini juga sangat bermanfaat untuk mengukur kekuatan Algoritma enkripsi lainnya, karena banyaknya calon Algoritma yang didaftarkan untuk menjadi Advanced Encryption Standard (AES), didesain untuk menahan serangan analisis sandi ini.

1.1 Kode Sandi SPN Dasar

Kode rahasia yang akan dibahas menggunakan kode sandi SPN dasar, dimana kode sandiini memiliki masukan 16 bit plaintext, dengan 4 ronde tahapan enkripsi. Setiap ronde terdiri dari :

1. subtitusi (kotak S11....S44),

2. transposisi (permutasi), misalnya bit ke-2 (keluaran dari ronde ke-1) menjadi bit ke-5 (masukan pada ronde ke-2),

3. pencampuran kunci, dimana setiap bit kunci di-XOR-kan dengan plaintext dan ciphertext sementara (keluaran kotak-S).  

1.2 Substitusi

Plaintext 16-bit yang kita miliki dipecah menjadi empat sub-b!ok 4-bit. Setiap sub-blok menjadi masukan ke dalam kotak-S 4 x 4 (kotak subtitusi dengan masukan 4-bit dan keluaran 4-bit), yang dengan mudah dapat diimplementasikan dengan tabel lookup dari  nilai 4-bit, yang diberi indek dengan integer yang dinyatakan dengan masukan 4-bit. Sifat yang paling fundamental dari kotak-S adalah memiliki pemetaan yang tidak linear, sehingga, keluaran kotak subtitusi tidak dapat dinyatakan sebagai operasi linear dari masukannya. untuk kode ini, kita menggunakan pemetaan tidak linear yang sama untuk semua kotak-S. Pada DES, ke-8 kotak-S jalan satu ronde berbeda. sedangkan seluruh ronde nenggunakan sekumpulan Kotak-S yang sama). Analisis sandi linear dapat digunakan untuk semua kasus ini. Pemetaan kotak-S dicantumkan pada tabel XX, diambil dari kotak-S pertama dan baris pertama milik DES. Most Significant Bit (MSB) terletak pada bit paling kiri.

1.3 Permutasi

Permutasi merupakan transposisi bit-bit atau pertukaran urutan bit. Bila urutan bit-bit semula adalah 1,2,3,.....16 secara berurutan, maka setelah permutasi, urutan bit-bit menjadi 1,5,9,13,2,6,10,14,3,7,11,15,4,8,12,16. Bit 1 menempati bit paling kiri. Setelah permutasi, bit ke-2 menjadi bit ke-5, bit ke-3 menjadi bit ke-9 dan seterusnya.

Masukkan 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Keluaran 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 16

1.3 Pencampuran Kunci

Untuk memberikan peran kepada kunci dalam proses enkripsi dan dekripsi, maka dapat dilakukan pencampuran kunci yang dalam contoh ini berupa XOR antara bit-bit kunci (biasanya berupa subkey) dengan masukan blok data dalam setiap ronde. Kunci yang terletak pada awal dan aknir ronde diberikan untuk meningkatkan keamanan kode rahasia. Pada umumnya kunci-kunci di atas diturunkan dari kunci master yang lebih pendek melalui proses pengaturan kunci. Pada contoh ini, dianggap tidak ada proses pengaturan kunci, sehingga kunci-kunci di atas dianggap dibuat secara independen dan tidak berkorelasi.

2. Analisis Sandi Linear

Pada bagian ini, kita kan membicarakan proses attack kode rahasia menggunakan Analisis Sandi Linear. Analisis Sandi Linear menggunakan tingginya peluang terjadinya ekspesi linear yang mencakup bit-bit plaintext, bit-bit "ciphertext" (bukan ciphertext yang sesungguhnya melainkan masukan untuk ronde terakhir), dan bit-bit subkey. Metoda ini merupakan jenis attack adalah known plaintext attack : sehingga attacker harus mengetahui sekumpulan plaintext dari ciphertext yang berhubungan. Tetapi attacker tidak mempunyai cara untuk memilih plaintext yang mana, dan ciphertext yang berkaitan, yang tersedia. Dalam banyak aplikasi dan skenario sangat masuk akal apabila hal ini terjadi Ide dasarnya adalah pendekatan operasi bagian dari sandi dengan ekspresi yang linear. maka peluang persamaan di atas akan dipenuhi adalah ½ . Penyimpangan dari peluang ½ bagi suatu persamaan u + v di atas, akan menimbulkan kesempatan untuk eksploitasi pada  Analisis Sandi Linear. Semakin besar penyimpangannya, semakin besar pula peiuang Analisis Sandi Linear akan meng-attack sandi. Besar penyimpangan peluang dari ½ ini disebut bias peluang linear. Jadi, bila ekspresi di atas dipenuhi dengan peluang pL untuk sebarang plaintext yang dipilih beserta ciphertext-nya, maka peluang biasnya adalah pL - ½ . Semakin besar nilai mutlak | pL - ½|, semakin baik kemampuan Analisis Sandi Linear untuk memecahkan kunci dengan sedikit plaintext yang diketahui. Terdapat beberapa cara untuk melakukan attack dengan Analisis Sandi Linear. Salah satu cara yaitu dengan meneliti konstruksi pendekatan linear yang berisi bit-bit plaintext (X) dan masukan ke ronde terakhir (atau ekivalen dengan keluaran dari ronde ke-3 untuk kasus ini) yang dinyatakan dengan Y pada persamaan (1). Karena plaintext acak, maka akan mengakibatkan Y juga acak. Persamaan (1) dapat ditulis ulang dan ekivalen dengan penambahan XOR bit-bit sub-kunci di sisi kanannya. Bila pada persamaan (1), tertulis angka 0 pada sisi kanan, maka ini menunjukkan bahwa hasil XOR bit-bit kunci dianggap = 0, dengan peluang pL. Bila pL = 1, maka persamaan (1) merupakan sandi yang memiliki kelemahan yang parah akibat fungsi linear yang sempurna berada dalam algoritma sandi. Bila pL = 0, maka persamaan (1) menyatakan hubungan fungsi affine dalam sandi, yang juga menunjukkan kelemahan yang fatal. Untuk sistem penjumlahan mod-2, fungsi affine merupakan komplemen fungsi linear. Aproksimasi linear dan affine yang ditunjukkan oleh pL >1/2 dan pL < ½ , merujuk pada mudahnya sandi diserang oleh Analisis Sandi Linear. Kita juga dapat menganggap bahwa baik hubungan affine maupun linear yang terdapat dalam sandi adalah linear.

Pertanyaan berikutnya adalah : bagaimana kita dapat menyusun ekspresi yang sangat linear sehingga dapat kita eksploitasi. Ini dilakukan dengan memperhatikan sifat-sifat komponen cipher yang tidak linear dari Kotak-S. Dengan meneliti sifat kotak-S, kita dapat menyusun aproksimasi antara set masukan dan keluaran dalam kotak-S. Kemudian kita dapat menggabungkan aproksimasi linear dari kotak-kotak-S sedemikian sehingga bit-bit antara (bit-bit data yang berada di dalam cipher) dapat dihilangkan pengaruhnya, sehingga kita mendapatkan ekspresi linear yang memiliki bias besar dan hanya mengandung bit-bit plaintext dan bit-bit masukan ronde terakhir.  

2.1 Analisis Komponen Cipher

Sebelum mempelajari attack lebih detil pada keseluruhan cipher, pertama-tama kita memerlukan pengetahuan kelemahan linear kotak-S. Perhatikan diagram blok kotak-S pada  Gambar 2 dengan masukan X = [X1,X2,X3,X4] keluarannya Y = [Y, Y2 Y3 Y4].

2.2 Menyusun Aproksimasi Linear

Sekali informasi aproksimasi linear kotak-S pada SPN disusun, kita memiliki data untuk diolah dengan menentukan aproksimasi linear dari keseluruhan cipher ke dalam bentuk persamaan (1). Ini dapat dicapai dengan menggabungkan aproksimasi linear kotak-kotak- yang tepat. Dengan membangun aproksimasi linear yang mencakup bit-bit plaintext dan data dari keluaran ronde-terakhir-kedua dari kotak-S, attack menjadi sangat dimungkinkan untuk mendapatkan sebagian bit-bit kunci yang terletak setelah ronde terakhir. Contohnya sebagai berikut : Perhatikan suatu aproksimasi yang berisi S12, S22, S32, dan S34 seperti yang ditunjukkan pada Gambar 3. Perhatikan bahwa disini, akan membangun ekspresi untuk 3 ronde pertama cipher dan bukannya 4 ronde penuh. Kita akan melihat bagaimana hal ini berguna untuk mendapatkan bit-bit kunci setelah ronde terakhir.

2.3 Mencari Bit-bit Kunci

Dengan aproksimasi linear (R-l) ronde dari cipher R ronde dengan bias peluang linear yang cukup besar, kita dapat melakukan attack terhadap cipher untuk mendapatkan bit-bit subkey setelah ronde terakhir. Untuk contoh, dimungkinkan mendapatkan bit-bit subkey K5 dari aproksimasi linear 3 ronde. Kita namakan bit-bit yang dicari dari subkey terakhir sebagai target partial subkey. Lebih khusus lagi, bit-bit targec partial subkey adalah bit-bit yang berasal dan subkey terakhir yang berhubungan dengan kotak-S di ronde terakhir yang dipengaruhi oleh bit data yang dimasukkan ke dalam aproksimasi linear.

Proses berikutnya mencakup dekripsi parsial terhadap ronde terakhir cipher. Untuk seluruh nilai target partial subkey yang mungkin, bit-bit ciphertext di-XOR-kan dengan bit-bit target partial subkey dan hasilnya dibalikkan ke kotak-S yang bersesuaian. Hal ini

dilakukan untuk semua sampel plaintext / ciphertext, dan setiap nilai target partial subkey diberi counter. Penambahan counter dilakukan untuk nilai target partial subkey tertentu, yaitu ketika expresi linear dipenuhi untuk bit-bit yang masuk ke dalam kotak-S ronde terakhir (yang ditentukan oleh dekripsi parsial) dan bit-bit plaintext yang diketahui. Nilai target partial subkey yang memiliki counter (penghitung) dengan beda terbesar dari setengah jumlah pasangan plaintext/ciphertext, dianggap menyatakan nilai bit-bit target partial subkey. Hal ini dianggap benar karena diasumsikan bahwa nilai partial subkey yang benar akan menghasilkan aproksimasi linear dipenuhi dengan peluang yang paling jauh dari ½ (tidak peduli apakah berada di atas ataukah di bawah ½ tergantung pada apakah expresi-nya linear atau affine dan ini tergantung pada nilai-nilai subkey yang belum dapat diketahui, yang secara implisit telah dimasukkan ke dalam persamaan linear. Subkey yang tidak tepat dianggap menghasilkan terkaan acak relatif pada bit-bit yang memasuki kotak-S pada ronde terakhir, dan sebagai akibatnya, expresi linear akan dipenuhi dengan peluang mendekati ½ .

3. Kompleksitas Serangan

Merujuk pada kotak-S yang disertakan ke dalam aproksimasi linear sebagai kotak-S aktif  Pada Gambar 3, empat kotak-S pada ronde 1 sampai 3 yang diberi garis tebal merupakan kotak-S aktif. Peluang bahwa expresi linear dipenuhi akan dipengaruhi oleh bias peluang linear dalam kotak-S aktif dan sejumlah kotak-S aktif lainnya. Secara umum, semakin besar bias dalam masing-masing kotak-S, semakin besar pula bias expresi secara keseluruhan. Dan semakin sedikit kotak-S yang aktif, semakin besar pula bias expresi linear secara keseluruhan.

Anggap e menyatakan bias dari peluang ½, bahwa expresi linear untuk cipher lengkap dipenuhi. Meenurut Matsui bahwa jumlah plaintext yang diketahui yang dibutuhkan dalam attack, sebanding dengan e-2 dan bila NL menyatakan jumlah plaintext yang diketahui dan yang diperlukan untuk attack.

Secara praktis, cukup layak untuk mengharapkan sejumlah kelipatan dari e-2 plaintext yang diketahui dan diperlukan, meskipun kompleksitas analisis sandi diukur dalam domain waktu dan ruang, kita merujuk pada data yang dibutuhkan untuk melakukan attack ketika membicarakan kompleksitas analisis sandi. Jadi, dapat diasumsikan bahwa apabila kita dapat memperoleh NL plaintext, maka kita akan dapat memprosesnya. Pendekatan umum untuk memberikan ketahanan terhadap analisis sandi linear telah difokuskan pada optimasi kotak-S (yaitu meminimalkan bias terbesar) dan mencari struktur untuk memaksimalkan jumlah kotak-S yang aktif. Prinsip desain AES merupakan contoh yang istimewa dalam kasus ini. Harus diperhatikan, konsep "terbukti" aman melawan Analisis Sandi Linear, biasanya didasarkan pada tidak ditemukannya aproksimasi linear yang memiliki peluang bias tinggi. Tetapi komputasi peluang aproksimasi linear semacam itu didasarkan pada asumsi bahwa setiap kotak-S saling bebas dan berdasar asumsi bahwa suatu skenario aproksimasi linear (yaitu sekumpulan kotak-S yang aktif) sudah cukup untuk menentukan expresi linear terbaik antara bit-bit plaintext, dan bit-bit data pada masukan ke ronde terakhir.

Kenyataannya adalah bahwa aproksimasi kotak-S tidaklah saling bebas dan ini memberi pengaruh penting terhadap perhitungan peluang. Juga skenario aproksimasi linear yang memasukkan plaintext yang sama dan bit-bit masukan ronde terakhir namun menggunakan set kotak-S aktif yang berbeda, dapat memberi kombinasi yang mengakibatkan peluang linear yang lebih tinggi dari pada yang diperkirakan untuk satu set kotak-S yang aktif.