一種新的抵抗差分錯(cuò)誤分析的S 盒實(shí)現(xiàn)*

徐翌豪, 李智虎, 樊燕紅, 王美琴

1. 山東大學(xué)網(wǎng)絡(luò)空間安全學(xué)院, 青島 266237

2. 密碼技術(shù)與信息安全教育部重點(diǎn)實(shí)驗(yàn)室, 青島 266237

3. 中國(guó)電力科學(xué)研究院有限公司, 北京 100192

1 引言

密碼算法的理論安全性是隨著密碼分析技術(shù)的不斷發(fā)展而逐漸完善的, 但是現(xiàn)代密碼算法安全性的威脅不僅來(lái)自對(duì)算法層次的數(shù)學(xué)理論分析. 隨著無(wú)線傳感、射頻識(shí)別(radio frequency identification,RFID)以及物聯(lián)網(wǎng)的高速發(fā)展, 輕量級(jí)密碼算法在資源相對(duì)受限的環(huán)境中應(yīng)用越來(lái)越廣泛[1,2], 而輕量級(jí)密碼算法大多采用硬件方式實(shí)現(xiàn), 這就導(dǎo)致物理攻擊對(duì)于密碼算法安全性的威脅越來(lái)越大. 在物理攻擊中, 錯(cuò)誤注入攻擊[3]屬于主動(dòng)的物理攻擊, 相比于被動(dòng)的側(cè)信道分析[4], 錯(cuò)誤注入攻擊可以極大地減少分析的樣本量[5], 極大提高了攻擊效率. 錯(cuò)誤注入攻擊主要通過(guò)電磁脈沖、時(shí)鐘毛刺、激光束等手段在密碼算法的硬件實(shí)現(xiàn)中使寄存器、門電路或者線發(fā)生錯(cuò)誤, 之后結(jié)合數(shù)學(xué)統(tǒng)計(jì)和分析, 通過(guò)注入錯(cuò)誤得到的錯(cuò)誤密文與正確運(yùn)算得到的無(wú)錯(cuò)密文之間的差分來(lái)獲取密鑰的相關(guān)信息, 這就是差分錯(cuò)誤分析(differential fault analysis, DFA)[6–9]. 隨著錯(cuò)誤注入精度以及軟硬件逆向技術(shù)的提高, 實(shí)施錯(cuò)誤攻擊所依賴的設(shè)備條件不斷減弱, 成本不斷下降, 錯(cuò)誤類型和位置已經(jīng)在一定程度上可以控制, 敵手可以輕松對(duì)任意不受保護(hù)的密碼算法進(jìn)行錯(cuò)誤注入, 因此幾乎所有的密碼算法都易受到DFA 的威脅. Aghaie 等人[10]從基于錯(cuò)誤檢測(cè)碼(error detecting code, EDC) 的并發(fā)錯(cuò)誤檢測(cè)(concurrent error detection, CED) 模式[11]出發(fā), 考慮錯(cuò)誤傳播在組合邏輯電路中的消極影響, 設(shè)計(jì)出對(duì)于給定的敵手模型下對(duì)于錯(cuò)誤注入的檢測(cè)有100% 覆蓋率的完美電路. Beierle 等人[12]首先在密碼算法的設(shè)計(jì)階段就考慮到在不同安全級(jí)別下抵抗DFA, 并設(shè)計(jì)出高效的輕量級(jí)密碼算法CRAFT. CRAFT 的S 盒設(shè)計(jì)理念充分考慮到錯(cuò)誤傳播的消極影響, 利用獨(dú)立特性, 使S 盒的全部輸入共同決定輸出的1 比特信息, 這樣不復(fù)用的電路元件之間就可以避免注入錯(cuò)誤的擴(kuò)散, 結(jié)合CED 模型, 敵手注入的錯(cuò)誤可以100% 被檢測(cè)到. Baksi 等人[13]從密碼算法抵抗差分分析和差分錯(cuò)誤分析的權(quán)衡出發(fā), 設(shè)計(jì)出可以用于抵抗DFA 的具有特殊線性結(jié)構(gòu)的S 盒, 為密碼算法抵抗DFA 的研究提供了新的思路.

