Saturnin 算法的不可能差分分析

蔣梓龍，金晨輝

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

0 引言

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

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

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

表1 經典分析方法對Saturnin 算法的攻擊結果

1 預備知識

1.1 符號表示

P：明文。

⊕：逐位異或。

Δx：x的差分值。

1.2 Saturnin 密碼簡介

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

圖14×4×4 個元胞算法的三維立方狀態

根據Saturnin 算法的三維立方狀態，本文定義了以下5 種立方狀態中的子集。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6)輪常數加AT。根據2 個輸入參數（加密輪數R和域分隔符D），生成2 個16 bit 字RC0和RC1，再由RC0和RC1生成輪常數Ti，在第i輪輸出前進行輪常數加變換。

Saturnin 算法的輪函數與輪號i有關。對第i輪加密，當imod2 ≡ 1時，輪函數為

當imod2 ≡ 0時，輪函數為

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

關于Saturnin 算法的完整詳細內容，可以通過查閱文獻[1]做進一步了解。

2 Saturnin 密碼的不可能差分區分器

為方便對差分路徑進行闡述，2.1 節將輪函數進行簡化，并給出狀態、頁、片和列的相關重量定義；2.2 節闡述Saturnin 算法3.5 輪不可能差分區分器的充分條件，并利用此充分條件構造了270.1個3.5 輪不可能差分區分器。

2.1 簡化輪和立方狀態重量

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

當imod2 ≡ 0時，輪函數為

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

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

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

2.23.5 輪不可能差分區分器的充分條件

基于中間相錯的思想，本節用性質1 刻畫Saturnin 算法3.5 輪不可能差分區分器的充分條件。

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

1)當st mod2 ≡ 1時，有

2)當st mod2 ≡ 0時，有

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

首先，因元胞替換和列混合變換不改變重量非0列的數量，故S?MC?S變換和對應的逆變換不會改變重量非0 頁的數量和非0 片的數量，即可得Wslice(m)=Wslice(S?MC ?S(m))；因頁行移位變換不改變重量非 0 頁的數量，即可得Wslice(m)=Wslice(SRs(m))。又因F1變換中只包含頁移位變換、元胞替換和列混合變換，故也不改變重量非0頁的數量，即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′)。

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

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

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

由性質1 可知，Saturnin 算法的不可能差分區分器與輸入和輸出差分的非0 頁數和非0 片數有關。以起始輪的輪號為奇數為例，統計Saturnin 算法3.5 輪截斷式不可能差分區分器數量。

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

在立方狀態中，存在一個差分非0 頁時，共有A1=×(216-1)≈ 218個差分模式χ(x)；存在2 個差分非0 頁時，共有A2=×(216-1)2≈234.6個差分模式χ(x)；存在 3 個差分非 0 頁時，共有A3=×(216-1)3≈250個差分模式χ(x)。由性質1中充分條件的限制，通過排列組合，可以得到3.5 輪截斷式不可能差分區分器個數分布，如表3所示。

表3 Saturnin算法截斷式不可能差分區分器個數分布

將表3 的數據求和可得，由性質1 構造的3.5 輪截斷式不可能差分區分器的個數約為270.1，設計報告[1]給出的兩條不可能差分區分器也在這270.1個區分器之中。

為便于直觀理解，令起始輪的輪號st 為奇數，輸入差分 Δi n的非0 頁數為3，輸出差分 Δout的非0 頁數為1。以上述輸入差分 Δi n、輸出差分 Δout為例，將性質1 構造的3.5 輪不可能差分區分器用圖4 展示，其中最左側的狀態代表第0 頁，從左至右的4 個狀態分別代表第0 頁至第3 頁。在列混合變換MC 兩側，存在對應兩列只有4 個差分非0 的元胞，這與列混合變換MC 的分支數為5 矛盾，故構成了截斷式不可能差分區分器。

圖4 Saturnin 算法的3.5 輪不可能差分區分器（起始輪號為奇數）

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

由性質1，令輸入差分只有3 個非0 頁，輸出差分均只有一個非0 頁，構造了四類從第3 輪到第5.5 輪的3.5 輪截斷式不可能差分區分器。為方便闡述，本節以頁行為單位，闡述區分器的截斷差分及擴展攻擊路徑中的截斷差分，并提出了頁行的3 個狀態：滿頁行狀態、空頁行狀態和單頁行狀態。滿頁行狀態指頁行的4 個元胞差分值均非0；空頁行狀態指頁行的4 個元胞差分值均為0；單頁行狀態指在頁行中，有且只有一個元胞差分值非0，其余3 個元胞的差分值為0，且要求在一個狀態中，單頁行狀態中差分值非0 的元胞都在同一片。

3.1 頁行視角和四類區分器

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

圖5 頁行視角的Saturnin 算法

本節由性質1 構造了從第3 輪至第5.5 輪的四類截斷式不可能差分區分器。區分器的四類輸入截斷差分：每類輸入差分各有4 個截斷差分，即第i類區分器的第i-1片上有3 列共12 元胞差分非0，其余元胞差分為0，有4 種情況；區分器的四類輸出截斷差分：第i類區分器在第i-1頁上共16 元胞差分非0，其余元胞差分為0。表4 展示了四類截斷式不可能差分區分器的具體截斷差分，其中的數字是4 個元胞差分值均非0 列的列號。表4中的任意輸入/輸出截斷差分組合，都可構成3.5 輪不可能差分區分器，故一共有64 個不可能差分區分器，每一類分別有16 個不可能差分區分器。

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

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

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

2)區分器的輸出差分有且只有一個非0 面。

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

為便于直觀理解，以第一個輸入截斷差分和第一個輸出截斷差分構成的不可能差分區分器為例，如圖6 所示，以頁行、元胞為單位，分別展示此不可能差分區分器樣例。圖6(a)是以頁行為單位的截斷差分示意，其中實心三角代表滿頁行狀態，空心三角代表單頁行狀態，且此單頁行狀態中差分非0的元胞均在第0 片；圖6(b)是以元胞為單位的截斷差分示意。

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

3.25.5 輪不可能差分攻擊方案

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

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

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

預處理階段。為降低子密鑰篩選階段的時間復雜度，本節先對攻擊過程中所需的計算存表，具體表的構造如下。

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

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

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

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

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

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

3.3 復雜度分析

預處理階段復雜度相較整體攻擊方案而言較少，可忽略不計。

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

密鑰篩選階段需要對四條攻擊路徑的復雜度進行分析。

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

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

下面分析經過第一條攻擊路徑篩選后，候選子密鑰的個數。

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

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

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

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

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

4 結束語

本文對Saturnin 算法進行不可能差分分析。首先，提出并證明了Saturnin 算法3.5 輪不可能差分區分器的充分條件，利用此條件可快速構造270.1個截斷式不可能差分區分器，從而為可以攻擊方案的設計提供更多的選擇。之后，構造了四類3.5 輪區分器，向前擴展2 輪得到了四條有相同的明文結構的攻擊路徑，利用這四條攻擊路徑，提出了Saturnin 算法的5.5輪不可能差分攻擊方案，數據、存儲和時間復雜度分別為2176.88個選擇明文、2143.88算法規模和2176.91次5.5 輪加密，這是目前可見的對Saturnin 算法的一種不可能差分攻擊方案。