Saturnin 算法的不可能差分分析

蔣梓龍，金晨輝

（信息工程大學(xué)密碼工程學(xué)院，河南 鄭州 450001）

0 引言

在NIST 輕量級密碼標(biāo)準(zhǔn)競賽中，Saturnin 算法[1]是進(jìn)入第二輪的候選算法之一。算法設(shè)計(jì)者聲稱該算法不僅適用于小型電子設(shè)備，并且可以作為哈希和認(rèn)證加密的基礎(chǔ)算法。該算法在保持高效輕巧的同時(shí)具有極高的安全性，甚至可以抵抗量子計(jì)算分析。作為一個(gè)輕量級可抗量子計(jì)算分析的新算法，Saturnin 算法的安全性更值得深入研究。

不可能差分攻擊[2-3]是差分攻擊的一種特殊變體。與傳統(tǒng)的差分攻擊利用高概率差分對應(yīng)完全相反，不可能差分攻擊利用不可能出現(xiàn)的差分對應(yīng)，即差分轉(zhuǎn)移概率為0 的差分對應(yīng)，來刻畫算法的不完全隨機(jī)性，并利用此信息泄露做區(qū)分攻擊或者密鑰恢復(fù)。關(guān)于不可能差分區(qū)分器的構(gòu)造問題一直都是熱點(diǎn)課題，在1999 年的FSE 會議上，Biham 等[2]詳細(xì)地闡述了運(yùn)用“中間相遇找矛盾”的方法構(gòu)造不可能差分。后來隨著自動搜索技術(shù)的出現(xiàn)，不可能差分區(qū)分器的構(gòu)造變得更加高效精細(xì)，例如，Kim 等[3]提出的U 方法；Luo等[4]提出U 方法的改進(jìn)版本，稱之為UID 方法；Wu等[5]提出的線性化方法；Mouha 等[6]將混合整數(shù)規(guī)劃（MILP，mixed integer linear programming）搜索用于差分分析。之后這類工具被廣泛用于各類分析方法[7-9]，不可能差分區(qū)分器搜索與構(gòu)造也是研究的熱點(diǎn)，Cui等[10]首次利用MILP 求解不可能差分區(qū)分器；Sasaki等[11]系統(tǒng)詳盡地闡述了如何利用MILP 方法搜索不可能差分；Hu 等[12]利用傳播狀態(tài)的特性，進(jìn)一步改進(jìn)了分析結(jié)果；張仕偉等[13]利用AND 組件特性，基于SAT求解器搜索到了更多的不可能差分區(qū)分器；Zhang等[14]提出了“模式運(yùn)算”方法，實(shí)現(xiàn)了ARX 密碼算法不可能差分區(qū)分器的自動化搜索。針對輕量級分組密碼算法，也有不少關(guān)于不可能差分的分析結(jié)果，如武小年等[15]給出了GRANULE 算法的7 輪不可能差分區(qū)分器和MANTRA 的9 輪不可能差分區(qū)分器；王旭姿等[16]在相關(guān)密鑰的條件下，首次給出了SIMON 算法的13輪不可能差分區(qū)分器。

