An XSL Analysis on BES

Since the proposal of the XSL cryptanalysis and the construction of the big encryption system (BES), the potential for algebraic attacks against the advanced encryption system (AES), especially over GF(2⁸), has attracted a lot of attention from the cryptographic community. This paper presents an analysis of the compact XSL attack applied to the BES with the key schedule involved. We introduce a new strategy to reduce the number of S-boxes which is used to multiply the equations derived from the cipher linear layer. Then the scale of the expanded equation system can be reduced and it, in theory, leads to a better result than exhaustive key search: for BES corresponding to 128-bit key size AES, the complexity estimate is about 2⁹⁷.