Your browser does not support JavaScript!

access icon free S-boxes representation and efficiency of algebraic attack

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 study investigates some different S-box representations and their effect on complexity of algebraic attacks. In particular, the authors observe that a S-box representation defined in the work as forward–backward (FWBW) leads to a collection of equations that can be solved efficiently. They show that the SR(10,2,1,4) cipher can be broken with algebraic cryptanalysis using standard algebra software 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 some improvements have been achieved on the algebraic cryptanalysis of LBlock, PRESENT and MIBS light-weight block ciphers. The authors’ study and experiments confirm 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 with quadratic S-box representation.


    1. 1)
      • 19. Bogdanov, A., Knudsen, L.R., Leander, G., et al: ‘PRESENT: an ultra-lightweight block cipher’. Cryptographic Hardware and Embedded Systems (CHES 2007), Vienna, Austria, 2007, pp. 450466.
    2. 2)
      • 1. Daemen, J., Rijmen, V.: ‘AES proposal’ (NIST AES Proposal, Rijndael, 1998).
    3. 3)
      • 26. Brickenstein, M.: ‘Slimgb: gröbner bases with slim polynomials’, Rev. Mat. Complutense, 2009, 23, (2), pp. 453466.
    4. 4)
      • 24. Gao, S.: ‘Counting zeros over finite fields with Gröbner bases’ (Carnegie Mellon, Pittsburgh, Pennsylvania, USA, 2009). Available at
    5. 5)
      • 3. Cid, C.: ‘Some algebraic aspects of the advanced encryption standard’, in Dobbertin, H., Rijmen, V., Sowa, A. (eds.): ‘Advanced encryption standard – AES’ (Springer, Heidelberg, 2005), pp. 5866.
    6. 6)
      • 7. Bulygin, S., Brickenstein, M.: ‘Obtaining and solving systems of equations in key variables only for the small variants of AES’, Math. Comput. Sci., 2010, 3, (2), pp. 185200.
    7. 7)
      • 15. Faugère, J.C.: ‘FGb: a library for computing gröbner bases’. Mathematical software – (ICMS 2010), Kobe, Japan, 2010, pp. 8487.
    8. 8)
      • 33. Faugère, J.C., Perret, L.: ‘Algebraic cryptanalysis of curry and flurry using correlated messages’, in Bao, F., Yung, M., Lin, D., Jing, J. (eds.): ‘Information security and cryptology’ (Springer, Heidelberg, 2010), pp. 266277.
    9. 9)
      • 36. Z'aba, M.R., Raddum, H., Henricksen, M., et al: ‘Bit-pattern based integral attack’, in Nyberg, K. (ed.): ‘Fast software encryption’ (Springer, Heidelberg, 2008), pp. 363381.
    10. 10)
      • 2. Courtois, N.T., Pieprzyk, J.: ‘Cryptanalysis of block ciphers with overdefined systems of equations’. Advances in Cryptology – (ASIACRYPT 2002), Queenstown, New Zealand, 2002, pp. 267287.
    11. 11)
      • 30. Sušil, P., Sepehrdad, P., Vaudenay, S.: ‘On selection of samples in algebraic attacks and a new technique to find hidden low degree equations’, in Susilo, W., Mu, Y. (eds.): ‘Information security and privacy’ (Springer, Cham, 2014), pp. 5065.
    12. 12)
      • 4. Cid, C., Leurent, G.: ‘An analysis of the XSL algorithm’. Advances in Cryptology (ASIACRYPT 2005), Paris, France, 2005, pp. 333352.
    13. 13)
      • 5. Cid, C., Murphy, S., Robshaw, M.J.B.: ‘Small scale variants of the AES’, in Gilbert, H., Handschuh, H. (eds.): ‘Fast software encryption’ (Springer, Heidelberg, 2005), pp. 145162.
    14. 14)
      • 22. Bosch, S.: ‘Algebraic geometry and commutative algebra’, Universitext (Springer-Verlag, London, 2013). Available at
    15. 15)
      • 32. Dinur, I., Shamir, A.: ‘Cube attacks on tweakable black box polynomials’. Advances in Cryptology (EUROCRYPT 2009), Cologne, Germany, 2009, pp. 278299.
    16. 16)
      • 16. Soos, M.: ‘SAT-solver cryptominisat, Version 2.9.0, January 20 2011 ’.
    17. 17)
      • 25. Buchberger, B.: ‘A criterion for detecting unnecessary reductions in the construction of Gröbner-bases’, in Ng, E.W. (ed.): ‘Symbolic and algebraic computation’ (Springer, Heidelberg, 1979), pp. 321.
    18. 18)
      • 12. Fuhs, C., Schneider-Kamp, P.: ‘Synthesizing shortest linear straight-line programs over GF(2) using SAT’. Theory and Applications of Satisfiability Testing (SAT 2010), Edinburgh, UK, 2010, pp. 7184.
    19. 19)
      • 13. Courtois, N., Mourouzis, T., Hulme, D.: ‘Exact logic minimization and multiplicative complexity of concrete algebraic and cryptographic circuits’, Int. J. Adv. Intell. Syst., 2013, 6, (3), pp. 165176.
    20. 20)
      • 31. Nakahara, J., Sepehrdad, P., Zhang, B., et al: ‘Linear (hull) and algebraic cryptanalysis of the block cipher PRESENT’, in Garay, J.A., Miyaji, A., Otsuka, A. (eds.): ‘Cryptology and network security’ (Springer, Heidelberg, 2009), pp. 5875.
    21. 21)
      • 38. Wu, S., Wang, M.: ‘Integral attacks on reduced-round PRESENT’, in Qing, S., Zhou, J., Liu, D. (eds.): ‘Information and communications security’ (Springer, Cham, 2013), pp. 331345.
    22. 22)
      • 10. Courtois, N.T.: ‘Some algebraic description for various S-boxes’. Accessed 2017-01-31. Available at
    23. 23)
      • 27. Miolane, C.: ‘Block cipher Analysis’ (Technical University of Denmark (DTU), Copenhagen, Denmark, 2009). Available at
    24. 24)
      • 41. Bard, G.V., Courtois, N.T., Jefferson, C.: ‘Efficient methods for conversion and solution of sparse systems of low-degree multivariate polynomials over GF(2) via SAT-solvers’. Cryptology ePrint Archive, Report 2007/024. Available at
    25. 25)
      • 18. Wu, W., Zhang, L.: ‘LBlock: a lightweight block cipher’, in Lopez, J., Tsudik, G. (eds.): ‘Applied cryptography and network security’ (Springer, Heidelberg, 2011), pp. 327344.
    26. 26)
      • 39. Wang, M.: ‘Differential cryptanalysis of reduced-round PRESENT’. Progress in Cryptology (AFRICACRYPT 2008), Casablanca, Morocco, 2008, pp. 4049.
    27. 27)
      • 35. Sasaki, Y., Wang, L.: ‘Comprehensive study of integral analysis on 22-round LBlock’. Information Security and Cryptology (ICISC 2012), Seoul, South Korea, 2013, pp. 156169.
    28. 28)
      • 29. Courtois, N.T., Sepehrdad, P., Sušil, P., et al: ‘Elimlin algorithm revisited’, in Canteaut, A. (ed.): ‘Fast software encryption’ (Springer, Heidelberg, 2012), pp. 306325.
    29. 29)
      • 40. Bay, A., Nakahara, J., Vaudenay, S.: ‘Cryptanalysis of reduced-round MIBS block cipher’, in Heng, S.H., Wright, R.N., Goi, B.M. (eds.): ‘Cryptology and network security’ (Springer, Heidelberg, 2010), pp. 119.
    30. 30)
      • 6. Faugére, J.C.: ‘A new efficient algorithm for computing gröbner bases (F4)’, J. Pure Appl. Algebra, 1999, 139, (1-3), pp. 6188.
    31. 31)
      • 9. Courtois, N.T., Castagnos, G., Goubin, L.: ‘What do DES S-boxes Say to Each Other?’. Cryptology ePrint Archive Report 2003/184. Available at
    32. 32)
      • 34. Islam, S., Afzal, M., Rashdi, A.: ‘On the security of LBlock against the cube attack and side channel cube attack’, in Cuzzocrea, A., Kittl, C., Simos, D.E., Weippl, E., Xu, L. (eds.): ‘Security engineering and intelligence informatics’ (Springer, Heidelberg, 2013), pp. 105121.
    33. 33)
      • 14. Decker, W., Greuel, G.M., Pfister, G., et al: ‘Singular 3-1-7 – a computer algebra system for polynomial computations’, 2015. Available at
    34. 34)
      • 23. Buchberger, B.: ‘Bruno buchberger's PhD thesis 1965: an algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal’, J. Symb. Comput., 2006, 41, (3-4), pp. 475511.
    35. 35)
      • 8. Courtois, N.T., Bard, G.V.: ‘Algebraic cryptanalysis of the data encryption standard’, in Galbraith, S.D. (ed.): ‘Cryptography and coding’ (Springer, Heidelberg, 2007), pp. 152169.
    36. 36)
      • 11. Courtois, N.T.: ‘Some algebraic description for various S-boxes’. Accessed 2017-01-31. Available at
    37. 37)
      • 20. Izadi, M., Sadeghiyan, B., Sadeghian, S.S., et al: ‘MIBS: a new lightweight block cipher’, in Garay, J.A., Miyaji, A., Otsuka, A. (eds.): ‘Cryptology and network security’ (Springer, Heidelberg, 2009), pp. 334348.
    38. 38)
      • 17. Brickenstein, M., Dreyer, A.: ‘Polybori: a framework for Gröbner-basis computations with Boolean polynomials’, J. Symb. Comput., 2009, 44, (9), pp. 13261345.
    39. 39)
      • 37. Eskandari, Z., Kidmose, A.B., Kölbl, S., et al: ‘Finding integral distinguishers with ease’. Cryptology ePrint Archive, Report 2018/688. Available at
    40. 40)
      • 28. The Sage Developers: ‘Sagemath, the sage mathematics software system (version 6.7)’, 2015, Available at
    41. 41)
      • 21. Cox, D., Little, J., O'Shea, D.: ‘Ideals, varieties, and algorithms’, Undergraduate Texts in Mathematics (Springer, New York, 2007).

Related content

This is a required field
Please enter a valid email address