Attack Pada Block Cipher

Related key attack on SHACAL-1
Shacal adalah penyandian block 160-bit dengan panjang variabel kunci hingga 512-bit kunci dan 80 round yang berdasarkan pd fungsi kompresi hash SHA-1. Serangan ini memerlukan 2159.8 teks terang yang dipilih dan dienkripsi dengan empat kunci terkait dan memiliki kompleksitas waktu 2423.

Deskripsi SHACAL:
160-bit plaintext dibagi menjadi 5x32-bit word, A_0,B_0,C_0,D_0,E_0
Setiap round diperbaharui dengan rumus:

Ai+1 = Wi + ROTL5(Ai) + fi(Bi,Ci,Di) + Ei + Ki
Bi+1 = Ai
Ci+1 = ROTL30(Bi)
Di+1 = Ci
Ei+1 = Di



Dengan Wi Sub kunci round, Ki konstanta round

Langkah pertama dalam pembangkitan kunci adalah padding menjadi 512 bit lalu di ekspansi menjadi 8x32-bit subkunci dengan LFSR )GF(232)).
Terdapat 16 word kunci M0,…,M15 (32-bit), untuk mdapatkan subkunci round W0,…W79 dengan:

Biryukov dan Wagner menunjukkan bahwa related key attack dapat ditulis sebagai dimana fk adalah fungsi “relative-simple” key-dependent. Serangan yang dilakukan melihat pada dua plainteks P1 dan P2 yang memiliki relasi P2 = fk(P1). Pasangan ini disebut dengan slid pair. Attacker mengecek untuk setiap pasang plainteks P1 dan P2 yang memenuhi slid pair untuk menyerang fk. Kompleksitas waktu 2n.
Slid pair dikonstruksi melalui blok pesan yang saling berhubungan (related key).
jika W = (W0, W1,…., W15) adalah kunci pertama dan W* = (W0*, W1*,…, W15*),

Maka kunci yang berhubungan memenuhi persamaan Wi* = Wi+1 untuk 0≤ i ≤ 78
Untuk memperoleh pasangan, maka dipilih 232 chosen plainteks sehingga SetP = (A, B, C, D, x) untuk A, B, C, D yang tetap dan semua kemungkinan nilai dari x, serta SetP* = (y, A, ROTL30(B), C, D) untuk semua kemungkinan nilai y.

Related Key Attack
Enkripsi beberapa pasangan plainteks menggunakan dua kunci yang berhubungan
Tiap pasangan kandidat menghasilkan sebuah nilai untuk dua buah keyword yang merupakan subkey pada round terakhir menggunakan kunci W*, sedangkan subkey pd round pertama menggunakan W.
Lakukan langkah berikut sebanyak M kali:

a.1. pilih A, B, C, dan D secara acak dan lakukan proses enkripsi untuk himpunan SetP = (A,B, C,D,x) untuk semua kemungkinan nilai x pada W dan himpunan SetP = (y, A, ROTL30(B), C, D) untuk semua kemungkinan nilai y pada W*.
a.2. Lakukan pencarian untuk pasangan kandidat, i.e., pasangan ciphertext T =(a,b,c,d,e) SetP dan T* = (a*, b*, c*, d*, e*) SetP* sedemikian hingga b* = a,c* = ROTL30(b),d* = c, dan e* = d. Lanjut ke tahap berikutnya, semua pasangan kandidat, dan pasangan plainteks yang berkorespondensi yang dinotasikan dengan P = (A, B, C, D, X) dan P* = (Y*, A, ROTL30(B), C, D).


Pada SHACAL-1, konstanta round digunakan pada seluruh fungsi round, namun kenyataannya bahwa konstanta tersebut berubah sekali tiap 20 round dan juga kenyataannya bahwa fungsi round tersebut berubah sedikit demi sedikit pada tempat-tempat yang sama dimana dapat digunakan untuk mengkonstruksi pasangan plainteks yang diharapkan.

Cube attack pada Courtois Toy Cipher

