Kriptanalisis Linear & Tabel Aproksimasi

Kriptanalisis linear (Matsui, 1993) adalah serangan dengan teks terang yang diketahui untuk menemukan pendekatan linear (XOR bit tertentu) dari sebuah sandi yang berlaku dengan probabilitas p ≠ 1/2. Dengan menggunakan banyak pasangan teks terang-teks tersandi, bias statistik mengungkapkan bit kunci.

Pendekatan linear untuk kotak-S: jumlah bit masukan yang dipilih XOR jumlah bit keluaran yang dipilih = 0 (mod 2) dengan probabilitas p. Dinyatakan sebagai: P[a·x XOR b·y = 0] = 1/2 + ε, dengan a,b adalah topeng bit dan ε adalah bias (|ε| >> 0 diinginkan).

LAT menghitung: untuk setiap topeng masukan a dan topeng keluaran b, jumlah masukan x yang memenuhi (a·x) XOR (b·S(x)) = 0. Kurangi 2^{n-1} untuk mendapatkan bias. Kotak-S yang baik memiliki |max_bias| = 1 (probabilitas 1/2 ± 1/2^{n/2}) — sedatar mungkin.

Untuk pendekatan linear independen melalui beberapa putaran, bias saling dikalikan: ε_total = 2^{r-1} * ε_1 * ε_2 * ... * ε_r. Setiap pendekatan putaran mengurangi bias efektif menjadi setengahnya. Setelah banyak putaran, bias total mendekati 0 sehingga diperlukan jauh lebih banyak pasangan untuk mendeteksinya.

Untuk menyerang sandi r putaran: temukan jejak linear ε melalui r-1 putaran. Kumpulkan N = 1/ε^2 teks terang yang diketahui. Untuk setiap kandidat byte kunci putaran terakhir k': lakukan dekripsi-XOR sebagian pada putaran terakhir, lalu periksa apakah pendekatan linear berlaku lebih dari N/2 kali. k' yang benar menunjukkan bias yang benar.

Matsui menyerang DES 16 putaran pada 1993 menggunakan pendekatan linear 14 putaran dengan bias 2^{-21.4}. Diperlukan 2^{43} teks terang yang diketahui. Sebanyak 26 bit kunci dipulihkan pada fase 1; 30 bit sisanya ditemukan melalui pencarian menyeluruh. Ini adalah serangan praktis pertama yang lebih cepat daripada pencarian menyeluruh terhadap DES penuh.

Kotak-S AES memiliki entri LAT maksimum |ε| = 4/256 = 1/64 per kotak-S. Strategi Wide Trail membatasi jumlah kotak-S aktif dalam setiap jejak 4 putaran menjadi ≥ 25. Bias total ≤ (1/64)^{25/2} ≈ 2^{-75}. Diperlukan 2^{150} teks terang yang diketahui — tidak layak secara komputasi.

Diferensial: pasangan teks terang yang diketahui/dipilih; memanfaatkan perbedaan keluaran. Linear: teks terang yang diketahui; memanfaatkan pendekatan linear statistik. Keduanya menggunakan teks terang pilihan dalam serangan praktis. Keduanya merupakan kriteria desain: kotak-S harus tahan terhadap keduanya (maksimum DDT rendah AND maksimum LAT rendah).

Gunakan beberapa pendekatan linear secara bersamaan untuk mengurangi kompleksitas data. Nyberg dan Leander memperluas metode Matsui: penggabungan M pendekatan mengurangi data dengan faktor log(M). Diterapkan pada PRESENT, SIMON, dan sandi ringan lainnya.

Pendekatan linear yang diterapkan pada sandi aliran: temukan korelasi antara aliran kunci dan fungsi linear dari keluaran LFSR. Korelasi ini, jika bukan nol, memungkinkan pemulihan kunci yang lebih cepat daripada pencarian menyeluruh. Pendekatan ini mengilhami desain fungsi penggabung nonlinier dalam sandi aliran.

Kriptanalisis integral (Knudsen-Wagner): pilih sekumpulan teks terang yang byte tertentu mengambil semua 256 nilai sementara byte lainnya tetap. Setelah beberapa putaran, XOR semua keluaran pada posisi tertentu adalah 0 (seimbang). Serangan ini memanfaatkan struktur AES dan secara efisien memecahkan AES dengan jumlah putaran yang dikurangi.

Kriptanalisis linear menemukan pendekatan linear berkebiasan pada kotak-S. AES menahannya melalui kotak-S yang optimal menurut LAT dan desain Wide Trail. Matsui memecahkan DES dengan 2^43 teks terang yang diketahui menggunakan jejak 14 putaran. Berikutnya: serangan ulang tahun dan pencarian tabrakan.