劉國升，王偉嘉，郁 昱，姚 立，梁浩飛

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

2.泉城省實(shí)驗(yàn)室，濟(jì)南250103

3.山東大學(xué) 密碼技術(shù)與信息安全教育部重點(diǎn)實(shí)驗(yàn)室，青島266237

4.上海交通大學(xué) 電子信息與電氣工程學(xué)院，上海200240

1 引言

自從二十世紀(jì)九十年代Kocher 等人提出側(cè)信道攻擊(side-channel attack)[1]以來，這種技術(shù)就一直被認(rèn)為是密碼系統(tǒng)實(shí)現(xiàn)過程中的重大安全威脅.側(cè)信道攻擊主要利用系統(tǒng)設(shè)備在執(zhí)行過程中產(chǎn)生的功耗等行為信息恢復(fù)秘密數(shù)據(jù)，因此即使是在可證明安全模型下的密碼系統(tǒng)也會(huì)受到側(cè)信道攻擊的威脅[2].當(dāng)系統(tǒng)設(shè)備處理密碼算法相關(guān)數(shù)據(jù)與側(cè)信道泄漏(如運(yùn)行時(shí)間、功耗、電磁輻射、故障信息等) 之間存在數(shù)據(jù)依賴性時(shí)，攻擊者就可以利用這些泄漏信息恢復(fù)密鑰等秘密數(shù)據(jù)[2].側(cè)信道攻擊往往給用戶或系統(tǒng)帶來災(zāi)難性的后果，因此需要抵御這種攻擊，抵御這類攻擊的軟硬件措施稱為側(cè)信道防護(hù).

側(cè)信道防護(hù)的核心是消除或減少攻擊者能夠利用的具有數(shù)據(jù)依賴性的側(cè)信息.針對(duì)單一側(cè)信道攻擊的防護(hù)方法有兩類思路: 第一類是消除側(cè)信息的數(shù)據(jù)依賴性，例如在進(jìn)行有關(guān)秘密信息的計(jì)算時(shí)，使用在各個(gè)步驟時(shí)間恒定的算法，或使用掩碼方案將重要的中間變量隨機(jī)化，從而難以利用物理設(shè)備運(yùn)行密碼算法時(shí)產(chǎn)生的能量消耗;第二類是通過掩蓋側(cè)信息的某些特征使攻擊者無法加以利用，例如使用吸收材料消除聲、光、熱等側(cè)信息的泄漏，或是引入頻率接近的隨機(jī)干擾源，與密碼運(yùn)行設(shè)備同時(shí)釋放相同類型的側(cè)信息，從而達(dá)到側(cè)信道防御的目的.抵抗側(cè)信道攻擊還需從系統(tǒng)級(jí)層面綜合應(yīng)用多種側(cè)信道防護(hù)措施以達(dá)到最佳效果.

為了抵抗側(cè)信道攻擊，量化密碼算法執(zhí)行過程中的側(cè)信道泄漏以及合理評(píng)估密碼系統(tǒng)的安全性，密碼學(xué)家提出了一個(gè)重要的研究方向—抗泄漏密碼學(xué).在其考慮的場(chǎng)景中，攻擊者可以獲得有關(guān)內(nèi)部狀態(tài)的物理泄漏，密碼學(xué)家需要在此條件下構(gòu)造出抗泄漏的密碼方案，一些滿足抗泄漏安全性的方案也隨之產(chǎn)生.抗泄漏是指在一定泄漏模型下(計(jì)算模型、有界泄漏模型、無界泄漏模型和連續(xù)泄漏模型等)，假設(shè)攻擊者得到部分信息，設(shè)備仍然是安全的.在此框架下，許多抗泄漏密碼方案相繼被提出.例如在公鑰加密與數(shù)字簽名方面，Dachman-Soled 等人[3]用不可區(qū)分混淆構(gòu)造了抗泄漏的公鑰加密方案.

不可區(qū)分混淆(indistinguishability obfuscation，iO) 是指擁有同樣功能性的一類程序被混淆之后變得不可區(qū)分的特性.這一理論研究是由Barak 等人[4]發(fā)起的，他論證了虛擬黑盒(virtual black-box) 混淆的概念是不可能對(duì)所有電路實(shí)現(xiàn)的.當(dāng)Garg 等人[5]給出了第一個(gè)不可區(qū)分性混淆的候選構(gòu)造，并在后續(xù)的工作[6]中展示了如何在眾多密碼學(xué)上有用的方式中使用這個(gè)構(gòu)造時(shí)，iO才被真正重視起來.事實(shí)上，今天的iO被廣泛認(rèn)為是“完整的密碼學(xué)”，能夠基本上實(shí)現(xiàn)任何密碼學(xué)任務(wù).

幾年前Bartusek 等人[7]提出了一種特殊的候選混淆器，它用于混淆仿射行列式程序.仿射行列式程序(affine determinant program，ADP):{0，1}n →{0，1}是由一個(gè)有限域Fq上的方形矩陣元組(A，B1，B2，···，Bn) 和一個(gè)評(píng)估函數(shù)Eval: Fq → {0，1}來描述的，并通過計(jì)算Eval(det(A+來對(duì)進(jìn)行0，1}n評(píng)估.基于ADP 的候選混淆方案是獨(dú)一無二的，因?yàn)樗瞧駷橹刮ㄒ徊灰蕾嚾魏蝹鹘y(tǒng)密碼學(xué)假設(shè)(如離散對(duì)數(shù)或LWE) 的未被打破的候選方案.該候選者的描述也相對(duì)簡(jiǎn)單.此外，目前的量子技術(shù)在破解基于ADP 的候選方案方面似乎沒有顯示出特殊優(yōu)勢(shì).因此，如果LWE在未來被量子算法打破，ADP 的混淆候選方案可能是唯一對(duì)抗量子計(jì)算機(jī)的iO候選方案.