S 盒是分組密碼算法的重要組件之一, 是執(zhí)行非線性運(yùn)算的算法組件, 安全性和軟硬件性能[14–16]是衡量S 盒優(yōu)劣的兩個(gè)重要指標(biāo). S 盒的實(shí)現(xiàn)方式有兩種: 查表(lookup table, LUT) 和布爾函數(shù)表達(dá)式, S 盒的實(shí)現(xiàn)環(huán)境分為軟件實(shí)現(xiàn)和硬件實(shí)現(xiàn). S 盒的軟硬件實(shí)現(xiàn)通常利用LUT 實(shí)現(xiàn). 對(duì)于S 盒查表的硬件實(shí)現(xiàn)[17]而言, 實(shí)現(xiàn)者利用綜合器內(nèi)置的優(yōu)化算法將S 盒轉(zhuǎn)化為布爾電路. 雖然綜合器能夠?qū)盒的LUT 實(shí)現(xiàn)進(jìn)行一定程度的優(yōu)化, 但是由于其內(nèi)置的優(yōu)化算法是面向通用函數(shù)的, 對(duì)于S 盒的特殊實(shí)現(xiàn)要求輸出的結(jié)果有可能不是最優(yōu)[18]. 針對(duì)不同的實(shí)現(xiàn)準(zhǔn)則如等價(jià)門電路的復(fù)雜度(gate equivalent complexity, GEC)、切片門電路的復(fù)雜度(bitslice gate complexity, BGC)、深度(depth) 等, 如何找到S 盒較好的布爾函數(shù)實(shí)現(xiàn)成為近期的熱門研究領(lǐng)域. 針對(duì)ASIC (application specific integrated circuit)平臺(tái), Lighter[18]工具實(shí)現(xiàn)了在給定指令集下搜索S 盒的最優(yōu)面積布爾函數(shù); Guo 等人[19]提出了一種基于深度的S 盒實(shí)現(xiàn)方法, 通過(guò)遞歸的算法尋找給定S 盒的深度最優(yōu)的布爾函數(shù)實(shí)現(xiàn); PEIGEN[20]工具是一種集S 盒實(shí)現(xiàn), 評(píng)估及設(shè)計(jì)為一體的綜合工具, 其在Lighter 工具的基礎(chǔ)上進(jìn)行改進(jìn), 提升了搜索S 盒布爾表達(dá)式的效率, 除此之外, PEIGEN 工具也優(yōu)化了Guo 等人S 盒深度最優(yōu)的實(shí)現(xiàn)方法, 在保證深度最優(yōu)的前提下同時(shí)保證面積的局部最優(yōu).

我們的工作深入理解在差分錯(cuò)誤分析中錯(cuò)誤傳播的消極影響, 提出密碼算法抵抗DFA 的S 盒獨(dú)立性實(shí)現(xiàn), 并在實(shí)現(xiàn)性能方面進(jìn)行了提升. Aghaie 等人[10]采用LUT 方法進(jìn)行S 盒實(shí)現(xiàn), 利用綜合軟件內(nèi)部的優(yōu)化算法進(jìn)行優(yōu)化. 綜合器對(duì)復(fù)雜S 盒的LUT 的優(yōu)化并不是最優(yōu)的, 因?yàn)橥ㄓ玫膬?yōu)化算法不會(huì)考慮S 盒的具體實(shí)現(xiàn)特性. 我們使用基于圖的布爾函數(shù)生成算法, 通過(guò)回溯的方式篩選出給定S 盒滿足獨(dú)立性的布爾表達(dá)式, 在限制深度的同時(shí), 選取面積最優(yōu)的實(shí)現(xiàn)方式, 來(lái)優(yōu)化獨(dú)立性S 盒的硬件布爾表達(dá)式實(shí)現(xiàn). 利用我們提出的生成獨(dú)立性S 盒的算法, 對(duì)GIFT、Khazad、LBlock 等已知S 盒進(jìn)行實(shí)現(xiàn), 并利用Synopsys DC 綜合軟件和UMC 55 nm 標(biāo)準(zhǔn)元件庫(kù)對(duì)S 盒獨(dú)立性布爾表達(dá)式實(shí)現(xiàn)進(jìn)行綜合. 綜合結(jié)果顯示, 與單純的依賴綜合軟件優(yōu)化的LUT 實(shí)現(xiàn)方法相比, 我們提出的S 盒獨(dú)立性優(yōu)化實(shí)現(xiàn)方法, 不同程度地提升了S 盒的實(shí)現(xiàn)效率.

