PRESENT代數(shù)故障攻擊的改進(jìn)與評估

黃靜，趙新杰，張帆，郭世澤，周平，陳浩，楊建

（1. 61541部隊(duì)3室，北京 100083；2. 北方電子設(shè)備研究所，北京 100191；3. 浙江大學(xué)信息與電子工程學(xué)院，浙江 杭州 310027；4. 保密通信重點(diǎn)實(shí)驗(yàn)室，四川 成都 610041；5. 軍械工程學(xué)院信息工程系，河北 石家莊 050003）

PRESENT代數(shù)故障攻擊的改進(jìn)與評估

黃靜1，趙新杰2，張帆3,4，郭世澤2，周平5，陳浩5，楊建3

（1. 61541部隊(duì)3室，北京 100083；2. 北方電子設(shè)備研究所，北京 100191；3. 浙江大學(xué)信息與電子工程學(xué)院，浙江 杭州 310027；4. 保密通信重點(diǎn)實(shí)驗(yàn)室，四川 成都 610041；5. 軍械工程學(xué)院信息工程系，河北 石家莊 050003）

提出了一種基于代數(shù)分析的PRESENT故障攻擊改進(jìn)方法，將代數(shù)分析用于密碼和故障方程構(gòu)建，通過逆向構(gòu)建加密方程來加快求解速度；提出了一種故障注入后的密鑰剩余熵評估方法，可評估不同故障模型下的PRESENT抗故障攻擊安全性；最后對智能卡上的8位智能卡上的PRESENT實(shí)現(xiàn)進(jìn)行了時(shí)鐘毛刺故障注入，最好情況下1次故障注入即可恢復(fù)主密鑰，這是PRESENT故障攻擊在數(shù)據(jù)復(fù)雜度上的最好結(jié)果。

代數(shù)分析；輕量級分組密碼；故障攻擊；可滿足性求解；時(shí)鐘毛刺

1 引言

近年來，物聯(lián)網(wǎng)的發(fā)展熱潮帶動了便攜設(shè)備、無線傳感器、智能卡等微型計(jì)算設(shè)備的廣泛應(yīng)用。不同于傳統(tǒng)的計(jì)算設(shè)備，這些微型設(shè)備的計(jì)算能力有限、存儲容量低、功耗要求低，傳統(tǒng)的分組密碼實(shí)現(xiàn)在這些設(shè)備上略顯龐大，會增加物聯(lián)網(wǎng)功耗、降低效率。因此，輕量級分組密碼應(yīng)運(yùn)而生，典型算法包括：PRESENT、MIBS、LED、Piccolo、LBlock等，這些算法大都可在3 000個(gè)電路門內(nèi)實(shí)現(xiàn)，特別適用于資源受限環(huán)境下的加解密需要。

PRESENT是Bogdanov等[1]提出的一種超輕量級分組密碼算法。算法采用SPN結(jié)構(gòu)，分組長度為64位，密鑰長度支持 80位和 128位，分別對應(yīng)PRESENT-80和PRESENT-128。由于PRESENT采用了基于位的置換操作，硬件執(zhí)行效率很高，PRESENT-80加密僅需 1 570個(gè)門電路。目前，PRESENT-80已經(jīng)被選定為80位的國際輕量級分組密碼標(biāo)準(zhǔn)ISO/IEC 29192-2；基于PRESENT-80可以設(shè)計(jì)輕量級散列算法[2]。當(dāng)前，PRESENT的安全性分析主要從設(shè)計(jì)安全性和實(shí)現(xiàn)安全性 2個(gè)層面進(jìn)行。

在設(shè)計(jì)安全性分析方面，文獻(xiàn)[3～5]基于差分攻擊對PRESENT進(jìn)行了分析，最多可以分析到26輪；文獻(xiàn)[6,7]基于線性攻擊對PRESENT進(jìn)行了分析，最多可以分析到27輪；Albrecht等[8]基于代數(shù)攻擊對PRESENT進(jìn)行了分析，最多可以分析到19輪；在2015年的美密會上，Blondeau[9]構(gòu)建了一個(gè)已知密鑰的區(qū)分器，可以對全輪的PRESENT進(jìn)行分析，攻擊的數(shù)據(jù)復(fù)雜度為235.58，時(shí)間復(fù)雜度為256次加密?？梢钥闯?，全輪的PRESENT仍然相對安全，傳統(tǒng)密碼分析方法在有限復(fù)雜度內(nèi)攻破 PRESENT的可行性不高。

在實(shí)現(xiàn)安全性方面，現(xiàn)有研究主要集中在旁路攻擊和故障攻擊2個(gè)方面。在旁路攻擊方面，文獻(xiàn)[10,11]對PRESENT抗差分功耗分析、相關(guān)功耗分析能力進(jìn)行了評估，幾百條功耗曲線可以恢復(fù)完整密鑰；文獻(xiàn)[12]將代數(shù)分析引入到PRESENT功耗攻擊，一條加密曲線可以恢復(fù)完整密鑰，但需要在已知密鑰下預(yù)先采集幾百條曲線建立功耗模板；文獻(xiàn)[13]將立方體分析引入到PRESENT功耗攻擊中，990條功耗曲線可在未知算法設(shè)計(jì)下恢復(fù)PRESENT-80的72位密鑰。在故障攻擊方面，Li等[14]首次提出了針對PRESENT-80的差分故障攻擊，基于Nibble（半字節(jié)）故障模型，在故障注入到第 29輪的查找S盒輸入時(shí)，40～50次故障注入可以恢復(fù)64位后白化密鑰；Wang等[15]提出了針對 PRESENT密鑰擴(kuò)展的差分故障攻擊，假定1個(gè)Nibble的故障能夠注入到第31輪密鑰生成中，64次故障注入可以恢復(fù)51位密鑰；Zhao等[16]提出了一種基于故障傳播模式分析的PRESENT差分故障攻擊，基于第29輪Nibble故障模型，可使用8次和16次故障注入分別將PRESENT-80/128的主密鑰搜索空間降低到214.7和221.1；Gu等[17]將統(tǒng)計(jì)分析引入到故障分析，基于Nibble故障模型，通過構(gòu)建最大似然和歐幾里德距離區(qū)分器，可使用10 000次故障注入對倒數(shù) 8輪以內(nèi)的故障進(jìn)行分析；Wu等[18]將代數(shù)攻擊引入到PRESENT故障分析，通過分析差分S盒，可基于第29輪Nibble故障模型使用 2次有效錯(cuò)誤密文恢復(fù)主密鑰；Jeong等[19]基于第28輪雙字節(jié)故障模型，可使用2次和3次故障注入將PRESENT-80/128的密鑰搜索空間降低到1.7和222.3。