使用ADP 程序模型進(jìn)行混淆的想法也被用于Bartusek 等人的早期論文中[8]，他們實(shí)現(xiàn)了基于可證明的安全性.他們可以實(shí)現(xiàn)基于標(biāo)準(zhǔn)密碼學(xué)假設(shè)的可證明的安全性，然而混淆通用程序需要明顯不同的想法.所以Yao 等人[9]針對(duì)Bartusek 等人的iO候選方案[8]進(jìn)行了密碼分析攻擊.他們利用算法中一個(gè)隨機(jī)化步驟的弱點(diǎn)進(jìn)行攻擊，該攻擊適用于相當(dāng)普遍的一類程序，最后還提出了抵抗攻擊的合理對(duì)策.

本文對(duì)這種基于ADP 的iO方案進(jìn)行了改善.將整體密碼算法的ADP 編碼拆解成多個(gè)部分運(yùn)算再利用掩碼方案進(jìn)行組合，大大降低了對(duì)ADP 進(jìn)行iO時(shí)的運(yùn)算成本;另外結(jié)合側(cè)信道安全性定義，對(duì)iO過程進(jìn)行改善，刪除了小偶數(shù)噪聲和對(duì)角矩陣塊的構(gòu)造，加入了ADP 更新算法.改善后的防護(hù)方案可以在真實(shí)場(chǎng)景中進(jìn)行應(yīng)用，然后通過FPGA 功耗測(cè)試采集了足夠的曲線進(jìn)行Welch’s t-test，沒有明顯泄漏，實(shí)現(xiàn)了針對(duì)側(cè)信道攻擊的防護(hù).

2 預(yù)備知識(shí)

2.1 符號(hào)

本文應(yīng)用到的符號(hào): 使用PPT 表示概率多項(xiàng)式時(shí)間;使用粗體大寫字母表示矩陣;使用det(A) 表示求矩陣A的行列式;使用|A|表示矩陣A的階數(shù);使用λ表示安全參數(shù);使用[n]表示集合{1，2，···，n};使用· 表示數(shù)乘;使用⊕表示按位異或運(yùn)算;使用∧表示按位與運(yùn)算;使用?表示循環(huán)右移;使用ˉx表示二進(jìn)制對(duì)x取反.

2.2 SHA-2

安全散列算法2 (secure hash algorithm 2，SHA-2) 是美國國家安全局研發(fā)[10]的密碼散列函數(shù)算法標(biāo)準(zhǔn)，由美國國家標(biāo)準(zhǔn)與技術(shù)研究院(NIST) 在2001 年發(fā)布，屬于SHA 算法之一，是SHA-1 的后繼者.其下又可再分為六個(gè)不同的算法標(biāo)準(zhǔn)，包括了: SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256.

NIST 發(fā)布了三個(gè)額外的SHA 變體，這三個(gè)函數(shù)都將消息對(duì)應(yīng)到更長(zhǎng)的消息摘要.以它們的摘要長(zhǎng)度(以比特計(jì)算) 加在原名后面來命名: SHA-256、SHA-384 和SHA-512.它們發(fā)布于2001 年的FIPS PUB 180-2 草稿中，隨即通過審查和評(píng)論.包含SHA-1 的FIPS PUB 180-2，于2002 年以官方標(biāo)準(zhǔn)發(fā)布.2004年2 月，發(fā)布了一次FIPS PUB 180-2 的變更通知，加入了一個(gè)額外的變種SHA-224，這是為了符合雙密鑰3DES 所需的密鑰長(zhǎng)度而定義[11].

SHA-256 和SHA-512 是很新的散列函數(shù)，前者定義一個(gè)word 為32 位，后者則定義一個(gè)word 為64 位.它們分別使用了不同的偏移量，或用不同的常量，然而，實(shí)際上二者結(jié)構(gòu)是相同的，只在循環(huán)執(zhí)行的次數(shù)上有所差異.SHA-224 以及SHA-384 則是前述二種散列函數(shù)的截短版，利用不同的初始值做計(jì)算.

2.3 仿射行列式程序

定義1(分支程序)[9]分支程序(branching programs，BP) 由一個(gè)有向無環(huán)圖G(V，E)、兩個(gè)特殊頂點(diǎn)s，和一個(gè)標(biāo)記函數(shù)φ表示，該函數(shù)給E中的每條邊分配一個(gè)標(biāo)簽(即xi或) 或常數(shù)1.其大小表示|V|-1.每個(gè)輸入分配x(x1，x2，···，xn) 會(huì)自然生成出一個(gè)無標(biāo)簽的子圖Gx，其中每條邊，使x滿足φ(e).輸入x的可達(dá)路徑是圖Gx中的一條有向s-t路徑.如果對(duì)于每一個(gè)x，Gx的頂點(diǎn)出度最多為1，則BP 被稱為確定性的.因此，一個(gè)確定性的分支程序會(huì)計(jì)算出函數(shù)f:{0，1}n →{0，1}，當(dāng)且僅當(dāng)x上可達(dá)路徑的數(shù)量為1 時(shí)，f(x)1.

在該定義的基礎(chǔ)上可以定義一類新的分支程序，看作是確定性BP 的延展，其每個(gè)頂點(diǎn)的出度對(duì)所有x都不受1 的限制.這個(gè)新概念在混淆ADP 時(shí)很有幫助.

