自动化搜索ARX密码差分特征的方法
2016-10-13刘正斌
刘正斌
自动化搜索ARX密码差分特征的方法
刘正斌1,2
(1. 中国科学院信息工程研究所信息安全国家重点实验室,北京 100093;2. 中国科学院大学,北京 100049)
要解决ARX密码算法差分特征的自动化搜索问题,关键是要解决搜索过程中模加差分的快速计算。首先,提出了相关差分分布表的概念,通过查找相关差分分布表,可以有效地计算模加的差分以及差分概率;其次,利用相关差分分布表,将Matsui算法扩展到ARX密码,提出了自动化搜索ARX密码差分特征的算法;最后,利用提出的搜索算法,搜索SPECK算法的差分特征,得到了SPECK32、SPECK48和SPECK64的最优差分特征。
分组密码;ARX;差分特征;自动化搜索;SPECK
1 引言
许多分组密码算法采用ARX结构——模加(addition)、循环移位(rotation)、异或(XOR),这些密码算法称为ARX密码算法。这种设计的优点在于算法设计简单、执行效率高,并且非常适于软硬件实现。到目前为止,已经提出了许多ARX密码算法,比较著名的算法有分组密码FEAL[1]、TEAXTEA[2]、RC5[3]、HIGHT[4]和SPECK[5];序列密码Salsa20[6];散列函数MD4MD5[7]、SHA-1以及SHA-3中的Skein[8]和Blake[9]等。
差分分析[10]是分组密码中最有效的分析方法,对于现代分组密码的设计,抵抗差分分析是一个基本的设计准则。对于基于S盒的分组密码,目前,已经存在多种自动化搜索差分特征的算法,利用这些算法可以评估分组密码抵抗差分分析的安全性[11~18]。由于基于S盒的分组密码通常使用8 bit或者4 bit的S盒,可以很容易构造S盒的差分分布表。而对于ARX密码算法,由于模加是其唯一的非线性部件,要构造bit模加的差分分布表,需要23n×4 B的存储空间。由于ARX密码通常使用32 bit的模加作为非线性部件,要构造其差分分布表是不现实的。……
