×

The MILP-aided conditional differential attack and its application to Trivium. (English) Zbl 1457.94198

Summary: Conditional differential attacks were proposed by S. Knellwolf et al. [Lect. Notes Comput. Sci. 6477, 130–145 (2010; Zbl 1253.94056)] which targeted at cryptographic primitives based on non-linear feedback shift registers. The main idea of conditional differential attacks lies in controlling the propagation of a difference through imposing some conditions on public/key variables. In this paper, we improve the conditional differential attack by introducing the mixed integer linear programming (MILP) method to it. Let \(J=\{f_i(\mathbf{x,v})=\gamma_i\mid 1\le i\le N\}\) be a set of conditions that we want to impose, where \(\mathbf{x}=(x_1,x_2,\ldots ,x_n)\) (resp. \(\mathbf{v}=(v_1,v_2,\ldots ,v_n))\) represents key (resp. public) variables and \(\gamma_i \in \{0,1\}\) needs evaluating. Previous automatic conditional differential attacks evaluate \(\gamma_1,\gamma_2,\ldots ,\gamma_N\) just in order with the preference to zero. Based on the MILP method, conditions in \(J\) could be automatically analysed together. In particular, to enhance the effect of conditional differential attacks, in our MILP models, we are concerned with minimizing the number of 1’s in \(\{\gamma_1,\gamma_2,\ldots ,\gamma_N\}\) and maximizing the number of weak keys. We apply our method to analyse the security of Trivium. As a result, key-recovery attacks are preformed up to the 978-round Trivium and non-randomness is detected up to the 1108-round Trivium out of its 1152 rounds both in the weak-key setting. All the results are the best known so far considering the number of rounds and could be experimentally verified. Hopefully, the new method would provide insights on conditional differential attacks and the security evaluation of Trivium.

MSC:

94A60 Cryptography

Citations:

Zbl 1253.94056
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Banik, S., Conditional differential cryptanalysis of 105 round Grain v1, Cryptogr. Commun., 8, 1, 113-137 (2016) · Zbl 1344.94029
[2] Cannière C.D., Preneel B.: Trivium. In: New Stream Cipher Designs—The eSTREAM Finalists, pp. 244-266 (2008). · Zbl 1285.94054
[3] Cannière C.D., Dunkelman, O., Knezevic, M.: KATAN and KTANTAN—a family of small and efficient hardware-oriented block ciphers. In: 11th International Workshop of Cryptographic Hardware and Embedded Systems—CHES 2009, Lausanne, Switzerland, 6-9 September 2009, Proceedings, pp. 272-288 (2009). · Zbl 1290.94060
[4] Canteaut, A.; Carpov, S.; Fontaine, C.; Lepoint, T.; Naya-Plasencia, M.; Paillier, P.; Sirdey, R., Stream ciphers: a practical solution for efficient homomorphic-ciphertext compression, J. Cryptol., 31, 3, 885-916 (2018) · Zbl 1400.94132
[5] Dinur I., Shamir A.: Cube attacks on tweakable black box polynomials. In: Advances in Cryptology—EUROCRYPT 2009, 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, 26-30 April 2009. Proceedings, pp. 278-299 (2009). · Zbl 1239.94045
[6] Dinur I., Shamir A.: Breaking Grain-128 with dynamic cube attacks. In: Fast Software Encryption—18th International Workshop, FSE 2011, Lyngby, Denmark, 13-16 February 2011, Revised Selected Papers, pp. 167-187 (2011). · Zbl 1282.94042
[7] Fouque P., Vannet T.: Improving key recovery to 784 and 799 rounds of Trivium using optimized cube attacks. In: Fast Software Encryption—20th International Workshop, FSE 2013, Singapore, 11-13 March 2013. Revised Selected Papers, pp. 502-517 (2013). · Zbl 1321.94058
[8] Fu X., Wang X., Dong X., Meier W.: A key-recovery attack on 855-round Trivium. In: Advances in Cryptology—CRYPTO 2018—38th Annual International Cryptology Conference, Santa Barbara, CA, USA, 19-23 August 2018, Proceedings, Part II, pp. 160-184 (2018). · Zbl 1436.94066
[9] Gu Z., Rothberg E., Bixby R.: Gurobi optimizer. http://www.gurobi.com/.
[10] Hao Y., Jiao L., Li C., Meier W., Todo Y., Wang Q.: Observations on the dynamic cube attack of 855-round TRIVIUM from crypto’18. Cryptology ePrint Archive, Report 2018/972 (2018).
[11] Hao, Y.; Isobe, T.; Jiao, L.; Li, C.; Meier, W.; Todo, Y.; Wang, Q., Improved division property based cube attacks exploiting algebraic properties of superpoly, IEEE Trans. Comput., 68, 10, 1470-1486 (2019) · Zbl 07159067
[12] Hao Y., Leander G., Meier W., Todo Y., Wang Q.: Modeling for three-subset division property without unknown subset—improved cube attacks against trivium and grain-128aead. In: Canteaut, A., Ishai, Y. (eds.) Advances in Cryptology—EUROCRYPT 2020—39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, 10-14 May 2020, Proceedings, Part I. Lecture Notes in Computer Science, vol. 12105, pp. 466-495. Springer (2020).
[13] Hell, M.; Johansson, T.; Meier, W., Grain: a stream cipher for constrained environments, IJWMC, 2, 1, 86-93 (2007)
[14] Knellwolf S., Meier W., Naya-Plasencia M.: Conditional differential cryptanalysis of NLFSR-Based cryptosystems. In: Advances in Cryptology—ASIACRYPT 2010—16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, 5-9 December 2010. Proceedings, pp. 130-145 (2010). · Zbl 1253.94056
[15] Knellwolf S., Meier W., Naya-Plasencia M.: Conditional differential cryptanalysis of Trivium and KATAN. In: Selected Areas in Cryptography—8th International Workshop, SAC 2011, Toronto, ON, Canada, 11-12 August 2011, Revised Selected Papers, pp. 200-212 (2011). · Zbl 1292.94095
[16] Li, J.; Guan, J., Advanced conditional differential attack on Grain-like stream cipher and application on Grain v1, IET Inf. Security, 13, 2, 141-148 (2019)
[17] Liu M., Yang J., Wang W., Lin D.: Correlation cube attacks: From weak-key distinguisher to key recovery. In: Advances in Cryptology—EUROCRYPT 2018—37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, 29 April-3 May 2018 Proceedings, Part II, pp. 715-744 (2018). · Zbl 1428.94086
[18] Ma, Z.; Tian, T.; Qi, W., Improved conditional differential attacks on Grain v1, IET Inf. Security, 11, 1, 46-53 (2017)
[19] Mouha N., Wang Q., Gu D., Preneel B.: Differential and linear cryptanalysis using mixed-integer linear programming. In: Information Security and Cryptology—7th International Conference, Inscrypt 2011, Beijing, China, 30 November-3 December 2011. Revised Selected Papers, pp. 57-76 (2011). · Zbl 1292.94118
[20] Mroczkowski, P.; Szmidt, J., Corrigendum to: The cube attack on stream cipher Trivium and quadraticity tests, IACR Cryptol. ePrint Arch., 2011, 32 (2011) · Zbl 1237.94080
[21] Sasaki Y., Todo Y.: New impossible differential search tool from design and cryptanalysis aspects—revealing structural properties of several ciphers. In: Advances in Cryptology—EUROCRYPT 2017—36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, 30 April-4 May 2017, Proceedings, Part III, pp. 185-215 (2017). · Zbl 1394.94941
[22] Sun S., Hu L., Wang M., Wang P., Qiao K., Ma X., Shi D., Song L., Fu K.: Towards finding the best characteristics of some bit-oriented block ciphers and automatic enumeration of (related-key) differential and linear characteristics with predefined properties. Cryptology ePrint Archive, Report 2014/747 (2014).
[23] Sun S., Hu L., Wang P., Qiao K., Ma X., Song L.: Automatic security evaluation and (related-key) differential characteristic search: Application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers. In: Advances in Cryptology—ASIACRYPT 2014—20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., 7-11 December 2014. Proceedings, Part I, pp. 158-178 (2014). · Zbl 1306.94093
[24] Todo Y., Isobe T., Hao Y., Meier W.: Cube attacks on non-blackbox polynomials based on division property. In: Advances in Cryptology—CRYPTO 2017—37th Annual International Cryptology Conference, Santa Barbara, CA, USA, 20-24 August 2017, Proceedings, Part III, pp. 250-279 (2017). · Zbl 1406.94081
[25] Todo, Y.; Isobe, T.; Hao, Y.; Meier, W., Cube attacks on non-Blackbox polynomials based on division property, IEEE Trans. Comput., 67, 12, 1720-1736 (2018) · Zbl 07033435
[26] Wang Q., Hao Y., Todo Y., Li C., Isobe T., Meier W.: Improved division property based cube attacks exploiting algebraic properties of superpoly. In: Advances in Cryptology—CRYPTO 2018—38th Annual International Cryptology Conference, Santa Barbara, CA, USA, 19-23 August 2018, Proceedings, Part I, pp. 275-305 (2018). · Zbl 1444.94103
[27] Wang S., Hu B., Guan J., Zhang K., Shi T.: Milp-aided method of searching division property using three subsets and applications. In: Advances in Cryptology—ASIACRYPT 2019—25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, 8-12 December 2019, Proceedings, Part III, pp. 398-427 (2019). · Zbl 1455.94197
[28] Watanabe Y., Isobe T., Morii M.: Conditional differential cryptanalysis for Kreyvium. In: Information Security and Privacy—22nd Australasian Conference, ACISP 2017, Auckland, New Zealand, 3-5 July 2017, Proceedings, Part I, pp. 421-434 (2017).
[29] Xiang Z., Zhang W., Bao Z., Lin D.: Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers. In: Advances in Cryptology—ASIACRYPT 2016—22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, 4-8 December 2016, Proceedings, Part I, pp. 648-678 (2016). · Zbl 1404.94120
[30] Ye C., Tian T.: A new framework for finding nonlinear superpolies in cube attacks against Trivium-Like ciphers. In: Information Security and Privacy—23rd Australasian Conference, ACISP 2018, Wollongong, NSW, Australia, 11-13 July 2018, Proceedings, pp. 172-187 (2018). · Zbl 1444.94110
[31] Ye, C.; Tian, T., Revisit division property based cube attacks: Key-recovery or distinguishing attacks?, IACR Trans. Symm. Cryptol., 2019, 3, 81-102 (2019)
[32] Ye, C.; Tian, T., Algebraic method to recover superpolies in cube attacks, IET Inf. Security, 14, 4, 430-441 (2020)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.