n 比特置換的差分分支數(shù)上界*

尤啟迪, 周 旋, 李 順, 張英杰

1. 清華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系, 北京100084

2. 北京衛(wèi)星信息工程研究所, 北京100086

3. 上海交通大學(xué) 計(jì)算機(jī)科學(xué)與工程系, 上海200240

4. 中國(guó)科學(xué)院 信息工程研究所 信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室, 北京100093

5. 中國(guó)科學(xué)院 數(shù)據(jù)與通信保護(hù)研究教育中心, 北京100093

6. 中國(guó)科學(xué)院大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院, 北京100093

1 介紹

對(duì)稱密碼中使用的線性和非線性部件, 充分地體現(xiàn)了Shannon 關(guān)于密碼學(xué)部件擴(kuò)散和混淆功能的經(jīng)典論述[1]. 以最簡(jiǎn)單的分組密碼為例, 擴(kuò)散功能通常由線性部件提供, 它將明文的局部統(tǒng)計(jì)性質(zhì), 盡可能快速地?cái)U(kuò)散到整個(gè)密碼的計(jì)算路徑中去, 從而盡可能多地激活可以削弱這些統(tǒng)計(jì)性質(zhì)的其他部件(這通常為提供混淆功能的非線性部件). 近十年以來, 密碼學(xué)界在分組密碼整體結(jié)構(gòu)的設(shè)計(jì)上趨于穩(wěn)定(大部分分組密碼都采用了SPN 結(jié)構(gòu)、Feistel 結(jié)構(gòu)及它們的變種), 鮮有突破. 因此, 研究具有良好性質(zhì)的局部密碼學(xué)部件, 是近幾年學(xué)界的熱點(diǎn).

對(duì)于線性部件, 人們主要關(guān)注它的擴(kuò)散性質(zhì). 利用極大距離線性可分碼(MDS), 我們可以構(gòu)造具有(局部) 最優(yōu)擴(kuò)散性質(zhì)的線性部件. 使用MDS 矩陣作為分組密碼的線性部件的優(yōu)勢(shì)主要體現(xiàn)在兩個(gè)方面.第一, 針對(duì)差分攻擊和線性攻擊的安全性論證較為直接, 可以較為容易的界定差分和線性活躍S 盒的下屆.第二, 可以在較小的輪數(shù)下達(dá)到足夠的安全強(qiáng)度, 從而降低算法的延遲. 實(shí)際上, AES[2]正是由于這些優(yōu)勢(shì), 得到了學(xué)界和工業(yè)界的廣泛認(rèn)可. 近些年來, 由于普世計(jì)算和物聯(lián)網(wǎng)的快速發(fā)展, 學(xué)界將更多的注意力放在了可以在資源受限環(huán)境中實(shí)現(xiàn)的輕量級(jí)MDS 矩陣的構(gòu)造上, 得到了一系列實(shí)現(xiàn)面積更小、電路延遲更低的新的MDS 矩陣[3-13].

對(duì)于小的非線性部件(如4×4 S 盒), 人們對(duì)它們的差分均勻度、代數(shù)免疫度、非線性度等一系列性質(zhì)已經(jīng)研究得較為透徹. 對(duì)于規(guī)模較大的S 盒, 由于對(duì)某些性質(zhì)的分析和歸納需要進(jìn)行強(qiáng)力搜索, 人們對(duì)其認(rèn)識(shí)還不夠徹底. 非常值得注意的是, 近幾年, 人們開始關(guān)注非線性部件的擴(kuò)散性質(zhì), 這在之前是很少見的. 非線性部件可以提供擴(kuò)散功能, ISO 國(guó)際標(biāo)準(zhǔn)輕量級(jí)分組密碼算法PRESENT[14]是最好的例證.

PRESENT 的S 盒具有這樣一個(gè)性質(zhì), 即對(duì)任意差分活躍的S 盒, 其輸入差分和輸出差分中至少有三個(gè)比特非零. 而PRESENT 的線性層又保證了其任意一個(gè)S 盒的4 位輸出比特, 分別為下一輪的四個(gè)S 盒的輸入比特. 這兩個(gè)性質(zhì)確保了當(dāng)某一輪的輸入差分只有一比特非零時(shí), 下一輪至少激活兩個(gè)S盒. 這種性質(zhì)使得線性部件和非線性部件相互配合, 在整體上保證了差分活躍S 盒的個(gè)數(shù). 這種有效的配合, 使得PRESENT 采用了如圖1 所示的幾乎沒有實(shí)現(xiàn)代價(jià)的線性層(只有布線產(chǎn)生的微小代價(jià)). 可見,對(duì)非線性部件的擴(kuò)散性質(zhì)進(jìn)行研究, 是非常有價(jià)值的. 在文獻(xiàn)[15] 中, Sumanta Sarkar 和Habeeb Syed討論了非線性置換作為S 盒的兩個(gè)參數(shù)差分分支數(shù)和線性分支數(shù)的上界. 對(duì)于任意一個(gè)GF2n上的置換,他們給出了差分分支數(shù)上界的一般表達(dá)式. 更具體地, 他們對(duì)GF24上任意置換的差分分支數(shù)進(jìn)行詳細(xì)的討論, 其最大值是與上界的一般表達(dá)式符合的. 但是當(dāng)長(zhǎng)度增加時(shí), Sarkar 給出的上界值與Griesmer 界相距甚遠(yuǎn), 這個(gè)上界值與最大值的距離有多遠(yuǎn)產(chǎn)生了新的問題. 在文獻(xiàn)[16] 中, Yunwen Liu 和Vincent Rijmen, Gregor Leander 討論了分別基于Kerdock 碼和T 函數(shù)構(gòu)造的非線性擴(kuò)散部件, 通過將這兩個(gè)函數(shù)應(yīng)用到具體的密碼算法設(shè)計(jì)中, 他們說明了這兩個(gè)擴(kuò)散部件能同時(shí)提供擴(kuò)散性和混淆性. 具體地, 基于Kerdock 碼的擴(kuò)散函數(shù)比相同長(zhǎng)度下的其他線性置換的差分分支數(shù)都要高, 即擴(kuò)散性質(zhì)是8 比特里面最好的. 基于T 函數(shù)的擴(kuò)散函數(shù)則僅比線性置換的差分分支數(shù)少1. 作者所給出的非線性擴(kuò)散都是4 比特和8 比特的, 能否在其他長(zhǎng)度上找到類似的具有較好擴(kuò)散性的非線性函數(shù)也是值得考慮的.

圖1 PRESENT 輪函數(shù), 其線性層為比特的位置置換Figure 1 Round function of PRESENT, whose linear layer is a permutation of bit positions

2 背景知識(shí)

如果這個(gè)碼長(zhǎng)度為n, 最小距離為d, 含有N個(gè)碼字, 那么可以記為(n,N,d).A(n,d) 表示長(zhǎng)度為n最小距離為d的最大的二元碼包含的元素個(gè)數(shù). 我們稱A(·,·) 為A函數(shù).

2.1 擴(kuò)散函數(shù)和分支數(shù)

擴(kuò)散層是分組密碼中的核心部件之一. 在密碼算法的設(shè)計(jì)歷史中, 各種各樣的擴(kuò)散函數(shù)被提出來以達(dá)到某種極佳的擴(kuò)散效果. 著名的例子包括AES[2]中的MixColumn 函數(shù). 該函數(shù)是基于MDS 碼構(gòu)造的,在分支數(shù)方面實(shí)現(xiàn)了最佳的擴(kuò)散性. 分支數(shù)經(jīng)常被用于衡量有限域上線性函數(shù)的擴(kuò)散性, 然而它也可以對(duì)一般的函數(shù)進(jìn)行分析.

定義1 對(duì)GF2n上任意置換φ, 它的差分分支數(shù)記作Bd(φ) 定義為