通過分析已有PRESENT故障攻擊，本文發(fā)現(xiàn)已有攻擊大都基于Nibble故障模型，最多可以分析倒數(shù)3輪。已有的差分故障攻擊需要手工對故障傳播路徑進(jìn)行分析，恢復(fù)密鑰所需故障注入次數(shù)相對較多[14～16]，文獻(xiàn)[19]所需的故障次數(shù)雖然較少，但雙字節(jié)故障在實(shí)際環(huán)境中（PRESENT大都是用于8位處理器）很難注入；同時(shí)，已有PRESENT統(tǒng)計(jì)故障攻擊需要對大量錯(cuò)誤密文進(jìn)行統(tǒng)計(jì)分析，在故障利用率上并不是最優(yōu)的；已有的PRESENT代數(shù)故障分析[18]需要特定的故障密文，為了得到這些特定的故障密文，攻擊者需要進(jìn)行多次故障注入和篩選，對故障模型有著特殊的要求，在故障注入次數(shù)上也不是最優(yōu)的。

為分析、改進(jìn)、評估已有PRESENT故障攻擊，本文開展了大量的研究工作，主要?jiǎng)?chuàng)新點(diǎn)如下。

1)本文提出了一種基于代數(shù)分析的PRESENT故障攻擊改進(jìn)方法，通過逆向構(gòu)建加密方程來加快求解速度，構(gòu)建了更為緊湊、適合代數(shù)故障分析的方程，可適用到不同故障模型，并利用解析器進(jìn)行密鑰自動化求解。

2)本文提出了一種故障注入后的密鑰剩余熵評估方法，通過仿真實(shí)驗(yàn)評估了不同故障模型下的PRESENT抗故障攻擊安全性。實(shí)驗(yàn)結(jié)果可對已有PRESENT故障攻擊進(jìn)行解釋和分析，得到更準(zhǔn)確的故障注入后的密鑰搜索空間降低情況；同時(shí)可改進(jìn)已有攻擊，尋找最優(yōu)故障模型，降低攻擊所需故障注入次數(shù)、延伸故障分析輪數(shù)。

3)基于 8位故障模型，首次對符合 ISO/IEC 7816-3協(xié)議智能卡上的PRESENT軟件實(shí)現(xiàn)進(jìn)行了2類故障注入物理實(shí)驗(yàn)，最佳結(jié)果表明1次故障注入可恢復(fù)PRESENT密鑰，這是PRESENT故障攻擊在數(shù)據(jù)復(fù)雜度方面的最好結(jié)果。

需要說明的是，本文方法可用于指導(dǎo)攻擊者根據(jù)故障注入條件選取最佳故障模型、新型算法設(shè)計(jì)者評估設(shè)計(jì)算法抗故障攻擊能力、已有算法實(shí)現(xiàn)者對一定輪數(shù)內(nèi)的算法進(jìn)行故障攻擊防護(hù)。

2 PRESENT算法與故障模型

2.1 PRESENT算法設(shè)計(jì)

PRESENT采用SPN結(jié)構(gòu)，分組長度為64位，支持80位、128位2種密鑰長度，共迭代31輪。

1)加密過程

輪函數(shù)F由輪密鑰加、S盒代換、移位置換這3部分組成。

① 輪密鑰加：64位輪輸入同輪密鑰異或。

② S盒代換：輪密鑰加輸出查找16次4進(jìn)4出的S盒。

③ 移位置換：通過置換表P(i)對S盒代換輸出按位重新排列。

為提高算法安全性，PRESENT在第31輪后使用64位白化密鑰K32進(jìn)行后期白化操作。

2)密鑰擴(kuò)展算法

將初始主密鑰存儲在寄存器 K中，表示為k0k1…k79。第 i輪密鑰Ki由寄存器K的前64位組成。當(dāng)生成第i輪密鑰Ki后，K通過以下方法進(jìn)行更新。

其中，round_counter為當(dāng)前的加密輪數(shù)。

2.2 PRESENT算法軟件實(shí)現(xiàn)

PRESENT算法的典型軟件實(shí)現(xiàn)包括2種[20]：1)開銷優(yōu)先實(shí)現(xiàn) PRESENT_SIZE，使用了 4進(jìn) 4出的S盒，其中，輪密鑰加、S盒代換以Nibble為基本運(yùn)算單位，優(yōu)點(diǎn)是實(shí)現(xiàn)規(guī)模小，代碼更加緊湊，但不足是速度較慢；2)速度優(yōu)先實(shí)現(xiàn) PRESENT_SPEED，將2個(gè)相鄰的S盒使用1個(gè)8進(jìn)8出的查找表來實(shí)現(xiàn)，這樣輪密鑰加、S盒代換均以字節(jié)為單位進(jìn)行計(jì)算，執(zhí)行速度較快。

2.3 故障模型

一般來說，故障模型由5元組F(X,λ,w,t,f)構(gòu)成。

X：故障注入針對的中間狀態(tài)。

X*：故障注入后錯(cuò)誤的中間狀態(tài)。

λ：X的長度。

w：故障寬度。

Xi：X中第i個(gè)單元，X=X1|| X2||…||Xm。

t：故障單元索引。

f：故障差分，f=Xt+Xt*。

本文利用的故障模型為PRESENT加密過程中查找S盒操作產(chǎn)生故障，具體的故障模型參數(shù)設(shè)置見后續(xù)幾個(gè)小節(jié)。

3 改進(jìn)的PRESENT代數(shù)故障分析方法

3.1 攻擊框架

圖1給出了本文利用的代數(shù)故障攻擊框架，由以下3部分組成。

1)故障注入

圖1 代數(shù)故障攻擊框架

故障注入是指攻擊者通過光學(xué)輻射、電壓毛刺、時(shí)鐘毛刺等方法修改芯片工作條件，使密碼算法在某個(gè)輪次計(jì)算過程中注入故障產(chǎn)生錯(cuò)誤，并將錯(cuò)誤傳播至密文。故障注入屬于在線攻擊階段。故障注入方法和目標(biāo)密碼芯片的類型與故障模型直接相關(guān)。如對于8位微控制器上的軟件實(shí)現(xiàn)，使用電壓或者時(shí)鐘故障誘導(dǎo)的故障一般為8位，而使用光學(xué)輻射誘導(dǎo)則可以達(dá)到單位精度。

2)方程構(gòu)建

方程構(gòu)建是指攻擊者構(gòu)建出給定正確和錯(cuò)誤加密樣本的代數(shù)方程，屬于離線攻擊階段。一般來說，攻擊者需要構(gòu)建出密碼算法和故障方程。在密碼算法代數(shù)方程構(gòu)建方面，攻擊者可以采取不同的策略。一方面，可以構(gòu)建出從故障注入輪到密文正確和錯(cuò)誤加密的代數(shù)方程，然后加上一個(gè)正確加密的全輪方程（稱為校驗(yàn)方程），并和故障方程聯(lián)立求解恢復(fù)唯一的密鑰；同時(shí)，攻擊者也可以不使用校驗(yàn)方程，此時(shí)方程可能會有多個(gè)可滿足解，可以利用支持多個(gè)解的解析器來統(tǒng)計(jì)故障注入后的密鑰搜索空間。另一方面，攻擊者可以選取不同方法構(gòu)建密碼或者故障方程，如S盒的方程構(gòu)建就有待定系數(shù)法、矩陣法、真值表構(gòu)造法等。此外，攻擊者還可以選定是正向還是逆向構(gòu)建密碼算法方程。

