iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/978-3-031-58716-0_12
Probabilistic Extensions: A One-Step Framework for Finding Rectangle Attacks and Beyond | SpringerLink
Skip to main content
Springer Nature Link
Log in

Probabilistic Extensions: A One-Step Framework for Finding Rectangle Attacks and Beyond

  • 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

In differential-like attacks, the process typically involves extending a distinguisher forward and backward with probability 1 for some rounds and recovering the key involved in the extended part. Particularly in rectangle attacks, a holistic key recovery strategy can be employed to yield the most efficient attacks tailored to a given distinguisher. In this paper, we treat the distinguisher and the extended part as an integrated entity and give a one-step framework for finding rectangle attacks with the purpose of reducing the overall complexity or attacking more rounds. In this framework, we propose to allow probabilistic differential propagations in the extended part and incorporate the holistic recovery strategy. Additionally, we introduce the “split-and-bunch technique” to further reduce the time complexity. Beyond rectangle attacks, we extend these foundational concepts to encompass differential attacks as well. To demonstrate the efficiency of our framework, we apply it to Deoxys-BC-384, SKINNY, ForkSkinny, and CRAFT, achieving a series of refined and improved rectangle attacks and differential attacks. Notably, we obtain the first 15-round attack on Deoxys-BC-384, narrowing its security margin to only one round. Furthermore, our differential attack on CRAFT extends to 23 rounds, covering two more rounds than the previous best attacks.

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
$34.99 /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
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 189.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 139.99
Price excludes VAT (USA)
  • 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

Similar content being viewed by others

Notes

  1. 1.

    We use a variant of formulas from Sect. 2.3 in the related-key setting for ciphers with a linear key schedule.