擴(kuò)散層的分支數(shù)對(duì)算法整體抗差分及線性攻擊等的強(qiáng)度有重要影響. 一方面, 使用分支數(shù)較高的線性層可以在較小的輪數(shù)內(nèi)達(dá)到較高的抗差分和攻擊強(qiáng)度, 從而降低算法的整體延遲. 另一方面, 分支數(shù)較高的線性層其實(shí)現(xiàn)代加也更大. 因此, 設(shè)計(jì)者往往會(huì)進(jìn)行各種參數(shù)的權(quán)衡. 例如, 近些年來, 在一些輕量級(jí)分組密碼算法的設(shè)計(jì)中, 擴(kuò)散層往往不使用MDS 矩陣, 如PRINCE[17]和MIDORI[18]使用的擴(kuò)散函數(shù)分支數(shù)為4 (最大值為5), 而像PRESENT 使用的是分支數(shù)僅為2 的比特拉線, 并通過非線性層和線性層的配合達(dá)到更好的擴(kuò)散效果.

假設(shè)有一個(gè)長(zhǎng)度為2n的二元碼C, 且{ci0ci1···cin?1:c ∈C}=GF2n, 則映射

構(gòu)成一個(gè)n×nS 盒, 其中{i0,i1,··· ,in?1}∪{j0,j1,··· ,jn?1}={0,1,··· ,2n ?1}. 那么這個(gè)S 盒的差分分支數(shù)和二元碼的最小距離是一致的. 在后面的章節(jié)中, 我們將利用二元碼的性質(zhì)來研究任意置換的分支數(shù).

2.2 S 盒的其他密碼學(xué)性質(zhì)

一個(gè)n比特的S 盒是GF2n上的(嚴(yán)格) 非線性置換. 在對(duì)稱密碼設(shè)計(jì)中, 我們通常采用一些具有優(yōu)良局部密碼學(xué)性質(zhì)的S 盒, 如高非線性度(Nonlinearity), 高差分一致性(Differential Uniformity) 以及高代數(shù)次數(shù)(Algebraic Degree) 等.

非線性度: 令S:GF2n →GF2m,X →S(X) 是一個(gè)n比特輸入m比特輸出的S 盒, 稱

3 差分分支數(shù)上界

對(duì)于GF2n上任意置換, 我們已知兩個(gè)上界: Griesmer 界[23]和Sarkar 界[15].

3.1 GF2n 上置換的差分分支數(shù)

對(duì)任意 GF2n上的非線性置換φ, 若其差分分支數(shù)為B=Bd(φ), 那么以此置換能定義一個(gè)(2n,2n,B) 非線性二元碼

我們利用A函數(shù)的性質(zhì)去分析B和n的關(guān)系. 首先, 我們有如下引理.

引理1A(n ?1,2d ?1)=A(n,2d).

證明: 假設(shè)有長(zhǎng)度為n ?1、最小距離為2d ?1 的二元碼, 我們考慮將這個(gè)碼中的每個(gè)碼字加一個(gè)比特, 這個(gè)比特就是每個(gè)碼字自身的奇偶性表示, 也就是如果碼字中有奇數(shù)個(gè)1, 那就再在末尾加一個(gè)1;如果碼字中有偶數(shù)個(gè)1, 那就再在末尾加一個(gè)0. 這樣得到的新的碼字組成的新的二元碼就是一個(gè)長(zhǎng)度為n ?1+1 =n、最小距離為2d ?1+1 = 2d的碼. 關(guān)于最小距離的改變, 我們只需要考慮原來距離為2d ?1 的碼字, 因?yàn)榫嚯x為奇數(shù), 這2 個(gè)碼字的奇偶性一定不同, 也就是最后面添加的數(shù)一定不同, 那么經(jīng)過修改后得到的新的碼字的距離一定為2d ?1+1 = 2d. 而對(duì)于本來就大于等于2d的碼字而言, 修改后距離一定不比原來的小. 故新的二元碼的最小距離為2d, 即A(n,2d)≥A(n ?1,2d ?1); 假設(shè)有長(zhǎng)度為n, 最小距離為2d的二元碼, 我們?nèi)〕銎渲腥我粚?duì)距離為2d的碼字c和c′. 任意選取c,c′某一位置i使得ci ?=c′i. 然后將每個(gè)碼字做這樣的操作: 刪去位置i處的值. 這樣每個(gè)碼字的碼長(zhǎng)均為n ?1, 最小距離變成2d ?1. 所以A(n ?1,2d ?1)≥A(n,2d). 綜合以上內(nèi)容得到A(n,2d)=A(n ?1,2d ?1).

我們?cè)诤罄m(xù)的推導(dǎo)中要用到下面極其重要的結(jié)論.

定理1A(4k,2k)≤8k且A(n,d)≤2A(n ?1,d).

證明: 見文獻(xiàn)[24] 中的Theorem 1 和Theorem 2.

注3 有趣的是, 如果存在4k×4k的Hadamard 矩陣(命題2) 那么定理1 左邊等號(hào)成立, 且滿足等號(hào)的二元碼就是Hadamard 碼.

定義2 (Hadamard 矩陣[25]) 一個(gè)n階的Hadamard 矩陣是一個(gè)由1 和?1 構(gòu)成的n×n矩陣, 它滿足H ·HT=nIn. 其中In是單位矩陣.

關(guān)于Hadamard 矩陣的存在性猜想可能是正確的但是仍然還未被證明, 目前已知驗(yàn)證到664×664 Hadamard 矩陣的存在性.

回到本節(jié)開頭, 我們現(xiàn)在尋找二元碼滿足A(2n,B)≥2n的B的最大值B?. 首先需要下面引理2,

引理2A(2n,B)≥A(2n,B+1).

3.2 GF28 置換的差分分支數(shù)

考慮可能用于設(shè)計(jì)8 比特S 盒的置換即GF28上非線性置換. 用上節(jié)的方法我們有:

表1 三個(gè)上界的比較Table 1 Comparison of three different bounds

那么8 比特S 盒差分分支數(shù)最多為6. 而實(shí)際上確實(shí)存在這樣的S 盒, 我們找到了一個(gè)非線性二元碼(16,256,6)-Nordstrom-Robinson 碼[26].

注5 (Nordstrom-Robinson 碼) Nordstrom-Robinson 碼(NR碼) 在1967 年由Nordstrom 和Robinson 構(gòu)造. 它同時(shí)屬于加長(zhǎng)Preparata 碼[27]和Kerdock 碼[28]. Preparata 碼和Kerdock 碼都是無限長(zhǎng)的非線性碼類, 參數(shù)為(2m ?1,22m?2m,5) 和(2m,22m,2m?1?2(m?2)/2), 其中m需要是偶數(shù).因此, Nordstrom-Robinson 碼的特殊之處在于它是這兩個(gè)無限次的非線性碼類種的唯一交集. 更有趣的性質(zhì)在于將NR碼在Z4-線性下分析[29,30]得到.

于是我們嘗試對(duì)這個(gè)非線性碼變換, 看是否存在碼字的一個(gè)拆分, 使得拆分后的碼字的兩部分都包含8 比特, 且滿足每個(gè)碼字在同一拆分坐標(biāo)下的子碼字兩兩不等.

我們?cè)贛agma 上進(jìn)行這種嘗試, 發(fā)現(xiàn)有2760 種拆分滿足, 計(jì)算其中一個(gè)S 盒的密碼學(xué)性質(zhì), 發(fā)現(xiàn)它的非線性度為0(最低)、代數(shù)度為2(最低)、差分均勻性為256(最高), 3 個(gè)參數(shù)都是最差的情形, 總體來看除了差分分支數(shù)以外其他的密碼學(xué)性質(zhì)均不好. 雖然如此, 對(duì)于這個(gè)置換存在如文獻(xiàn)[16] 中所展示的使用方式.

而且這2760 個(gè)差分分支數(shù)為6 的8 比特S 盒, 其中有很多是等價(jià)的. 這種等價(jià)性指的是密碼學(xué)性質(zhì)如非線性度、差分均勻性保持一致. 我們有下面的定理:

定理2 如果S 盒是通過一個(gè)二元碼C轉(zhuǎn)化而得到的, 那么C的其他轉(zhuǎn)換得到的S 盒的密碼學(xué)性質(zhì)——差分均勻性、非線性度均保持不變.

證明: 假設(shè)二元碼C中碼字的長(zhǎng)度是2n. 不失一般性, 可以假設(shè)前n個(gè)坐標(biāo)和后n個(gè)坐標(biāo)的劃分就能得到這個(gè)二元碼的一個(gè)S 盒即映射

那么這個(gè)S 盒的差分均勻性(2.2節(jié)) 對(duì)應(yīng)于一組概率最大的差分傳播a →b, 則原來的二元碼中碼字的異或值等于(a,b)的對(duì)也是最多的. 如果有一個(gè)新的劃分T1、T2,滿足T1∪T2={1,2,··· ,2n}、T1∩T2=?且坐標(biāo)集合T1到T2的映射是置換, 即構(gòu)成S 盒, 那么只需要將(a,b) 的坐標(biāo)進(jìn)行變換, 假設(shè)在T1下的n比特值為a′, 在T2下的n比特值為b′. 那么對(duì)于新的S 盒而言, (a′,b′) 是傳播概率最大的那個(gè)差分對(duì).于是坐標(biāo)變換不改變S 盒的差分均勻性.

同理, 對(duì)于非線性度(2.2節(jié)), 假設(shè)前n個(gè)坐標(biāo)劃分的S 盒非線性度對(duì)應(yīng)于一組線性逼近u →l, 使得輸出掩碼Su(X)=u·S(X) 與輸入掩碼l(X)=w·X+ε的Hamming 距離最小, 那么其他的坐標(biāo)劃分對(duì)應(yīng)的新的S 盒只需要進(jìn)行同樣的u,w,ε的坐標(biāo)變換即可導(dǎo)致同樣的Hamming 距離, 也就是同樣的非線性度.

注6 對(duì)于另一個(gè)重要的參數(shù)-代數(shù)度, 我們對(duì)于其變換前后的改變無法進(jìn)行準(zhǔn)確的度量, 一個(gè)具體的例子是Keccak[31]中的χ函數(shù).χ函數(shù)的代數(shù)度為2, 逆的代數(shù)度為3.

根據(jù)定理2, 我們?nèi)我膺x取Magma 找到的其中一個(gè)拆分. 如劃分的坐標(biāo)集合分別為

和

得到的從集合B對(duì)應(yīng)的字符串到集合A對(duì)應(yīng)的字符串的映射, 它對(duì)應(yīng)的從坐標(biāo)集合B到坐標(biāo)集合A的映射如表2 所示.

表2 一個(gè)拆分對(duì)應(yīng)的S 盒Table 2 An S-box from Nordstrom-Robinson code

4 與其他上界的比較

5 總結(jié)

在本文中, 我們的主要工作是對(duì)非線性置換的差分分支數(shù)進(jìn)行了分析, 尋找了一般性的上界, 并且將這個(gè)上界與Griesmer 界、Sarkar 界進(jìn)行了比較, 說明了我們得到的界是好的. 同時(shí), 對(duì)于這個(gè)界在n=8這一常用的場(chǎng)景進(jìn)行了具體的討論, 由著名的Nordstrom-Robinson 碼說明了8 比特S 盒存在差分分支數(shù)達(dá)到上界6 的情況, 并且討論這一類S 盒所具有的密碼學(xué)性質(zhì), 得到的結(jié)果并不好.

盡管我們找到的8 比特最大差分分支數(shù)S 盒的密碼學(xué)性質(zhì)并不好, 接下來我們可以嘗試降低差分分支數(shù)要求, 看能達(dá)到較強(qiáng)學(xué)安全性的8 比特S 盒的差分分支數(shù)最大可以是多少. 另外, S 盒還有其他的安全指標(biāo)值得繼續(xù)分析, 如差分均勻性在n ≥8 且n是偶數(shù)時(shí)的最小值是多少, 特別是8 比特這一常用的S 盒規(guī)模, 如果能得到確切的下界, 對(duì)于設(shè)計(jì)更好的S 盒也有很大的幫助.