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

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

PRESENT代數故障攻擊的改進與評估

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

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

需要說明的是，本文方法可用于指導攻擊者根據故障注入條件選取最佳故障模型、新型算法設計者評估設計算法抗故障攻擊能力、已有算法實現者對一定輪數內的算法進行故障攻擊防護。

2 PRESENT算法與故障模型

2.1 PRESENT算法設計

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

1)加密過程

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

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

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

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

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

2)密鑰擴展算法

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

其中，round_counter為當前的加密輪數。

2.2 PRESENT算法軟件實現

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

2.3 故障模型

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

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

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

λ：X的長度。

w：故障寬度。

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

t：故障單元索引。

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

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

3 改進的PRESENT代數故障分析方法

3.1 攻擊框架

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

1)故障注入

圖1 代數故障攻擊框架

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

2)方程構建

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

3)方程求解

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

3.2 PRESENT代數方程構建

1)代數故障分析密碼整體結構構建策略

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

圖2 代數故障分析密碼整體結構構建策略

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

算法 1PRESENT代數故障分析方程組構建算法

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

輸出代數故障分析所需方程

Step1構建密鑰擴展方程

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

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

GenerateKS_R(i);}

Else { //逆向構建倒數31?r輪密鑰擴展方程

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

GenerateKS_R(i); }

Step2逆向構建倒數31?r輪正確和錯誤加密方程、故障方程

RandomPlaintextGenerating();//產生攻擊所需的隨機加密明文

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

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

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

GenerateES_R(j);

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

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

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

GenerateES_R(j);

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

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

Step3逆向構建驗證故障方程

VerifyPlaintextGenerating(Pv)//生成隨機驗證明文

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

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

GenerateES_R(i);

Generate_Input_ES(Pv,Cv)

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

3)PRESENT密鑰擴展方程構建

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

① 異或輪常量函數

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

② 逆S盒函數

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

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

③ 右移61位函數

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

4)PRESENT加密方程構建

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

① 逆置換函數

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

③ 逆S盒代換

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

③ 逆輪密鑰加

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

3.3 故障代數方程構建

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

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

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

1)故障索引t已知

假設t值已知，則Z可表示為

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

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

2)故障索引t未知

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

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

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

3.4 主密鑰搜索空間評估

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

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

輸入L,N,θ,τ

輸出φ(K)

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

4 PRESENT抗故障攻擊能力評估

本節(jié)的故障注入是通過仿真實現的，故障攻擊物理實驗細節(jié)可參考第5節(jié)。

4.1 第29輪隨機Nibble故障攻擊

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

圖3 第29輪注入單次Nibble故障后φ(K)統計

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

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

圖4 第29輪注入8次Nibble故障后φ(K)統計

4.2 第28輪隨機Nibble故障攻擊

1)第28輪注入Nibble故障

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

圖5 第28輪注入1次Nibble故障后φ(K)統計

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

N=3時，100次故障攻擊后φ(K)統計如圖6所示。φ(K)可被降低到12以內，平均被降低到4.05。

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

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

圖6 第28輪注入3次Nibble故障后φ(K)統計

圖7 第29輪注入不同寬度故障φ(K)統計

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

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

表1 N=1時攻擊平均恢復密鑰位

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

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

圖8 第28輪注入不同寬度故障φ(K)統計

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

4.4 故障分析結果比較與解讀

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

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

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

表2 PRESENT故障分析結果比較

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

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

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

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

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

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

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

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

5 故障攻擊物理實驗

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

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

5.1 實驗配置

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

5.2 基于時鐘毛刺的故障注入

1)時鐘毛刺生成過程

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

圖11 局部寄存器電路

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

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

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

圖12 時鐘毛刺生成原理

2)時鐘毛刺控制參數

為方便說明，對時鐘毛刺的參數定義如下。

T：一個正常的時鐘周期，為 280 ns（對應頻率 3.57 MHz）。

Tt：trigger信號位置。

To：毛刺相對于trigger的偏置，通過調整這一參數可以靈活調整時鐘毛刺的注入位置。

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

3)時鐘毛刺位置控制

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

4)時鐘毛刺寬度控制

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

實驗令毛刺寬度Gw的值從95 ns開始，以0.56 ns為步長逐步減小，對每個 Gw值進行重復故障注入實驗，統計故障發(fā)生概率。結果如圖13所示,每點均對應270次故障注入的統計結果。

圖13 故障頻率與毛刺寬度的關系

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

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

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

圖14 第28輪注入2次隨機字節(jié)故障φ(K)統計

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

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

圖15 第30輪注入1次查找S盒跳過故障后求解時間統計

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

6 結束語

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

未來的工作主要有以下3個方面：1)結合硬件木馬實現單位故障注入[23]，或對PRESENT的輪計數器打入故障[24]，有望在1次故障注入下恢復主密鑰；2)開展基于故障不完美分布特征的故障攻擊研究[25]，在唯錯誤密文場景下實現密鑰恢復；3)開展PRESENT故障靈敏度分析研究[26,27]，攻破帶有傳統故障攻擊防護的密碼實現。

[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]. 計算機應用研究,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密碼代數故障攻擊[J]. 通信學報,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]. 北京：科學出版社,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

國家重點基礎研究發(fā)展計劃（“973”計劃）基金資助項目（No.2013CB338004）；國家自然科學基金資助項目（No.61173191,No.61271124,No.61272491,No.61309021,No.61472357,No.61571063）；中央高校基本科研專項基金資助項目（No.2015QNA5005）；保密通信重點實驗室基金資助項目（No.9140C110602150C11053）

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

黃靜（1983-），女，四川南充人，61541部隊助理工程師，主要研究方向為衛(wèi)星網絡與信息安全。

趙新杰（1986-），男，河南開封人，博士，北方電子設備研究所工程師，主要研究方向為網絡空間安全與密碼學。

張帆（1978-），男，浙江杭州人，博士，浙江大學講師，主要研究方向為密碼旁路分析和故障分析。

郭世澤（1969-），男，河北石家莊人，北京電子設備研究所研究員，主要研究方向為網絡空間安全與密碼學。

周平（1988-），男，安徽無為人，軍械工程學院博士生，主要研究方向為密碼算法旁路分析與故障分析等。

陳浩（1987-），男，湖北武漢人，軍械工程學院博士生，主要研究方向為密碼算法旁路分析與故障分析等。

楊建（1991-），男，湖北武漢人，主要研究方向為分組密碼代數故障分析。