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

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

通信学报 ›› 2018, Vol. 39 ›› Issue (5): 103-110.doi: 10.11959/j.issn.1000-436x.2018081

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

韩亚^1,²,王明生^1,²

¹ 中国科学院信息工程研究所信息安全国家重点实验室，北京 100093
² 中国科学院大学网络空间安全学院，北京 100049

修回日期:2018-04-20 出版日期:2018-05-01 发布日期:2018-06-01
作者简介:韩亚（1989-），男，河南商丘人，中国科学院信息工程研究所博士生，主要研究方向为信息安全、密码学等。|王明生（1967-），男，四川遂宁人，中国科学院信息工程研究所研究员、博士生导师，主要研究方向为轻量密码学、大数据密码和密码相关的困难问题等。
基金资助:
国家自然科学基金资助项目(61772516)

Automatic method for searching integral distinguishers of ARX block ciphers

Ya HAN^1,²,Mingsheng WANG^1,²

¹ State Key Laboratory of Information Security,Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China
² School of Cyber Security,University of Chinese Academy of Sciences,Beijing 100049,China

Revised:2018-04-20 Online:2018-05-01 Published:2018-06-01
Supported by:
The National Natural Science Foundation of China(61772516)

摘要/Abstract

摘要：

首先，基于三子集传播的积分可分性质，分别构造ARX结构分组密码积分的K集和L集传播方程，其中，经过分组密码轮函数异或操作时，L集所有向量影响K集向量传播；然后，利用SAT/SMT求解器，建立ARX结构分组密码积分传播方程；最后，遍历满足一定数据复杂度的积分输入，自动化搜索缩减轮数的 ARX 结构分组密码积分区分器。利用该方法能高效地自动化搜索ARX结构，包括类SIMON簇、HIGHT、SPECK簇和LEA等分组密码算法的积分区分器。

关键词: ARX, 三子集, 积分区分器, SAT/SMT

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

中图分类号:

TP391

韩亚,王明生. ARX结构分组密码积分区分器的自动化搜索[J]. 通信学报, 2018, 39(5): 103-110.

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

图/表 6

表1

常规模加运算K集传播"

输出状态	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}}}}}$

表1

表2

常数模加运算K集传播"

输出状态	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}}}}}$

表2

图1

表3

表4

图2

参考文献 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.

分组密码	轮数	数据量	平衡比特	条数
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

[1]	高阳, 张宏莉. 基于随机游走的社区发现方法综述[J]. 通信学报, 2023, 44(6): 198-210.
[2]	郑金志, 汲如意, 张立波, 赵琛. 基于Transformer解码的端到端场景文本检测与识别算法[J]. 通信学报, 2023, 44(5): 64-78.
[3]	李开菊, 许强, 王豪. 冗余数据去除的联邦学习高效通信方法[J]. 通信学报, 2023, 44(5): 79-93.
[4]	张佳乐, 朱诚诚, 孙小兵, 陈兵. 基于GAN的联邦学习成员推理攻击与防御方法[J]. 通信学报, 2023, 44(5): 193-205.
[5]	胡斌, 谈潇, 王森鹏. 基于分治策略的SAT差分自动化搜索算法及其应用[J]. 通信学报, 2023, 44(4): 137-144.
[6]	董煜, 张友鹏. 基于聚类赋权的冲突证据组合方法[J]. 通信学报, 2023, 44(3): 157-163.
[7]	霍纬纲, 梁锐, 李永华. 基于随机Transformer的多维时间序列异常检测模型[J]. 通信学报, 2023, 44(2): 94-103.
[8]	廖苗, 陆颜, 张锦, 赵于前, 邸拴虎. 基于雾线和颜色衰减先验的图像去雾方法[J]. 通信学报, 2023, 44(1): 211-222.
[9]	王泽宇, 布树辉, 黄伟, 郑远攀, 吴庆岗, 常化文, 张旭. 基于多模态特征的无监督领域自适应多级对抗语义分割网络[J]. 通信学报, 2022, 43(12): 157-171.
[10]	段雪源, 付钰, 王坤, 李彬. 基于简单统计特征的LDoS攻击检测方法[J]. 通信学报, 2022, 43(11): 53-64.
[11]	仲美玉, 吴培良, 窦燕, 刘毅, 孔令富. 基于中文语义-音韵信息的语音识别文本校对模型[J]. 通信学报, 2022, 43(11): 65-79.
[12]	龙建武, 朱江洲. 融合超像素与窗口偏移的多尺度引导滤波[J]. 通信学报, 2022, 43(11): 158-170.
[13]	段雪源, 付钰, 王坤, 刘涛涛, 李彬. 基于多尺度特征的网络流量异常检测方法[J]. 通信学报, 2022, 43(10): 65-76.
[14]	刘威, 陈成, 江锐, 卢涛. 四通道无监督学习图像去雾网络[J]. 通信学报, 2022, 43(10): 210-222.
[15]	袁程胜, 郭强, 付章杰. 基于差分隐私的深度伪造指纹检测模型版权保护算法[J]. 通信学报, 2022, 43(9): 181-193.

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

Automatic method for searching integral distinguishers of ARX block ciphers

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 12

相关文章 15

Metrics

推荐阅读 0