王 安,李 圓,丁瑤玲,祝烈煌,王永娟

1.北京理工大學(xué)計算機學(xué)院,北京 100081

2.河南省網(wǎng)絡(luò)密碼技術(shù)重點實驗室,鄭州 450001

1 引言

側(cè)信道攻擊通過利用密碼設(shè)備加密過程中泄露的功耗、電磁、時間等側(cè)信息,獲取敏感數(shù)據(jù).經(jīng)典的側(cè)信道攻擊方法有能量攻擊[1,2]、故障攻擊[3]、模板攻擊[4]、碰撞攻擊[5]等;近年來,出現(xiàn)一些基于人工智能的側(cè)信道攻擊方法,尤其是機器學(xué)習(xí)在側(cè)信道領(lǐng)域受到廣泛關(guān)注,包括支持向量機[6,7]、隨機森林[8,9]、多層感知器神經(jīng)網(wǎng)絡(luò)[10,11]、卷積神經(jīng)網(wǎng)絡(luò)[12-14]等.

文獻(xiàn)[15]提出一種非建模類的基于人工智能的側(cè)信道攻擊方法,將遺傳算法(genetic algorithm,GA)與相關(guān)能量分析(correlation power analysis,CPA)結(jié)合,應(yīng)用到密碼算法硬件實現(xiàn)場景下的側(cè)信道攻擊中,通過更高信噪比的泄露模型達(dá)到了超越傳統(tǒng)CPA的表現(xiàn).文獻(xiàn)[16]在其基礎(chǔ)上,針對其存在的早熟收斂的問題,使用多種群的方法,每個種群仍舊采用類似于文獻(xiàn)[15]的簡單遺傳算法,分別獨立進(jìn)化,但是對不同種群迭代結(jié)束得到的最優(yōu)個體進(jìn)行“組合”,來獲取更優(yōu)的個體,這種方法可以一定程度上克服早熟收斂的問題.

學(xué)界有很多關(guān)于多種群遺傳算法的研究.文獻(xiàn)[17]提出基于多種群的強者進(jìn)化遺傳算法,使用多個單種群和一個主種群進(jìn)行兩階段進(jìn)化,第一階段由多個異構(gòu)單種群單獨進(jìn)化到一定代數(shù),將各自的最優(yōu)個體傳遞給主種群,第二階段進(jìn)行由強者構(gòu)成的主種群的進(jìn)化,使用自定義的變異算子.文獻(xiàn)[18]提出變搜索區(qū)域多種群遺傳算法,依據(jù)各種群最優(yōu)個體的分布不斷縮小搜索區(qū)域,并且隨著搜索區(qū)域減小種群規(guī)模成正比減小,新種群中的個體一部分來自該區(qū)域已存在的優(yōu)秀個體,另一部分由隨機均勻方法產(chǎn)生.文獻(xiàn)[19]提出一種改進(jìn)的雙種群遺傳算法.同時進(jìn)化兩個種群,一個種群讓高相似個體之間具有相對高的交叉率,注重局部搜索;另一個種群讓低相似個體之間具有相對高的交叉率,注重全局搜索,在兩個種群間使用移民,使得算法兼具較強的局部搜索與全局搜索能力.文獻(xiàn)[20]使用兩個輔助種群和一個主種群,三個種群分別獨立進(jìn)化,每完成一次種群更新,都用兩個輔助種群的最優(yōu)個體替換主種群中最差的兩個個體.文獻(xiàn)[21]采用多個普通種群和一個優(yōu)良種群,通過縱橫協(xié)同方式進(jìn)化多輪,以實現(xiàn)多種群之間的信息共享和優(yōu)勢互補,一定程度克服了遺傳算法的早熟收斂特性.文獻(xiàn)[22]常用于解決多目標(biāo)優(yōu)化,通過設(shè)置不同的控制參數(shù)或目標(biāo)函數(shù),并且通過移民算子相互引入種群中的優(yōu)秀個體,實現(xiàn)種群協(xié)同進(jìn)化,并設(shè)置精英種群用以保留每代的最優(yōu)個體,避免早熟收斂.

