嚴(yán)迎建, 鄭震, 郭朋飛, 朱春生

(戰(zhàn)略支援部隊(duì)信息工程大學(xué) 密碼工程學(xué)院,河南,鄭州 450001)

1 t檢驗(yàn)檢測(cè)能量信息泄漏的步驟

對(duì)密碼設(shè)備側(cè)信道能量信息泄漏的檢測(cè)是目前側(cè)信道領(lǐng)域受關(guān)注度較高的研究方向.對(duì)能量信息泄漏進(jìn)行檢測(cè)時(shí)，往往不要求對(duì)泄漏的具體情況進(jìn)行精確地描述，而只需確定在一定的安全級(jí)別下是否能夠檢測(cè)到能量消耗中的信息泄漏[1].t檢驗(yàn)法是能夠滿足這種需求的一種較為簡(jiǎn)單易行的能量信息泄漏檢測(cè)方法，t檢驗(yàn)結(jié)果描述了被檢測(cè)密碼算法能量信息泄漏的情況，該值超出一定的閾值時(shí)可以判定能夠檢測(cè)出能量信息泄漏，否則判定不能檢測(cè)出泄漏[2].

目前國(guó)內(nèi)外對(duì)t檢驗(yàn)法檢測(cè)能量信息泄漏的相關(guān)研究不夠具體，對(duì)t檢驗(yàn)位的受檢順序的研究較少，多以從前到后或隨機(jī)的順序進(jìn)行檢驗(yàn)[3-4].這樣的檢驗(yàn)方法效率較低，因此有必要對(duì)t檢驗(yàn)位的排序方法進(jìn)行研究以提高t檢驗(yàn)效率.

分組密碼運(yùn)行過(guò)程中字節(jié)代替變換(S盒)處存在能量信息泄漏的概率最大[5-7]，本文以DES算法為例，將S盒輸出這一關(guān)鍵中間狀態(tài)設(shè)置為t檢驗(yàn)位，對(duì)分組密碼的能量信息泄漏實(shí)施t檢驗(yàn)過(guò)程中檢驗(yàn)位排序的問(wèn)題進(jìn)行研究，通過(guò)建立S盒的非線性性質(zhì)與能量信息泄漏之間的聯(lián)系，提出一種檢測(cè)分組密碼S盒能量信息泄漏的t檢驗(yàn)方法.

t檢驗(yàn)是統(tǒng)計(jì)學(xué)中假設(shè)檢驗(yàn)問(wèn)題的一種基本方法，對(duì)能量信息泄漏情況實(shí)施t檢驗(yàn)的假設(shè)檢驗(yàn)問(wèn)題可以敘述成：在顯著性水平α下，檢驗(yàn)零假設(shè)H0：在一定安全級(jí)別下所選檢驗(yàn)位數(shù)值對(duì)該時(shí)間點(diǎn)處的能耗沒(méi)有影響，即在給定的檢驗(yàn)標(biāo)準(zhǔn)下不能檢測(cè)出能量信息泄漏.t檢驗(yàn)的具體步驟如下[8].

(1) 能耗采集.

對(duì)密碼算法運(yùn)行過(guò)程中的能耗進(jìn)行采集，得到n條能量跡Ti(i∈{1，2,…,n})，其中每條包含m個(gè)采樣點(diǎn){Ti(1)，Ti(2)，…,Ti(m)}.

(2) 分組.

選擇密碼算法的某中間節(jié)點(diǎn)作為檢驗(yàn)位，記作Di.而后選定能量跡中的采樣點(diǎn)，根據(jù)Di的數(shù)值將能量跡分為Ψ0和Ψ1兩組：

Ψ0={Ti|Di=0},Ψ1={Ti|Di=1}

(1)

需要指出的是t檢驗(yàn)位的選取并不局限于單比特，同樣地可以選擇多比特作為檢驗(yàn)位.此時(shí)需要設(shè)置一特定的數(shù)值x，在選定的采樣點(diǎn)處根據(jù)所選檢驗(yàn)位多比特的值是否等于x將能量跡分為Ψ0和Ψ1兩組：

