Evaluasi Serangan Aljabar XSL pada AES

Para peneliti telah berusaha untuk membongkar Algoritma Rijndael, yang merupakan algoritma yang dipakai dalam AES dengan menggunakan berbagai Aljabar. Salah satunya adalah aljabar XLS. Aljabar ini pertama kali dipublikasikan oleh Nicolas Courtois dan Josep Pieprzyk dalam makalah mereka yang berjudul “Cryptanalysis of Block Ciphers with Overdefined Systems of Equations” pada tahun 2002. Teknik penyerangan ini diklaim dapat memecahkan AES lebih cepat dari cara exhaustive search. XSL attack mengandalkan pada keberhasilan menganalisis subsistem internal dari cipher untuk menurunkan persamaan kuadrat secara simultan. Kumpulan persamaan ini umumnya sangat besar. Contohnya pada 128 bit AES terdapat 8000 persamaan dengan jumlah variable 1600. Metode untuk memecahkan persamaan ini disebut XSL (eXtended Sparse Linearisation). Jika persamaan tersebut dapat dipecahkan, maka kunci dapat diperoleh.

Pemecahan persamaan tersebut menjadi masalah jika ditemukan persamaan yang bersifat MQ(Multivariate quadratic). Persamaan MQ merupakan permasalahan yang bersifat NP-hard(Non Polinomial). XSL attack membutuhkan algoritma yang efisien untuk menyelesaikan MQ. Salah satu teknik untuk menyelesaikan sistem MQ adalah dengan linearisasi, yang mengubah setiap persamaan quadratic menjadi variable yang independent yang akan menghasilkan persamaan linier dengan menggunakan algoritma seperti Gaussian elimination.
Tahun 2000, Courtois mengajukan algoritma untuk MQ yang bernama XL(eXtended Linearisastion). Algoritma ini meningkatkan jumlah persamaan dengan mengalikan dengan monomial derajat tertentu. Algoritma ini akan menghasilkan suatu bentuk struktur yang disebut XSL. Algoritma XSL dibentuk dari algoritma XL dengan memilih monomial secara selektif.

Kesimpulan yang dapat diambil dari studi literatur mengenai berbagai macam serangan pada blok cipher ini adalah :

1. Advanced Encryption Standard(AES) masih merupakan suatu standard yang layak pakai untuk mengatasi masalah keamanan data.
2. Penemuan dari serangan algebraic (aljabar) membuka kesempatan baru untuk melakukan riset dan mengubah cara pandang dalam melakukan rancangan dan kriptanalisis dari suatu cipher ke level selanjutnya.
3. Cipher Rijndael dapat diekpresikan dengan rumus aljabar yang ringkas dan rapi.
4. XLS attack mengurangi waktu yang diperlukan untuk melakukan pemecahan block cipher daripada pemecahan blok cipher menggunakan exhaustive search.