一種檢測S盒能量信息泄漏的t檢驗(yàn)方法

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

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

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

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

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

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

(1) 能耗采集.

對(duì)密碼算法運(yùn)行過程中的能耗進(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)行檢測時(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)

也可通過式(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)過程較復(fù)雜，因此在實(shí)際檢驗(yàn)中可以采取簡化的t檢驗(yàn)方法：不考慮自由度、概率密度函數(shù)和分布函數(shù)等參量而只對(duì)統(tǒng)計(jì)量t進(jìn)行計(jì)算，根據(jù)t值是否超出閾值得出是否能夠檢測出信息泄漏的結(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%以上.簡便起見，本文選擇|t|=4.5作為閾值實(shí)施t檢驗(yàn)，當(dāng)計(jì)算得到的|t|>4.5時(shí)判定兩組數(shù)據(jù)間存在差異，即能夠檢測出能量信息的泄漏；否則判定不能檢測到泄漏.

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

S盒是分組密碼的核心部分，在加解密過程中起到混亂和局部擴(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)行刻畫.

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

Walsh譜可以將布爾函數(shù)的特征表示出來，通過研究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ū)——門多薩（Mendoza）舉行的國際葡萄采收節(jié)，時(shí)間為從12月持續(xù)到次年2月，舉辦范圍為門多薩的18個(gè)地區(qū)。節(jié)日里，游客除了可以在葡萄園附近品嘗美味優(yōu)質(zhì)的葡萄酒，還可以參加以葡萄酒為主題的巡游和派對(duì)。在酒節(jié)結(jié)束的那一天，會(huì)在一個(gè)具有希臘風(fēng)格的競技場中舉辦一場表演活動(dòng)，由超過2萬名的游客充當(dāng)評(píng)判，評(píng)選出冠軍演員。

S盒作為分組密碼算法的惟一非線性部件，非線性性質(zhì)是其區(qū)別于行移位、列混合等其他變換的決定因素.非線性度是用來刻畫函數(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]提出，用來表示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)一步化簡可得

(20)

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

3 方法驗(yàn)證

本文以DES算法為例，在公開的DPA Contest V2(http://www.DPA Contest V2.org/)數(shù)據(jù)庫中選擇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ù)庫中對(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)，降維后通過矩陣逆映射的方法對(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盒的第二位輸出不能檢測出能量信息的泄漏.而后按照既定順序，對(duì)S盒輸出的第三位進(jìn)行檢驗(yàn)，計(jì)算得到t值為7.37>4.50，判定第三位輸出能夠檢測出信息泄漏.至此t檢驗(yàn)結(jié)束，結(jié)論為能夠檢測出能量信息的泄漏.

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

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

(1) 第4個(gè)和第6個(gè)S盒各位輸出的非線性度相同，新方法與原方法檢驗(yàn)順序相同，檢驗(yàn)效率不能得到提升.需要說明的是本文提出的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)效率有所下降.需要說明的是本文所提出的排序方法是建立在信息泄漏“可能性”基礎(chǔ)上的，因此在一定的檢驗(yàn)閾值下，會(huì)出現(xiàn)泄漏可能性較大的檢驗(yàn)位不能檢測出泄漏而泄漏可能性較小的檢驗(yàn)位能檢測出泄漏的情況從而使檢驗(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é)束語

本文通過布爾函數(shù)的Walsh變換和非線性度對(duì)分組密碼的S盒進(jìn)行了研究，通過分析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)檢測分組密碼能量信息泄漏的排序問題進(jìn)行了研究，下一步可以對(duì)其他密碼算法的t檢驗(yàn)過程進(jìn)行研究以構(gòu)建更完善的t檢驗(yàn)位排序方法體系.