楊江帥 ，陳懷鳳 ，鮑金鳳 ，康瀟文

(1.中國電子信息產(chǎn)業(yè)集團有限公司第六研究所，北京 100083；2.北京聯(lián)合大學(xué)旅游學(xué)院，北京 110101；3.61428 部隊，北京 100097)

0 引言

為推動我國密碼算法的設(shè)計及實現(xiàn)技術(shù)發(fā)展，培養(yǎng)密碼學(xué)人才，中國密碼學(xué)會于2018 年啟動了全國密碼算法設(shè)計競賽，共22 個分組密碼算法進入第一輪評估，有10 個算法進入第二輪評估[1]。其中ublouk[2]、FESH[3]、TANGRAM[4]和SPRING[5]算法采用SPN 結(jié)構(gòu)，ANT[6]、SMBA[7]和Raindrop[8]算法采用Feistel 結(jié)構(gòu)，NBC[9-10]和FBC[11]算法采用廣義Feistel 結(jié)構(gòu)。最終，uBlock 和Ballet 獲得一等獎，F(xiàn)ESH、ANT 和TANGRAM 獲得二等獎，Raindrop、NBC、FBC、SMBA 和SPRING 獲得三等獎。

本文將針對NBC 算法進行安全性分析，NBC 算法由徐洪等人設(shè)計并提出，支持128/128 bit、128/256 bit、256/256 bit 3 種分組和密鑰尺寸。該算法的非線性F 函數(shù)部分采用16 bit S 盒，由16 級非線性反饋移位寄存器迭代而成，具有較低的硬件實現(xiàn)成本。差分分析[12]、線性分析[13]、不可能差分分析[14]、零相關(guān)線性分析[15-17]和積分分析[18]等是分析分組密碼算法安全性的主要方法，算法設(shè)計者針對NBC 算法的各個版本給出了初步分析結(jié)果。

針對NBC-128 算法的兩個版本，設(shè)計者的研究表明[9-10]：NBC-128 算法不存在9 輪有效的線性特征和差分特征。對于不可能差分攻擊和零相關(guān)線性攻擊，設(shè)計者在第二輪的提交文檔[9]中給出了10 輪的區(qū)分器及詳細(xì)的攻擊過程，后來在新版本中[10]將兩類路線各擴展一輪，并相應(yīng)地將可攻擊輪數(shù)擴展了一輪。利用不可能差分分析方法，設(shè)計者攻擊19 輪NBC-128/256、17 輪NBC-128/128，利用零相關(guān)線性分析方法，可以攻擊16輪NBC-128/256、15 輪NBC-128/128。對于積分分析方法，設(shè)計者給出了12 輪的積分路線，數(shù)據(jù)復(fù)雜度為2127，可以攻擊18 輪NBC-128/256、16 輪NBC-128/128。

本文將針對NBC-128/256 和NBC-128/128 兩個版本進行獨立的安全分析，主要從不可能差分分析、零相關(guān)分析和積分分析3 種分析方法出發(fā)開展研究，相關(guān)的攻擊結(jié)果比較見表1。主要貢獻如下：

(1)給出NBC-128 算法的兩類11 輪不可能差分路線，利用其中一類不可能差分路線進行了NBC-128/256和NBC-128/128 算法的不可能差分攻擊。本文認(rèn)為文獻[9]中的密鑰猜測過程少猜了幾個子密鑰，達到預(yù)期攻擊輪數(shù)的計算復(fù)雜度將超過窮搜密鑰復(fù)雜度。表1 給出了修正后的數(shù)據(jù)和計算復(fù)雜度估計。

(2)給出NBC-128 算法的兩類11 輪零相關(guān)線性路線，基于其中一類零相關(guān)線性路線構(gòu)造多維零相關(guān)區(qū)分器，在卡方統(tǒng)計法多維零相關(guān)攻擊模型下進行了NBC-128/256 和NBC-128/128 算法的密鑰恢復(fù)攻擊，對于NBC-128/256 算法可以攻擊到19 輪，對于NBC-128/128 算法可以攻擊到16 輪，比已知的多維零相關(guān)攻擊分別擴展了3 輪和1 輪。

(3)給出了NBC-128 算法基于分離特性的新型12輪積分路線，并進行了積分攻擊，需要的數(shù)據(jù)復(fù)雜度僅為2125，優(yōu)于原有積分攻擊的數(shù)據(jù)復(fù)雜度。

表1 對NBC-128 的攻擊結(jié)果比較

1 NBC-128 算法描述

圖1 NBC-128 的輪函數(shù)

