ARX结构分组密码积分区分器的自动化搜索

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

Abstract

Abstract:

Firstly,based on three subsets division property propagation technique,the propagation function of the K-set and L-set of ARX block ciphers was constructed respectively.All vectors in L-set affected the propagation of K-set when propagate through xored round key operation.With SAT/SMT solver,round reduced integral propagation functions of ARX block ciphers could be established.Finally,by exhausting all possible input integral characteristics with proper data complexity,round reduced integral distinguishers of ARX block ciphers could be found.The proposed method can be used for searching integral distinguishers of ARX block ciphers including SIMON-like family block ciphers,HIGHT,SPECK family block ciphers and LEA effectively.

Key words: ARX, three subsets, integral distinguishers, SAT/SMT

CLC Number:

TP391

Ya HAN,Mingsheng WANG. Automatic method for searching integral distinguishers of ARX block ciphers[J]. Journal on Communications, 2018, 39(5): 103-110.

Figures/Tables 6

输出状态	K集传播	进位状态	K集传播
kz_{m? 1}	$\underset{k x_{m - 1}^{}}{\underset{︸}{k x_{m - 1}}} \oplus \underset{k y_{m - 1}^{}}{\underset{︸}{k y_{m - 1}}} \oplus \underset{k c_{m - 1}^{*}}{\underset{︸}{0}}$	$\underset{k c_{m - 1}^{* *}}{\underset{︸}{k c_{m - 1}}}$	$\overset{k u_{0}}{\overset{︷}{\underset{k x_{0}^{* }}{\underset{︸}{0}} \land \underset{k y_{0}^{ }}{\underset{︸}{0}}}} \oplus \overset{k w_{0}}{\overset{︷}{\overset{k v_{0}}{\overset{︷}{(\underset{k x_{0}^{ * }}{\underset{︸}{0}} \land \underset{k y_{0}^{ * }}{\underset{︸}{0}})}} \land \overset{k c_{0}^{ * *}}{\overset{︷}{0}}}}$
kz_{m? 2}	$\underset{k x_{m - 2}^{}}{\underset{︸}{k x_{m - 2}}} \oplus \underset{k y_{m - 2}^{}}{\underset{︸}{k y_{m - 2}}} \oplus \underset{k c_{m - 2}^{*}}{\underset{︸}{k c_{m - 2}}}$	$\underset{k c_{m - 2}^{* *}}{\underset{︸}{k c_{m - 2}}}$	$\overset{k u_{m - 1}}{\overset{︷}{\underset{k x_{m - 1}^{* }}{\underset{︸}{k x_{m - 1}}} \land \underset{k y_{m - 1}^{ }}{\underset{︸}{k y_{m - 1}}}}} \oplus \overset{k w_{m - 1}}{\overset{︷}{\overset{k v_{m - 1}}{\overset{︷}{(\underset{k x_{m - 1}^{ * }}{\underset{︸}{0}} \land \underset{k y_{m - 1}^{ * }}{\underset{︸}{0}})}} \land \overset{k c_{m - 1}^{ * *}}{\overset{︷}{0}}}}$
kz_{m? 3}	$\underset{k x_{m - 3}^{}}{\underset{︸}{k x_{m - 3}}} \oplus \underset{k y_{m - 3}^{}}{\underset{︸}{k y_{m - 3}}} \oplus \underset{k c_{m - 3}^{*}}{\underset{︸}{k c_{m - 3}}}$	$\underset{k c_{m - 3}^{* *}}{\underset{︸}{k c_{m - 3}}}$	$\overset{k u_{m - 2}}{\overset{︷}{\underset{k x_{m - 2}^{* }}{\underset{︸}{k x_{m - 2}}} \land \underset{k y_{m - 2}^{ }}{\underset{︸}{k y_{m - 2}}}}} \oplus \overset{k w_{m - 2}}{\overset{︷}{\overset{k v_{m - 2}}{\overset{︷}{(\underset{k x_{m - 2}^{ * }}{\underset{︸}{k x_{m - 2}}} \land \underset{k y_{m - 2}^{ * }}{\underset{︸}{k y_{m - 2}}})}} \land \overset{k c_{m - 2}^{ * *}}{\overset{︷}{k c_{m - 2}}}}}$
$⋮$	$⋮$	$⋮$	$⋮$
k ₀z	$\underset{k x_{0}^{}}{\underset{︸}{k x_{0}}} \oplus \underset{k y_{0}^{}}{\underset{︸}{k y_{0}}} \oplus \underset{k c_{0}^{*}}{\underset{︸}{k c_{0}}}$	$\underset{k c_{0}^{* *}}{\underset{︸}{k c_{0}}}$	$\overset{k u_{1}}{\overset{︷}{\underset{k x_{1}^{* }}{\underset{︸}{k x_{1}}} \land \underset{k y_{1}^{ }}{\underset{︸}{k y_{1}}}}} \oplus \overset{k w_{1}}{\overset{︷}{\overset{k v_{1}}{\overset{︷}{(\underset{k x_{1}^{ * }}{\underset{︸}{k x_{1}}} \land \underset{k y_{1}^{ * }}{\underset{︸}{k y_{1}}})}} \land \overset{k c_{1}^{ * *}}{\overset{︷}{k c_{1}}}}}$

输出状态	K集传播	进位状态	K集传播
kz_{m? 1}	$\underset{k x_{m - 1}^{}}{\underset{︸}{k x_{m - 1}}} \oplus \underset{k c_{m - 1}^{}}{\underset{︸}{0}}$	$\underset{k c_{m - 1}^{* *}}{\underset{︸}{k c_{m - 1}}}$	$\underset{k x_{0}^{* }}{\underset{︸}{0}} \oplus \overset{k u_{0}}{\overset{︷}{\underset{k x_{0}^{ * }}{\underset{︸}{0}} \land \underset{k c_{0}^{ * *}}{\underset{︸}{0}}}}$
kz_{m? 2}	$\underset{k x_{m - 2}^{}}{\underset{︸}{k x_{m - 2}}} \oplus \underset{k c_{m - 2}^{}}{\underset{︸}{k c_{m - 2}}}$	$\underset{k c_{m - 2}^{* *}}{\underset{︸}{k c_{m - 2}}}$	$\underset{k x_{m - 1}^{* }}{\underset{︸}{k x_{m - 1}}} \oplus \overset{k u_{m - 1}}{\overset{︷}{\underset{k x_{m - 1}^{ * }}{\underset{︸}{0}} \land \underset{k c_{m - 1}^{ * *}}{\underset{︸}{0}}}}$
kz_{m? 3}	$\underset{k x_{m - 3}^{}}{\underset{︸}{k x_{m - 3}}} \oplus \underset{k c_{m - 3}^{}}{\underset{︸}{k c_{m - 3}}}$	$\underset{k c_{m - 3}^{* *}}{\underset{︸}{k c_{m - 3}}}$	$\underset{k x_{m - 2}^{* }}{\underset{︸}{k x_{m - 2}}} \oplus \overset{k u_{m - 2}}{\overset{︷}{\underset{k x_{m - 2}^{ * }}{\underset{︸}{k x_{m - 2}}} \land \underset{k c_{m - 2}^{ * *}}{\underset{︸}{k c_{m - 2}}}}}$
$⋮$	$⋮$	$⋮$	$⋮$
k ₀z	$\underset{k x_{0}^{}}{\underset{︸}{k x_{0}}} \oplus \underset{k c_{0}^{}}{\underset{︸}{k c_{0}}}$	$\underset{k c_{0}^{* *}}{\underset{︸}{k c_{0}}}$	$\underset{k x_{1}^{* }}{\underset{︸}{k x_{1}}} \oplus \overset{k u_{1}}{\overset{︷}{\underset{k x_{1}^{ * }}{\underset{︸}{k x_{1}}} \land \underset{k c_{1}^{ * *}}{\underset{︸}{k c_{1}}}}}$

References 12

[1]	TODO Y , . Structural evaluation by generalized integral property[C]// EUROCRYPT. 2015: 287-314.
[2]	TODO Y , . Integral cryptanalysis on full MISTY1[C]// CRYPTO. 2015: 413-432.
[3]	WANG Q J , LIU Z Q , KEREM V ,et al. Cryptanalysis of reduced-round SIMON32 and SIMON48[C]// INDOCRYPT. 2014: 143-160.
[4]	TODO Y , MORII M . Bit-based division property and application to simon family[C]// Fast Software Encryption. 2016: 357-377.
[5]	ALEX B , ARNAB R , VESSELIN V . Differential analysis of block ciphers SIMON and SPECK[C]// Fast Software Encryption. 2014: 546-570.
[6]	XIANG Z J , ZHANG W T , BAO Z Z ,et al. Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers[C]// ASIACRYPT. 2016: 648-678.
[7]	SUN L , WANG W , LIU R ,et al. Milp-aided bit-based division property for arx-based block cipher[M]. IACR Cryptology ePrint Archive, 2016.
[8]	DEUKIO H , JAECHUL S , SEOKHIE H ,et al. HIGHT:a new block cipher suitablefor low-resource device[C]// Cryptographic Hardware and Embedded Systems. 2006: 46-59.
[9]	DEUKIO H , JUNG K L , DONG C K ,et al. LEA:a 128-bit block cipher for fast encryption on common processors[C]// WISA. 2013: 3-27.
[10]	DAVID J,WHEELER , ROGER M . Tea,a tiny encryption algorithm[C]// Fast Software Encryption. 1994: 363-366.
[11]	YAO J T , LIU W N . The STP model for solving imprecise problems[C]// GrC. 2006: 683-687.
[12]	YANG G Q , ZHU B , VALENTIN S ,et al. The simeck family of lightweight block ciphers[C]// Cryptographic Hardware and Embedded Systems. 2015: 307-329.

Metrics

Recommended 0

No Suggested Reading articles found!

分组密码	轮数	数据量	平衡比特	条数
SIMON32	14	2³¹	3	32
SIMON48	15	2⁴⁷	24	48
SIMON64	17	2⁶³	22	64
SIMON96	21	2⁹⁵	5	96
SIMON128	25	2¹²⁷	3	128

分组密码	轮数	数据量	平衡比特	条数
HIGHT	18	2⁶³	1	4
	18	2⁶³	2	4

[1]	Yang GAO, Hongli ZHANG. Survey on community detection method based on random walk [J]. Journal on Communications, 2023, 44(6): 198-210.
[2]	Jinzhi ZHENG, Ruyi JI, Libo ZHANG, Chen ZHAO. End-to-end scene text detection and recognition algorithm based on Transformer decoders [J]. Journal on Communications, 2023, 44(5): 64-78.
[3]	Kaiju LI, Qiang XU, Hao WANG. Communication-efficient federated learning method via redundant data elimination [J]. Journal on Communications, 2023, 44(5): 79-93.
[4]	Jiale ZHANG, Chengcheng ZHU, Xiaobing SUN, Bing CHEN. Membership inference attack and defense method in federated learning based on GAN [J]. Journal on Communications, 2023, 44(5): 193-205.
[5]	Bin HU, Xiao TAN, Senpeng WANG. SAT-based differential automatic search algorithm using divide-and-conquer strategy and its applications [J]. Journal on Communications, 2023, 44(4): 137-144.
[6]	Yu DONG, Youpeng ZHANG. Conflict evidence combination method based on clustering weighting [J]. Journal on Communications, 2023, 44(3): 157-163.
[7]	Weigang HUO, Rui LIANG, Yonghua LI. Anomaly detection model for multivariate time series based on stochastic Transformer [J]. Journal on Communications, 2023, 44(2): 94-103.
[8]	Miao LIAO, Yan LU, Jin ZHANG, Yuqian ZHAO, Shuanhu DI. Image dehazing method based on haze-line and color attenuation prior [J]. Journal on Communications, 2023, 44(1): 211-222.
[9]	Zeyu WANG, Shuhui BU, Wei HUANG, Yuanpan ZHENG, Qinggang WU, Huawen CHANG, Xu ZHANG. Unsupervised domain adaptation multi-level adversarial network for semantic segmentation based on multi-modal features [J]. Journal on Communications, 2022, 43(12): 157-171.
[10]	Xueyuan DUAN, Yu FU, Kun WANG, Bin LI. LDoS attack detection method based on simple statistical features [J]. Journal on Communications, 2022, 43(11): 53-64.
[11]	Meiyu ZHONG, Peiliang WU, Yan DOU, Yi LIU, Lingfu KONG. Chinese semantic and phonological information-based text proofreading model for speech recognition [J]. Journal on Communications, 2022, 43(11): 65-79.
[12]	Jianwu LONG, Jiangzhou ZHU. Multi-scale guided filtering integrated with superpixel and patch shift [J]. Journal on Communications, 2022, 43(11): 158-170.
[13]	Xueyuan DUAN, Yu FU, Kun WANG, Taotao LIU, Bin LI. Network traffic anomaly detection method based on multi-scale characteristic [J]. Journal on Communications, 2022, 43(10): 65-76.
[14]	Wei LIU, Cheng CHEN, Rui JIANG, Tao LU. Four-path unsupervised learning-based image defogging network [J]. Journal on Communications, 2022, 43(10): 210-222.
[15]	Chengsheng YUAN, Qiang GUO, Zhangjie FU. Copyright protection algorithm based on differential privacy deep fake fingerprint detection model [J]. Journal on Communications, 2022, 43(9): 181-193.

Automatic method for searching integral distinguishers of ARX block ciphers

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 12

Related Articles 15

Metrics

Recommended 0