Skip to main content
SpringerLink
Log in

Massive Superpoly Recovery with a Meet-in-the-Middle Framework

Improved Cube Attacks on Trivium and Kreyvium

  • Conference paper
  • First Online:
Advances in Cryptology – EUROCRYPT 2024 (EUROCRYPT 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14651))

Abstract

The cube attack extracts the information of secret key bits by recovering the coefficient called superpoly in the output bit with respect to a subset of plaintexts/IV, which is called a cube. While the division property provides an efficient way to detect the structure of the superpoly, superpoly recovery could still be prohibitively costly if the number of rounds is sufficiently high. In particular, Core Monomial Prediction (CMP) was proposed at ASIACRYPT 2022 as a scaled-down version of Monomial Prediction (MP), which sacrifices accuracy for efficiency but ultimately gets stuck at 848 rounds of Trivium.

In this paper, we provide new insights into CMP by elucidating the algebraic meaning to the core monomial trails. We prove that it is sufficient to recover the superpoly by extracting all the core monomial trails, an approach based solely on CMP, thus demonstrating that CMP can achieve perfect accuracy as MP does. We further reveal that CMP is still MP in essence, but with variable substitutions on the target function. Inspired by the divide-and-conquer strategy that has been widely used in previous literature, we design a meet-in-the-middle (MITM) framework, in which the CMP-based approach can be embedded to achieve a speedup.

To illustrate the power of these new techniques, we apply the MITM framework to Trivium, Grain-128AEAD and Kreyvium. As a result, not only can the previous computational cost of superpoly recovery be reduced (e.g., 5x faster for superpoly recovery on 192-round Grain-128AEAD), but we also succeed in recovering superpolies for up to 851 rounds of Trivium and up to 899 rounds of Kreyvium. This surpasses the previous best results by respectively 3 and 4 rounds. Using the memory-efficient Möbius transform proposed at EUROCRYPT 2021, we can perform key recovery attacks on target ciphers, even though the superpoly may contain over \(2^{40}\) monomials. This leads to the best cube attacks on the target ciphers.