Ψ0={Ti|Di=x},Ψ1={Ti|Di≠x}

(2)

在實(shí)際中對(duì)泄漏進(jìn)行檢測(cè)時(shí)，由于明文、密鑰和設(shè)備運(yùn)行情況等信息未知，要同時(shí)獲取中間狀態(tài)多比特的信息往往存在較大難度，因此本文只對(duì)檢驗(yàn)位位寬為1 bit的情況進(jìn)行研究.

(3) 處理能耗數(shù)據(jù).

(3)

按式(4)計(jì)算自由度v為

(4)

再由自由度v可得到t分布的概率密度函數(shù)：

(5)

其中Γ表示伽馬函數(shù).由式(5)進(jìn)一步可得到t檢驗(yàn)中零假設(shè)成立的概率：

(6)

也可通過(guò)式(7)得出分布函數(shù)：

(7)

其中2F1表示超幾何函數(shù).而后進(jìn)一步得到t檢驗(yàn)中零假設(shè)成立的概率：

p=2F(-|t|,v)

(8)

(4) 比較分析，得出結(jié)論.

進(jìn)行上述完整t檢驗(yàn)的計(jì)算量較大且檢驗(yàn)過(guò)程較復(fù)雜，因此在實(shí)際檢驗(yàn)中可以采取簡(jiǎn)化的t檢驗(yàn)方法：不考慮自由度、概率密度函數(shù)和分布函數(shù)等參量而只對(duì)統(tǒng)計(jì)量t進(jìn)行計(jì)算，根據(jù)t值是否超出閾值得出是否能夠檢測(cè)出信息泄漏的結(jié)論.可以參考式(9)對(duì)閾值進(jìn)行設(shè)置：

p=2F(t=±4.5,v>1 000)<0.000 01

(9)

式(9)表明，樣本量大于1 000時(shí)，將統(tǒng)計(jì)量t的閾值設(shè)置為4.5,能夠使得檢驗(yàn)的準(zhǔn)確率達(dá)到99.999%以上.簡(jiǎn)便起見(jiàn)，本文選擇|t|=4.5作為閾值實(shí)施t檢驗(yàn)，當(dāng)計(jì)算得到的|t|>4.5時(shí)判定兩組數(shù)據(jù)間存在差異，即能夠檢測(cè)出能量信息的泄漏；否則判定不能檢測(cè)到泄漏.

2 對(duì)S盒實(shí)施t檢驗(yàn)的排序方法

S盒是分組密碼的核心部分，在加解密過(guò)程中起到混亂和局部擴(kuò)散等作用：S盒輸入中一個(gè)比特的不同會(huì)導(dǎo)致輸出中多個(gè)比特的不同.S盒的非線性度越大，其達(dá)到的混亂和局部擴(kuò)散的效果越好.在對(duì)S盒進(jìn)行設(shè)計(jì)時(shí)為應(yīng)對(duì)差分分析、線性分析和代數(shù)計(jì)算攻擊等傳統(tǒng)密碼分析手段，要求其具有良好的非線性性質(zhì)，即要求其具有較大的非線性度[9].另一方面，良好的非線性性質(zhì)即較大的非線性度容易在側(cè)信道能量分析攻擊等新型密碼分析手段中被攻擊者利用. 從這一矛盾出發(fā)，對(duì)現(xiàn)有t檢驗(yàn)方法進(jìn)行創(chuàng)新.

2.1 S盒非線性度

S盒的實(shí)質(zhì)是多輸入多輸出布爾函數(shù)，其性質(zhì)可以用相應(yīng)的布爾函數(shù)的性質(zhì)進(jìn)行刻畫(huà).

(1) 布爾函數(shù)的Walsh變換.

Walsh譜可以將布爾函數(shù)的特征表示出來(lái)，通過(guò)研究Walsh變換可以更好地對(duì)布爾函數(shù)的性質(zhì)進(jìn)行把握，n元布爾函f(x)數(shù)的第一種Walsh變換為[10]

(10)

