A Holistic Framework for Impossible Boomerang Attacks
Authors
Yincen Chen, Qinggan Fu, Ning Zhao, Jiahao Zhao, Ling Song, Qianqian Yang
Yincen Chen
College of Cyber Security, Jinan University, Guangzhou, China
icsnow98 at gmail dot com
icsnow98 at gmail dot com
Qinggan Fu
College of Cyber Security, Jinan University, Guangzhou, China
fuqinggan at stu2018 dot jnu dot edu dot cn
fuqinggan at stu2018 dot jnu dot edu dot cn
Ning Zhao
College of Cyber Security, Jinan University, Guangzhou, China
znkirito023 at gmail dot com
znkirito023 at gmail dot com
Jiahao Zhao
Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China
School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
zhaojiahao at iie dot ac dot cn
School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
zhaojiahao at iie dot ac dot cn
Ling Song
College of Cyber Security, Jinan University, Guangzhou, China
National Joint Engineering Research Center of Network Security Detection and Protection Technology, Jinan University, Guangzhou, China
songling dot qs at gmail dot com
National Joint Engineering Research Center of Network Security Detection and Protection Technology, Jinan University, Guangzhou, China
songling dot qs at gmail dot com
Qianqian Yang
Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China
School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
yangqianqian at iie dot ac dot cn
School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
yangqianqian at iie dot ac dot cn
Keywords:
Impossible boomerang
Guessing strategy
Meet-in-the-Middle
{Deoxys-BC}
{Joltik-BC}
{SKINNYe v2}
Abstract
In 2011, Lu introduced the impossible boomerang attack at DCC. This powerful cryptanalysis technique combines the strengths of the impossible differential and boomerang attacks, thereby inheriting the advantages of both cryptographic techniques. In this paper, we propose a holistic framework comprising two generic and effective algorithms and a MILP-based model to search for the optimal impossible boomerang attack systematically. The first algorithm incorporates any key guessing strategy, while the second integrates the meet-in-the-middle (MITM) attack into the key recovery process. The MILP-based model combines the generic key recovery algorithms and supports the arbitrary location of the contradiction. Our highly flexible framework treats the distinguisher and the extended part as a whole, returning the optimal attack parameters and complexity. When applying our framework to Deoxys-BC-256, Deoxys-BC-384, Joltik-BC-128, Joltik-BC-192, and SKINNYe v2, we achieve several significant improvements. We achieve the first 11-round impossible boomerang attacks on Deoxys-BC-256 and Joltik-BC-128. For SKINNYe v2, we achieve the first 33-round impossible boomerang attack, then using the MITM approach in the key recovery attack, the time complexity is significantly reduced. Additionally, for the 14-round Deoxys-BC-384 and Joltik-BC-192, the time complexity of the impossible boomerang attack is reduced by factors exceeding $2^{27}$ and $2^{12}$, respectively.
References
[AKM+24]
Zahra Ahmadian, Akram Khalesi, Dounia M'foukh, Hossein Moghimi, and María Naya-Plasencia. Improved Differential Meet-in-the-Middle Cryptanalysis. In Marc Joye and Gregor Leander, editors, Advances in Cryptology - EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Switzerland, May 26-30, 2024, Proceedings, Part I, volume 14651 of Lecture Notes in Computer Science, pages 280–309. 2024. Springer. DOI: 10.1007/978-3-031-58716-0_10
[BBS99a]
Eli Biham, Alex Biryukov, and Adi Shamir. Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials. In Jacques Stern, editor, Advances in Cryptology - EUROCRYPT '99, International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, May 2-6, 1999, Proceeding, volume 1592 of Lecture Notes in Computer Science, pages 12–23. 1999. Springer. DOI: 10.1007/3-540-48910-X_2
[BBS99b]
Eli Biham, Alex Biryukov, and Adi Shamir. Miss in the Middle Attacks on IDEA and Khufu. In Lars R. Knudsen, editor, Fast Software Encryption, 6th International Workshop, FSE '99, Rome, Italy, March 24-26, 1999, Proceedings, volume 1636 of Lecture Notes in Computer Science, pages 124–138. 1999. Springer. DOI: 10.1007/3-540-48519-8_10
[BCL+24]
Xavier Bonnetain, Margarita Cordero, Virginie Lallemand, Marine Minier, and María Naya-Plasencia. On Impossible Boomerang Attacks Application to Simon and SKINNYee. IACR Trans. Symmetric Cryptol., 2024(2):222–253, 2024. DOI: 10.46586/TOSC.V2024.I2.222-253
[BDD+23]
Christina Boura, Nicolas David, Patrick Derbez, Gregor Leander, and María Naya-Plasencia. Differential Meet-In-The-Middle Cryptanalysis. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part III, volume 14083 of Lecture Notes in Computer Science, pages 240–272. 2023. Springer. DOI: 10.1007/978-3-031-38548-3_9
[BDK01]
Eli Biham, Orr Dunkelman, and Nathan Keller. The Rectangle Attack - Rectangling the Serpent. In Birgit Pfitzmann, editor, Advances in Cryptology - EUROCRYPT 2001, International Conference on the Theory and Application of Cryptographic Techniques, Innsbruck, Austria, May 6-10, 2001, Proceeding, volume 2045 of Lecture Notes in Computer Science, pages 340–357. 2001. Springer. DOI: 10.1007/3-540-44987-6_21
[BJK+16]
Christof Beierle, Jérémy Jean, Stefan Kölbl, Gregor Leander, Amir Moradi, Thomas Peyrin, Yu Sasaki, Pascal Sasdrich, and Siang Meng Sim. The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part II, volume 9815 of Lecture Notes in Computer Science, pages 123–153. 2016. Springer. DOI: 10.1007/978-3-662-53008-5_5
[BL23]
Augustin Bariant and Gaëtan Leurent. Truncated Boomerang Attacks and Application to AES-based Ciphers. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part IV, volume 14007 of Lecture Notes in Computer Science, pages 3–35. 2023. Springer. DOI: 10.1007/978-3-031-30634-1_1
[BL24]
Xavier Bonnetain and Virginie Lallemand. A Note on the use of the Double Boomerang Connectivity Table (DBCT) for Spotting Impossibilities. Cryptology ePrint Archive, Paper 2024/1218. 2024.
[BS91]
Eli Biham and Adi Shamir. Differential Cryptanalysis of DES-like Cryptosystems. J. Cryptol., 4(1):3–72, 1991. DOI: 10.1007/BF00630563
[CHP+17]
Carlos Cid, Tao Huang, Thomas Peyrin, Yu Sasaki, and Ling Song. A Security Analysis of Deoxys and its Internal Tweakable Block Ciphers. IACR Trans. Symmetric Cryptol., 2017(3):73–107, 2017. DOI: 10.13154/TOSC.V2017.I3.73-107
[CHP+18]
Carlos Cid, Tao Huang, Thomas Peyrin, Yu Sasaki, and Ling Song. Boomerang Connectivity Table: A New Cryptanalysis Tool. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part II, volume 10821 of Lecture Notes in Computer Science, pages 683–714. 2018. Springer. DOI: 10.1007/978-3-319-78375-8_22
[DKS10]
Orr Dunkelman, Nathan Keller, and Adi Shamir. A Practical-Time Related-Key Attack on the KASUMI Cryptosystem Used in GSM and 3G Telephony. In Tal Rabin, editor, Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings, volume 6223 of Lecture Notes in Computer Science, pages 393–410. 2010. Springer. DOI: 10.1007/978-3-642-14623-7_21
[HBS21]
Hosein Hadipour, Nasour Bagheri, and Ling Song. Improved Rectangle Attacks on SKINNY and CRAFT. IACR Trans. Symmetric Cryptol., 2021(2):140–198, 2021. DOI: 10.46586/TOSC.V2021.I2.140-198
[HFJ+24]
Xichao Hu, Dengguo Feng, Lin Jiao, Yonglin Hao, Xinxin Gong, and Yongqiang Li. A Deep Study of The Impossible Boomerang Distinguishers: New Construction Theory and Automatic Search Methods. IACR Cryptol. ePrint Arch., 2024.
[HGSE24]
Hosein Hadipour, Simon Gerhalter, Sadegh Sadeghi, and Maria Eichlseder. Improved Search for Integral, Impossible Differential and Zero-Correlation Attacks Application to Ascon, ForkSKINNY, SKINNY, MANTIS, PRESENT and QARMAv2. IACR Trans. Symmetric Cryptol., 2024(1):234–325, 2024. DOI: 10.46586/TOSC.V2024.I1.234-325
[JNP14]
Jérémy Jean, Ivica Nikolic, and Thomas Peyrin. Tweaks and Keys for Block Ciphers: The TWEAKEY Framework. In Palash Sarkar and Tetsu Iwata, editors, Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014, Proceedings, Part II, volume 8874 of Lecture Notes in Computer Science, pages 274–288. 2014. Springer. DOI: 10.1007/978-3-662-45608-8_15
[JNP15]
Jérémy Jean, Ivica Nikolić, and Thomas Peyrin. Joltik v1. 3. CAESAR Round, 2, 2015.
[JNPS16]
Jérémy Jean, Ivica Nikolic, Thomas Peyrin, and Yannick Seurin. Deoxys v1. 41. Submitted to CAESAR, 124, 2016.
[KHS+03]
Jongsung Kim, Seokhie Hong, Jaechul Sung, Changhoon Lee, and Sangjin Lee. Impossible Differential Cryptanalysis for Block Cipher Structures. In Thomas Johansson and Subhamoy Maitra, editors, Progress in Cryptology - INDOCRYPT 2003, 4th International Conference on Cryptology in India, New Delhi, India, December 8-10, 2003, Proceedings, volume 2904 of Lecture Notes in Computer Science, pages 82–96. 2003. Springer. DOI: 10.1007/978-3-540-24582-7_6
[KKS00]
John Kelsey, Tadayoshi Kohno, and Bruce Schneier. Amplified Boomerang Attacks Against Reduced-Round MARS and Serpent. In Bruce Schneier, editor, Fast Software Encryption, 7th International Workshop, FSE 2000, New York, NY, USA, April 10-12, 2000, Proceedings, volume 1978 of Lecture Notes in Computer Science, pages 75–93. 2000. Springer. DOI: 10.1007/3-540-44706-7_6
[LC21]
Manman Li and Shaozhen Chen. Improved meet-in-the-middle attacks on reduced-round Joltik-BC. IET Inf. Secur., 15(3):247–255, 2021. DOI: 10.1049/ISE2.12019
[Lu08]
Jiqiang Lu. Cryptanalysis of block ciphers. PhD thesis. University of London UK, 2008.
[Lu11]
Jiqiang Lu. The (related-key) impossible boomerang attack and its application to the AES block cipher. Des. Codes Cryptogr., 60(2):123–143, 2011. DOI: 10.1007/S10623-010-9421-9
[MWGP11]
Nicky Mouha, Qingju Wang, Dawu Gu, and Bart Preneel. Differential and Linear Cryptanalysis Using Mixed-Integer Linear Programming. In Chuankun Wu, Moti Yung, and Dongdai Lin, editors, Information Security and Cryptology - 7th International Conference, Inscrypt 2011, Beijing, China, November 30 - December 3, 2011. Revised Selected Papers, volume 7537 of Lecture Notes in Computer Science, pages 57–76. 2011. Springer. DOI: 10.1007/978-3-642-34704-7_5
[NSS20a]
Yusuke Naito, Yu Sasaki, and Takeshi Sugawara. Lightweight Authenticated Encryption Mode Suitable for Threshold Implementation. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part II, volume 12106 of Lecture Notes in Computer Science, pages 705–735. 2020. Springer. DOI: 10.1007/978-3-030-45724-2_24
[NSS20b]
Yusuke Naito, Yu Sasaki, and Takeshi Sugawara. Lightweight Authenticated Encryption Mode Suitable for Threshold Implementation. IACR Cryptol. ePrint Arch., 2020.
[QDW+22]
Lingyue Qin, Xiaoyang Dong, Anyu Wang, Jialiang Hua, and Xiaoyun Wang. Mind the TWEAKEY Schedule: Cryptanalysis on SKINNYe-64-256. In Shweta Agrawal and Dongdai Lin, 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 I, volume 13791 of Lecture Notes in Computer Science, pages 287–317. 2022. Springer. DOI: 10.1007/978-3-031-22963-3_10
[SLY+24]
Ling Song, Huimin Liu, Qianqian Yang, Yincen Chen, Lei Hu, and Jian Weng. Generic Differential Key Recovery Attacks and Beyond. In Kai-Min Chung and Yu Sasaki, editors, Advances in Cryptology - ASIACRYPT 2024 - 30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9-13, 2024, Proceedings, Part VII, volume 15490 of Lecture Notes in Computer Science, pages 361–391. 2024. Springer. DOI: 10.1007/978-981-96-0941-3_12
[ST17]
Yu Sasaki and Yosuke Todo. New Impossible Differential Search Tool from Design and Cryptanalysis Aspects - Revealing Structural Properties of Several Ciphers. In Jean-Sébastien Coron and Jesper Buus Nielsen, 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 III, volume 10212 of Lecture Notes in Computer Science, pages 185–215. 2017. DOI: 10.1007/978-3-319-56617-7_7
[SYC+24]
Ling Song, Qianqian Yang, Yincen Chen, Lei Hu, and Jian Weng. Probabilistic Extensions: A One-Step Framework for Finding Rectangle Attacks and Beyond. In Marc Joye and Gregor Leander, editors, Advances in Cryptology - EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Switzerland, May 26-30, 2024, Proceedings, Part I, volume 14651 of Lecture Notes in Computer Science, pages 339–367. 2024. Springer. DOI: 10.1007/978-3-031-58716-0_12
[SZY+22]
Ling Song, Nana Zhang, Qianqian Yang, Danping Shi, Jiahao Zhao, Lei Hu, and Jian Weng. Optimizing Rectangle Attacks: A Unified and Generic Framework for Key Recovery. In Shweta Agrawal and Dongdai Lin, 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 I, volume 13791 of Lecture Notes in Computer Science, pages 410–440. 2022. Springer. DOI: 10.1007/978-3-031-22963-3_14
[Wag99]
David A. Wagner. The Boomerang Attack. In Lars R. Knudsen, editor, Fast Software Encryption, 6th International Workshop, FSE '99, Rome, Italy, March 24-26, 1999, Proceedings, volume 1636 of Lecture Notes in Computer Science, pages 156–170. 1999. Springer. DOI: 10.1007/3-540-48519-8_12
[WSW+24]
Libo Wang, Ling Song, Baofeng Wu, Mostafizar Rahman, and Takanori Isobe. Revisiting the Boomerang Attack From a Perspective of 3-Differential. IEEE Trans. Inf. Theory, 70(7):5343–5357, 2024. DOI: 10.1109/TIT.2023.3324738
[YSZ+24]
Qianqian Yang, Ling Song, Nana Zhang, Danping Shi, Libo Wang, Jiahao Zhao, Lei Hu, and Jian Weng. Optimizing Rectangle and Boomerang Attacks: A Unified and Generic Framework for Key Recovery. J. Cryptol., 37(2):19, 2024. DOI: 10.1007/S00145-024-09499-1
[ZD19]
Rui Zong and Xiaoyang Dong. MILP-Aided Related-Tweak/Key Impossible Differential Attack and its Applications to QARMA, Joltik-BC. IEEE Access, 7:153683–153693, 2019. DOI: 10.1109/ACCESS.2019.2946638
[ZDW19]
Rui Zong, Xiaoyang Dong, and Xiaoyun Wang. Related-tweakey impossible differential attack on reduced-round Deoxys-BC-256. Sci. China Inf. Sci., 62(3):32102:1–32102:12, 2019. DOI: 10.1007/S11432-017-9382-2
[ZWT24]
Jianing Zhang, Haoyang Wang, and Deng Tang. Impossible Boomerang Attacks Revisited Applications to Deoxys-BC, Joltik-BC and SKINNY. IACR Trans. Symmetric Cryptol., 2024(2):254–295, 2024. DOI: 10.46586/TOSC.V2024.I2.254-295
PDF
History
Submitted: 2025-04-07
Accepted: 2025-06-02
Published: 2025-07-07
Accepted: 2025-06-02
Published: 2025-07-07
How to cite
Yincen Chen, Qinggan Fu, Ning Zhao, Jiahao Zhao, Ling Song, and Qianqian Yang, A Holistic Framework for Impossible Boomerang Attacks. IACR Communications in Cryptology, vol. 2, no. 2, Jul 07, 2025, doi: 10.62056/abhee0zn4.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.