Simpira置換的差分路線研究

李 錚，張建標(biāo)，趙靜遠(yuǎn)，徐萬山，袁藝林

（1 北京工業(yè)大學(xué)信息學(xué)部 可信計(jì)算北京市重點(diǎn)實(shí)驗(yàn)室 北京 100022 2 中國科學(xué)院信息工程研究所 信息安全國家重點(diǎn)實(shí)驗(yàn)室 北京 100093 3 北京遙測(cè)技術(shù)研究所 北京 100094）

引 言

我們處在一個(gè)信息爆炸的時(shí)代，無論是人們?nèi)粘Ｉ钪械纳缃痪W(wǎng)絡(luò)、線上支付，還是航空航天、衛(wèi)星探測(cè)等科工項(xiàng)目，都離不開密碼算法的應(yīng)用。由于加密速度快，對(duì)稱密碼算法在很多效率要求比較高的事務(wù)中得到了廣泛的應(yīng)用。

目前，對(duì)稱密碼算法設(shè)計(jì)進(jìn)入一個(gè)相對(duì)成熟、較為穩(wěn)定的發(fā)展階段，算法結(jié)構(gòu)的類型主要包括有Feistel結(jié)構(gòu)、SPN（substitution permutation network）結(jié)構(gòu)、ARX（modular addition，rotation and bitwisexor）結(jié)構(gòu)等，而算法的置換函數(shù)是提供算法隨機(jī)性的重要部件，它對(duì)于密碼算法的安全性和效率等性能都十分重要。對(duì)稱密碼算法設(shè)計(jì)由算法結(jié)構(gòu)設(shè)計(jì)和內(nèi)部置換函數(shù)設(shè)計(jì)組成，但又不是一種單純的累加，算法結(jié)構(gòu)與置換函數(shù)之間的配合與相互作用也是至關(guān)重要的。對(duì)配套密碼算法進(jìn)行安全性分析研究，除了對(duì)于該算法本身具有評(píng)估價(jià)值之外，還可以對(duì)于算法結(jié)構(gòu)和置換函數(shù)的設(shè)計(jì)與結(jié)合方式給出理論參考，對(duì)密碼算法的設(shè)計(jì)也有一定的指導(dǎo)意義。

高級(jí)加密標(biāo)準(zhǔn)AES（Advanced Encryption Standard）[1]于2001年由NIST（National Institute of Standards and Technology）頒布，其安全性和效率經(jīng)過了密碼分析者和工程設(shè)計(jì)人員多年來的分析、應(yīng)用和研究，實(shí)踐出真知，AES至今在安全性和效率兩個(gè)方面的表現(xiàn)仍然十分突出，應(yīng)用十分廣泛，現(xiàn)今已成為許多算法設(shè)計(jì)的標(biāo)桿算法，也是相似應(yīng)用方向的模板算法。其設(shè)計(jì)過程遵循寬軌道設(shè)計(jì)原則，AES經(jīng)由嵌套，改造等多種方式，呈現(xiàn)在不同對(duì)稱密碼算法當(dāng)中，提供著穩(wěn)定可靠的性能。更因如此，AES及其相關(guān)算法的安全性研究具有十分重要的價(jià)值和意義。Simpira置換[2]是由Gueron和Nicky Mouha在2016年亞密會(huì)上提出的，是一族密碼置換，其內(nèi)核算法即為AES，充分利用了AES高效成熟的指令集，實(shí)現(xiàn)了高吞吐量。SPHINCS[3]由Bernstein等在2015年歐密會(huì)上提出，是基于哈希函數(shù)算法、具有后量子安全性的數(shù)字簽名算法。后來，其設(shè)計(jì)者又將其運(yùn)用到了SPHINCS當(dāng)中，提出了SPHINCS-Simpira[4]，為原始的SPHINCS-256算法加快了實(shí)現(xiàn)速度。

1 Simpira算法介紹

Simpira置換支持128×b比特的輸入，其中b是一個(gè)正整數(shù)，其設(shè)計(jì)目標(biāo)是為了覆蓋現(xiàn)有的64位存儲(chǔ)器，實(shí)現(xiàn)高吞吐量，因?yàn)楝F(xiàn)有處理器已經(jīng)具有AES的指令集。為了充分利用指令集，實(shí)現(xiàn)高吞吐量，Simpira以AES的輪函數(shù)作為唯一的構(gòu)建模塊，對(duì)于b=1的情形，Simpira相當(dāng)于輪密鑰具有固定取值的12輪AES，對(duì)于b≥2，Simpira的F函數(shù)為2輪AES，整體結(jié)構(gòu)為廣義Feistel結(jié)構(gòu)。對(duì)于以上所有的情形，考慮進(jìn)區(qū)分器的情況，設(shè)計(jì)者給出的安全界均為2128。b∈{1,2,3}時(shí)Simpira的框架圖如圖1所示。

本文主要研究的情形為F函數(shù)為1輪AES的情形，因此，接下來再簡單介紹一下AES的輪函數(shù)，包括密鑰加、S盒代換、行移位、列混合這四個(gè)步驟。這里考慮單密鑰的情形，因此忽略密鑰加。S盒代換操作過程如圖2所示，行移位操作過程如圖3所示，列混合是對(duì)狀態(tài)的每一列進(jìn)行線性變換，變換公式如下：

2 安全性分析相關(guān)研究

圖1 Simpira的框架圖（b∈{1,2,3}）[2]Fig.1 Structure of Simpira（b∈{1,2,3}）[2]

圖2 AES中的S盒代換[1]Fig.2 S-box operation in AES[1]

圖3 AES中的行移位[1]Fig.3 ShiftRows operation in AES[1]

密碼算法的設(shè)計(jì)離不開安全性分析評(píng)估。Simpira置換支持可變的狀態(tài)大小128×b比特，其中b為正整數(shù)，即為Simpira-b。鑒于差分分析和線性分析在安全性評(píng)估中的重要意義，其設(shè)計(jì)者在安全性評(píng)估中給出了最小活躍S盒個(gè)數(shù)的下界。此外，Simpira置換適用于多種功能模式，設(shè)計(jì)者提出了許多應(yīng)用場(chǎng)景，包括Even-Mansour分組密碼結(jié)構(gòu)，或用于限制輸入長度的哈希函數(shù)的無密鑰的Davies-Meyer結(jié)構(gòu)。Mendel等[5]對(duì)基于Davies-Meyer結(jié)構(gòu)的哈希函數(shù)Simpira-4給出了全輪的碰撞攻擊，主要基于15輪40個(gè)活躍S盒的碰撞路線。鑒于他們的研究工作，Simpira也經(jīng)歷了從v1版本到v2版本的改變。R?njom等[6]發(fā)現(xiàn)了Simpira-4算法中的不變子空間，Zong等[7]給出了9輪Simpira-4算法的不可能差分路線。Simpira置換選取著名的AES算法作為內(nèi)部函數(shù)，密碼工作者在過去的二十年間持續(xù)、廣泛地研究AES類算法的安全性，AES類算法的安全性分析是密碼學(xué)領(lǐng)域的焦點(diǎn)問題之一，陸續(xù)有一些縮減輪數(shù)AES的區(qū)分攻擊出現(xiàn)。區(qū)分攻擊的目的在于將密碼算法與隨機(jī)置換區(qū)分開來，也就是找到非隨機(jī)特性，使得在相應(yīng)的測(cè)試中，密碼算法與隨機(jī)置換的測(cè)試結(jié)果具有足夠不同的概率。本文發(fā)現(xiàn)的差分路線即為密碼算法區(qū)分器的一種形式，在算法安全性要求范圍內(nèi)，對(duì)縮減輪數(shù)簡化版本密碼算法進(jìn)行了分析研究。

3 差分路線研究

