High performance computing techniques for attacking reduced version of AES using XL and XSL methods

A known-plaintext attack on the Advanced Encryption Standard can be formulated as a system of quadratic multivariate polynomial equations in which the unknowns represent key bits. Algorithms such as XSL and XL use properties of the cipher to build a sparse system of linear equations over the field GF(2) from those multivariate polynomial equations. A scaled down version of AES called Baby Rijndael has structure similar to AES and can be attacked using the XL and XSL techniques among others. This results in a large sparse system of linear equations over the field GF(2) with an unknown number of extraneous solutions that need to be weeded out. High Performance Computing techniques were used to create SPSOLVERMOD2 a parallel software designed to solve sparse systems of linear equations over the field GF(2).;In this thesis we apply XL and XSL attacks on Baby Rijndael. Using SPSOLVERMOD2 we have shown XL and XSL attacks on Baby Rijndael do not give the desired result when one block of message and corresponding cipher text are provided. The number of linearly dependent equations we get close to 100000 and the number of possible solutions is huge. Finally we present the design of SPSOLVERMOD2 as well as the challenges we met on our way. Also the performance results for random matrices on different clusters and supercomputers are discussed.