Jaringan Subtitusi-Permutasi

Nama : jizan Qifli Ilhamdi 

NIM : 17.01.071.054

PRODI : INFORMATIKA

Kelas : Informatika 2017 A

MATA KULIAH : KRIPTOGRAFI 

Jaringan Subtitusi-Permutasi

Properti utama dari block cipher adalah seharusnya seperti permutasi Random. Tentu saja, permutasi yang benar-benar random pasti akan menjadi sempurna. Namun, untuk cipher blok dengan panjang input dan output dari n bit, ukuran tabel yang dibutuhkan untuk memegang permutasi random adalah n · 2ⁿ (ukuran tabel yang dibutuhkan untuk fungsi random itu tidak jauh lebih kecil untuk permutasi random). Jadi, yang kita perlu bagaimana membangun fungsi ringkas seperti yang dirandom.

Paradigma kebingungan-difusi.

Shannon memperkenalkan paradigma dasar untuk membangun singkat mencari fungsi random. Ide dasarnya adalah memecahkan input menjadi beberapa bagian kecil dan kemudian memberi makan bagian-bagian ini melalui fungsi acak kecil yang berbeda. Output dari fungsi-fungsi random ini kemudian dicampur bersama, dan prosesnya diulangi lagi (untuk beberapa kali). Setiap aplikasi fungsi random yang diikuti oleh pencampuran disebut putaran jaringan (konstruksi) sering disebut "jaringan" dan kami menjaga nama ini untuk konsistensi dengan yang lain sumber). Paradigma ini sering diperkenalkan oleh Shannon disebut pendekatan kebingungan-difusi (pada kenyataannya, Shannon sendiri yang menciptakan ini istilah dalam makalah aslinya). Fungsi random kecil memperkenalkan "kebingungan" ke dalam konstruksi. Namun, untuk menyebarkan kebingungan ke seluruh, hasilnya dicampur bersama, mencapai "difusi".

Untuk melihat mengapa difusi diperlukan, pertimbangkan blok-cipher F_k itu bekerja dengan hanya menerapkan fungsi acak kecil untuk setiap porsi 8-bit input. Sekarang, biarkan x dan x’ menjadi nilai yang hanya berbeda pada bit pertama. Itu mengikuti bahwa F_k (x) dan F_k (x’) hanya berbeda dalam byte pertama (karena dalam semua byte lain x sama dengan x’). Dalam fungsi yang benar-benar acak, F_k (x) dan F_k (x’) harus terlihat sangat berbeda, karena setiap nilai output dalam fungsi acak adalah dipilih secara seragam dan independen dari semua nilai output lainnya. Namun, dalam cipher blok imajiner ini di mana difusi tidak digunakan, mereka sama kecuali di byte pertama. Dengan demikian, cipher blok seperti itu sangat jauh dari a fungsi pseudorandom. Pengulangan kebingungan dan difusi memastikan bahwa setiap perubahan kecil pada input akan tercampur dan sebagainya output dari input yang sama akan terlihat sangat berbeda.

Jaringan substitusi-permutasi.

Jaringan substitusi-permutasi adalah implementasi langsung dari paradigma ini. Bagian "substitusi" mengacu pada fungsi acak kecil dan "permutasi" mengacu pada pencampuran output dari fungsi acak. Dalam konteks ini, "permutasi" mengacu pada penataan ulang bit output. Fungsi substitusi kecil disebut S-box. Anda mungkin bertanya pada diri sendiri, di mana kunci rahasia itu masuk? Ada sejumlah kemungkinan jawaban untuk ini, dan berbagai jaringan pergantian-permutasi dapat menggunakan metode yang berbeda. Salah satu kemungkinan adalah memiliki spesifikasi kunci jika S-Box dan pencampuran permutasi. Kemungkinan lain adalah mencampur kunci ke dalam perhitungan di antara setiap putaran substitusi-permutasi (ingat bahwa operasi substitusi-permutasi diulang berkali-kali). Presentasi kami di sini sesuai dengan pendekatan yang terakhir, di mana kuncinya dicampur menjadi hasil antara antara setiap putaran. Ini seringkali hanya dengan cara sederhana Operasi XOR. Artinya, kuncinya adalah XORed dengan hasil antara setelah setiap putaran perhitungan jaringan. Untuk lebih tepatnya, kunci cipher blok disebut sebagai kunci utama,dan subkunci untuk setiap putaran diturunkan dari itu; prosedur derivasi ini adalah dikenal sebagai jadwal kunci. Jadwal kuncinya seringkali sangat sederhana dan dapat bekerja dengan hanya mengambil himpunan bagian dari bit, meskipun kompleks jadwal juga dapat ditentukan.