3)方程求解

首先將代數(shù)方程轉(zhuǎn)化為解析器可以理解的格式，然后利用解析器進(jìn)行密鑰求解。方程求解策略有多種，如基于可滿足性問題的求解策略，典型解析器包括zChaff、MiniSAT、CryptoMiniSAT等，再如基于混合整數(shù)編程問題的求解策略，典型解析器有 SCIP、Gurobi等。本文選取專門用于密碼代數(shù)分析的解析器CryptoMiniSAT進(jìn)行方程求解，可以自動對任意長度的異或表達(dá)式進(jìn)行切割，十分便于密碼方程構(gòu)建。此外，CryptoMiniSAT支持多個(gè)解的輸出，可以統(tǒng)計(jì)故障注入后的密鑰搜索空間。

3.2 PRESENT代數(shù)方程構(gòu)建

1)代數(shù)故障分析密碼整體結(jié)構(gòu)構(gòu)建策略

在代數(shù)故障分析中，密鑰分析常是從密文開始，因此從密文開始反向構(gòu)建加密方程，可以有效降低求解時(shí)間[21,22]，構(gòu)建方法如圖2所示。同時(shí)，密鑰擴(kuò)展方程建議也反向構(gòu)建。PRESENT采用了SPN結(jié)構(gòu)，每輪輸出同輸入有很大差異，需要首先求出每個(gè)密碼操作逆運(yùn)算函數(shù)，再為之建立方程。

圖2 代數(shù)故障分析密碼整體結(jié)構(gòu)構(gòu)建策略

2)PRESENT代數(shù)故障分析方程組構(gòu)建算法算法1給出了PRESENT故障分析代數(shù)方程組構(gòu)建過程，如下所示。

算法 1PRESENT代數(shù)故障分析方程組構(gòu)建算法

輸入故障注入數(shù)量(N)；注入故障的加密輪(r)；故障寬度(w)；故障位置是否已知標(biāo)志位(b)

輸出代數(shù)故障分析所需方程

Step1構(gòu)建密鑰擴(kuò)展方程

If (b=1){//逆向構(gòu)建全輪密鑰擴(kuò)展方程

For(i=31;i≥1;i? ?)

GenerateKS_R(i);}

Else { //逆向構(gòu)建倒數(shù)31?r輪密鑰擴(kuò)展方程

For(i=31;i≥r;i? ?)

GenerateKS_R(i); }

Step2逆向構(gòu)建倒數(shù)31?r輪正確和錯(cuò)誤加密方程、故障方程

RandomPlaintextGenerating();//產(chǎn)生攻擊所需的隨機(jī)加密明文

For(i=0; ilt;N; i++){

Ci=E(Pi,K)//第i個(gè)明文正確加密

For(j=31; j≥r; j? ?)//逆向構(gòu)建倒數(shù)31?r輪加密方程

GenerateES_R(j);

Generate_Input_ES(Ci)//輸入正確密文

Ci*=FaultInjecting(E(Pi,K))//第i個(gè)明文加密注入故障

For(j=31; j≥r; j? ?)//逆向構(gòu)建倒數(shù)31?r輪加密方程

GenerateES_R(j);

Generate_Input_ES(Ci*)//輸入錯(cuò)誤密文

Generate_Faults_ES(f=X+X*)//構(gòu)建故障方程

Step3逆向構(gòu)建驗(yàn)證故障方程

VerifyPlaintextGenerating(Pv)//生成隨機(jī)驗(yàn)證明文

Cv=E(Pv,K)//驗(yàn)證明文正確加密

For(i=31; i≥1; i??)//逆向構(gòu)建全輪加密方程

GenerateES_R(i);

Generate_Input_ES(Pv,Cv)

可以看出，方程分為3部分。第1部分為密鑰擴(kuò)展方程，整個(gè)攻擊過程中只需構(gòu)建一次；第2部分為加密和故障方程，需要為每次正確和錯(cuò)誤加密建立方程；第3部分為可選部分，主要構(gòu)建用于密鑰校驗(yàn)的明密文方程。需要說明的是，代數(shù)故障方程構(gòu)建分為2種模式。第1種模式是含校驗(yàn)方程時(shí)，稱為Type A模式，此時(shí)方程求解只有唯一解。第2種模式為不含校驗(yàn)方程模式，稱之為Type B模式，此時(shí)代數(shù)方程會包含多個(gè)可滿足解、代數(shù)方程規(guī)模較小，求解速度較快。

3)PRESENT密鑰擴(kuò)展方程構(gòu)建

下面給出密鑰擴(kuò)展方程的逆向構(gòu)建方法。正向密鑰擴(kuò)展函數(shù)由左移61位、查找S盒、異或輪常量組成，則逆向密鑰擴(kuò)展函數(shù)由異或輪常量、查找逆S盒、右移61位組成。

① 異或輪常量函數(shù)

令異或輪常量函數(shù)輸入為(x0||x1||…||x79)，輸出為(y0||y1||…||y79)，輪常量用(z0||z1||…||z79)來表示，則異或輪常量函數(shù)可表示為

② 逆S盒函數(shù)

令逆 S盒函數(shù)輸入為(x0||x1||x2||x3)，輸出為(y0||y1||y2||y3)，則逆S盒代數(shù)方程可表示為

需要說明的是，PRESENT密鑰擴(kuò)展每輪只查找1次S盒。

③ 右移61位函數(shù)

令函數(shù)輸入為(x0||x1||…||x79)，輸出為(y0||y1||…||y79)，則右移函數(shù)代數(shù)方程可表示為

4)PRESENT加密方程構(gòu)建

PRESENT加密輪函數(shù)由輪密鑰加、S盒代換、置換函數(shù)組成，則逆輪函數(shù)由逆置換函數(shù)、逆S盒代換、逆輪密鑰加組成。

① 逆置換函數(shù)

令逆置換函數(shù)輸入為(x0||x1||…||x63)，輸出為(y0||y1||…||y63)，則逆置換函數(shù)代數(shù)方程可表示為

③ 逆S盒代換

逆S盒代換方程如式(2)所示。這里，每次需要查找16次S盒。

③ 逆輪密鑰加

令逆S盒代換的輸出為(x0||x1||…||x63)，輪密鑰為(y0||y1||…||y63)，逆輪密鑰加輸出為(z0||z1||…||z63)，則逆輪密鑰加可表示為

3.3 故障代數(shù)方程構(gòu)建

令 X表示 λ位正確加密狀態(tài)，則 X=(x0||x1||…||x63)；令X*表示注入寬度為w位的故障后的λ位錯(cuò)誤加密狀態(tài)，X*=(x0*||x1* ||…||x63*)，故障可能位置有m個(gè)令Z表示X和X*的故障差分。

根據(jù)故障寬度大小w不同，Z可以被劃分為m個(gè)w位變量，Z=(Z0||Z1||…||Zm?1)

根據(jù)攻擊者是否已知故障索引值t，Z可以用不同的代數(shù)方程來表示。

1)故障索引t已知