Due to page limits, all appendixes and some tables of this paper are provided in our full version [21].

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 25167
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 18589
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. eSTREAM: the ECRYPT stream cipher project (2018). https://www.ecrypt.eu.org/stream/. Accessed 23 Mar 2021

  2. Gurobi Optimization. https://www.gurobi.com

  3. ISO/IEC 29192-3:2012: Information technology - Security techniques - Lightweight cryptography - Part 3: stream ciphers. https://www.iso.org/standard/56426.html

  4. Aumasson, J.-P., Dinur, I., Meier, W., Shamir, A.: Cube testers and key recovery attacks on reduced-round MD6 and Trivium. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 1–22. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03317-9_1

    Chapter  Google Scholar 

  5. Baudrin, J., Canteaut, A., Perrin, L.: Practical cube attack against nonce-misused Ascon. IACR Trans. Symmetric Cryptol. 2022(4), 120–144 (2022)

    Article  Google Scholar 

  6. Boura, C., Coggia, D.: Efficient MILP modelings for sboxes and linear layers of SPN ciphers. IACR Trans. Symmetric Cryptol. 2020(3), 327–361 (2020)

    Article  Google Scholar 

  7. De Cannière, C., Preneel, B.: Trivium. In: Robshaw, M., Billet, O. (eds.) New Stream Cipher Designs. LNCS, vol. 4986, pp. 244–266. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-68351-3_18

    Chapter  Google Scholar 

  8. 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)

    Article  MathSciNet  Google Scholar 

  9. Che, C., Tian, T.: An experimentally verified attack on 820-round trivium. In: Deng, Y., Yung, M., editors, Information Security and Cryptology - 18th International Conference, Inscrypt 2022, Beijing, China, December 11-13, 2022, Revised Selected Papers, volume 13837 of Lecture Notes in Computer Science, pp. 357–369. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-26553-2_19

  10. Delaune, S., Derbez, P., Gontier, A., Prud’homme, C.: A simpler model for recovering superpoly on trivium. In: AlTawy, R., Hülsing, A. (eds.) SAC 2021. LNCS, vol. 13203, pp. 266–285. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-99277-4_13

    Chapter  Google Scholar 

  11. Dinur, I.: Cryptanalytic applications of the polynomial method for solving multivariate equation systems over GF(2). In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12696, pp. 374–403. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77870-5_14

    Chapter  Google Scholar 

  12. Dinur, I., Morawiecki, P., Pieprzyk, J., Srebrny, M., Straus, M.: Cube attacks and cube-attack-like cryptanalysis on the round-reduced Keccak sponge function. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 733–761. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_28

    Chapter  Google Scholar 

  13. Dinur, I., Shamir, A.: Cube attacks on tweakable black box polynomials. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 278–299. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01001-9_16

    Chapter  Google Scholar 

  14. Dinur, I., Shamir, A.: Breaking grain-128 with dynamic cube attacks. In: Joux, A. (ed.) FSE 2011. LNCS, vol. 6733, pp. 167–187. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21702-9_10

    Chapter  Google Scholar 

  15. Dobraunig, C., Eichlseder, M., Mendel, F., Schläffer, M.: Ascon v1.2: lightweight authenticated encryption and hashing. J. Cryptol. 34(3), 33 (2021)

    Google Scholar 

  16. Fan, H., Hao, Y., Wang, Q., Gong, X., Jiao, L.: Key filtering in cube attacks from the implementation aspect. In: Deng, J., Kolesnikov, V., Schwarzmann, A.A., editors, Cryptology and Network Security - 22nd International Conference, CANS 2023, Augusta, GA, USA, October 31 - November 2, 2023, Proceedings, vol. 14342 of Lecture Notes in Computer Science, pp. 293–317. Springer, Singapore (2023). https://doi.org/10.1007/978-981-99-7563-1_14

  17. Fouque, P.-A., Vannet, T.: Improving key recovery to 784 and 799 rounds of trivium using optimized cube attacks. In: Moriai, S. (ed.) FSE 2013. LNCS, vol. 8424, pp. 502–517. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43933-3_26

    Chapter  Google Scholar 

  18. Funabiki, Y., Todo, Y., Isobe, T., Morii, M.: Improved integral attack on HIGHT. ACISP 2017, 363–383 (2017)

    Google Scholar 

  19. Hao, Y., Jiao, L., Li, C., Meier, W., Todo, Y., Wang, Q.: Links between division property and other cube attack variants. IACR Trans. Symmetric Cryptol. 2020(1), 363–395 (2020)

    Article  Google Scholar 

  20. Hao, Y., Leander, G., Meier, W., Todo, Y., Wang, Q.: Modeling for three-subset division property without unknown subset. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 466–495. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45721-1_17

    Chapter  Google Scholar 

  21. He, J., Hu, K., Lei, H., Wang, M.: Massive superpoly recovery with a meet-in-the-middle framework – improved cube attacks on trivium and kreyvium. Cryptology ePrint Archive, Paper 2024/342 (2024). https://eprint.iacr.org/2024/342

  22. He, J., Hu, K., Preneel, B., Wang, M.: Stretching cube attacks: improved methods to recover massive superpolies. In: Agrawal, S., Lin, D., editors, Advances in Cryptology - ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5–9, 2022, Proceedings, Part IV, volume 13794 of Lecture Notes in Computer Science, pp. 537–566. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-22972-5_19

  23. Hu, K., Sun, S., Todo, Y., Wang, M., Wang, Q.: Massive superpoly recovery with nested monomial predictions. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021. LNCS, vol. 13090, pp. 392–421. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92062-3_14

    Chapter  Google Scholar 

  24. Hu, K., Sun, S., Wang, M., Wang, Q.: An algebraic formulation of the division property: revisiting degree evaluations, cube attacks, and key-independent sums. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12491, pp. 446–476. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64837-4_15

    Chapter  Google Scholar 

  25. Huang, S., Wang, X., Xu, G., Wang, M., Zhao, J.: Conditional cube attack on reduced-round keccak sponge function. In: Coron, J.-S., Nielsen, J.B., editors, Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2017, Proceedings, Part II, volume 10211 of Lecture Notes in Computer Science, pp. 259–288 (2017)

    Google Scholar 

  26. Lei, H., He, J., Hu, K., Wang, M.: More balanced polynomials: cube attacks on 810- and 825-round trivium with practical complexities. IACR Cryptol. ePrint Arch., 1237 (2023)

    Google Scholar 

  27. Li, Z., Bi, W., Dong, X., Wang, X.: Improved conditional cube attacks on keccak keyed modes with MILP method. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10624, pp. 99–127. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_4

    Chapter  Google Scholar 

  28. Li, Z., Dong, X., Wang, X.: Conditional cube attack on round-reduced ASCON. IACR Trans. Symmetric Cryptol. 2017(1), 175–202 (2017)

    Article  Google Scholar 

  29. Liu, M.: Degree evaluation of NFSR-based cryptosystems. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10403, pp. 227–249. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63697-9_8

    Chapter  Google Scholar 

  30. Liu, M., Yang, J., Wang, W., Lin, D.: Correlation Cube Attacks: from weak-key distinguisher to key recovery. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 715–744. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_23

    Chapter  Google Scholar 

  31. Mroczkowski, P., Szmidt, J.: The cube attack on stream cipher Trivium and quadraticity tests. Fundam. Informaticae 114(3–4), 309–318 (2012)

    Article  MathSciNet  Google Scholar 

  32. Rohit, R., Kai, H., Sarkar, S., Sun, S.: Misuse-free key-recovery and distinguishing attacks on 7-round ascon. IACR Trans. Symmetric Cryptol. 2021(1), 130–155 (2021)

    Article  Google Scholar 

  33. Rohit, R., Sarkar, S.: Diving deep into the weak keys of round reduced ascon. IACR Trans. Symmetric Cryptol. 2021(4), 74–99 (2021)

    Article  Google Scholar 

  34. Salam, I., Bartlett, H., Dawson, E., Pieprzyk, J., Simpson, L., Wong, K.K.-H.: Investigating cube attacks on the authenticated encryption stream cipher ACORN. In: Batten, L., Li, G., editors, ATIS 2016, volume 651 of Communications in Computer and Information Science, pp. 15–26 (2016)

    Google Scholar 

  35. Sasaki, Yu., Todo, Y.: New algorithm for modeling S-box in MILP based differential and division trail search. In: Farshim, P., Simion, E. (eds.) SecITC 2017. LNCS, vol. 10543, pp. 150–165. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-69284-5_11

    Chapter  Google Scholar 

  36. Song, L., Guo, J., Shi, D., Ling, S.: New MILP Modeling: improved conditional cube attacks on keccak-based constructions. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11273, pp. 65–95. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03329-3_3

    Chapter  Google Scholar 

  37. Sun, L., Wang, W., Wang, M.: Automatic search of bit-based division property for ARX ciphers and word-based division property. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10624, pp. 128–157. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_5

    Chapter  Google Scholar 

  38. Sun, L., Wang, W., Wang, M.: MILP-aided bit-based division property for primitives with non-bit-permutation linear layers. IET Inf. Secur. 14(1), 12–20 (2020)

    Article  Google Scholar 

  39. 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: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 158–178. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45611-8_9

    Chapter  Google Scholar 

  40. Sun, Y.: Automatic search of cubes for attacking stream ciphers. IACR Trans. Symmetric Cryptol. 2021(4), 100–123 (2021)

    Article  Google Scholar 

  41. Todo, Y.: Integral cryptanalysis on full MISTY1. In: Gennaro, R., Robshaw, M., editors, CRYPTO 2015, LNCS, vol. 9215, pp. 413–432 (2015)

    Google Scholar 

  42. Todo, Y.: Structural evaluation by generalized integral property. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 287–314. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_12

    Chapter  Google Scholar 

  43. Todo, Y., Isobe, T., Hao, Y., Meier, W.: Cube attacks on non-blackbox polynomials based on division property. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10403, pp. 250–279. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63697-9_9

    Chapter  Google Scholar 

  44. Todo, Y., Morii, M.: Bit-based division property and application to Simon family. In: Peyrin, T. (ed.) FSE 2016. LNCS, vol. 9783, pp. 357–377. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-52993-5_18

    Chapter  Google Scholar 

  45. Wang, J., Qin, L., Wu, B.: Correlation cube attack revisited: improved cube search and superpoly recovery techniques. Cryptology ePrint Archive, Paper 2023/1408 (2023). https://eprint.iacr.org/2023/1408

  46. Wang, J., Wu, B., Liu, Z.: Improved degree evaluation and superpoly recovery methods with application to trivium. CoRR, abs/2201.06394 (2022)

    Google Scholar 

  47. Wang, Q., Grassi, L., Rechberger, C.: Zero-sum partitions of PHOTON permutations. In: Smart, N.P. (ed.) CT-RSA 2018. LNCS, vol. 10808, pp. 279–299. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-76953-0_15

    Chapter  Google Scholar 

  48. Wang, Q., Hao, Y., Todo, Y., Li, C., Isobe, T., Meier, W.: Improved division property based cube attacks exploiting algebraic properties of superpoly. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 275–305. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_10

    Chapter  Google Scholar 

  49. Wang, S., Hu, B., Guan, J., Zhang, K., Shi, T.: MILP-aided method of searching division property using three subsets and applications. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019. LNCS, vol. 11923, pp. 398–427. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34618-8_14

    Chapter  Google Scholar 

  50. 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: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 648–678. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_24

    Chapter  Google Scholar 

  51. Ye, C., Tian, T.: A new framework for finding nonlinear superpolies in cube attacks against trivium-like ciphers. In: Susilo, W., Yang, G. (eds.) ACISP 2018. LNCS, vol. 10946, pp. 172–187. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-93638-3_11

    Chapter  Google Scholar 

  52. Ye, C.-D., Tian, T.: A practical key-recovery attack on 805-round trivium. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021. LNCS, vol. 13090, pp. 187–213. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92062-3_7

    Chapter  Google Scholar 

