3D密碼的7輪子空間跡區分器

楊 陽 劉文豪 曾 光

(信息工程大學密碼工程學院 鄭州 450000)

1 引言

2008年，Nakahara[1]在CANS2008上提出3D密碼。3D密碼可視為3維的AES算法，將 4 ×4的字節矩陣擴展為 4×4×4，分組長度和密鑰規模均為512 bit，共22輪。

3D密碼設計理念新穎，對它的安全性分析自提出起持續至今。2010年王美一等人[2]提出了9輪3D密碼的Square攻擊，唐學海等人[3]給出了9輪不可能差分攻擊，之后Nakahara[4]將不可能差分攻擊提升到10輪。2012年，蘇崇茂等人[5]構造出3D密碼的5輪中間相遇區分器，給出了10輪中間相遇攻擊，Koyama等人[6]于同年給出11輪3D密碼的截斷差分分析，成功率約為24%。2014年，謝作敏等人[7]給出了11輪3D密碼的不可能差分攻擊。2015年，任炯炯等人[8]給出了11輪3D密碼的中間相遇攻擊。2021年，Hou等人[9]利用3D密碼的6輪yoyo區分器，給出了實際可行的7輪3D密碼算法的密鑰恢復攻擊。

在關注對3D密碼的攻擊的同時，可以發現上述攻擊使用的區分器輪數均小于7輪。Square攻擊使用了5.25輪、6.25輪區分器，11輪3D密碼的不可能差分和中間相遇攻擊均構造出6輪區分器，且區分優勢均為 2?504，區分3D密碼與隨機函數所需數據量不低于 2252.5。7輪3D密碼的yoyo攻擊使用了6輪yoyo區分器。為突破現有的區分器輪數，本文研究子空間跡分析方法在3D密碼上的應用。

2016年，Grassi等人[10]提出了子空間跡的概念。子空間跡不強調子空間結構在輪函數下的不變性，而是表現了子空間結構在輪函數下變化的規律，進而利用具有一定規律的子空間跡建立區分器。自提出以來，子空間跡主要用于對AES,Midori等SPN密碼算法的分析[11]，利用該方法在構造區分器或進行密鑰恢復時，不需要S盒的具體信息。

下面描述基于子空間跡的區分器—結構區分器。

2017年文獻[12]利用子空間跡，找到了AES的新性質——窮舉子空間Di的全部明文對，經過5輪加密，將有固定倍數個密文對的差分屬于子空間MJ(子空間Di和MJ將在第3節中定義)。將這樣的“n倍”性質與明確子空間跡結合，構造出5輪AES子空間跡結構區分器。同年，Grassi[13]給出了基于AES結構區分器的混合差分攻擊。2019年Boura等人[14]給出了結構區分器的構造條件。2020年，Grassi等人[15]利用子空間跡給出9輪AES-128的選擇密鑰區分器。2021年，Grassi等人[16]對P-SPN結構及Hades結構進行子空間跡分析并給出判斷線性層是否易受攻擊的工具。

子空間跡分析方法在構造區分器上有獨特的優勢，往往可以找到輪數更長的區分器。本文將基于子空間的性質，尋找3D密碼的7輪區分器。

第2節介紹3D密碼算法，定義其子空間并研究子空間傳播規律；第3節證明了3D密碼兩個子空間交集為0，由此給出在選擇明文條件下，區分優勢最大的6輪3D密碼差分區分器，進一步給出首個7輪3D密碼的子空間跡不可能差分區分器；第4節介紹兼容、信息集、等價關系的定義及相關定理，說明了3D密碼特定子空間與S層的可兼容性，據此給出3D密碼的7輪結構區分器；第5節總結成果并提出開放性問題。

2 初步準備

2.1 3D密碼算法

3D密碼算法的分組規模和密鑰規模都是512 bit，迭代輪數為22輪。分組狀態表示為64 Byte的形式，可視為4個子塊的聯結

3D算法采用SPN結構，輪函數依次由非線性變換、行移位、列混合變換、密鑰異或這4個變換組成。具體介紹如下。

非線性變換γ。使用AES的8 bit S盒。