其中，x=(x1,x2,…,xn)∈GF(2)n，ω=(ω1,ω2,…,ωn)∈GF(2)n，ω·x為ω與x的點(diǎn)積.

ω·x=ω1x1+ω2x2+…+ωnxn

(11)

f(x)的第二種Walsh變換為[10]

(12)

(2) 布爾函數(shù)的非線性度.

在阿根廷最知名的葡萄酒產(chǎn)區(qū)——門(mén)多薩（Mendoza）舉行的國(guó)際葡萄采收節(jié)，時(shí)間為從12月持續(xù)到次年2月，舉辦范圍為門(mén)多薩的18個(gè)地區(qū)。節(jié)日里，游客除了可以在葡萄園附近品嘗美味優(yōu)質(zhì)的葡萄酒，還可以參加以葡萄酒為主題的巡游和派對(duì)。在酒節(jié)結(jié)束的那一天，會(huì)在一個(gè)具有希臘風(fēng)格的競(jìng)技場(chǎng)中舉辦一場(chǎng)表演活動(dòng)，由超過(guò)2萬(wàn)名的游客充當(dāng)評(píng)判，評(píng)選出冠軍演員。

S盒作為分組密碼算法的惟一非線性部件，非線性性質(zhì)是其區(qū)別于行移位、列混合等其他變換的決定因素.非線性度是用來(lái)刻畫(huà)函數(shù)非線性性質(zhì)的參數(shù)，對(duì)n元布爾函數(shù)，其非線性度Nf為[11]

Nf=2n-1(1-max|Sf(ω)|),0≤ω≤2n-1-1

(13)

對(duì)某(p,q)函數(shù)F，其非線性度為[12]

(14)

根據(jù)布爾函數(shù)的Walsh變換式(12)可對(duì)式(14)進(jìn)行推導(dǎo)得

(15)

式(15)描述了布爾函數(shù)非線性度的計(jì)算方法.以DES算法第一個(gè)S盒為例，設(shè)其輸出各位分別為y1,y2,y3,y4∈GF(2).根據(jù)式(10)、式(12)和式(15)，可以編程分別計(jì)算出DES算法第一個(gè)S盒輸出各位的非線性度如表1所示.

表1 DES第一個(gè)S盒各位輸出的非線性度

2.2 S盒輸出位排序方法

引入“透明階[12]”這一概念，對(duì)S盒的非線性性質(zhì)與能量信息泄漏之間的關(guān)系進(jìn)行推導(dǎo).“透明階”為Prouff等[12]提出，用來(lái)表示S盒抗能量攻擊的能力：透明階的值越大，能量信息泄漏程度越大，S盒抗能量攻擊的能力越弱.

對(duì)一個(gè)(p,q)函數(shù)F，其透明階τF定義為

(16)

式中：β為S盒輸出連續(xù)的狀態(tài)函數(shù)；H(β)為其漢明質(zhì)量；DεF為函數(shù)F的線性結(jié)構(gòu).透明階的下界公式如式(17).

(17)

又由式(13)可得

max|Sf(ω)|=1-21-nNf,0≤ω≤2n-1

(18)

根據(jù)式(18)對(duì)式(17)進(jìn)行推導(dǎo)可得

(19)

進(jìn)一步化簡(jiǎn)可得

(20)

由式(20)可知非線性度與透明階之間存在正相關(guān)的關(guān)系：非線性度越大，透明階越大；反之亦然.從側(cè)信道泄漏角度來(lái)看，式(20)說(shuō)明，S盒輸出各位中非線性度大的比特位存在信息泄漏的概率更大.利用該結(jié)論可得到提高t檢驗(yàn)效率的方法：先對(duì)S盒輸出位的非線性度進(jìn)行計(jì)算，而后按照非線性度由大到小的順序?qū)Ω鬏敵鑫粚?shí)施t檢驗(yàn).由于檢測(cè)的目的在于確定是否能夠檢測(cè)出信息泄漏，而非準(zhǔn)確地量化信息泄漏或得到信息泄漏的特征，因此當(dāng)某一比特位檢測(cè)出能量信息泄漏時(shí)t檢驗(yàn)即可停止，而無(wú)需對(duì)剩余S盒輸出位進(jìn)行檢驗(yàn)，當(dāng)所有的檢驗(yàn)位均通過(guò)t檢驗(yàn)時(shí)方可判定不存在信息泄漏.