定義2(仿射行列式程序)[4]仿射行列式程序(affine determinant program，ADP) 由輸入長(zhǎng)度n、階數(shù)k和有限域Fq三個(gè)參數(shù)定義.它由仿射函數(shù)M:{0，1}n →和評(píng)估函數(shù)Eval : Fq →{0，1}組成.其中仿射函數(shù)M是在有限域Fq上的n+1 個(gè)k×k的矩陣元組M(A，B1，B2，···，Bn)，使得:

對(duì)于輸入0，1}n，計(jì)算ADPM，Eval(x)等價(jià)于計(jì)算Eval(det(M(x))).

評(píng)估函數(shù)Eval 一般有以下三種，通常會(huì)使用其中一個(gè).

ADP 需要由BP 編碼得到.假設(shè)有一個(gè)大小為l的分支程序，其中每個(gè)輸入最多有一條可達(dá)路徑.我們可以將該分支程序表示為一個(gè)大小為(l+1)×(l+1)的鄰接矩陣.該矩陣用M(x)來表示，其中的每個(gè)值都是0、1 或者一些變量(xi或ˉxi).由于BP 可以被看做DAG，那么矩陣M(x)中主對(duì)角線及以下的值均為0.因此可以將M(x)的主對(duì)角線元素修改為-1，并刪除最左邊一行和最下邊一列，得到一個(gè)l×l的新矩陣，稱之為L(zhǎng)(x).對(duì)于所有0，1}n，就有det(L(x))f(x).然后定義AL(0)，BiL(1i)-A，其中，0 是指所有輸入全為0，1i是指第i位輸入為1 而其他位全為0.對(duì)于所有的0，1}n，有

從而完成了ADP 的編碼，其中使用的評(píng)估函數(shù)是Eval0.Ishai 等人[12]詳細(xì)介紹了BP 到ADP 的編碼過程.

2.4 不可區(qū)分混淆

不可區(qū)分混淆 (indistinguishability obfuscation，iO) 是一種概率多項(xiàng)式時(shí)間 (probabilistic polynomial-time，PPT) 算法，在保留原功能的同時(shí)，將電路C轉(zhuǎn)化成混淆后的電路C′iO(C)，而且對(duì)于任何大小相同和功能相等的電路C1和C2，iO(C1) 和iO(C2) 在計(jì)算上是不可區(qū)分的.嚴(yán)格定義如下:

定義3(不可區(qū)分混淆器) 如果滿足以下條件，均勻PPT 工具iO就是電路{Cλ}的無差別混淆器:

· (保持強(qiáng)功能性) 對(duì)于所有的安全參數(shù)N+及所有的，有

· (不可區(qū)分性) 對(duì)于任意非均勻PPT 區(qū)分器D，存在一個(gè)可忽略的函數(shù)α使以下情況成立: 對(duì)于所有的N+，所有的電路對(duì)C0，C1，我們有，對(duì)于所有的輸入x，并且|C0||C1| (其中|C| 表示電路的大小)，如果C0(x)C1(x)，那么

iO是一類強(qiáng)大的密碼學(xué)原語，在密碼學(xué)和復(fù)雜性理論中有著廣泛的應(yīng)用.過去十年里，有許多iO候選方案被提出，可以分為以下四類:

· 基于多重線性映射(multilinear maps) 的候選方案.最初的iO方案是基于多重線性映射[13-15]建立的，由Garg 等人[5]進(jìn)行構(gòu)造.到目前為止，源于Garg 方案的一些變體依舊可以保持安全，但不是可證明安全也沒有使用強(qiáng)理論模型.

· 基于簡(jiǎn)要函數(shù)加密(functional encryption，F(xiàn)E) 的候選方案.一些優(yōu)秀的工作致力于從簡(jiǎn)潔FE方案中構(gòu)造iO，這些構(gòu)造都是基于有根據(jù)的假設(shè)，包括LPN 假設(shè)、配對(duì)密碼學(xué)中的DLIN 假設(shè)和NC0中的PRG 假設(shè)[16-26].這些構(gòu)造通過一系列的減法構(gòu)造出iO，并且利用了基于屬性的加密、全同態(tài)加密、基于二次函數(shù)的FE、同態(tài)秘密共享和通用電路等密碼學(xué)原理.這些方案整體結(jié)構(gòu)復(fù)雜，且效率低下.

· 基于非標(biāo)準(zhǔn)格假設(shè)的候選方案.Brakerski 等人[27-29]構(gòu)造了基于強(qiáng)循環(huán)安全假設(shè)的候選方案，Wee 等人[30]給出了一個(gè)基于類循環(huán)假設(shè)的方案，但Hopkins 等人[31]提供了這兩個(gè)假設(shè)的反例.除此之外，一些工作嘗試基于噪聲線性FE 構(gòu)造iO.Devadas 等人[32]在Wee 等人[30]的基礎(chǔ)上進(jìn)行了改進(jìn)，在簡(jiǎn)潔的LWE 采樣基礎(chǔ)上構(gòu)造iO.這是一個(gè)較弱的概念，它提出了一個(gè)候選者，其安全性與解多項(xiàng)式方程組的難度有關(guān).這些候選方案的安全性都依賴于非標(biāo)準(zhǔn)的假設(shè).

· 基于仿射行列式程序的候選方案.Bartusek 等人[8]提出了一種特殊的候選混淆方案，它用于混淆仿射行列式程序.仿射行列式程序(affine determinant program，ADP):{0，1}n →{0，1}是由一個(gè)有限域Fq上的方形矩陣元組(A，B1，B2，···，Bn) 和一個(gè)評(píng)估函數(shù)Eval: Fq →{0，1}來描述的，并通過計(jì)算Eval(det(A+∑i∈[n]xiBi)) 來對(duì)0，1}n進(jìn)行評(píng)估.非統(tǒng)一對(duì)數(shù)空間的計(jì)算(用L/poly 表示) 可以轉(zhuǎn)化為多項(xiàng)式大小的ADP.因?yàn)镹C1?L/poly，所以這種ADP 混淆器可以混淆NC1電路，這意味著可以構(gòu)造出通用的iO.

