自动化搜索ARX密码差分特征的方法

刘正斌



自动化搜索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的模加作为非线性部件，要构造其差分分布表是不现实的。

Biryukov等[19]提出了部分差分分布表（PDDT, partial difference distribution table）的概念，在部分差分分布表中，仅仅存储差分概率大于特定阈值的差分值。虽然无法构造bit模加（≥16）的差分分布表，但是可以非常有效地构造其部分差分分布表。利用部分差分分布表，Biryukov等首次将Matsui算法[16]扩展到了ARX密码差分特征的搜索，提出了一种阈值搜索算法，并用该算法搜索ARX密码算法TEA/XTEA、SPECK和SIMON的差分特征，得到一些改进的差分特征[19~20]。但是，Biryukov等的算法无法保证得到最优的差分特征。

本文提出了一种通用的自动化搜索ARX密码差分特征的算法，该算法也是基于Matsui的分支定界算法。主要思想是首先将bit模加的计算分块成小比特字，如4 bit字或者8 bit字；然后计算小比特字的部分和；最后再将这些部分和组合起来计算整个bit模加。对于4 bit字或者8 bit字，很容易构造其部分和的真值表。在基于S盒的分组密码中，各个S盒之间是相互独立的，然而，由于进位的影响，部分和的真值表是相互关联的，本文将这种相互关联的真值表称为相关S盒。

类似地，可以构造相关差分分布表（CDDT, correlated difference distribution table），相关差分分布表其实就是这些部分和的差分分布表。通过查找相关差分分布表，可以很容易地计算模加中给定输入差分对应的输出差分以及相应的差分概率。基于CDDT提出了一种自动化搜索ARX密码差分特征的算法。将此算法应用到SPECK算法的3个实例SPECK32、SPECK48和SPECK64中，得到了SPECK32、SPECK48和SPECK64的最优差分特征。由于此算法能够遍历SPECK32和SPECK48的明文差分，所以，能够得到其抗差分分析的可证明的安全界。对于SPECK64，尽管本文没有遍历所有可能的明文差分，但是其结果依然是目前最优的。

2 相关S盒与相关差分分布表

其中，(,)可按如下方式迭代计算：0=0，c+1=(x∧y)(x∧c)(y∧c)，0≤≤−2。

定义2 设,,,',','∈，=,'=''。令,,分别表示,,的异或差分，即=',=',γ='。将比特模加=的差分定义为由输入差分,和输出差分构成的三元组(,)，则比特模加的差分概率定义为

定义3 设,,∈，=。假设,∈，且满足=×，则=x可以分块成个部分和，其中，每一个部分和对应bit的加法。遍历2个bit加数的所有可能取值，可以构造bit部分和的真值表，这样，通过依次查找这些部分和的真值表就可以计算=（由于进位的影响，只能从最低比特对应的真值表开始依次查找），这些部分和的真值表称为相关S盒。

当然，要计算bit模加，没有必要通过查找相关S盒来实现，因为计算机软件可以快速实现模加的计算。但是，要计算bit模加的差分却非常耗时，因为给定2个加数的差分，需要遍历和差分的所有可能取值才能确定所有可能的和差分。对于bit的字，需要遍历2种可能取值，由于密码算法中通常使用32 bit的字，因此，这是无法实现的。下面给出相关差分分布表的定义，利用相关差分分布表可以非常有效地计算模加的差分，因此，利用相关差分分布表可以有效地搜索ARX密码的差分特征，就像基于S盒的密码中搜索差分特征一样。

定义4 设,,∈，=。假设,∈，且满足=×。令,,分别表示,,的异或差分，=()(()())，则的计算可以划分成块，每一块包含bit。对于每一块可以构造相应的差分分布表，由于加法运算中进位的影响，2个相邻的差分分布表是相关联的，这样的差分分布表称为相关差分分布表。

利用相关差分分布表计算模加差分概率的过程如下：设,,,','∈，=，令,,分别表示,,的异或差分，即=',='，则

其中，(,)=(c−1,…,1,0)表示的进位向量，(',')=('−1,…,'1,'0)表示''的进位向量，0=0，'0=0。

令

X=[(+1)−1:]，Y=[(+1)−1:] (4)

'='[(+1)−1:]，'='[(+1)−1:] (5)

Γ=[(+1)−1:] (6)

δ定义为()(''')=Γ，则比特模加的差分概率可以按照全概率公式进行如下计算。

1) 当=1时

(,)=(0) (7)

2) 当=2时

3) 当≥3时

下面给出一个具体实例来说明相关差分分布表的构造，以及利用相关差分分布表计算模加的差分概率。

例1 设,,,,,∈，=，,,分别表示,,的异或差分。令=(1010)2,=(1101)2,=(0101)2，则根据模加差分概率的定义，可以计算出(,)=。

接下来，利用相关差分分布表计算(,)。令表示的进位向量，'表示()()的进位向量，=(3,2,1, 0)，'=('3,'2,'1, 0)。因为,,都是4 bit字，所以，可以构造2个2 bit的相关差分分布表0和1，0和1通过进位比特2和'2相关联。因为2,'2∈2，所以0和1各包含4张表。

记

=(3,2,1,0),1=(3,2),0=(1,0) (10)

=(3,2,1,0),1=(3,2),0=(1,0) (11)

=(3,2,1,0),1=(3,2),0=(1,0) (12)

=(3,2,1,0),1=(3,2),0=(1,0) (13)

=(3,2,1,0),1=(3,2),0=(1,0) (14)

=(3,2,1,0),1=(3,2),0=(1,0) (15)

那么，(0,0,0)就是相关差分分布表0的输入和输出差分，(1,1,1)就是相关差分分布表1的输入和输出差分，在存储过程中将输入差分(0,0)和(1,1) 分别存储成0||0和1||1。相关差分分布表0和1的构造算法如下。

算法1 相关差分分布表0和1的构造算法

1) 构造0，其中，表示模加中的进位标记，用于选择1的表。

for0,0,0=0 to 3 do

for0,0=0 to 3 do

0=00;

'0=(00)(00);

2=;

'2=;

=2||'2;

if0'0=0then

end if

end for

end for

2) 构造1。

for1,1,1=0 to 3 do

for1,1=0 to 3 do

for2,'2=0 to 1 do

1=112;

'1=(11)(11)'2;

=2||'2;

if1'1=1then

end if

end for

end for

end for

1=(3,2)=(11)2，0=(1,0)=(01)2(17)

1=(3,2)=(01)2，0=(1,0)=(01)2(18)

因此，可以计算出

(,→)=(0,00)1,d(1,11)

表1 相关差分分布表CS0

表2 相关差分分布表CS1

3 ARX密码差分特征的自动化搜索算法

在1994年的欧密会上，Matsui提出了一种自动化搜索DES最优差分特征的算法[16]。Matsui算法本质上是一种深度优先的搜索算法，对于轮差分特征，Matsui算法执行一个递归搜索。如果已知轮最优差分特征概率B(0≤≤−1)和轮最优差分特征概率的一个初始估计值，Matsui算法就能给出轮最优差分特征概率B，对轮数进行迭代，就可以得到所有轮数的最优差分特征概率。然而Matsui算法仅仅适用于基于S盒的分组密码，并不能用于搜索ARX密码的差分特征，因为无法直接构造模加的差分分布表。Biryukov等在CT-RSA2014提出了搜索ARX密码差分特征的阈值搜索算法[19]，他们提出部分差分分布表的概念，第一次将Matsui算法扩展到了ARX密码差分特征的搜索。尽管Biryukov等的算法可以用于搜索各种ARX密码的差分特征，但是他们的算法无法保证得到最优的差分特征。

本文提出了相关差分分布表的概念，利用相关差分分布表，同样将Matsui算法扩展到了ARX密码差分特征的搜索。因为本文的算法能够遍历明文差分，所以本文的算法能够给出ARX密码的最优差分特征。下面以Feistel结构为例，给出本文的算法。Feistel结构的一轮如图1所示，其中F表示包含循环移位（rotation）、逻辑移位（shift）、异或运算（XOR）等部件的线性层。

算法2 本文算法

Procedure Round-1:

Begin the program

For each candidate for Δ0, Δ1, Δ1, do the following：

Δ1=(Δ1);

Let1=(Δ0, Δ11);

If1B−1≥, then call Procedure Round-2;

Exit the program

Procedure Round-(2≤≤−1):

For each candidate for ΔZ, do the following：

Let ΔX= ΔZ−1and ΔY=(ΔX);

Letp=(ΔX−1,YZ);

If1∙2∙…∙p∙B−i≥, then call Procedure Round-(+1) ;

Return to the upper procedure.

Procedure Round-:

Let ΔX= ΔZ−1and ΔY=(ΔX);

Letp=maxΔP(ΔX−1,ΔYΔZ);

If1∙2∙…∙p≥, then=1∙2∙…∙p;

Return to the upper procedure

当计算(ΔX−1, ΔYΔZ)时，只需要通过查找相关差分分布表即可，跟基于S盒的密码算法中差分概率的计算类似。对于bit的模加，相关差分分布表的字长可以是整除的任意整数，并且其字长越大，搜索算法执行效率越高。考虑到相关差分分布表的存储，本文在实验过程中采用了8 bit的相关差分分布表。

4 SPECK算法及其差分特征

4.1 SPECK算法描述

SPECK算法是美国国家安全局（NSA, National Security Agency）在2013年提出的一组轻量级分组密码算法[5]，共包含10个算法实例，其分组长度分别为32 bit、48 bit、64 bit、96 bit和128 bit，相应的算法记为SPECK32、SPECK48、SPECK64、SPECK96和SPECK128。

SPECK算法采用了类似Threefish算法的结构，其轮函数仅仅使用了3种简单的运算：模加（addition）、循环移位、异或。令(L−1, R−1)表示第轮的输入，(L,R)表示第轮的输出，第轮的轮密钥记为K，则(L,R)可以通过下式计算

L=((L−1)−1)K，R=(R−1)(20)

其中，当分组长度为32 bit时，=7,=2，对于其他分组长度=8,=3 。SPECK算法的轮函数如图2所示。

4.2 SPECK算法的差分特征

本文利用算法2搜索SPECK32、SPECK48和SPECK64的差分特征，所用的实验平台是Intel Core i5 3.2 GHz，采用VS2010软件平台，得到的结果如下：对于SPECK32，得到的最优差分特征包含9轮，其差分概率为2−30；对于SPECK48，得到的最优差分特征包含11轮，其差分概率为2−45；对于SPECK64，得到的最优差分特征包含15轮，其差分概率为2−62。这些结果跟Fu等[21]在FSE’16上发表的结果相同，但是本文的算法遍历了SPECK32和SPECK48的明文差分，因此能够说明该结果就是SPECK32和SPECK48最好的差分特征，而且本文给出了SPECK32和SPECK48抗差分分析的可证明的安全界。而对于SPECK64，由于受到计算能力的限制，并没有遍历所有可能的明文差分，尽管如此，本文给出的结果依然是目前最优的。SPECK32、SPECK48和SPECK64的最优差分特征的概率如表3所示，其9轮、11轮和15轮的最优差分特征如表4所示。

表3 SPECK32、SPECK48和SPECK64最优差分特征的概率

表4 SPECK32、SPECK48和SPECK64的9轮、11轮和15轮最优差分特征

5 结束语

本文提出了一种自动化搜索ARX密码最优差分特征的算法，该算法是基于Matsui算法，通过引入相关差分分布表，解决了搜索过程中模加差分的快速计算问题，即给定模加的输入差分，通过查找相关差分分布表，可以快速计算出输出差分以及差分概率。

本文以SPECK算法中的3个实例SPECK32、SPECK48和SPECK64为测试平台说明该算法的有效性。使用本文提出的算法搜索SPECK32、SPECK48和SPECK64的差分特征，分别得到了9轮、11轮和15轮的差分特征，其概率分别为2−30、2−45和2−62。这些差分特征是目前能够找到的最好的差分特征，其中，SPECK32和SPECK48的差分特征通过遍历明文差分得到，因此可以给出其抗差分分析的可证明的安全界。

本文提出的算法是一种通用的自动化搜索ARX密码差分特征的算法，尽管仅以SPECK算法作为测试平台，但是此算法可以用于搜索其他ARX密码的差分特征，作者正在研究使用本文算法搜索其他ARX密码的差分特征。

[1] SHIMIZU A, MIYAGUCHI S. Fast data encipherment algorithm FEAL[C]//International Conference on Theory and Application of Cryptographic Techniques.c1987:267-278.

[2] WHEELER D J, NEEDHAM R M. Tea, a tiny encryption algorithm[M]// Fast Software Encryption. Berlin: Springer, 2015: 363-366.

[3] RIVEST R L.The RC5 encryption algorithm[C]//Fast Software Encryption: Second International Workshop. c1994:14-16.

[4] HONG D, SUNG J, HONG S ,et al. HIGHT: a new block cipher suitable for low-resource device[M]//Cryptographic Hardware and Embedded Systems-CHES 2006. Berlin: Springer, 2006: 46-59.

[5] BEAULIEU R, SHORS D, SMITH J, et al.The SIMON and SPECK families of lightweight block ciphers[R]. IACR Cryptology ePrint Archive，2013.

[6] BERNSTEIN D J. The salsa20 family of stream ciphers[R]. New Stream Cipher Designs - The eSTREAM Finalists ，2008.

[7] RIVEST R L. The MD4 message digest algorithm[C]//CRYPTO. c1990:303-311.

[8] FERGUSON N, LUCKS S, SCHNEIER B, et al.The skein hash function family[R]. Submission to NIST(Round 3), 2010.

[9] AUMASSON J P, HENZEN L, MEIER W, et al. Sha-3 proposal blake[R]. Submission to NIST(Round 3), 2010.

[10] BIHAM E, SHAMIR A. Differential cryptanalysis of des-like cryptosystems[J]. Journal of Cryptology, 1991, 1(4): 3-72.

[11] AOKI K, KOBAYASHI K, MORIAI S. Best differential characteristic search of FEAL[M]//Fast Software Encryption. Berlin ：Springer, 1997:41-53.

[12] BANNIER A, BODIN N, FILIOL E.Automatic search for a maximum probability differential characteristic in a substitution-permutation network[C]//International Conference on System Sciences, IEEE Computer Society. c2015: 5165-5174.

[13] BIRYUKOV A, NIKOLIC I. Automatic search for related-key differential characteristics in byte-oriented block ciphers : application to AES, camellia, khazad and others[C]//International Conference on the Theory and Applications of Cryptographic Techniques. c2010: 322-344.

[14] BIRYUKOV A, NIKOLIC I. Search for related-key differential characteristics in des-like ciphers[C]// International Conference on FAST Software Encryption. c2011:18-34.

[15] BOUILLAGUET C, DERBEZ P , FOUQUE P. Automatic search of attacks on round-reduced AES and applications[R]. IACR Cryptology ePrint Archive, 2012.

[16] MATSUI M. On correlation between the order of s-boxes and the strength of DES [M]// Advances in Cryptology — EUROCRYPT'94. Berlin: Springer, 1994:366-375.

[17] MOUHA N, WANG Q, GU D, et al. Differential and linear cryptanalysis using mixed-integer linear programming[C]//7th International Conference on Information Security and Cryptology. c2011.

[18] 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]//The 20th International Conference on the Theory and Application of Cryptology and Information Security. c2014.

[19] BIRYUKOV A, VELICHKOV V. Automatic search for differential trails in ARX ciphers[M]//Topics in Cryptology – CT-RSA 2014. Berlin: Springer , 2014:227-250.

[20] BIRYUKOV A, ROY A, VELICHKOV V. Differential analysis of block ciphers SIMON and SPECK[M]//Fast Software Encryption. Berlin: Springer Heidelberg, 2014:546-570.

[21] FU K, WANG M Q, GUO Y ,et al. MILP-based automatic search algorithms for differential and linear trails for speck[C]//Fast Software Encryption, 23rd International Workshop. c2016.

Automatic search algorithm for differential characteristics in ARX ciphers

LIU Zheng-bin1,2

(1. The State Key Lab of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China; 2. University of Chinese Academy of Sciences, Beijing 100049, China)

How to compute the differential of modular addition efficiently is critical to automatic search for differential characteristic in ARX ciphers. To solve this problem, firstly, the concept of collerated difference distribution table (CDDT) was proposed. By looking up the CDDT, it was very efficient to compute the differential probability of modular addition. Secondly, extending Matsui’s algorithm to ARX cihpers and using CDDT, an automatic search algorithm was proposed, and the algorithm could give the differential characteristic with highest probability in ARX ciphers. Finally, the proposed algorithm was applied to the ARX cipher SPECK, and got the best differential characteristics for SPECK32, SPECK48 and SPECK64.

block cipher, ARX, differential characteristic, automatic search, SPECK

The National Natural Science Foundation of China (No.61379142), The National Basic Research Program of China (973 Program)(No.2013CB834203)

TP393

A

10.11959/j.issn.2096-109x.2016.00050

2016-03-17；

2016-04-27。

刘正斌，liuzhengbin@iie.ac.cn

国家自然科学基金资助项目（No.61379142）；国家重点基础研究发展计划（“973”计划）基金资助项目（No.2013CB834203）

刘正斌（1985-），男，山东青岛人，中国科学院信息工程研究所博士生，主要研究方向为密码学。