差分分析是密碼分析中最重要的分析方法之一，尋找概率大于隨機(jī)情況的差分路線，以此作為非隨機(jī)特性，是差分分析的關(guān)鍵，概率越高，區(qū)分效果越好。一般來說，差分路線中的活躍S盒越少，則差分路線的概率越高。事實(shí)上，Simpira設(shè)計(jì)文檔中也考慮了輪函數(shù)為1輪AES的情況，并給出在b=2的情況下，需要25輪來保證至少有25個(gè)線性活躍S盒。本文研究的對(duì)象就是Simpira-2的這種簡化情形，算法的狀態(tài)大小為256比特，整體結(jié)構(gòu)為Feistel結(jié)構(gòu)，其中F函數(shù)采用1輪AES。

對(duì)于這種情形，我們研究給出了4輪截?cái)嗖罘致肪€，共有6個(gè)活躍S盒，如圖4所示，對(duì)應(yīng)具體的4輪差分路線，概率為2–36；以及5輪截?cái)嗖罘致肪€，共有15個(gè)活躍S盒，如圖5所示，對(duì)應(yīng)具體的5輪差分路線，概率為2–91。在圖4和圖5中，灰色方塊代表字節(jié)的差分非零，部分取值需滿足一些約束條件；而白色方塊表示該字節(jié)為全零差分。中間狀態(tài)的符號(hào)表示說明，第r輪的輸入狀態(tài)記為Sr，第r輪的輸入差分記為ΔSr，Sr中（i,j）位置的字節(jié)記為Sr[i][j]，其中r≥1，0≤i≤3，0≤j≤3。第r輪字節(jié)代換S盒的輸出狀態(tài)為，類似地，第r輪過程中的狀態(tài)依次為輸入狀態(tài)，常數(shù)加、字節(jié)代換、行移位、列混合和總的輸出狀態(tài)，即，第r輪的輸出狀態(tài)，即第r+1輪的輸入狀態(tài)，其中

圖4 4輪截?cái)嗖罘致肪€Fig.4 4-round truncated differential trail

根據(jù)Feistel結(jié)構(gòu)的性質(zhì)，在第1輪中，初始狀態(tài)的左側(cè)一半，共有128比特進(jìn)入AES算法的S盒。為使得總體活躍S盒的個(gè)數(shù)更少，我們優(yōu)先考慮了第1輪中有1個(gè)活躍S盒的情況，也就是第1輪S盒代換的輸入狀態(tài)中，只有1個(gè)非零S盒。首先經(jīng)過第1輪的常數(shù)加和S盒代換操作，并不改變活躍S盒的個(gè)數(shù)。此外，我們選?。?,0）位置的字節(jié)作為活躍S盒，因此在第1輪中行移位操作相當(dāng)于一個(gè)恒等變換，并不改變活躍S盒的個(gè)數(shù)和位置。經(jīng)過第1輪的列混合操作時(shí)，其輸入差分具有1個(gè)活躍S盒，輸出差分具有4個(gè)活躍S盒，這里的輸出狀態(tài)與初始狀態(tài)當(dāng)中的右側(cè)一半比特異或。因?yàn)槲覀兛梢宰杂傻剡x取初始狀態(tài)，所以選取初始狀態(tài)右側(cè)一半與第1輪中列混合的輸出狀態(tài)完全相等，這樣可以抵消掉第1輪中F函數(shù)的輸出差分，由此，第2輪中F函數(shù)的輸入差分為零，即活躍S盒的個(gè)數(shù)為零。

