SpringerLink
Log in

Truncated Boomerang Attacks and Application to AES-Based Ciphers

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

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

Abstract

The boomerang attack is a cryptanalysis technique that combines two short differentials instead of using a single long differential. It has been applied to many primitives, and results in the best known attacks against several AES-based ciphers (Kiasu-BC, Deoxys-BC). In this paper, we introduce a general framework for boomerang attacks with truncated differentials.

We show that the use of truncated differentials provides a significant improvement over the best boomerang attacks in the literature. In particular, we take into account structures on the plaintext and ciphertext sides, and include an analysis of the key recovery step. On 6-round AES, we obtain a competitive structural distinguisher with complexity \(2^{87}\) and a key recovery attack with complexity \(2^{61}\).

The truncated boomerang attack is particularly effective against tweakable AES variants. We apply it to 8-round Kiasu-BC, resulting in the best known attack with complexity \(2^{83}\) (rather than \(2^{103}\)). We also show an interesting use of the 6-round distinguisher on the full TNT-AES, a tweakable block cipher using 6-round AES as a building block. Finally, we apply this framework to Deoxys-BC, using a MILP model to find optimal trails automatically. We obtain the best attacks against round-reduced versions of all variants of Deoxys-BC.

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
EUR 32.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
EUR 29.95
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 85.59
Price includes VAT (Germany)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 106.99
Price includes VAT (Germany)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** 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.

    S-Box 3 on the plaintext side has two pairs \((x, x + \delta ), (x', x'+\delta )\) following the transition fixed by the trail. Instead of listing four key candidates, we identify one of the \(2^6\) cosets of \(\langle \delta , x+x' \rangle \).

References

  1. Bao, Z., Guo, C., Guo, J., Song, L.: TNT: how to tweak a block cipher. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12106, pp. 641–673. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45724-2_22

    Chapter  Google Scholar 

  2. Bao, Z., Guo, J., List, E.: Extended truncated-differential distinguishers on round-reduced AES. IACR Trans. Symm. Cryptol. 2020(3), 197–261 (2020). https://doi.org/10.13154/tosc.v2020.i3.197-261

  3. Bar-On, A., Dunkelman, O., Keller, N., Ronen, E., Shamir, A.: Improved key recovery attacks on reduced-round AES with practical data and memory complexities. J. Cryptol. 33(3), 1003–1043 (2019). https://doi.org/10.1007/s00145-019-09336-w

    Article  MathSciNet  MATH  Google Scholar 

  4. Bardeh, N.G.: A key-independent distinguisher for 6-round AES in an adaptive setting. Cryptology ePrint Archive, Report 2019/945 (2019). https://eprint.iacr.org/2019/945

  5. Bardeh, N.G., Rønjom, S.: The exchange attack: how to distinguish six rounds of AES with \(2^{88.2}\)chosen plaintexts. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019. LNCS, vol. 11923, pp. 347–370. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34618-8_12

    Chapter  Google Scholar 

  6. Bariant, A., Leurent, G.: Truncated boomerang attacks and application to AES-based ciphers. Cryptology ePrint Archive, Report 2022/701 (2022). https://eprint.iacr.org/2022/701

  7. Bariant, A., Leurent, G.: Truncated boomerang attacks and application to AES-based ciphers – Additional data (2023). https://github.com/AugustinBariant/Truncated_boomerangs

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

  9. 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 

  10. Biryukov, A.: The boomerang attack on 5 and 6-round reduced AES. In: Dobbertin, H., Rijmen, V., Sowa, A. (eds.) AES 2004. LNCS, vol. 3373, pp. 11–15. Springer, Heidelberg (2005). https://doi.org/10.1007/11506447_2

    Chapter  MATH  Google Scholar 

  11. Boura, C., Lallemand, V., Naya-Plasencia, M., Suder, V.: Making the impossible possible. J. Cryptol. 31(1), 101–133 (2017). https://doi.org/10.1007/s00145-016-9251-7

    Article  MathSciNet  MATH  Google Scholar 

  12. Cid, C., Huang, T., Peyrin, T., Sasaki, Y., Song, L.: A security analysis of Deoxys and its internal tweakable block ciphers. IACR Trans. Symm. Cryptol. 2017(3), 73–107 (2017). https://doi.org/10.13154/tosc.v2017.i3.73-107

  13. Cid, C., Huang, T., Peyrin, T., Sasaki, Y., 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 

  14. Daemen, J., Knudsen, L., Rijmen, V.: The block cipher square. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 149–165. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0052343

    Chapter  Google Scholar 

  15. Daemen, J., Rijmen, V.: The Design of Rijndael, vol. 2. Springer, Heidelberg (2002). https://doi.org/10.1007/978-3-662-04722-4

  16. Delaune, S., Derbez, P., Vavrille, M.: Catching the fastest boomerangs application to SKINNY. IACR Trans. Symm. Cryptol. 2020(4), 104–129 (2020). https://doi.org/10.46586/tosc.v2020.i4.104-129

  17. Dobraunig, C., Eichlseder, M., Mendel, F.: Square attack on 7-round Kiasu-BC. In: Manulis, M., Sadeghi, A.-R., Schneider, S. (eds.) ACNS 2016. LNCS, vol. 9696, pp. 500–517. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-39555-5_27

    Chapter  Google Scholar 

  18. Dobraunig, C., List, E.: Impossible-differential and boomerang cryptanalysis of round-reduced Kiasu-BC. In: Handschuh, H. (ed.) CT-RSA 2017. LNCS, vol. 10159, pp. 207–222. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-52153-4_12

    Chapter  Google Scholar 

  19. Dunkelman, O., Keller, N., Ronen, E., Shamir, A.: The retracing boomerang attack. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 280–309. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45721-1_11

    Chapter  Google Scholar 

  20. 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  MATH  Google Scholar 

  21. Ferguson, N., et al.: Improved cryptanalysis of Rijndael. In: Goos, G., Hartmanis, J., van Leeuwen, J., Schneier, B. (eds.) FSE 2000. LNCS, vol. 1978, pp. 213–230. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44706-7_15

    Chapter  Google Scholar 

  22. Grassi, L.: MixColumns properties and attacks on (round-reduced) AES with a single secret S-box. In: Smart, N.P. (ed.) CT-RSA 2018. LNCS, vol. 10808, pp. 243–263. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-76953-0_13

    Chapter  Google Scholar 

  23. Grassi, L., Rechberger, C., Rønjom, S.: Subspace trail cryptanalysis and its applications to AES. IACR Trans. Symm. Cryptol. 2016(2), 192–225 (2016). https://doi.org/10.13154/tosc.v2016.i2.192-225, https://tosc.iacr.org/index.php/ToSC/article/view/571

  24. Grassi, L., Rechberger, C., Rønjom, S.: A new structural-differential property of 5-round AES. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 289–317. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56614-6_10

    Chapter  Google Scholar 

  25. Guo, C., Guo, J., List, E., Song, L.: Towards closing the security gap of tweak-and-tweak (TNT). In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12491, pp. 567–597. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64837-4_19

    Chapter  Google Scholar 

  26. Jean, J., Nikolić, I., Peyrin, T.: Kiasu v1. Submitted to the CAESAR competition (2014)

    Google Scholar 

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

    Chapter  Google Scholar 

  28. Jean, J., Nikolić, I., Peyrin, T., Seurin, Y.: The Deoxys AEAD family. J. Cryptol. 34(3), 1–51 (2021). https://doi.org/10.1007/s00145-021-09397-w

    Article  MathSciNet  MATH  Google Scholar 

  29. Mantin, I., Shamir, A.: A practical attack on broadcast RC4. In: Matsui, M. (ed.) FSE 2001. LNCS, vol. 2355, pp. 152–164. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45473-X_13

    Chapter  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  31. Qin, L., Dong, X., Wang, X., Jia, K., Liu, Y.: Automated search oriented to key recovery on ciphers with linear key schedule. IACR Trans. Symm. Cryptol. 2021(2), 249–291 (2021). https://doi.org/10.46586/tosc.v2021.i2.249-291

  32. Rahman, M., Saha, D., Paul, G.: Boomeyong: embedding yoyo within boomerang and its applications to key recovery attacks on AES and Pholkos. IACR Trans. Symm. Cryptol. 2021(3), 137–169 (2021). https://doi.org/10.46586/tosc.v2021.i3.137-169

  33. Rønjom, S., Bardeh, N.G., Helleseth, T.: Yoyo tricks with AES. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10624, pp. 217–243. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_8

    Chapter  Google Scholar 

  34. Sasaki, Y.: Improved related-tweakey boomerang attacks on Deoxys-BC. In: Joux, A., Nitaj, A., Rachidi, T. (eds.) AFRICACRYPT 2018. LNCS, vol. 10831, pp. 87–106. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-89339-6_6

    Chapter  Google Scholar 

  35. Selçuk, A.A.: On probability of success in linear and differential cryptanalysis. J. Cryptol. 21(1), 131–147 (2007). https://doi.org/10.1007/s00145-007-9013-7

    Article  MathSciNet  MATH  Google Scholar 

  36. Song, L., Qin, X., Hu, L.: Boomerang connectivity table revisited. IACR Trans. Symm. Cryptol. 2019(1), 118–141 (2019). https://doi.org/10.13154/tosc.v2019.i1.118-141

  37. Tiessen, T., Knudsen, L.R., Kölbl, S., Lauridsen, M.M.: Security of the AES with a secret S-box. In: Leander, G. (ed.) FSE 2015. LNCS, vol. 9054, pp. 175–189. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48116-5_9

    Chapter  Google Scholar 

  38. Tolba, M., Abdelkhalek, A., Youssef, A.M.: A meet in the middle attack on reduced round Kiasu-BC. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 99(10), 1888–1890 (2016)

    Article  MATH  Google Scholar 

  39. 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 

  40. Wang, H., Peyrin, T.: Boomerang switch in multiple rounds. IACR Trans. Symm. Cryptol. 2019(1), 142–169 (2019). https://doi.org/10.13154/tosc.v2019.i1.142-169

  41. Yang, Q., Song, L., Sun, S., Shi, D., Hu, L.: New properties of the double boomerang connectivity table. IACR Trans. Symmetric Cryptol. 2022(4), 208–242 (2022). https://doi.org/10.46586/tosc.v2022.i4.208-242, https://tosc.iacr.org/index.php/ToSC/article/view/9977

  42. Zhao, B., Dong, X., Jia, K.: New related-tweakey boomerang and rectangle attacks on deoxys-bc including BDT effect. IACR Trans. Symm. Cryptol. 2019(3), 121–151 (2019). https://doi.org/10.13154/tosc.v2019.i3.121-151

  43. Zhao, B., Dong, X., Jia, K., Meier, W.: Improved related-tweakey rectangle attacks on reduced-round Deoxys-BC-384 and Deoxys-I-256-128. In: Hao, F., Ruj, S., Sen Gupta, S. (eds.) INDOCRYPT 2019. LNCS, vol. 11898, pp. 139–159. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-35423-7_7

    Chapter  Google Scholar 

Download references

Acknowledgement

We would like to thank the authors of [12] for providing the code they used to generate the MILP programs. This work was supported by the French Ministry of Defence (AID), and by the French Agence Nationale de la Recherche (ANR), under grant ANR-20-CE48-0017 (project SELECT).

Author information

Authors and Affiliations

  1. Inria, Paris, France

    Augustin Bariant & Gaëtan Leurent

Authors
  1. Augustin Bariant
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gaëtan Leurent
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Gaëtan Leurent .

Editor information

Editors and Affiliations

  1. Bar-Ilan University, Ramat Gan, Israel

    Carmit Hazay

  2. Simula UiB, Bergen, Norway

    Martijn Stam

Rights and permissions

Reprints and permissions

Copyright information

© 2023 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Bariant, A., Leurent, G. (2023). Truncated Boomerang Attacks and Application to AES-Based Ciphers. In: Hazay, C., Stam, M. (eds) Advances in Cryptology – EUROCRYPT 2023. EUROCRYPT 2023. Lecture Notes in Computer Science, vol 14007. Springer, Cham. https://doi.org/10.1007/978-3-031-30634-1_1

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-30634-1_1

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-30633-4

  • Online ISBN: 978-3-031-30634-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation