輕量級可調分組密碼QARMA的不可能差分攻擊

張國強,張文英

(山東師范大學 信息科學與工程學院,濟南 250014)

1 引 言

分組密碼作為對稱加密的一個重要分支,在信息安全方面具有極其重要的作用,一直是研究的熱點.分組密碼的設計一直遵循香農提出的“混淆”與“擴散”原則.

可調分組密碼是由Moses Lisko等人在2002年提出的.可調分組密碼是一種帶有額外輸入的分組密碼,我們通常稱這一額外輸入為調柄(tweak).調柄并不需要保密,通過加入它來提高加密的靈活性.

近些年,隨著微型設備如RIFD、無線傳感等技術的飛速發展,輕量級分組密碼應運而生并成為研究的熱點.許多輕量級分組密碼被提出來,如LBlock[1]、Khudra[2]、RECTANGLE[3]、Lilliput[4]、SIMON[5]等.另外,我國的王鵬博士、吳文玲教授等基于CTR模式利用Hash-CTR-Hash結構設計了HCTR模式[6].

由Roberto Avanzi設計的QARMA算法是一種輕量級可調分組密碼[7].在2016年,QARMA被引進到ARMv8-A架構,用來實現軟件保護.QARMA算法有64比特和128比特兩個版本.

不可能差分攻擊是差分密碼分析的一個變種,是由Kundesn[8]和Biham[9]分別獨立提出的.不可能差分密碼分析方法是利用概率為0的特征,其基本思想是排除那些使得概率為0的特征或者差分的候選密鑰.對于概率為0的差分路徑,如果我們用正確的密鑰解密密文對時,一定不會得到符合該路徑的差分;而當我們用猜測的密鑰去解密密文時,如果得到了符合該路徑的差分,則我們猜測的密鑰是錯誤的,應該篩去.當我們篩掉全部的錯誤密鑰后,剩下的就是我們要恢復的正確密鑰.

由于該分析方法簡單有效,因此在算法分析中得到廣泛應用,成功的用于分析大量的分組密碼,如:PRINCE[10],SIMECK[11],LBlock-s[12],AES[13],MIBS[14]等.

到目前為止,還沒有任何用不可能差分攻擊對QARMA算法進行分析的文檔.據我們所知,對于QARMA算法最好的攻擊是文獻[15]中的中間相遇攻擊.該攻擊在包含了反仿射結構的5輪區分器的基礎上,對10輪的QARMA-64算法進行了攻擊,攻擊所需的時間復雜度為270.1次10輪加密,存儲復雜度為2116個192比特序列,數據復雜度為253個明文.

本文使用不可能差分攻擊對QARMA算法進行分析.我們給出了5輪的不可能差分區分器,進而對10輪的QARMA算法進行了攻擊.另外,通過使用兩條不同的差分路徑,來進一步降低了攻擊的時間復雜度.與現有的中間相遇攻擊相比[15],我們的攻擊的時間復雜度和存儲復雜度均有所降低.據我們所知,這是首次使用不可能差分對該算法進行分析.

2 QARMA算法

在本節中首先對本文中用到的符號進行說明,然后對QARMA算法進行簡要的介紹.

2.1 符號說明

P:明文

C:密文

ω0:主密鑰的左半部分

K0:主密鑰的右半部分

T:調柄

Ci:輪常數

Xi,Yi,Zi,Wi:加密過程中第i輪的狀態

Ki[j]:第i輪的密鑰的第j個半字節

‖:級聯操作

>>>:循環右移

2.2 QARMA算法介紹

QARMA是帶有調柄(tweak)的可調分組密碼.QARMA算法加密過程由三部分組成(如圖1所示),其中第一部分和第三部分是完全相反的操作變換.QARMA的具體加密流程如圖2所示.

圖1 QARMA整體結構Fig.1 Overall scheme

QARMA算法的分組長度有64比特和128比特兩個版本.接下來,我們以64比特版本為例來對加密過程中的操作進行具體說明.

圖2 QARMA具體結構Fig.2 Structure of QARMA

主密鑰長度是128比特,分為等長的兩部分(ω0‖K0),各為64比特.加密過程中還用到密鑰ω1‖K1,其中

ω1=o(ω0)=(ω0>>>1)+(ω0>>(63)),K1= K0.

QARMA-64是帶有仿反射結構的SPN結構的分組密碼.加密過程可以看做是對64比特內部狀態的一系列操作.內部狀態表示成一個4×4的方陣,方陣中每個元素是4比特(n=64),如下所示:

加密過程中的第一部分包含如下四個基本操作:

密鑰加操作(AK):將內部狀態與輪密鑰Ki、調柄T以及輪常數Ci進行模2加操作.

位置變換操作(τ):將內部狀態的16個元素進行位置變換:

τ=[0,11,6,13,10,1,12,7,5,14,3,8,15,4,9,2]

列混合操作(M):用狀態矩陣M乘以內部狀態的每一列.矩陣M如下所示:

值得注意的是,矩陣M是對合矩陣(M2=I).一個元素乘以ρi相當于將這個元素向左循環移動i比特.

字節替換操作(S):內部狀態的每個元素進一個4比特的s盒.

表1 QARMA-64 s盒
Table 1 Sbox of QARMA-64

x01234567s(x)014210915811x89101112131415s(x)6437131215

加密流程的第三部分是與第一部分完全相反的操作.在第一輪和最后一輪省略掉了位置變換和列混合操作,只進行密鑰加和進s盒操作.

加密流程的第二部分包含前向一輪、后向一輪以及一個仿反射結構.仿反射結構包含四個操作:位置變換、列混合、密鑰加、位置變換逆變換.在列混合操作中用到的矩陣Q和M是一樣的.

3 QARMA的10輪不可能差分攻擊

在本節中,我們首先給出了一個關于QARMA的列混合變換的性質,然后給出了一個5輪的不可能差分區分器,最后在5輪不可能差分區分器的基礎上,對10輪的QARMA進行攻擊.

3.1 QARMA列混合變換的性質

性質1.如果一列中有一個位置差分為0,另外三個元素存在差分,那么經過列混合變換后在原來差分為0的位置有差分,其余三個位置沒有差分的概率為2-8.例如:P((0***)→(*000))=2-8(其中0表示差分為0,*表示差分不為0,兩者都代表一個4比特的元素).

證明:

在這里我們用一個一般性的例子((0***)→(*000))進行說明.我們用x1x2x3x4表示輸入狀態一列中的4個位置的差分.首先假設輸入只有第一個位置上差分為0(x1=0,x2≠0,x3≠0,x4≠0),輸出的第一個位置差分不為0,第二、三個位置上差分為0,不考慮第四個位置的差分,那么能得到這種輸出的概率為2-8,即:P((0***)→(*00?))=2-8.根據以上條件,我們可以列出以下等式:

進而可以得到:ρ·x1+ρ·x3+ρ2·x4=0,ρ2·x1+ρ·x2+ρ·x4=0.由此可以計算y=ρ·x1+ρ2·x2+ρ·x3=0.所以輸出三個位置沒有差分的概率為2-8.

當我們改變輸入或者輸出差分為0的位置時,使用同樣的方法可以得到此結論.因此性質1得證.

3.2 5輪不可能差分區分器

如圖3所示(白色位置表示差分為0,黑色位置表示一定存在差分,陰影位置表示差分不確定),當輸入為差分為(a000 0a00 0000 0000)時,經過兩輪的第一部分變換以及仿反射結構后,輸出差分為(**?* 0*?* *?** *?*0).當輸出差分為(0000 *000 0000 0000)時,解密三輪,我們得到輸出差分為(*??* **?? ???? ?*?*).我們發現在第4和第15個元素位置存在矛盾.由此我們得到了一條5輪的不可能差分路徑:(a000 0a00 0000 0000)→(0000 *000 0000 0000)(其中,a表示差分為a,*表示一定存在差分,？表示差分不確定).

圖3 QARMA 5輪不可能差分區分器Fig.3 Distinguisher of 5-Round on QARMA

3.3 10輪不可能差分攻擊

利用上述的不可能差分路徑,我們在前面加兩輪,后面加三輪,對10輪的QARMA進行攻擊.

選取2n個明文結構,每個結構里面的明文在(4,5,10,11,14,15)6個位置上取遍所有值,其余10個位置上固定.每個結構中包含224個明文,可以構成224×(224-1)/2≈247個明文對.2n個結構可以得到2n+47個明文對.

1)對于每個結構,將明文加密得到密文,看密文在C[0,1,2,3,6,9,12]位置的差分是否為0,差分不為0的刪除.經過這一步后,剩余的明密文對數量為2n+47×2-28=2n+19.

2)猜測密鑰k1[4,11,14],根據密鑰編排,可以求出k2[4,11,14].對于剩下的每一對,可以求出Y2[4,11,14],經過位置變換操作后,可以求出W2[1,9,13].進而可以計算ΔZ2[1,5,9,13],如果ΔZ2[1,9,13]=0,則保留;否則,刪除.根據性質1,經過這一步后剩余的明密文對的數量為2n+19×2-8=2n+11.

圖4 QARMA 10輪不可能攻擊Fig.4 Impossible differential attack on QARMA

3)根據密鑰編排及k1[4,11,14],可以計算k10[4,11,14]和k9[4,11,14].對于剩下的每一對,可以求出Y9[4,11,14],經過位置變換操作后,可以求出W9[1,9,13].進而可以計算ΔZ9[1,9,13],如果ΔZ9[1,9,13]=0,則保留;否則,刪除.經過這一步后剩余的明密文對的數量為2n+11×2-8=2n+3.

4)猜測密鑰k1[5,10,15],根據密鑰編排,可以求出k2[5,10,15].對于剩下的每一對,可以求出Y2[5,10,15],經過位置變換操作后,可以求出W2[4,8,12].進而可以計算ΔZ2[0,4,8,12],如果ΔZ2[4,8,12]=0且ΔZ2[0]=ΔZ2[5],則保留;否則,刪除.經過這一步后剩余的明密文對的數量為2n+3×2-12=2n-9.

5)根據密鑰編排及k1[5,10,15],可以計算k10[5,10,15]和k9[5,10,15],可以求出Y9[5,10,15],經過位置變換操作后,可以求出W9[4,8,12].進而可以計算ΔZ9[4,8,12],如果ΔZ9[4,8,12]=0,則保留;否則,刪除.經過這一步后剩余的明密文對的數量為2n-9×2-8=2n-17.

6)猜測k10[7,8,13],可以計算出k9[7,8,13],可以求出Y9[7,8,13],經過位置變換操作后,可以求出W9[3,7,11].進而可以計算ΔZ9[3,7,11],如果ΔZ9[3,7,11]=0,則保留;否則,刪除.經過這一步后剩余的明密文對的數量為2n-17×2-8=2n-25.

7)根據k10[5,15],推導出k8[5,15].猜測k8[0],可以計算出Y8[0,5,15],進而計算W8[0,8,12],進一步計算ΔZ8[0,8,12].根據性質1,ΔZ8[0,8,12]=0的概率為2-8.

表2 時間復雜度和空間復雜度
Table 2 Time complexity and memory complexity

步驟時間復雜度存儲復雜度(1)237．9+24(10R+P)≈265．4R2×237．9+1964?bit(2)3/16×2×237．9+19×212(R+ADK+S)≈268．5R2×237．9+1164?bit(3)3/16×2×237．9+11×212((R+ADK+S)≈260．5R2×237．9+364?bit(4)3/16×2×237．9+3×224(R+ADK+S)≈264．5R2×237．9-964?bit(5)3/16×2×237．9-9×224(R+ADK+S)≈252．5R2×237．9-1764?bit(6)3/16×2×237．9-17×236(R+ADK+S)≈256．5R2×237．9-2564?bit(7)3/16×2×237．9-25×240R≈251．5R總計265．4+268．5+260．5+264．5+252．5+256．5+251．5≈268．7R257．964?bit

我們總共猜測了40比特的密鑰,經過上述一系列操作后,剩余的錯誤密鑰數量為N=(240-1)×(1-2-8)2^(n-25).為了使N<1,我們取n=37.9.這樣,我們就可以得到唯一正確的40比特密鑰k0[0,4,5,7,8,10,11,13,14,15].

3.4 復雜度分析

我們選擇了237.9個明文結構,所以數據復雜度為237.9+24=261.9個明文.表2顯示了每一步的時間復雜度和存儲復雜度.所以時間復雜度是268.7輪加密,相當于265.2次10輪加密,存儲復雜度為257.9個64比特序列.

通過窮舉來恢復剩余的88比特密鑰,恢復這剩余的88比特密鑰所需的時間復雜度為288(10R+P)≈291.3R.所以總的時間復雜度為270.1R +291.3R≈291.3R.可以發現,總的時間復雜度主要是由窮舉剩余的88比特密鑰所造成的.

4 雙區分器密鑰恢復算法

在本節,使用新的方法來減少恢復剩余的88比特密鑰的時間復雜度.在恢復了40比特密鑰的基礎上,先恢復k0剩余的24比特,對剩余的ω0的64比特通過窮舉來恢復.

圖5 不同的不可能差分攻擊Fig.5 Another impossible differential acttack

我們使用新的5輪不可能差分路徑(00a0 000a 0000 0000)→(0000 0000 0000 0*00)(構造方法與上一個不可能差分區分器類似).在上述區分器前面加兩輪,后面加上三輪,構成10輪的不可能差分攻擊(如圖5所示).

在恢復48比特密鑰時,使用了237.9個明文結構,總共是261.9個明文.可以使得選擇的明文前15個元素取遍所有的可能,最后一個元素取21.9個可能.同樣可以使用這些明文來構成237.9個新的明文結構,每個結構里面的明文在(2,3,8,9,12,13)6個位置上取遍所有值,其余10個位置上固定.每個結構中包含224個明文,可以構成224×(224-1)/2≈247個明文對.2m個結構可以得到2m+47個明文對.

8)對于每個結構,將明文加密得到密文,看密文在C[0,5,8,9,10,11,15]位置的差分是否為0,差分不為0的刪除.經過這一步后,剩余的密文對數量為2m+47×2-28=2m+19.

