自动化搜索ARX分组密码不可能差分与零相关线性闭包

doi:10.11959/j.issn.2096-109x.2017.00175

网络与信息安全学报 ›› 2017, Vol. 3 ›› Issue (7): 58-63.doi: 10.11959/j.issn.2096-109x.2017.00175

自动化搜索ARX分组密码不可能差分与零相关线性闭包

韩亚^1,²

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

修回日期:2017-06-15 出版日期:2017-07-01 发布日期:2017-08-01
作者简介:韩亚（1989-），男，河南商丘人，中国科学院信息工程研究所博士生，主要研究方向为密码学。
基金资助:
国家自然科学基金资助项目(61379142);国家重点基础研究发展计划（“973”计划）基金资助项目(2013CB834203)

Automatic method for searching impossible differentials and zero-correlation linear hulls of ARX block ciphers

Ya HAN^1,²

¹ The State Key Lab of Information Security,Institute of Information Engineering,Chinese Academy of Science,Beijing 100093,China
² University of Chinese Academy of Sciences,Beijing 100049,China

Revised:2017-06-15 Online:2017-07-01 Published:2017-08-01

摘要/Abstract

摘要：

首先，构造了ARX分组密码差分特征及线性掩码的传播方程；然后，利用SAT求解器求解传播方程并且判定该传播系统是否为有效传播；最后，遍历差分特征及线性掩码自动化搜索不可能差分及零相关线性闭包。利用该算法搜索TEA、XTEA和SIMON的不可能差分与零相关线性闭包，并得到TEA、XTEA及SIMON 族分组密码的最优不可能差分与零相关线性闭包。此外，利用差分以及线性分布表，该算法能有效搜索基于S盒分组密码的不可能差分及零相关线性闭包。

关键词: 不可能差分, 零相关线性, ARX结构, SAT求解器

Abstract:

Firstly,the differences and linear masks propagation equations of ARX ciphers were established.Secondly,the propagation equations were solved by SAT solver and judged valid or not.Finally,differences and linear masks were traversed to search impossible differentials and zero-correlation linear hulls automatically.The proposed algorithm was applied to TEA,XTEA and SIMON family block ciphers.The optimal impossible differentials and zero-correlation linear hulls for TEA,XTEA and SIMON family block ciphers were proposed.Moreover，with DDT and LAT,the algorithm can also be applied to search the impossible differentials and zero-correlation linear hulls of S-box based block ciphers.

Key words: impossible differential, zero-correlation linear hull, ARX structure, SAT solver

中图分类号:

TP309

韩亚. 自动化搜索ARX分组密码不可能差分与零相关线性闭包[J]. 网络与信息安全学报, 2017, 3(7): 58-63.

Ya HAN. Automatic method for searching impossible differentials and zero-correlation linear hulls of ARX block ciphers[J]. Chinese Journal of Network and Information Security, 2017, 3(7): 58-63.

图/表 5

表1

图1

表2

图2

表3

参考文献 20