2 研究背景

2.1 獨(dú)立性

密碼算法的錯(cuò)誤注入攻擊方法首先被Boneh 和DeMillo 等人[3]提出并成功運(yùn)用到RSA 的CRT 版本中. 隨后Shamir 等人[6]利用差分分析的方法與錯(cuò)誤注入攻擊相結(jié)合, 提出差分錯(cuò)誤分析的攻擊方法,并對(duì)傳統(tǒng)的DES 算法進(jìn)行了攻擊. 其核心思想就是利用差分錯(cuò)誤分析的方法, 使用時(shí)鐘毛刺、激光束、電磁干擾等手段在密碼算法運(yùn)行時(shí)向其中注入錯(cuò)誤, 使最終的加密結(jié)果出現(xiàn)差錯(cuò), 從而恢復(fù)出相關(guān)的密鑰信息. 2018 年, Aghaie 等人[10]從錯(cuò)誤傳播的消極影響出發(fā), 設(shè)計(jì)出在給定敵手模型下錯(cuò)誤檢測(cè)率100% 的完美電路, 并提出獨(dú)立性將其應(yīng)用于抵抗DFA 的S 盒實(shí)現(xiàn)中, 下面給出獨(dú)立性質(zhì)的定義.

其中Gi代表成員函數(shù)Ti的門電路實(shí)現(xiàn)集合. 那么滿足上述形式的組成電路集合是獨(dú)立的, 滿足獨(dú)立特性可以避免錯(cuò)誤傳播, 即一個(gè)錯(cuò)誤的門最多導(dǎo)致輸出1 比特的錯(cuò)誤.

由定義可知, 獨(dú)立性質(zhì)主要為了避免密碼算法執(zhí)行時(shí)在S 盒組件中發(fā)生的錯(cuò)誤擴(kuò)散傳播, 如果設(shè)計(jì)的S 盒滿足獨(dú)立特性, 那么在最壞的情況下(注入的錯(cuò)誤門一定導(dǎo)致錯(cuò)誤的輸出), 敵手攻擊t個(gè)門電路也最多只會(huì)導(dǎo)致對(duì)應(yīng)t比特出現(xiàn)錯(cuò)誤, 這就使注入的錯(cuò)誤不會(huì)在電路中發(fā)生擴(kuò)散.

接下來(lái)我們介紹非獨(dú)立性S 盒的實(shí)現(xiàn)方式與獨(dú)立特性S 盒實(shí)現(xiàn)方式的區(qū)別, 非獨(dú)立性S 盒實(shí)現(xiàn)時(shí)一般不考慮門電路是否復(fù)用, 這就可能導(dǎo)致在S 盒的具體實(shí)現(xiàn)時(shí), 會(huì)存在S 盒不同輸出復(fù)用門電路的情況,使得一個(gè)門可能被多個(gè)輸出共用, 如圖1(a) 所示. 獨(dú)立性S 盒的電路實(shí)現(xiàn)避免了門電路的復(fù)用問(wèn)題, S 盒的每一比特輸出都獨(dú)立于其他輸出比特對(duì)應(yīng)的電路實(shí)現(xiàn), 如圖1(b) 所示. 圖中的x,y,z表示電路的輸入,x′和y′表示電路的輸出.

從圖1 可以看出,非獨(dú)立特性S 盒的兩個(gè)輸出具有一個(gè)復(fù)用的異或門(XOR),獨(dú)立特性S 盒的實(shí)現(xiàn)沒(méi)有復(fù)用的門. 假設(shè)敵手有攻擊一個(gè)門電路XOR 的能力, 非獨(dú)立性的實(shí)現(xiàn)方式會(huì)使錯(cuò)誤擴(kuò)散到第二個(gè)OR門從而導(dǎo)致輸出的兩個(gè)比特全部出錯(cuò), 而獨(dú)立性的實(shí)現(xiàn)方式保證了兩個(gè)輸出對(duì)應(yīng)的門電路獨(dú)立, 只能影響輸出的1 個(gè)比特, 這樣就阻止了錯(cuò)誤的擴(kuò)散, 使得在并發(fā)錯(cuò)誤檢測(cè)模式下可以精準(zhǔn)的檢測(cè)錯(cuò)誤.