Download references

Acknowledgment

The authors would like to thank the anonymous reviewers for their valuable comments and suggestions to improve the quality of the paper. This research is supported by the National Key Research and Development Program of China (Grant No. 2018YFA0704702), the National Natural Science Foundation of China (Grant No. 62032014, U2336207), Department of Science & Technology of Shandong Province (No. SYS202201), Quan Cheng Laboratory (Grant No. QCLZD202301, QCLZD202306). Kai Hu is supported by the “ANR-NRF project SELECT”. The scientific calculations in this paper have been done on the HPC Cloud Platform of Shandong University.

Author information

Authors and Affiliations

  1. School of Cyber Science and Technology, Shandong University, Qingdao, Shandong, China

    Jiahui He, Kai Hu, Hao Lei & Meiqin Wang

  2. Quan Cheng Shandong Laboratory, Jinan, China

    Meiqin Wang

  3. Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China

    Jiahui He, Kai Hu, Hao Lei & Meiqin Wang

  4. School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, Singapore

    Kai Hu

Authors
  1. Jiahui He
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kai Hu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hao Lei
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Meiqin Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Meiqin Wang .

Editor information

Editors and Affiliations

  1. Zama, Paris, France

    Marc Joye

  2. Ruhr University Bochum, Bochum, Germany

    Gregor Leander

Rights and permissions

Reprints and permissions

Copyright information

© 2024 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

He, J., Hu, K., Lei, H., Wang, M. (2024). Massive Superpoly Recovery with a Meet-in-the-Middle Framework. In: Joye, M., Leander, G. (eds) Advances in Cryptology – EUROCRYPT 2024. EUROCRYPT 2024. Lecture Notes in Computer Science, vol 14651. Springer, Cham. https://doi.org/10.1007/978-3-031-58716-0_13

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-58716-0_13

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-58715-3

  • Online ISBN: 978-3-031-58716-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation