SIMON算法相關(guān)密鑰不可能差分特征搜索*

王旭姿,吳保峰,侯 林,林東岱

1.中國科學(xué)院 信息工程研究所 信息安全國家重點實驗室,北京 100093

2.中國科學(xué)院大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院,北京 100049

1 引言

近些年來,隨著物聯(lián)網(wǎng)和人工智能的迅速發(fā)展,人們生活中出現(xiàn)了越來越多的小型便攜設(shè)備,這些設(shè)備雖然計算資源受限,但由于其傳輸?shù)男畔⑸婕皞€人隱私越來越多,所以對安全性要求反而更高.另外隨著5G網(wǎng)絡(luò)的日益普及,對加密算法的軟硬件實現(xiàn)速度也有著越來越高的要求,傳統(tǒng)的加密算法已無法滿足需求.因此各個國家都開始著手征集和制定輕量級分組密碼算法標(biāo)準(zhǔn),其中美國NSA于2013年發(fā)布的SIMON算法和SPECK算法[1]由于其優(yōu)秀的軟硬件實現(xiàn)性能引起了廣泛的關(guān)注.2015年Yang等人于CHES發(fā)表SIMECK算法[2],將SIMON循環(huán)移位參數(shù)由(8,1,2)改為(0,5,1),并在密鑰擴(kuò)展算法中重用輪函數(shù)代替SIMON的線性密鑰擴(kuò)展算法,使其軟硬件實現(xiàn)速度更高效.

目前,學(xué)術(shù)界已有非常多對SIMON和SIMECK算法單密鑰下的安全性分析結(jié)果,如差分分析[3-7]、不可能差分分析[8-12]、線性分析及零相關(guān)線性分析[13-15]和積分分析[16,17]等.但相關(guān)密鑰條件下的安全性分析非常有限,SIMON算法設(shè)計者在文獻(xiàn)[18]中也提到了這一點,而SIMECK算法相關(guān)密鑰條件下安全性依賴于SIMON算法在該條件下安全性分析結(jié)果[2].截至目前只有文獻(xiàn)[19]中給出了SIMON和SIMECK相關(guān)密鑰下高概率差分長路徑,文獻(xiàn)[20]中給出了SIMECK在輸入輸出差分均只有1比特活躍條件下的相關(guān)密鑰不可能差分特征.而SIMON和SIMECK算法相比較,不同點就在于循環(huán)移位參數(shù)的改變和密鑰擴(kuò)展算法由線性變?yōu)榉蔷€性,研究其密鑰擴(kuò)展算法對安全性的影響是非常有必要的.為了應(yīng)對資源受限條件下對高速加解密的需求,美國NIST正在征集輕量級密碼算法標(biāo)準(zhǔn),截至目前第二輪候選算法中有三個算法采用了SIMECK輪函數(shù)作為底層置換算法[21-23],分別為ACE、SPIX和SpoC,在此底層置換基礎(chǔ)上不僅實現(xiàn)加密和解密功能,也同時提供了MAC和HASH功能.結(jié)合SIMON和SIMECK算法安全性分析現(xiàn)狀,進(jìn)一步研究其相關(guān)密鑰條件下的安全性是當(dāng)前急需解決的問題.在表1中總結(jié)了SIMON32/64和SIMON48/96當(dāng)前已有區(qū)分器對應(yīng)的概率和包含的輪數(shù),并與本文結(jié)果對比.

目前對分組密碼算法進(jìn)行安全性分析時,使用的自動化搜索工具主要為MILP、SAT、SMT/STP等.這些工具的搜索效率受維數(shù)影響很大,特別是當(dāng)前輕量級分組密碼算法幾乎都是基于比特運算的,即使是單密鑰下路徑搜索,隨著輪數(shù)的增加,搜索速度降低也非常明顯,無法在此基礎(chǔ)上直接進(jìn)行相關(guān)密鑰下路徑搜索.對不可能差分特征的搜索,需要限制輸入輸出差分均只有1比特或1個S盒活躍,在此基礎(chǔ)上找出概率為1的截斷差分路徑,當(dāng)中間某一輪中某個比特位的差分值沿加密和解密方向分別以概率1取值為0和1時,則找到了一條不可能差分特征,這種產(chǎn)生矛盾的情況被稱為miss-in-the-middle.2017年歐密會上Sasaki和Todo給出了利用MILP(mixed-integer linear programming)自動化搜索不可能差分特征的方法[24],然而由于全空間搜索的復(fù)雜度過高,該方法也需要限制輸入和輸出差分均只有1比特或1個S盒活躍.SIMON算法由于采用線性密鑰擴(kuò)展算法,其每一輪的差分活躍比特數(shù)并不隨著輪數(shù)的增加而逐漸增加,限制其輸入輸出差分和主密鑰差分中活躍比特數(shù)并不能得到更長輪的不可能差分特征.

本文通過對SIMON加密算法中間輪某1比特差分取確定值時,每一輪差分需滿足約束條件的研究,得到其子密鑰差分需滿足的約束條件,并結(jié)合密鑰擴(kuò)展算法的MILP模型進(jìn)行求解,如果有解則說明找到了一條不可能差分路徑,如果模型無解則需要繼續(xù)調(diào)整約束條件求解.

本文第2節(jié)給出SIMON算法和MILP模型的基本介紹,第3節(jié)研究了SIMON子密鑰需滿足的約束條件.本文首次給出SIMON32/64和SIMON48/96的相關(guān)密鑰不可能差分特征,分別為13輪,其對應(yīng)的單密鑰下最長不可能差分特征分別為11輪和12輪.第4節(jié)給出這兩條不可能差分特征矛盾產(chǎn)生的具體推導(dǎo).

表1SIMON32/64和SIMON48/96不同類型區(qū)分器比較

Table 1 Comparision of different distinguishers for SIMON32/64 and SIMON48/96

分析方法 SIMON32/64 SIMON48/96概率 輪數(shù) 來源 概率 輪數(shù) 來源差分路徑 2?30 11 [5] 2?46 15 [5]差分區(qū)分器 2?30.76 14 [5] 2?46.32 17 [3]線性路徑 2?30 11 [25] 2?46 15 [25]線性區(qū)分器 2?29.43 13 [25] 2?46.3 21 [25]積分區(qū)分器 1 15 [11] 1 16 [17]相關(guān)密鑰差分路徑 2?24 15 [19] 2?36 15 [19]零相關(guān)線性特征 1 11 [11] 1 12 [11]不可能差分特征 1 11 [19] 1 12 [19]相關(guān)密鑰不可能差分特征 1 13 本文 1 13 本文

2 預(yù)備知識

2.1 符號

本文中用到的符號如表2所示.

表2 符號Table 2 Notations

2.2 SIMON算法描述

SIMON算法是一種Feistel類型算法,其輪函數(shù)僅包含:與運算、循環(huán)移位運算和異或運算,因此具有非常好的軟硬件實現(xiàn)性能.SIMON算法依據(jù)不同參數(shù)一般記為SIMON2n/mn,分組長度記為2n,其中n∈{16,24,32,48,64},密鑰長度記為mn,m∈{2,3,4},其對應(yīng)加密輪數(shù)如表3所示.其輪函數(shù)為F(X r,X r?1)=(S a(X r)⊙S b(X r)⊕S c(X r)⊕X r?1⊕K,X r),循環(huán)移位參數(shù)(a,b,c)取值為(8,1,2),輪函數(shù)示意圖如圖1所示.

圖1 SIMON輪函數(shù)Figure 1 Round function of SIMON

表3 SIMON參數(shù)Table 3 SIMON parameters

SIMON算法密鑰擴(kuò)展算法根據(jù)m取值不同分為3個版本,但均為線性擴(kuò)展算法,如下所示

其中常數(shù)C=2n?4=0xff···fc,常數(shù)序列{z j}的生成詳細(xì)過程見文獻(xiàn)[1],由于本文只考慮子密鑰差分,而輪常數(shù)不影響差分所以本文不再贅述.

2.3 MILP模型介紹

混合整數(shù)線性規(guī)劃(MILP)的方法在分組密碼的安全性分析中發(fā)揮了重要作用.2014年亞密會上Sun等人首次給出構(gòu)造分組密碼算法MILP模型的方法[26],對多種算法的最小活躍S盒路徑和高概率差分路徑、線性路徑的搜索效率都很高,利用MILP更新了多種算法的最優(yōu)路徑及其包含的輪數(shù).2017年歐密會Sasaki和Todo給出了利用MILP模型自動化搜索輸入輸出差分只有1比特或1個S盒活躍的不可能差分特征的方法[24].2016年亞密會Xiang等人給出了利用MILP模型自動化搜索基于可分性的積分路徑的方法[17].目前MILP已成為分組密碼算法安全分析必不可少的重要工具,需要解決的關(guān)鍵問題是如何構(gòu)造適合不同分析方法和加密算法的MILP模型.

由于本文目標(biāo)是搜索SIMON相關(guān)密鑰下不可能差分特征,只需構(gòu)造并求解密鑰擴(kuò)展算法的MILP模型和附加的約束條件,而SIMON算法采用線性的密鑰擴(kuò)展算法,只包含異或操作,所以在該部分我們只展示能夠完整描述異或操作的線性不等式組.SIMON算法不同密鑰長度對應(yīng)的密鑰擴(kuò)展算法中子密鑰差分需滿足的條件如下:

以m=4為例,第r輪子密鑰的第i比特差分滿足等式

Sun等人在文獻(xiàn)[24]中給出的刻畫異或操作的約束條件需要引入虛擬變量.設(shè)a⊕b=c,其對應(yīng)的線性不等式組為

3 SIMON不可能差分特征的約束條件

對SIMON算法搜索不可能差分特征,無論是手動推導(dǎo)概率為1的截斷差分特征還是用MILP等自動化搜索工具,都需要限制輸入輸出差分只有1比特活躍,這么做的依據(jù)是差分活躍比特數(shù)會隨著輪數(shù)增加而逐漸增多.以1比特活躍作為初始值期望其截斷差分路徑能夠包含盡可能多的輪數(shù),而SIMON密鑰擴(kuò)展算法采用線性結(jié)構(gòu),即使限制主密鑰差分只有1比特活躍,也會在幾輪之后很快完成全擴(kuò)散,這使得無法通過限制初始活躍比特數(shù)的方法來得到相關(guān)密鑰下最長不可能差分特征.本文在3.1節(jié)中研究了SIMON中某一比特位置差分取確定值時,其上一輪差分需滿足的必要條件,并在3.2節(jié)中首次給出不限制初始差分值的截斷差分路徑,與原有結(jié)果進(jìn)行對比,以SIMON32為例利用miss-in-the-middle方法,使截斷差分在中間輪某比特位分別以概率1取值為0和1產(chǎn)生矛盾,在3.3節(jié)中給出此條件下每一輪子密鑰需滿足的約束條件.

3.1 ROTATION-AND運算差分傳播性質(zhì)

3.2 SIMON32截斷差分

SIMON算法截斷差分已有結(jié)果都是限制輸入差分只有1比特取值為1,其他位置差分取值均為0,以SIMON32為例,結(jié)果如表4所示.

表4 SIMON32輸入差分只有1比特活躍的截斷差分路徑Table 4 Truncated differential trails for SIMON32 with 1-bit constraint

利用3.1節(jié)中定理1,我們先確定中間某一輪第i比特位差分取值為0,不妨取i=1.由此逆向推導(dǎo)當(dāng)已知第6輪截斷差分(????????????????,?0??????????????)以概率為1成立時,第0-5輪所需滿足的約束條件,結(jié)果如表5所示.

表5 SIMON32第6輪右半部分第1比特位以概率1取值為0時需滿足的約束條件Table 5 Constraints for value of 1th bit of 6th round of right block of SIMON32 with probability 1

3.3 SIMON32子密鑰差分約束條件

本節(jié)以SIMON32為例,構(gòu)造出其中間輪能夠以概率為1產(chǎn)生矛盾時其子密鑰差分需滿足的約束條件.根據(jù)3.2節(jié)中給出的當(dāng)中間第r輪第i比特差分以概率1取值為0或1時,其他輪差分必須滿足的差分約束條件,結(jié)合引理1推出輪子密鑰差分必須滿足的約束條件.分為如下兩步:

由此隨著輪數(shù)的增加和取確定差分值的比特數(shù)的增加,所有可能的情況數(shù)量會呈指數(shù)增長.由于當(dāng)前計算能力有限,本文增加了一條限制條件:輪子密鑰差分約束條件中只有一比特差分值被限制為1,且該限制條件發(fā)生在第2步中.即若需保證中間輪某位置差分值取0時,其前幾輪差分取值情況均參照式(4),若需保證中間輪某位置差分值取1時,其前幾輪約束條件中只有1比特約束條件參照式(7),其他比特位約束條件均參照式(6).滿足約束條件式(7)的比特位是可以選擇的,由此輪子密鑰差分存在多組可用約束條件,結(jié)合密鑰擴(kuò)展算法MILP模型依次對其進(jìn)行求解,若有解則得到一條相關(guān)密鑰不可能差分路徑.

表6 SIMON32相關(guān)密鑰不可能差分中子密鑰差分的一組約束條件Table 6 Constraints of subkey difference for related-key impossible differentials for SIMON32/64

4 SIMON32和SIMON48相關(guān)密鑰不可能差分特征

本節(jié)給出對SIMON算法搜索相關(guān)密鑰不可能差分特征的步驟,并在圖2中給出SIMON32/64的一條13輪相關(guān)密鑰不可能差分路徑(0000,2a94)?(c4e9,0000),其主密鑰差分為(2a94,8000,4082,8005),在圖3中給出SIMON48/96的一條13輪相關(guān)密鑰不可能差分特征(000000,e14102)?(18852e,000000),其主密鑰差分為(e14102,000000,000002,0000cc),從而顯示的展示中間輪矛盾產(chǎn)生原因.圖2和圖3分別用藍(lán)色標(biāo)記出為滿足中間輪0-1矛盾以概率1發(fā)生時其每一輪差分和子密鑰約束條件中必須取固定值的差分比特位,用紅色標(biāo)記出子密鑰約束條件中唯一差分值被限制為1的比特位,其中圖2可以和表6對應(yīng).

圖3 SIMON48/96的13輪相關(guān)密鑰不可能差分路徑Figure 3 13-round related-key impossible differential trail for SIMON48/96

SIMON算法相關(guān)密鑰不可能差分特征搜索步驟如下:

(3)結(jié)合2.3節(jié)MILP模型中異或操作對應(yīng)的線性不等式組和SIMON算法的密鑰擴(kuò)展算法,得出其MILP模型,并在此基礎(chǔ)上添加以上2步得到的約束條件,利用Gurobi求解工具(https://www.gurobi.com)對該模型自動化求解.若有解,則得到一條相關(guān)密鑰不可能差分特征,將子密鑰差分結(jié)果代入得到完整路徑,例如圖2和3;若無解,去掉首輪或最后一輪約束條件后繼續(xù)求解,直到包含輪數(shù)小于等于單密鑰下不可能差分特征輪數(shù)為止,若仍無解則回到第2步調(diào)整子密鑰差分約束條件中差分值為1的比特位后繼續(xù)求解.

圖2 SIMON32/64的13輪相關(guān)密鑰不可能差分路徑Figure 2 13-round related-key impossible differential trail for SIMON32/64

5 總結(jié)

目前對于分組密碼算法單密鑰下不可能差分特征的搜索結(jié)果有很多,無論是對基于字運算還是基于比特運算的算法,考慮到算法本身的擴(kuò)散性,一般化方法是限制其輸入和輸出差分均只有一個S盒活躍或只有一比特活躍作為初始搜索條件,并結(jié)合其概率為一的截斷差分路徑找出符合miss-in-the-middle條件的路徑.隨著分組密碼算法中自動化搜索算法的廣泛應(yīng)用,利用算法MILP模型并給定輸入輸出差分即可自動化檢測該路徑是否為不可能的.但由于基于比特運算的分組密碼算法全空間檢測復(fù)雜度過高為O(22n),其中n為分組長度,目前不可能差分路徑自動化搜索仍保持輸入輸出差分只有一比特活躍的限制.若密鑰擴(kuò)展算法是隨著輪數(shù)增加而逐漸擴(kuò)散則可以沿用此搜索策略,如文獻(xiàn)[20]中利用MILP對SIMECK算法搜索輸入輸出差分在1比特限制條件下的最長輪相關(guān)密鑰不可能差分特征.而對于SIMON算法我們沿用此搜索策略,對SIMON32只能找到最長11輪相關(guān)密鑰不可能差分特征,此輪數(shù)與單密鑰下最優(yōu)結(jié)果保持一致.其原因是由于SIMON采用了和SIMECK完全不同的線性密鑰擴(kuò)展算法,其活躍比特數(shù)并不隨輪數(shù)增加而逐漸擴(kuò)散,難以直接控制其每一輪子密鑰差分.

那么SIMON算法在相關(guān)密鑰條件下是否存在包含更多輪數(shù)的不可能差分特征?如何在無一比特活躍限制條件,全空間搜索復(fù)雜度高達(dá)O(2(m+2)n)的情況下,對SIMON算法搜索盡可能包含更多輪數(shù)的相關(guān)密鑰不可能差分特征?本文通過研究SIMON算法中非線性部件ROTATION-AND輸出差分中第i比特以概率1取值為0或1時其輸入差分需滿足的充要條件,結(jié)合miss-in-the-middle方法,在給定中間輪某一比特差分值后,分別沿加密和解密方向以概率1擴(kuò)展.最后得到當(dāng)中間輪第i比特差分以概率1取某確定值時,其對應(yīng)的輸入或輸出差分需滿足的條件.考慮到每一輪子密鑰均以異或的方式加入每一輪運算,在搜索相關(guān)密鑰不可能差分特征時還需考慮由子密鑰差分引起的混亂和擴(kuò)散.本文結(jié)合截斷差分約束條件不斷調(diào)整子密鑰差分的約束條件,使每一輪在引入子密鑰差分后仍能保持中間輪第i比特以概率1取差分值0或1.通過利用MILP模型對SIMON算法密鑰擴(kuò)展算法和約束條件進(jìn)行求解,若模型有解則得到一條相關(guān)密鑰下不可能差分特征,否則需要調(diào)整子密鑰差分約束條件繼續(xù)求解.

利用本文方法對SIMON32/64和SIMON48/96分別得到一條13輪相關(guān)密鑰不可能差分特征,而其單密鑰下最長輪不可能差分特征包含輪數(shù)分別為11和12輪.這也是首次有對SIMON算法相關(guān)密鑰不可能差分特征的搜索結(jié)果,是對SIMON算法相關(guān)密鑰條件下安全性分析的補充.

同時本文方法也存在一些改進(jìn)空間.第一,密鑰擴(kuò)展算法約束條件存在多比特差分為1的情況,由于搜索條件限制本文目前只考慮了1比特的情況,如果能自動化遍歷所有可能的子密鑰差分約束條件并求解可能會得到更多數(shù)量的或包含更多輪數(shù)的相關(guān)密鑰不可能差分特征;第二,利用MILP求解約束條件的方法得到子密鑰差分,對SIMON32和SIMON48求解速度是比較理想的,最多只需要幾分鐘,而對大于等于64的分組長度求解速度非常慢,如果能調(diào)整密鑰擴(kuò)展算法MILP模型或使用其他更高效的求解方法,則可以對其他參數(shù)搜索得到其相關(guān)密鑰下不可能差分特征.

本文通過對SIMON相關(guān)密鑰不可能差分特征的搜索,并與SIMECK算法相同條件下結(jié)果對比,發(fā)現(xiàn)密鑰擴(kuò)展算法的差分變化規(guī)律對相關(guān)密鑰不可能差分特征有很大影響.若限制SIMON算法主密鑰差分只有1比特活躍其余全0,無法得到比單密鑰條件下包含更多輪數(shù)的不可能差分特征,而采用本文方法能夠?qū)IMON32/64和SIMON48/96分別給出一條13輪相關(guān)密鑰不可能差分特征,這也是SIMON算法不可能差分特征首次得出相關(guān)密鑰條件下的搜索結(jié)果.隨著計算能力的提升,SIMON和SIMECK算法相關(guān)密鑰不可能差分特征的搜索還有很大的研究空間,研究結(jié)果對算法安全性研究和密鑰擴(kuò)展算法的設(shè)計都有很重要的意義.