3D密碼的7輪子空間跡區(qū)分器

楊 陽 劉文豪 曾 光

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

1 引言

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

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

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

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

下面描述基于子空間跡的區(qū)分器—結(jié)構(gòu)區(qū)分器。

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

子空間跡分析方法在構(gòu)造區(qū)分器上有獨特的優(yōu)勢，往往可以找到輪數(shù)更長的區(qū)分器。本文將基于子空間的性質(zhì)，尋找3D密碼的7輪區(qū)分器。

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

2 初步準備

2.1 3D密碼算法

3D密碼算法的分組規(guī)模和密鑰規(guī)模都是512 bit，迭代輪數(shù)為22輪。分組狀態(tài)表示為64 Byte的形式，可視為4個子塊的聯(lián)結(jié)

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

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

行移位θ1, θ2。θ1是 對3D密碼的4個子塊做AES的行移位變換，θ2是將字節(jié)塊視為一個整體進行行移位。θ1將式(1)中的狀態(tài)矩陣變?yōu)?/p>

密鑰異或KeyAdd。將狀態(tài)矩陣與輪子密鑰對應(yīng)字節(jié)進行模2加運算。

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

2.2 3D密碼的子空間與傳播規(guī)律

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

本節(jié)研究3D密碼子空間的交集性質(zhì)，尋找交集為{0}的兩個子空間，構(gòu)造出區(qū)分優(yōu)勢最大的6輪3D密碼不可能差分區(qū)分器。文獻[10]介紹了一種將密鑰恢復(fù)攻擊轉(zhuǎn)化成區(qū)分器的技術(shù)，能把基于子空間跡區(qū)分器的攻擊變?yōu)樾聟^(qū)分器，從而延長區(qū)分器輪數(shù)。將這種技術(shù)應(yīng)用于3D密碼，首次構(gòu)造出3D密碼的7輪子空間跡不可能差分區(qū)分器。

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

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

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

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

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

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

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

根據(jù)2.2節(jié)給出的3D密碼子空間傳播規(guī)律及引理5得到一條3D密碼的子空間跡

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

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

下面計算該區(qū)分器所需數(shù)據(jù)量及時間復(fù)雜度。

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

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

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

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

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

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

4 3D密碼的結(jié)構(gòu)區(qū)分器

第3節(jié)研究了3D密碼子空間交集性質(zhì)，給出了3D密碼的7輪子空間跡不可能差分區(qū)分器，下面給出兼容、信息集、等價等概念的定義及相關(guān)定理，利用3 D 密碼子空間與S 層的可兼容性，得到“n倍”性質(zhì)并給出3D密碼的7輪區(qū)分器?，F(xiàn)有密碼的結(jié)構(gòu)區(qū)分器長度均不超過5輪，這是目前輪數(shù)最長的結(jié)構(gòu)區(qū)分器。

4.1 兼容、信息集與等價關(guān)系

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

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

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

K是輪密鑰加操作，將內(nèi)部狀態(tài)與輪密鑰異或。

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

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

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

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

4.2 3D密碼的7輪結(jié)構(gòu)區(qū)分器

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

5 結(jié)束語

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

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

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