假設(shè)t值已知，則Z可表示為

Zt是一個(gè)非0的w位變量，可通過引入單位變量ut來表示Zt是否非0。

根據(jù)式(8)和式(9)，Z可通過引入w+1個(gè)變量和w(m+1)+2個(gè)交集普通方程（CNF）變量來表示。

2)故障索引t未知

在實(shí)際攻擊中，故障索引t可能是未知的，可通過引入m個(gè)變量ui來表示Zi是否被注入故障。

如果ui=0，則 Zi即為注入故障的位。由于 u0,u1,…,um?1有且只有一個(gè)為0，則可表示為

根據(jù)上式，Z可通過引入 m(w+2)個(gè)變量和m(2w+0.5m+1.5)+1個(gè)CNF變量來表示。需要說明的是，式(11)可適用于不同的w、m、λ參數(shù)。

3.4 主密鑰搜索空間評估

由3.1節(jié)和3.2節(jié)可知，根據(jù)是否引入校驗(yàn)方程，代數(shù)故障分析方程求解可分為唯一解求解（Type A）和多個(gè)解求解（Type B）2種模式。需要說明的是，一般的可滿足性問題（SAT）解析器大都僅支持 Type A模式，不支持 Type B模式，CryptoMiniSAT解析器從v2.9.4版本開始支持多個(gè)解輸出。在Type B模式下，令φ(K)表示故障注入后的剩余密鑰熵，即密鑰搜索空間求 Log2結(jié)果，下面簡要給出如何利用CryptoMiniSAT估計(jì)φ(K)。令L表示主密鑰K的長度，N表示一次故障攻擊的故障注入次數(shù)，θ表示輸入的已知密鑰位數(shù)量。為了準(zhǔn)確地評估φ(K)，θ一般從最大值L開始設(shè)定，逐漸降低到0。令 η(θ)表示解析器，根據(jù)給定 θ得到的可滿足解數(shù)量。在實(shí)際攻擊中發(fā)現(xiàn)，如果一次代數(shù)故障攻擊中可滿足解的數(shù)量大于218，解析器很難在有限時(shí)間內(nèi)找到所有解。為此，設(shè)定了一個(gè)多個(gè)解空間上限 τ。下面給出主密鑰搜索空間的窮舉算法。

算法2剩余密鑰熵評估算法（Type B模式）

輸入L,N,θ,τ

輸出φ(K)

對于PRESENT攻擊，L設(shè)定為80，τ設(shè)定為218。當(dāng) η(θ)≥τ 且 θ＞0 時(shí)，φ(K)≈θ+lb(η(θ))，由于已知的θ位密鑰可能在后續(xù)攻擊中被恢復(fù)，此時(shí)一般實(shí)際的 φ(K)值會比 θ+lb(η(θ))要小，也就是此時(shí)得到了φ(K)值的一個(gè)上限估計(jì)；當(dāng)θ=0時(shí)，等價(jià)于在未知密鑰下的代數(shù)故障攻擊，φ(K)=lb(η(θ))。

4 PRESENT抗故障攻擊能力評估

本節(jié)的故障注入是通過仿真實(shí)現(xiàn)的，故障攻擊物理實(shí)驗(yàn)細(xì)節(jié)可參考第5節(jié)。

4.1 第29輪隨機(jī)Nibble故障攻擊

在N=1時(shí)，使用在第29輪S盒輸入進(jìn)行了注入隨機(jī)Nibble（w=4）故障實(shí)驗(yàn)，攻擊在Type B求解模式下執(zhí)行了100次，得到的φ(K)統(tǒng)計(jì)如圖3所示。

圖3 第29輪注入單次Nibble故障后φ(K)統(tǒng)計(jì)

根據(jù)圖3，φ(K)可被降低到54～78位，平均值為 70.58位，φ(K)平均被降低了 9.42位，8～10次故障注入即有望將 φ(K)降低到較小值。需要說明的是，φ(K)的波動主要取決于故障注入后在后續(xù)輪次中傳播影響到的S盒數(shù)量。如果最后一輪查找S盒出錯(cuò)數(shù)量較少時(shí)，如2～4時(shí)，φ(K)的取值則較大；否則較小。

圖4給出了第29輪注入8次隨機(jī)Nibble故障后的密鑰剩余熵 φ(K)的統(tǒng)計(jì)?？梢钥闯觯?次故障注入后φ(K)平均可被降低為8.13位。需要說明的是，8次故障注入是平均值，在故障影響的S盒數(shù)量較大的情況下，3次故障注入可將 φ(K)降低到較小范圍。

圖4 第29輪注入8次Nibble故障后φ(K)統(tǒng)計(jì)

4.2 第28輪隨機(jī)Nibble故障攻擊

1)第28輪注入Nibble故障

在N=1時(shí)，在第28輪S盒輸入進(jìn)行了注入隨機(jī)Nibble（w=4）故障實(shí)驗(yàn)，攻擊執(zhí)行了100次，得到的φ(K)統(tǒng)計(jì)如圖5所示。

圖5 第28輪注入1次Nibble故障后φ(K)統(tǒng)計(jì)

可以看出：φ(K)取值符合指數(shù)分布，取值范圍大致為26～72，平均被降低到51.49，攻擊效果比第29輪攻擊好，2～3次故障注入有望恢復(fù)主密鑰。

N=3時(shí)，100次故障攻擊后φ(K)統(tǒng)計(jì)如圖6所示。φ(K)可被降低到12以內(nèi)，平均被降低到4.05。

4.3 不同故障寬度、深度攻擊比較

為研究不同故障寬度對攻擊的影響，首先對第29輪隨機(jī)單位故障（w=1）、隨機(jī)Nibble故障（w=4）、隨機(jī)單字節(jié)故障（w=8）、隨機(jī)雙字節(jié)故障（w=16）、隨機(jī)4字節(jié)故障（w=32）進(jìn)行了代數(shù)故障攻擊實(shí)驗(yàn)，分別執(zhí)行100次攻擊實(shí)驗(yàn)，得到的φ(K)統(tǒng)計(jì)如圖7所示。

圖6 第28輪注入3次Nibble故障后φ(K)統(tǒng)計(jì)

圖7 第29輪注入不同寬度故障φ(K)統(tǒng)計(jì)

可以看出，φ(K)大致為44～76，如果故障傳播影響的S盒較多，3次注入即可恢復(fù)80位主密鑰。需要說明的是，Nibble隨機(jī)故障模型下，如果攻擊執(zhí)行次數(shù)較多（一般要 10萬次左右），從中篩選出第29輪1次故障注入后影響最后一輪16次查找S盒操作的故障樣本，本文發(fā)現(xiàn)單次故障注入后可將 φ(K)降低到40以內(nèi)，2次故障注入可恢復(fù)完整主密鑰。

表1給出了一次故障注入下PRESENT代數(shù)故障攻擊平均可恢復(fù)的密鑰位（即 80?φ(K)）。第 29輪注入故障時(shí)，單位故障模型平均恢復(fù)密鑰位最多；單字節(jié)故障模型次之，Nibble、雙字節(jié)故障模型相對接近；4字節(jié)故障模型則接近于單字節(jié)故障模型，這主要是由于4字節(jié)故障模型在很大概率上可以導(dǎo)致最后一輪16次查找S盒出錯(cuò)導(dǎo)致的。