本文在文獻(xiàn)[16]的基礎(chǔ)上針對由多個種群獨立進(jìn)化得到的優(yōu)秀個體間的結(jié)合策略進(jìn)行探究,提出小組賽、投票法及二次進(jìn)化三種結(jié)合策略.小組賽不再采用文獻(xiàn)[16]中第一個種群與之后每個種群中最優(yōu)個體相繼組合的方式,而是將優(yōu)秀個體進(jìn)行兩兩分組,再進(jìn)行組合.投票法通過讓所有優(yōu)秀個體進(jìn)行投票,決出一個最優(yōu)個體.二次進(jìn)化與文獻(xiàn)[17]相似,但是采用的是多個同構(gòu)單種群,且在再次進(jìn)化時,通過使用穩(wěn)態(tài)遺傳的方式,并且選擇合適的參數(shù),加快收斂速度.將上述三種策略與文獻(xiàn)[16]的方法從成功率和計算代價兩個角度進(jìn)行了對比實驗,并對結(jié)果進(jìn)行了分析.

文章接下來的結(jié)構(gòu):第2節(jié)介紹預(yù)備知識,包括CPA、簡單遺傳算法、穩(wěn)態(tài)遺傳算法、基于簡單遺傳算法的CPA和基于多種群遺傳算法的CPA;第3節(jié)介紹小組賽、投票法和二次進(jìn)化這三種結(jié)合策略的思想和算法步驟;第4節(jié)介紹遺傳算法的參數(shù)選取;第5節(jié)介紹效率對比實驗;第6節(jié)總結(jié)和討論.

2 預(yù)備知識

2.1 相關(guān)能量分析

漢明距離模型與漢明重量模型是能量分析中兩種常用能量模型,用于將操作數(shù)映射為能量消耗值,作為對設(shè)備的能量仿真.x的漢明重量HW(x)等于二進(jìn)制形式x中為1的比特數(shù)量,x與y之間的漢明距離HD(x,y)=HW(x⊕y),漢明重量(距離)模型認(rèn)為能量消耗與兩個操作數(shù)的漢明重量(距離)呈線性關(guān)系.公式(1)代表能量消耗與操作數(shù)間的線性關(guān)系模型,其中T代表能量消耗,a是標(biāo)量增益,H代表操作數(shù)的漢明重量或漢明距離,b包含偏移量、與時間相關(guān)的分量及噪聲.

CPA基于能量模型和相關(guān)系數(shù)恢復(fù)密鑰,下面以恢復(fù)AES-128算法密鑰第一字節(jié)為例對CPA分兩階段進(jìn)行介紹,分別是數(shù)據(jù)準(zhǔn)備階段和分析階段.假設(shè)攻擊位置是AES-128第一輪S盒的輸出,能量消耗服從漢明重量模型.在數(shù)據(jù)準(zhǔn)備階段,攻擊者需獲取一組明文波形對,波形是指在固定密鑰、隨機明文下加密時位于攻擊位置時刻的真實能量消耗值.用k代表密鑰字節(jié)的可能取值,k有256種取值.在分析階段,首先使用公式(2)計算與k相關(guān)的操作數(shù)m,其中p代表一字節(jié)明文,Sbox代表AES-128的S盒運算;再計算m下的漢明重量H=HW(m),依據(jù)公式(1)計算假設(shè)能量消耗T,依據(jù)相關(guān)系數(shù)計算公式(3)計算假設(shè)能量消耗H與波形T的相關(guān)系數(shù);k有256種取值,所以k參與運算的m、H、ρH,T相應(yīng)也有256種取值,最后找到最大相關(guān)系數(shù)所對應(yīng)的密鑰字節(jié)取值,認(rèn)為是該密鑰字節(jié)的正確取值.其余密鑰字節(jié)也采取同樣的方式進(jìn)行恢復(fù).

2.2 簡單遺傳算法和穩(wěn)態(tài)遺傳算法

GA是一類模擬生物進(jìn)化過程、用于解決優(yōu)化或搜索問題的啟發(fā)式算法.對GA的描述涉及“個體”、“種群”、“代”、“適應(yīng)度”、“選擇”、“交叉”和“變異”等概念.其中,“個體”指問題的一個候選解,需進(jìn)行編碼表示,二進(jìn)制編碼是一種常見方式.“種群”由一組個體構(gòu)成,比如由N個個體構(gòu)成,則種群規(guī)模大小就是N.由一個初始種群,繁殖產(chǎn)生新的一組個體,這組個體又構(gòu)成一個種群,繼續(xù)繁殖產(chǎn)生新個體,整個繁殖過程不斷迭代,每次迭代產(chǎn)生一“代”個體.“適應(yīng)度”用于評估個體的優(yōu)劣,計算方法基于目標(biāo)函數(shù).“選擇”類似于生物界的自然選擇,選擇策略有多種,但共同原則是讓更優(yōu)的個體以更大概率被保留下來并進(jìn)行交叉和變異.“交叉”和“變異”是產(chǎn)生新個體的方式,類似于生物界的染色體交叉和變異,表1描述了8比特表示的個體間的單點交叉,箭頭位置代表交叉點.表2描述了8比特表示的個體的單比特變異,粗斜體標(biāo)識的比特發(fā)生了變異.

