SYMAES: A Fully Symbolic Polynomial System Generator for AES-128

Most of the existing polynomial system generators for AES are typically used under the assumption that the plaintext and ciphertext bits are known, and therefore are treated as constants. Although some of the generators, such as the AES (SR) Polynomial System Generator [2, 3], can also be used when this assumption is not made, the instructions to do this are not always very natural. SYMAES is specifically designed to address the case in which (some of) the plaintext and ciphertext bits are unknown and are therefore treated as symbolic variables. Such a scenario is realistic and arises during the algebraic cryptanalysis of AES-based constructions, where only parts of the plaintext and/or ciphertext are known. An example of such a construction is the stream cipher LEX [4], a small-scale version of which has been analysed using SYMAES [5]. The inputs to SYMAES are the bits of the plaintext and the bits of the original key, represented as symbolic variables in GF (2). The output is a system of equations describing the output bits of one round of AES as a function of the input bits and the key. SYMAES also generates symbolic equations for the AES key schedule. Then, the bits of the round keys are expressed as polynomials in the bits of the original key.

As a final note we would like to stress that SYMAES should not be seen as a competitor to existing AES polynomial system generators, but rather as an addition to them. SYMAES achieves in a more natural way what can also be achieved using SR [3]. Similarly to SR, SYMAES is also written in Python and is used within the open source computer algebra Sage [6]. This makes possible a future integration of the SYMAES code into SR. This submission is accompanied by an appendix containing the SYMAES source code and usage instructions.