Saturnin 是類AES 密碼算法，分組長度為256 bit，由64 個(gè)4 bit 元胞構(gòu)成。設(shè)計(jì)者聲稱針對AES 算法[17]的分析方法都可以用來分析Saturnin 算法，且Saturnin算法的安全性基礎(chǔ)也受益于AES 的安全性結(jié)果。在設(shè)計(jì)報(bào)告[1]的第6 節(jié)中，基于在單密鑰條件下的AES 安全性分析結(jié)果，設(shè)計(jì)者給出了Saturnin 算法抵抗經(jīng)典攻擊方法的安全性分析，包括差分攻擊、線性攻擊、代數(shù)攻擊、不可能差分、中間相遇等分析方法。在攻擊方案的安全性評估上，設(shè)計(jì)報(bào)告只給出了7.5 輪的中間相遇攻擊方案；之后Hou 等[18]提出了用Yoyo 方法分析Saturnin 算法的攻擊方案，但是Yoyo 需要自適應(yīng)的明密文選擇，分析方法所需要的條件較強(qiáng)。針對不可能差分，設(shè)計(jì)報(bào)告[1]中只給出了兩條3.5 輪的不可能差分區(qū)分器，設(shè)計(jì)者聲稱“我們提出的2 個(gè)不可能差分區(qū)分器得到的攻擊路徑都需要攻擊全部密鑰比特。我們認(rèn)為可能可以構(gòu)造出4 輪或4.5 輪的攻擊方案，但是至今我們也沒有達(dá)成這個(gè)目標(biāo)。”截至目前，只有設(shè)計(jì)報(bào)告[1]中給出了Saturnin 算法抵抗不可能差分的安全性分析，且設(shè)計(jì)者只給出了兩條3.5 輪的不可能差分區(qū)分器，并沒有給出完整的不可能差分攻擊方案。為彌補(bǔ)這個(gè)缺項(xiàng)，本文對Saturnin 算法進(jìn)行不可能差分分析，并提出了具體的5.5 輪不可能差分攻擊方案。首先，基于Saturnin 算法的結(jié)構(gòu)特性，本文提出并證明了3.5 輪不可能差分區(qū)分器的充分條件，即輸入差分和輸出差分非0 面（頁）的個(gè)數(shù)和小于或等于4。利用此充分條件，可以快速構(gòu)造270.1個(gè)不可能差分區(qū)分器，可以為攻擊方案的設(shè)計(jì)提供更多的選擇。之后，從構(gòu)造的270.1個(gè)區(qū)分器中，有針對性地挑選了64 個(gè)區(qū)分器并分成了四類。將這四類區(qū)分器向前擴(kuò)展2 輪各得一條攻擊路徑，這四條攻擊路徑不僅具有相同的明密文結(jié)構(gòu)，且具有大量的公共密鑰字節(jié)，利用這2 個(gè)特性可以改善攻擊方案的整體復(fù)雜度。基于上述的四條攻擊路徑，結(jié)合一系列分析技術(shù)，本文提出了對Saturnin算法的5.5 輪不可能差分攻擊方案。作為比較，設(shè)計(jì)者只構(gòu)造了兩條3.5 輪的不可能差分區(qū)分器，認(rèn)為可能可以設(shè)計(jì)出4 輪或4.5 輪的不可能差分攻擊方案，但他們也沒有設(shè)計(jì)出相應(yīng)的攻擊方案。表1 總結(jié)了經(jīng)典分析方法對Saturnin 算法的攻擊結(jié)果。

表1 經(jīng)典分析方法對Saturnin 算法的攻擊結(jié)果

1 預(yù)備知識

1.1 符號表示

P：明文。

⊕：逐位異或。

Δx：x的差分值。

1.2 Saturnin 密碼簡介

Saturnin 算法是一個(gè)SPN 結(jié)構(gòu)密碼算法。算法的主密鑰和中間狀態(tài)都為256 bit，可以將主密鑰和操作中間狀態(tài)看作4 ×4 ×4個(gè)元胞的立方體，其中元胞代表一個(gè)4 bit 值。4 ×4 ×4個(gè)元胞的三維立方狀態(tài)如圖1 所示，立方狀態(tài)中的元胞可以由三維坐標(biāo)(x，y，z)表示位置，其中x，y，z∈{0，1，2，3}，對應(yīng)的元胞號為(y+4x+16z)，元胞號為0～63，0 為最低有效位。舉例而言，第33 號元胞的坐標(biāo)為(0，1，2)。

圖14×4×4 個(gè)元胞算法的三維立方狀態(tài)

根據(jù)Saturnin 算法的三維立方狀態(tài)，本文定義了以下5 種立方狀態(tài)中的子集。

1)頁：在立方狀態(tài)中，當(dāng)z坐標(biāo)值為固定值，x，y坐標(biāo)值遍歷，對應(yīng)得到的16 個(gè)元胞集合為一頁，記作第z頁，符號表示為slice(z)。

2)片：在立方狀態(tài)中，當(dāng)x坐標(biāo)值為固定值，y，z坐標(biāo)值遍歷，對應(yīng)得到的16 個(gè)元胞集合為一片，記作第x片，符號表示為sheet(x)。

3)列：在立方狀態(tài)中，當(dāng)x，z坐標(biāo)值都為固定值，y坐標(biāo)值遍歷，對應(yīng)得到的4 個(gè)元胞集合為一列，記作第x+4z列，符號表示為column(x+4z)。

4)頁行：在立方狀態(tài)中，當(dāng)y，z坐標(biāo)值都為固定值，x坐標(biāo)值遍歷，對應(yīng)得到的4 個(gè)元胞集合為一個(gè)頁行，記作第y+4z頁行，符號表示為xrow(y+4z)。

