Paper 2017/007

Algebraic Attack Efficiency versus S-box Representation

Hossein Arabnezhad-Khanoki, Babak Sadeghiyan, and Josef Pieprzyk


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 $SR(10,2,1,4)$ 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.

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Algebraic cryptanalysisSmall scaled AESSAT-solverGröbner basis computationLBlockPRESENTMIBS
Contact author(s)
arabnezhad @ aut ac ir
2018-01-06: revised
2017-01-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Hossein Arabnezhad-Khanoki and Babak Sadeghiyan and Josef Pieprzyk},
      title = {Algebraic Attack Efficiency versus S-box Representation},
      howpublished = {Cryptology ePrint Archive, Paper 2017/007},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.