圖1 非獨(dú)立性電路與獨(dú)立性電路的錯(cuò)誤擴(kuò)散Figure 1 Error propagation in non-independent circuits and independent circuits

2.2 深度最優(yōu)的S 盒實(shí)現(xiàn)

電路深度復(fù)雜度通常定義為從輸入門到輸出門的最長(zhǎng)路徑的長(zhǎng)度. 在高速電路硬件實(shí)現(xiàn)的情況下, 實(shí)現(xiàn)者有時(shí)候希望將電路的深度保持盡可能低, 以便能夠增加時(shí)鐘頻率, 而不必使用更多的門. 例如任何函數(shù)都可以通過(guò)深度為2 的電路來(lái)計(jì)算, 即將該函數(shù)通過(guò)合取或析取范式來(lái)表示, 然而這樣的表示方法可能會(huì)導(dǎo)致電路中門電路數(shù)量較大, 這是實(shí)現(xiàn)者不希望看到的, 因此需要在電路的深度和門電路數(shù)量之間權(quán)衡.下面給出S 盒深度的定義.

定義2 (S 盒深度) S 盒深度定義為, 在S 盒輸入到輸出電路中, 最長(zhǎng)路徑所包含的邏輯門電路的個(gè)數(shù).

Guo 等人[19]提出一種S 盒的深度評(píng)估工具, 其核心是預(yù)計(jì)算的功能模塊. 預(yù)計(jì)算模塊通過(guò)一個(gè)遞歸算法枚舉在某一個(gè)深度下S 盒輸入比特的所有可能的布爾函數(shù). 深度評(píng)估工具通過(guò)與預(yù)計(jì)算得到的布爾函數(shù)進(jìn)行匹配來(lái)找到給定S 盒深度最優(yōu)的布爾函數(shù)實(shí)現(xiàn). Bao 等人[20]對(duì)文獻(xiàn)[19] 中的算法在等價(jià)門電路復(fù)雜度(GEC) 方面進(jìn)行了提升, 實(shí)現(xiàn)了深度最優(yōu)、等價(jià)門電路局部最優(yōu)的S 盒布爾表達(dá)式的實(shí)現(xiàn). 具體實(shí)現(xiàn)方式是在一個(gè)指令集β(包括AND, OR, XOR, NAND, NOR, XNOR 和NOT 等) 中, 通過(guò)廣度優(yōu)先的方式生成一個(gè)圖. 圖的每一個(gè)節(jié)點(diǎn)表示一個(gè)狀態(tài)值(即操作數(shù))及其布爾函數(shù),邊代表前一層上的節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)通過(guò)操作指令產(chǎn)生的聯(lián)系. 假設(shè)一個(gè)i比特輸入的S 盒, 初始節(jié)點(diǎn)定義為v0,v1,··· ,v(i-1),也稱為輸入的恒等變換布爾函數(shù), 初始節(jié)點(diǎn)對(duì)應(yīng)的層數(shù)定義為圖的第0 層. 圖的擴(kuò)展以初始節(jié)點(diǎn)開始, 以層為單位遍歷指令集中的所有指令, 圖的生成過(guò)程如圖2 所示.

圖2 布爾函數(shù)圖的生成示意圖Figure 2 Diagram of generation of Boolean function graph

在每一層圖節(jié)點(diǎn)的生成過(guò)程中, 不僅需要對(duì)指令集中的操作指令遍歷, 同時(shí)還要遍歷操作數(shù), 操作數(shù)包括層數(shù)小于當(dāng)前層數(shù)的所有節(jié)點(diǎn), 新生成的節(jié)點(diǎn)需要記錄生成該節(jié)點(diǎn)的操作類型以及操作數(shù), 在圖的生成過(guò)程中, 對(duì)新生成的節(jié)點(diǎn)布爾函數(shù)的門電路復(fù)雜度不斷優(yōu)化, 過(guò)濾掉有相同狀態(tài)值但門電路復(fù)雜度較大的節(jié)點(diǎn), 不僅保證S 盒每一個(gè)分量的門電路復(fù)雜度最小, 同時(shí)利用在不同分量之間選擇可共享的指令前綴的方式優(yōu)化等價(jià)門電路的全局復(fù)雜度, 即對(duì)于每一個(gè)分量深度最小的前提下找到等價(jià)門電路復(fù)雜度最小的實(shí)現(xiàn)方式, 最后保證圖中每個(gè)布爾函數(shù)都是深度最優(yōu), 等價(jià)門電路復(fù)雜度局部最優(yōu).

3 獨(dú)立性S 盒實(shí)現(xiàn)算法

3.1 設(shè)計(jì)策略

我們借鑒了Guo 等人[19]的生成S 盒的布爾表達(dá)式的方法以及Bao 等人[20]的改進(jìn)方法, 通過(guò)生成圖的方式在一個(gè)指令集β中, 尋找已知S 盒獨(dú)立實(shí)現(xiàn)的最優(yōu)硬件表達(dá)式.

(1) 本文的算法著重于布爾函數(shù)的硬件實(shí)現(xiàn)的優(yōu)化, 選擇的硬件指令集是單輸入的NOT 門以及兩輸入的邏輯門AND/OR, XOR/XNOR, NAND/NOR. 我們使用∧、∨、⊕和?分別代表邏輯與、或、異或、非, 指令集及邏輯運(yùn)算如表1 所示.

表1 算法邏輯指令集Table 1 Logic instruction set in algorithm

(2) 設(shè)計(jì)的S 盒的門電路實(shí)現(xiàn)具有獨(dú)立特性. 本文設(shè)計(jì)的獨(dú)立性布爾函數(shù)的過(guò)濾策略基于這種以深度擴(kuò)展的圖算法, 獨(dú)立性要求在門電路實(shí)現(xiàn)時(shí)沒(méi)有共用門, 即如果在以初始節(jié)點(diǎn)進(jìn)行第一層圖擴(kuò)展時(shí)生成的所有新節(jié)點(diǎn), 在給定S 盒的所有分量布爾函數(shù)中至多只出現(xiàn)一次, 則該S 盒的布爾函數(shù)實(shí)現(xiàn)滿足獨(dú)立特性.

(3) 根據(jù)指令集的權(quán)重, 尋找滿足獨(dú)立性S 盒的最優(yōu)面積實(shí)現(xiàn). 我們?cè)O(shè)計(jì)策略是在深度最優(yōu)的情況下,搜索面積局部最優(yōu)的獨(dú)立布爾表達(dá)式實(shí)現(xiàn).

3.2 獨(dú)立性S 盒算法設(shè)計(jì)

獨(dú)立性S 盒實(shí)現(xiàn)算法包括兩個(gè)模塊的設(shè)計(jì): 圖生成模塊和獨(dú)立性實(shí)現(xiàn)模塊. 圖生成模塊利用指令集和擴(kuò)展算法構(gòu)建不同層上的節(jié)點(diǎn), 直至構(gòu)建出滿足S 盒特定狀態(tài)值的節(jié)點(diǎn). 獨(dú)立性實(shí)現(xiàn)模塊的主要功能是:在生成圖的基礎(chǔ)上, 篩選滿足獨(dú)立特性S 盒的布爾表達(dá)式.

3.2.1 圖生成模塊

在圖生成模塊中, 與文獻(xiàn)[19,20] 的不同之處在于, 我們不對(duì)生成的節(jié)點(diǎn)進(jìn)行過(guò)濾與優(yōu)化, 保留所有的節(jié)點(diǎn), 這樣生成的圖中, 存在多個(gè)不同的節(jié)點(diǎn)代表的狀態(tài)值是相同的, 但是他們分別表示不同的布爾函數(shù),這樣我們可以得到所有可能的布爾表達(dá)式, 以保證進(jìn)入獨(dú)立性實(shí)現(xiàn)模塊的布爾函數(shù)的完整性. 當(dāng)然算法的生成圖模塊只需執(zhí)行一次, 對(duì)于不同S 盒可以多次重用. 隨著圖的層數(shù)的增加, 節(jié)點(diǎn)數(shù)量呈指數(shù)級(jí)增長(zhǎng), 我們考慮有限的計(jì)算資源和內(nèi)存資源, 定義參數(shù)λ作為層數(shù)閾值,λ可以根據(jù)內(nèi)存資源設(shè)定作為圖擴(kuò)展算法的終止條件. 當(dāng)圖的擴(kuò)展算法完成時(shí), 就得到了在給定指令集下的全部布爾函數(shù), 對(duì)于給定的S 盒, 算法可以回溯圖中的節(jié)點(diǎn), 推導(dǎo)出該S 盒對(duì)應(yīng)的布爾函數(shù)實(shí)現(xiàn).

3.2.2 獨(dú)立性實(shí)現(xiàn)模塊

在給定深度和指令集的生成圖中, 包含了S 盒對(duì)應(yīng)的所有可能的布爾函數(shù). 算法的獨(dú)立性實(shí)現(xiàn)模塊的設(shè)計(jì)思路是, 在所有可能的布爾表達(dá)式實(shí)現(xiàn)中, 利用兩次過(guò)濾的方法, 篩選出滿足獨(dú)立特性的布爾表達(dá)式.兩次過(guò)濾的具體內(nèi)容如下:

(1) 首先過(guò)濾掉面積成本較高的實(shí)現(xiàn)方式;

(2) 然后過(guò)濾掉不滿足獨(dú)立特性的實(shí)現(xiàn)方式.

以4 比特S 盒為例, 我們介紹搜索獨(dú)立性實(shí)現(xiàn)模塊的操作流程.

(1) 在生成的圖中搜索滿足目標(biāo)S 盒的4 個(gè)分量函數(shù)的節(jié)點(diǎn)并分類存儲(chǔ)為4 個(gè)組,記C1,C2,C3,C4.

(2) 從4 個(gè)組的每一組中任取其中一個(gè)元素進(jìn)行組合, 即可得到給定S 盒的一種布爾函數(shù)實(shí)現(xiàn). 這樣的組合方式會(huì)使一個(gè)S 盒有很多種不同的布爾函數(shù)實(shí)現(xiàn).

(3) 我們首先針對(duì)所有組合, 考慮其實(shí)現(xiàn)的等價(jià)門電路復(fù)雜度, 根據(jù)指令集的面積權(quán)重設(shè)置過(guò)濾閾值,濾除面積實(shí)現(xiàn)成本高的組合, 這樣大大減少了獨(dú)立性篩選的樣本量.

3.3 算法實(shí)現(xiàn)

已知S 盒的獨(dú)立性布爾表達(dá)式的優(yōu)化實(shí)現(xiàn)如算法1 所示. 給定參數(shù)λ作為層數(shù)閾值, 此參數(shù)可根據(jù)操作系統(tǒng)的內(nèi)存容量進(jìn)行調(diào)整, 以避免深度過(guò)大時(shí)的內(nèi)存溢出, 算法的另一個(gè)參數(shù)target 是目標(biāo)S 盒. 以i表示S 盒的位數(shù),V表示圖的節(jié)點(diǎn),Vdepth表示在第depth 層的生成的所有節(jié)點(diǎn)集合, 其中depth 參數(shù)初始化為0, 使用SUCC(v,o) 記錄新節(jié)點(diǎn)與操作數(shù)以及指令之間的運(yùn)算關(guān)系, 使用before 指針記錄新節(jié)點(diǎn)與操作數(shù)節(jié)點(diǎn)之間的邏輯關(guān)系, 以便于節(jié)點(diǎn)指針的回溯. 在判斷候選布爾表達(dá)式是否為獨(dú)立特性時(shí), 為了便于表述, 我們使用AreaFilter 函數(shù)過(guò)濾面積較大的布爾函數(shù)實(shí)現(xiàn). 取出分量節(jié)點(diǎn)N1,N2,··· ,Ni中的指令面積并求和與AreaThreshold 參數(shù)進(jìn)行比較, 返回值為True 表示面積大于指定閾值, 此函數(shù)可以根據(jù)給定的S 盒自定義調(diào)整以獲得局部面積最優(yōu)的實(shí)現(xiàn)方式. 另外使用IsDump 函數(shù)表示向量組中是否有重復(fù)的節(jié)點(diǎn), 如果返回為真, 則說(shuō)明給定S 盒的i個(gè)候選布爾函數(shù)在圖的首次擴(kuò)展時(shí)產(chǎn)生了共同了相同的節(jié)點(diǎn), 即最終結(jié)果不滿足獨(dú)立特性, 反之, 則表示S 盒的布爾函數(shù)實(shí)現(xiàn)沒(méi)有共用的門電路, 即此候選布爾表達(dá)式滿足獨(dú)立特性. 算法1 生成圖階段和獨(dú)立性搜索階段的時(shí)間復(fù)雜度均約為226.56, 故本算法總時(shí)間復(fù)雜度約為227.56, 而在生成圖的具體實(shí)現(xiàn)時(shí), 本文使用structure 來(lái)表示節(jié)點(diǎn)記錄的信息, 具體包括該節(jié)點(diǎn)的狀態(tài)值及其對(duì)應(yīng)的布爾函數(shù)、操作指令、指令權(quán)重, 所以, 本文所提算法的空間復(fù)雜度約為226.56個(gè)structure.

算法1 獨(dú)立性S 盒實(shí)現(xiàn)Input: target, λ Output: 獨(dú)立布爾函數(shù)實(shí)現(xiàn)ImplementFile 1 初始化depth ←0,E ←?,V0 ←{v0,v1,··· ,vi},G = {V0,E}2 調(diào)用圖生成函數(shù)GenGraph(G,depth,λ)3 遍歷圖G 搜索目標(biāo)S 盒targrt 的分量函數(shù), 并將這些節(jié)點(diǎn)分別存儲(chǔ)在C1,C2,··· ,Ci 中4 for each N1,N2,··· ,Ni in C1,C2,··· ,Ci do 6 while (N1,N2,··· ,Ni) /∈V1 do 5if AreaFilter(N1,N2,··· ,Ni,AreaThreshold) then 7 N1 = N1.before,N2 = N2.before,···, Ni = Ni.before 8 end將N1,N2,··· ,Ni 的切片數(shù)據(jù)存儲(chǔ)到向量Vec 中10if IsDump(Vec) then 9 11Print Result(N1,N2,··· ,Ni,False)12end 13else 14Print Result(N1,N2,··· ,Ni,True)15end 16end 17 end 18 function GenGraph(G,depth,λ)19 Vt = ? 20 for all o in β do 21if (o == NOT) then 22for all v ∈Vdepth do 23N ←SUCC(v,o)24N.before=v,Vt ←Vt ∪N, E ←E ∪{v →N}25end 26end 27else 28for all vx ∈Vdepth do 29for all vy ∈V do 30N ←SUCC(vx,vy,o), N.before=(vx,vy)31Vt ←Vt ∪N,E ←E ∪{vx →N}32end 33end 34end 35 end 36 depth = depth+1, Vdepth = Vt, G ←G ∪{Vdepth,E}37 if (depth ≤λ) then 38GenGraph(G,depth,λ)39 end 40 return G

4 實(shí)驗(yàn)與結(jié)果

4.1 實(shí)驗(yàn)環(huán)境

S 盒獨(dú)立特性優(yōu)化實(shí)現(xiàn)算法用C++ 語(yǔ)言進(jìn)行了程序?qū)崿F(xiàn), 程序運(yùn)行的系統(tǒng)環(huán)境為: Intel Xeon CPU E5 2620 @2.00 GHz 128 G 內(nèi)存, 64 位Ubuntu 16.04.4 LTS. 對(duì)不同的目標(biāo)S 盒, 算法程序返回優(yōu)化后的獨(dú)立表達(dá)式所用的時(shí)間平均約為12.36 分鐘. 獲得S 盒的具有獨(dú)立性的布爾表達(dá)式后, 先使用Verilog HDL 進(jìn)行硬件實(shí)現(xiàn), 然后在Modelsim 軟件上進(jìn)行功能仿真, 最后使用Synopsys Design Compiler 綜合軟件與UMC 55 nm 的標(biāo)準(zhǔn)元件庫(kù)進(jìn)行硬件電路的綜合仿真, 得到S 盒的面積及時(shí)延的測(cè)試結(jié)果.

