Dasar-Dasar Kriptanalisis Diferensial

Kriptanalisis diferensial (Biham & Shamir, 1990) adalah serangan dengan teks terang pilihan yang menganalisis bagaimana perbedaan pada pasangan teks terang merambat melalui sebuah sandi. Dengan menemukan perbedaan masukan yang menghasilkan perbedaan keluaran yang dapat diprediksi dengan probabilitas tinggi, penyerang memulihkan bit kunci secara statistik.

Untuk sandi berbasis XOR: perbedaan ΔX = X XOR X'. Untuk sandi berbasis penjumlahan: perbedaan ΔX = X - X' mod 2^n. Perbedaan XOR paling umum karena XOR komutatif terhadap peng-XOR-an dengan kunci (dampak jadwal kunci saling meniadakan dalam pasangan diferensial).

Pasangan diferensial (P, P') memiliki perbedaan masukan ΔP = P XOR P'. Setelah enkripsi: (C, C') dengan perbedaan keluaran ΔC = C XOR C'. Diferensial yang berguna adalah ΔP → ΔC dengan probabilitas tinggi p — artinya banyak pasangan (P, P') dengan perbedaan ΔP menghasilkan perbedaan keluaran ΔC.

DDT (Tabel Distribusi Diferensial) menghitung: untuk setiap perbedaan masukan Δx dan perbedaan keluaran Δy, berapa banyak masukan x yang memenuhi S(x) XOR S(x XOR Δx) = Δy. Bagilah dengan 2^n untuk mendapatkan probabilitas. Kotak-S yang baik memiliki nilai DDT maksimum 2 (probabilitas 1/2^{n-1}) — tidak memiliki diferensial yang kuat.

Untuk sandi blok dengan r putaran: temukan urutan ΔP → ΔU1 → ΔU2 → ... → ΔU_{r-1}, dengan setiap transisi putaran memiliki probabilitas yang diketahui. Kalikan probabilitas di seluruh putaran: probabilitas keseluruhan p = p1 * p2 * ... * p_{r-1}. Serangan ini menggunakan 2/p pasangan untuk memulihkan kunci putaran terakhir.

Dengan diferensial r-1 putaran yang berprobabilitas tinggi: kumpulkan N = 2/p pasangan teks terang. Untuk setiap kandidat kunci putaran terakhir K': dekripsi kedua teks tersandi selama satu putaran, XOR hasilnya, lalu periksa apakah perbedaannya cocok dengan ΔU_{r-1}. K' yang benar cocok sekitar N/2 kali; kunci yang salah cocok sekitar N/2^{bit_size} kali.

Kotak-S AES adalah invers perkalian pada GF(2^8) yang diikuti transformasi afin. Nilai maksimum DDT-nya adalah 4 (dari 256), sehingga probabilitas diferensialnya ≤ 4/256 = 1/64 per kotak-S. AES memiliki 4 kotak-S per putaran, tetapi desain Wide Trail memastikan jejak diferensial lengkap berada di bawah 2^{-100}.

Desain Wide Trail karya Joan Daemen (digunakan dalam AES/Rijndael): tentukan bilangan cabang B dari MixColumns. Setiap jejak diferensial nontrivial melalui satu putaran mengaktifkan ≥ B kotak-S aktif. 4 putaran × 4 kotak-S per putaran menjamin ≥ 25 kotak-S aktif → probabilitas < 2^{-100}.

Diferensial terpotong hanya menentukan sebagian perbedaan (misalnya, kolom mana yang aktif, bukan nilai perbedaan yang tepat). Ini memungkinkan serangan pada lebih banyak putaran ketika diferensial lengkap terlalu lemah. Digunakan terhadap AES dengan jumlah putaran yang dikurangi, SERPENT, dan sandi SPN lainnya.

Diferensial mustahil adalah pasangan (ΔP, ΔC) yang tidak mungkin terjadi untuk kunci apa pun. Setiap kunci yang memetakan pasangan teramati (P, P') dengan perbedaan ini disingkirkan. Dengan mengumpulkan cukup banyak pasangan, semua kunci yang salah disingkirkan dan kunci yang benar tersisa.

Serangan bumerang (Wagner, 1999) menggabungkan dua diferensial pendek menjadi serangan teks terang/tersandi pilihan adaptif. Sandi diuraikan menjadi dua bagian, masing-masing dengan diferensial pendek berprobabilitas tinggi, sehingga memungkinkan serangan yang lebih panjang daripada yang dapat dilakukan oleh satu diferensial.

Kriptanalisis diferensial memanfaatkan perambatan perbedaan masukan→keluaran dengan probabilitas tinggi. AES menahannya melalui kotak-S yang optimal menurut DDT dan desain Wide Trail. Berikutnya: kriptanalisis linear dan tabel pendekatan.