3 方法驗(yàn)證

本文以DES算法為例，在公開(kāi)的DPA Contest V2(http://www.DPA Contest V2.org/)數(shù)據(jù)庫(kù)中選擇10 000條密鑰為一固定值，明文為一組隨機(jī)輸入的DES加密算法的能量跡，對(duì)提出的排序方法進(jìn)行實(shí)驗(yàn)驗(yàn)證.

3.1 驗(yàn)證基礎(chǔ)

在對(duì)S盒的輸出位實(shí)施t檢驗(yàn)時(shí)，首先需要確定S盒輸出時(shí)刻在DES算法的完整能量跡中的位置.本文采用主成分分析(principle component analysis,PCA)降維法對(duì)S盒輸出時(shí)刻所對(duì)應(yīng)的能量跡中的采樣點(diǎn)位置進(jìn)行確定[13-14]，DPA Contest V2數(shù)據(jù)庫(kù)中對(duì)每條DES算法的能量跡設(shè)置了10 088個(gè)采樣點(diǎn)，圖1為利用10 000條能量跡進(jìn)行PCA降維的分析圖.

圖1 PCA降維分析圖Fig.1 PCA dimensionality reduction analysis diagram

圖1中，橫軸為能量跡中的采樣點(diǎn)編號(hào)，縱軸為PCA降維的主成分相關(guān)系數(shù)，主成分相關(guān)系數(shù)的絕對(duì)值越大，采樣點(diǎn)能耗中所含的信息量越大.

PCA降維結(jié)果中的特征維度與能量跡中的采樣點(diǎn)一一對(duì)應(yīng)，降維后通過(guò)矩陣逆映射的方法對(duì)含信息量較多的特征維度所對(duì)應(yīng)的能量跡中的采樣點(diǎn)位置進(jìn)行確定，綜合時(shí)間順序和能耗大小兩方面因素進(jìn)行篩選可知，DES加密算法第一輪S盒輸出時(shí)刻對(duì)應(yīng)的是能量跡中的第314個(gè)采樣點(diǎn).

3.2 實(shí)驗(yàn)驗(yàn)證

首先對(duì)DES加密算法第一輪第一個(gè)S盒實(shí)施t檢驗(yàn).按照表1中得到的非線性度的大小順序，利用所提出的排序方法實(shí)施t檢驗(yàn)時(shí)的檢驗(yàn)順序應(yīng)為y2→y3→y1→y4(yi表示S盒的第i位輸出)，其中y1和y4的非線性度相等，檢驗(yàn)順序可調(diào)換.

1.85<4.50

據(jù)此判斷，第一個(gè)S盒的第二位輸出不能檢測(cè)出能量信息的泄漏.而后按照既定順序，對(duì)S盒輸出的第三位進(jìn)行檢驗(yàn)，計(jì)算得到t值為7.37>4.50，判定第三位輸出能夠檢測(cè)出信息泄漏.至此t檢驗(yàn)結(jié)束，結(jié)論為能夠檢測(cè)出能量信息的泄漏.

為與原方法進(jìn)行比較，對(duì)S盒第一位輸出進(jìn)行檢驗(yàn)，得到t值為2.79<4.50，判定第一位輸出不能檢測(cè)出能量信息泄漏；對(duì)第4位輸出進(jìn)行檢驗(yàn)得到t值為8.32>4.50，能夠檢測(cè)出能量信息泄漏.

根據(jù)以上結(jié)果分析可知，在改進(jìn)前從前至后逐位實(shí)施的t檢驗(yàn)方法中，需要依次檢驗(yàn)S盒輸出的前3位才能檢測(cè)出能量信息的泄漏，而按照本文所提出的方法則只需要檢驗(yàn)第2位和第3位輸出即可得出正確結(jié)論，可較原方法少進(jìn)行一次t檢驗(yàn).為排除偶然性因素，隨后對(duì)其余7個(gè)S盒分別進(jìn)行了實(shí)驗(yàn)驗(yàn)證，具體驗(yàn)證過(guò)程不再贅述，實(shí)驗(yàn)結(jié)果匯總?cè)绫?.

表2 DES加密第一輪各S盒輸出位方法驗(yàn)證情況

表2中，“實(shí)際驗(yàn)證中節(jié)省的檢驗(yàn)位數(shù)”指利用本文所提出的方法較原方法少實(shí)施的t檢驗(yàn)次數(shù)，分析該指標(biāo)可知在本文的驗(yàn)證實(shí)驗(yàn)中，利用新的排序方法令DES算法中半數(shù)的S盒不同程度地減少了檢驗(yàn)次數(shù)，提升了檢驗(yàn)效率.同時(shí)，對(duì)驗(yàn)證過(guò)程中出現(xiàn)的兩種特殊情況分析如下.

(1) 第4個(gè)和第6個(gè)S盒各位輸出的非線性度相同，新方法與原方法檢驗(yàn)順序相同，檢驗(yàn)效率不能得到提升.需要說(shuō)明的是本文提出的t檢驗(yàn)位排序方法僅適用于S盒各輸出位非線性度不同的情況，不適用于非線性度相同的情況.事實(shí)上，本文提出的排序方法可以“變相”地應(yīng)用于這種情況：第4個(gè)S盒較第6個(gè)S盒輸出位的非線性度大，因此可以先對(duì)第4個(gè)S盒實(shí)施檢驗(yàn).

(2) 在對(duì)第7個(gè)S盒實(shí)施t檢驗(yàn)時(shí)，新方法較原方法的檢驗(yàn)效率有所下降.需要說(shuō)明的是本文所提出的排序方法是建立在信息泄漏“可能性”基礎(chǔ)上的，因此在一定的檢驗(yàn)閾值下，會(huì)出現(xiàn)泄漏可能性較大的檢驗(yàn)位不能檢測(cè)出泄漏而泄漏可能性較小的檢驗(yàn)位能檢測(cè)出泄漏的情況從而使檢驗(yàn)效率下降.根據(jù)統(tǒng)計(jì)學(xué)原理分析可知，當(dāng)檢驗(yàn)量足夠大時(shí)，這種情況出現(xiàn)的概率將大大減小.

總而言之，與原檢驗(yàn)方法相比，本文提出的檢驗(yàn)位排序方法可對(duì)存在能量信息泄漏概率大的t檢驗(yàn)位先進(jìn)行檢驗(yàn)，從而能夠減少檢驗(yàn)次數(shù)，比原方法更快地檢驗(yàn)出存在的能量信息泄漏，這在檢驗(yàn)位數(shù)較多，檢驗(yàn)情況較復(fù)雜，數(shù)據(jù)處理較繁瑣的情況下可以顯著提升檢驗(yàn)效率，節(jié)省檢驗(yàn)成本.

4 結(jié)束語(yǔ)

本文通過(guò)布爾函數(shù)的Walsh變換和非線性度對(duì)分組密碼的S盒進(jìn)行了研究，通過(guò)分析S盒輸出位的非線性度與“透明階”這一衡量能量信息泄漏參數(shù)的聯(lián)系，得出了一種對(duì)分組密碼的能量信息泄漏實(shí)施t檢驗(yàn)時(shí)對(duì)S盒輸出位進(jìn)行排序的方法.驗(yàn)證的結(jié)果表明該方法能夠有效提升t檢驗(yàn)效率，節(jié)省檢驗(yàn)資源.

由于時(shí)間等因素所限，本文僅對(duì)t檢驗(yàn)檢測(cè)分組密碼能量信息泄漏的排序問(wèn)題進(jìn)行了研究，下一步可以對(duì)其他密碼算法的t檢驗(yàn)過(guò)程進(jìn)行研究以構(gòu)建更完善的t檢驗(yàn)位排序方法體系.