表1 N=1時(shí)攻擊平均恢復(fù)密鑰位

為了解不同深度、寬度條件下的攻擊影響，本文將攻擊擴(kuò)展到第28輪，針對w的5個(gè)參數(shù)值分別進(jìn)行了100次攻擊實(shí)驗(yàn)，得到的φ(K)統(tǒng)計(jì)如圖8所示。1次故障注入下w=1、4、8、16時(shí)均有很大概率將φ(K)降低到40以內(nèi)，有的甚至可降低到20以內(nèi)，1～2次故障注入后有望恢復(fù)主密鑰；w=32時(shí)大部分情況下可將φ(K)降低到48～60，大約3次故障注入后有望恢復(fù)主密鑰。

第 28輪一次故障注入下不同寬度平均可恢復(fù)的密鑰位的統(tǒng)計(jì)見表1第2行，可以看出第28輪攻擊恢復(fù)密鑰位要多于第 29輪；單位故障攻擊效果最好，其次為單字節(jié)、雙字節(jié)故障模型，最后是Nibble和4字節(jié)故障模型。

圖8 第28輪注入不同寬度故障φ(K)統(tǒng)計(jì)

此外，本文還將攻擊擴(kuò)展至第 27輪，此時(shí)隨著已知密鑰位數(shù)量θ的減小，解析器求解速度越來越慢。實(shí)驗(yàn)大致可估計(jì)出當(dāng) θ=40時(shí)，可滿足解數(shù)量大部分情況下仍為 1，這就意味著一次故障注入后至少恢復(fù)40位密鑰，2次故障注入有望恢復(fù)主密鑰。但實(shí)際攻擊中，隨著輪數(shù)的增加，解析器求解代數(shù)方程的復(fù)雜度較大，導(dǎo)致求解時(shí)間較長，2次故障注入本文在 24 h內(nèi)也無法實(shí)現(xiàn)密鑰恢復(fù)。為此，本文增大了故障注入樣本量，5次故障注入可在1 h內(nèi)恢復(fù)主密鑰。

4.4 故障分析結(jié)果比較與解讀

表2給出了本文與已有故障分析結(jié)果的比較。

1)第29輪故障攻擊比較與解讀

在第29輪注入故障，目前有4項(xiàng)研究工作，均基于Nibble故障模型。① Li等[14]的差分故障分析工作，在故障注入到第29輪的查找S盒輸入時(shí)，40～50次故障注入可以恢復(fù)64位后白化密鑰。② Zhao等[16]的基于故障傳播模式分析的差分故障攻擊工作，基于文獻(xiàn)[14]相同故障模型，通過分析故障密文索引和差分特征來識別故障傳播路徑，8次故障注入分別將PRESENT-80/128的密鑰搜索空間降低到214.7。③ Gu等[17]的統(tǒng)計(jì)故障分析，通過構(gòu)建基于最大似然區(qū)分器和歐幾里德距離區(qū)分器，10 000次故障注入可恢復(fù)最后一輪的64位后白化密鑰。④ 吳等[18]的代數(shù)故障分析，通過篩選特定的故障密文，2次故障注入樣本可恢復(fù)64位后白化密鑰。

表2 PRESENT故障分析結(jié)果比較

已有工作受制于密碼分析者對故障信息的利用率和密碼分析認(rèn)知能力，代數(shù)故障分析則將該問題轉(zhuǎn)化為機(jī)器解析器求解問題，結(jié)果更加可靠。本文前面結(jié)果表明，第29輪注入單個(gè)隨機(jī)Nibble故障平均可恢復(fù)9.42個(gè)位（如表1所示），8次故障注入后平均可將φ(K)降低到8.13，結(jié)果要優(yōu)于文獻(xiàn)[14]、文獻(xiàn)[16]，這主要是由于解析器自動求解可充分分析故障注入位置至密文的所有故障信息導(dǎo)致的；同時(shí)，Gu等的統(tǒng)計(jì)故障分析依賴于構(gòu)建的最大似然區(qū)分器和歐幾里德距離區(qū)分器，在數(shù)據(jù)復(fù)雜度上并不是最優(yōu)的，這一點(diǎn)在文獻(xiàn)[17]中也明確提出了；吳等[18]的代數(shù)故障分析依賴于特定的故障模型，攻擊者需要篩選出第29輪注入Nibble故障后密文的16個(gè)Nibble全出錯(cuò)的特定樣本，2次故障注入可恢復(fù) 64位后白化密鑰，而基于相同故障模型，利用本文方法可直接恢復(fù) 80位主密鑰，結(jié)果要優(yōu)于文獻(xiàn)[18]。

2)第28輪故障攻擊比較與解讀

第28輪故障攻擊有2項(xiàng)工作：① 文獻(xiàn)[17]基于Nibble故障模型的統(tǒng)計(jì)故障分析，10 000次故障注入可恢復(fù)最后一輪的64位后白化密鑰；② 文獻(xiàn)[21]基于雙字節(jié)故障模型的差分故障分析，可使用2次和3次故障注入分析將PRESENT-80/128的密鑰搜索空間降低到1.7和222.3。

本文代數(shù)故障分析結(jié)果表明，文獻(xiàn)[17]在第28輪Nibble故障攻擊的數(shù)據(jù)復(fù)雜度仍不是最優(yōu)的，3次故障注入即可將主密鑰剩余熵平均降低到4.05；基于第28輪隨機(jī)雙字節(jié)故障模型，2次故障注入時(shí)執(zhí)行了 100次攻擊實(shí)驗(yàn)得到的 φ(K)統(tǒng)計(jì)如圖 9所示，φ(K)的取值范圍大致為0～40，平均值為12.60。由于文獻(xiàn)[21]中僅給出使用 2次故障注入可將PRESENT-80密鑰搜索空間降低到1.7，并沒有給出攻擊的重復(fù)執(zhí)行次數(shù)和φ(K)的統(tǒng)計(jì)分布特征，其攻擊結(jié)果可信度有待考證。文獻(xiàn)[19]中攻擊對故障注入可能有特定要求，要求每次故障注入都會產(chǎn)生最多的活躍S盒，從而使密鑰恢復(fù)效率較高導(dǎo)致的，本文的攻擊實(shí)驗(yàn)中主密鑰剩余熵也可被降低到零也可說明該特性。

本文4.3節(jié)第28輪注入不同寬度故障攻擊結(jié)果表明，第 28輪雙字節(jié)故障模型并不是最優(yōu)模型，單位故障模型和字節(jié)故障模型的攻擊效果要優(yōu)于雙字節(jié)故障模型，如圖9所示。

圖9 第28輪注入2次隨機(jī)雙字節(jié)故障φ(K)統(tǒng)計(jì)

此外，基于雙字節(jié)故障模型對PRESENT-128進(jìn)行了攻擊，N=3時(shí)，100次攻擊后 φ(K)的統(tǒng)計(jì)分布特征如圖10所示，128位主密鑰熵可平均被降低到44.91，結(jié)果要大于文獻(xiàn)[19]的222.3，本文猜測可能仍是文獻(xiàn)[19]中攻擊每次故障注入都會產(chǎn)生最多的活躍S盒，從而使密鑰恢復(fù)效率較高導(dǎo)致的。

圖10 第28輪注入3次隨機(jī)雙字節(jié)故障φ(K)統(tǒng)計(jì)

5 故障攻擊物理實(shí)驗(yàn)

本節(jié)旨在對PRESENT在智能卡上的軟件實(shí)現(xiàn)開展故障注入物理實(shí)驗(yàn)，研究不同條件下的故障注入成功率，以及現(xiàn)實(shí)中的故障模型，并驗(yàn)證本文故障分析結(jié)果的正確性。

需要說明的是，故障注入的方法有很多種，如電壓毛刺、時(shí)鐘毛刺、電磁輻射、激光照射等。其中，激光故障注入精度最高，可以到單比特，但需對芯片進(jìn)行剖片，成本較高；電壓和時(shí)鐘毛刺注入故障成本較低，基本能夠注入半字節(jié)或者單字節(jié)故障。因此，本文選取時(shí)鐘毛刺作為故障注入手段。

5.1 實(shí)驗(yàn)配置

實(shí)驗(yàn)中，PRESENT實(shí)現(xiàn)在符合ISO/IEC 7816-3協(xié)議的智能卡上，核心為 ATMega163微控制器，工作頻率為3.57 MHz，算法采用速度優(yōu)先的8位軟件實(shí)現(xiàn)。故障注入使用ChipWhisperer設(shè)備來實(shí)現(xiàn)，其中，時(shí)鐘毛刺通過Xilinx Spartan 6 FPGA芯片來生成和控制。故障分析電腦配置為 Intel(R)Core(TM)I7-2640 CPU 2.80 GHz，4 GB內(nèi)存，Win7 64位操作系統(tǒng)，解析器版本為CryptoMiniSAT v2.9.6。

5.2 基于時(shí)鐘毛刺的故障注入

1)時(shí)鐘毛刺生成過程

時(shí)鐘毛刺是時(shí)鐘信號中不規(guī)則的情形，使用時(shí)鐘毛刺可以比較精確地向某一計(jì)算過程引入故障，例如對加密過程中的一個(gè) 8 位寄存器中的數(shù)據(jù)產(chǎn)生隨機(jī)故障的效果，這也是許多故障攻擊假設(shè)中所使用到的模型。圖11是一個(gè)局部寄存器結(jié)構(gòu)，CLK表示寄存器的時(shí)鐘信號，r_in和r_out分別表示寄存器的輸入和輸出數(shù)據(jù)。Data input和Data output則是該電路的輸入輸出，在密碼算法執(zhí)行中常代表加密中間變量。

圖11 局部寄存器電路

在每個(gè)時(shí)鐘上升沿，寄存器進(jìn)行數(shù)據(jù)讀入和輸出，且在每個(gè)時(shí)鐘周期內(nèi)，由于模擬電路設(shè)計(jì)和路徑延時(shí)等原因，寄存器存在一段數(shù)據(jù)不穩(wěn)定的時(shí)間。當(dāng)2個(gè)相鄰上升沿時(shí)間間隔大于該不穩(wěn)定區(qū)間，寄存器輸出數(shù)據(jù)和輸入數(shù)據(jù)相等，電路運(yùn)行正常；否則r_out值尚未穩(wěn)定下來就輸出到下一級電路，寄存器處于不穩(wěn)定區(qū)間，r_out輸出將是隨機(jī)值，導(dǎo)致該部分電路運(yùn)算出錯(cuò)。

實(shí)驗(yàn)中，使用Xilinx Spartan 6系列FPGA芯片來實(shí)現(xiàn)時(shí)鐘毛刺的生成與精確控制，生成的時(shí)鐘信號將作為密碼芯片的時(shí)鐘信號輸入，如圖12所示。輸入時(shí)鐘信號input_clk經(jīng)2次相移后生成2路同頻不同相的時(shí)鐘信號，利用這2路信號，經(jīng)過運(yùn)算可以得到一串連續(xù)的脈沖信號毛刺。將該脈沖信號流與原始輸入時(shí)鐘信號 input_clk進(jìn)行異或即可得到毛刺時(shí)鐘信號 g_clk。上述 2次相移操作均是通過FPGA芯片中的數(shù)字時(shí)鐘管理模塊實(shí)現(xiàn)。

為精確控制故障注入位置，在指定時(shí)機(jī)產(chǎn)生毛刺，攻擊者需要在input_clk和g_clk之間按需進(jìn)行切換。切換是通過調(diào)節(jié)外部輸入信號trigger的位置進(jìn)行控制的，當(dāng)FPGA檢測到trigger信號拉高時(shí)，密碼芯片的時(shí)鐘輸入切換為毛刺時(shí)鐘，而當(dāng)trigger信號為低電平時(shí)，密碼芯片時(shí)鐘輸入恢復(fù)為正常時(shí)鐘。

圖12 時(shí)鐘毛刺生成原理

2)時(shí)鐘毛刺控制參數(shù)

為方便說明，對時(shí)鐘毛刺的參數(shù)定義如下。

T：一個(gè)正常的時(shí)鐘周期，為 280 ns（對應(yīng)頻率 3.57 MHz）。

Tt：trigger信號位置。

To：毛刺相對于trigger的偏置，通過調(diào)整這一參數(shù)可以靈活調(diào)整時(shí)鐘毛刺的注入位置。

Gw：毛刺寬度，指毛刺信號中2個(gè)相鄰上升沿之間的時(shí)間間隔。

3)時(shí)鐘毛刺位置控制

實(shí)驗(yàn)中使用智能卡AUX1腳輸出的trigger信號實(shí)現(xiàn)這一控制，當(dāng)FPGA芯片檢測到trigger信號上升沿時(shí)，F(xiàn)PGA中的計(jì)數(shù)器開始計(jì)數(shù)，計(jì)To個(gè)時(shí)鐘周期后，將輸入給智能卡的時(shí)鐘信號切換為毛刺信號，并在添加一個(gè)毛刺時(shí)鐘后切換為正常時(shí)鐘信號。根據(jù)逆向推理驗(yàn)證，一個(gè)合適的毛刺信號通常只造成一個(gè)8位數(shù)據(jù)寄存器出現(xiàn)數(shù)據(jù)混淆，即產(chǎn)生一個(gè)單字節(jié)故障。To的值需要通過多次嘗試和逆向推理驗(yàn)證來確定，為了能夠在合適時(shí)機(jī)注入故障，本文通常將Tt設(shè)置在距離故障注入點(diǎn)較近的操作前，這樣To的嘗試范圍將可以縮小到50 ns以內(nèi)。

4)時(shí)鐘毛刺寬度控制

