一般SPT模型的抗差分和線性攻擊安全性研究

劉鳳梅，陳連俊，李春祥，李艷梅，張國(guó)雙

（信息保障技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100072）

1 引言

差分攻擊和線性攻擊是對(duì)分組密碼最有效的2種攻擊方法，研究和評(píng)估密碼算法抵抗差分攻擊和線性攻擊的能力，是密碼設(shè)計(jì)者和分析者必須考慮的問(wèn)題[1~3]。SPS模型（如圖1和圖2所示）是分組密碼的一個(gè)基本模型[3~5]，它主要是由混淆層－擴(kuò)散層－混淆層組成，通常會(huì)在第2層混淆之前異或加入輪密鑰。對(duì)于分組密碼來(lái)講，為了保證其能夠解密，一般要求每個(gè)iS（1in≤≤）都是置換且上下2個(gè)混淆層是完全一樣的。

近年來(lái)，在序列密碼的設(shè)計(jì)中，人們也廣泛應(yīng)用將混淆和擴(kuò)散分層實(shí)現(xiàn)的設(shè)計(jì)理念[6~8]。與分組密碼不同的是，對(duì)于序列密碼，在采用SP網(wǎng)絡(luò)時(shí)，由于其解密機(jī)制不同于分組密碼，且可以使用壓縮環(huán)節(jié)來(lái)實(shí)現(xiàn)輸入多輸出少的功能，因此在“混淆層－擴(kuò)散層－混淆層”這一設(shè)計(jì)模型中，上下2個(gè)混淆層可以不一樣，也不需要其中S盒都是置換。具體來(lái)說(shuō)，序列密碼中利用分組密碼的迭代思想時(shí)既可以先迭代最后再壓縮[6]，也可以邊迭代邊壓縮[7]。因此，在序列密碼的設(shè)計(jì)中，為同時(shí)且高效地實(shí)現(xiàn)迭代和壓縮（多輸入少輸出），可以使用更加一般的SPT模型（如圖3和圖4所示），這里S和T表示2個(gè)不同的混淆層，而且每個(gè)S或T都不必是置換。這就需要對(duì)SPT模型抗已知攻擊的能力進(jìn)行評(píng)估，弄清一般SPT模型抵抗差分攻擊和抵抗線性攻擊的能力。

對(duì)于SPS模型的抗差分攻擊和抗線性攻擊的安全性問(wèn)題，一直是受到密碼學(xué)者關(guān)注，也已有了完善的結(jié)果[9~13]。但對(duì)于更一般的可實(shí)現(xiàn)壓縮功能的SPT模型的抗差分攻擊能力和抗線性攻擊能力卻未見(jiàn)研究。本文正是在這一背景需求下進(jìn)行研究的，通過(guò)分析，本文克服了S變換和T變換的非雙射性給證明過(guò)程帶來(lái)的困難，給出了一般SPT模型在P為最佳擴(kuò)散層時(shí)抗差分攻擊和線性攻擊（S變換和T變換平衡時(shí)）能力估計(jì)的結(jié)果，這對(duì)于該模型在序列密碼設(shè)計(jì)中的應(yīng)用有重要的意義。

圖1 SPS模型(差分路徑)

圖2 SPS模型(線性路徑)

圖3 SPT模型(差分路徑)

本文第2節(jié)給出了相關(guān)定義和已有的結(jié)論；在第3節(jié)中，研究了如圖3所示的一般SPT模型在P為最佳擴(kuò)散層時(shí)抗差分攻擊的安全性問(wèn)題，給出了該模型的最大差分概率上界。

在第4節(jié)中，研究了如圖4所示的一般SPT模型在P為最佳擴(kuò)散層且S變換及T變換平衡時(shí)抗線性攻擊的安全性問(wèn)題，給出了類(lèi)似于SPS模型的最大線性逼近優(yōu)勢(shì)的上界和最大線性包優(yōu)勢(shì)的上界。

2 相關(guān)定義和已有結(jié)論

圖3和圖4中各記號(hào)約定如下。

設(shè)m,m1,m',n為4個(gè)正整數(shù)，且 m ≥ m ' ≥m1。i = 1 ,… ,n 。

記 Δα = (Δ α1, Δ α2, … ,Δ αn)， Δ β = (Δ β1,Δβ2,… ,Δ βn)，Δδ = (Δ δ1,Δ δ2,…,Δ δn)，Δ γ = (Δγ1,Δγ2, … ,Δ γn)，其中，Δαi∈ G F(2)m，Δ βi∈ G F(2)m1，Δδi,Δγi∈ G F(2)m'， i = 1,… ,n 。