NBC-128 算法采用8 分支廣義Feistel 結(jié)構(gòu)，迭代32輪。每個分支16 bit，每輪存在4 個F 函數(shù)，F(xiàn) 函數(shù)的輸入為輸入分支與輪密鑰的異或值，經(jīng)過1 個16 bit 的S 盒查表，輸出與另外一個分支異或，最后經(jīng)過一個分支位置變換操作。在NBC-128 算法的最后一輪，F(xiàn) 函數(shù)的輸出與相鄰分支異或后，不再進行分支位置變換操作。設(shè)第i 輪的輸入為，輸出為第i 輪的子密鑰為其一輪變換的結(jié)構(gòu)如圖1 所示。

NBC-128 算法存在256 bit 和128 bit 兩個密鑰尺寸，本文的主要研究與密鑰擴展算法關(guān)聯(lián)不大，此處不再給出NBC-128 算法的密鑰擴展算法。

2 對NBC-128 算法的不可能差分分析

2.1 NBC-128 算法的11 輪不可能差分路線

本節(jié)給出NBC-128 算法的兩類新型11 輪不可能差分路線，其中第一類不可能差分路線在文獻[10]中已被提出。

命題1：(NBC-128 的第一類11 輪不可能差分路線)

(0，Δ，0，0，0，0，0，0)/→(0，0，0，Δ，0，Γ，0，0)是NBC-128 算法的一條11 輪不可能差分路線，最后一輪不包括位置置換，其中Δ，?！?，Δ≠Γ，圖2 給出了該不可能差分路線的矛盾產(chǎn)生過程，圖中* 表示差分非零，?表示差分不確定，空白位置表示差分為0。

命題2：(NBC-128 的第二類11 輪不可能差分路線)

圖2 NBC-128 的第一類11 輪不可能差分路線

(0，Δ，0，0，0，0，0，0)/→(0，0，0，Δ，0，Γ，0，0)是NBC-128 算法的一條11 輪不可能差分路線，最后一輪不包括位置置換，其中Δ，?！?，且Δ 與Γ 相互獨立，圖3 給出了該不可能差分路線的矛盾產(chǎn)生過程，圖中* 表示差分非零，?表示差分不確定，空白位置表示差分為0。

圖3 NBC-128 的第二類11 輪不可能差分路線

實際上，NBC-128 算法為每一輪具有4個F 函數(shù)的廣義Feistel 結(jié)構(gòu)，通過移動輸入差分、輸出差分中非零差分的位置，可以構(gòu)造一系列類似的11 輪不可能差分路線，從結(jié)構(gòu)以及攻擊能力方面考慮與上述路線等價，此處不再給出具體細(xì)節(jié)。

2.2 對NBC-128/256 算法的不可能差分攻擊

在文獻[9]、[10]中的不可能差分分析過程中，認(rèn)為作者漏猜了幾個子密鑰，因此實際攻擊效果達不到預(yù)期的那么好。利用第一類11 輪不可能差分路線，本文對NBC-128/256 算法進行修正的不可能差分攻擊，圖4 給出了攻擊過程中的差分及符號，主要攻擊過程如下：

(1)構(gòu)造Structure：Sc={X=(X0，X1，X2，X3，X4，X5，X6，X7)|(X0，X4，X5)}=c，其他位置遍歷}，則每個Structure 中有280個元素，可以構(gòu)造約2159組符合(0，*，*，*，0，0，Δ，*)的差分對(Δ 取遍非零可能值)。

(2)通過構(gòu)造m 個Structure，可以構(gòu)造2t=2159×m×2-48個明文差分符合(0，*，*，*，0，0，Δ，*)，相應(yīng)的密文差分符合(0，*，0，0，*，*，Γ，*)，Γ≠Δ，Γ≠0 的正確數(shù)據(jù)對。

(3)按照表2 進行密鑰猜測及錯誤對篩除，對于每一個錯誤密鑰，每一個正確對被留下的概率為2-16×8=2-128。對于錯誤密鑰，沒有差分對留下的概率為p=(1-2-128)2t≈2-114×(t-128)，即剩余約2256×p 個候選正確密鑰。

圖4 NBC-128/256 的17 輪不可能差分攻擊

(4)利用兩個明文對進行候選正確密鑰的窮搜，完成密鑰恢復(fù)攻擊。

復(fù)雜度估計：選取m=222個Structure，共需要2102個選擇明文。此時，步驟(3)的總計算復(fù)雜度約為2t+80=2159+22-48+80=2213次簡單計算，步驟(4)的窮搜復(fù)雜度為2256×p≈2209.82次17 輪加密?？倳r間復(fù)雜度約為2210.5次17 輪加密。

表2 對NBC-128/256 的不可能差分攻擊

2.3 對NBC-128/128 算法的不可能差分攻擊

對于NBC-128/128 算法，主密鑰長度僅有128 bit，只能在區(qū)分器前后各添加兩輪進行15 輪密鑰恢復(fù)攻擊。

通過選擇252個Sc={X=(X0，X1，X2，X3，X4，X5，X6，X7)|(X2，X3，X4，X6，X7)}=c，其他位置遍歷}類型的結(jié)構(gòu)體，可以構(gòu)造252+95-80=267個輸入差分符合(*，*，0，0，0，Δ，0，0)、輸出差分符合(0，*，0，0，*，0，Γ，0)、Γ ≠Δ 的數(shù)據(jù)對，用類似于上述的密鑰猜測及錯誤對篩除，對于錯誤密鑰，無差分對剩余的概率為p=(1-2-64)267≈2-11.52。錯誤對篩除的總計算量約為267+48=2115次簡單計算，剩余約2128×2-11.52=2116.48，總時間復(fù)雜度約為2116.51次15 輪加密。需要的數(shù)據(jù)量為252+48=2100個選擇明文。

3 對NBC-128 算法零相關(guān)線性分析

3.1 NBC-128 算法的11 輪零相關(guān)線性路線

本節(jié)給出NBC-128 算法的兩類新型11 輪零相關(guān)線性路線，其中第一類零相關(guān)線性路線在文獻[10]中已被提出。

命題3：(NBC-128 的第一類11 輪零相關(guān)線性路線)

(α，0，0，0，0，0，0，0)→(0，0，0，0，β，0，0，0)是NBC-128 算法的一條11 輪零相關(guān)路線，最后一輪不包括位置置換，其中α，β≠0，α≠β，圖5 給出了該零相關(guān)線性路線的矛盾產(chǎn)生過程，*表示掩碼非零，?表示掩碼不確定，空白位置表示掩碼為0。

圖5 NBC-128 的第一類11 輪零相關(guān)路線

命題4：(NBC-128 的第二類11 輪零相關(guān)線性路線)

(α，0，0，0，0，0，0，0)→(0，0，0，0，α，0，β，0)是NBC-128 算法的一條11 輪零相關(guān)線性路線，最后一輪不包括位置置換，其中α，β≠0，且α 與β 相互獨立，圖6 給出了該零相關(guān)線性路線的矛盾產(chǎn)生過程，*表示掩碼非零，?表示掩碼不確定，空白位置表示掩碼為0。

3.2 對NBC-128/256 的多維零相關(guān)線性攻擊

通過選取特定形式的輸入掩碼和輸出掩碼，可以構(gòu)造t=12 維的多維零相關(guān)線性區(qū)分器，例如選取α=04||06||*6，β=04||*6||06的零相關(guān)路線。在該區(qū)分器前后各添加4 輪進行19 輪算法的密鑰恢復(fù)攻擊，相關(guān)狀態(tài)及猜測的密鑰情況如圖7 所示，具體攻擊過程如下：

(1)對于N 個已知明文及其相應(yīng)的密文數(shù)據(jù)，猜測128 bit 密鑰可以計算得到，根據(jù)區(qū)分器的輸入、輸出掩碼表示，共需存儲t bit 即可，因此可將中間狀態(tài)存儲于296+t個計數(shù)器中。該步驟需要的計算復(fù)雜度約為N×2128次8 個S 盒的查表。(2)猜測，計算得到,可存儲于280+t個計數(shù)器中。該步驟需要的計算復(fù)雜度約為296+t×2128+16=2240+t次1 個S 盒的查表。

圖6 NBC-128 的第二類11 輪零相關(guān)路線

圖7 NBC-128/256 的19 輪零相關(guān)攻擊

(4)最終得到t 維的計數(shù)器向量，計算統(tǒng)計數(shù)并保留小于閾值τ 的密鑰，剩余約2256×α1個候選密鑰，這里α1表示將錯誤密鑰判定為正確密鑰的概率。通過至多兩個明密文數(shù)據(jù)進行窮搜攻擊，恢復(fù)各輪密鑰。

復(fù)雜度估計[19-20]：通過設(shè)置兩類錯誤概率α0=2-2.7，α1=2-11，這里α0表示將正確密鑰判定為錯誤密鑰的概率，可以計算出需要的不同已知明文數(shù)據(jù)復(fù)雜度為N ≈2124.5537，區(qū)分密鑰使用的閾值為τ=3803.173。步驟(1)需要的計算復(fù)雜度約為T1=N×2128×(8/(4×19))≈2249.3058；步驟(2)和步驟(3)需要的計算復(fù)雜度約為T2=2240+t×6×(1/(4×19))≈2248.337；步驟(4)需要的計算復(fù)雜度約為T3=2245。綜上，總計算復(fù)雜度約為2249.9487次19 輪加密。

3.3 對NBC-128/128 的多維零相關(guān)線性攻擊

利用類似的t=8 維的多維零相關(guān)路線，可以在前后分別添加2 和3 輪，針對NBC-128/128 算法進行16 輪的攻擊。沿用圖7 的表示，進行第3～18輪的攻擊，攻擊過程如下：

(1)對于N 個不同的已知明文及其密文數(shù)據(jù)，可壓縮為存儲個數(shù)的計數(shù)器。對于，根據(jù)區(qū)分器的輸入、輸出掩碼表示，共需存儲t bit 即可，因此可將中間狀態(tài)存儲于296+t個計數(shù)器中。

(4)最終得到t 維的計數(shù)器向量，計算統(tǒng)計數(shù)并保留小于閾值τ 的密鑰，剩余約2128×α1個候選密鑰。通過至多兩個明密文數(shù)據(jù)進行窮搜攻擊，恢復(fù)各輪密鑰。

復(fù)雜度估計[9-10]：通過設(shè)置兩類錯誤概率α0=2-2.7，α1=2-8，可以計算出需要的不同已知明文數(shù)據(jù)復(fù)雜度為N≈2123.3548，區(qū)分密鑰使用的閾值為τ=15905.54。步驟(1)需要的計算復(fù)雜度約為T1=N 次狀態(tài)壓縮；步驟(2)和步驟(3)需要的計算復(fù)雜度約為T2=2112+t×6×(1/(4×16))≈2122.585；步驟(4)需要的計算復(fù)雜度約為T3=2120。綜上，總計算復(fù)雜度不超過為2124.1069次16 輪加密。

表3 NBC-128 的積分路線

4 NBC-128 算法的積分攻擊

4.1 NBC-128 算法的積分路線

利用Todo 的分離特性[21]搜索方法，實現(xiàn)了廣義Feistel結(jié)構(gòu)的搜索算法，并對NBC-128 進行了積分路線搜索。搜索得到的NBC-128 算法最長積分路線為12 輪，需要的數(shù)據(jù)復(fù)雜度為2125，基于分離特性的積分路線如表3所示(文獻[9]、[10]中給出的數(shù)據(jù)量為2127)。

第4 條分離特性路線的積分特性見命題5。

命題5:（NBC-128 的一條積分路線）

(A16，A16，A16，A16，A16，A16，A13，A16)→(U，U，U，U，U，U，U，B)是NBC-128 算法的一條12 輪積分路線，最后一輪包括位置置換，其中An表示n 個比特遍歷，16-n 個比特取常數(shù)，U 表示異或和狀態(tài)不確定，B 表示異或和為0，對應(yīng)著存在積分特性的分支。

4.2 對NBC-128/256、NBC-128/128 算法的積分攻擊

對NBC-128 的攻擊過程與文獻[9]中的描述大部分相同，下面不詳細(xì)描述具體細(xì)節(jié)，只說明攻擊中的不同點。

(1)本文采用的積分路線需要的數(shù)據(jù)量為2125，而不是2127。

(2)在使用2125數(shù)據(jù)量的積分區(qū)分器下，只有一個分支存在積分特性，該分支狀態(tài)異或和為16 bit 全0 時對應(yīng)的密鑰為候選正確密鑰，剩余密鑰量為總密鑰量的2-16。

(3)對于NBC-128/256，利用12 輪積分路線可以攻擊18 輪算法，計算一個分支異或和的計算復(fù)雜度約為2204.15。因此，使用一條積分路線攻擊時，總計算復(fù)雜度為2204.15+2256-16≈2240。

(4)對于NBC-128/128，利用12 輪積分路線可以攻擊16 輪算法，計算一個分支異或和的計算復(fù)雜度約為292.32。因此，使用一條積分路線攻擊時，總計算復(fù)雜度為292.32+2128-16≈2112。

5 結(jié)論

本文針對NBC-128 的兩個密鑰尺寸版本的算法，給出改進的不可能差分分析、多維零相關(guān)線性分析和積分分析結(jié)果。其中不可能差分攻擊對之前的攻擊進行了修正，零相關(guān)線性分析在攻擊輪數(shù)上有所擴展，積分分析則降低了攻擊的數(shù)據(jù)復(fù)雜度。針對NBC-128/256 的19 輪多維零相關(guān)線性攻擊從輪數(shù)上來說是已知的最優(yōu)攻擊。