為找到一個(gè)合適的毛刺寬度 Gw，對毛刺寬度和故障發(fā)生概率之間的關(guān)系做了進(jìn)一步實(shí)驗(yàn)，下面以 PRESENT第28輪首個(gè)查找 S盒為例進(jìn)行討論。

實(shí)驗(yàn)令毛刺寬度Gw的值從95 ns開始，以0.56 ns為步長逐步減小，對每個(gè) Gw值進(jìn)行重復(fù)故障注入實(shí)驗(yàn)，統(tǒng)計(jì)故障發(fā)生概率。結(jié)果如圖13所示,每點(diǎn)均對應(yīng)270次故障注入的統(tǒng)計(jì)結(jié)果。

圖13 故障頻率與毛刺寬度的關(guān)系

由圖13可知，當(dāng)Gw從95 ns開始減小時(shí)，故障概率呈上升趨勢，在Gw=85 ns時(shí)，故障概率增大，且隨著Gw減小故障概率增加。16 nslt;Gwlt;82 ns對應(yīng)的區(qū)間，由該時(shí)鐘毛刺引導(dǎo)的故障概率接近100%。物理實(shí)驗(yàn)中，本文采用Gw=20 ns進(jìn)行故障注入。下面介紹2種針對PRESENT-80的故障攻擊實(shí)驗(yàn)。

5.3 基于字節(jié)模型的故障攻擊

實(shí)驗(yàn)中設(shè)定Gw=20 ns，To取值為15～20時(shí)，可將故障注入到第28輪查找S盒，使查找S盒輸出產(chǎn)生一個(gè)字節(jié)故障，如圖 14所示。由于攻擊針對的是PRESENT-80軟件實(shí)現(xiàn)，結(jié)合簡單功耗分析可識別出故障針對的字節(jié)索引，在Type B求解模式下執(zhí)行了100次故障攻擊實(shí)驗(yàn)，2次故障注入后80位主密鑰剩余熵平均可被降低到8.07，攻擊平均執(zhí)行時(shí)間約為1 min。

圖14 第28輪注入2次隨機(jī)字節(jié)故障φ(K)統(tǒng)計(jì)

5.4 基于操作跳躍的故障攻擊

在實(shí)驗(yàn)中，本文還發(fā)現(xiàn)，Gw=20 ns、To取值為13、14、24時(shí)，雖然從功耗曲線上可以看到8次查找8進(jìn)8出大S盒的操作，但實(shí)際上該查找S盒操作被跳過去了，相當(dāng)于注入了向8個(gè)S盒注入了差分為正確S盒輸入和正確S盒輸出異或結(jié)果的一個(gè)故障。實(shí)驗(yàn)中，故障注入到第30輪S盒計(jì)算過程中，首先使用1次故障注入樣本在Type B求解模式下執(zhí)行了100次攻擊，PRESENT-80的密鑰剩余熵可被降低到15～20。然后使用1次故障注入樣本在Type A求解模式下執(zhí)行了100次攻擊，得到求解時(shí)間的統(tǒng)計(jì)分布，如圖15所示。

圖15 第30輪注入1次查找S盒跳過故障后求解時(shí)間統(tǒng)計(jì)

由圖15可以看出94%的情況下80位主密鑰可在1個(gè)小時(shí)內(nèi)求解出來。事實(shí)上，如果將求解時(shí)間放寬至6個(gè)小時(shí)，攻擊成功率為100%。

6 結(jié)束語

提出了一種改進(jìn)的基于代數(shù)分析的輕量級分組密碼PRESENT算法代數(shù)故障分析方法，對其抗故障攻擊能力進(jìn)行了評估。結(jié)果表明，提出方法可建立十分緊湊的代數(shù)方程，挖掘所有的故障信息，得到更為準(zhǔn)確的故障注入后的密鑰剩余熵，攻擊所需數(shù)據(jù)復(fù)雜度相比前人工作要低；同時(shí)，首次基于不同故障寬度、不同故障深度對PRESENT抗故障攻擊能力進(jìn)行了評估，并根據(jù)結(jié)果對已有故障攻擊進(jìn)行了解讀和分析；最后對符合ISO/IEC 7816-3協(xié)議的智能卡上的PRESENT軟件實(shí)現(xiàn)進(jìn)行了基于時(shí)鐘毛刺的故障注入實(shí)驗(yàn)，結(jié)果表明，如果第 28輪注入字節(jié)故障，2次故障注入可將主密鑰剩余熵降低到8.07；如果第30輪注入跳過S盒計(jì)算故障，1次故障注入即可在94%的情況下、1個(gè)小時(shí)內(nèi)恢復(fù)80位主密鑰。

未來的工作主要有以下3個(gè)方面：1)結(jié)合硬件木馬實(shí)現(xiàn)單位故障注入[23]，或?qū)RESENT的輪計(jì)數(shù)器打入故障[24]，有望在1次故障注入下恢復(fù)主密鑰；2)開展基于故障不完美分布特征的故障攻擊研究[25]，在唯錯(cuò)誤密文場景下實(shí)現(xiàn)密鑰恢復(fù)；3)開展PRESENT故障靈敏度分析研究[26,27]，攻破帶有傳統(tǒng)故障攻擊防護(hù)的密碼實(shí)現(xiàn)。

[1]BOGDANOV A,KNUDSEN L R,LEANDER G,et al. PRESENT: an ul-tra-lightweight block cipher[C]//CHES 2007. Vienna,Austria,c2007: 450-466.

[2]BOGDANOV A,LEANDER G,PAARC,et al. Hash functions and RFID tags: mind the gap[C]//CHES 2008. Washington,DC,USA,c2008: 283-299.

[3]WANG M. Differential cryptanalysis of reduced-round PRESENT[C]//AFRICACRYPT 2008. Casablanca,Morocco,c2008: 40-49.

[4]BLONDEAU C,NYBERG K. New links between differential and linear cryptanalysis[C]//EUROCRYPT 2013. Athens,Greece,c2013:388-404.

[5]BLONDEAU C,NYBERG K. Links between truncated differential and multidimensional linear properties of block ciphers and underlying attack complexities[C]//EUROCRYPT 2014. Athens,Greece,c2014:165-182.

[6]NAKAHARA J,SEPEHRDAD P,ZHANG B,et al. Linear (hull)and algebraic cryptanalysis of the block cipher PRESENT[C]//CANS 2009.Ishikawa,Japan,c2009: 58-75.

[7]CHO J Y. Linear cryptanalysis of reduced-round PRESENT[C]//CT-RSA 2010. San Francisco,CA,USA,c2010: 302-317.

[8]ALBRECHT M,CID C. Algebraic techniques in differential cryptanalysis[C]//FSE 2009. Leuven,Belgium,c2009: 193-208.

[9]BLONDEAU C,PEYRIN T,WANG L. Known-key distinguisher on full PRESENT [EB/OL]. http://eprint.iacr.org/2015/575.pdf,2015.

[10]ZHANG J,GU D W,GUO Z,et al. Differential power cryptanalysis attacks against PRESENT implementation[C]//ICACTE 2010. Chengdu,China,c2010: 661-665.

