改进的全轮HALFLOOP-48相关调柄攻击

孙晓萌; 张文英; 苑兆忠

doi:10.11999/JEIT251014

改进的全轮HALFLOOP-48相关调柄攻击

doi: 10.11999/JEIT251014 cstr: 32379.14.JEIT251014

山东师范大学信息科学与工程学院济南 250358

基金项目: 国家自然科学基金(62272282)

详细信息

作者简介:
孙晓萌：女，博士生，研究方向为分组密码算法的安全性分析

张文英：女，教授，博士生导师，研究方向为哈希函数、分组密码算法设计与分析、口令安全

苑兆忠：男，副教授，研究方向为信息安全

通讯作者:
张文英　zhangwenying@sdnu.edu.cn

中图分类号: TN918; TP309
计量
- 文章访问数: 99
- HTML全文浏览量: 47
- PDF下载量: 3
- 被引次数: 0
出版历程
- 收稿日期: 2025-09-26
- 修回日期: 2026-01-08
- 录用日期: 2026-01-12
- 网络出版日期: 2026-01-27

Improved Related-tweak Attack on Full-round HALFLOOP-48

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

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

摘要

摘要: HALFLOOP是一类基于调柄机制、结构类似AES的轻量级分组密码，用于保护第4代高频无线电系统中的自动链路消息。由于其行移位与列混合操作具有使差分快速扩散的特点，寻找具有实际可行性的长轮数、高概率的差分区分器，并实现对完整轮HALFLOOP-48的有效攻击仍是亟待解决的关键问题。为此，该文提出一个新的截断差分三明治区分器框架，并基于布尔可满足性(SAT)方法实现自动化搜索最优差分区分器。该框架将密码分为3个子密码层， $ {{E}}_{0} $和$ {{E}}_{1} $使用字节级模型，$ {{E}}_{{m}} $使用比特级模型。为突破大型S盒差分特征建模的瓶颈，该文提出基于仿射子空间的降维方法，将高维向量的差分特征分解为两个低维子向量，显著降低了SAT的约束规模。其次，为提高区分器概率，将$ {{E}}_{0} $与$ {{E}}_{1} $的依赖关系系统地分为3层，逐一计算每层概率并相乘，得到了概率高达$ {2}^{-43.2} $的8轮HALFLOOP-48截断差分三明治区分器，且给出了满足该差分路径的明文对实例。最终，利用该实际差分路径，对完整轮数的HALFLOOP-48算法发起密钥恢复攻击。与已有结果相比，该文结果在时间复杂度上减少了$ {2}^{25.4} $，在内存复杂度上减少了$ {2}^{10} $。结果说明HALFLOOP算法无法抵抗相关调柄下的三明治攻击。
- 轻量级分组密码 /
- 相关调柄攻击 /
- 截断三明治区分器 /
- 布尔可满足性问题 /
- 密钥恢复攻击
Abstract: Objective HALFLOOP is a family of tweakable AES-like lightweight block ciphers used to encrypt automatic link establishment messages in fourth-generation high-frequency radio systems. Because the RotateRows and MixColumns operations diffuse differences rapidly, long differentials with high probability are difficult to construct, which limits attacks on the full cipher. This study examines full HALFLOOP-48 and evaluates its resistance to sandwich attacks in the related-tweak setting, a critical method in lightweight-cipher cryptanalysis. Methods A new truncated sandwich distinguisher framework is proposed to attack full HALFLOOP-48. The cipher is decomposed into three sub-ciphers, $ {{E}}_{0} $, $ {{E}}_{1} $. A model is built by applying an automatic search method based on the Boolean Satisfiability Problem (SAT) to each part: byte-wise models for $ {{E}}_{0} $, $ {{E}}_{1} $ and a bit-wise model for $ {E}_{m} $. For $ {E}_{m} $, a method is proposed to model large S-boxes using SAT, the Affine Subspace Dimensional Reduction method (ADR). ADR converts the modeling of a high-dimensional set into two sub-problems for a low-dimensional set. ADR ensures that the SAT-searched differentials exist and that their probabilities are accurate, while reducing the size of Conjunctive Normal Form (CNF) clauses. It also enables the SAT method to search longer differentials efficiently when large S-boxes appear. To improve probability accuracy in $ {E}_{m} $, dependencies between $ {{E}}_{0} $ and $ {{E}}_{1} $ are evaluated across three layers, and their probabilities are multiplied. Two key-recovery attacks, a sandwich attack and a rectangle-like sandwich attack, are mounted on the distinguisher in the related-tweak scenario. Results and Discussions The SAT-based model reveals a critical weakness in HALFLOOP-48. A practical sandwich distinguisher for the first 8 rounds withprobability $ {2}^{-43.415} $ is identified. An optimal truncated sandwich distinguisher for 8-round HALFLOOP-48 with probability $ {2}^{-43.2} $ is then established by exploiting the clustering effect of the identified differentials. Compared with earlier results, this distinguisher is practical and extends the reach by two rounds. Using the 8-round distinguisher, both a sandwich attack and a rectangle-like sandwich attack are mounted on full-round HALFLOOP-48 under related tweaks. The sandwich attack requires data complexity of $ {2}^{32.8} $, time complexity $ {2}^{92.2} $ and memory complexity $ {2}^{42.8} $. For the 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, these attacks reduce time complexity by $ {2}^{25.4} $ and memory complexity by $ {2}^{10} $. Conclusions To handle the rapid diffusion of differences in HALFLOOP, a new perspective on sandwich attacks based on truncated differentials is developed by combining byte-wise and bit-wise models. The models for $ {{E}}_{0} $ and $ {{E}}_{1} $ are byte-wise and extend these two parts forward and backward into $ {E}_{m} $, which is based on bit-wise. To efficiently model the 8-bit S-box in the layer $ {E}_{m} $, which is bit-wise. To model the 8-bit S-box in Em efficiently, an affine subspace dimensional reduction approach is proposed. This model ensures compatibility between the two truncated differential trails and covers as many rounds as possible with high probability. It supports a new 8-round truncated boomerang distinguisher that outperforms previous distinguishers for HALFLOOP-48. Based on this 8-round truncated boomerang distinguisher, a key-recovery attack is achieved with success probability 63%. The results show that (1) the ADR method offers an efficient way to apply large S-boxes in lightweight ciphers, (2) the truncated boomerang distinguisher construction can be applied to other AES-like lightweight block ciphers, and (3) HALFLOOP-48 does not provide an adequate security margin for use in the U.S. military standard.
- Lightweight block cipher /
- Related-tweak attack /
- Truncated sandwich distinguisher /
- Boolean SATisfiability problem (SAT) /
- Key recovery attack

