楊 陽(yáng) 劉文豪 曾 光

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

1 引言

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

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

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

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

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

2017年文獻(xiàn)[12]利用子空間跡，找到了AES的新性質(zhì)——窮舉子空間Di的全部明文對(duì)，經(jīng)過(guò)5輪加密，將有固定倍數(shù)個(gè)密文對(duì)的差分屬于子空間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]對(duì)P-SPN結(jié)構(gòu)及Hades結(jié)構(gòu)進(jìn)行子空間跡分析并給出判斷線(xiàn)性層是否易受攻擊的工具。

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

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

2 初步準(zhǔn)備

2.1 3D密碼算法

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

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

非線(xiàn)性變換γ。使用AES的8 bit S盒。

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

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

密鑰擴(kuò)展算法與子空間跡分析無(wú)關(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è)子空間，構(gòu)造出區(qū)分優(yōu)勢(shì)最大的6輪3D密碼不可能差分區(qū)分器。文獻(xiàn)[10]介紹了一種將密鑰恢復(fù)攻擊轉(zhuǎn)化成區(qū)分器的技術(shù)，能把基于子空間跡區(qū)分器的攻擊變?yōu)樾聟^(qū)分器，從而延長(zhǎng)區(qū)分器輪數(shù)。將這種技術(shù)應(yīng)用于3D密碼，首次構(gòu)造出3D密碼的7輪子空間跡不可能差分區(qū)分器。

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

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

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

截?cái)嗖豢赡懿罘謪^(qū)分器從終點(diǎn)差分矩陣脫密到中間差分矩陣，再與起始差分加密得到的中間狀態(tài)產(chǎn)生矛盾。為延長(zhǎng)區(qū)分器，一般終點(diǎn)差分矩陣只有一個(gè)變量，例如3D密碼的6輪截?cái)嗖豢赡懿罘謪^(qū)分器[7]，其區(qū)分優(yōu)勢(shì)為 28/2512≈2?504，與3D密碼的6輪中間相遇區(qū)分器[8]區(qū)分優(yōu)勢(shì)相同。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

L是 QN上的一個(gè)F2- 線(xiàn)性雙射。Q→Q。

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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

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