Computational algebraic attacks on the Advanced Encryption Standard (AES)

Abstract

This thesis examines the vulnerability of the Advanced Encryption Standard (AES) to algebraic attacks. It will explore how strong the Rijndael algorithm must be in order to secure important federal information. There are several algebraic methods of attack that can be used to break a specific cipher, such as Buchburger's and Faugere's F4 and F5 methods. The method to be used and evaluated in this thesis is the Multiple Right Hand Sides (MRHS) Linear Equations. MRHS is a new method that allows computations to be more efficient and the equations to be more compact in comparison with the previously referred methods. Because of the high complexity of the Rijndael algorithm, the purpose of this thesis is to investigate the results of an MRHS attack in a small-scale variant of the AES, since it is impossible to break the actual algorithm by using only the existent knowledge. Instead of the original ten rounds of AES algorithm, variants of up to four rounds were used. Simple examples of deciphering some ciphertexts are presented for different variants of the AES, and the new attack method of MRHS linear equations is compared with the other older methods. This method is more effective timewise than the other older methods, but, in some cases, some systems cannot be uniquely solved.