Cube attack pada CTC dengan 4 round dan 120-bit kunci dan perluasan cube attack dengan mengkombinasikannya dengan metode meet-in-the-middle, dimana ditambah 1 round untuk dianalisis. Diasumsikan penyerang dapat mengenkripsi chosen plaintext dan meneliti penjumlahan dari bit ciphertext sebagai fungsi dari bit kunci. Tujuannya adalah menemukan fungsi linier (atau affine) menggunakan tes linear dan mencari banyak ekspresi linear dalam bit kunci dan memilih yang saling bebas secara linear.

Fase on-line dimana dilakukan serangan chosen plaintext dimana satu round ditambahkan dalam sistem tsb. Kunci bersifat rahasia dan penyerang melakukan enkripsi teks terang ( yang didapatkan dari cube pada fase sebelumnya) dan mengumpulkan teks sandi setelah satu round ditambahkan. Fase meet-in-the-middle adalah membandingkan sisi sebelah kanan dari ekspresi linear pada tahap preprocessing dengan penjumlahan bit setelah round terakhir dari sistem tsb.

Misalkan p adalah polynomial dari n variabel x1, …, xn pada field GF(2). Untuk subset index tetap I = {i1, …, ik} ⊆ {1, …, n}, misalkan monomial tI = xi1 … xik .
Lalu kami memiliki dekomposisi
p(x1, …, xn) = tI . pS(I) + q(x1, …, xn),
dimana polinomial pS(I) tidak tergantung pada variabel xi1 , …, xik .

Langkah:
Memperbaiki dimensi cube dan variabel publik yang akan dijumlah yang disebut variabel tweakable dab variabel publiknya sama dengan nol.

Lakukan tes linier untuk fungsi yang dihasilkan

untuk beberapa argumen yang dipilih secara acak x, x’. Jika fungsi linear f dapat melewati tes untuk beberapa ratus pasang x, x’ dan itu bukan merupakan fungsi konstan (sama dengan nol atau satu), maka kita dapat membuat hipotesis bahwa ini adalah fugsi linear (atau affine).

Menghitung nilai eksplisit koefisien yang diperoleh dari fungsi linear.
Tujuan serangan fase on-line: menemukan beberapa bit rahasia kunci dengan kompleksitas yang lebih rendah dr exhaustive search. Penyerang menggunakan sistem turunan persamaan linear untuk variabel rahasia dimana sisi kanan persamaan ini adalah nilai-nilai jumlah bit ciphertexts yang diperoleh setelah penjumlahan pada cube yang sama seperti pada tahap preprocessing, tapi sekarang kunci tidak diketahui. cube attack berlaku untuk kriptosistem tanpa mengetahui struktur dalam mereka. Penyerang harus memiliki kemungkinan untuk mewujudkan fase preprocessing dan fase on-line dan memiliki akses pada implementasi algoritma (untuk melakukan penjumlahan melalui cube dengan kunci tidak diketahui).

CTC Adalah sistem SPN dengan jumlah round, blok, dan panjang kunci yang skalable. Setiap round menggunakan operasi yang sama pada input data kecuali ditambahkan kunci round yang beda tiap roundnya.
Nr dinotasikan sebagai jumlah round, output pada round ke i-1 sebagai input pada round ke-i. Setiap round terdiri dari B S-box paralel (S), tahap difusi linear (D), dan penambahan kunci akhir round (Ki). Kunci round K0 ditambahkan pada blok plainteks sebelum round pertama.
Bit plaintext p0 . . . pBs−1 diidentifikasikan dengan Z0,0 . . . Z0,Bs−1 dan bit ciphertext c0 . . . cBs−1 diidentifikasikan denan XNr +1,0 . . . XNr +1,Bs−1 untuk mendapatkan notasi seragam (s = 3 adalah ukuran S-box). S-box dipilih sebagai permutasi
[7, 6, 0, 4, 2, 5, 1, 3].

CTC mempunyai 23 = 8 input dan 8 output. Bit output adalah fungsi quadratic Boolean
Key schedulenya adalah permutasi bit sederhana:
Ki,j = K0,(i+j)modBs
untuk semua i dan j, di mana K0 adalah kunci utama. Key addition dilakukan dalam bit:
Xi+1,j = Zi,j + Ki,j