2.5 掩碼技術(shù)

掩碼技術(shù)[33]是指隨機(jī)化密碼設(shè)備所處理的中間值來實(shí)現(xiàn)側(cè)信道防護(hù)的一類技術(shù).在掩碼技術(shù)中，每個(gè)中間值v都基于一個(gè)稱為“掩碼” 的隨機(jī)數(shù)m進(jìn)行變換，即vmv*m，運(yùn)算* 通常根據(jù)密碼算法所使用的操作進(jìn)行定義，多為布爾異或運(yùn)算⊕、模加運(yùn)算+或模乘運(yùn)算×.在模加和模乘運(yùn)算的情況下，根據(jù)密碼算法選擇不同的模數(shù).采用多個(gè)掩碼的秘密共享是一種通用的掩碼實(shí)現(xiàn)方法，即將多個(gè)掩碼作用于同一個(gè)中間值，采用n個(gè)掩碼可以抵御n階DPA 攻擊[34].

在布爾掩碼中，中間值與掩碼進(jìn)行異或運(yùn)算，即vmv ⊕m.在算術(shù)掩碼中，中間值與掩碼進(jìn)行加法或乘法運(yùn)算，即vmv+mmodn或vmv×mmodn.有些算法會(huì)同時(shí)基于布爾運(yùn)算和算術(shù)運(yùn)算，因此需要同時(shí)采用兩種類型的掩碼技術(shù)，這將會(huì)帶來額外的計(jì)算開銷.

另外，密碼算法會(huì)使用線性和非線性函數(shù).線性函數(shù)可以通過上述掩碼技術(shù)來解決，而非線性函數(shù)一般采用查找表來實(shí)現(xiàn)，因此需要構(gòu)造對(duì)應(yīng)的掩碼型查找表Tm:Tm(v ⊕m)T(v)⊕m.這種表的生成非常簡(jiǎn)單，但是必須窮舉所有的掩碼m和輸入v，然后對(duì)應(yīng)記錄的結(jié)果.因此隨著查找表使用掩碼數(shù)量的增加，計(jì)算所占內(nèi)存也相應(yīng)增加.在降低計(jì)算開銷和提高效率方面，學(xué)術(shù)界相繼提出了一系列的改進(jìn)方法[35-37].

掩碼技術(shù)是一種被廣泛關(guān)注的防御對(duì)策，近年來已有大量文章提出了不同類型的掩碼方案、安全性證明及相關(guān)的元件級(jí)應(yīng)用.

3 基于ADP 的iO 方案

基于ADP 的候選方案是獨(dú)一無二的，因?yàn)樗瞧駷橹刮ㄒ徊灰蕾嚾魏蝹鹘y(tǒng)密碼學(xué)假設(shè)(如離散對(duì)數(shù)或LWE) 且未被打破的候選方案.此外，目前的量子技術(shù)在破解基于ADP 的iO方面似乎沒有顯示出特殊優(yōu)勢(shì).因此，如果LWE 在未來被量子算法打破，ADP 的混淆候選方案可能是唯一對(duì)抗量子計(jì)算機(jī)的iO候選方案.該方案通過四個(gè)構(gòu)造來混淆ADP[7]，每一個(gè)構(gòu)造都是在前一個(gè)的基礎(chǔ)上進(jìn)行改善，因此本節(jié)將按順序詳細(xì)介紹Bartusek 等人提出的iO方案[8]，本文后續(xù)內(nèi)容將會(huì)在這種iO方案的基礎(chǔ)上進(jìn)行改善及應(yīng)用.

3.1 隨機(jī)局部替換

隨機(jī)局部替換(random local substitutions，RLS) 的目標(biāo)是通過增加一些頂點(diǎn)和以某種隨機(jī)的方式修改邊來增加BP 的熵，我們用M′(x) 來表示修改后的BP.具體來說就是在每一個(gè)頂點(diǎn)對(duì)(vi，vj) 上添加一個(gè)中間節(jié)點(diǎn)vi，j.用M′(x) 的2×2 子矩陣表示該矩陣) 來舉例，所在行用vi和vi，j表示，所在列用vi，j和vj表示.

如果頂點(diǎn)vi，vj之間邊的標(biāo)簽值為1，那么有4 種隨機(jī)替換方法:

如果頂點(diǎn)vi，vj之間邊的標(biāo)簽值為0，那么有3 種替換方法:

如果頂點(diǎn)vi，vj之間邊的標(biāo)簽值為xi，那么有12 種替換方法:

此時(shí)ADP 的計(jì)算為:

3.2 添加小偶數(shù)噪聲

首先給出一個(gè)結(jié)論，對(duì)于任意多項(xiàng)式g:Zn →Z 及任意噪聲{eiZ}i∈[n]，有

因此，當(dāng)把ADP 作為輸入時(shí)，我們可以利用這個(gè)結(jié)論，向{A，{Bi}i∈[n]}中的每一項(xiàng)添加獨(dú)立隨機(jī)偶數(shù)作為噪聲.然后將加入噪聲后的矩陣定義為{A+2E0，Bi+2Ei}i∈[n].評(píng)估函數(shù)Eval 也需要改變，用Eval/=0代替Evalparity.