行移位θ1, θ2。θ1是 對3D密碼的4個子塊做AES的行移位變換，θ2是將字節塊視為一個整體進行行移位。θ1將式(1)中的狀態矩陣變為

密鑰異或KeyAdd。將狀態矩陣與輪子密鑰對應字節進行模2加運算。

密鑰擴展算法與子空間跡分析無關，在此不做介紹。記Ek和Ek′分別表示奇數輪和偶數輪加密函數，旨在突出兩種行移位變換，不區分圈子密鑰。使用Fkm表示m輪3D密碼加密函數。a加密一輪的結果為Fk(a)=π·θ·γ·KeyAdd(a)。為保證3D密碼算法加脫密相似性，算法在最后一輪省略列混合變換。

2.2 3D密碼的子空間與傳播規律

3 3D密碼的子空間跡不可能差分區分器

本節研究3D密碼子空間的交集性質，尋找交集為{0}的兩個子空間，構造出區分優勢最大的6輪3D密碼不可能差分區分器。文獻[10]介紹了一種將密鑰恢復攻擊轉化成區分器的技術，能把基于子空間跡區分器的攻擊變為新區分器，從而延長區分器輪數。將這種技術應用于3D密碼，首次構造出3D密碼的7輪子空間跡不可能差分區分器。

3.1 3D密碼子空間的交集性質及6輪子空間跡不可能差分區分器

研究子空間的交集性質對子空間跡分析有重要意義，根據跡端點的交集屬性，可以得到較長跡的可預測子空間屬性，原因是兩個子空間的交集經過密碼函數時，交集屬性被保持。而交集能夠降低子空間的維數，故精確地刻畫一個子空間是哪些子空間的交集，并以交集的形式進行傳播，能有效降低子空間經過密碼函數時增長的維數，從而尋找到更長的子空間跡。先定義兩個新的子空間。

結合引理2，得到3D密碼的一條6輪子空間跡不可能差分

截斷不可能差分區分器從終點差分矩陣脫密到中間差分矩陣，再與起始差分加密得到的中間狀態產生矛盾。為延長區分器，一般終點差分矩陣只有一個變量，例如3D密碼的6輪截斷不可能差分區分器[7]，其區分優勢為 28/2512≈2?504，與3D密碼的6輪中間相遇區分器[8]區分優勢相同。

而子空間跡不可能差分區分器在中間矛盾處，利用的是兩個子空間交集為{0}的性質，且后幾輪為明確子空間跡，維數保持不變，故終點子空間的差分變量更多。上面給出的3D密碼的6輪子空間跡不可能差分區分器的區分優勢為24×4×8/2512≈2?384，這是目前選擇明文條件下區分優勢最大的6輪3D密碼區分器。

注意到，上面的子空間跡不可能差分區分器與密碼規模、S盒和密鑰的具體信息無關，即對帶一個秘密S盒的3D密碼同樣有效。

3.2 3D密碼的7輪子空間跡不可能差分區分器

根據2.2節給出的3D密碼子空間傳播規律及引理5得到一條3D密碼的子空間跡

為計算區分器的數據復雜度，首先介紹“生日悖論”，尋找所需輸入明文的最小數目，以保證在隨機情形中以高概率產生碰撞。

給定d值和n個變量，其中至少兩個變量具有相同值的概率可以計算為

下面計算該區分器所需數據量及時間復雜度。

實驗數據表明，256次碰撞中有63.8%的概率得到正確密鑰對應的明文對。當函數為3D密碼時，修改該明文對第 0 Byte、第5 Byte以外的值并加密，不會得到碰撞。512次碰撞對應概率為87.8%。

以256次碰撞為區分界限，使用 2193.1個選擇明文，將以95%的概率得到256次碰撞，有63.8%的概率將7輪3D密碼與隨機函數區分開。故該3D密碼的7輪子空間跡不可能差分區分器的數據復雜度為2193.1個 選擇明文，成功率為9 5%×63.8%=60.6%。

最后給出3D密碼的7輪子空間跡不可能差分區分器的具體算法：

離線階段。建立表格T，存儲S(x)⊕02x·S(y)⊕S(z)⊕02x·S(w)=0全部解。