5)片行：在立方狀態(tài)中，當(dāng)x，y坐標(biāo)值都為固定值，z坐標(biāo)值遍歷，對應(yīng)得到的4 個(gè)元胞集合為一個(gè)片行，記作第y+4x片行，符號表示為zrow(y+4x)。

Saturnin 算法的設(shè)計(jì)者提出了合并輪[1]的概念。為方便闡述，本文中的一輪均指一個(gè)合并輪，加密算法的輪數(shù)從1 開始計(jì)數(shù)。用戶可以輸入2 個(gè)參數(shù)，分別為加密輪數(shù)R∈{10，…，31}和4 bit 的域分隔符D。算法默認(rèn)加密10 輪，用戶也可以在{10，…，31}中任選加密輪數(shù)。算法輪函數(shù)共包括6 種變換，分別為元胞替換S、頁行移位變換SRs、片行移位變換SRt、列混合變換MC、輪子密鑰加AK和輪常數(shù)加AT。這6 種變換簡述如下。

1)元胞替換S。對立方狀態(tài)中的全部64 個(gè)元胞做查S 盒的非線性變換。此變換由兩類4 bit 的S盒構(gòu)成，分別記作S0、S1，對元胞號為偶數(shù)的元胞查S0盒，對元胞號為奇數(shù)的元胞查S1盒。S0和S1如表2 所示。

表2 Saturnin 算法的兩類4 bit 的S 盒

2)頁行移位SRs。根據(jù)y坐標(biāo)值進(jìn)行頁行循環(huán)移位操作，即在第y行按x坐標(biāo)方向循環(huán)移位y元胞(y=0，1，2，3)，為SRs的逆變換。以第0 頁為例，具體變換如圖2 所示。

圖2 Saturnin 算法的頁行移位樣例

3)片行移位SRt。根據(jù)y坐標(biāo)值進(jìn)行片行循環(huán)移位操作，即在第y行按z坐標(biāo)方向循環(huán)移位y元胞(y=0，1，2，3)，為SRt的逆變換。以第0 片為例，具體變換如圖3 所示。

圖3 Saturnin 算法的片行移位樣例

4)列混合變換MC。對立方狀態(tài)中的全部十六列做左乘變換M。

其中，α作用于4 bit 元胞。

5)輪子密鑰加AK。在每輪輸出前進(jìn)行輪子密鑰加變換。記主密鑰為64 元胞K0=(k0，…，k63)，對第i輪加密，若imod2=1，則用主密鑰進(jìn)行輪子密鑰加變換；若imod 2=0，則將K0循環(huán)左移20 元胞，即用密鑰K1=(k20，…，k63，k0，…，k19)進(jìn)行輪子密鑰加變換。算法開始時(shí)以K0為白化密鑰，先對明文進(jìn)行一次密鑰加變換。

6)輪常數(shù)加AT。根據(jù)2 個(gè)輸入?yún)?shù)（加密輪數(shù)R和域分隔符D），生成2 個(gè)16 bit 字RC0和RC1，再由RC0和RC1生成輪常數(shù)Ti，在第i輪輸出前進(jìn)行輪常數(shù)加變換。

Saturnin 算法的輪函數(shù)與輪號i有關(guān)。對第i輪加密，當(dāng)imod2 ≡ 1時(shí)，輪函數(shù)為

當(dāng)imod2 ≡ 0時(shí)，輪函數(shù)為

注意，白化密鑰采用主密鑰K0，需要先用K0與明文P做密鑰加變換，即第一輪的輸入為m0=P⊕K0，再調(diào)用輪函數(shù)進(jìn)行加密。

關(guān)于Saturnin 算法的完整詳細(xì)內(nèi)容，可以通過查閱文獻(xiàn)[1]做進(jìn)一步了解。

2 Saturnin 密碼的不可能差分區(qū)分器

為方便對差分路徑進(jìn)行闡述，2.1 節(jié)將輪函數(shù)進(jìn)行簡化，并給出狀態(tài)、頁、片和列的相關(guān)重量定義；2.2 節(jié)闡述Saturnin 算法3.5 輪不可能差分區(qū)分器的充分條件，并利用此充分條件構(gòu)造了270.1個(gè)3.5 輪不可能差分區(qū)分器。

2.1 簡化輪和立方狀態(tài)重量

在單密鑰且單常數(shù)的條件下，異或加不影響差分值。在忽略輪子密鑰加和輪常數(shù)加變換的情況下，簡化的輪函數(shù)也與輪數(shù)i(i＞ 0)有關(guān)。當(dāng)imod2 ≡ 1時(shí)，輪函數(shù)為

當(dāng)imod2 ≡ 0時(shí)，輪函數(shù)為

當(dāng)輪號為奇數(shù)時(shí)，記簡化輪函數(shù)為F1(m)；當(dāng)輪號為偶數(shù)時(shí)，記簡化輪函數(shù)為F0(m)。記F(st，r)(m)為從第st 輪開始加密r次簡化輪，F(xiàn)-(st，r)(m)為從第st 輪開始脫密r次簡化輪，其中st，r∈ {1，…，31}。例如，算法默認(rèn)的10 次簡化輪加密記為F(1，10)(m)=(F0?F1(m))5。

由1.2 節(jié)可知，Saturnin 算法的立方狀態(tài)m有4 個(gè)頁、4 個(gè)片和16 個(gè)列，每個(gè)頁、每個(gè)片分別有16元胞，每個(gè)列有4 元胞。對立方狀態(tài)、頁、片和列而言，元胞重量指包含的非0 元胞個(gè)數(shù)，元胞重量的符號定義為Wnibble。例如，Wnibble(mslice(0))=3表示在立方狀態(tài)m的第0 頁中有3 個(gè)非0 元胞。

若頁、片、列的全部元胞值都為0，則元胞重量為0；反之元胞重量非0。對一個(gè)立方狀態(tài)m而言，Wslice、Wsheet、Wcolumn分別表示在一個(gè)立方狀態(tài)中重量非 0 的頁、片、列的數(shù)量。例如，Wslice(m)=3表示在立方狀態(tài)m中，重量非0 的頁有3 個(gè)；Wcolumn(mslice(0))=3表示在立方狀態(tài)m的第0頁中，重量非0 的列有3 個(gè)。

2.23.5 輪不可能差分區(qū)分器的充分條件

基于中間相錯(cuò)的思想，本節(jié)用性質(zhì)1 刻畫Saturnin 算法3.5 輪不可能差分區(qū)分器的充分條件。

性質(zhì)1在Saturnin 算法中，記輸入差分為Δi n，經(jīng)過3.5 輪加密后輸出差分為 Δout。0.5 輪加密變換為在3 輪加密后再進(jìn)行S?MC?S變換。根據(jù)起始輪輪號st 的不同，可得如下2 個(gè)3.5 輪不可能差分區(qū)分器的充分條件。

1)當(dāng)st mod2 ≡ 1時(shí)，有

2)當(dāng)st mod2 ≡ 0時(shí)，有

證明以 1)為例，證明充分性，已知Wslice(Δi n)+Wslice(Δout)≤4。

首先，因元胞替換和列混合變換不改變重量非0列的數(shù)量，故S?MC?S變換和對應(yīng)的逆變換不會改變重量非0 頁的數(shù)量和非0 片的數(shù)量，即可得Wslice(m)=Wslice(S?MC ?S(m))；因頁行移位變換不改變重量非 0 頁的數(shù)量，即可得Wslice(m)=Wslice(SRs(m))。又因F1變換中只包含頁移位變換、元胞替換和列混合變換，故也不改變重量非0頁的數(shù)量，即Wslice(m)=Wslice(F1(m))。則由上述分析可得，對?Δ in′=S?MC?S?F1(Δin)，都有Wslice(Δin)=Wslice(Δin′)；對?Δout′=?S-1?MC-1?S-1(Δout)，都有Wslice(Δout)=Wslice(Δout′)。

其次，因?yàn)棣ut是由Δin經(jīng)過變換S?MC ?S?F1?F0?F1得到的。則可以推得在2 個(gè)立方狀態(tài) Δi n′=SRt(Δi n′)、Δ out′=SRt(Δout′)之間還存在一個(gè)列混合變換MC。

已知Wslice(Δ in)+Wslice(Δout)≤4，則由上述分析可得Wslice(Δi n′)+Wslice(Δ out′)≤4，即在2 個(gè)立方狀態(tài) Δi n′、Δout′中，至多存在4 個(gè)重量非0 頁，則可得在2 個(gè)立方狀態(tài) Δi n′、Δout′中，同一片號i∈{0，1，2，3}下的兩片 Δi n′(sheeti)、Δout′(sheeti)至多有4 個(gè)重量非0 列，不妨設(shè)為第0 片，則可得Wcolumn(sheet0)+Wcolumn(sheet0)≤4。對這兩片Δin′(sheet0)、Δout′(sheet0)進(jìn)行片移位變換SRt，可得 Δi n′′和Δout′第0 列的非0 元胞數(shù)最多為4 個(gè)，即W(Δin′column(0))+W(Δout′column(0))≤4，但這與列混合變換MC 的分支數(shù)為 5 矛盾，故Δi n3.5-roundΔout 成立。

性質(zhì)1中2)部分的證明與上述類似。證畢。

由性質(zhì)1 可知，Saturnin 算法的不可能差分區(qū)分器與輸入和輸出差分的非0 頁數(shù)和非0 片數(shù)有關(guān)。以起始輪的輪號為奇數(shù)為例，統(tǒng)計(jì)Saturnin 算法3.5 輪截?cái)嗍讲豢赡懿罘謪^(qū)分器數(shù)量。

設(shè)x=(x0，…，x63)∈GF(24)64為Saturnin 算法的立方狀態(tài)，令θ為GF(24)→GF(2)的映射，當(dāng)xi=0時(shí)，有θ(xi)=0；當(dāng)xi≠ 0時(shí)，有θ(xi)=1。則稱χ(x)=χ(x0，…，x63)=(θ(x0)，…，θ(x63))為x的模式。

在立方狀態(tài)中，存在一個(gè)差分非0 頁時(shí)，共有A1=×(216-1)≈ 218個(gè)差分模式χ(x)；存在2 個(gè)差分非0 頁時(shí)，共有A2=×(216-1)2≈234.6個(gè)差分模式χ(x)；存在 3 個(gè)差分非 0 頁時(shí)，共有A3=×(216-1)3≈250個(gè)差分模式χ(x)。由性質(zhì)1中充分條件的限制，通過排列組合，可以得到3.5 輪截?cái)嗍讲豢赡懿罘謪^(qū)分器個(gè)數(shù)分布，如表3所示。

表3 Saturnin算法截?cái)嗍讲豢赡懿罘謪^(qū)分器個(gè)數(shù)分布

將表3 的數(shù)據(jù)求和可得，由性質(zhì)1 構(gòu)造的3.5 輪截?cái)嗍讲豢赡懿罘謪^(qū)分器的個(gè)數(shù)約為270.1，設(shè)計(jì)報(bào)告[1]給出的兩條不可能差分區(qū)分器也在這270.1個(gè)區(qū)分器之中。

為便于直觀理解，令起始輪的輪號st 為奇數(shù)，輸入差分 Δi n的非0 頁數(shù)為3，輸出差分 Δout的非0 頁數(shù)為1。以上述輸入差分 Δi n、輸出差分 Δout為例，將性質(zhì)1 構(gòu)造的3.5 輪不可能差分區(qū)分器用圖4 展示，其中最左側(cè)的狀態(tài)代表第0 頁，從左至右的4 個(gè)狀態(tài)分別代表第0 頁至第3 頁。在列混合變換MC 兩側(cè)，存在對應(yīng)兩列只有4 個(gè)差分非0 的元胞，這與列混合變換MC 的分支數(shù)為5 矛盾，故構(gòu)成了截?cái)嗍讲豢赡懿罘謪^(qū)分器。

圖4 Saturnin 算法的3.5 輪不可能差分區(qū)分器（起始輪號為奇數(shù)）

3 Saturnin 密碼的5.5 輪不可能差分攻擊

由性質(zhì)1，令輸入差分只有3 個(gè)非0 頁，輸出差分均只有一個(gè)非0 頁，構(gòu)造了四類從第3 輪到第5.5 輪的3.5 輪截?cái)嗍讲豢赡懿罘謪^(qū)分器。為方便闡述，本節(jié)以頁行為單位，闡述區(qū)分器的截?cái)嗖罘旨皵U(kuò)展攻擊路徑中的截?cái)嗖罘郑⑻岢隽隧撔械? 個(gè)狀態(tài)：滿頁行狀態(tài)、空頁行狀態(tài)和單頁行狀態(tài)。滿頁行狀態(tài)指頁行的4 個(gè)元胞差分值均非0；空頁行狀態(tài)指頁行的4 個(gè)元胞差分值均為0；單頁行狀態(tài)指在頁行中，有且只有一個(gè)元胞差分值非0，其余3 個(gè)元胞的差分值為0，且要求在一個(gè)狀態(tài)中，單頁行狀態(tài)中差分值非0 的元胞都在同一片。

3.1 頁行視角和四類區(qū)分器

由2.2 節(jié)可知，頁行定義以頁行為單位，則可以將Saturnin 算法看作由16 個(gè)頁行組成。圖5 展示了頁行視角的Saturnin 算法狀態(tài)，其中數(shù)字為頁行號，從右至左分別代表第0 頁至第3 頁。

圖5 頁行視角的Saturnin 算法

本節(jié)由性質(zhì)1 構(gòu)造了從第3 輪至第5.5 輪的四類截?cái)嗍讲豢赡懿罘謪^(qū)分器。區(qū)分器的四類輸入截?cái)嗖罘郑好款愝斎氩罘指饔? 個(gè)截?cái)嗖罘郑吹趇類區(qū)分器的第i-1片上有3 列共12 元胞差分非0，其余元胞差分為0，有4 種情況；區(qū)分器的四類輸出截?cái)嗖罘郑旱趇類區(qū)分器在第i-1頁上共16 元胞差分非0，其余元胞差分為0。表4 展示了四類截?cái)嗍讲豢赡懿罘謪^(qū)分器的具體截?cái)嗖罘郑渲械臄?shù)字是4 個(gè)元胞差分值均非0 列的列號。表4中的任意輸入/輸出截?cái)嗖罘纸M合，都可構(gòu)成3.5 輪不可能差分區(qū)分器，故一共有64 個(gè)不可能差分區(qū)分器，每一類分別有16 個(gè)不可能差分區(qū)分器。

設(shè)計(jì)者指出，他們提出的2 個(gè)不可能差分區(qū)分器，即使是擴(kuò)展1 輪或0.5 輪，得到的攻擊路徑都需要攻擊全部密鑰比特，故設(shè)計(jì)者沒有構(gòu)造出相應(yīng)的不可能差分攻擊方案。為使構(gòu)造的區(qū)分器能夠適用于不可能差分攻擊，本文特意選取了表4中的64 個(gè)區(qū)分器，這64 個(gè)區(qū)分器滿足以下2 個(gè)特性。

表4 Saturnin 算法的四類3.5 輪不可能差分區(qū)分器

1)區(qū)分器輸入差分有3 個(gè)非0 面，且在這3 個(gè)非0 面中，都有且只有一個(gè)非0 列；同時(shí)，這3 個(gè)非0 列都在一個(gè)頁上。

2)區(qū)分器的輸出差分有且只有一個(gè)非0 面。

將上述的64 個(gè)區(qū)分器分為四類，根據(jù)特性1)和Saturnin 算法的具體結(jié)構(gòu)，構(gòu)造了四條5.5 輪的不可能差分攻擊路徑，每條攻擊路徑都不需要攻擊全部密鑰比特。同時(shí)，本文仔細(xì)考慮了密鑰生成算法，進(jìn)一步減少了這四條攻擊路徑所需要攻擊的密鑰比特。

為便于直觀理解，以第一個(gè)輸入截?cái)嗖罘趾偷谝粋€(gè)輸出截?cái)嗖罘謽?gòu)成的不可能差分區(qū)分器為例，如圖6 所示，以頁行、元胞為單位，分別展示此不可能差分區(qū)分器樣例。圖6(a)是以頁行為單位的截?cái)嗖罘质疽猓渲袑?shí)心三角代表滿頁行狀態(tài)，空心三角代表單頁行狀態(tài)，且此單頁行狀態(tài)中差分非0的元胞均在第0 片；圖6(b)是以元胞為單位的截?cái)嗖罘质疽狻?/p>

圖6 Saturnin 算法的3.5 輪不可能差分區(qū)分器樣例

3.25.5 輪不可能差分攻擊方案

基于3.1 節(jié)中的四類不可能差分區(qū)分器，只向前擴(kuò)展2 輪，得到了四條5.5 輪的不可能差分攻擊路徑。由第i類區(qū)分器擴(kuò)展的攻擊路徑記作第i條攻擊路徑，以圖6中的第一類不可能差分區(qū)分器為例構(gòu)造第一條攻擊路徑樣例，利用圖7 展示Saturnin算法的5.5 輪不可能差分攻擊路徑樣例，其中，變換S?MC?S簡記為MS，第一輪的子密鑰加和常數(shù)加一起記為AKT1。在設(shè)計(jì)攻擊方案時(shí)，先使用三條攻擊路徑只需要攻擊9 列子密鑰，第四條路徑需要攻擊10 列子密鑰，即先使用需要攻擊密鑰較少的攻擊路徑，再利用攻擊路徑中的公共密鑰信息，這樣可以進(jìn)一步改善攻擊方案的整體復(fù)雜度。

圖7 Saturnin 算法的5.5 輪不可能差分攻擊路徑樣例

