Extension of Cube Attack with Probabilistic Equations and its Application on Cryptanalysis of KATAN Cipher

Document Type: ORIGINAL RESEARCH PAPER

Authors

Data and Communication Security Lab., Computer Dept., Ferdowsi University of Mashhad, Iran

10.22042/isecure.2020.199304.481

Abstract

Cube Attack is a successful case of Algebraic Attack. Cube Attack consists of two phases, linear equation extraction and solving the extracted equation system. Due to the high complexity of equation extraction phase in finding linear equations, we can extract nonlinear ones that could be approximated to linear equations with high probability. The probabilistic equations could be considered as linear ones under some noises. Existing approaches to solve noisy equation systems work well provided that the equation system has low error rate; however, as the error rate increases, the success rate of finding the exact solution diminishes, making them rather inefficient in high error rate. In this paper, we extend Cube Attack to probabilistic equations. First, an approximation approach based on linear combinations of nonlinear equations is presented to find probabilistic linear equations with high probability. Then, we present an approach to improve the efficiency of current solving approaches and make them practical to solve high error rate linear equation system. Finally, utilizing proposed approaches, we find the right key under extended noisy equation system with lower complexity in comparison to the original Cube Attack.

Keywords


References [1] T. Nicolas Courtois. Higher order correlation attacks, xl algorithm and cryptanalysis of toyocrypt. In Information Security and Cryptology — ICISC 2002, pages 182–199. Springer Berlin Heidelberg, 2003.

[2] Ilya Mironov and LintaoZhang. Applications of sat solvers to cryptanalysis of hash functions. In Theory and Applications of Satisfiability Testing - SAT 2006, pages 102–115. Springer Berlin Heidelberg, 2006.

[3] Jean-Charles Faugere and Antoine Joux. Algebraic cryptanalysis of hidden field equation (hfe) cryptosystems using grobner bases. In Advances in Cryptology - CRYPTO 2003, pages 44–60. Springer Berlin Heidelberg, 2003.

[4] Itai Dinur and Adi Shamir. Cube attacks on tweakable black box polynomials. In Advances in Cryptology - EUROCRYPT 2009, pages 278–299. Springer Berlin Heidelberg, 2009.

[5] Yuan Yao, Bin Zhang, and Wen-Ling Wu. Utilizing probabilistic linear equations in cube attacks. Journal of Computer Science and Technology, 31(2):317–325, 2016.

[6] Willi Meier, Enes Pasalic, and Claude Carlet. Algebraic attacks and decomposition of boolean functions. In Advances in Cryptology - EUROCRYPT 2004, pages 474–491. Springer Berlin Heidelberg, 2004.

[7] Pratish Datta, Dibyendu Roy, and Sourav Mukhopadhyay. A probabilistic algebraic attack on thegrain family ofstream ciphers. In Network and System Security, pages 558–565. Springer International Publishing, 2014.

[8] Martin Albrecht and Carlos Cid. Cold boot key recovery by solving polynomial systems with noise. In Applied Cryptography and Network Security, pages 57–72. Springer Berlin Heidelberg, 2011.

[9] Zhenyu Huang and Dongdai Lin. Solving polynomial systems with noise over f2: Revisited. Theoretical Computer Science, 676:52 – 68, 2017.

[10] Julia Borghoff, Lars R. Knudsen, and Mathias Stolpe. Bivium as a mixed-integer linear programming problem. In IMA Int. Conf., 2009.

[11] Mohamed Ahmed Abdelraheem, Julia Borghoff, Erik Zenner, and Mathieu David. Cryptanalysis of the light-weight cipher a2u2. In Cryptography and Coding, pages 375–390. Springer Berlin Heidelberg, 2011.

[12] Xiao shan Gao and Zhenyu Huang. Efficient characteristic set algorithms for equation solving in finite fields and application in analysis of stream ciphers. Cryptology ePrint Archive, Report 2009/637, 2009. https://eprint.iacr. org/2009/637.

