High Performance Computing techniques for attacking reduced version of AES using XL and XSL methods

Thumbnail Image
Date
2010-01-01
Authors
Kleiman, Elizabeth
Major Professor
Advisor
Clifford Bergman
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Organizational Unit
Journal Issue
Is Version Of
Versions
Series
Department
Mathematics
Abstract

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.

Comments
Description
Keywords
Citation
Source
Subject Categories
Copyright
Fri Jan 01 00:00:00 UTC 2010