步驟1 隨機選擇明密對，檢測經逆列混合變換后的密文對差分是否屬于子空間(IDi, IDi, IDi, IDi)，其中i=0,1,2,3。 若無碰撞且已經使用2193.1個明密對，輸出1，否則返回步驟1；若產生碰撞，進入步驟2；

步驟2 排除明文對與表格T中的解異或后的密鑰值。若全部密鑰被排除，輸出0；否則，返回步驟1。

4 3D密碼的結構區分器

第3節研究了3D密碼子空間交集性質，給出了3D密碼的7輪子空間跡不可能差分區分器，下面給出兼容、信息集、等價等概念的定義及相關定理，利用3 D 密碼子空間與S 層的可兼容性，得到“n倍”性質并給出3D密碼的7輪區分器。現有密碼的結構區分器長度均不超過5輪，這是目前輪數最長的結構區分器。

4.1 兼容、信息集與等價關系

令d為S 盒操作在二元域F2上的擴張系數，Q=F2d，對于3D密碼，d=8。設SPN密碼作用于N個字，每個字的規模等于S盒的規模，則狀態矩陣和圈密鑰可表示為 QN上的向量，SPN密碼的圈函數為R=K ?L ?S。

S是字節代替層，對狀態矩陣中的比特塊做非線性變換，{f0, f1,..., fN?1}為 QN一組基。

L是 QN上的一個F2- 線性雙射。Q→Q。

K是輪密鑰加操作，將內部狀態與輪密鑰異或。

定義5(兼容)[14]設V是 QN的子空間，如果V存在一組基在{f0, f1,..., fN?1}上表示為塊對角矩陣時，則V與S兼容，并且稱這類基為V的兼容基。

根據兼容的定義，文獻[14]給出了信息集、等價關系的定義，并證明當存在與S層兼容的子空間時，密碼算法有“n倍”性質，可以構造結構區分器，進一步給出結構區分器的構造條件。

根據子空間 (Mi, Mj, Ms, Mt)與S層的可兼容性，結合定理1，容易得到引理6。證明思路是交換碰撞對的某幾列，得到等價消息對，結合定理1，等價消息對加密一輪差分相等，即仍然碰撞。

命題1說明當子空間V與S層兼容時，窮舉V一個陪集中全部明文對并加密，差分屬于同一子空間的密文對個數總是 2h?1的倍數，這種規律被稱為密碼算法的“n倍性質”。

4.2 3D密碼的7輪結構區分器

以碰撞數模 215的數值作為區分依據，定理2說明窮舉 (Di, Di, Di, Di)+a全部明文對，7輪3D密碼得到的碰撞數模 215為0，而隨機函數的碰撞數模 215為0的概率為2?15。區分成功的概率為1?2?15，大于99.99%，且利用的性質與密鑰無關。需要3·2128≈2129.6次查表操作，存儲復雜度為2128Byte。

5 結束語

本文對3D密碼進行子空間跡分析，研究子空間傳播規律，首先利用找到的3輪明確子空間跡，結合子空間的交集性質，構造了7輪3D密碼的子空間跡不可能差分區分器。然后利用與S層兼容的子空間，給出了3D密碼的7輪結構區分器，為基于子空間跡的攻擊提供了基礎。本文尋找子空間跡不可能差分區分器與結構區分器的方法，適用于任何SPN密碼。

在利用子空間跡分析3D密碼的過程中，發現其在尋找區分器上擁有優勢。首先，截斷不可能差分相比與子空間跡不可能差分，前者利用的中間相遇思想是從維數較小的終點差分矩陣脫密，在中間產生矛盾，因此區分優勢較小，而后者利用的矛盾是兩個子空間交集為{0}，脫密過程是一條明確子空間跡，維數保持不變，區分優勢往往更大。結構區分器的原理是當輸入子空間與S層兼容時，等價消息對經過一輪加密函數，差分為常數，這是SPN結構密碼的新性質，但對明確子空間跡依賴很強，例如AES只有5輪結構區分器，而3D密碼存在3輪明確子空間跡，故可以構造7輪結構區分器。

因此能否得到子空間跡區分器與明確子空間跡的關系，給出基于子空間跡攻擊的輪數的下界是有待解決的問題。