自動(dòng)化搜索ARX密碼差分特征的方法

劉正斌

?

自動(dòng)化搜索ARX密碼差分特征的方法

劉正斌1,2

（1. 中國(guó)科學(xué)院信息工程研究所信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100093；2. 中國(guó)科學(xué)院大學(xué)，北京 100049）

要解決ARX密碼算法差分特征的自動(dòng)化搜索問(wèn)題，關(guān)鍵是要解決搜索過(guò)程中模加差分的快速計(jì)算。首先，提出了相關(guān)差分分布表的概念，通過(guò)查找相關(guān)差分分布表，可以有效地計(jì)算模加的差分以及差分概率；其次，利用相關(guān)差分分布表，將Matsui算法擴(kuò)展到ARX密碼，提出了自動(dòng)化搜索ARX密碼差分特征的算法；最后，利用提出的搜索算法，搜索SPECK算法的差分特征，得到了SPECK32、SPECK48和SPECK64的最優(yōu)差分特征。

分組密碼；ARX；差分特征；自動(dòng)化搜索；SPECK

1 引言

許多分組密碼算法采用ARX結(jié)構(gòu)——模加（addition）、循環(huán)移位（rotation）、異或（XOR），這些密碼算法稱為ARX密碼算法。這種設(shè)計(jì)的優(yōu)點(diǎn)在于算法設(shè)計(jì)簡(jiǎn)單、執(zhí)行效率高，并且非常適于軟硬件實(shí)現(xiàn)。到目前為止，已經(jīng)提出了許多ARX密碼算法，比較著名的算法有分組密碼FEAL[1]、TEAXTEA[2]、RC5[3]、HIGHT[4]和SPECK[5]；序列密碼Salsa20[6]；散列函數(shù)MD4MD5[7]、SHA-1以及SHA-3中的Skein[8]和Blake[9]等。

差分分析[10]是分組密碼中最有效的分析方法，對(duì)于現(xiàn)代分組密碼的設(shè)計(jì)，抵抗差分分析是一個(gè)基本的設(shè)計(jì)準(zhǔn)則。對(duì)于基于S盒的分組密碼，目前，已經(jīng)存在多種自動(dòng)化搜索差分特征的算法，利用這些算法可以評(píng)估分組密碼抵抗差分分析的安全性[11~18]。由于基于S盒的分組密碼通常使用8 bit或者4 bit的S盒，可以很容易構(gòu)造S盒的差分分布表。而對(duì)于ARX密碼算法，由于模加是其唯一的非線性部件，要構(gòu)造bit模加的差分分布表，需要23n×4 B的存儲(chǔ)空間。由于ARX密碼通常使用32 bit的模加作為非線性部件，要構(gòu)造其差分分布表是不現(xiàn)實(shí)的。

Biryukov等[19]提出了部分差分分布表（PDDT, partial difference distribution table）的概念，在部分差分分布表中，僅僅存儲(chǔ)差分概率大于特定閾值的差分值。雖然無(wú)法構(gòu)造bit模加（≥16）的差分分布表，但是可以非常有效地構(gòu)造其部分差分分布表。利用部分差分分布表，Biryukov等首次將Matsui算法[16]擴(kuò)展到了ARX密碼差分特征的搜索，提出了一種閾值搜索算法，并用該算法搜索ARX密碼算法TEA/XTEA、SPECK和SIMON的差分特征，得到一些改進(jìn)的差分特征[19~20]。但是，Biryukov等的算法無(wú)法保證得到最優(yōu)的差分特征。

本文提出了一種通用的自動(dòng)化搜索ARX密碼差分特征的算法，該算法也是基于Matsui的分支定界算法。主要思想是首先將bit模加的計(jì)算分塊成小比特字，如4 bit字或者8 bit字；然后計(jì)算小比特字的部分和；最后再將這些部分和組合起來(lái)計(jì)算整個(gè)bit模加。對(duì)于4 bit字或者8 bit字，很容易構(gòu)造其部分和的真值表。在基于S盒的分組密碼中，各個(gè)S盒之間是相互獨(dú)立的，然而，由于進(jìn)位的影響，部分和的真值表是相互關(guān)聯(lián)的，本文將這種相互關(guān)聯(lián)的真值表稱為相關(guān)S盒。