表1 單點交叉Table 1 One-point crossover

表2 單比特變異Table 2 One-bit mutation

GA的過程可描述為:首先初始化一個種群作為初代,接著不斷迭代繁殖.繁殖過程中,種群中每個個體需要計算適應(yīng)度.繼而通過選擇策略,讓適應(yīng)度更高的個體以更大概率被選中,未被選中的個體將被淘汰,以此提高整個種群的平均適應(yīng)度.被選中的個體作為父代,再以一定概率進(jìn)行交叉和變異產(chǎn)生子代個體.子代個體是否替換父代進(jìn)入下一代取決于遺傳方式,對于簡單遺傳算法,子代將替換父代進(jìn)入下一代,對于穩(wěn)態(tài)遺傳算法,子代只有適應(yīng)度高于父代,才能替換父代進(jìn)入下一代.種群的下一代重復(fù)同樣的繁殖過程,不斷迭代至算法收斂到一個最優(yōu)解.

2.3 基于簡單遺傳算法的CPA

在硬件實現(xiàn)的密碼算法中,同一時刻多個S盒運算并行執(zhí)行.對這類算法進(jìn)行經(jīng)典CPA,若只利用其中一個S盒的信息量,其余S盒的信息量就只能被視作噪聲,導(dǎo)致低信噪比.將多個S盒的假設(shè)能量消耗相加,與波形計算相關(guān)系數(shù),所得結(jié)果比單個S盒的假設(shè)能量消耗與波形的相關(guān)系數(shù)要高,且S盒的數(shù)量越多,相關(guān)系數(shù)越高.經(jīng)典CPA若要利用全部S盒的信息量,以提高信噪比,獲得更大的相關(guān)系數(shù),會導(dǎo)致巨大的搜索空間.因此,文獻(xiàn)[15]提出基于簡單遺傳算法的CPA,利用了全部S盒的信息量,且遺傳算法的啟發(fā)式搜索特性使得巨大的搜索空間也變得可行,相比經(jīng)典CPA,信噪比提高,因而攻擊效率也得到顯著提高.

算法首先初始化一組密鑰猜測,作為初始種群,這一步驟用函數(shù)Selection()表示;種群適應(yīng)度的計算通過將各個S盒的假設(shè)能量消耗相加與波形計算相關(guān)系數(shù),這一步驟用函數(shù)CalculateFitness()表示;隨后選擇適應(yīng)度大的個體,按一定交叉概率和變異概率進(jìn)行交叉和變異,其中交叉操作用函數(shù)Crossover()表示,變異操作用函數(shù)Mutation()表示,交叉和變異以字節(jié)為單位,交叉策略見表1,變異策略見表2;種群不斷迭代,直至找到正確密鑰或者達(dá)到繁殖代數(shù)上限. 具體步驟見算法1,我們將這個算法稱作SGA_CPA().

算法1基于簡單遺傳算法的CPA Input:繁殖代數(shù)上限gen_thre,種群規(guī)模N,交叉率p c,變異率p m,明文plaintext,波形trace Output:最優(yōu)個體best_key 1 count_gen←0;2 Initialize(pop,N); //初始化種群3 while count_genFitness(comebine_key)then 14 comebine_key[i]:=tmp[i];15 else 16 tmp[i]:=comebine_key[i];17 end 18 end 19 end 20 if Equal(combine_key,right_key=true)then 21 break;22 end 23 else 24 return best_key; //如果單種群找到正確密鑰,則輸出25 end 26 end 27 return combine_key;

2.4 基于多種群遺傳算法的CPA

基于簡單遺傳算法的CPA存在早熟收斂問題,尤其在S盒大、數(shù)量多的時候.為了克服這個問題,文獻(xiàn)[16]提出基于多種群遺傳算法的CPA.雖然單個種群在進(jìn)化時由于早熟收斂,最終只能猜對部分密鑰字節(jié),但各個種群基本都能猜對差不多數(shù)量的密鑰字節(jié),并且猜對的密鑰字節(jié)序數(shù)也有不同,通過收集多個種群的最優(yōu)個體,進(jìn)行“組合”,有機會恢復(fù)全部密鑰字節(jié).算法首先讓第一個單種群進(jìn)化得到一個最優(yōu)個體,記為combine_key,若沒有得到正確密鑰,則開始新的單種群進(jìn)化,得到的最優(yōu)個體記為individual.individual如果也不是正確密鑰,則對combine_key和individual進(jìn)行“組合”,“組合”后的結(jié)果仍記為combine_key,若仍不是正確密鑰,則繼續(xù)新的單種群進(jìn)化,得到的最優(yōu)個體繼續(xù)與combine_key“組合”,直到恢復(fù)密鑰成功或達(dá)到種群個數(shù)上限.其中“組合”是指:依次將combine_key中各字節(jié)取值替換為individual中相應(yīng)字節(jié)取值,并重新計算適應(yīng)度,若適應(yīng)度低于原來的combine_key,則還原該字節(jié).具體步驟見算法2.

