基于MILP的轻量级密码算法ACE的差分分析

doi:10.11959/j.issn.1000-436x.2023023

摘要/Abstract

摘要：

研究了轻量级密码算法ACE的差分性质。首先定义了n维环形与门组合，充分分析了该结构中与门之间的相互关系，仅利用O(n)个表达式给出其精确的MILP差分刻画，将ACE算法中的非线性操作转化为32维环形与门组合，从而给出了ACE算法的MILP差分模型。其次根据MILP模型求解器Gurobi的求解特点，给出了快速求解ACE的MILP差分模型的方法。对于3～6步的ACE置换，得到了最优差分链，利用多差分技术给出了更高概率的差分对应，从而给出了 ACE 置换为 3 步的认证加密算法 ACE- $A E$ -128 的差分伪造攻击与哈希算法ACE- $H$ -256的差分碰撞攻击，成功概率为2^-90.52，并证明了4步ACE置换达到了128 bit的差分安全边界。实际上，n维环形与门组合的MILP差分刻画具有更多的应用场景，可应用于SIMON、Simeck等密码算法的分析中。

关键词: 轻量级密码算法, 混合整数线性规划, 环形与门组合, 差分分析

Abstract:

The differential property of the lightweight cipher algorithm ACE was researched.n-dimension ring AND-gate combination was defined and its differential property was described accurately by only O(n) expressions with the MILP method by analyzing the relationship among AND gates.The nonlinear operation of ACE was transformed to the 32-dimension ring AND-gate combination and the MILP differential model of ACE was proposed.According to the characteristics of Gurobi solver, a model for fast solving the MILP differential model of ACE was given.For ACE permutation with 3 to 6 steps, the optimal differential characteristic was obtained and its probability was improved by multi-difference technique.The differential forge attack on authenticated encryption algorithm ACE- $A E$ -128 and the differential collision attack on hash algorithm ACE- $H$ -256 was given with 3-step ACE permutation, and the success probability was 2^-90.52.And it was proved that the 4-steps ACE permutation arrived the differential security bound of 128 bit.Actually, the MILP differential description of ring AND-gate combination can be applied on more cipher algorithms, such as SIMON, Simeck.

Key words: lightweight cipher algorithm, MILP, ring AND-gate combination, differential analysis

中图分类号:

TN918.1

刘帅, 关杰, 胡斌, 马宿东. 基于MILP的轻量级密码算法ACE的差分分析[J]. 通信学报, 2023, 44(1): 39-48.

Shuai LIU, Jie GUAN, Bin HU, Sudong MA. Differential analysis of lightweight cipher algorithm ACE based on MILP[J]. Journal on Communications, 2023, 44(1): 39-48.

图/表 11

图1

图2

图3

图4

图5

表1

表2

表3

表4

表5

表6

参考文献 31

[1]	POSCHMANN A Y . Lightweight cryptography:cryptographic engineering for a pervasive world[M]. Bochum: Ruhr-University Bochum, 2009.
[2]	YANG G Q , ZHU B , SUDER V ,et al. The simeck family of lightweight block ciphers[C]// 2015 Cryptographic Hardware and Embedded Systems. Berlin:Springer, 2015: 307-329.
[3]	BANIK S , PANDEY S K , PEYRIN T ,et al. GIFT:a small present[C]// 2017 Cryptographic Hardware and Embedded Systems. Berlin:Springer, 2017: 321-345.
[4]	BOGDANOV A , KNUDSEN L R , LEANDER G ,et al. PRESENT:an ultra-lightweight block cipher[C]// 2007 Cryptographic Hardware and Embedded Systems. Berlin:Springer, 2007: 450-466.
[5]	SUZAKI T , MINEMATSU K , MORIOKA S ,et al. TWINE:a lightweight block cipher for multiple platforms[C]// 2012 Selected Areas in Cryptograph. Berlin:Springer, 2012: 339-354.
[6]	李玮, 汪梦林, 谷大武 ,等. 轻量级密码算法TWINE的唯密文故障分析[J]. 通信学报, 2021,42(3): 135-149.
	LI W , WANG M L , GU D W ,et al. Ciphertext-only fault analysis of the TWINE lightweight cryptogram algorithm[J]. Journal on Communications, 2021,42(3): 135-149.
