Paper 2017/007

Algebraic Attack Efficiency versus S-box Representation

Hossein Arabnezhad-Khanoki, Babak Sadeghiyan, and Josef Pieprzyk

Abstract

Algebraic analysis of block ciphers aims at finding the secret key by solving a collection of polynomial equations that describe the internal structure of a cipher for chosen observations of plaintext/ciphertext pairs. Although algebraic attacks are addressed for cryptanalysis of block and stream ciphers, there is a lack of understanding of the impact of algebraic representation of the cipher on efficiency of solving the resulting collection of equations. The work investigates different S-box representations and their effect on complexity of algebraic attacks. In particular, we observe that a S-box representation defined in the work as \textit{Forward-Backward} (FWBW) leads to a collection of equations that can be solved efficiently. We show that the $$ cipher can be broken using standard algebra software \textsc{Singular} and FGb. This is the best result achieved so far. The effect of description of S-boxes for some light-weight block ciphers is investigated. A by-product of this result is that we have achieved some improvements on the algebraic cryptanalysis of LBlock, PRESENT and MIBS light-weight block ciphers. Our study and experiments confirms a counter-intuitive conclusion that algebraic attacks work best for the FWBW S-box representation. This contradicts a common belief that algebraic attacks are more efficient for quadratic S-box representation.