Improved Related-Tweak Attack on Full-Round HALFLOOP-48

SUN Xiaomeng; ZHANG Wenying; YUAN Zhaozhong

doi:10.11999/JEIT251014

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2026 >

SUN Xiaomeng, ZHANG Wenying, YUAN Zhaozhong. Improved Related-Tweak Attack on Full-Round HALFLOOP-48[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT251014

Citation:

SUN Xiaomeng, ZHANG Wenying, YUAN Zhaozhong. Improved Related-Tweak Attack on Full-Round HALFLOOP-48[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT251014

SUN Xiaomeng, ZHANG Wenying, YUAN Zhaozhong. Improved Related-Tweak Attack on Full-Round HALFLOOP-48[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT251014

Citation:

SUN Xiaomeng, ZHANG Wenying, YUAN Zhaozhong. Improved Related-Tweak Attack on Full-Round HALFLOOP-48[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT251014

PDF( 2711 KB)

Improved Related-Tweak Attack on Full-Round HALFLOOP-48

doi: 10.11999/JEIT251014 cstr: 32379.14.JEIT251014

School of Information Science and Engineering, Shandong Normal University, Jinan 250358, China

Funds: The National Natural Science Foundation of China (62272282)

Accepted Date: 2026-01-12
Rev Recd Date: 2026-01-12

Available Online: 2026-01-27

Abstract

Abstract

Objective HALFLOOP, a family of tweakable AES-like lightweight block cipher used to encrypt automatic link establishment messages in the fourth-generation high frequency radio systems. Since the RotateRows and MixColumns operations of HALFLOOP diffuse differences rapidly, it is difficult to build long differentials with higher probability in general, further to attack full cipher. This study aims to attack full HALFLOOP-48 and evaluates the cipher’s resistance to sandwich attacks in setting of related tweak, a critical cryptanalysis method for lightweight ciphers. Methods To attack full HALFLOOP-48, the paper proposes a new truncated sandwich distinguisher framework, which decomposes the cipher into three sub-ciphers:$ {\mathrm{E}}_{0} $, $ {\mathrm{E}}_{1} $ and $ {\mathrm{E}}_{\mathrm{m}} $ to connect with $ {\mathrm{E}}_{0} $, $ {\mathrm{E}}_{1} $. A model is built by using an automatic search method -- Boolean Satisfiability Problem (SAT) for three parts respectively: byte-wise models for $ {\mathrm{E}}_{0} $, $ {\mathrm{E}}_{1} $ together with a bit-wise model for $ {\mathrm{E}}_{\mathrm{m}} $. In $ {\mathrm{E}}_{\mathrm{m}} $, we propose a novel method to effectively model large S-boxes using SAT -- the Affine Subspace Dimensional Reduction method (ADR). The ADR method can turn the problem of modeling a high-dimensional set into two sub-problems for a low-dimensional set. The ADR method makes sure the differentials searched by SAT exist and the accurate probability with reducing the size of Conjunctive Normal Form(CNF) clauses. It also makes the SAT method to search for the longer differentials with large S-boxes effectively. To improve the accuracy of the probability in $ {\mathrm{E}}_{\mathrm{m}} $, we comprehensively evaluate the dependencies between$ {\mathrm{E}}_{0} $ and $ {\mathrm{E}}_{1} $ by considering three layers with multiplying their probability of each layer. The two key-recovery attacks -- a sandwich attack and a rectangle-like sandwich attack can be launched on the sandwich distinguisher in related-tweak scenario. Results and Discussions The SAT-based model reveals a critical vulnerability of the HALFLOOP-48 cipher. We find the first 8 round practical sandwich distinguisher with probability $ {2}^{-43.415} $. Then, an optimal truncated sandwich distinguisher for 8-round HALFLOOP-48 with probability$ {2}^{-43.2} $ is established via the clustering effect of the founded differentials. Compared with the previous results, our distinguisher is practical with extending two more rounds. Employing the 8-round distinguisher, we mount two key-recovery attacks -- a sandwich attack and a rectangle-like sandwich attack on full-round HALFLOOP-48 in related-tweak scenario. The proposed sandwich attack has a data complexity of $ {2}^{32.8} $, time complexity $ {2}^{92.2} $ and memory complexity $ {2}^{42.8} $. For our rectangle-like sandwich attack, the data complexity is $ {2}^{16.2} $, with time complexity $ {2}^{99.2} $ and memory complexity $ {2}^{26.2} $. Compared with the previous results, the key recovery attacks decrease time complexity by $ {2}^{25.4} $and decrease memory complexity by $ {2}^{10} $. Conclusions To overcome the rapidly difference diffusion of HALFLOOP, we derive a new perspective on sandwich attacks with truncated differentials by combining byte-wise and bit-wise models. The models for $ {\mathrm{E}}_{0} $ and $ {\mathrm{E}}_{1} $ are based on bytes-wise and extend these two parts in forward and backward directions into the middle part $ {\mathrm{E}}_{\mathrm{m}} $, which is based on bit-wise. To efficiently model the 8-bit S-box in the layer $ {\mathrm{E}}_{\mathrm{m}} $, we propose a new approach based on affine subspace dimension reduction. This model ensures that the two truncated differential trails are compatible and covers as many rounds as possible with high probability. It allows us to introduce a new 8-round truncated boomerang distinguisher that performs better than earlier distinguishers of HALFLOOP-48. Based on the 8-round truncated boomerang distinguisher, we launch the key-recovery attack successfully with probability 63%. The results show that (1) The proposed ADR method provides a new perspective to efficiently apply large S-box to lightweight ciphers. (2) The constructure of the truncated boomerang distinguisher could be applied to other AES-like lightweight block cipher. (3) HALFLOOP-48 has not enough security margin to be applied on the U.S. military standard.
- Lightweight block cipher,
- Related-tweak attack,
- Truncated sandwich distinguisher,
- Boolean Satisfiability Problem (SAT),
- Key recovery attack

FullText(HTML)

References(19)

References

[1]	Department of Defense. MILSTD-188-141D Interoperability and performance standardsfor medium and high frequencyradio systems[S]. Washington: Department of Defense, 2017. (查阅网上资料, 未找到本条文献出版地, 请确认).
[2]	DANSARIE M, DERBEZ P, LEANDER G, et al. Breaking HALFLOOP-24[J]. IACR Transactions on Symmetric Cryptology, 2022, 2022(3): 217–238. doi: 10.46586/tosc.v2022.I3.217-238.
[3]	LEANDER G, RASOOLZADEH S, and STENNES L. Cryptanalysis of HALFLOOP block ciphers: Destroying HALFLOOP-24[J]. IACR Transactions on Symmetric Cryptology, 2023, 2023(4): 58–82. doi: 10.46586/tosc.v2023.I4.58-82.
[4]	LIN Yunxue and SUN Ling. Related-tweak and related-key differential attacks on HALFLOOP-48[C]. Proceedings of the 22nd International Conference on Applied Cryptography and Network Security, Abu Dhabi, United Arab Emirates, 2024: 355–377. doi: 10.1007/978-3-031-54776-8_14.
[5]	WAGNER D A. The boomerang attack[C]. Proceedings of the 6th International Workshop on Fast Software Encryption, Rome, Italy, 1999: 156–170. doi: 10.1007/3-540-48519-8_12.
[6]	MURPHY S. The return of the cryptographic boomerang[J]. IEEE Transactions on Information Theory, 2011, 57(4): 2517–2521. doi: 10.1109/TIT.2011.2111091.
[7]	DUNKELMAN O, KELLER N, and SHAMIR A. A practical-time related-key attack on the KASUMI cryptosystem used in GSM and 3G telephony[C]. Proceedings of the 30th Annual Cryptology Conference on Advances in Cryptology, Santa Barbara, USA, 2010: 393–410. doi: 10.1007/978-3-642-14623-7_21.
[8]	BIRYUKOV A and KHOVRATOVICH D. Related-key cryptanalysis of the full AES-192 and AES-256[C]. Proceedings of the 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, 2009: 1–18. doi: 10.1007/978-3-642-10366-7_1.
[9]	谭林, 曾新皓, 刘加美. AES-192的相关密钥飞去来器攻击和矩形攻击[J]. 密码学报(中英文), 2024, 11(5): 1018–1028. doi: 10.13868/j.cnki.jcr.000723. TAN Lin, ZENG Xinhao, and LIU Jiamei. Related-key boomerang and rectangle attacks on AES-192[J]. Journal of Cryptologic Research, 2024, 11(5): 1018–1028. doi: 10.13868/j.cnki.jcr.000723.
[10]	BOURA C and COGGIA D. Efficient MILP modelings for Sboxes and linear layers of SPN ciphers[J]. IACR Transactions on Symmetric Cryptology, 2020, 2020(3): 327–361. doi: 10.13154/tosc.v2020.i3.327-361.
[11]	ANKELE R and KÖLBL S. Mind the gap - a closer look at the security of block ciphers against differential cryptanalysis[C]. Proceedings of the 25th International Conference on Selected Areas in Cryptography, Calgary, Canada, 2018: 163–190. doi: 10.1007/978-3-030-10970-7_8.
[12]	MA Sudong, JIN Chenhui, SHI Zhen, et al. Correlation attacks on snow-v-like stream ciphers based on a heuristic MILP model[J]. IEEE Transactions on Information Theory, 2024, 70(6): 4478–4491. doi: 10.1109/TIT.2023.3326348.
[13]	DAEMEN J and RIJMEN V. The Design of Rijndael: AES - The Advanced Encryption Standard[M]. Berlin, Heidelberg: Springer, 2002. doi: 10.1007/978-3-662-04722-4. .
[14]	CID C, HUANG T, PEYRIN T, et al. Boomerang connectivity table: A new cryptanalysis tool[C]. Proceedings of the 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, 2018: 683–714. doi: 10.1007/978-3-319-78375-8_22.
[15]	蒋梓龙, 金晨辉. 对TweAES的相关调柄多重不可能差分攻击[J]. 电子与信息学报, 2023, 45(1): 344–352. doi: 10.11999/JEIT211147. JIANG Zilong and JIN Chenhui. Related-tweak multiple impossible differential attack for TweAES[J]. Journal of Electronics & Information Technology, 2023, 45(1): 344–352. doi: 10.11999/JEIT211147.
[16]	张丽, 吴文玲, 张蕾, 等. 基于交换等价的缩减轮AES-128的密钥恢复攻击[J]. 计算机研究与发展, 2021, 58(10): 2213–2221. doi: 10.7544/issn1000-1239.2021.20210549. ZHANG Li, WU Wenling, ZHANG Lei, et al. Key-recovery attack on reduced-round AES-128 using the exchange-equivalence[J]. Journal of Computer Research and Development, 2021, 58(10): 2213–2221. doi: 10.7544/issn1000-1239.2021.20210549.
[17]	SONG Ling, ZHANG Nana, YANG Qianqian, et al. Optimizing rectangle attacks: A unified and generic framework for key recovery[C]. Proceedings of the 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, China, 2022: 410–440. doi: 10.1007/978-3-031-22963-3_14.
[18]	BLONDEAU C, GÉRARD B, and TILLICH J P. Accurate estimates of the data complexity and success probability for various cryptanalyses[J]. Design Codes Cryptography, 2011, 59(1/3): 3–34. doi: 10.1007/S10623-010-9452-2.
[19]	严智广, 韦永壮, 叶涛. 全轮超轻量级分组密码PFP的相关密钥差分分析[J]. 电子与信息学报, 2025, 47(3): 729–738. doi: 10.11999/JEIT240782. YAN Zhiguang, WEI Yongzhuang, and YE Tao. Related-key differential cryptanalysis of full-round PFP ultra-lightweight block cipher[J]. Journal of Electronics & Information Technology, 2025, 47(3): 729–738. doi: 10.11999/JEIT240782.