此時(shí)ADP 的計(jì)算為:

3.3 對(duì)角矩陣塊構(gòu)造

理想情況下，在混淆ADP 的時(shí)候，需要強(qiáng)制對(duì)手用預(yù)計(jì)的方式來計(jì)算程序.這個(gè)目標(biāo)可以通過增加矩陣隨機(jī)性來實(shí)現(xiàn)，只有按照固定的方式進(jìn)行計(jì)算才能消除隨機(jī)性，以其他方式組合矩陣將會(huì)使矩陣隨機(jī)性保持不變，從而隱藏原始ADP 的有效信息.通過采樣2n個(gè)行列式為1 的隨機(jī)矩陣{Gi，Hi}i∈[n]，然后將每個(gè)Gi沿對(duì)角線按矩陣塊的方式添加到矩陣A中，同時(shí)在Bi中對(duì)應(yīng)的第i個(gè)添加Hi-Gi.將處理后的矩陣定義為{diag(A，G1，G2，···，Gn)，{diag(Bi，0，···，0，Hi-Gi，0，···，0)}i∈[n]}.

此時(shí)ADP 的計(jì)算為:

3.4 矩陣重隨機(jī)化

重隨機(jī)化在整個(gè)混淆過程中應(yīng)用了兩次，第一次是在加入噪聲后，第二次是在構(gòu)造對(duì)角矩陣塊后.在這兩個(gè)步驟中，分別使用均勻的隨機(jī)矩陣U，V對(duì)每個(gè)矩陣進(jìn)行左乘和右乘，來實(shí)現(xiàn)ADP 的不可區(qū)分性，其中隨機(jī)矩陣需要滿足det(U)·det(V)1.Applebaum 等人[38]給出了詳細(xì)證明，這里簡(jiǎn)述一下思路:

假設(shè)存在M，M′，其中rank(M)M′r，det(M)det(M′)d.然后對(duì)兩個(gè)矩陣進(jìn)行矩陣的行變換和列變換，即左右各乘一個(gè)矩陣，使得

這就說明集合SQ和的大小是相同的，可以理解為M與M′變成某一個(gè)其他矩陣的概率是一樣大的，也就是兩個(gè)矩陣具有不可區(qū)分性.

綜合上述四個(gè)小節(jié)，最后ADP 的總計(jì)算過程為:

4 側(cè)信道防護(hù)方案設(shè)計(jì)

為了將上述混淆ADP 的候選方案應(yīng)用于側(cè)信道防護(hù)中，本文對(duì)上述方案進(jìn)行了改進(jìn).上述方案中使用的ADP 編碼過程是對(duì)整個(gè)程序進(jìn)行整體ADP 編碼，導(dǎo)致生成的ADP 矩陣占用內(nèi)存過大，而后續(xù)使用的混淆方案本身就需要大量的內(nèi)存消耗，所以對(duì)這些矩陣進(jìn)行混淆時(shí)，一旦矩陣規(guī)模稍大就會(huì)占用數(shù)GB甚至幾十GB 的內(nèi)存，這種防護(hù)方案的代價(jià)太大，無法在真實(shí)場(chǎng)景中實(shí)施，因此需要對(duì)這種方案進(jìn)行改進(jìn).本節(jié)利用了抗側(cè)信道的安全性定義弱于傳統(tǒng)不可區(qū)分混淆的安全性這一特性，對(duì)上述方案進(jìn)行了改進(jìn)，在實(shí)現(xiàn)側(cè)信道安全防護(hù)的同時(shí)使混淆程序的內(nèi)存占用大大減小，既能保證安全性又能提高效率，使其能夠在真實(shí)場(chǎng)景中進(jìn)行應(yīng)用.

4.1 總方案設(shè)計(jì)

ADP 需要滿足{0，1}n →{0，1}的映射，本文方案也同樣基于這個(gè)映射.方案分為兩部分: 線性操作和非線性操作.

線性操作就是簡(jiǎn)單的比特異或操作，將線性映射定義為f，則f(x1，x2，···，xn)x1⊕x2⊕···⊕xn，其中輸入xi {0，1}.

而非線性操作是基于查找表的一類ADP 設(shè)計(jì)，通過查找表畫出對(duì)應(yīng)的DAG，然后將DAG 轉(zhuǎn)化成BP，BP 編碼成ADP 從而實(shí)現(xiàn)非線性操作的ADP 編碼，這種做法可以將任意的非線性操作編碼為ADP.將非線性映射定義為g，即

其中輸入xi {0，1}，°表示非線性操作.而為了抵抗側(cè)信道攻擊，我們對(duì)這兩類操作加入了一階掩碼，能夠隱藏真實(shí)輸入并且更新ADP 矩陣，達(dá)到抗泄漏的效果.

原做法[7]中提到的ADP 主要是針對(duì)整體的密碼算法進(jìn)行ADP 編碼，而ADP 的特性是每多編碼一個(gè)變量，矩陣的規(guī)模就會(huì)以O(shè)(n2) 的速度增長(zhǎng)，這樣生成的矩陣占用內(nèi)存會(huì)很大，而經(jīng)過我們改良后的ADP 可以對(duì)這種規(guī)模較大的ADP 進(jìn)行拆分，也就是將整體的密碼算法拆解成多個(gè)部分的運(yùn)算再通過掩碼方案進(jìn)行組合，例如對(duì)x1⊕x2⊕···⊕xn進(jìn)行ADP 編碼，先進(jìn)行拆分，對(duì)其中的每一個(gè)運(yùn)算xi-1⊕xi(可以是一個(gè)運(yùn)算也可以是n個(gè)運(yùn)算)進(jìn)行獨(dú)立的ADP 編碼，通過掩碼方案產(chǎn)生一個(gè)隱蔽后的中間值xm，再進(jìn)行xm ⊕xi+1的編碼，最后將一個(gè)大規(guī)模的ADP 拆解成n-1 個(gè)小規(guī)模的ADP 從而降低對(duì)ADP進(jìn)行iO時(shí)的運(yùn)算成本，然后可以分別對(duì)這些拆分后的ADP 進(jìn)行iO構(gòu)造.

在對(duì)ADP 進(jìn)行混淆構(gòu)造時(shí)，我們采取了第3 節(jié)Bartusek 等人[8]提出的候選混淆方案.為了與本文的側(cè)信道防護(hù)方案進(jìn)行結(jié)合，對(duì)第3 節(jié)提出的方案進(jìn)行了改進(jìn).我們保留了3.1 節(jié)和3.4 節(jié)的構(gòu)造，去除了3.2 和3.3 節(jié)的構(gòu)造，原因如下:

由于本文方案設(shè)計(jì)用于側(cè)信道防護(hù)方向，而側(cè)信道攻擊本身就會(huì)產(chǎn)生大量的噪聲，這些噪聲對(duì)矩陣數(shù)據(jù)的影響比3.2 節(jié)添加的小偶數(shù)噪聲效果更好，因此無需生成大量隨機(jī)數(shù)來模擬噪聲，去掉這一構(gòu)造既能降低隨機(jī)數(shù)的消耗又不會(huì)導(dǎo)致安全性的降低.3.3 節(jié)對(duì)角矩陣塊是一種防護(hù)密碼分析攻擊(如多項(xiàng)式拓展攻擊) 的構(gòu)造，這類攻擊需要在模擬白盒的條件下進(jìn)行，即需要知道所有的輸入和輸出值，而我們的方案設(shè)計(jì)是針對(duì)側(cè)信道攻擊進(jìn)行防護(hù)，側(cè)信道防護(hù)的安全性定義弱于傳統(tǒng)密碼分析防護(hù)的定義，更遠(yuǎn)達(dá)不到白盒的條件，攻擊者并不能通過這個(gè)構(gòu)造的有無獲取任何有價(jià)值的信息，而且構(gòu)造對(duì)角矩陣塊會(huì)使得計(jì)算成本以O(shè)(n2) 的速度提高，是整個(gè)方案中內(nèi)存占用最大的部分，所以去掉這一構(gòu)造后既不會(huì)降低防護(hù)的安全性，又能大大降低資源消耗.

綜上所述，本文用到的iO方案為:

混淆ADP 方案的整體流程如算法1 所示.

4.2 ADP 更新

上述提及的一階掩碼，放入線性操作中即為

其中輸入xi {0，1}，隨機(jī)數(shù)mi {0，1}.想要得出正確結(jié)果，只需要將所有隨機(jī)數(shù)異或之后與計(jì)算結(jié)果進(jìn)行異或.非線性操作的隱藏過程與之相仿:

其中輸入xi {0，1}，隨機(jī)數(shù)mi {0，1}，°表示非線性操作.想恢復(fù)正確結(jié)果，需要對(duì)非線性操作對(duì)應(yīng)的查找表進(jìn)行分析，然后將所有隨機(jī)數(shù)進(jìn)行合適的處理后才能恢復(fù)正確結(jié)果，下一節(jié)中將舉例說明如何對(duì)非線性操作的結(jié)果進(jìn)行恢復(fù).

從函數(shù)f，g中可以看出，由于mi是隨機(jī)生成的，每進(jìn)行一次計(jì)算，mi就會(huì)發(fā)生一次變化，ADP 也會(huì)隨之更新，從而達(dá)到抗泄漏的效果，保證了ADP 的安全性.ADP 更新算法如算法2 所示.

本文設(shè)計(jì)的ADP 更新算法可以對(duì)ADP 矩陣進(jìn)行更新，即在每次運(yùn)行ADP 時(shí)生成的ADP 矩陣都不相同，這樣被混淆的程序進(jìn)行ADP 編碼后生成的矩陣具有不確定性，從而可以有效防止敵手進(jìn)行側(cè)信道攻擊恢復(fù)出原始ADP 矩陣，提高了該側(cè)信道防護(hù)方案的安全性.

5 側(cè)信道應(yīng)用

本節(jié)將第4 節(jié)提出的側(cè)信道防護(hù)方法針對(duì)具體的算法進(jìn)行應(yīng)用.

5.1 加法應(yīng)用

將上一節(jié)提到的防護(hù)方法用于加法中，首先給出一個(gè)基于不可區(qū)分混淆的ADP 加法器電路結(jié)構(gòu).加法器由兩部分組成: 本位和進(jìn)位.由于加法器是二進(jìn)制加法實(shí)現(xiàn)，所以本位只需對(duì)輸入進(jìn)行異或即可，而進(jìn)位函數(shù)如下:

其中x，y為加法的兩個(gè)輸入值，c為加法的進(jìn)位值，初始為0，c′為輸出結(jié)果，c′為輸出的進(jìn)位值，另有隨機(jī)數(shù)mx，my，mc，作為掩碼，隱藏輸入和輸出的值，其中mx，my，mc用于隱藏混淆ADP 加法器的輸入值，用于隱藏混淆ADP 加法器的中間輸出值且mx ⊕my ⊕mz.通過這個(gè)簡(jiǎn)易的加法器函數(shù)可以實(shí)現(xiàn)任意比特的加法操作.下面就要針對(duì)該函數(shù)編碼出對(duì)應(yīng)的ADP 并進(jìn)行混淆.