9)由于已經確定了k1[8,13] 和k2[8,13],猜測k1[2],推出k2[2].對于剩余的每一對,可以部分解密求得W2[3,11,15].進而可以計算ΔZ9[3,7,11,15],如果ΔZ9[3,11,15]=0,則保留;否則,刪除.經過這一步后剩余的密文對的數量為2m+19×2-8=2m+11.

10)根據密鑰編排以及k1[2,7,13],可以推出k10[2,7,13] 和k9[2,7,13],從而可以部分解密得到W9[3,7,15],進而可以計算ΔZ9[3,7,15],如果ΔZ9[3,7,15]=0,則保留;否則,刪除.經過這一步后剩余的明密文對的數量為2m+11×2-8=2m+3.

11)猜測k1[3,9,12],可以推出k2[3,9,12],可以部分解密得到W2[6,10,14],進而可以計算ΔZ2[2,6,10,14],如果ΔZ2[6,10,14]=0且ΔZ2[2]=ΔZ2[7],則保留;否則,刪除.經過這一步后剩余的密文對的數量為2m+3×2-12=2m-9.

12)根據密鑰編排以及k1[3,12],可以推出k10[3,12]和k9[3,12].猜測k10[6],可以推出k9[6],從而可以部分解密得到W9[2,6,10],進而可以計算ΔZ9[2,6,10],如果ΔZ9[2,6,10]=0,則保留;否則,刪除.經過這一步后剩余的密文對的數量為2m-9×2-8=2m-17.

13)猜測k10[1],推出k9[1].由于k10[4,14]和k9[4,14]已經確定,對于剩余的對,經過部分加密,可以求得W9[5,9,13],進而求得ΔZ9[5,9,13].如果ΔZ9[5,9,13]=0,則保留;否則,刪除.經過這一步后剩余的密文對的數量為2m-17×2-8=2m-25.

14)根據k10[1,11,14],推導出k8[1,11,14].進而可以計算W8[1,5,9],進一步計算ΔZ8[1,5,9].根據性質1,ΔZ8[1,5,9]=0的概率為2-8.

我們總共猜測了24比特的密鑰,經過上述一系列操作后,剩余的錯誤密鑰數量為N=(224-1)×(1-2-8)2^(m-25).為了使N<1,取m=37.1.這樣,就可以得到唯一正確的24比特密鑰.

恢復剩下的64比特密鑰所需的時間復雜度為264(10R+P)≈267.5R.

表3 時間復雜度和空間復雜度
Table 3 Time complexity and memory complexity

步驟時間復雜度存儲復雜度8)2×237．1+1964?bit9)3/16×2×237．1+19×24(R+ADK+S)≈259．7R2×237．1+1164?bit10)3/16×2×237．1+11×24(R+ADK+S)≈251．7R2×237．1+364?bit11)3/16×2×2237．1+3×216(R+ADK+S)≈255．7R2×237．1-964?bit12)3/16×2×2237．1-9×220(R+ADK+S)≈247．7R2×237．1-1764?bit13)3/16×2×2237．1-17×224(R+ADK+S)≈243．7R2×237．1-2564?bit14)3/16×2×2237．1-25×224R≈235．7R總計259．7+251．7+255．7+247．7+243．7+235．7≈259．8R257．164?bit

