對NBC-128 的安全性分析

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

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

0 引言

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

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

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

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

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

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

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

表1 對NBC-128 的攻擊結果比較

1 NBC-128 算法描述

圖1 NBC-128 的輪函數

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 對NBC-128 算法零相關線性分析

3.1 NBC-128 算法的11 輪零相關線性路線

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

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

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

圖5 NBC-128 的第一類11 輪零相關路線

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

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

3.2 對NBC-128/256 的多維零相關線性攻擊

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

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

圖6 NBC-128 的第二類11 輪零相關路線

圖7 NBC-128/256 的19 輪零相關攻擊

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

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

3.3 對NBC-128/128 的多維零相關線性攻擊

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

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

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

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

表3 NBC-128 的積分路線

4 NBC-128 算法的積分攻擊

4.1 NBC-128 算法的積分路線

利用Todo 的分離特性[21]搜索方法，實現了廣義Feistel結構的搜索算法，并對NBC-128 進行了積分路線搜索。搜索得到的NBC-128 算法最長積分路線為12 輪，需要的數據復雜度為2125，基于分離特性的積分路線如表3所示(文獻[9]、[10]中給出的數據量為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 個比特取常數，U 表示異或和狀態不確定，B 表示異或和為0，對應著存在積分特性的分支。

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

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

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

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

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

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

5 結論

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