想要編碼ADP 需要對(duì)函數(shù)進(jìn)行分析后畫出對(duì)應(yīng)的DAG，然后將DAG 分解成BP，對(duì)BP 進(jìn)行編碼.函數(shù)g(x，y，c) 的運(yùn)算存在掩碼，那對(duì)于過程中隨機(jī)生成的掩碼(mx，my，mc) 會(huì)編碼出不同的ADP.

當(dāng)(mx，my，mc)(0，0，0) 時(shí)，有0，這種情況下掩碼并不會(huì)影響計(jì)算過程和結(jié)果(等同于無掩碼)，所以輸出為1 的情況有4 種:

當(dāng)(mx，my，mc)(0，1，1) 時(shí)，有0，這種情況下輸入值被掩碼隱藏，如果按照上述情況生成ADP 的話結(jié)果顯然是不正確的，因?yàn)檩敵鰹? 的情況有:

而當(dāng)(mx，my，mc)(0，0，1) 時(shí)，有1，這種情況下輸入和輸出值都被掩碼隱藏，其輸出結(jié)果為1 的情況有:

可以看出，對(duì)于不同的掩碼組合，相同的輸入并不會(huì)得到同樣的結(jié)果，因此針對(duì)不同的掩碼組合需要編碼不同的ADP，這里列出編碼ADP 所需的查找表:

因此對(duì)于這八種情況只需4 個(gè)DAG 即可表示全部情況.以(mx，my，mc)(0，1，1) 為例來介紹編碼ADP 及混淆ADP 的全過程.

首先畫出(mx，my，mc)(0，1，1) 對(duì)應(yīng)的DAG，如圖1 所示:

圖1 有向無環(huán)實(shí)例圖Figure 1 Example of directed acyclic graph

然后根據(jù)DAG 生成對(duì)應(yīng)的鄰接矩陣并對(duì)矩陣進(jìn)行初步處理(處理方法為減去最左一列和最下一行).

再將上述處理后的矩陣分解為仿射函數(shù)中的矩陣元組(A，B1，B2，···，Bn).

根據(jù)矩陣元組可以計(jì)算出ADP 的值:

接著對(duì)ADP 進(jìn)行混淆操作.混淆按照第4 節(jié)改進(jìn)后的iO方案進(jìn)行操作.第一步按照3.1 節(jié)隨機(jī)局部替換的做法對(duì)原始矩陣進(jìn)行RLS 操作，第二步進(jìn)行矩陣重隨機(jī)化操作，隨機(jī)生成兩個(gè)矩陣U、V，矩陣需滿足det(U)·det(V)1，利用這兩個(gè)矩陣可以實(shí)現(xiàn)det(UMV)det(UM′V) 從而實(shí)現(xiàn)矩陣的不可區(qū)分.

通過以上步驟實(shí)現(xiàn)對(duì)ADP 的iO操作從而實(shí)現(xiàn)完整的加法應(yīng)用.

5.2 SHA-2 及BIP-0032 應(yīng)用

傳統(tǒng)非確定性錢包是通過隨機(jī)數(shù)生成多個(gè)互不相關(guān)的私鑰.但是區(qū)塊鏈中的用戶為了保證自己的安全性往往會(huì)生成多個(gè)私鑰，以保證每次交易不會(huì)被追蹤，此時(shí)非確定性錢包會(huì)生成多個(gè)公私鑰對(duì)，這些密鑰需要反復(fù)備份.

為了解決傳統(tǒng)非確定性錢包每當(dāng)一批私鑰用完后必須重新生成一批私鑰并且及時(shí)備份的問題，分層確定性錢包的定義被提出.分層確定性錢包通過支持從單個(gè)根派生出多個(gè)密鑰對(duì)鏈.BIP-0032 定義了分層確定性錢包，系統(tǒng)會(huì)產(chǎn)生一個(gè)隨機(jī)種子，根據(jù)種子通過分層確定性推導(dǎo)的方式得到n個(gè)私鑰，這樣保存的時(shí)候，只需要保存一個(gè)種子就可以，私鑰可以推導(dǎo)出來.

BIP-0032 整體流程如下:

首先系統(tǒng)會(huì)使用橢圓曲線私鑰簽名算法SECP256K1 加密算法，利用熵(entropy) 函數(shù)產(chǎn)生一個(gè)隨機(jī)的128 比特種子S，然后將S通過HMAC-SHA512 哈希算法產(chǎn)生一組256 比特的父擴(kuò)展私鑰m和一組256 比特的鏈碼c，而m可以通過SECP256K1 生成父擴(kuò)展公鑰M.即

然后就可以使用到子密鑰派生(CKD) 函數(shù)，通過父擴(kuò)展私鑰求出下一級(jí)父私鑰，通過父擴(kuò)展公鑰生成下一級(jí)父私鑰，即

而上述都要用到HMAC-SHA512 哈希算法，算法3 給出SHA512 算法的主壓縮循環(huán)函數(shù).可以看到算法中除了非線性計(jì)算外，還存在7 個(gè)64 比特的加法，可以對(duì)這些64 比特加法進(jìn)行混淆從而抵抗側(cè)信道攻擊.

6 實(shí)驗(yàn)測(cè)試與分析

6.1 安全性測(cè)試

為了驗(yàn)證本算法的安全性，在ChipWhisperer STM32F4 目標(biāo)板上進(jìn)行泄漏評(píng)估.使用Picoscope 5244D 示波器，采樣率為20.8 MS/s，采集在線計(jì)算部分的功耗.首先對(duì)功耗曲線進(jìn)行簡(jiǎn)單的預(yù)處理，即進(jìn)行滑動(dòng)窗口平均，以減少噪音數(shù)據(jù).