HTML全文

图 1 HALFLOOP-48的轮函数

下载: 全尺寸图片幻灯片

图 2 截断三明治区分器

下载: 全尺寸图片幻灯片

图 3 活跃字节$ {S}_{2,2} $在RR下产生的两条差分特征

下载: 全尺寸图片幻灯片

图 4 $ {E}_{m} $的3轮最优截断差分

下载: 全尺寸图片幻灯片

图 5 对完整轮数HALFLOOP-48算法的密钥恢复攻击

下载: 全尺寸图片幻灯片

表 1 HALFLOOP-48算法分析结果

攻击场景	攻击轮数	时间复杂度	数据复杂度	存储复杂度	文献
DS中间相遇攻击	10	2¹²²	13	2⁵⁷B	[3]
相关调柄攻击	8	2^92.71	2^33.27	2^36.385B	[4]
相关调柄三明治攻击	10	2^96.2	2^32.8	2^42.8B	第5节
相关调柄矩形攻击	10	2^99.2	2^16.2	2^26.2B	第5节

下载: 导出CSV

表 2 轮密钥差分特征

轮密钥	差分特征
$ \Delta {\text{rk}}_{1} $	$ {0}^{16}\parallel \delta \parallel {0}^{24} $
$ \Delta {\text{rk}}_{2} $	0
$ \Delta {\text{rk}}_{3} $	0
$ \Delta {\text{rk}}_{4} $	$ \delta \parallel {0}^{24}\parallel \delta \parallel {0}^{8} $
$ \Delta {\text{rk}}_{5} $	$ {0}^{16}\parallel \delta \parallel {0}^{24} $
$ \Delta {\text{rk}}_{6} $	$ \delta \parallel {0}^{16}\parallel S\left(\delta \right)\parallel \delta \parallel {0}^{8} $
$ \Delta {\text{rk}}_{7} $	$ {0}^{8}\parallel S\left(\delta \right){\parallel 0}^{24}\parallel S\left(\delta \right) $
$ \Delta {\text{rk}}_{8} $	$ \delta \parallel {0}^{16}\parallel S\left(\delta \right)\parallel {0}^{16} $
$ \Delta {\text{rk}}_{9} $	$ S\left(S\left(\delta \right)\right)\parallel S\left(\delta \right)\parallel \delta \parallel {0}^{8}\parallel \delta \parallel {0}^{8} $
$ \Delta {\text{rk}}_{10} $	$ \delta \parallel {0}^{8}\parallel S\left(\delta \right)\parallel S\left(\delta \right){\parallel 0}^{16} $
$ \Delta {\text{rk}}_{11} $	$ S(\delta )\parallel {0}^{24}\parallel S\left(\left(\delta \right)\right)\parallel S\left(\delta \right) $