References

  1. Anderson, R., Biham, E., Knudsen, L.: Serpent: a proposal for the advanced encryption standard. NIST AES Proposal 174, 1–23 (1998)

    Google Scholar 

  2. Boura, C., David, N., Derbez, P., Leander, G., Naya-Plasencia, M.: Differential meet-in-the-middle cryptanalysis. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023, Part III. LNCS, vol. 14083, pp. 240–272. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-38548-3_9

    Chapter  Google Scholar 

  3. Biham, E., Dunkelman, O., Keller, N.: The rectangle attack — rectangling the serpent. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 340–357. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44987-6_21

    Chapter  Google Scholar 

  4. Biham, E., Dunkelman, O., Keller, N.: New results on boomerang and rectangle attacks. In: Daemen, J., Rijmen, V. (eds.) FSE 2002. LNCS, vol. 2365, pp. 1–16. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45661-9_1

    Chapter  Google Scholar 

  5. Beierle, C., et al.: The SKINNY family of block ciphers and its low-latency variant MANTIS. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part II. LNCS, vol. 9815, pp. 123–153. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_5

    Chapter  Google Scholar 

  6. Biryukov, A., Khovratovich, D.: Related-key cryptanalysis of the full AES-192 and AES-256. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 1–18. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10366-7_1

    Chapter  Google Scholar 

  7. Bariant, A., Leurent, G.: Truncated boomerang attacks and application to AES-based ciphers. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part IV. LNCS, vol. 14007, pp. 3–35. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-30634-1_1

    Chapter  Google Scholar 

  8. Beierle, C., Leander, G., Moradi, A., Rasoolzadeh, S.: CRAFT: lightweight tweakable block cipher with efficient protection against DFA attacks. IACR Trans. Symmetric Cryptol. 2019(1), 5–45 (2019)

    Article  Google Scholar 

  9. Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. J. Cryptol. 4(1), 3–72 (1991)

    Article  MathSciNet  Google Scholar 

  10. Cid, C., Huang, T., Peyrin, T., Sasaki, Yu., Song, L.: Boomerang connectivity table: a new cryptanalysis tool. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 683–714. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_22

    Chapter  Google Scholar 

  11. Delaune, S., Derbez, P., Vavrille, M.: Catching the fastest boomerangs - application to SKINNY. IACR Cryptology ePrint Archive, p. 20 (2021)

    Google Scholar 

  12. Derbez, P., Euler, M., Fouque, P.A., Nguyen, P.H.: Revisiting related-key boomerang attacks on AES using computer-aided tool. In: Agrawal, S., Lin, D. (eds.) ASIACRYPT 2022, Part III. LNCS, vol. 13793, pp. 68–88. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-22969-5_3

    Chapter  Google Scholar 

  13. Dinur, I.: Improved differential cryptanalysis of round-reduced speck. In: Joux, A., Youssef, A. (eds.) SAC 2014. LNCS, vol. 8781, pp. 147–164. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13051-4_9

    Chapter  Google Scholar 

  14. Dunkelman, O., Keller, N., Shamir, A.: A practical-time related-key attack on the Kasumi cryptosystem used in GSM and 3G telephony. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 393–410. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_21

    Chapter  Google Scholar 

  15. Dunkelman, O., Keller, N., Shamir, A.: A practical-time related-key attack on the KASUMI cryptosystem used in GSM and 3G telephony. J. Cryptol. 27(4), 824–849 (2014)

    Article  MathSciNet  Google Scholar 

  16. Dong, X., Qin, L., Sun, S., Wang, X.: Key guessing strategies for linear key-schedule algorithms in rectangle attacks. IACR Cryptology ePrint Archive, p. 856 (2021)

    Google Scholar 

  17. Dong, X., Qin, L., Sun, S., Wang, X.: Key guessing strategies for linear key-schedule algorithms in rectangle attacks. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022, Part III. LNCS, vol. 13277, pp. 3–33. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-07082-2_1

  18. Guo, H., et al.: Differential attacks on CRAFT exploiting the involutory s-boxes and tweak additions. IACR Trans. Symmetric Cryptol. 2020(3), 119–151 (2020)

    Article  Google Scholar 

  19. Hadipour, H., Bagheri, N., Song, L.: Improved rectangle attacks on SKINNY and CRAFT. IACR Trans. Symmetric Cryptol. 2021(2), 140–198 (2021)

    Article  Google Scholar 

  20. Hadipour, H., Sadeghi, S., Eichlseder, M.: Finding the impossible: automated search for full impossible-differential, zero-correlation, and integral attacks. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023. LNCS, vol. 14007, pp. 128–157. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-30634-1_5

    Chapter  Google Scholar 

  21. Jean, J., Nikolić, I., Peyrin, T.: Tweaks and keys for block ciphers: the TWEAKEY framework. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, Part II. LNCS, vol. 8874, pp. 274–288. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45608-8_15

    Chapter  Google Scholar 

  22. Jean, J., Nikolic, I., Peyrin, T., Seurin, Y.: Deoxys v1. 41. In: Submitted to CAESAR, vol. 124 (2016)

    Google Scholar 

  23. Kelsey, J., Kohno, T., Schneier, B.: Amplified boomerang attacks against reduced-round MARS and serpent. In: Goos, G., Hartmanis, J., van Leeuwen, J., Schneier, B. (eds.) FSE 2000. LNCS, vol. 1978, pp. 75–93. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44706-7_6

    Chapter  Google Scholar 

  24. Knudsen, L.R.: Truncated and higher order differentials. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 196–211. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-60590-8_16

    Chapter  Google Scholar 

  25. Liu, G., Ghosh, M., Song, L.: Security analysis of SKINNY under related-TWEAKEY settings. IACR Trans. Symmetric Cryptol. 2017(3), 37–72 (2017)

    Article  Google Scholar 

  26. Leander, G., Rasoolzadeh, S.: Weak tweak-keys for the CRAFT block cipher. IACR Trans. Symmetric Cryptol. 2022(1), 38–63 (2022)

    Article  Google Scholar 

  27. Matsui, M.: On correlation between the order of S-boxes and the strength of DES. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 366–375. Springer, Heidelberg (1995). https://doi.org/10.1007/BFb0053451

    Chapter  Google Scholar 

  28. Mouha, N., Preneel, B.: A proof that the ARX cipher Salsa20 is secure against differential cryptanalysis. IACR Cryptology ePrint Archive, p. 328 (2013)

    Google Scholar 

  29. Murphy, S.: The return of the cryptographic boomerang. IEEE Trans. Inf. Theory 57(4), 2517–2521 (2011)

    Article  MathSciNet  Google Scholar 

  30. Qin, L., Dong, X., Wang, X., Jia, K., Liu, Y.: Automated search oriented to key recovery on ciphers with linear key schedule applications to boomerangs in SKINNY and FORKSKINNY. IACR Trans. Symmetric Cryptol. 2021(2), 249–291 (2021)

    Article  Google Scholar 

  31. 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, Part I. LNCS, vol. 8873, pp. 158–178. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45611-8_9

    Chapter  Google Scholar 

  32. Song, L., Qin, X., Lei, H.: Boomerang connectivity table revisited: application to SKINNY and AES. IACR Trans. Symmetric Cryptol. 2019(1), 118–141 (2019)

    Article  Google Scholar 

  33. Shi, D., Sun, S., Derbez, P., Todo, Y., Sun, B., Hu, L.: Programming the Demirci-Selçuk meet-in-the-middle attack with constraints. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018, Part II. LNCS, vol. 11273, pp. 3–34. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03329-3_1

    Chapter  Google Scholar 

  34. Song, L., Yang, Q., Chen, Y., Hu, L., Weng, J.: Probabilistic extensions: a one-step framework for finding rectangle attacks and beyond. Cryptology ePrint Archive, Paper 2024/344 (2024). https://eprint.iacr.org/2024/344

  35. Song, L., Yang, Q., Liu, H.: Revisiting the differential meet-in-the-middle cryptanalysis. IACR Cryptology ePrint Archive, p. 1302 (2023)

    Google Scholar 

  36. Song, L., et al.: Optimizing rectangle attacks: a unified and generic framework for key recovery. In: Agrawal, S., Lin, D. (eds.) ASIACRYPT 2022, Part I. Lecture Notes in Computer Science, vol. 13791, pp. 410–440. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-22963-3_14

    Chapter  Google Scholar 

  37. Wagner, D.: The boomerang attack. In: Knudsen, L. (ed.) FSE 1999. LNCS, vol. 1636, pp. 156–170. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48519-8_12

    Chapter  Google Scholar 

  38. Zong, R., Dong, X., Chen, H., Luo, Y., Wang, S., Li, Z.: Towards key-recovery-attack friendly distinguishers: application to GIFT-128. IACR Trans. Symmetric Cryptol. 2021(1), 156–184 (2021)

    Article  Google Scholar 

  39. Zhao, B., Dong, X., Jia, K.: New related-TWEAKEY boomerang and rectangle attacks on Deoxys-BC including BDT effect. IACR Trans. Symmetric Cryptol. pp. 121–151 (2019)

    Google Scholar 

  40. Zhao, B., Dong, X., Meier, W., Jia, K., Wang, G.: Generalized related-key rectangle attacks on block ciphers with linear key schedule: applications to SKINNY and GIFT. Des. Codes Crypt. 88(6), 1103–1126 (2020)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgement

The authors would like to thank anonymous reviewers for their helpful comments and suggestions and Ye Luo for preparing some figures. The work of this paper was supported by the National Key Research and Development Program (No. 2018YFA0704704) and the National Natural Science Foundation of China (Grants 62202460, 62372213, 62132008, 62022036). Jian Weng is supported by the National Natural Science Foundation of China under Grant Nos. 61825203, 62332007, and U22B2028, Science and Technology Major Project of Tibetan Autonomous Region of China under Grant No. XZ202201ZD0006G, National Joint Engineering Research Center of Network Security Detection and Protection Technology, Guangdong Key Laboratory of Data Security and Privacy Preserving, Guangdong Hong Kong Joint Laboratory for Data Security and Privacy Protection, and Engineering Research Center of Trustworthy AI, Ministry of Education.

Author information

Authors and Affiliations

  1. Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China

    Qianqian Yang & Lei Hu

  2. College of Cyber Security, Jinan University, Guangzhou, China

    Ling Song, Yincen Chen & Jian Weng

  3. National Joint Engineering Research Center of Network Security Detection and Protection Technology, Jinan University, Guangzhou, China

    Ling Song, Yincen Chen & Jian Weng

  4. Guangdong Key Laboratory of Data Security and Privacy Preserving, Jinan University, Guangzhou, China

    Jian Weng

  5. School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

    Qianqian Yang & Lei Hu

Authors
  1. Ling Song
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Qianqian Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yincen Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Lei Hu
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Jian Weng
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Qianqian Yang .

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

Song, L., Yang, Q., Chen, Y., Hu, L., Weng, J. (2024). Probabilistic Extensions: A One-Step Framework for Finding Rectangle Attacks and Beyond. 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_12

Download citation

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

  • 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