(n，m)函數(shù)抗差分功耗攻擊指標的研究綜述

周 宇，陳智雄，卓澤朋，杜小妮

(1.保密通信重點實驗室，四川 成都 610041；2．莆田學院 福建省應用數(shù)學重點實驗室，福建 莆田 351100；3.淮北師范大學 數(shù)學科學學院，安徽 淮北 235000；4.西北師范大學 數(shù)學與統(tǒng)計學院，甘肅 蘭州 730070)

(n，m)函數(shù)是對稱密碼算法的基本部件之一，其研究重點在設計和分析兩個方面。設計主要是通過數(shù)學方法構造出滿足多種密碼學性質的函數(shù)，而分析主要是研究函數(shù)的各種密碼學指標，這些密碼學指標往往與其對應的攻擊緊密聯(lián)系在一起。從(n，m)函數(shù)面對的各種攻擊來看，可以將密碼學指標分為兩大類：

(1) 基于數(shù)學的傳統(tǒng)攻擊手段，例如線性攻擊、差分攻擊、代數(shù)攻擊、相關攻擊等，一些指標主要有非線性度、相關免疫度和代數(shù)免疫度等；

(2) 基于物理的差分功耗分析手段，例如差分功耗攻擊，主要有信噪比[1]、透明階[2]和混淆系數(shù)[3]等。

文中重點討論信噪比、透明階和混淆系數(shù)這三個指標，以及這些指標與傳統(tǒng)密碼學指標的關系等。

差分功耗攻擊(Differential Power Attack，DPA)[4]是能量分析中一種強有力的攻擊手段，其原理是通過統(tǒng)計密碼設備或者密碼算法在加密運算過程中泄漏的功耗消耗特征，來破譯出一些密鑰信息。該方法最早是在1999年由KOCHER等人[4]提出，當時是對分組密碼數(shù)據(jù)加密標準(Data Encryption Standard，DES)進行了差分功耗攻擊。這種方法后來被廣泛用于公鑰密碼算法和分組密碼算法的安全分析中。而在實驗層面進行差分功耗攻擊是在2002年由MESSERGES等人[5]提出。在此基礎上，漢明距離功耗模型被BRIER等人[6]提出，該模型驗證了相關功耗分析(Correlation Power Analysis，CPA)攻擊，實驗結果進一步表明，CPA在某些方面相對DPA有較大優(yōu)勢，這也是后來CPA被廣泛使用的原因之一。以上的實驗和一些模型都是針對非線性S盒展開分析，S盒作為對稱加密算法的主要非線性部件之一，對算法的安全性起著關鍵性作用，但是傳統(tǒng)密碼學性質好的S盒未必能抵抗差分功耗分析。因此，必須對S盒的抗差分功耗攻擊指標進行系統(tǒng)研究。下面將從差分功耗分析角度給出三個密碼學指標(信噪比、透明階和混淆系數(shù))的發(fā)展現(xiàn)狀。

第1個指標：信噪比(Signal-to-Noise Ratio，SNR)。該指標是在2004年8月的CARDIS會議上被GUILLEY等人[1]提出。首先他們基于傳統(tǒng)密碼分析的框架對信息泄漏進行完整建模，對于攻擊者來說可以獲取密鑰猜測值的Hamming權重的自相關值。該模型表明，當S盒抵抗線性密碼分析能力增強時，S盒對應的信噪比值也將隨之增大。但是從S盒抵抗DPA角度來說，信噪比越小，抵抗DPA越好。這就表明S盒的信噪比和S盒抵抗線性密碼分析之間存在著制約關系，兩者不能同時達到最好。通過信噪比模型和定義可以看出，非線性S盒的噪聲對密碼算法的DPA信號起著決定性作用。隨著該指標出現(xiàn)也產(chǎn)生了一些研究結果[7]。

第2個指標：透明階(Transparency Order，TO)。該指標是在2005年的FSE會議上被PROUFF[2]首次提出。文獻[2]基于差分功耗思想，建立了多入多出(n，m)函數(shù)與漢明距離模型的緊密關系，得到了S盒的透明階與傳統(tǒng)的一些密碼學性質不能同時達到最好。隨著國內外學者研究的深入，也衍生出了改進的透明階概念(Redefining Transparency Order，RTO)[8]和修改的透明階(Modified Transparency Order，MTO)概念[9]。在新指標和舊指標的共同指引下得到了一系列研究成果[10-12]。

第3個指標：混淆系數(shù)(Confusion Coefficient，CC)。該指標是在2012 年的密碼硬件和嵌入式系統(tǒng)國際研討會上被FEI等人[13]提出。研究表明，S盒的混淆系數(shù)值越大，S盒抵抗DPA能力就越強?；贔EI等人的結果，PICEK等人[14]在2014 年計算了不同大小的 S 盒的非線性度，得到了混淆系數(shù)方差。同年，邱爽等人[15]為了降低維數(shù)和混淆系數(shù)的個數(shù)，對原始混淆系數(shù)進行了修訂，給出了新的混淆系數(shù)定義?；谠撔露x，重新計算了DES針對各個備選密鑰的功耗差(Difference of Means，DoM)期望的分布。實驗結果與利用修改后的混亂系數(shù)計算得到的DoM期望值相符。

因此，筆者試圖從數(shù)學理論角度來綜述(n，m)函數(shù)的這三個指標的研究進展，而不考慮其背后的物理實驗背景。

1 基本概念

2004年GUILLEY等人在研究DPA信號時提出了信噪比(SNR)概念[1]。

定義1[1]設F=(f1，f2，…，fm)是一個(n，m)函數(shù)，則函數(shù)F的信噪比(SNR)定義為

(1)

緊接著，在2005年的FSE會議上，PROUFF擴展了GUILLEY等人提出的多比特DPA攻擊[1]和功耗模型，提出了漢明重量模型，建立了S盒與DPA攻擊的關系，給出了(n，m)函數(shù)的透明階概念(TO)[2]。

定義2[2]設F=(f1，f2，…，fm)是一個(n，m)函數(shù)，則函數(shù)F的透明階(TO)定義為

(2)

2017年CHAKRABORTY等人在研究(n，m)函數(shù)的TO基礎上，發(fā)現(xiàn)了TO的冗余，所以提出了改進透明階概念(RTO)[8]。

定義3[8]設F=(f1，f2，…，fm)是一個(n，m)函數(shù)，則函數(shù)F的改進透明階(RTO)定義為

(3)

2019年周永彬等在研究(n，m)函數(shù)的RTO基礎上，通過多比特DPA(Multi-bit DPA)和變型多比特DPA(Variant multi-bit DPA)實驗，發(fā)現(xiàn)線性 (n，m)函數(shù)可以完全抵抗變型多比特DPA攻擊，但是線性(n，m)函數(shù)很容易受到DPA攻擊，為此提出了修改的透明階概念(Modified Transparency Order，MTO)[9]。

定義4[9]設F=(f1，f2，…，fm)是一個(n，m)函數(shù)，則函數(shù)F的修改透明階(MTO)定義為

(4)

從定義2～4可以看出，TO與F=(f1，f2，…，fm)的分量函數(shù)自相關函數(shù)緊密聯(lián)系在一起，而RTO和MTO與F=(f1，f2，…，fm)的分量函數(shù)自相關函數(shù)和互相關函數(shù)緊密聯(lián)系在一起；定義3和4惟一不同在于絕對值的位置，這決定了在DPA攻擊中泄露的信息多少。

2012年，F(xiàn)EI等人在研究DPA統(tǒng)計模型時，建立了DPA成功率與密碼算法之間的定量關系?；谠摱筷P系，用一種新混淆分析法提取密碼算法的邊信道特性，提出了(n，m)函數(shù)的混淆系數(shù)概念(CC)[3]。

定義5[3]設F=(f1，f2，…，fm)是一個(n，m)函數(shù)，則函數(shù)F的混淆系數(shù)(CC)定義為

(5)

其中，σ2為方差函數(shù)，κ(ki，kj)=Ep[(L(F(ki+p))-L(F(kj+p))2)]，ki，kj分別表示第i個和第j個密鑰值，p為明文，L為泄露函數(shù)。

受篇幅限制，布爾函數(shù)的相關其它概念(例如擴散性、代數(shù)免疫、相關免疫、全局雪崩準則等)請參考文獻[16]。

2 (n，m)函數(shù)的信噪比研究進展

GUILLEY等人[1]得到了平衡(n，m)函數(shù)信噪比的上下界、非平衡(n，m)函數(shù)信噪比的下界、Bent(n，m)函數(shù)信噪比的下界，并證明了當(n，m)函數(shù)抵抗線性密碼分析能力增加時，信噪比也將隨之增加。2020年，周宇等人研究了布爾函數(shù)(即(n，1)函數(shù))的信噪比[7]，給出了任意n元函數(shù)的信噪比緊的上界和緊的下界，以及下界與非線性度的關系，得到了n元函數(shù)信噪比與2個n-1元分解函數(shù)信噪比的關系。特別地，對于平衡布爾函數(shù)，給出了信噪比更緊的上界和下界，最后給出了兩個n元函數(shù)相加與兩個n元函數(shù)乘積的信噪比與各自信噪比的關系，同時也給出了4元、5元平衡布爾函數(shù)信噪比的分布表。