[1]	KNUDSEN L R . Deal - a 128 bit block cipher[J]. Complexity, 2004.
[2]	BIHAM E , BIRYUKOV A , SHAMIR A . Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials[C]// Advances in Cryptology — EUROCRYPT ’99. 1999: 12-23.
[3]	BIHAM E , BIRYUKOV A , SHAMIR A . Miss in the middle attacks on IDEA and Khufu[C]// The International Workshop on FAST Software Encryption. 1999: 124-138.
[4]	PHAN C W . Impossible differential cryptanalysis of 7-round advanced encryption standard(AES)[J]. Information Processing Letters, 2004,91(1): 33-38.
[5]	LU J , DUNKELMAN O , KELLER N ,et al. New impossible differential attacks on AES[C]// Progress in Cryptology-INDOCRYPT. 2008: 279-293.
[6]	BOURA C , NAYA-PLASENCIA M , SUDER V . Scrutinizing and improving impossible differential attacks:applications to CLEFIA,camellia,lblock and simon[C]// The International Conference on the Theory and Application of Cryptology and Information Security. 2014: 179-199.
[7]	CHEN J , FUTA Y , MIYAJI A ,et al. Improving impossible differential cryptanalysis with concrete investigation of key scheduling algorithm and its application to lblock[C]// The 8th International Conference on Network and System Security. 2014: 184-197.
[8]	BOGDANOV A , RIJMEN V . Linear hulls with correlation zero and linear cryptanalysis of block ciphers[J]. Designs Codes ＆Cryptography, 2014,70(3): 369-383.
[9]	YI W T , CHEN S Z . Improved integral and zero-correlation linear cryptanalysis of reduced-round CLEFIA block cipher[J]. IACR Cryptology ePrint Archive, 2016: 149.
[10]	SOLEIMANY H , NYBERG K . Zero-correlation linear cryptanalysis of reduced-round LBlock[J]. Designs Codes ＆Cryptography, 2014,73(2): 683-698.
[11]	XU H , JIA P , HUANG G ,et al. Multidimensional zero-correlation linear cryptanalysis on 23-round LBlock-s[M]// Information and Communications Security. Berlin: SpringerPress, 2015.
[12]	ZHANG K , GUAN J , HU B ,et al. Security evaluation on simeck against zero correlation linear cryptanalysis[J]. IACR Cryptology ePrint Archive, 2015.
[13]	KIM J , HONG S , SUNG J ,et al. Impossible differential cryptanalysis for block cipher structures[C]// The 4th International Conference on Cryptology. 2003: 82-96.
[14]	LUO Y , LAI X , WU Z ,et al. A unified method for finding impossible differentials of block cipher structures[J]. Information Sciences, 2014,263(1): 211-220.
[15]	WU S , WANG M . Automatic search of truncated impossible differentials for word-oriented block ciphers[C]// The International Conference on Cryptology. 2012: 283-302.
[16]	LIPMAA H , MORIAI S . Efficient algorithms for computing differential properties of addition[C]// The 8th International Workshop on Fast Software Encryption. 2001: 336-350.
[17]	WALLéN J , . Linear approximations of addition modulo 2n[C]// The 10th International Workshop on Fast Software Encryption(2003). 2003: 261-273.
[18]	K?LBL S , LEANDER G , TIESSEN T . Observations on the SIMON block cipher family[C]// Advances in Cryptology - CRYPTO. 2015: 161-185.
[19]	WHEELER D J , NEEDHAM R M . Tea,a tiny encryption algo-rithm[M]// Fast Software Encryption. Berlin : SpringerPress, 1994: 363-366.
[20]	BEAULIEU R , SHORS D , SMITH J ,et al. The simon and speck families of lightweight block ciphers[J]. IACR Cryptology ePrint Archive, 2013(6): 404.

分组密码	不可能差分				零相关线性闭包
分组密码	轮数	搜索空间	条数	耗时/min	轮数	搜索空间	条数	耗时/min
TEA	15	2¹²	2	7.45	15	2¹²	2	3.39
XTEA	15	2¹²	2	5.91	15	2¹²	2	0.96

分组密码	不可能差分				零相关线性闭包
分组密码	轮数	搜索空间	条数	耗时/min	轮数	搜索空间	条数	耗时/min
SIMON32	11	2¹⁰	32	0.72	11	2¹⁰	32	0.45
SIMON48	12	2^11.2	48	2.23	12	2^11.2	48	1.27
SIMON64	13	2¹²	192	5.41	13	2¹²	192	2.62
SIMON96	16	2^13.2	192	15.72	16	2^13.2	192	8.72
SIMON128	19	2¹⁴	256	42.16	19	2¹⁴	256	23.36

自动化搜索ARX分组密码不可能差分与零相关线性闭包

Automatic method for searching impossible differentials and zero-correlation linear hulls of ARX block ciphers

在线阅读

pdf下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 20

相关文章 1

Metrics

推荐阅读 0

分组密码	最优不可能差分	最优零相关线性闭包
TEA	15	15
XTEA	15	15
SIMON32	11	11
SIMON48	12	12
SIMON64	13	13
SIMON96	16	16
SIMON128	19	19