[13] Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. 47(3):549–595, 1993.

[14] Jean-Philippe Aumasson, Itai Dinur, Willi Meier, and Adi Shamir. Cube testers and key recovery attacks on reduced-round md6 and trivium. In Fast Software Encryption, pages 1–22, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg.

[15] Itai Dinur and Adi Shamir. Breaking grain-128 with dynamic cube attacks. In Fast Software Encryption, pages 167–187, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.

[16] Christophe De Cannière, Orr Dunkelman, and Miroslav Knežević. Katan and ktantan — a family of small and efficient hardware-oriented block ciphers. In Cryptographic Hardware and Embedded Systems - CHES 2009, pages 272–288, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg.

[17] Yosuke Todo, Takanori Isobe, Yonglin Hao, and Willi Meier. Cube attacks on non-blackbox polynomials based on division property. In Advances in Cryptology – CRYPTO 2017, pages 250–279. Springer International Publishing, 2017.

[18] Z. Eskandari and A. Ghaemi Bafghi. Cube distinguisher extraction using division property in block ciphers. IET Information Security, 14(1):72–80, 2020.

[19] Yosuke Todo. Structural evaluation by generalized integral property. In Advances in Cryptology – EUROCRYPT 2015, pages 287–314. Springer Berlin Heidelberg, 2015.

[20] Yosuke Todo and Masakatu Morii. Bit-based division property and application to simon family. In Fast Software Encryption, pages 357–377. Springer Berlin Heidelberg, 2016.

[21] Ling Sun, Wei Wang, and Meiqin Wang. Milpaided bit-based division property for primitives with non-bit-permutation linear layers. Cryptology ePrint Archive, Report 2016/811, 2016. https://eprint.iacr.org/2016/811.

[22] Ling Sun, Wei Wang, and Meiqin Wang. Automatic search of bit-based division property for arx ciphers and word-based division property, 2017.

[23] Nicolas T. Courtois and Josef Pieprzyk. Cryptanalysis of block ciphers with overdefined systems of equations. In Advances in Cryptology — ASIACRYPT 2002, pages 267–287, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg.

[24] Igor Shafarevich and Alexey R. Remizov. linear algebra and geometry. Springer Science & Business Media, 2012.

[25] Shahram Rasoolzadeh and Håvard Raddum. Improved multi-dimensional meet-in-the-middle cryptanalysis of katan. 2016. https://eprint. iacr.org/2016/077.

[26] Zahra Ahmadian, Shahram Rasoolzadeh, Mahmoud Salmasizadeh, and Mohammad Reza Aref. Automated dynamic cube attack on block ciphers: Cryptanalysis of simon and katan. Cryptology ePrint Archive, Report 2015/040, 2015. https://eprint.iacr.org/2015/040.

[27] Gregory V. Bard, Nicolas T. Courtois, Jorge Nakahara, Pouyan Sepehrdad, and Bingsheng Zhang. Algebraic, aida/cube and side channel analysis of katan family of block ciphers. In Progress in Cryptology - INDOCRYPT 2010, pages 176–196. Springer Berlin Heidelberg, 2010. [28] Simon Knellwolf, Willi Meier, and María NayaPlasencia. Conditional differential cryptanalysis of nlfsr-based cryptosystems. In Advances in Cryptology - ASIACRYPT 2010, pages 130–145, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.

[29] Martin R. Albrecht and Gregor Leander. An all-in-one approach to differential cryptanalysis for small block ciphers. In Selected Areas in Cryptography, pages 1–15, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.

[30] Takanori Isobe and Kyoji Shibutani. Improved all-subkeys recovery attacks on fox, katan and shacal-2 block ciphers. In Fast Software Encryption, pages 104–126, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg.

[31] Thomas Fuhr and Brice Minaud. Match box meet-in-the-middle attack against katan. In Fast Software Encryption, pages 61–81, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg.