AES CRYPTOGRAPHIC ATTACKS

AES Cryptographic Attacks

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(28). 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(28). The controversy over how effective XSL is at solving this system is briefly touched upon.

AES Cryptographic Attacks

Cryptography may be described as the science of secure communication over a public channel. An important area of cryptography is symmetric key cryptography. In symmetric key cryptography? the two parties share a secret piece of information? the key? and a public encryption algorithm. Assume Alice wants to send a message M? also known as the plaintext? to Bob? and they already share a secret key K and a cryptographic algorithm? called a cipher. The cipher consists of an encrypting function E? that depends on both the key and the message? and a decrypting function D? the inverse of E when the same key is used. Alice encrypts M by using the encryption half of the algorithm to compute the ciphertext C = EK(M)? which she then sends to Bob? possibly over a public channel. Bob then decrypts the message by computing DK(C) = DK(EK(M)) = M. Without any loss of generality? we may take M?K? and C to be finite sequences of bits.

What is meant by secure? The hope is that? without knowing K? an attacker cannot compute M from C. Can this be achieved? If the key K is as long as the message M? we may define EK(M) = M K? where refers to addition mod 2? also known as the exclusive OR or XOR. Then DK(C) = C K = M K K = M. Further? it is provably impossible to recover M from C so long as the key K is not reused and was randomly generated. The problem is that this requires us to securely transmit beforehand as much information as we want to send. Most symmetric key cryptography? then? is the study of cryptographic algorithms where K is much smaller in length than M and where K can be reused multiple times. Unfortunately? we must then change what we mean by secure. The messages will? in general? possess some statistical properties? and only some possible messages will 'make sense'. For example? there are far fewer words of 4 letters ...