Algebraic immunity of symmetric ciphers
Keywords:
symmetric ciphers, algebraic immunity, nonlinear substitution blocks
Abstract
A key component of modern symmetric ciphers are nonlinear blocks (non-linear substitutions, substitution tables, S-boxes) that perform functions of hiding statistical links of plaintext and ciphertext, mixing and disseminating data, and introducing nonlinearity into the encryption procedure to counter various crypto-analytical and statistical attacks. The effectiveness of a symmetric cipher, its resistance to the majority of known cryptographic attacks and the level of information technology security provided by it directly depend on the performance of nonlinear nodes (balance, nonlinearity, autocorrelation, correlation immunity etc.). In this paper various methods for calculating algebraic immunity are examined, their interrelation is studied, and the results of comparative studies of the algebraic immunity of nonlinear blocks of the most well-known modern symmetric ciphers are presented.
Downloads
Download data is not yet available.
References
Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Handbook of Applied Cryptography – CRC Press, 1997. – 794 р.
Gorbenko I.D., Gorbenko Y.I. Applied cryptology. Theory. Praxis. Exploitation: Textbook for higher educational institutions. – Kharkiv: Publishing house “Fort”, 2013. – 880 p.
Bart Preneel. Analysis and Design of Cryptographic Hash Functions. [Electronic resource] – Access mode: homes.esat.kuleuven.be/~preneel/phd_preneel_feb1993.pdf.
Carlet C. Vectorial Boolean functions for // Cambridge Univ. Press, Cambridge. – 95 p. [Electronic resource] – Access mode: www.math.univ-paris13.fr/~carlet/chap-vectorial-fcts-corr.pdf.
Carlet C. Boolean functions for cryptography and error correcting codes // Cambridge Univ. Press, Cambridge. – 2007. – 148 p. [Electronic resource] – Access mode: www1.spms.ntu.edu.sg/~kkhoongm/chap-fcts-Bool.pdf.
Zhuo Zepeng, Zhang Weiguo On correlation properties of Boolean functions // Chinese Journal of Electronics. Jan, Vol.20, 2011, №1, 143-146 pp.
O’Connor L. An analysis of a class of algorithms for S-box construction // J. Cryptology. -1994. – p. 133-151.
Clark J.A., Jacob J.L., Stepney S. The Design of S-Boxes by Simulated Annealing // New Generation Computing. – 2005. – 23(3). – p.219–231.
Kuznetsov A.A., Bielozertsev I.N., Andrushkevich A.V. Analysis and comparative studies of nonlinear substitution blocks of modern block symmetric ciphers // Applied electronics. – Kharkiv: KhNURE. – 2015. – Vol. 14. №4. – pp. 343–350.
Courtois N., Meier W. Algebraic Attacks on Stream Ciphers with Linear Feedback, Eurocrypt 2003, LNCS 2656, Springer, 2003. – pp. 345-359.
Meier W., Pasalic E., Carlet C: Algebraic Attacks and Decomposition of Boolean Functions, Eurocrypt 2004, LNCS 3027, Springer, 2004. – pp. 474-491.
Nicolas Courtois; Josef Pieprzyk (2002). "Cryptanalysis of Block Ciphers with Overdefined Systems of Equations". LNCS. 2501: pp. 267–287.
Gw´enol´e Ars, Jean-Charles Faug`ere. Algebraic Immunities of functions over finite fields. [Research Report] RR-5532, INRIA. 2005, pp.17.
Bayev Vladimir Valerievich. Effective algorithms for obtaining estimates of the algebraic immunity of Boolean functions: a thesis for the degree of candidate of physical and mathematical sciences: 01.01.09 / Bayev Vladimir Valerievich; [Institution of defense of a thesis: Moskow state university]. - Moskow, 2008. - 101 p.
I.V. Arzhantsev. Gröbner bases and systems of algebraic equations. Summer school. Modern mathematics. Dubna, Yuly 2002. – Moskow: MCNMO, 2003. – 68 p.
AI Zlobin, O. Sokolova. Computer algebra in the Sage system. Tutorial. - Moscow: MSTU named after Bauman, 2011. – 55 p.
Faugère, J.-C. (June 1999). A new efficient algorithm for computing Gröbner bases (F4). Journal of Pure and Applied Algebra. Elsevier Science. 139 (1): 61–88.
Faugère, J.-C. (July 2002). A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). Proceedings of the 2002 international symposium on Symbolic and algebraic computation (ISSAC). ACM Press: 75–83.
Massimiliano Sala, Teo Mora, Ludovic Perret, Shojiro Sakata, Carlo Traverso Gröbner Bases, Coding, and Cryptography. Springer-Verlag Berlin Heidelberg. – 426 p.
FIPS 197. National Institute of Standards and Technology. [Electronic resource]: Advanced Encryption Standard. – 2001. – Available at: http://www.nist.gov/aes.
ISO/IEC 18033-3. Information technology – Security techniques – Encryption algorithms, Part 3: Block ciphers, 80 p.
DSTU 7624:2014. Information technology. Cryptographic security of information. The algorithm of symmetric block transfor-mation. – Kyiv: Ministry of economic development of Ukraine, 2015. – 238 p.
GOST R 34.12-2015. Information technology. Cryptographic security of information. Block ciphers. – Moscow: Standartinform, 2015. – 25p.
STB 34.101.31-2011. Information technology and security. Cryptographic algorithms for encryption and integrity control. – Minsk: Gosstandart, 2011. – 32 p.
ISO/IEC 10118-3:2004. Information technology – Security techniques – Hash-functions – Part 3: Dedicated hash-functions, 94 p.
Magma Computational Algebra System. Available at: http://magma.maths.usyd.edu.au/magma.
Nicolas Courtois, Alexander Klimov, Jacques Patarin, Adi Shamir. Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations. Proceeding EUROCRYPT'00 Proceedings of the 19th international conference on Theory and application of cryptographic techniques. pp. 392-407.
Nicolas Courtois, Josef Pieprzyk. Cryptanalysis of Block Ciphers with Overdefined Systems of Equations. Advances in cryptology – ASIACRYPT 2002. pp. 267-287.
Andrey Pyshkin. Algebraic Cryptanalysis of Block Ciphers Using Grobner Bases. Dissertation zur Erlangung des Grades Doktor rerum naturalium. Technischen Universit¨at Darmstadt. – Darmstadt, 2008, 118 р.
Gorbenko I.D., Gorbenko Y.I. Applied cryptology. Theory. Praxis. Exploitation: Textbook for higher educational institutions. – Kharkiv: Publishing house “Fort”, 2013. – 880 p.
Bart Preneel. Analysis and Design of Cryptographic Hash Functions. [Electronic resource] – Access mode: homes.esat.kuleuven.be/~preneel/phd_preneel_feb1993.pdf.
Carlet C. Vectorial Boolean functions for // Cambridge Univ. Press, Cambridge. – 95 p. [Electronic resource] – Access mode: www.math.univ-paris13.fr/~carlet/chap-vectorial-fcts-corr.pdf.
Carlet C. Boolean functions for cryptography and error correcting codes // Cambridge Univ. Press, Cambridge. – 2007. – 148 p. [Electronic resource] – Access mode: www1.spms.ntu.edu.sg/~kkhoongm/chap-fcts-Bool.pdf.
Zhuo Zepeng, Zhang Weiguo On correlation properties of Boolean functions // Chinese Journal of Electronics. Jan, Vol.20, 2011, №1, 143-146 pp.
O’Connor L. An analysis of a class of algorithms for S-box construction // J. Cryptology. -1994. – p. 133-151.
Clark J.A., Jacob J.L., Stepney S. The Design of S-Boxes by Simulated Annealing // New Generation Computing. – 2005. – 23(3). – p.219–231.
Kuznetsov A.A., Bielozertsev I.N., Andrushkevich A.V. Analysis and comparative studies of nonlinear substitution blocks of modern block symmetric ciphers // Applied electronics. – Kharkiv: KhNURE. – 2015. – Vol. 14. №4. – pp. 343–350.
Courtois N., Meier W. Algebraic Attacks on Stream Ciphers with Linear Feedback, Eurocrypt 2003, LNCS 2656, Springer, 2003. – pp. 345-359.
Meier W., Pasalic E., Carlet C: Algebraic Attacks and Decomposition of Boolean Functions, Eurocrypt 2004, LNCS 3027, Springer, 2004. – pp. 474-491.
Nicolas Courtois; Josef Pieprzyk (2002). "Cryptanalysis of Block Ciphers with Overdefined Systems of Equations". LNCS. 2501: pp. 267–287.
Gw´enol´e Ars, Jean-Charles Faug`ere. Algebraic Immunities of functions over finite fields. [Research Report] RR-5532, INRIA. 2005, pp.17.
Bayev Vladimir Valerievich. Effective algorithms for obtaining estimates of the algebraic immunity of Boolean functions: a thesis for the degree of candidate of physical and mathematical sciences: 01.01.09 / Bayev Vladimir Valerievich; [Institution of defense of a thesis: Moskow state university]. - Moskow, 2008. - 101 p.
I.V. Arzhantsev. Gröbner bases and systems of algebraic equations. Summer school. Modern mathematics. Dubna, Yuly 2002. – Moskow: MCNMO, 2003. – 68 p.
AI Zlobin, O. Sokolova. Computer algebra in the Sage system. Tutorial. - Moscow: MSTU named after Bauman, 2011. – 55 p.
Faugère, J.-C. (June 1999). A new efficient algorithm for computing Gröbner bases (F4). Journal of Pure and Applied Algebra. Elsevier Science. 139 (1): 61–88.
Faugère, J.-C. (July 2002). A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). Proceedings of the 2002 international symposium on Symbolic and algebraic computation (ISSAC). ACM Press: 75–83.
Massimiliano Sala, Teo Mora, Ludovic Perret, Shojiro Sakata, Carlo Traverso Gröbner Bases, Coding, and Cryptography. Springer-Verlag Berlin Heidelberg. – 426 p.
FIPS 197. National Institute of Standards and Technology. [Electronic resource]: Advanced Encryption Standard. – 2001. – Available at: http://www.nist.gov/aes.
ISO/IEC 18033-3. Information technology – Security techniques – Encryption algorithms, Part 3: Block ciphers, 80 p.
DSTU 7624:2014. Information technology. Cryptographic security of information. The algorithm of symmetric block transfor-mation. – Kyiv: Ministry of economic development of Ukraine, 2015. – 238 p.
GOST R 34.12-2015. Information technology. Cryptographic security of information. Block ciphers. – Moscow: Standartinform, 2015. – 25p.
STB 34.101.31-2011. Information technology and security. Cryptographic algorithms for encryption and integrity control. – Minsk: Gosstandart, 2011. – 32 p.
ISO/IEC 10118-3:2004. Information technology – Security techniques – Hash-functions – Part 3: Dedicated hash-functions, 94 p.
Magma Computational Algebra System. Available at: http://magma.maths.usyd.edu.au/magma.
Nicolas Courtois, Alexander Klimov, Jacques Patarin, Adi Shamir. Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations. Proceeding EUROCRYPT'00 Proceedings of the 19th international conference on Theory and application of cryptographic techniques. pp. 392-407.
Nicolas Courtois, Josef Pieprzyk. Cryptanalysis of Block Ciphers with Overdefined Systems of Equations. Advances in cryptology – ASIACRYPT 2002. pp. 267-287.
Andrey Pyshkin. Algebraic Cryptanalysis of Block Ciphers Using Grobner Bases. Dissertation zur Erlangung des Grades Doktor rerum naturalium. Technischen Universit¨at Darmstadt. – Darmstadt, 2008, 118 р.
Published
2018-04-27
Cited
How to Cite
Kuznetsov, A., Serhiienko, R., Prokopovych-Tkachenko, D., Tarasenko, Y., & Belozertsev, I. (2018). Algebraic immunity of symmetric ciphers. Computer Science and Cybersecurity, (4), 36-48. Retrieved from https://periodicals.karazin.ua/cscs/article/view/10456
Issue
Section
Статті