因此,數據復雜度為261.9個明文,總的時間復雜度為268.7+259.8+267.5≈269.3輪加密,相當于265.8次10輪加密,存儲復雜度為257.9+257.1≈258.6個64比特序列.

5 總 結

本文通過使用5輪的不可能差分路徑對10輪的QARMA-64進行攻擊.據我們所知,這是首次使用不可能差分攻擊對QARMA-64進行分析.此外我們通過使用兩個不同的5輪不可能差分區分器來降低恢復密鑰的時間復雜度.文獻[15]中的中間相遇攻擊的時間復雜度為270.1次10輪加密,存儲復雜度為2116個192比特序列,而我們的時間復雜度為265.8次10輪加密,空間復雜度為258.6個64比特序列,在時間復雜度和存儲復雜度方面我們的攻擊存在明顯的優勢.

[1] Wu Wen-ling,Zhang Lei.LBlock:a lightweight block cipher [C].Applied Cryptography and Network Security (ACNS2011),LNCS 6715,2011:327-344.

[2] Souvik Kolay,Debdeep Mukhopadhyay.Khudra:a new lightweight block cipher for FPGAs[C].International Conference on Security,Privacy,and Applied Cryptography Engineering,Springer,Cham (SPACE 2014),2014:126-145.

[3] Zhang Wen-tao,Bao Zhen-zhen,Lin Dong-dai,et al.RECTANGLE:a bit-slice lightweight block cipher sui
Table for multiple platforms[J].Science China Information Sciences,2015,58(12):1-15.

[4] Thierry P Berger,Julien Francq,Marine Minier,et al.Extended generalized Feistel networks using matrix representation to propose a new lightweight block cipher:Lilliput[J].IEEE Transactions on Computers,2016,65(7):2074-2089.

[5] Beaulieu Ray,Treatman-Clark Stefan,Shors Douglas,et al.The SIMON and SPECK lightweight block ciphers[C].Design Automation Conference (DAC),52nd ACM/EDAC/IEEE,2015:1-6.

[6] Wang Peng,Feng Deng-guo,Wu Wen-ling.HCTR:a variable-input-length enciphering mode [C].China Information System Curricula(CISC 2005),Beijing,2005:175-188.

[7] Roberto Avanzi.The QARMA block cipher family[C].IACR Transactions on Symmetric Cryptology,2017,(1):4-44.

[8] Lars Knudsen.DEAL-A 128-bit block cipher[R].In:NIST AES Proposal,1998.

[9] Eli Biham,Alex Biryukov,Adi Shamir.Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials [C].EUROCRYPT 99,LNCS 1592,1999:12-23.

[10] Jia Ping,Xu Hong,Lai Xue-jia.Impossible differential attack on LBlock-s[J].Chinese Journal of Electronics,2017,45(4):966-973.

[11] Chen Yan-qin,Zhang Wen-ying.Impossible differential attack on SIMECK32/64[J].Computer Engineering (CE),2017,43(4):141-144+153.

[12] Wei Yue-chuan,Pan Xiao-zhong,Rong Yi-sheng,et al.Impossible differential attack on block cipher PRINCE[J].Journal of Xidian University,2017,44(1):119-124.

[13] Hu Hong-jian,Jin Chen-hui,Li Xin-ran.Improved impossible differential attack of 7-Round on AES-128 [J].Journal of Cryptologic Research,2015,2(1):92-100.

[14] Fu Li-shi,Jin Chen-hui.Impossible differential attack of 13-Round on MIBS-128 [J].Journal of Electronics & Information Technology,2016,38(4):848-855.

[15] Zong Rui,Dong Xiao-yang.Meet-in-the-middle attack on QARMA block cipher [C].ePrint Archive,2016:1160.

附中文參考文獻：

[10] 賈 平,徐 洪,來學嘉.LBlock-s算法的不可能差分分析[J].電子學報,2017,45(4):966-973.

[11] 陳彥琴,張文英.SIMECK32/64算法的不可能差分分析[J].計算機工程,2017,43(4):141-144+153.

[12] 魏悅川,潘曉中,戎宜生,等.對PRINCE分組密碼的不可能差分攻擊[J].西安電子科技大學學報,2017,44(1):119-124.

[13] 胡弘堅,金晨輝,李信然.改進的7輪AES-128的不可能差分攻擊[J].密碼學報,2015,2(1):92-100.

[14] 付立仕,金晨輝.MIBS-80的13輪不可能差分分析[J].電子與信息學報,2016,38(4):848-855.