Poin penting untuk diperhatikan adalah bahwa kita belum menentukan sama sekali bagaimana Kotak-S dan permutasi pencampuran harus dipilih. Kami juga belum fied apakah S-box dan permutasi pencampuran adalah sama atau berbeda di setiap babak. Kami tidak akan mempresentasikan prinsip desain untuk konstruksi S-box “bagus” (dengan satu pengecualian di bawah), dan juga tidak akan dijelaskan bagaimana subkunci harus diturunkan dari kunci master dan bagaimana permutasi harus dipilih.

Meskipun ada dua pilihan desain yang akan sebutkan, yang pertama diperlukan untuk membuat blok cipher permutasi (yaitu, 1-1 dan ke fungsi), dan yang lainnya adalah persyaratan dasar untuk keamanan. Keduanya pilihan berhubungan dengan S-box.

Pilihan desain 1 - keterbalikan S-box.

Dalam substitusi- jaringan permutasi, S-box harus dapat dibalik. Dengan kata lain, mereka harus 1–1 dan ke fungsi. sebaliknya ini adalah Alasan untuk cipher blok tidak akan menjadi permutasi. Di Untuk melihat bahwa membuat S-box 1–1 dan sudah mencukupi, kami menunjukkan itu dengan asumsi ini dimungkinkan untuk sepenuhnya menentukan input yang diberikan output dan kuncinya. Secara khusus, kami menunjukkan bahwa setiap putaran bisa unik terbalik (menghasilkan bahwa seluruh jaringan dapat dibalik dengan bekerja dari akhir kembali ke awal). Demi uraian ini, kami mendefinisikan a bulat terdiri dari tiga tahap: XORing dari subkey dengan input ke bulat, melewati input melalui kotak-S, dan mencampur hasilnya melalui pencampuran permutasi. Permutasi pencampuran dapat dengan mudah dibalik karena permutasi menentukan untuk setiap bit i dalam input, bit j di mana itu muncul dalam output (dengan demikian j^th bit hanya terbalik dengan i^th bit). Diberikan output dari permutasi, oleh karena itu kami mendapatkan input ke permutasi, yang persis merupakan output dari S-box. Mengingat fakta bahwa S-box 1–1 dan ke fungsi, ini juga dapat dibalik dengan melihat tabel yang mendefinisikan mereka. Karena itu kami mendapatkan input ke kotak-S. Akhirnya, subkunci dapat XOR dengan input ini dan kami mendapatkan nilainya dari awal putaran (perhatikan bahwa subkey yang diperlukan dapat diturunkan dari kunci master dengan cara yang sama ketika membalikkan cipher blok seperti saat menghitungnya). Karena itu, kami memiliki klaim berikut:

KLAIM : Dalam jaringan substitusi-permutasi F di mana S-box semuanya 1–1 dan ke atas (dan berukuran polinomial), terdapat prosedur yang efisien dure untuk menghitung F −1 (y). Selanjutnya, untuk setiap kunci k dan setiap input x, F_k-1(F_k (x)) = x.

Pilihan desain 2 - efek longsoran salju.

Properti penting dalam segala hal block cipher adalah bahwa perubahan kecil pada input harus menghasilkan perubahan besar ke output. Jika tidak, output dari cipher blok pada input yang sama tidak akan terlihat independen (sedangkan dalam permutasi acak, output dari input serupa didistribusikan secara independen). Untuk memastikan ini masalahnya, cipher blok dirancang untuk memiliki efek longsoran, artinya bahwa perubahan kecil pada input menyebar dengan cepat ke perubahan yang sangat besar di nilai menengah (dan dengan demikian menghasilkan). Sangat mudah untuk menunjukkan bahwa Efek longsor berlaku di jaringan substitusi-permutasi, asalkan dua sifat berikut tahan :