2.1 (n，m)函數(shù)的信噪比

對于F=(f1，f2，…，fm)的信噪比與分量函數(shù)的信噪比有如下關系。

定理1[7]設F=(f1，f2，…，fm)是一個(n，m)函數(shù)，則

(6)

但是對于由分量函數(shù)信噪比決定的F=(f1，f2，…，fm)的信噪比上界，僅能給出(n，2)函數(shù)的結果，對于m≥3，很難給出精確的刻畫。

定理2[7]設F=(f1，f2)是一個(n，2)函數(shù)，則

(7)

(8)

進而得出

在此基礎上，得到一些(n，m)函數(shù)信噪比的上界或者下界，具體如表1[1]所示。

表1 (n，m)函數(shù)信噪比上界或者下界

表2 5元平衡布爾函數(shù)的信噪比分布

2.2 布爾函數(shù)的信噪比

當m=1時，(n，m)函數(shù)就是n元布爾函數(shù)，其信噪比性質較(n，m)函數(shù)刻畫得更清晰。其結果如下。

定理3[7]設f∈Bn，則1≤SSNR(f)≤2n/2，其中左邊等號成立，當且僅當f是仿射函數(shù)，而右邊等號成立，當且僅當f是bent函數(shù)。

進一步可以知道f的信噪比與非線性度的關系：SSNR(f)≥2n/(2n-2nl(f))。

(9)

而對于兩個變量不交的函數(shù)，其和函數(shù)和積函數(shù)的信噪比結果如下。

定理5[7]設f∈Bn，g∈Bm，則

(1)SSNR(f+g)=SSNR(f)SSNR(g)；

而對于滿足一定擴散性的布爾函數(shù)來說，其信噪比上界如下。

通過程序計算[7]可知，4元平衡布爾函數(shù)的SNR為4值分布：{1.000 000，1.705 606，2.000 000，2.529 822}，而5元平衡布爾函數(shù)的SNR為18值分布：{1.000 000，1.302 062，1.705 606，1.735 444，2.000 000，2.157 440，2.285 714，2.359 071，2.439 977，2.529 822，2.630 384，2.873 685，3.023 716，3.200 000，3.411 211，3.670 652，4.000 000，4.437 602}。5元平衡布爾函數(shù)的信噪比具體分布如表2所示。

3 (n，m)函數(shù)的透明階研究進展

在(n，m)函數(shù)的透明階發(fā)展中出現(xiàn)了三個不同概念，依次介紹如下。

(1) 2005年，PROUFF首次在FSE上提出(n，m)函數(shù)的透明階(TO)概念[2]，在DPA攻擊的模型中發(fā)現(xiàn)了S盒的透明階與S盒的非線性不能同時達到最好，即如果S盒抵抗線性攻擊的能力越強，S盒抵抗DPA攻擊的能力就越弱。緊接著，CARLET系統(tǒng)研究了高非線性S盒的透明階，得到了該S盒的透明階下界[26]。該結果反映了透明階與非線性度的關系，進一步他也研究了其它一些高非線性函數(shù)(例如逆函數(shù)、Gold 函數(shù)、Kasami 函數(shù))，發(fā)現(xiàn)在理論上這些S盒具有較差的透明階。后來，F(xiàn)AN等人[27]通過引入一個精心設計的閾值濾波器提出了一種計算S盒透明階的快速實現(xiàn)方法，基于此，給出了兩種S盒透明階的優(yōu)化計算技術。MAZUMDAR等人[28]在2013 年得到了一些偶數(shù)元和奇數(shù)元S盒的透明階上界和下界，利用搜索方法得到了一類TO值優(yōu)于AES算法中的S 盒。2014年PICEK等人[29]研究了輕量級分組密碼PRINCE，通過進化算法得到了非線性度為4且透明階最低的S盒，以此生成具有改進DPA相關特性的S盒。后來，SARKAR等人[30]針對(n，n)函數(shù)，基于差分能量分析回答了如何在仿射等價下對S盒的選擇問題。同年MAZUMDAR[31]找到了在傳統(tǒng)密碼特性(如高非線性和低GAC絕對指示符)和透明階指標方面都較好的S盒。