類似地，可以構(gòu)造相關(guān)差分分布表（CDDT, correlated difference distribution table），相關(guān)差分分布表其實(shí)就是這些部分和的差分分布表。通過(guò)查找相關(guān)差分分布表，可以很容易地計(jì)算模加中給定輸入差分對(duì)應(yīng)的輸出差分以及相應(yīng)的差分概率?；贑DDT提出了一種自動(dòng)化搜索ARX密碼差分特征的算法。將此算法應(yīng)用到SPECK算法的3個(gè)實(shí)例SPECK32、SPECK48和SPECK64中，得到了SPECK32、SPECK48和SPECK64的最優(yōu)差分特征。由于此算法能夠遍歷SPECK32和SPECK48的明文差分，所以，能夠得到其抗差分分析的可證明的安全界。對(duì)于SPECK64，盡管本文沒(méi)有遍歷所有可能的明文差分，但是其結(jié)果依然是目前最優(yōu)的。

2 相關(guān)S盒與相關(guān)差分分布表

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

定義2 設(shè),,,',','∈，=,'=''。令,,分別表示,,的異或差分，即=',=',γ='。將比特模加=的差分定義為由輸入差分,和輸出差分構(gòu)成的三元組(,)，則比特模加的差分概率定義為

定義3 設(shè),,∈，=。假設(shè),∈，且滿足=×，則=x可以分塊成個(gè)部分和，其中，每一個(gè)部分和對(duì)應(yīng)bit的加法。遍歷2個(gè)bit加數(shù)的所有可能取值，可以構(gòu)造bit部分和的真值表，這樣，通過(guò)依次查找這些部分和的真值表就可以計(jì)算=（由于進(jìn)位的影響，只能從最低比特對(duì)應(yīng)的真值表開(kāi)始依次查找），這些部分和的真值表稱為相關(guān)S盒。

當(dāng)然，要計(jì)算bit模加，沒(méi)有必要通過(guò)查找相關(guān)S盒來(lái)實(shí)現(xiàn)，因?yàn)橛?jì)算機(jī)軟件可以快速實(shí)現(xiàn)模加的計(jì)算。但是，要計(jì)算bit模加的差分卻非常耗時(shí)，因?yàn)榻o定2個(gè)加數(shù)的差分，需要遍歷和差分的所有可能取值才能確定所有可能的和差分。對(duì)于bit的字，需要遍歷2種可能取值，由于密碼算法中通常使用32 bit的字，因此，這是無(wú)法實(shí)現(xiàn)的。下面給出相關(guān)差分分布表的定義，利用相關(guān)差分分布表可以非常有效地計(jì)算模加的差分，因此，利用相關(guān)差分分布表可以有效地搜索ARX密碼的差分特征，就像基于S盒的密碼中搜索差分特征一樣。

定義4 設(shè),,∈，=。假設(shè),∈，且滿足=×。令,,分別表示,,的異或差分，=()(()())，則的計(jì)算可以劃分成塊，每一塊包含bit。對(duì)于每一塊可以構(gòu)造相應(yīng)的差分分布表，由于加法運(yùn)算中進(jìn)位的影響，2個(gè)相鄰的差分分布表是相關(guān)聯(lián)的，這樣的差分分布表稱為相關(guān)差分分布表。

利用相關(guān)差分分布表計(jì)算模加差分概率的過(guò)程如下：設(shè),,,','∈，=，令,,分別表示,,的異或差分，即=',='，則