[7]	LIU S , GUAN J , HU B . Fault attacks on authenticated encryption modes for GIFT[J]. IET Information Security, 2022,16(1): 51-63.
[8]	陈平, 廖福成, 卫宏儒 . 对轻量级密码算法 MIBS 的相关密钥不可能差分攻击[J]. 通信学报, 2014,35(2): 190-193,201.
	CHEN P , LIAO F C , WEI H R . Related-key impossible differential attack on a lightweight block cipher MIBS[J]. Journal on Communications, 2014,35(2): 190-193,201.
[9]	LAWRENCE B . Submission requirements and evaluation criteria for the lightweight cryptography standardization process[M]. Gaithersburg: Submission to NIST-LWC, 2019.
[10]	吴文玲 . 认证加密算法研究进展[J]. 密码学报, 2018,5(1): 70-82.
	WU W L . Research advances on authenticated encryption algorithms[J]. Journal of Cryptologic Research, 2018,5(1): 70-82.
[11]	MATSUI M , . On correlation between the order of S-boxes and the strength of DES[C]// Advances in Cryptology — EUROCRYPT’94. Berlin:Springer, 1994: 366-375.
[12]	WANG S P , HU B , GUAN J ,et al. MILP-aided method of searching division property using three subsets and applications[C]// Advances in Cryptology — ASIACRYPT 2019. Berlin:Springer, 2019: 398-427.
[13]	K?LBL S , LEANDER G , TIESSEN T . Observations on the SIMON block cipher family[C]// Advances in Cryptology — CRYPTO 2015. Berlin:Springer, 2015: 161-185.
[14]	SONG L , HUANG Z J , YANG Q Q . Automatic differential analysis of ARX block ciphers with application to SPECK and LEA[C]// 2016 Information Security and Privacy — 21st Australasian Conference. Berlin:Springer, 2016: 379-394.
[15]	SUN S W , GERAULT D , LAFOURCADE P ,et al. Analysis of AES,SKINNY,and others with constraint programming[J]. IACR Transactions on Symmetric Cryptology, 2017(1): 281-306.
[16]	SUN S W , HU L , WANG P ,et al. Automatic security evaluation and (related-key) differential characteristic search:application to SIMON,PRESENT,LBlock,DES(L) and other bit-oriented block ciphers[C]// Advances in Cryptology — ASIACRYPT 2014. Berlin:Springer, 2014: 158-178.
[17]	SHI D P , SUN S W , DERBEZ P ,et al. Programming the Demirci-Selcuk meet-in-the-middle attack with constraints[C]// Advances in Cryptology — ASIACRYPT 2018. Berlin:Springer, 2018: 3-34.
[18]	HU K , SUN S W , TODO Y ,et al. Massive superpoly recovery with nested monomial predictions[C]// Advances in Cryptology — ASIACRYPT 2021. Berlin:Springer, 2021: 392-421.
[19]	SASAKI Y , TODO Y . New algorithm for modeling S-box in MILP based differential and division trail search[C]// Innovative Security Solutions for Information Technology and Communications. Berlin:Springer, 2017: 150-165.
[20]	FU K , WANG M Q , GUO Y H ,et al. MILP-based automatic search algorithms for differential and linear trails for speck[C]// Fast Software Encryption. Berlin:Springer, 2016: 268-288.
[21]	SAHA D , SASAKI Y , SHI D P ,et al. On the security margin of TinyJAMBU with refined differential and linear cryptanalysis[J]. IACR Transactions on Symmetric Cryptology, 2020,2020(3): 152-174.
[22]	ZHOU C N , ZHANG W T , DING T Y ,et al. Improving the MILP-based security evaluation algorithm against differential/linear cryptanalysis using a divide-and-conquer approach[J]. IACR Transactions on Symmetric Cryptology, 2019(4): 438-469.
[23]	刘帅, 关杰, 胡斌 ,等. 基于混合整数线性规划的 MORUS 初始化阶段的差分分析[J]. 电子与信息学报， 2022:doi.10.11999/JEIT220735.
	LIU S , GUAN J , HU B ,et al. Differential analysis of the initialization of MORUS based on mixed-integer linear programming[J]. Journal of Electronics ＆ Information Technology, 2022:doi.10.11999/JEIT220735.
[24]	AAGAARD M , ALTAWY R , GONG G ,et al. ACE:an authenticated encryption and hash algorithm[M]. Gaithersburg: Submission to NIST-LWC, 2019.
[25]	LIU J Y , LIU G Q , QU L J . A new automatic tool searching for impossible differential of NIST candidate ACE[J]. Mathematics, 2020,8(9): 1576-1587.
[26]	叶涛, 韦永壮, 李灵琛 . ACE密码算法的积分分析[J]. 电子与信息学报, 2021,43(4): 908-914.
	YE T , WEI Y Z , LI L C . Integral cryptanalysis of ACE encryption algorithm[J]. Journal of Electronics ＆ Information Technology, 2021,43(4): 908-914.
[27]	CHANG L P , WEI Y C , HE S Y ,et al. Research on forgery attack on authentication encryption algorithm ACE[C]// Proceedings of 2022 IEEE 10th Joint International Information Technology and Artificial Intelligence Conference. Piscataway:IEEE Press, 2022: 1952-1958.
[28]	蒋梓龙, 金晨辉 . Saturnin 算法的不可能差分分析[J]. 通信学报, 2022,43(3): 53-62.
	JIANG Z L , JIN C H . Impossible differential cryptanalysis of Saturnin algorithm[J]. Journal on Communications, 2022,43(3): 53-62.
[29]	DUNKELMAN O , LAMBOOIJ E , GHOSH S . Practical related-key forgery attacks on the full TinyJUMBU-192/256[M]. London: Eprint, 2022.
[30]	ABDELKHALEK A , SASAKI Y , TODO Y ,et al. MILP modeling for (large) S-boxes to optimize probability of differential characteristics[J]. IACR Transactions on Symmetric Cryptology, 2017(4): 99-129.
[31]	ALTAWY R , ROHIT R , HE M ,et al. Sliscp-light:towards hardware optimized sponge-specific cryptographic permutations[J]. ACM Transactions on Embedded Computing Systems, 2018,17(4): 1-26.

?x _i	?x_{i+ 1}	?x_ix_i+1	概率
0	0	0	1
		1	0
0	1	x_i	2^{- 1}
1	0	x_{i+ 1}	2^{- 1}
1	1	x_i⊕x_i+1⊕1	2^{- 1}

?x _i	?x_{i+ 1}	?x_{i+ 2}	式(2)是否成立
0	0	0	是
0	0	1	是
0	1	0	是
0	1	1	是
1	0	0	是
1	0	1	否
1	1	0	是
1	1	1	是

步数	活跃SB-64最小数量	搜索时间/s
3	4	0.13
4	6	1.82
5	6	0.41
6	8	0.92

步数	差分转移概率
3	2^{- 98}
4	2^{- 142}
5	2^{- 142}
6	2^-198

状态	?S ⁰	?S ¹	?S ²	?S ³
A	00000000	00000000	00000001	00000010
	00000000	00000000	00000000	00000000
B	00000000	00000011	00000000	00000000
	00000000	00000000	00000000	00000000
C	00000001	00000000	00000000	00000011
	00000000	00000000	00000000	00000000
D	00000000	00000000	00000001	00000000
	00000000	00000000	00000000	00000000
E	00000000	00000011	00000011	00000000
	00000000	00000000	00000000	00000000