(2) 2017年，CHAKRABORTY等人指出TO指標存在一定的局限性，給出了修改的透明階指標(RTO)[8]。在該概念的引導下，PICEK等人基于遺傳算法和隨機搜索等算法搜索找到了一些抵抗 DPA好的S盒[29]。

2017年程讓在其碩士論文[10]中對RTO進行了研究，推導出了RTO下界與分量函數(shù)Walsh譜值的關系，給出了RTO與非線性度之間的一種制約關系，并分別基于Maiorana-McFarland函數(shù)構造法和Bracken-Leander函數(shù)構造法得到了平衡且具有較低RTO的(4，4)函數(shù)。2019年WANG等人[11]針對TO和RTO研究了布爾函數(shù)的透明階，給出了由非線性度決定的RTO的下界，提出了2種具有良好透明階的無限類平衡半bent函數(shù)，同時也給出了擇多函數(shù)(the majority function)、隱藏重量函數(shù)(the hidden weighted bit function)、Carlet-Feng函數(shù)、旋轉對稱布爾函數(shù)(rotation symmetric Boolean functions)的透明階。

(3) 2019年周永彬等人[9]指出多比特DPA攻擊中RTO定義的不足，提出了修訂的透明階概念(MTO)，對某些S盒進行了實驗仿真，進一步分析了16類最優(yōu)(4，4)函數(shù)的仿射等價類MTO分布規(guī)律。

3.1 (n，m)函數(shù)的透明階

首先，給出2005年由PROUFF得到的擴散準則與透明階關系[2]。

定理7[2]設F=(f1，f2，…，fm)是一個(n，m) 函數(shù)(m≤n)。如果F滿足t階擴散準則，則

(10)

緊接著，對于任意(n，m)函數(shù)來說，其透明階介于0和m之間。

定理8[2]設F=(f1，f2，…，fm)是一個(n，m) 函數(shù)，則0≤TTO(F)≤m。

而對于(n，m)函數(shù)來說，其透明階的下界與分量函數(shù)的Walsh譜有如下關系[26]。

定理9[26]設F=(f1，f2，…，fn)是一個(n，n) 函數(shù)，則

(11)

CHAKRABORTY等人在TO的基礎上，分析了仿射變換下RTO的變化情況，指出對 (n，m) 函數(shù)的輸入變量做仿射變換不改變RTO的值，而對(n，m) 函數(shù)的輸出值做某個仿射變換后RTO的值會發(fā)生改變[8]。

定理10[8]設F=(f1，f2，…，fm)是一個平衡(n，m) 函數(shù)，則對任意的n階可逆矩陣A，有RRTO(F°A)=RRTO(F)。

2017年程讓在其碩士論文中證明了分量函數(shù)非零線性組合后的函數(shù)最大Walsh譜與RTO的關系[10]。

結合文獻[8]和[9]的結果，可以看到MMTO(F)和RRTO(F)有共同的下界。

定理12[8-9]設F=(f1，f2，…，fm)是一個(n，m) 函數(shù)，則MMTO(F)和RRTO(F)有共同的下界，即

(12)

3.2 最優(yōu)(4，4) 函數(shù)的透明階分布

對于任意的F=(f1，f2，…，fm)，文獻[9]證明了對任意的n階可逆矩陣A有MMTO(F)=MMTO(F°A)，但存在某些n階可逆矩陣A能使得MMTO(F)≠MMTO(A°F)。這也就表明MTO不是仿射變換下的不變量。根據(jù)該結論就可以給出16類最優(yōu) (4，4)S盒的仿射等價S盒(共20 160×16個)的各類透明階分布圖。圖1為TO的分布圖(可知TO為9值分布)，圖2為RTO的分布圖(可知RTO為30值分布)，圖3為MTO的分布圖(可知MTO為11值分布)。

圖1 TTO(A°Gi)的分布圖

圖2 RRTO(A°Gi)的分布圖

圖3 MMTO(A°Gi)的分布圖

3.3 布爾函數(shù)的透明階

當m=1時，(n，m)函數(shù)F就是n元布爾函數(shù)，此時有TTO(F)=RRTO(F)=MMTO(F)。

4 (n，m)函數(shù)的混淆系數(shù)研究進展

文獻[29]基于漢明重量對給定的CPA選擇函數(shù)給出了計算混淆系數(shù)的方法。對所有密鑰對ka，kb(ka≠kb)，計算κ(ka，kb)=E[(HW(F(in+ka))-HW(F(in+kb)))2]。

定理14[29]設F=(f1，f2，…，fm)是一個(n，m) 函數(shù)，則對密鑰的第ki，kj，kh對應的三方混淆系數(shù)如下：

(13)

針對F=(f1，f2，…，fm)進行DPA時各個備選密鑰的功耗差(DoM)期望的分布，F(xiàn)EI等人[13]得到如下結論：

定理15[13]設F=(f1，f2，…，fm)是一個(n，m) 函數(shù)，kc為錯誤密鑰猜測值，kg為正確密鑰，kc和kg對應的DoM分別為δc和δg，則對Δ(kc，kg)有

(1)E[Δ(kc，kg)]=2κ(kc，kg)ε；

而關于混淆系數(shù)與成功率，F(xiàn)EI等人[3]得到成功率的公式。

定理16[3]基于CPA泄露模型，在對稱密鑰假設下，CPA的漸進成功率為

(14)

其中，K**表示另外一個(NK-1)(NK-1)維混淆矩陣。

在混淆系數(shù)計算中，首先得根據(jù)不同的密鑰ki，kj計算出κ(ki，kj)。為此，文獻[14]基于仿射變換給出了16類最優(yōu)4比特S盒[17]和一些公開算法中S盒的κ值大小(如表3所示)。

表3 一些 (4，4) S盒κ值

2014年，邱爽等人[15]指出，F(xiàn)EI[3]提出的混淆系數(shù)定義中存在冗余，并且修改了混亂系數(shù)的定義，重新構建了DPA模型中算法相關的部分，其定義如下：

定義6[3]設F=(f1，f2，…，fm)是一個(n，m)函數(shù)，則函數(shù)F的修改混淆系數(shù)(RCC)定義為

(15)

其中，of表示兩個密鑰之間的異或關系KS1+KS2，假設F(·)b表示選定F的某一位的輸出。

可以看出，RRCC(F)只與兩個密鑰之間的異或值相關，和混淆系數(shù)κ值的關系為

RRCC(KS1+KS2)=κ(KS1，KS2) ，

(16)

根據(jù)這個關系式可知，修改后的混淆系數(shù)在個數(shù)方面有較大的下降。

根據(jù)定義6，邱爽等人[15]針對DES算法得到了DPA各個假設密鑰產(chǎn)生的均值差，計算了修改混淆系數(shù)，從實驗角度驗證了修改混淆系數(shù)的合理性。

5 一些(n，n) S盒的常用密碼學指標值對照

首先，對于一些公開算法中(4，4) S盒，2014年文獻[29]給出了這些常用密碼學指標的對照表(如表4所示)。

表4 一些 (4，4) S盒的各種密碼學指標對照表

然后，對于一些公開算法中(8，8) S盒，2018年文獻[32]給出了這些常用密碼學指標的對照表(如表5所示)。

表5 一些 (8，8) S盒的各種密碼學指標對照表

最后，對于一些構造得到的(8，8) S盒，文獻[32]給出了這些常用密碼學指標的對照表(如表6所示)。

表6 一些 (8，8) S盒構造方法的各種密碼學指標對照表

6 值得進一步研究的問題

(n，m)函數(shù)是對稱密碼算法中的基本部件，其安全性對密碼算法安全性起著重要作用。經(jīng)過國內外學者多年來的共同努力，在(n，m)函數(shù)抵抗差分功耗攻擊方面已經(jīng)取得了豐富的成果。文中重點綜述了(n，m)函數(shù)的三個密碼學指標(信噪比、透明階和混淆系數(shù))。由于文章篇幅所限，對如何構造滿足良好信噪比、透明階和混淆系數(shù)的(n，m)函數(shù)的研究成果介紹相對簡單，感興趣的讀者可以進一步查閱相關參考文獻。結合目前(n，m)函數(shù)的這三個密碼學指標的研究結果，以及抗側信道模型的分析，作者認為下列問題值得進一步研究：

(1) 信噪比、透明階和混淆系數(shù)分別與傳統(tǒng)密碼學指標的關系已經(jīng)研究出了一些結論，但是還不夠詳盡，需要進一步研究。

(2) 信噪比、透明階和混淆系數(shù)之間相互的制約關系研究的較少，特別是針對某些密碼結構，例如某些特殊構造的4比特S盒[48]、線性移位寄存器[49]，等等。

(3) 構造符合特定場景需求且滿足一定密碼學性質的S盒是密碼算法設計的重要研究方向，特別是構造同時抵抗側信道攻擊和抵抗傳統(tǒng)密碼攻擊(某些特殊模型的快速代數(shù)攻擊[50])的S盒是研究的重點。