Degree Type

Dissertation

Date of Award

2010

Degree Name

Doctor of Philosophy

Department

Mathematics

First Advisor

Clifford Bergman

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.

Copyright Owner

Elizabeth Kleiman

Language

en

Date Available

2012-04-30

File Format

application/pdf

File Size

90 pages

Included in

Mathematics Commons

Share

COinS