4.2 實(shí)驗(yàn)結(jié)果

我們以GIFT 的S 盒為例, 給出生成的獨(dú)立布爾表達(dá)式. 值得注意的是, 使用我們的算法生成的所有布爾表達(dá)式中, 可能存在一個(gè)給定S 盒的多種不同的表達(dá)式實(shí)現(xiàn), 而這些不同的表達(dá)式經(jīng)過(guò)綜合之后得到相同的硬件面積和時(shí)延, 這里只給出其中一種表達(dá)式實(shí)現(xiàn). 定義S 盒的輸入和輸出分別為{X[3],X[2],X[1],X[0]}和{Y[3],Y[2],Y[1],Y[0]}, 其中X[3] 和Y[3] 分別代表最高位.

從如上所示的布爾表達(dá)式實(shí)現(xiàn)來(lái)看, GIFT 的S 盒的每一個(gè)分量函數(shù)對(duì)應(yīng)的布爾表達(dá)式彼此之間互相獨(dú)立, 這樣就可以使注入的錯(cuò)誤在S 盒層不發(fā)生擴(kuò)散, 大大提高并發(fā)錯(cuò)誤檢測(cè)的效率. 利用我們的S 盒實(shí)現(xiàn)算法, 生成了目標(biāo)S 盒的具有獨(dú)立特性的布爾表達(dá)式. 然后對(duì)每個(gè)目標(biāo)S 盒進(jìn)行兩種實(shí)現(xiàn): LUT 和獨(dú)立布爾函數(shù). 最后利用ASIC 綜合平臺(tái)分別將兩種實(shí)現(xiàn)方式進(jìn)行綜合, 得到面積和時(shí)延的測(cè)試結(jié)果, 具體的實(shí)驗(yàn)結(jié)果見表2. 從實(shí)驗(yàn)結(jié)果可以看出, 對(duì)于一個(gè)給定的S 盒, 使用本文的算法生成的獨(dú)立布爾表達(dá)式的實(shí)現(xiàn)無(wú)論在面積或者時(shí)延開銷上都優(yōu)于直接獨(dú)立LUT 的實(shí)現(xiàn)方法. 本文對(duì)S 盒的獨(dú)立性實(shí)現(xiàn)性能進(jìn)行提升, 使其在實(shí)現(xiàn)時(shí)的硬件開銷和時(shí)延都優(yōu)于之前的工作, 為抵抗DFA 的S 盒的實(shí)現(xiàn)設(shè)計(jì)提供了新的思路.

表2 實(shí)驗(yàn)結(jié)果Table 2 Experimental results

5 總結(jié)

實(shí)驗(yàn)結(jié)果顯示, 使用我們的算法生成S 盒獨(dú)立特性的布爾表達(dá)式綜合之后的結(jié)果會(huì)好于獨(dú)立LUT 的方法. 該算法以及思路是首次對(duì)于抵抗DFA 的S 盒獨(dú)立特性的研究, 提出的生成獨(dú)立特性布爾表達(dá)式的新方法, 對(duì)于防止差分錯(cuò)誤注入分析的S 盒有實(shí)踐意義, 為研究設(shè)計(jì)抵抗DFA 的密碼算法的組件提供一個(gè)新的思路. 雖然我們提出的新思想和新方法對(duì)于傳統(tǒng)的抵抗DFA 的S 盒有提升, 但是我們提出的算法也有局限性, 對(duì)于實(shí)現(xiàn)復(fù)雜的S 盒, 需要更多的層數(shù)來(lái)實(shí)現(xiàn), 生成的圖的規(guī)模會(huì)呈指數(shù)級(jí)別的增長(zhǎng), 從而需要相當(dāng)大的時(shí)間和空間復(fù)雜度去生成優(yōu)化的獨(dú)立布爾表達(dá)式. 接下來(lái)我們會(huì)繼續(xù)研究和改進(jìn)我們的算法,考慮在生成圖的過(guò)程中如何避免龐大的節(jié)點(diǎn)個(gè)數(shù)以及在獨(dú)立的布爾表達(dá)式的生成過(guò)程中如何設(shè)計(jì)更高效的搜索算法.