Cryptology ePrint Archive: Report 2017/007

Algebraic Attack Efficiency versus S-box Representation

Hossein Arabnezhad-Khanoki and 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 $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.

Category / Keywords: secret-key cryptography / Algebraic cryptanalysis, Small scaled AES, SAT-solver, Gr\"obner basis computation, LBlock, PRESENT, MIBS

Date: received 6 Jan 2017, last revised 6 Jan 2018

Contact author: arabnezhad at aut ac ir

Available format(s): PDF | BibTeX Citation

Version: 20180106:102020 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]