第2輪中F函數(shù)的輸出狀態(tài)與初始狀態(tài)的左側(cè)一半比特異或，于是第3輪中F函數(shù)的輸入狀態(tài)與初始狀態(tài)的左側(cè)一半完全相等，可以選擇第3輪中F函數(shù)的差分變換與第1輪中的情況相同，因此，第3輪中F函數(shù)的輸入差分具有1個(gè)活躍S盒，輸出差分具有4個(gè)活躍S盒。由于第2輪中F函數(shù)的輸入差分為零，所以第4輪中F函數(shù)的輸入差分與第3輪中F函數(shù)的輸出差分一致。然后在第4輪中，常數(shù)加和S盒代換并不改變活躍S盒的位置和個(gè)數(shù)情況，在行移位操作之后，4個(gè)活躍S盒分布到了互不相同的列。于是，在列混合之后，第4輪F函數(shù)輸出的整個(gè)差分狀態(tài)中的每個(gè)S盒都活躍，實(shí)現(xiàn)了首次差分?jǐn)U滿的現(xiàn)象。在第4輪末尾，第4輪F函數(shù)的輸出狀態(tài)與第3輪F函數(shù)的輸入狀態(tài)異或，這里限定兩狀態(tài)在（0,0）位置的差分抵消。至此，給出了4輪6個(gè)活躍S盒的截?cái)嗖罘致肪€。

圖5 5輪截?cái)嗖罘致肪€Fig.5 5-round truncated differential trail

具體分析第4輪F函數(shù)后異或的情況，為了使得（0,0）位置處的差分抵消，那么第3輪的輸入差分與第4輪F函數(shù)的輸出差分相等，即例如，列出一組可能的相關(guān)差分取值：

這里第3輪、第4輪中（0,0）位置S盒的差分概率均為2–6，其他S盒的取值不受列混合操作的限制，因此，4輪差分路線具有1+0+1+4=6個(gè)活躍S盒，概率可以達(dá)到2–36。如果由此路線出發(fā)，那么第5輪中有15個(gè)活躍S盒，由此得到的5輪截?cái)嗖罘致肪€將具有21個(gè)活躍S盒。

為尋找活躍S盒個(gè)數(shù)更少的差分路線模式，我們?cè)诮財(cái)嗖罘致肪€中加入列混合中的線性約束，并選取S盒輸入、輸出的差分狀態(tài)，進(jìn)而給出具有15個(gè)活躍S盒的5輪截?cái)嗖罘致肪€，如圖5所示。為使得分別為（i,j）位置S盒的輸入差分和輸出差分，且0≤i≤3，0≤j≤3。根據(jù)第3輪的行移位

在第4輪的F函數(shù)之后，為抵消（0,0）處的差分，需要滿足在上述前提條件下，第3輪和第4輪位置S盒的輸入輸出情況需要特別研究，其他活躍S盒均可直接取到概率2–6。特別地，當(dāng)?shù)?輪（0,0）位置S盒的輸入輸出差分取值為該S盒的概率為2–6，當(dāng)?shù)?輪（0,0）位置S盒的輸入輸出差分取值為該S盒的概率為2–7。綜上，5輪差分路線具有4+0+4+1+6=15個(gè)活躍S盒，概率可以達(dá)到2–91。

4 結(jié)束語

本文對(duì)于Simpira置換的差分路線進(jìn)行了初步探索，對(duì)標(biāo)準(zhǔn)Feistel結(jié)構(gòu)下簡化版F函數(shù)為1輪AES的情況，給出了4、5輪截?cái)嗖罘致肪€，對(duì)應(yīng)差分路線的概率分別達(dá)到2–36、2–91。高級(jí)加密標(biāo)準(zhǔn)AES的安全性和效率等性能出眾，經(jīng)過了多年來的分析評(píng)估、應(yīng)用和研究，現(xiàn)今應(yīng)用十分廣泛，對(duì)于分組密碼算法的設(shè)計(jì)具有很強(qiáng)的參考價(jià)值和參照意義，它在不同密碼結(jié)構(gòu)中的混合應(yīng)用，對(duì)于AES本身和相關(guān)密碼算法，比如Simpira置換，其安全性、效率等性能的評(píng)估可以相互借鑒。此外，對(duì)于相關(guān)密碼算法的分析工作在數(shù)學(xué)本質(zhì)上是對(duì)有限域多項(xiàng)式系統(tǒng)的研究，也是一個(gè)數(shù)學(xué)困難問題。因此，這些安全性分析工作在理論和應(yīng)用方面都具有很重要的意義。