多種群中各個單種群進(jìn)化方式仍采用算法1,只是選擇、交叉和變異的策略進(jìn)行了改進(jìn).選擇策略采用算法3截斷選擇的方式,只在適應(yīng)度靠前的一段范圍內(nèi)選擇個體.交叉策略采用算法4按字節(jié)交叉的方式,交換的是個體間的字節(jié).變異策略采用算法5按字節(jié)隨機變異的方式,變異方向為一字節(jié)內(nèi)的任意取值.

算法3截斷選擇Input:按適應(yīng)度從高到低排序的種群Pop,種群規(guī)模N,截斷選擇閾值p t Output:選中的個體individual 1 i←Random(1,N×p t);2 individual:=Pop[i];3 return individual;算法4按字節(jié)交叉Input:要交叉的兩個個體individual1,individual2,交叉率p c Output:更新后的兩個個體individual1,individual2 1 for i←1 to n word do 4 tmp:=individual1[i];2 r:=Random(0,1);3 if r

3 多種群遺傳算法個體結(jié)合策略

基于多種群遺傳算法的CPA使用多個單種群,分別進(jìn)化得到多個優(yōu)秀個體,通過對個體進(jìn)行組合以利用各個個體的信息量來克服遺傳算法容易早熟收斂的缺點.如何充分利用優(yōu)秀個體的信息量獲取正確密鑰,是基于多種群遺傳算法的相關(guān)能量分析中個體結(jié)合策略要解決的問題.接下來分別介紹“小組賽”、“投票”及“二次進(jìn)化”這三種個體結(jié)合策略,以及基于這三種策略的多種群遺傳算法與CPA的結(jié)合.

3.1 小組賽

基于小組賽多種群遺傳算法的CPA,本文簡稱為小組賽.文獻(xiàn)[16]中個體結(jié)合策略通過將第一個種群的最優(yōu)個體依次與之后的種群得到的最優(yōu)個體進(jìn)行組合,小組賽仍舊使用相同的組合方式,這個方式在2.4節(jié)已經(jīng)介紹,與文獻(xiàn)[16]不同的是小組賽使用了另一種組合順序.圖1描述了種群個數(shù)上限為8時小組賽的組合順序,類似于一棵倒置的二叉樹,所以種群個數(shù)需是2的整數(shù)次方,圖中每個圓圈代表一個優(yōu)秀個體,種群1、種群2的最優(yōu)個體最先進(jìn)行組合,得到的結(jié)果記為組合1.接下來種群3和種群4組合,得到的結(jié)果記為組合2,然后組合1和組合2組合,得到的結(jié)果記為組合3.種群5至種群8的組合順序類似于種群1至種群4,依次產(chǎn)生的結(jié)果是組合4至組合6,最后由組合3與組合6產(chǎn)生組合7.組合1至6任意一個為正確密鑰時,程序就會結(jié)束,不再繼續(xù)新的單種群進(jìn)化和組合.小組賽中各個單種群的進(jìn)化方式與2.4節(jié)中的單種群進(jìn)化方式相同,具體步驟見算法6.

圖1 小組賽示例Figure 1 Group match example

3.2 投票法

