ALGEBRAIC CRYPTANALYSIS OF AES: AN OVERVIEW

Abstract. In this paper, we examine algebraic attacks on the Advanced Encryption Standard (AES, also known as Rijndael). We begin with a brief review of the history of AES, followed by a description of the AES algorithm. We then discuss the problem of solving systems of multivariate quadratic equations over arbitrary fields (the MQ problem), as well as some recent general methods for solving it, namely relinearization and XL, in preparation for a discussion of recent work that reduces breaking an AES encryption to solving an MQ problem over GF(2), and an MQ algorithm designed for this purpose, XSL. This leads to a summary of other work that ‘embeds ’ AES into another cryptosystem, BES, defined solely over GF(2 8). This allows breaking AES encryption to be reduced to solving the MQ problem for a much simpler (fewer and sparser) system of quadratic equations defined over GF (2 8). The controversy over how effective XSL is at solving this system is briefly touched upon. 1