untuk semua i = 1, . . . , Nr dan j = 0, 1, . . . , Bs − 1, di mana Zi,j merepresentasikan bit output layer difusi sebelumnya , Xi+1,j bit input round berikutnya, dan Ki,j bit kunci round yang sedang digunakan.
Kompleksitas fase on-line di sini adalah 211 enkripsi CTC lima round dan penyimpanan 211 ciphertext 120 bit. Kompleksitas pada bagian linier diabaikan.

Interpolation Attack pada SNAKE
Interpolation merupakan jenis serangan pada block cipher. Notasi yang akan digunakan adalah

GF(2m)t,

Terdapat kunci tetap k, d ciphertext pada subblock yj GF(2m)t dapat di ekspresikan sebagai persamaan polynomial pada subblock plaintext { , ,…, }

Dimana :
GF(2m)[X] adalah polynomial ring X pada GF(2m)
Jika bilangan koefisien pada adalah N maka penyerang akan dapat menkonstruksi dari perbedaan N pasangan plaintext dan ciphertext.

Jika penyerang dapat mengkonstruksi maka ia dapat mengenkripsi beberapa teks terang lainnya untuk mengkorespondensi ciphertext dengan kunci k tanpa mengetahui kuncinya dan sebaliknya dengan ciphertext. Attack ini disebut global deduction.

Instance deduction
Penyerang dapat mengkonstruksi dari sedikit chosen plaintext dan ciphertext.
jika N adalah bilangan koefisien dan , N mengestimasi sebagai . Jika penyerang dapat mengkontruksi dari pasangan N dari plaintext dan ciphertext, maka dia dapat mengenkripsi semua subset plaintext , e.g., , kedalam korespondensi cipher pada kunci k, tanpa diketahui kunci k. Serangan ini disebut instance deduction.

Key recovery
Penyerang merecover kunci round terakhir. Jika notasi output round ke r-1 dengan dapat diekspresikan sbg polinomial.

Jika N’ adalah bilangan koefisien pada . Dalam kata lain, dapat diekspresikan juga menggunakan ciphertext y dan kunci . Jika pasangan N’ dari plaintext x dan ciphertext y tersedia, penyerang dapat mengkontruksi menggunakan dihitung menggunakan y dan :
= ( , )

Jika persamaan diatas dilakukan untuk beberapa pasangan plain atau cipher, benar dengan probabilitas tinggi.
Dari penjelasan di atas, global deduction attack / known plaintext attack, instance deduction attack / chosen plaintext attack dapat digunakan.

Meet in-the-middle Approach
Output pada round internal dinotasikan sebagai Sub blok dari dapat diekspresikan sebagai polynomial

Jumlah pasangan yang dibutuhkan dengan cara memisalkan f dan g sebagai representasi dari polinomial. Jika f dan g direpresentasikan sbg ekspresi pada rasional ( ), ( ), , dan , maka jumlah pasagan yang dibutuhkan adalah ((# koefisien pada f1) - 1) x (# koefisien pada g2) + (# koefisien pada f2) x ((# koefisien pada g1) – 1). Pengurangan dilakukan karena dapat menetapkan satu koefisien ekspresi rasional yang mempunyai nilai tetap contohnya 1. Seorang penyerang dapat mempertimbangkan benar atau tidak dengan mencocokkan persamaan dengan pasangan ciphertext dan plaintext yang lain.

Deskripsi algoritma SNAKE:
Block cipher yang menggunakan struktur feistel. Ada dua jenis yaitu feistel 1 dan 2 yang perbedaannya terletak pada fungsi round yang dipakai. Variabel yang digunakan:

i : 1 atau 2 yang menyatakan tipe SNAKE
m : ukuran input/output yang digunakan
s : jumlah S-box yang dipakai pada fungsi round
w ukuran blok (w= 2sm)
r : jumlah round

Pada s-box yang digunakan fungsi invers dari s-boxnya adalah pada yang digunakan, karena probabilitas dfferential dan linier probability dari adalah dimana m adalah genap.

Sumber