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

1. 清華大學 計算機科學與技術系, 北京100084

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

3. 上海交通大學 計算機科學與工程系, 上海200240

4. 中國科學院 信息工程研究所 信息安全國家重點實驗室, 北京100093

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

6. 中國科學院大學 網絡空間安全學院, 北京100093

1 介紹

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

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

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

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

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

2 背景知識

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

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

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

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

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

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

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

2.2 S 盒的其他密碼學性質

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

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

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

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

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

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

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

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

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

我們在后續(xù)的推導中要用到下面極其重要的結論.

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

證明: 見文獻[24] 中的Theorem 1 和Theorem 2.

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

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

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

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

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

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

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

表1 三個上界的比較Table 1 Comparison of three different bounds

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

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

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

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

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

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

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

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

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

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

根據定理2, 我們任意選取Magma 找到的其中一個拆分. 如劃分的坐標集合分別為

和

得到的從集合B對應的字符串到集合A對應的字符串的映射, 它對應的從坐標集合B到坐標集合A的映射如表2 所示.

表2 一個拆分對應的S 盒Table 2 An S-box from Nordstrom-Robinson code

4 與其他上界的比較

5 總結

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

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