[11]李浪,李仁發(fā),李肯立,等. 輕量級 PRESENT加密算法功耗攻擊研究[J]. 計(jì)算機(jī)應(yīng)用研究,2014,31(3),843-845.LI L,LI R F,LI K L,et al. Differential power analysis attacks on PRESENT[J]. Application Research of Computers,2014,31(3),843-845.

[12]RENAULD M,STANDAERT F X. Algebraic side-channel attacks[C]//In-scrypt 2009. Beijing,China,c2010: 393-410.

[13]ZHAO X J,GUO S Z,ZHANG F,et al. Efficient Hamming weight-based side-channel cube attacks on PRESENT[J]. The Journal of Systems and Software,2013,86: 728-743.

[14]LI J,GU D W. Differential fault analysis on PRESENT[C]//CHNA-CRYPT 2009. Guang Zhou,China,c2009: 3-13.

[15]WANG G,WANG S. Differential fault analysis on present key schedule[C]//CIS 2010. Nanning,China,c2010: 362-366.

[16]ZHAO X J,GUO S Z,ZHANG F,et al. Fault-propagate pattern based DFA on PRESENT and PRINT cipher[J]. Wuhan University Journal of Natural Sciences,2012,17(6): 485-493.

[17]GU D W,LI J R,LI S,et al. Differential fault analysis on light-weight block ciphers with statistical cryptanalysis techniques[C]//FDTC 2012.Leuven,Belgium,c2012: 27-33.

[18]吳克輝,趙新杰,王韜,等. PRESENT密碼代數(shù)故障攻擊[J]. 通信學(xué)報(bào),2012,33(8): 85-92.WU K H,ZHAO X J,WANG T. Algebraic fault attack on PRESENT[J]. Journal on Communications,2012,33(8): 85-92.

[19]JEONG K,LEE Y,SUNG J,et al. Improved differential fault analysis on PRESENT-80/128[J]. International Journal of Computer Mathematics,2013,90(12): 2553-2563.

[20]KLOSE,D. PRESENT implementation[EB/OL]. http://www. lightweightcrypto. org/implementations.php,2011.

[21]郭世澤,王韜,趙新杰. 密碼旁路分析原理與方法[M]. 北京：科學(xué)出版社,2014.GUO S Z,WANG T,ZHAO X J. Principles and methodologies of side-channel analysis in cryptography[M]. Science Press,Beijing,China,2014.

[22]ZHAO X J,GUO S Z,ZHANG F,et al. Improving and evaluating differen-tial fault analysis on LED with algebraic techniques[C]//FDTC 2013. Santa Barbara,CA,USA,c2013: 41-51.

[23]KUMAR R,JOVANOVIC P,BURLESON W P,et al. Parametric trojans for fault-injection attacks on cryptographic hardware[C]//FDTC 2014. Busan,Korea,c2014: 18-28.

[24]DEHBAOUI A,MIRBAHA A P,MORO N,et al. Electromagnetic glitch on the aes round counter[C]//COSADE 2013. Paris,France,c2013: 17-31.

[25]LI Y,HAYASHI Y,MATSUBARA A,et al. Yet another fault-based leakage in non-uniform faulty ciphertexts[C]//FPS 2013. La Rochelle,France,c2013: 272-287.

[26]LI Y,SAKIYAMA K,GOMISAWA S,et al. Fault sensitivity analysis[C]//CHES 2010. Santa Barbara,California,USA,c2010: 320-334.

[27]MORADI A,MISCHKE O,PAAR C,et al. On the power of fault sensitivity analysis and collision side-channel attacks in a combined setting[C]//CHES 2011. Nara,Japan,c2011: 292-311.

Improvement and evaluation for algebraic fault attacks on PRESENT

HUANG Jing1,ZHAO Xin-jie2,ZHANG Fan3,4,GUO Shi-ze2,ZHOU Ping5,CHEN Hao5,YANG Jian3

(1. Third Department of No.61541 Unit,Beijing 100083,China;2. The Institute of North Electronic Equipment,Beijing 100191,China;3. College of Information Science amp; Electrical Engineering,Zhejiang University,Hangzhou 310027,China;4. Science and Technology on Communication Security Laboratory,Chengdu 610041,China;5. Department of Information Engineering,Ordnance Engineering College,Shijiazhuang 050003,China)

An enhanced algebraic fault analysis on PRESENT was proposed. Algebraic cryptanalysis was introduced to build the algebraic equations for both the target cipher and faults. The equation set of PRESENT was built reversely in order to accelerate the solving speed. An algorithm of estimating the reduced key entropy for given amount of fault injections was proposed,which can evaluate the resistance of PRESENT against fault attacks under different fault models. Finally,extensive glitch-based fault attacks were conducted on an 8-bit smart card PRESENT implemented on a smart card.The best results show that only one fault injection was required for the key recovery,this is the best result of fault attacks on PRESENT in terms of the data complexity.

algebraic cryptanalysis,lightweight block cipher,fault attack,satisfiability solving,clock glitch

s:The National Basic Research Program of China (973 Program)(No.2013CB338004),The National Natural Science Foundation of China (No.61173191,No.61271124,No.61272491,No.61309021,No.61472357,No.61571063),The Fundamental Research Funds for the Central Universities (No.2015QNA5005),The Science and Technology on Communication Security Laboratory (No.9140C110602150C11053)

TP393

A

2015-07-15；

2016-01-13

國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃（“973”計(jì)劃）基金資助項(xiàng)目（No.2013CB338004）；國家自然科學(xué)基金資助項(xiàng)目（No.61173191,No.61271124,No.61272491,No.61309021,No.61472357,No.61571063）；中央高?；究蒲袑ｍ?xiàng)基金資助項(xiàng)目（No.2015QNA5005）；保密通信重點(diǎn)實(shí)驗(yàn)室基金資助項(xiàng)目（No.9140C110602150C11053）

10.11959/j.issn.1000-436x.2016165

黃靜（1983-），女，四川南充人，61541部隊(duì)助理工程師，主要研究方向?yàn)樾l(wèi)星網(wǎng)絡(luò)與信息安全。

趙新杰（1986-），男，河南開封人，博士，北方電子設(shè)備研究所工程師，主要研究方向?yàn)榫W(wǎng)絡(luò)空間安全與密碼學(xué)。

張帆（1978-），男，浙江杭州人，博士，浙江大學(xué)講師，主要研究方向?yàn)槊艽a旁路分析和故障分析。

郭世澤（1969-），男，河北石家莊人，北京電子設(shè)備研究所研究員，主要研究方向?yàn)榫W(wǎng)絡(luò)空間安全與密碼學(xué)。

周平（1988-），男，安徽無為人，軍械工程學(xué)院博士生，主要研究方向?yàn)槊艽a算法旁路分析與故障分析等。

陳浩（1987-），男，湖北武漢人，軍械工程學(xué)院博士生，主要研究方向?yàn)槊艽a算法旁路分析與故障分析等。

楊建（1991-），男，湖北武漢人，主要研究方向?yàn)榉纸M密碼代數(shù)故障分析。