周 宇,陳智雄,卓澤朋,杜小妮
(1.保密通信重點(diǎn)實(shí)驗(yàn)室,四川 成都 610041;2.莆田學(xué)院 福建省應(yīng)用數(shù)學(xué)重點(diǎn)實(shí)驗(yàn)室,福建 莆田 351100;3.淮北師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,安徽 淮北 235000;4.西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,甘肅 蘭州 730070)
(n,m)函數(shù)是對稱密碼算法的基本部件之一,其研究重點(diǎn)在設(shè)計(jì)和分析兩個方面。設(shè)計(jì)主要是通過數(shù)學(xué)方法構(gòu)造出滿足多種密碼學(xué)性質(zhì)的函數(shù),而分析主要是研究函數(shù)的各種密碼學(xué)指標(biāo),這些密碼學(xué)指標(biāo)往往與其對應(yīng)的攻擊緊密聯(lián)系在一起。從(n,m)函數(shù)面對的各種攻擊來看,可以將密碼學(xué)指標(biāo)分為兩大類:
(1) 基于數(shù)學(xué)的傳統(tǒng)攻擊手段,例如線性攻擊、差分攻擊、代數(shù)攻擊、相關(guān)攻擊等,一些指標(biāo)主要有非線性度、相關(guān)免疫度和代數(shù)免疫度等;
(2) 基于物理的差分功耗分析手段,例如差分功耗攻擊,主要有信噪比[1]、透明階[2]和混淆系數(shù)[3]等。
文中重點(diǎn)討論信噪比、透明階和混淆系數(shù)這三個指標(biāo),以及這些指標(biāo)與傳統(tǒng)密碼學(xué)指標(biāo)的關(guān)系等。
差分功耗攻擊(Differential Power Attack,DPA)[4]是能量分析中一種強(qiáng)有力的攻擊手段,其原理是通過統(tǒng)計(jì)密碼設(shè)備或者密碼算法在加密運(yùn)算過程中泄漏的功耗消耗特征,來破譯出一些密鑰信息。該方法最早是在1999年由KOCHER等人[4]提出,當(dāng)時是對分組密碼數(shù)據(jù)加密標(biāo)準(zhǔn)(Data Encryption Standard,DES)進(jìn)行了差分功耗攻擊。這種方法后來被廣泛用于公鑰密碼算法和分組密碼算法的安全分析中。而在實(shí)驗(yàn)層面進(jìn)行差分功耗攻擊是在2002年由MESSERGES等人[5]提出。在此基礎(chǔ)上,漢明距離功耗模型被BRIER等人[6]提出,該模型驗(yàn)證了相關(guān)功耗分析(Correlation Power Analysis,CPA)攻擊,實(shí)驗(yàn)結(jié)果進(jìn)一步表明,CPA在某些方面相對DPA有較大優(yōu)勢,這也是后來CPA被廣泛使用的原因之一。以上的實(shí)驗(yàn)和一些模型都是針對非線性S盒展開分析,S盒作為對稱加密算法的主要非線性部件之一,對算法的安全性起著關(guān)鍵性作用,但是傳統(tǒng)密碼學(xué)性質(zhì)好的S盒未必能抵抗差分功耗分析。因此,必須對S盒的抗差分功耗攻擊指標(biāo)進(jìn)行系統(tǒng)研究。下面將從差分功耗分析角度給出三個密碼學(xué)指標(biāo)(信噪比、透明階和混淆系數(shù))的發(fā)展現(xiàn)狀。
第1個指標(biāo):信噪比(Signal-to-Noise Ratio,SNR)。該指標(biāo)是在2004年8月的CARDIS會議上被GUILLEY等人[1]提出。首先他們基于傳統(tǒng)密碼分析的框架對信息泄漏進(jìn)行完整建模,對于攻擊者來說可以獲取密鑰猜測值的Hamming權(quán)重的自相關(guān)值。該模型表明,當(dāng)S盒抵抗線性密碼分析能力增強(qiáng)時,S盒對應(yīng)的信噪比值也將隨之增大。但是從S盒抵抗DPA角度來說,信噪比越小,抵抗DPA越好。這就表明S盒的信噪比和S盒抵抗線性密碼分析之間存在著制約關(guān)系,兩者不能同時達(dá)到最好。通過信噪比模型和定義可以看出,非線性S盒的噪聲對密碼算法的DPA信號起著決定性作用。隨著該指標(biāo)出現(xiàn)也產(chǎn)生了一些研究結(jié)果[7]。
第2個指標(biāo):透明階(Transparency Order,TO)。該指標(biāo)是在2005年的FSE會議上被PROUFF[2]首次提出。文獻(xiàn)[2]基于差分功耗思想,建立了多入多出(n,m)函數(shù)與漢明距離模型的緊密關(guān)系,得到了S盒的透明階與傳統(tǒng)的一些密碼學(xué)性質(zhì)不能同時達(dá)到最好。隨著國內(nèi)外學(xué)者研究的深入,也衍生出了改進(jìn)的透明階概念(Redefining Transparency Order,RTO)[8]和修改的透明階(Modified Transparency Order,MTO)概念[9]。在新指標(biāo)和舊指標(biāo)的共同指引下得到了一系列研究成果[10-12]。
第3個指標(biāo):混淆系數(shù)(Confusion Coefficient,CC)。該指標(biāo)是在2012 年的密碼硬件和嵌入式系統(tǒng)國際研討會上被FEI等人[13]提出。研究表明,S盒的混淆系數(shù)值越大,S盒抵抗DPA能力就越強(qiáng)?;贔EI等人的結(jié)果,PICEK等人[14]在2014 年計(jì)算了不同大小的 S 盒的非線性度,得到了混淆系數(shù)方差。同年,邱爽等人[15]為了降低維數(shù)和混淆系數(shù)的個數(shù),對原始混淆系數(shù)進(jìn)行了修訂,給出了新的混淆系數(shù)定義?;谠撔露x,重新計(jì)算了DES針對各個備選密鑰的功耗差(Difference of Means,DoM)期望的分布。實(shí)驗(yàn)結(jié)果與利用修改后的混亂系數(shù)計(jì)算得到的DoM期望值相符。
因此,筆者試圖從數(shù)學(xué)理論角度來綜述(n,m)函數(shù)的這三個指標(biāo)的研究進(jìn)展,而不考慮其背后的物理實(shí)驗(yàn)背景。
2004年GUILLEY等人在研究DPA信號時提出了信噪比(SNR)概念[1]。
定義1[1]設(shè)F=(f1,f2,…,fm)是一個(n,m)函數(shù),則函數(shù)F的信噪比(SNR)定義為
(1)
緊接著,在2005年的FSE會議上,PROUFF擴(kuò)展了GUILLEY等人提出的多比特DPA攻擊[1]和功耗模型,提出了漢明重量模型,建立了S盒與DPA攻擊的關(guān)系,給出了(n,m)函數(shù)的透明階概念(TO)[2]。
定義2[2]設(shè)F=(f1,f2,…,fm)是一個(n,m)函數(shù),則函數(shù)F的透明階(TO)定義為
(2)
2017年CHAKRABORTY等人在研究(n,m)函數(shù)的TO基礎(chǔ)上,發(fā)現(xiàn)了TO的冗余,所以提出了改進(jìn)透明階概念(RTO)[8]。
定義3[8]設(shè)F=(f1,f2,…,fm)是一個(n,m)函數(shù),則函數(shù)F的改進(jìn)透明階(RTO)定義為
(3)
2019年周永彬等在研究(n,m)函數(shù)的RTO基礎(chǔ)上,通過多比特DPA(Multi-bit DPA)和變型多比特DPA(Variant multi-bit DPA)實(shí)驗(yàn),發(fā)現(xiàn)線性 (n,m)函數(shù)可以完全抵抗變型多比特DPA攻擊,但是線性(n,m)函數(shù)很容易受到DPA攻擊,為此提出了修改的透明階概念(Modified Transparency Order,MTO)[9]。
定義4[9]設(shè)F=(f1,f2,…,fm)是一個(n,m)函數(shù),則函數(shù)F的修改透明階(MTO)定義為
(4)
從定義2~4可以看出,TO與F=(f1,f2,…,fm)的分量函數(shù)自相關(guān)函數(shù)緊密聯(lián)系在一起,而RTO和MTO與F=(f1,f2,…,fm)的分量函數(shù)自相關(guān)函數(shù)和互相關(guān)函數(shù)緊密聯(lián)系在一起;定義3和4惟一不同在于絕對值的位置,這決定了在DPA攻擊中泄露的信息多少。
2012年,F(xiàn)EI等人在研究DPA統(tǒng)計(jì)模型時,建立了DPA成功率與密碼算法之間的定量關(guān)系?;谠摱筷P(guān)系,用一種新混淆分析法提取密碼算法的邊信道特性,提出了(n,m)函數(shù)的混淆系數(shù)概念(CC)[3]。
定義5[3]設(shè)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ù)的相關(guān)其它概念(例如擴(kuò)散性、代數(shù)免疫、相關(guān)免疫、全局雪崩準(zhǔn)則等)請參考文獻(xiàn)[16]。
GUILLEY等人[1]得到了平衡(n,m)函數(shù)信噪比的上下界、非平衡(n,m)函數(shù)信噪比的下界、Bent(n,m)函數(shù)信噪比的下界,并證明了當(dāng)(n,m)函數(shù)抵抗線性密碼分析能力增加時,信噪比也將隨之增加。2020年,周宇等人研究了布爾函數(shù)(即(n,1)函數(shù))的信噪比[7],給出了任意n元函數(shù)的信噪比緊的上界和緊的下界,以及下界與非線性度的關(guān)系,得到了n元函數(shù)信噪比與2個n-1元分解函數(shù)信噪比的關(guān)系。特別地,對于平衡布爾函數(shù),給出了信噪比更緊的上界和下界,最后給出了兩個n元函數(shù)相加與兩個n元函數(shù)乘積的信噪比與各自信噪比的關(guān)系,同時也給出了4元、5元平衡布爾函數(shù)信噪比的分布表。
對于F=(f1,f2,…,fm)的信噪比與分量函數(shù)的信噪比有如下關(guān)系。
定理1[7]設(shè)F=(f1,f2,…,fm)是一個(n,m)函數(shù),則
(6)
但是對于由分量函數(shù)信噪比決定的F=(f1,f2,…,fm)的信噪比上界,僅能給出(n,2)函數(shù)的結(jié)果,對于m≥3,很難給出精確的刻畫。
定理2[7]設(shè)F=(f1,f2)是一個(n,2)函數(shù),則
(7)
(8)
進(jìn)而得出
在此基礎(chǔ)上,得到一些(n,m)函數(shù)信噪比的上界或者下界,具體如表1[1]所示。
表1 (n,m)函數(shù)信噪比上界或者下界
表2 5元平衡布爾函數(shù)的信噪比分布
當(dāng)m=1時,(n,m)函數(shù)就是n元布爾函數(shù),其信噪比性質(zhì)較(n,m)函數(shù)刻畫得更清晰。其結(jié)果如下。
定理3[7]設(shè)f∈Bn,則1≤SSNR(f)≤2n/2,其中左邊等號成立,當(dāng)且僅當(dāng)f是仿射函數(shù),而右邊等號成立,當(dāng)且僅當(dāng)f是bent函數(shù)。
進(jìn)一步可以知道f的信噪比與非線性度的關(guān)系:SSNR(f)≥2n/(2n-2nl(f))。
(9)
而對于兩個變量不交的函數(shù),其和函數(shù)和積函數(shù)的信噪比結(jié)果如下。
定理5[7]設(shè)f∈Bn,g∈Bm,則
(1)SSNR(f+g)=SSNR(f)SSNR(g);
而對于滿足一定擴(kuò)散性的布爾函數(shù)來說,其信噪比上界如下。
通過程序計(jì)算[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所示。
在(n,m)函數(shù)的透明階發(fā)展中出現(xiàn)了三個不同概念,依次介紹如下。
(1) 2005年,PROUFF首次在FSE上提出(n,m)函數(shù)的透明階(TO)概念[2],在DPA攻擊的模型中發(fā)現(xiàn)了S盒的透明階與S盒的非線性不能同時達(dá)到最好,即如果S盒抵抗線性攻擊的能力越強(qiáng),S盒抵抗DPA攻擊的能力就越弱。緊接著,CARLET系統(tǒng)研究了高非線性S盒的透明階,得到了該S盒的透明階下界[26]。該結(jié)果反映了透明階與非線性度的關(guān)系,進(jìn)一步他也研究了其它一些高非線性函數(shù)(例如逆函數(shù)、Gold 函數(shù)、Kasami 函數(shù)),發(fā)現(xiàn)在理論上這些S盒具有較差的透明階。后來,F(xiàn)AN等人[27]通過引入一個精心設(shè)計(jì)的閾值濾波器提出了一種計(jì)算S盒透明階的快速實(shí)現(xiàn)方法,基于此,給出了兩種S盒透明階的優(yōu)化計(jì)算技術(shù)。MAZUMDAR等人[28]在2013 年得到了一些偶數(shù)元和奇數(shù)元S盒的透明階上界和下界,利用搜索方法得到了一類TO值優(yōu)于AES算法中的S 盒。2014年P(guān)ICEK等人[29]研究了輕量級分組密碼PRINCE,通過進(jìn)化算法得到了非線性度為4且透明階最低的S盒,以此生成具有改進(jìn)DPA相關(guān)特性的S盒。后來,SARKAR等人[30]針對(n,n)函數(shù),基于差分能量分析回答了如何在仿射等價(jià)下對S盒的選擇問題。同年MAZUMDAR[31]找到了在傳統(tǒng)密碼特性(如高非線性和低GAC絕對指示符)和透明階指標(biāo)方面都較好的S盒。
(2) 2017年,CHAKRABORTY等人指出TO指標(biāo)存在一定的局限性,給出了修改的透明階指標(biāo)(RTO)[8]。在該概念的引導(dǎo)下,PICEK等人基于遺傳算法和隨機(jī)搜索等算法搜索找到了一些抵抗 DPA好的S盒[29]。
2017年程讓在其碩士論文[10]中對RTO進(jìn)行了研究,推導(dǎo)出了RTO下界與分量函數(shù)Walsh譜值的關(guān)系,給出了RTO與非線性度之間的一種制約關(guān)系,并分別基于Maiorana-McFarland函數(shù)構(gòu)造法和Bracken-Leander函數(shù)構(gòu)造法得到了平衡且具有較低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ù)、旋轉(zhuǎn)對稱布爾函數(shù)(rotation symmetric Boolean functions)的透明階。
(3) 2019年周永彬等人[9]指出多比特DPA攻擊中RTO定義的不足,提出了修訂的透明階概念(MTO),對某些S盒進(jìn)行了實(shí)驗(yàn)仿真,進(jìn)一步分析了16類最優(yōu)(4,4)函數(shù)的仿射等價(jià)類MTO分布規(guī)律。
首先,給出2005年由PROUFF得到的擴(kuò)散準(zhǔn)則與透明階關(guān)系[2]。
定理7[2]設(shè)F=(f1,f2,…,fm)是一個(n,m) 函數(shù)(m≤n)。如果F滿足t階擴(kuò)散準(zhǔn)則,則
(10)
緊接著,對于任意(n,m)函數(shù)來說,其透明階介于0和m之間。
定理8[2]設(shè)F=(f1,f2,…,fm)是一個(n,m) 函數(shù),則0≤TTO(F)≤m。
而對于(n,m)函數(shù)來說,其透明階的下界與分量函數(shù)的Walsh譜有如下關(guān)系[26]。
定理9[26]設(shè)F=(f1,f2,…,fn)是一個(n,n) 函數(shù),則
(11)
CHAKRABORTY等人在TO的基礎(chǔ)上,分析了仿射變換下RTO的變化情況,指出對 (n,m) 函數(shù)的輸入變量做仿射變換不改變RTO的值,而對(n,m) 函數(shù)的輸出值做某個仿射變換后RTO的值會發(fā)生改變[8]。
定理10[8]設(shè)F=(f1,f2,…,fm)是一個平衡(n,m) 函數(shù),則對任意的n階可逆矩陣A,有RRTO(F°A)=RRTO(F)。
2017年程讓在其碩士論文中證明了分量函數(shù)非零線性組合后的函數(shù)最大Walsh譜與RTO的關(guān)系[10]。
結(jié)合文獻(xiàn)[8]和[9]的結(jié)果,可以看到MMTO(F)和RRTO(F)有共同的下界。
定理12[8-9]設(shè)F=(f1,f2,…,fm)是一個(n,m) 函數(shù),則MMTO(F)和RRTO(F)有共同的下界,即
(12)
對于任意的F=(f1,f2,…,fm),文獻(xiàn)[9]證明了對任意的n階可逆矩陣A有MMTO(F)=MMTO(F°A),但存在某些n階可逆矩陣A能使得MMTO(F)≠M(fèi)MTO(A°F)。這也就表明MTO不是仿射變換下的不變量。根據(jù)該結(jié)論就可以給出16類最優(yōu) (4,4)S盒的仿射等價(jià)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)的分布圖
當(dāng)m=1時,(n,m)函數(shù)F就是n元布爾函數(shù),此時有TTO(F)=RRTO(F)=MMTO(F)。
文獻(xiàn)[29]基于漢明重量對給定的CPA選擇函數(shù)給出了計(jì)算混淆系數(shù)的方法。對所有密鑰對ka,kb(ka≠kb),計(jì)算κ(ka,kb)=E[(HW(F(in+ka))-HW(F(in+kb)))2]。
定理14[29]設(shè)F=(f1,f2,…,fm)是一個(n,m) 函數(shù),則對密鑰的第ki,kj,kh對應(yīng)的三方混淆系數(shù)如下:
(13)
針對F=(f1,f2,…,fm)進(jìn)行DPA時各個備選密鑰的功耗差(DoM)期望的分布,F(xiàn)EI等人[13]得到如下結(jié)論:
定理15[13]設(shè)F=(f1,f2,…,fm)是一個(n,m) 函數(shù),kc為錯誤密鑰猜測值,kg為正確密鑰,kc和kg對應(yīng)的DoM分別為δc和δg,則對Δ(kc,kg)有
(1)E[Δ(kc,kg)]=2κ(kc,kg)ε;
而關(guān)于混淆系數(shù)與成功率,F(xiàn)EI等人[3]得到成功率的公式。
定理16[3]基于CPA泄露模型,在對稱密鑰假設(shè)下,CPA的漸進(jìn)成功率為
(14)
其中,K**表示另外一個(NK-1)(NK-1)維混淆矩陣。
在混淆系數(shù)計(jì)算中,首先得根據(jù)不同的密鑰ki,kj計(jì)算出κ(ki,kj)。為此,文獻(xiàn)[14]基于仿射變換給出了16類最優(yōu)4比特S盒[17]和一些公開算法中S盒的κ值大小(如表3所示)。
表3 一些 (4,4) S盒κ值
2014年,邱爽等人[15]指出,F(xiàn)EI[3]提出的混淆系數(shù)定義中存在冗余,并且修改了混亂系數(shù)的定義,重新構(gòu)建了DPA模型中算法相關(guān)的部分,其定義如下:
定義6[3]設(shè)F=(f1,f2,…,fm)是一個(n,m)函數(shù),則函數(shù)F的修改混淆系數(shù)(RCC)定義為
(15)
其中,of表示兩個密鑰之間的異或關(guān)系KS1+KS2,假設(shè)F(·)b表示選定F的某一位的輸出。
可以看出,RRCC(F)只與兩個密鑰之間的異或值相關(guān),和混淆系數(shù)κ值的關(guān)系為
RRCC(KS1+KS2)=κ(KS1,KS2) ,
(16)
根據(jù)這個關(guān)系式可知,修改后的混淆系數(shù)在個數(shù)方面有較大的下降。
根據(jù)定義6,邱爽等人[15]針對DES算法得到了DPA各個假設(shè)密鑰產(chǎn)生的均值差,計(jì)算了修改混淆系數(shù),從實(shí)驗(yàn)角度驗(yàn)證了修改混淆系數(shù)的合理性。
首先,對于一些公開算法中(4,4) S盒,2014年文獻(xiàn)[29]給出了這些常用密碼學(xué)指標(biāo)的對照表(如表4所示)。
表4 一些 (4,4) S盒的各種密碼學(xué)指標(biāo)對照表
然后,對于一些公開算法中(8,8) S盒,2018年文獻(xiàn)[32]給出了這些常用密碼學(xué)指標(biāo)的對照表(如表5所示)。
表5 一些 (8,8) S盒的各種密碼學(xué)指標(biāo)對照表
最后,對于一些構(gòu)造得到的(8,8) S盒,文獻(xiàn)[32]給出了這些常用密碼學(xué)指標(biāo)的對照表(如表6所示)。
表6 一些 (8,8) S盒構(gòu)造方法的各種密碼學(xué)指標(biāo)對照表
(n,m)函數(shù)是對稱密碼算法中的基本部件,其安全性對密碼算法安全性起著重要作用。經(jīng)過國內(nèi)外學(xué)者多年來的共同努力,在(n,m)函數(shù)抵抗差分功耗攻擊方面已經(jīng)取得了豐富的成果。文中重點(diǎn)綜述了(n,m)函數(shù)的三個密碼學(xué)指標(biāo)(信噪比、透明階和混淆系數(shù))。由于文章篇幅所限,對如何構(gòu)造滿足良好信噪比、透明階和混淆系數(shù)的(n,m)函數(shù)的研究成果介紹相對簡單,感興趣的讀者可以進(jìn)一步查閱相關(guān)參考文獻(xiàn)。結(jié)合目前(n,m)函數(shù)的這三個密碼學(xué)指標(biāo)的研究結(jié)果,以及抗側(cè)信道模型的分析,作者認(rèn)為下列問題值得進(jìn)一步研究:
(1) 信噪比、透明階和混淆系數(shù)分別與傳統(tǒng)密碼學(xué)指標(biāo)的關(guān)系已經(jīng)研究出了一些結(jié)論,但是還不夠詳盡,需要進(jìn)一步研究。
(2) 信噪比、透明階和混淆系數(shù)之間相互的制約關(guān)系研究的較少,特別是針對某些密碼結(jié)構(gòu),例如某些特殊構(gòu)造的4比特S盒[48]、線性移位寄存器[49],等等。
(3) 構(gòu)造符合特定場景需求且滿足一定密碼學(xué)性質(zhì)的S盒是密碼算法設(shè)計(jì)的重要研究方向,特別是構(gòu)造同時抵抗側(cè)信道攻擊和抵抗傳統(tǒng)密碼攻擊(某些特殊模型的快速代數(shù)攻擊[50])的S盒是研究的重點(diǎn)。