Robin 算法一個新的不可能差分攻擊*

王佳琳 歐海文 施 瑞

1.西安電子科技大學，西安市 710071

2.北京電子科技學院，北京市 100070

1 引言

對稱密碼按照加解密機制不同可以分為分組密碼和流密碼[1]，本文研究分組密碼中的Robin 算法[2]。 對分組密碼算法的安全性分析主要包括以下三個方面[1]:一是使用數(shù)學知識和計算機工具分析，二是結合物理環(huán)境進行分析，三是研究算法在工作模式下的安全性。 其中從物理實現(xiàn)角度，對密碼算法通過載體芯片運行時捕獲的信息進行分析被稱為間接分析，又稱為側信道分析或旁路攻擊[3，4]。 基于抵抗側信道分析的考量，Grosso 等人[2]于2014 年在FSE(快速軟件加密)會議上設計了一類基于LS 設計的新的算法族。 該算法族采用比特切片設計，并給出了兩個具體的分組密碼算法。 其中一個就是采用SPN(Substitution Permutation Network)結構的對合分組密碼算法Robin 算法。 所謂對合是指其線性組件和非線性組件均是對合的，即加解密的結構一樣。

不可能差分分析由Knudsen 和Biham 分別獨立提出[5，6]，是差分密碼分析的一個變種。 與差分分析盡可能憑借高概率的差分特征[7]來恢復密鑰不同的是，不可能差分分析是利用概率為零的差分特征，逐漸按部分排除那些會導致概率為零的差分出現(xiàn)的候選密鑰，最后在剩下的密鑰值中用窮盡搜索的辦法可以恢復正確密鑰。

目前，Robin 算法的不可能差分攻擊結果主要有:2014 年，Grosso 等人在設計文檔中基于算法的比特模式，利用中間相錯技術構造了3 輪的不可能差分區(qū)分器。 該區(qū)分器主要是利用中間差分某一比特構造矛盾，該構造方法并未充分利用線性層的信息。 對Robin 算法的不可能差分攻擊由設計者在設計文檔中構造的3 輪不可能差分區(qū)分器進化為了現(xiàn)在的構造4 輪不可能差分區(qū)分器、實現(xiàn)共計6 輪的不可能差分攻擊，并經(jīng)歷了前人的兩次改良:一次是2018 年沈等人[8]將Robin 算法的比特模式等價轉換為字節(jié)模式，并利用線性層信息通過UID 方法[9]搜索到4 輪不可能差分區(qū)分器，達到了不考慮非線性層細節(jié)情況下的最優(yōu)長度；另一次是2021 年沈等人[10]對Robin 算法的4 輪不可能差分區(qū)分器充分挖掘輪密鑰的信息、降低輪密鑰的猜測量后的改進攻擊，能夠降低約28的時間復雜度，時間復雜度為大約293.97次6 輪加密運算、數(shù)據(jù)復雜度為2118.8。

根據(jù)沈等人在文獻[10]中的思路，結合王湘南等人[11]的方法，改變一個約束條件，手工推出并證明本文性質一。 根據(jù)性質一利用輪密鑰之間的線性關系構造新的區(qū)分器形式，降低了選擇明文數(shù)N，使得數(shù)據(jù)復雜度降低了大約28，時間復雜度有所上升。 利用提前拋棄技術[12]計算復雜度可知該攻擊時間復雜度為大約2118.21次6輪加密運算、數(shù)據(jù)復雜度為2111.18。

其余部分的結構安排如下:第2 節(jié)簡要介紹Robin 密碼的加密算法；第3 節(jié)證明性質一，并構造Robin 算法一條新的4 輪不可能差分區(qū)分器；第4 節(jié)根據(jù)新的4 輪不可能差分區(qū)分器，在其首尾各加一輪，攻擊6 輪的Robin 算法，并給出攻擊的完整步驟及復雜度分析；第5 節(jié)是結束語。

2 Robin 算法

2.1 Robin 算法簡介

Robin 算法是分組長度為128 比特的SPN型分組密碼，密鑰比特為128 比特，完整輪數(shù)為16 輪。 Robin 每一輪由3 個部件構成:

(1) 混淆層(Substitution Layer，SL). 由16個8×8 的S 盒并置組成，在本文中，S 盒只需要視為雙射即可，故S 盒的具體細節(jié)不給出，可參見文獻[2]。

(2) 擴散層(Diffusion Layer，DL). 擴散層置換是一個將128 比特輸入狀態(tài)看成16 字節(jié)，通過乘以16×16 的二元矩陣進行矩陣運算得到16 比特輸出狀態(tài)的線性函數(shù)，具體如下:(3) 輪密鑰加(Round Key Addition，RKA).由每一輪的輸入狀態(tài)和輪密鑰ki兩者之間異或構成，輪密鑰ki是通過密鑰擴展算法得到的。

2.2 符號說明

本文使用的符號及標注如表1 所示。

表1 符號說明

3 Robin 算法的4 輪不可能差分區(qū)分器

本文是對Robin 算法的6 輪不可能差分分析，首先根據(jù)性質一構造了新的4 輪不可能差分區(qū)分器，然后在區(qū)分器上添加1 輪前置路徑和1輪后置路徑，得到6 輪不可能差分攻擊路徑。

性質一:

如圖1 所示，存在一明文對，在第3 字節(jié)處差分值非零，其余字節(jié)處差分值為零，4 輪變換后，密文對差分特征ΔX4不會是如下形式: (0，f，0，g，f，0，g，0，g，0，f，0，h，0，0，0)。 這一不可能差分性質可用下式表示:

(0，0，0，0，0，0，0，0，0，0，b，0，0，0，0，0)?(0，f，0，g，f，0，g，0，g，0，f，0，h，0，0，0)

圖1 Robin 算法一個新的4 輪不可能差分區(qū)分器

其中f，g為任意非零值，f≠g且h＝f⊕g。

證明:

先從前兩輪正推。 明文對的輸入狀態(tài)滿足(0，0，0，0，0，0，0，0，0，0，b，0，0，0，0，0)， 經(jīng)過第一輪SL運算，差分特征變?yōu)? (0，0，0，0，0，0，0，0，0，0，c，0，0，0，0，0)。 其中，c為非零字節(jié)。

經(jīng)過第一輪DL運算，差分特征為: (c，c，0，0，c，c，0，0，0，0，0，0，c，c，0，c)， 經(jīng)過第一輪的RKA運算后，因RKA運算不改變差分，所以差分沒有發(fā)生改變。

再進行第二輪SL運算，第二輪的輸入差分可第一輪的輸出差分相同，SL運算后差分特征為: (d0，d1，0，0，d4，d5，0，0，0，0，0，0，d12，d13，0，d15)。 接下來進行第二輪的DL運算和RKA運算后，差分特征為: (e0，e1，e2，e3，e4，e5，e6，e7，e8，e9，e10，e11，e12，e13，e14，e15)。

其中有e2＝e8＝d0⊕d5⊕d13⊕d15。

再推導(0，f，0，g，f，0，g，0，g，0，f，0，h，0，0，0) 經(jīng)過兩輪逆變換的過程。

經(jīng)過第四輪DL－1運算和RKA－1運算，差分特征為:(0，h，0，0，h，0，0，0，0，0，h，0，f，0，g，0)。

經(jīng)過第四輪SL－1運算，差分特征為: (0，g1，0，0，g4，0，0，0，0，0，g10，0，g12，0，g14，0)。

再進行第三輪DL－1運算和RKA－1運算，差分特征為:

(f0，f1，f2，f3，f4，f5，f6，f7，f8，f9，f10，f11，f12，f13，f14，f15)。

其中f2＝0，f8＝g14，且g1，g4，g10，g12，g14為非0 值。

最后經(jīng)過第三輪SL－1運算后，差分特征為:

4 對Robin 算法的6 輪不可能差分攻擊過程

本節(jié)在第3 節(jié)已證明的4 輪不可能差分區(qū)分器上添加1 輪前置路徑和1 輪后置路徑，得到6 輪不可能差分攻擊路徑，如圖2 所示。 Robin的1 輪加密由SL、DL和RKA組成(在最后一輪中省略了DL)，SL、DL和RKA的每一次加密等于1/3 次1 輪加密。

圖2 6 輪Robin 算法一條新的不可能差分分析路徑

4.1 攻擊步驟

步驟1. 定義一個在字節(jié)(2，3，6，7，8，9，10，11，14)處差分為0，在其余字節(jié)(0，1，4，5，12，13，15)處取遍0～127 的明文空間結構，這樣的空間中含有28×(16－9)＝256個明文。 每個結構中明文對共有256× 256× 1/2＝2111個。

步驟2. 取2N個上述結構，選取密文對中在(0，2，5，7，9，10，13，14，15)這9 個字節(jié)處差分為0，剩余密文對有2N＋111× 2－8×9＝2N＋39個。

步驟3. 假設步驟2 中保留下來的密文對為(C，C′)，猜測密鑰k7的7B (k7，1，k7，3，k7，4，k7，6，k7，8，k7，10，k7，12)，在計算復雜度時，只需要計算7B 的值的復雜度。

步驟3.3. 猜測密鑰(k7，12)，計算:

步驟4. 猜測密鑰k1的7B，使保留下來的密文對相應的明文對為(P，P′)。

根據(jù)k1和k7的關系[10]，有k7，10＝k1，0＋k1，1＋k1，4＋k1，5＋k1，12＋k1，13＋k1，15。 由于k7，10在步驟3 中已經(jīng)猜過了，故可減少猜測任1B 的k1，i值，其中i＝0，1，4，5，12，13，15。

4.2 復雜度分析

下面在分析時間復雜度時采用了密鑰恢復的提前拋棄技術。

本節(jié)步驟3 中只需要計算7B 的值，所以這一步驟需要2× (2N＋39× 216＋2N＋31× 224)×3/16＋2×224×(2N＋23×216＋2N＋15×224)×3/16＋2×248×(2N＋7×28)×1/16 ≈2117.99次1 輪解密運算。

在步驟4 需要256× 2× (28× 2N－1＋216×2N－9＋…＋248× 2N－41)× 7/16＝21× 2N＋61≈2120.57次1 輪加密。

Robin 算法1 輪加密運算和1 輪解密運算的時間復雜度相當，所以恢復96 比特密鑰信息所需要的時間復雜度為:

(2117.99＋2120.57)×1/6 ≈2118.21次6 輪加密。

種子密鑰信息是128 比特，上述攻擊能夠恢復其中104 比特信息，剩下的24 比特密鑰信息可通過窮盡搜索得到。 因而總的時間復雜為度為:2118.21＋224≈2118.21。

綜合而言，6 輪的攻擊復雜度為: 256＋N＝256＋55.18≈2111.18數(shù)據(jù)復雜度和時間復雜度為大約2118.21次6 輪加密運算。

5 結束語

本文提出了一條新的4 輪不可能差分區(qū)分器，在第4 部分中根據(jù)Robin 算法的結構特征，在新的4 輪不可能差分區(qū)分器上添加了1 輪前置路徑和1 輪后置路徑，實現(xiàn)了6 輪Robin 算法的不可能差分攻擊。 此路徑下，該攻擊時間復雜度為大約2118.21次6 輪加密運算、數(shù)據(jù)復雜度為2111.18。 表2 列出了本文的攻擊結果并比較了以往相關文獻的數(shù)據(jù)結果。

表2 Robin 算法的不可能差分分析的安全性總結