其中，(,)=(c?1,…,1,0)表示的進(jìn)位向量，(',')=('?1,…,'1,'0)表示''的進(jìn)位向量，0=0，'0=0。

令

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

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

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

δ定義為()(''')=Γ，則比特模加的差分概率可以按照全概率公式進(jìn)行如下計(jì)算。

1) 當(dāng)=1時(shí)

(,)=(0) (7)

2) 當(dāng)=2時(shí)

3) 當(dāng)≥3時(shí)

下面給出一個(gè)具體實(shí)例來(lái)說(shuō)明相關(guān)差分分布表的構(gòu)造，以及利用相關(guān)差分分布表計(jì)算模加的差分概率。

例1 設(shè),,,,,∈，=，,,分別表示,,的異或差分。令=(1010)2,=(1101)2,=(0101)2，則根據(jù)模加差分概率的定義，可以計(jì)算出(,)=。

接下來(lái)，利用相關(guān)差分分布表計(jì)算(,)。令表示的進(jìn)位向量，'表示()()的進(jìn)位向量，=(3,2,1, 0)，'=('3,'2,'1, 0)。因?yàn)?,都是4 bit字，所以，可以構(gòu)造2個(gè)2 bit的相關(guān)差分分布表0和1，0和1通過(guò)進(jìn)位比特2和'2相關(guān)聯(lián)。因?yàn)?,'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)就是相關(guān)差分分布表0的輸入和輸出差分，(1,1,1)就是相關(guān)差分分布表1的輸入和輸出差分，在存儲(chǔ)過(guò)程中將輸入差分(0,0)和(1,1) 分別存儲(chǔ)成0||0和1||1。相關(guān)差分分布表0和1的構(gòu)造算法如下。

算法1 相關(guān)差分分布表0和1的構(gòu)造算法

1) 構(gòu)造0，其中，表示模加中的進(jìn)位標(biāo)記，用于選擇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) 構(gòu)造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)

因此，可以計(jì)算出

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

表1 相關(guān)差分分布表CS0

表2 相關(guān)差分分布表CS1

3 ARX密碼差分特征的自動(dòng)化搜索算法

在1994年的歐密會(huì)上，Matsui提出了一種自動(dòng)化搜索DES最優(yōu)差分特征的算法[16]。Matsui算法本質(zhì)上是一種深度優(yōu)先的搜索算法，對(duì)于輪差分特征，Matsui算法執(zhí)行一個(gè)遞歸搜索。如果已知輪最優(yōu)差分特征概率B(0≤≤?1)和輪最優(yōu)差分特征概率的一個(gè)初始估計(jì)值，Matsui算法就能給出輪最優(yōu)差分特征概率B，對(duì)輪數(shù)進(jìn)行迭代，就可以得到所有輪數(shù)的最優(yōu)差分特征概率。然而Matsui算法僅僅適用于基于S盒的分組密碼，并不能用于搜索ARX密碼的差分特征，因?yàn)闊o(wú)法直接構(gòu)造模加的差分分布表。Biryukov等在CT-RSA2014提出了搜索ARX密碼差分特征的閾值搜索算法[19]，他們提出部分差分分布表的概念，第一次將Matsui算法擴(kuò)展到了ARX密碼差分特征的搜索。盡管Biryukov等的算法可以用于搜索各種ARX密碼的差分特征，但是他們的算法無(wú)法保證得到最優(yōu)的差分特征。

本文提出了相關(guān)差分分布表的概念，利用相關(guān)差分分布表，同樣將Matsui算法擴(kuò)展到了ARX密碼差分特征的搜索。因?yàn)楸疚牡乃惴軌虮闅v明文差分，所以本文的算法能夠給出ARX密碼的最優(yōu)差分特征。下面以Feistel結(jié)構(gòu)為例，給出本文的算法。Feistel結(jié)構(gòu)的一輪如圖1所示，其中F表示包含循環(huán)移位（rotation）、邏輯移位（shift）、異或運(yùn)算（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

當(dāng)計(jì)算(ΔX?1, ΔYΔZ)時(shí)，只需要通過(guò)查找相關(guān)差分分布表即可，跟基于S盒的密碼算法中差分概率的計(jì)算類似。對(duì)于bit的模加，相關(guān)差分分布表的字長(zhǎng)可以是整除的任意整數(shù)，并且其字長(zhǎng)越大，搜索算法執(zhí)行效率越高。考慮到相關(guān)差分分布表的存儲(chǔ)，本文在實(shí)驗(yàn)過(guò)程中采用了8 bit的相關(guān)差分分布表。

4 SPECK算法及其差分特征

4.1 SPECK算法描述

SPECK算法是美國(guó)國(guó)家安全局（NSA, National Security Agency）在2013年提出的一組輕量級(jí)分組密碼算法[5]，共包含10個(gè)算法實(shí)例，其分組長(zhǎng)度分別為32 bit、48 bit、64 bit、96 bit和128 bit，相應(yīng)的算法記為SPECK32、SPECK48、SPECK64、SPECK96和SPECK128。

SPECK算法采用了類似Threefish算法的結(jié)構(gòu)，其輪函數(shù)僅僅使用了3種簡(jiǎn)單的運(yùn)算：模加（addition）、循環(huán)移位、異或。令(L?1, R?1)表示第輪的輸入，(L,R)表示第輪的輸出，第輪的輪密鑰記為K，則(L,R)可以通過(guò)下式計(jì)算

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

其中，當(dāng)分組長(zhǎng)度為32 bit時(shí)，=7,=2，對(duì)于其他分組長(zhǎng)度=8,=3 。SPECK算法的輪函數(shù)如圖2所示。

4.2 SPECK算法的差分特征

本文利用算法2搜索SPECK32、SPECK48和SPECK64的差分特征，所用的實(shí)驗(yàn)平臺(tái)是Intel Core i5 3.2 GHz，采用VS2010軟件平臺(tái)，得到的結(jié)果如下：對(duì)于SPECK32，得到的最優(yōu)差分特征包含9輪，其差分概率為2?30；對(duì)于SPECK48，得到的最優(yōu)差分特征包含11輪，其差分概率為2?45；對(duì)于SPECK64，得到的最優(yōu)差分特征包含15輪，其差分概率為2?62。這些結(jié)果跟Fu等[21]在FSE’16上發(fā)表的結(jié)果相同，但是本文的算法遍歷了SPECK32和SPECK48的明文差分，因此能夠說(shuō)明該結(jié)果就是SPECK32和SPECK48最好的差分特征，而且本文給出了SPECK32和SPECK48抗差分分析的可證明的安全界。而對(duì)于SPECK64，由于受到計(jì)算能力的限制，并沒(méi)有遍歷所有可能的明文差分，盡管如此，本文給出的結(jié)果依然是目前最優(yōu)的。SPECK32、SPECK48和SPECK64的最優(yōu)差分特征的概率如表3所示，其9輪、11輪和15輪的最優(yōu)差分特征如表4所示。

表3 SPECK32、SPECK48和SPECK64最優(yōu)差分特征的概率

表4 SPECK32、SPECK48和SPECK64的9輪、11輪和15輪最優(yōu)差分特征

5 結(jié)束語(yǔ)

本文提出了一種自動(dòng)化搜索ARX密碼最優(yōu)差分特征的算法，該算法是基于Matsui算法，通過(guò)引入相關(guān)差分分布表，解決了搜索過(guò)程中模加差分的快速計(jì)算問(wèn)題，即給定模加的輸入差分，通過(guò)查找相關(guān)差分分布表，可以快速計(jì)算出輸出差分以及差分概率。

本文以SPECK算法中的3個(gè)實(shí)例SPECK32、SPECK48和SPECK64為測(cè)試平臺(tái)說(shuō)明該算法的有效性。使用本文提出的算法搜索SPECK32、SPECK48和SPECK64的差分特征，分別得到了9輪、11輪和15輪的差分特征，其概率分別為2?30、2?45和2?62。這些差分特征是目前能夠找到的最好的差分特征，其中，SPECK32和SPECK48的差分特征通過(guò)遍歷明文差分得到，因此可以給出其抗差分分析的可證明的安全界。

本文提出的算法是一種通用的自動(dòng)化搜索ARX密碼差分特征的算法，盡管僅以SPECK算法作為測(cè)試平臺(tái)，但是此算法可以用于搜索其他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

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61379142）；國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃（“973”計(jì)劃）基金資助項(xiàng)目（No.2013CB834203）

劉正斌（1985-），男，山東青島人，中國(guó)科學(xué)院信息工程研究所博士生，主要研究方向?yàn)槊艽a學(xué)。