記 Γα= ( Γ α1, Γ α2,… ,Γαn) ， Γ β=(Γ β1,Γβ2,… ,Γ βn)，Γδ = ( Γ δ1, Γ δ2,… ,Γδn) ，Γ γ=(Γ γ1,Γγ2,… , Γγn) ，其中，Γ αi∈ G F(2)m，Γ βi∈ G F(2)m1，Γδi∈ G F(2)m'， Γ γi∈ G F(2)m'， i = 1 ,… ,n 。

以wt(Δα)表 示 Δα 的 包 重 量 ， 即wt( Δ α ) = # ｛ i | Δ αi≠ 0 ｝;w t(Γ α)表示 Γα的包重量；以 MT表示矩陣M的轉(zhuǎn)置。

P:(GF(2)m')n→(GF(2)m')n為線性變換，且其為最佳擴(kuò)散層。

很容易有引理1~引理4。

引理1 設(shè)Δαi和Δδi分別為映射Si的輸入差和輸出差，則有 Δ αi=0? Δ δi= 0 ；又若 Si是雙射，則 Δ αi≠ 0 ? Δδi≠0。

引理2 設(shè)Δδ和Δγ分別為P的輸入差和輸出差，且P的分支數(shù)為n+1，則有wt(Δδ)+wt(Δγ)≥ n +1。

引理5[10]設(shè)n×n矩陣M對(duì)應(yīng)于變換P，則P的分支數(shù)為 n +1，當(dāng)且僅當(dāng)對(duì)于任意1 ≤ k ≤ n ，M的k×k子矩陣的秩為k（此時(shí)，MT的k×k子矩陣的秩也為k）。

引理6[10]設(shè)圖 1中 Si(i = 1 ,… ,n )均為置換且型SPS的最大差分概率上界為ρn。GF(2)m， Γ y ∈ G F(2)m'，S的線性?xún)?yōu)勢(shì)[9]定義為

其中，Γx?x表示Γx和x的點(diǎn)積。S的最大線性?xún)?yōu)勢(shì)定義為

根據(jù)Walsh譜[14]的定義，有

通?？疾靾D4所示模型SPT的2種線性?xún)?yōu)勢(shì)。

定義 3 (SPT的線性逼近優(yōu)勢(shì))[9]設(shè)Γα∈GF(2)m,Γδ, Γ γ∈ G F(2)m',Γ β∈ G F(2)m1,SPT的線性逼近優(yōu)勢(shì)定義為

SPT的最大線性逼近優(yōu)勢(shì)定義為

定義4 （SPT的線性包優(yōu)勢(shì)）[9]設(shè) Γ α∈G F(2)m,Γδ,Γ γ∈ G F(2)m',Γ β∈ G F(2)m1,SPT的線性包優(yōu)勢(shì)定義為

SPT的最大線性包優(yōu)勢(shì)定義為

引理7[9]設(shè)圖2中的 S ， i = 1 ,… ,n 均為置換，i衡當(dāng)且僅當(dāng)對(duì)任意 Γ y ∈GF(2)m'且Γy≠0，都有WalshS(Γ y,0) = 0。

由Walsh譜的定義及引理8有以下推論。

推論 1 設(shè)映射 S :GF(2)m→ G F(2)m'為平衡的，Γ x ∈ G F(2)m，Γ y ∈ G F(2)m'，則S的線性?xún)?yōu)勢(shì)有如下性質(zhì)：

引理9[14]Parseval等式：

引理 10[10]設(shè)P對(duì)應(yīng)于矩陣 M =(mij)n×n，

3 SPT模型的抗差分攻擊性

引理11 設(shè)n×n矩陣M對(duì)應(yīng)于變換P（即P(δ)=δ?M），且P是最佳擴(kuò)散層，Δγ=Δδ?M。再設(shè)wt(Δδ)=j，{i1,…,ij}為Δδ的非零分位的序號(hào)構(gòu)成的集合， s ≥ 1， w t( Δ γ) = n - s +1且 Δγ1=…決定。

證明 若 s =1，結(jié)論顯然成立。設(shè) s ＞ 1。取M的子矩陣，記Δδ'=(Δ δi1,… ,Δ δij)，則由題設(shè)知 Δδ?M的第1～s-1列=Δδ'?M'， 再 由 Δγ=Δδ?M知Δδ' ? M ' =(Δ γ1,… ,Δ γs-1) = 0。

記

則由P的分支數(shù)是 n +1和引理5知， M1可逆，且Δδis,… ,Δδij決定。#

下面將借助引理11，克服由 Si和 Ti的非雙射性引發(fā)的非零輸入差可能產(chǎn)生零輸出差的特性給研究過(guò)程造成的困難，獲得下述結(jié)論。

定理1 設(shè)圖3中P為最佳擴(kuò)散層，記ρd=非零時(shí)的最大差分概率上界為 ρdn。

證明 本證明所用符號(hào)如圖 3所示。設(shè)wt(Δ α)=k， Δβ≠0，且wt( Δ β )= n - s +1，不失一般性，不妨設(shè) Δ α1≠0,… , Δαk≠0， Δ βi1≠0,…,

假設(shè)密鑰K的各分位是相互獨(dú)立且服從均勻分布的，則可認(rèn)為SPT模型中各層輸入的各路彼此是獨(dú)立的，且Δα與Δγ獨(dú)立，因而

由引理4，有

依此類(lèi)推：

將所有可能的（即所有正概率差分路徑上的）Δδ 所在集合記為Mδ，則式(1)中的求和實(shí)際上是對(duì) Δ δ ∈ Mδ求和。Δδ ∈ Mδ,wt(Δ δ)=k1，且對(duì)于Δγ=Δδ?M,wt(Δγ)= n - s1+ 1 }，記所有可能的(k1,s1)所在的集合為Γ。則為諸 Mk1,s1的不交并。注意Δδ≠0（否則Δβ=0）且任意Δδ的非零位一定包含于{1,…,k},故1 ≤ k1≤ k 。又由 P的分支數(shù)為n+ 1 和引理2可知 k1≥s1≥1。故式(1)求和可化為

此即為式(3)的估計(jì)，進(jìn)而由式(2)可知：

因此圖 3所示模型SPT的輸出差非零時(shí)的最大差分概率上界為 ρdn。

定理2 設(shè)圖3所示模型SPT中P為最佳擴(kuò)散層，其輸入差為Δα且wt(Δα)=k，記

證明 同定理1證明，將所有可能的Δδ所在集合記為Mδ，則Mδ中可能含有0（S為壓縮變換時(shí)），同樣的推理可以得到

類(lèi)似于定理1可證

4 SPT模型的抗線性攻擊性

定理 3 設(shè)圖 4中 P為最佳擴(kuò)散層且 Si,Ti,則圖 4所示模型SPT的最大線性逼近優(yōu)勢(shì)

證明 設(shè) w t(Γ β) = k≥1，Γβ1≠ 0 ,… ,Γ βk≠0，Γα≠ 0 ，且設(shè) Γ αis≠ 0 ,… , Γαin≠ 0 ， Γ αi1= 0 ,…,

已知 Γ β1≠ 0 ,… ,Γ βk≠0， Γ βk+1=0,…,Γ βn=0，慮到 Ti、 Si平衡，由推論1有， Γ γ1≠ 0 ,… ,Γ γk≠0且 Γγk+1= 0,… ,Γ γn=0； Γ δis≠ 0 ,… , Γδin≠ 0 ，

又由變換P的分支數(shù)為 n +1，故 k + n - s +1

引理 12 設(shè)矩陣 M 對(duì)應(yīng)于變換P，Γδ=Γγ?MT， w t( Γ δ) = n -s +1，wt(Γγ)=k（則= Γ δs-1= 0 ，則存在指標(biāo)集 { i1, …,is-1}使得Γγi1≠

證明 結(jié)合引理5和引理10，對(duì)矩陣 MT利用類(lèi)似于引理11的證明方法即可得證。#

定理4 設(shè)圖4中 Si, Ti,i = 1 ,… ,n 均為平衡函數(shù)

證明 設(shè) w t(Γ β) = k≥1，Γβ1≠ 0 ,… ,Γ βk≠0，Γβk+1= 0 ,… ,Γ βn=0， w t( Γ α) = n - s + 1， s ≥ 1，Γαis≠ 0 ,… , Γαin≠ 0 ， Γ αi1= 0 ,… , Γαis-1= 0 。同定理3在題設(shè)條件下，只需考察Γα≠0時(shí)的情形。

由線性包優(yōu)勢(shì)的定義：

已知 Γ β1≠0,…,Γ βk≠0，Γβk+1= 0 ,… , Γ βn= 0 ，考慮到 Ti平衡，由推論1，若則 Γ γ1≠ 0 ,… ,Γ γk≠0且 Γ γk+1= 0 ,… , Γγn= 0 。再注意 L PTi(0 → 0 )= 1，故式(5)可化為

又 已 知 Γ αis≠ 0,… , Γαin≠ 0 , Γ αi1= 0 ,… ,，考慮到 Si平衡，同樣若≠ 0 ，則 Γ δis≠ 0 ,…, Γ δin≠ 0 ,Γ δi1= 0 ,… , Γ δis-1= 0 。

因此對(duì)于給定的Γγ，且Γγ的非零位為{1,… ,k }，

由以上分析，若記：

則式(6)可化為

因此只需考察Γ中的Γγ。對(duì)于Γγ∈Γ，由引理12可知，存在指標(biāo)集{ js, … , jk} ? {1,… ,k }，使得Γγ1,… ,Γγk由Γγjs,…,Γγjk決定。因此由式(7)得：

注：在對(duì)SPT模型最大線性逼近優(yōu)勢(shì)和最大線性包優(yōu)勢(shì)上界的估計(jì)中，其中所用S變換和T變換的平衡性是最關(guān)鍵的。

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

SPS網(wǎng)絡(luò)是分組密碼的一個(gè)基本模型，能夠同時(shí)實(shí)現(xiàn)壓縮功能的SPT模型是該模型的推廣，在序列密碼的設(shè)計(jì)中具有重要的應(yīng)用價(jià)值。本文在P為最佳擴(kuò)散層的條件下，研究了該模型的抗差分攻擊的安全性和抗線性攻擊（S和T平衡）的安全性，分別給出了其差分概率的上界、最大線性逼近優(yōu)勢(shì)的上界和最大線性包優(yōu)勢(shì)的上界，這些結(jié)論對(duì)于序列密碼的設(shè)計(jì)和分析具有現(xiàn)實(shí)的意義。在今后的工作中，還將研究該模型在更寬松條件下的抗差分和線性攻擊性能，并研究更加緊致的上界。

[1] KIM J S, LEE C H, SUNG J C, et al. Seven new block cipher structures with provable security against differential cryptanalysis[J].IEICE Trans Fundamentals, 2008,92(10): 3047-3058.

[2] SU B Z, WU W L, ZHANG W T. Security of the SMS4 block cipher against differential cryptanalysis[J]. Journal of Computer Science and Technology, 2011,26(1): 130-138.

[3] 張文濤, 卿斯?jié)h, 吳文玲. 嵌套Feistel結(jié)構(gòu)的SP型分組密碼的可證明安全性[J]. 計(jì)算機(jī)研究與發(fā)展, 2004, 41(8): 1389-1397.ZHANG W T, QIN S H, WU W L. Provable security for SPN block cIphers containing feistel structure[J]. Journal of Computer Research and Development, 2004,41(8): 1389-1397.

[4] 魏悅川, 孫兵, 李超. FOX密碼的不可能差分攻擊[J]. 通信學(xué)報(bào),2010, 31(9): 24-29.WEI Y C, SUN B, LI C. Impossible differential attacks on FOX[J].Journal on Communication, 2010, 31(9): 24-29.

[5] KELIHER L. Refined analysis of bounds related to linear and differential cryptanalysis for the AES[A]. AES 2004, LNCS 3373[C]. 2005. 42-57.

[6] BIRYUKOV A. Design of a new stream cipher-LEX, new stream cipher designs[A]. LNCS 4986[C]. 2008. 48-56.

[7] DAEMEN J, KITSOS P. The self-synchronizing stream cipher:MOUSTIQUE, new stream cipher designs[A]. LNCS 4986[C]. 2008.210-223.

[8] DE Cannière C，PRENAAL B, TRIVIUM. New stream cipher designs[A]. LNCS 4986[C]. 2008.244-266.

[9] KANG J S, HONG S, LEE S, et al. Practical and provable security against differential and linear cryptanalysis for the substitution- permutation networks[J]. ETRI Journal, 2001, 23(4):158-167.

[10] HONG S, LEE S, LIM J, et al. Provable security against differential and linear cryptanalysis for the SPN structure[A]. FSE 2000, LNCS 1978[C]. 2001. 273-283.

[11] 呂述望, 范修斌, 王昭順等. 完全映射及其密碼學(xué)應(yīng)用[M]. 合肥:中國(guó)科學(xué)技術(shù)大學(xué)出版社, 2008.LV S W, FAN X B, WANG Z S, et al. Complete Mapping and Application in Cryptography[M]. Hefei: University of Science and Technology of China Press, 2008.

[12] 吳文玲, 馮登國(guó), 張文濤. 分組密碼的設(shè)計(jì)與分析（第2版）[M]. 北京: 清華大學(xué)出版社, 2009.WU W L, FENG D G, ZHANG W T, The Design and Analysis of Block Ciphers(Second Edition)[M]. Beijing: Tsinghua University Press, 2009.

[13] KELIHER L, MEIJER H, TAVARES S. New method for upper bounding the maximum average linear hull probability for SPNs[A].EUROCRYPT 2001, LNCS 2045[C]. 2001. 420-436.

[14] 金晨輝, 鄭浩然, 張少武等. 密碼學(xué)[M]. 北京: 高等教育出版社,2009.JIN C H, ZHENG H R, ZHANG S W, et al. Cryptology[M]. Beijing:Higher Education Press, 2009.