本節(jié)將變換S?MC?S整體看作一個(gè)非線性變換，即將其看作一列16 bit 的大S 盒，用16 個(gè)大S 盒并置構(gòu)成了此非線性變換。攻擊方案的攻擊步驟包括預(yù)處理階段、數(shù)據(jù)處理階段和密鑰篩選階段3 個(gè)部分。

預(yù)處理階段。為降低子密鑰篩選階段的時(shí)間復(fù)雜度，本節(jié)先對攻擊過程中所需的計(jì)算存表，具體表的構(gòu)造如下。

表Λ。對Saturnin 算法的16 bit 大S 盒，在給定非0 輸入差分 Δin和非0 輸出差分 Δout時(shí)，方程S(x)⊕S(x⊕Δin)=Δout平均可以求得一個(gè)解，構(gòu)造表Λ 的索引為 (216-1)2個(gè)非0 差分(Δin，Δout)，每個(gè)(Δin，Δout)存儲對應(yīng)的方程解和對應(yīng)大S 盒的輸出(x，S(x))。

表Hi。對第i條攻擊路徑，在第一輪變換后，只有第i-1列和第i+3列中的8 個(gè)元胞差分非0，其余元胞差分均為0，共有 232個(gè)差分值對這 232個(gè)差分值做?MC ?SRs變換得到 232個(gè)差分值，將這 232個(gè)差分值存入對應(yīng)的表Hi。

數(shù)據(jù)處理階段。在明文的(8，9，10，11，12，13，14，15)這8 個(gè)頁行位置取固定值，遍歷其他8 個(gè)頁行，可以得到 2128個(gè)明文，將其稱之為一個(gè)明文結(jié)構(gòu)。對每個(gè)明文結(jié)構(gòu)下的 2128個(gè)明文，用快速排序技術(shù)[19]對明文做四次排序，即分別以密文的4 個(gè)頁行(0，1，2，3)、(4，5，6，7)、(8，9，10，11)和(12，13，14，15)為指標(biāo)排序，一共可以得到4 ×2128×(2128-1)÷2 ×2-192≈265個(gè)符合此攻擊路徑的明文對，將其存入表Ω中。本節(jié)選取個(gè)明文結(jié)構(gòu)，故攻擊方案中共有個(gè)明文對，可在四條攻擊路徑中重復(fù)使用。

密鑰篩選階段。為方便理解，本節(jié)以列為單位敘述密鑰，如四條攻擊路徑中，所需要攻擊的白化密鑰K0為第0 列至第7 列密鑰，記作K0，col(0，…，7)。四條攻擊路徑中所需攻擊的第一輪子密鑰K1分別為K1，col(0，4)、K1，col(1，5)、K1，col(2，6)和K1，col(3，7)，由Saturnin 算法的子密鑰生成算法可知，其對應(yīng)的主密鑰分別為K0，col(5，9)、K0，col(6，10)、K0，col(7，11)和K0，col(8，12)，可以看出，除了第四條攻擊路徑，其余三條攻擊路徑中都有一列密鑰與白化密鑰相同，故前三條攻擊路徑中，只需要攻擊9 列子密鑰，共 2144bit子密鑰。攻擊方案按攻擊路徑的序號順序進(jìn)行子密鑰篩選。以第一條攻擊路徑為例，用全部個(gè)明密對查表 H1得到密鑰K0，再用K1部分加密看是否能得到區(qū)分器輸入差分，若得到，則為錯(cuò)誤密鑰排除。若在子密鑰K0，col(0，…，7)固定的情況下，全部216個(gè)第9 列子密鑰K0，col(9)均為錯(cuò)誤密鑰，則當(dāng)前子密鑰K0，col(0，…，7)為錯(cuò)誤密鑰，予以排除，在后續(xù)的攻擊路徑中不需要再次檢測子密鑰K0，col(0，…，7)，從而改進(jìn)了此階段的時(shí)間復(fù)雜度。經(jīng)過全部四條攻擊路徑的篩選后，剩余的候選密鑰用加密驗(yàn)證排除錯(cuò)誤密鑰，直至恢復(fù)出正確主密鑰。為方便闡述，?MC ?SRs簡記為MR，密鑰篩選階段的具體步驟如下。將變換

步驟3由第二、三和四條攻擊路徑，利用對應(yīng)的表Hi，進(jìn)行與上述兩步類似的篩選。在四條攻擊路徑都篩選完畢后，最后可以得到13 列中的候選密鑰K0，col(0，…，12)。