這里采用的滑動(dòng)窗口平均是簡(jiǎn)單滑動(dòng)平均(simple moving average，SMA)，它是取前n個(gè)數(shù)據(jù)點(diǎn)的非加權(quán)平均值，而在工程領(lǐng)域，均值通常取自中心值兩側(cè)數(shù)量相等的數(shù)據(jù)，這樣可以確保平均值的變化與數(shù)據(jù)的變化保持一致，而不是隨著時(shí)間的推移而變化.然后參考了測(cè)試向量泄露評(píng)估(test vector leakage assessment，TVLA) 評(píng)估方法，TVLA 將泄漏評(píng)估與不斷發(fā)展的能量分析攻擊技術(shù)分離開來，將復(fù)雜的泄漏檢測(cè)問題轉(zhuǎn)化為簡(jiǎn)潔的數(shù)理統(tǒng)計(jì)步驟，使用固定的統(tǒng)計(jì)步驟來捕獲能量信息泄漏，且可以通過修改測(cè)試向量等方法來捕捉能量信息泄漏，并根據(jù)所需的安全要求調(diào)整閾值，具有簡(jiǎn)單高效等優(yōu)勢(shì).

把功耗曲線分為固定輸入組和隨機(jī)輸入組，兩組曲線間或采集，每組共采集25 000 條曲線.對(duì)預(yù)處理后的曲線，進(jìn)行Welch’s t-test 檢測(cè)[39].在統(tǒng)計(jì)學(xué)上，Welch’s t-test 是一種雙樣本位置檢驗(yàn)，用于檢驗(yàn)兩個(gè)總體均值相等的假設(shè).Welch’s t-test 是對(duì)Student’s t-test 的一種改編，當(dāng)兩個(gè)樣本的方差和樣本大小不相等時(shí)，其可靠性更高.當(dāng)比較的兩個(gè)樣本的統(tǒng)計(jì)單位不重疊時(shí)，通常會(huì)應(yīng)用這些檢驗(yàn).

將安全閾值設(shè)置為4.5，閾值所對(duì)應(yīng)的置信度為99.99%.4 bit 加法運(yùn)算時(shí)的評(píng)估結(jié)果如圖2 所示:

圖2 Welch’s t-test 結(jié)果Figure 2 Result of Welch’s t-test

可以看出t-test 結(jié)果并沒有尖端毛刺，均處于紅色虛線以內(nèi)，說明該算法并未產(chǎn)生側(cè)信道泄漏，算法的安全性可以得到驗(yàn)證.

6.2 效率分析

為了測(cè)試本算法的效率，對(duì)改進(jìn)后的混淆ADP 方案進(jìn)行了測(cè)試，測(cè)試的硬件環(huán)境為11th Gen Intel(R) Core(TM) i7-11700 @ 2.50 GHz 處理器.

首先測(cè)試?yán)迷摲雷o(hù)方案單獨(dú)實(shí)現(xiàn)64 比特加法的速度與在SHA512 上應(yīng)用該方案的運(yùn)行速度，測(cè)試結(jié)果如表1 所示.

表1 防護(hù)方案在不同場(chǎng)景下的運(yùn)行速度Table 1 Operational speed of protection solutions in different scenarios

然后對(duì)混淆ADP 占用的內(nèi)存進(jìn)行分析，對(duì)比分析混淆單ADP 占用內(nèi)存以及混淆ADP 加法器與編碼ADP 變量大小的關(guān)系，結(jié)果如圖3 所示:

圖3 ADP 占用內(nèi)存與變量大小的關(guān)系Figure 3 ADP memory usage vs.variable size

通過對(duì)比可以看出，采用加法器實(shí)現(xiàn)多比特加法所占用內(nèi)存(增長(zhǎng)速度O(n)) 遠(yuǎn)比直接進(jìn)行多比特加法編碼ADP 占用內(nèi)存(增長(zhǎng)速度O(n2)) 小得多.

最后測(cè)試混淆ADP 方案在ARM Cortex M4 處理器上執(zhí)行的數(shù)據(jù)，主要測(cè)試了不同加法位數(shù)在實(shí)現(xiàn)時(shí)的資源占用，測(cè)試說明該方案的計(jì)算成本及運(yùn)行速度都滿足實(shí)際應(yīng)用的條件.測(cè)試結(jié)果如表2 所示.

表2 混淆加法的空間占用Table 2 Memory usage of obfuscated addition

7 結(jié)語

本文提出了一種基于不可區(qū)分混淆的側(cè)信道防護(hù)方案，改進(jìn)基于ADP 的混淆方法，在保障側(cè)信道安全性的前提下大幅度提高運(yùn)行效率，從而給出可以執(zhí)行在嵌入式設(shè)備的側(cè)信道防護(hù)方法.通過功耗曲線采集對(duì)算法進(jìn)了泄漏評(píng)估，并未發(fā)現(xiàn)明顯泄漏，驗(yàn)證了工作的有效性.對(duì)比于傳統(tǒng)的側(cè)信道防護(hù)方案，該方案將不可區(qū)分混淆這一密碼學(xué)理論與側(cè)信道防護(hù)相結(jié)合，且抵抗側(cè)信道攻擊能力較好.

本方案的研究屬于側(cè)信道防護(hù)的范疇，而側(cè)信道的攻擊與防御技術(shù)在不斷交替發(fā)展，所以進(jìn)一步的研究可以圍繞如何在不降低運(yùn)行速度的前提下增強(qiáng)算法的安全性以及將iO與側(cè)信道防護(hù)深度結(jié)合等方面展開.