1.      S-box dirancang sedemikian rupa sehingga setiap perubahan minimal a bit tunggal ke input ke S-box menghasilkan perubahan pada Setidaknya dua bit dalam output.

2.      Permutasi pencampuran dirancang sehingga output bit dari S-box yang diberikan tersebar ke S-box yang berbeda di ronde selanjutnya.

properti pertama tidak harus diperoleh secara fngsi acak kecil atau permutasi. Sebagai contoh, perhatikan case yang dimiliki S-box panjang input / output 4 bit (ini mungkin tampak sangat kecil tetapi ukuran sebuah table untuk S-box 8-bit sering terlalu besar). Sekarang, untuk input 4-bit, ada 5 nilai yang berbeda dari input dengan 1 atau kurang bit (input itu sendiri ditambah empat nilai-nilai lain diperoleh dengan membalik sedikit input). Sebaliknya, di sana ada 16 kemungkinan nilai output. Dengan demikian, probabilitas itu adalah keluaran acak berbeda dari input dengan 1 atau kurang bit adalah 5/6 > 1/4 . Mengingat bahwa sejumlah S-box dapat digunakan (misalnya, DES memiliki 8 di antaranya), S-box yang dipilih secara acak tidak mungkin memiliki properti ini.

Kembali ke efek longsoran, Mempertimbangkan sekarang apa yang terjadi ketika cipher blok diterapkan pada dua input yang berbeda dengan hanya satu bit. Demi konkret, asumsikan bahwa S-box memiliki ukuran input / output 4 bit, dan ukuran blok adalah 128 bit. Kami melacak perhitungan dua input yang sama satu per satu:

1.      Setelah putaran pertama jaringan, nilai perantara berbeda dalam dua tempat. Ini disebabkan oleh fakta bahwa kedua input hanya berbeda bit tunggal dan semua nilai input sama kecuali dalam satu S-box. Dengan properti S-box di atas, maka output dari S-box ini berbeda di dua tempat.

2.      Dengan properti kedua, permutasi pada akhir babak pertama menyebar dua bit yang berbeda ke berbagai daerah perantara tali. Oleh karena itu, maka pada awal babak kedua, ada dua S-box yang menerima input yang berbeda satu bit.

3.      Melanjutkan dengan argumen diatas, kita memiliki perantara nilai berbeda 8 bit setelah putaran ke-3, 16 bit setelah putaran ke-4, 32 bit setelah putaran ke-5, 64 bit setelah putaran ke-6 dan 128 bit (yaitu, di mana-mana) setelah ronde ke-7. Tentu saja, kami tidak bermaksud begitu bit semua berbeda, tetapi mereka semua telah terpengaruh dan jadi tidak ada kesamaan yang tersisa.

Kami menyimpulkan bahwa setelah putaran saya, 2 bit i telah terpengaruh (dengan demikian untuk 128 bit blok, 7 putaran diperlukan untuk menyelesaikan efek longsoran salju).

Serangan pada jaringan substitusi-permutasi yang dikurangi. 

Untuk mendapatkan lebih banyak wawasan tentang jaringan substitusi-permutasi, kami akan menunjukkan serangan pada cipher blok jenis ini yang sangat beberapa putaran. Musuh diberikan oracle yang merupakan permutasi acak atau cipher blok yang diberikan (dengan sebuah kunci yang dipilih secara acak). Tujuan dari musuh adalah untuk menebak apa fungsinya dihitung berdasarkan ramalannya.  jika musuh dapat memperoleh kunci rahasia cipher blok, maka dapat membedakannya dari permutasi acak. Seperti itu serangan disebut istirahat total karena begitu kunci rahasia dipelajari, tidak keamanan tetap ada.