基于投票法多種群遺傳算法的CPA,本文簡稱為投票法.投票法首先需要收集各個種群進(jìn)化得到的最優(yōu)個體,并且讓每個個體對密鑰各個字節(jié)的可能取值進(jìn)行投票,再根據(jù)投票結(jié)果決出最終輸出密鑰各個字節(jié)的取值.個體對密鑰第一字節(jié)最基本的投票方式是讓該個體第一字節(jié)的取值得1票,但這種方式對于適應(yīng)度不同的個體的投票權(quán)重是一樣的,有可能導(dǎo)致適應(yīng)度最高的個體的各字節(jié)的取值不能脫穎而出,因而更合適的投票方式是令個體在該字節(jié)的取值增加的票數(shù)為個體的適應(yīng)度,其余密鑰字節(jié)也采取同樣方式.最后統(tǒng)計各個字節(jié)在各個可能取值下的票數(shù),每個字節(jié)得票最多的取值作為最終輸出密鑰在該字節(jié)的取值.投票法中各個單種群的進(jìn)化方式與2.4節(jié)中的單種群進(jìn)化方式相同,具體步驟見算法7.在單種群進(jìn)化不能收斂到全局最優(yōu)時,投票法需要先收集全部單種群的最優(yōu)個體,沒有中間結(jié)果來輔助判斷是否找到正確密鑰.而文獻(xiàn)[16]及小組賽在各個單種群進(jìn)化結(jié)束時,通過組合產(chǎn)生的新個體可輔助判斷是否找到正確密鑰,有機會不需要等到全部單種群進(jìn)化結(jié)束就可以結(jié)束程序.投票法方式一次性對全部優(yōu)秀個體統(tǒng)一進(jìn)行整合,文獻(xiàn)[16]及小組賽對優(yōu)秀個體分階段進(jìn)行整合.

3.3 二次進(jìn)化

基于二次進(jìn)化多種群遺傳算法的CPA,本文簡稱為二次進(jìn)化.文獻(xiàn)[16]、小組賽及投票法利用的信息量全部來自于各個種群進(jìn)化得到的最優(yōu)個體,如果這些個體各個字節(jié)的取值沒有全部覆蓋正確密鑰各個字節(jié)的取值,那么上述方法都不能夠成功恢復(fù)密鑰.二次進(jìn)化分兩階段,第一階段先讓各個單種群分別獨立進(jìn)化,進(jìn)化方式與2.4節(jié)中的單種群進(jìn)化方式相同,第二階段將各個單種群進(jìn)化得到的最優(yōu)個體構(gòu)成一個初始種群,進(jìn)行再次進(jìn)化,由于進(jìn)化過程中涉及交叉和變異操作,使得原本錯誤的部分密鑰字節(jié)有機會進(jìn)化正確,從而成功恢復(fù)密鑰,具體步驟見算法8.

算法6基于小組賽多種群遺傳算法的CPA Input:繁殖代數(shù)上限gen_thre,種群規(guī)模N,種群個數(shù)上限pop_thre,截斷選擇閾值p t,交叉率p c,變異率p m,明文plaintext,波形trace Output:最優(yōu)個體best_key 1 height←log2 pop_thre+1;2 count_pop←0;3 while count_pop

圖2比較了二次進(jìn)化第二階段分別使用簡單遺傳、簡單遺傳和保留全局最優(yōu)的組合、穩(wěn)態(tài)遺傳時的效果,三種方法在二次進(jìn)化第二階段的種群規(guī)模都等于第一階段進(jìn)化所使用的種群個數(shù)上限,這里統(tǒng)一設(shè)置為35,使用100次仿真實驗統(tǒng)計每10代最優(yōu)個體的平均正確密鑰字節(jié)數(shù).可以看到,使用簡單遺傳的二次進(jìn)化完全沒有收斂,這與種群規(guī)模太小有關(guān);使用簡單遺傳并且保留全局最優(yōu)的方式進(jìn)行二次進(jìn)化,種群收斂非常緩慢;使用穩(wěn)態(tài)遺傳方式進(jìn)行二次進(jìn)化,種群收斂速度最快.故二次進(jìn)化第二階段選用穩(wěn)態(tài)遺傳方式進(jìn)化,產(chǎn)生的子代個體只有適應(yīng)度高于相應(yīng)父代,才能替換父代被保留下來,這樣適應(yīng)度高于所產(chǎn)生子代的父代始終能被保留,種群整體穩(wěn)步向適應(yīng)度更高的方向進(jìn)化.

圖2 三種遺傳方式比較Figure 2 Comparison of three genetic methods

算法8基于二次進(jìn)化多種群遺傳算法的CPA Input:繁殖代數(shù)上限gen_thre,種群規(guī)模N,種群個數(shù)上限pop_thre,截斷選擇閾值p t,交叉率p c,變異率p m,二次進(jìn)化的子代更新比例r,二次進(jìn)化的繁殖上限sgen_thre,二次進(jìn)化的交叉率sp c,二次進(jìn)化的變異率sp m,明文plaintext,波形trace Output:最優(yōu)個體best_key 1 count_pop←0;2 while count_popFitness(p1)then 22 p1:=c1;23 end 24 if Fitness(c2)>Fitness(p2)then 25 p1:=c2;26 end 27 end 28 best_key:=MaxFitness(pop_good); //尋找適應(yīng)度最高的個體29 if Equal(best_key,right_key=true)then 30 break;31 end 32 end 33 return best_key;

4 參數(shù)選取

4.1 單種群遺傳算法參數(shù)選取

文獻(xiàn)[16]已經(jīng)針對單種群遺傳算法涉及的參數(shù)及多種群時的種群個數(shù)上限進(jìn)行過選參,最終擇優(yōu)選取的參數(shù)包括,種群規(guī)模500,繁殖代數(shù)上限150,截斷閾值0.4,交叉率0.5,變異率0.12,種群個數(shù)上限35.小組賽和投票法中的單種群遺傳算法也將采用這一組參數(shù),其中小組賽的種群個數(shù)上限需是2的整數(shù)次方,故不采用35,而是32.投票法需要在多個種群迭代結(jié)束后才能進(jìn)行票數(shù)統(tǒng)計決出各個密鑰字節(jié)的取值,考慮到計算復(fù)雜度,種群個數(shù)上限不宜設(shè)置過大,設(shè)置過小會影響投票結(jié)果的正確性,故仍舊設(shè)置為35.二次進(jìn)化所需的初始種群來源于多個單種群的最優(yōu)個體,這些個體越好,二次進(jìn)化第二階段越容易收斂到正確密鑰,因而對于單種群的選參,仍舊參考文獻(xiàn)[16],即截斷閾值0.4,交叉率0.5,變異率0.12.考慮到二次進(jìn)化第二階段仍然需要計算適應(yīng)度,為了避免過高的計算復(fù)雜度,單種群參數(shù)設(shè)置也有不同之處,包括種群規(guī)模設(shè)置為200,繁殖代數(shù)上限設(shè)置為100.

4.2 二次進(jìn)化參數(shù)選取

二次進(jìn)化第二階段涉及種群個數(shù)上限、子代更新比例、繁殖代數(shù)上限、交叉率和變異率這5個參數(shù)的選取,下面將通過實驗選取合適參數(shù)值.

4.2.1 種群個數(shù)上限與子代更新比例

種群個數(shù)上pop_thre直接決定二次進(jìn)化第二階段時的種群規(guī)模,而使用穩(wěn)態(tài)遺傳的二次進(jìn)化,子代數(shù)量為r×pop_thre,r代表子代更新比例,即每代產(chǎn)生的子代個體數(shù)量與種群規(guī)模的比值,這兩個參數(shù)共同影響收斂速度,故對種群個數(shù)上限pop_thre和子代更新比例r進(jìn)行組合尋優(yōu).由于文獻(xiàn)[16]中種群個數(shù)上限為35,而二次進(jìn)化涉及繼續(xù)迭代,為了避免過大的計算復(fù)雜度,這里測試種群個數(shù)上限的范圍為[10,35],步長為5,測試子代更新比例的范圍為[0.2,1],步長為0.2.對種群個數(shù)上限和子代更新比例的各個組合進(jìn)行100次仿真實驗,統(tǒng)計每50代的最優(yōu)個體平均正確密鑰字節(jié)數(shù),繁殖代數(shù)上限為8000,每次實驗使用180條仿真波形,噪聲標(biāo)準(zhǔn)差為3.實驗結(jié)果如圖3,可以看到,當(dāng)種群個數(shù)和子代更新比例分別是最大值35和最大值1時,平均正確密鑰字節(jié)數(shù)最高,為15.34,但此時次優(yōu)點15.24也不錯,對應(yīng)種群個數(shù)上限與子代更新比例的組合為(30,1),此時計算復(fù)雜度更低,所以后續(xù)實驗將采用這組參數(shù).

圖3 種群個數(shù)與子代更新比例選參Figure 3 Selection of pop_thre and r

4.2.2 第二階段繁殖代數(shù)上限

圖4是上述實驗結(jié)果的另一種表示方式,每一條線代表種群個數(shù)上限與子代更新比例的一個組合,展示了隨著繁殖代數(shù)上升,平均正確密鑰字節(jié)數(shù)的變化.其中紅色線代表種群個數(shù)上限與子代更新比例的最優(yōu)組合(35,1),綠色線代表次優(yōu)組合(30,1),灰色線代表其他組合.上面已經(jīng)分析過后續(xù)實驗會采用次優(yōu)組合,從圖中可看出次優(yōu)組合在2500代時已經(jīng)收斂,故后續(xù)實驗的二次進(jìn)化第二階段繁殖代數(shù)上限設(shè)置為2500.

圖4 不同種群個數(shù)與子代更新比例表現(xiàn)Figure 4 Peformance of pop_thre and r

4.2.3 交叉率和變異率

二次進(jìn)化第二階段采用穩(wěn)態(tài)遺傳方式,其收斂速度與簡單遺傳方式不同,故不再采取與前面簡單遺傳一致的交叉率和變異率,而是對交叉率和變異率的組合進(jìn)行新的尋優(yōu).交叉率的測試范圍[0.1,0.5],步長0.1,變異率的測試范圍[0.05,0.15],步長0.01,每次實驗使用130條仿真波形,噪聲標(biāo)準(zhǔn)差為3,進(jìn)行100次實驗,統(tǒng)計平均正確密鑰字節(jié)數(shù).實驗結(jié)果如圖5,(交叉率,變異率)存在兩個最優(yōu)組合,分別是(0.1,0.14)和(0.15,0.12),后續(xù)實驗采取的組合是(0.15,0.12).

圖5 二次進(jìn)化交叉率與變異率選參Figure 5 Selection of crossover rate and mutation rate for secondary evolution

5 效率對比實驗

5.1 仿真實驗

仿真實驗針對AES-128算法,攻擊位置為第一輪S盒的輸出.假定仿真波形服從漢明重量模型,噪聲服從高斯分布,噪聲標(biāo)準(zhǔn)差為3.探究文獻(xiàn)[16]中多個種群進(jìn)化得到的最優(yōu)個體間的結(jié)合策略、小組賽、投票法及二次進(jìn)化這四種方法在同一組波形上的表現(xiàn),下面將文獻(xiàn)[16]中使用的方法簡稱為原始方法.在多組不同數(shù)量的波形下均進(jìn)行了實驗,波形數(shù)量的范圍[100,500],步長為10.每組波形進(jìn)行100次實驗統(tǒng)計四種方法的成功率和計算代價,其中計算代價用適應(yīng)度的計算次數(shù)表示.

原始方法使用的參數(shù)包括(種群規(guī)模,單種群繁殖上限,截斷閾值,交叉率,變異率,種群個數(shù)上限),對應(yīng)取值為(500,150,0.4,0.5,0.12,35),小組賽使用的參數(shù)類型相同,對應(yīng)取值為(500,150,0.4,0.5,0.12,32).投票法使用與原始方法完全一致的一組參數(shù).二次進(jìn)化也使用到原始方法涉及的參數(shù)類型,對應(yīng)取值為(200,100,0.4,0.5,0.12,30),除此之外,還有二次進(jìn)化第二階段進(jìn)行穩(wěn)態(tài)遺傳時涉及的參數(shù),包括(繁殖代數(shù)上限,交叉率,變異率,子代更新比例),對應(yīng)取值為(2500,0.15,0.12,1).

四種方法成功率對比如圖6,計算代價對比如圖7.二次進(jìn)化在190條波形時成功率達(dá)到91%,計算代價0.63×106,同樣的波形條數(shù),原始方法、小組賽和投票法的成功率分別為60%、57%和22%,計算代價分別為1.60×106、1.66×106和2.24×106.同樣的波形條數(shù)下,二次進(jìn)化的成功率最高,投票法的成功率最低,原始方法與小組賽的成功率接近;對于計算代價,波形數(shù)不超過200條時,二次進(jìn)化的計算代價最小,投票法的計算代價最大,其余兩種方法介于中間,且計算代價接近,這是因為在波形數(shù)量少時,單個種群很難收斂到全局最優(yōu),投票法需要在各個單種群進(jìn)化結(jié)束后才能決出最終密鑰,二次進(jìn)化雖然也需要在各個單種群進(jìn)化結(jié)束后才進(jìn)入第二階段,但是二次進(jìn)化中種群規(guī)模和單種群繁殖上限設(shè)置得小很多,且二次進(jìn)化第二階段種群規(guī)模更小.波形數(shù)超過220條后二次進(jìn)化的計算代價逐漸變成四種方法中最大的,這是因為二次進(jìn)化中種群規(guī)模和單種群繁殖上限設(shè)置與其他三種方法相比,不是最優(yōu)的.實際上,隨著波形條數(shù)增加到250條,使用最優(yōu)參數(shù)的單種群表現(xiàn)通常已經(jīng)很好,這時二次進(jìn)化中的單種群參數(shù)也可以設(shè)置成與其他三種方法一樣的,基本上在二次進(jìn)化第二階段開始之前,密鑰就已經(jīng)恢復(fù)正確了,這樣二次進(jìn)化的計算代價可以降至與其它三種方法差不多的水平.

圖6 噪聲標(biāo)準(zhǔn)差為3時成功率對比Figure 6 Comparison of success rate when noise standard deviation is 3

圖7 噪聲標(biāo)準(zhǔn)差為3時計算代價對比Figure 7 Comparison of computation cost when noise standard deviation is 3

我們又在噪聲標(biāo)準(zhǔn)差為5的場景下進(jìn)行了同樣的實驗,考慮到噪聲標(biāo)準(zhǔn)差增加,二次進(jìn)化的單種群參數(shù)由200改為300,迭代上限仍為100,并且,當(dāng)波形數(shù)量充足時,單個種群就能大概率恢復(fù)密鑰,因此在波形條數(shù)大于等于400時,二次進(jìn)化的單種群參數(shù)由300改為500,迭代上限由100改為150,其余三種方法的參數(shù)保持不變,所得實驗結(jié)果如圖8和9所示.可以看到,當(dāng)波形條數(shù)小于360時,二次進(jìn)化的成功率和計算代價都是最有優(yōu)勢的,當(dāng)波形條數(shù)大于等于360時,小組賽方法的成功率與二次進(jìn)化方法接近,但計算代價略小于二次進(jìn)化方法.

圖8 噪聲標(biāo)準(zhǔn)差為5時成功率對比Figure 8 Comparison of success rate when noise standard deviation is 5

圖9 噪聲標(biāo)準(zhǔn)差為5時計算代價對比Figure 9 Comparison of computation cost when noise standard deviation is 5

5.2 FPGA上的實驗

我們在FPGA上進(jìn)行了真實實驗,通過采集2000條由隨機明文固定密鑰的AES-128算法在SAKURA-G上運行時所產(chǎn)生的能量波形,并選取攻擊位置為算法最后一輪S盒的輸入.首先通過在不同波形條數(shù)下計算錯誤密鑰與正確密鑰的相關(guān)系數(shù),結(jié)果如圖10所示,當(dāng)波形條數(shù)至少為260條時,正確密鑰的相關(guān)系數(shù)高于錯誤密鑰,因此可以從錯誤密鑰中區(qū)分出來.隨后固定波形條數(shù)為260條,進(jìn)行400次實驗統(tǒng)計四種方法的成功率和計算代價,每次實驗從2000條波形中隨機抽取260條波形,實驗結(jié)果如表3所示.可以看到,二次進(jìn)化的方法在成功率和計算代價上相比其余三種方法都有明顯優(yōu)勢.

表3 真實場景下效率對比Table 3 Efficiency comparison in real scenarios

圖10 不同密鑰取值下的相關(guān)系數(shù)與波形條數(shù)的關(guān)系Figure 10 Relationship between correlation coefficient and number of traces for different candidate keys

6 總結(jié)

本文受基于多種群遺傳算法的CPA啟發(fā),研究多個種群進(jìn)化得到的最優(yōu)個體間的結(jié)合策略,引入小組賽、投票法及二次進(jìn)化這三種個體結(jié)合策略,并與多種群遺傳算法、CPA結(jié)合,從成功率和計算代價兩個層面將三種方法與原始方法進(jìn)行比較,發(fā)現(xiàn)二次進(jìn)化的方式不再局限于多個最優(yōu)個體的各字節(jié)取值,而是通過進(jìn)化使得更有機會找到正確密鑰,故成功率是四種方法中最高的,且在波形數(shù)量不充足使得成功率小于80%時,二次進(jìn)化方法由于使用的單種群的種群規(guī)模和繁殖代數(shù)上限更小,因而計算代價顯著小于其余三種方法,而在波形數(shù)量充足使得成功率大于80%時,二次進(jìn)化方法的單種群的種群規(guī)模和繁殖代數(shù)上限也可以保持與其余三種方法一致,此時二次進(jìn)化方法的計算代價與其余三種方法接近.因而在實際攻擊中采用二次進(jìn)化方法從成功率和計算代價角度上分析都是最具優(yōu)勢的.小組賽和原始方法這兩種方法的成功率和計算代價都相近,投票法的成功率和計算代價均是四種方法中較差的.

通過對多種群中最優(yōu)個體間的原始結(jié)合策略進(jìn)行優(yōu)化,我們發(fā)現(xiàn)二次進(jìn)化方法在擁有更高的成功率的同時,計算代價也更低,有助于提升基于多種群遺傳算法的CPA的效率,并且進(jìn)一步克服了遺傳算法容易早熟收斂的固有缺點.我們希望找到更多思路并加以實踐來克服遺傳算法在側(cè)信道分析中容易早熟收斂的問題.