下载: 导出CSV

表 3 HALFLOOP的8轮区分器

轮数	$ \Delta \text{rk} $	$ \Delta x $	$ \Delta y $	$ \Delta w $	$ r $	轮数	$ \nabla \text{rk} $	$ \nabla x $	$ \nabla y $	$ \nabla w $	r
上差分特征						下差分特征
$ {R}_{1} $	00 00 00 00 b0 00	00 00 00 00 b0 00	00 00 00 00 00 00	00 00 00 00 b0 00	$ 1 $	$ {R}_{5} $	00 00 00 00 b0 00	98 91 00 ca 6c 60	25 5b 00 17 33 ab	fc ee 00 3d 00 00	$ {2}^{-11.415}\dagger $
$ {R}_{2} $	00 00 00 00 00 00	00 00 00 00 00 00	00 00 00 00 00 00	00 00 00 00 00 00	$ 1 $	$ {R}_{6} $	b0 01 00 b0 00 00	4c 76 00 8d 00 00	4a 5b 00 3e 00 00	d9 57 db 27 00 00	$ {2}^{-18}\dagger $
$ {R}_{3} $	00 00 00 00 00 00	00 00 00 00 00 00	00 00 00 00 00 00	00 00 00 00 00 00	$ 1 $	$ {R}_{7} $	00 00 db 00 00 db	d9 57 00 27 00 db	56 38 00 af 00 da	b0 a0 00 00 00 00	$ {2}^{-5.415}\dagger $
$ {R}_{4} $	b0 00 00 b0 00 00	b0 00 00 b0 00 00	84 00 00 84 00 00	89 00 6c 00 b0 00	$ {\left({2}^{-2}\right)}^{2} $	$ {R}_{8} $	b0 a0 00 00 00 00	00 00 00 00 00 00	00 00 00 00 00 00	00 00 00 00 00 00	$ 1 $
$ {R}_{5} $	00 00 00 00 b0 00	89 00 6c 00 00 00	c4 00 33 00 00 00	b0 01 38 b0 a4 06	$ {2}^{-11.415}\dagger $	$ {R}_{9} $	c9 00 a0 b0 b0 00	c9 00 a0 b0 b0 00
$ {R}_{6} $	b0 01 00 b0 00 00	00 00 38 00 a4 06	00 00 64 00 2a 0c	a0 00 aa 00 30 00	$ {2}^{-18}\dagger $
$ {R}_{7} $	00 00 31 00 00 31	a0 00 9b 00 30 31	83 00 77 00 67 a4	4e 53 98 a4 1f f3	$ {2}^{-5.415}\dagger $

下载: 导出CSV

参考文献(19)

[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]. 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]. 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]. 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]. 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]	CID C, HUANG T, PEYRIN T, et al. Boomerang connectivity table: A new cryptanalysis tool[C].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.
[11]	SONG Ling, ZHANG Nana, YANG Qianqian, et al. Optimizing rectangle attacks: A unified and generic framework for key recovery[C]. 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.
[12]	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.
[13]	ANKELE R and KÖLBL S. Mind the gap - a closer look at the security of block ciphers against differential cryptanalysis[C]. The 25th International Conference on Selected Areas in Cryptography, Calgary, Canada, 2018: 163–190. doi: 10.1007/978-3-030-10970-7_8.
[14]	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.
[15]	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.
[16]	蒋梓龙, 金晨辉. 对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.
[17]	张丽, 吴文玲, 张蕾, 等. 基于交换等价的缩减轮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.
[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.