1.      Serangan pada jaringan substitusi-permutasi satu putaran: Biarkan x menjadi input dan y output. Kami akan menunjukkan caranya musuh dapat dengan mudah mempelajari kunci rahasia k yang y = F_k (x), di mana F menunjukkan jaringan substitusi-permutasi satu putaran. Musuh dimulai dengan membalik permutasi pencampuran, dan kemudian S-box. Hal ini dapat dilakukan karena spesifikasi permutasi dan S-box bersifat publik. Nilai menengah bahwa musuh menerima dari inversi ini persis x ⊕ k (dengan desain satu babak substitusi-permutasi). Karena musuh juga memiliki taruh x, itu langsung mendapatkan kunci rahasia k. Karena itu ini adalah hal sepele istirahat total.

2.      Menyerang jaringan substitusi-permutasi dua putaran: Biarkan ukuran blok menjadi 64 bit dan biarkan setiap S-box memiliki input / output ukuran 4 bit (seperti yang telah kami sebutkan, 8 biasanya terlalu besar). Selanjutnya, biarkan kunci k panjangnya 128 bit di mana bagian pertama dari kunci digunakan di babak pertama dan kedua setengah di babak kedua (misalkan k a dan k b menunjukkan kedua bagian 64 bit ini kunci). Kami menggunakan kunci independen di sini untuk menyederhanakan deskripsi serangan di bawah ini, tetapi ini hanya membuat serangan "lebih sulit". Sekarang, mari x menjadi input dan y output (masing-masing 64 bit). Menunjukkan   z = z₁ , ..., z₁₆ , di mana setiap z_i memiliki panjang 4 bit (kami akan menggunakan notasi ini untuk x, y, k^a dan k^b ). Musuh dimulai dengan mengupas babak terakhir, seperti pada serangan pada cipher blok putaran tunggal. Ditunjukkan oleh w nilai yang diterimanya setelah membalik permutasi pencampuran dan S- boxs babak kedua. Nyatakan α = w₁ ⊕ k1b  (tentu saja, musuh tidak tahu k b tapi ingin mempelajarinya). Pengamatan penting di sini adalah bahwa ketika bekerja dari input ke output, nilai α dipengaruhi oleh paling banyak 4 S-box yang berbeda (karena yang terburuk kasus, setiap bit input berasal dari S-box yang berbeda di babak pertama). Selanjutnya, sejak permutasi pencampuran dari putaran pertama diketahui, musuh tahu persis mana dari S-box yang mempengaruhinya. Lanjut, perhatikan bahwa paling banyak 16 bit kunci k^a mempengaruhi perhitungan keempat S-box ini. Oleh karena itu musuh dapat menebak 16 bit k^a dan porsi 4 bit k1b dari kunci k^b , dan kemudian verifikasi tebakannya input-output (x, y). Verifikasi ini dilakukan oleh XOR  ing relevan 16 bit input x dengan relevan 16 bit k^a , dan kemudian menghitung 4 S-box putaran pertama dan 4 bit pertama yang sesuai permutasi pencampuran bulat. Nilai α yang diperoleh kemudian dibandingkan dengan w 1 ⊕ k1b (di mana   juga bagian dari tebakan). Jika kesetaraan tidak diperoleh, maka tebakan ini 16 bit k^a dan  tentu saja salah. Jika kesetaraan diperoleh, maka tebakan ini mungkin benar. Jadi, langkah difusi dalam konstruksi juga diperlukan untuk memastikan hal itu semua bit dari kunci mempengaruhi semua bit dari output. Dua putaran jaringan tidak cukup untuk ini terjadi.

3.      Menyerang jaringan substitusi-permutasi tiga putaran: Serangan ini berdasarkan pengamatan itu efek longsoran tidak lengkap setelah hanya tiga putaran (tentu saja, ini tergantung pada ukuran blok dan ukuran S-box, tetapi dengan parameter ini akan menjadi masalahnya). Jadi, musuh hanya perlu bertanya untuk fungsi yang dihitung pada dua string yang berbeda hanya pada satu sedikit. Cipher blok tiga putaran akan memiliki properti yang banyak bit dari output kedua input akan sama. Jadi, jelas bukan fungsi pseudorandom.