步驟4窮舉剩余的3 列子密鑰K0，col(13，…，15)，即得到了全部主密鑰，進(jìn)行加密驗(yàn)證，直至得到最后的正確主密鑰。

3.3 復(fù)雜度分析

預(yù)處理階段復(fù)雜度相較整體攻擊方案而言較少，可忽略不計(jì)。

數(shù)據(jù)處理階段主要為明文加密得到密文的時(shí)間，故數(shù)據(jù)處理階段的時(shí)間復(fù)雜度為次5.5輪加密。明文對只存儲前兩頁的值，故所需的存儲復(fù)雜度為算法規(guī)模。

密鑰篩選階段需要對四條攻擊路徑的復(fù)雜度進(jìn)行分析。

第一條攻擊路徑篩選子密鑰的復(fù)雜度分析如下。

第二步只需要在一片上進(jìn)行部分加密計(jì)算，故認(rèn)為其為0.25 輪加密。則第二步所需的時(shí)間復(fù)雜度為2128×2Ns-31×216÷(5.5 ×4)=次5.5 輪加密。由上述分析可知，對一條攻擊路徑而言，時(shí)間復(fù)雜度主要耗時(shí)在第二步。

下面分析經(jīng)過第一條攻擊路徑篩選后，候選子密鑰的個(gè)數(shù)。

由一條攻擊路徑可知，一個(gè)錯(cuò)誤子密鑰不通過一個(gè)有效明文對的檢測概率是2-110，則一個(gè)錯(cuò)誤子密鑰通過一條攻擊路徑的檢測概率是pL=。在第一條攻擊路徑中，經(jīng)過個(gè)有效明文對的檢測后，可得候選密鑰的個(gè)數(shù)為2144×pL。

第一條攻擊路徑共涉及9 列密鑰K0，col(0，…，7，9)。經(jīng)過第一步的篩選，平均每個(gè)密鑰K0，col(0，…，7)可以存儲個(gè)中間狀態(tài)對。在固定8 列密鑰密鑰K0，col(0，…，7)的條件下，K0，col(9)通過第一條攻擊路徑的檢測概率為，則全部216個(gè)K0，col(9)都沒有通過第一條攻擊路徑的檢測概率為，Pk也是當(dāng)前固定密鑰K0，col(0，…，7)是錯(cuò)誤子密鑰的概率，故經(jīng)過第一條攻擊路徑篩選后K0，col(0，…，7)的候選密鑰的個(gè)數(shù)為 2128×(1-Pk)。

后三條攻擊路徑篩選子密鑰的復(fù)雜度分析如下。

第一步均與第一條攻擊路徑的第一步相同。在第二步中，只需要攻擊7 列白化密鑰K0，col(0，…，7)中的候選密鑰，故第二條攻擊路徑所需的時(shí)間復(fù)雜度為×(1-Pk)次5.5 輪加密；第三條攻擊路徑所需的時(shí)間復(fù)雜度為×(1-Pk)2次5.5 輪加密。由于第四條攻擊路徑在第二步需多攻擊一列子密鑰，因此第四條攻擊路徑所需的時(shí)間復(fù)雜度為×(1-Pk)3次5.5 輪加密。

加密驗(yàn)證階段，即第四步，經(jīng)過四條攻擊路徑的檢測后，通過的候選子密鑰個(gè)數(shù)為Nk=(2208-1)×(pL)4，需窮舉 248子密鑰K0，col(13，…，15)，故所需的時(shí)間復(fù)雜度為 248×Nk次5.5 輪加密。

4 結(jié)束語

本文對Saturnin 算法進(jìn)行不可能差分分析。首先，提出并證明了Saturnin 算法3.5 輪不可能差分區(qū)分器的充分條件，利用此條件可快速構(gòu)造270.1個(gè)截?cái)嗍讲豢赡懿罘謪^(qū)分器，從而為可以攻擊方案的設(shè)計(jì)提供更多的選擇。之后，構(gòu)造了四類3.5 輪區(qū)分器，向前擴(kuò)展2 輪得到了四條有相同的明文結(jié)構(gòu)的攻擊路徑，利用這四條攻擊路徑，提出了Saturnin 算法的5.5輪不可能差分攻擊方案，數(shù)據(jù)、存儲和時(shí)間復(fù)雜度分別為2176.88個(gè)選擇明文、2143.88算法規(guī)模和2176.91次5.5 輪加密，這是目前可見的對Saturnin 算法的一種不可能差分攻擊方案。