針對輕量級分組密碼算法PRESENT的隨機差分故障攻擊

黃湘蜀, 王 敏, 杜之波, 吳 震, 王 燚

(成都信息工程大學網絡空間安全學院,四川 成都 610225)

0 引言

輕量級分組密碼算法憑借其結構簡單、功耗低、實現面積小、適應性廣泛等特點,已經成為物聯網應用的關鍵組成部分。目前在物聯網應用中,已經有許多輕量級分組密碼算法,如 MIBS[1]、TWINE[2]、HIGHT[3]、GIFT[4]。這些算法都具有加解密一致、結構簡單、易于實現等特點。而 PRESENT算法是 A.Bogdanov等[5]提出的一種輕量級分組密碼算法,其具有輕量級分組密碼普遍特點,同樣適合在物聯網相關應用中使用。當前針對PRESENT算法的分析方法主要有積分攻擊[5]、差分代數攻擊[6]、多重差分鏈攻擊[7]以及差分故障攻擊[8-9]等方法,文獻[5]通過分析PRESENT算法一系列中間狀態的和的概率進行攻擊,攻擊復雜度為220。文獻[6]將差分攻擊和代數攻擊相結合,建立并且簡化代數方程組,攻擊復雜度為264.58。文獻[7]利用多重差分鏈對PRESENT算法進行攻擊,攻擊復雜度為281。差分故障攻擊[10]作為旁路攻擊[11]的一種,最早在1996年由Boneh提出,是一種將差分分析[12]和故障攻擊[13]相結合的技術。攻擊原理是在加密過程中的某一時間段進行故障注入,制造數據差分,利用輸出的故障密文和故障動作,結合差分方程得到輪密鑰的可能值。該方法已經應用于 CLEFIA[14]、SM4[15]等分組密碼上,對分組密碼算法構成了嚴重的威脅。文獻[8]采用的是面向字節的隨機故障注入模型,在PRESENT算法的加密過程中引入單字節的故障,通過差分故障特性識別需要的故障密文,并由識別得到的故障密文恢復輪密鑰。文獻[9]建立單字節的隨機故障模型,利用PRESENT算法P置換層的故障傳播特性,通過單字節擴展的方式恢復輪子密鑰,攻擊復雜度為231。現有的兩種方法雖然都在理論上進行了證實,但在實際操作中攻擊者難以控制故障注入的位置以及產生故障的字節數,所以當前針對PRESENT算法的故障注入攻擊仍然有一定的局限性。

針對上述問題,為提高故障攻擊方法在實際攻擊中的可行性以及效率,降低故障注入的難度,對現有的單字節差分故障模型進行改進,利用固定的故障傳播路徑,建立多字節的故障注入模型。通過電壓注入的方式在第30、29輪任意位置進行隨機故障注入,并由輸出差分與S盒輸入值之間的關系,篩選出正確的S盒輸入。設計的故障模型,可將攻擊復雜度降低41.9%,攻擊平均時間由20000 ms降低到1000 ms。

1 PRESENT算法

1.1 符號說明

K:表示密鑰;

ki:表示當前輪密鑰的第i比特位;

p(i):第i比特位的置換運算;

S[]:表示S替換;

Si:表示第i輪S盒輸入;

Pi:表示第i輪P盒輸入;

Ci:表示第i輪P盒輸出;

Nci:表示經過第i輪P置換后故障變化到的比特位置;

Nsi:表示第i輪故障所在的S盒;

f:表示輸入差分;

f＇:表示輸出差分;

Sin:S盒的輸入值;

F(f＇):表示輸出差分為f＇時,輸入差分的候選集合。

1.2 PRESENT算法迭代過程

PRESENT算法的明文和密文長度都為64比特,主密鑰長度為80比特或者128比特,文中僅討論80比特的情況。該算法共有31輪迭代過程,每一輪的子密鑰長度為64比特,如圖1所示,在第31輪結束后,再進行一次輪密鑰加的白化操作。

圖1 PRESENT算法加密流程

算法主要是由 “輪密鑰加”“S盒置換”“P盒置換”3部分組成。“輪密鑰加”為按位進行異或操作。“S盒置換”為按照S盒置換表進行置換,每個S盒輸入和輸出都是4比特(為方便闡述,文中將4bits視作一個字節),由16個S盒組成,一共64比特,S盒置換如表1所示。

表1 S盒置換表

“P盒置換”相當于移位操作,每比特位置按式(1)進行置換,其中i為比特位。

1.3 PRESENT密鑰擴展

以80比特的主密鑰為例來闡述PRESENT算法的密鑰擴展方法。主密鑰首先存儲在存儲器中,表示為K=k79k78…k0,在進行輪密鑰加操作時按位取當前密鑰寄存器的高64比特,表示為K=k79k78…k17k16。提取完子密鑰后按如下方式進行擴展。首先,將80比特密鑰循環左移61位,之后依次從左到右取4比特進行S盒置換,最后將k19k18k17k16k15與輪計數器r做異或運算,并且將異或后產生的結果取代原來的5比特數據,如式(2)所示。

2 PRESENT分組密碼故障分析

2.1 PRESENT算法故障傳播路徑

PRESENT算法屬于輕量級分組密碼算法的一種,算法中的S盒和P置換是重要的組成成分,在故障攻擊中攻擊者可以根據S盒的非線性將S盒的輸入縮小范圍,通過對P置換的分析得到故障的傳播路徑。圖2是最后兩輪加密過程。

圖2 PRESENT算法最后兩輪加密過程

圖2中,首先以單字節故障進行說明,多字節故障傳播類似。假設在S30第15個字節處產生了單字節的故障,由于一個字節表示4bits,即最多4比特位的數據產生了變化。此時經過P置換后,該故障數據會傳播到S31的4個不同的S盒上,這4個S盒都會受到故障數據的影響。若再經過一次P置換運算,那么所有字節都會受到故障數據的影響。表2是故障傳播路徑表,其中i(0≤i≤15)表示在第30輪注入單字節故障的位置。

表2 故障傳播路徑表

由表2可知,當在第30輪產生一個單字節故障時,至多會影響第31輪的4個S盒的輸入,因此影響至多16比特位的S盒輸出。同理可得,當產生故障字節數為i(0≤i≤15)個時,則會影響下一輪16個S盒的輸入,并且影響64比特位的S盒輸出。利用上述故障傳播路徑,將有利于進行差分故障分析。

2.2 PRESENT算法S盒差分特征

在差分故障攻擊中,最為核心的步驟就是根據差分來計算每個S盒可能的輸入,為

攻擊者可以通過已知輸出差分f構建S盒輸入差分查詢表,如表3所示。通過差分查詢表來尋找可能的輸出差分f,最后通過式(3)求得S盒的輸入值Sin。相比于以往的通過窮舉的方式尋找Sin,利用查表方式能夠快速地找到f并且求得Sin,減少針對S盒輸入值的窮舉量,縮短攻擊時間。

表3 差分S盒特征

表3僅僅給出了每個S盒輸出差分只有1位為1的情況,然而在實際情況中每個S盒的輸出差分可能有4個位為1,需要根據實際的輸出差分來找對應的輸入差分。

3 PRESENT算法的隨機差分故障攻擊

利用PRESENT算法的故障傳播特性,可設計如下方案對其實施隨機差分故障攻擊,具體過程如下:

步驟一 首先隨機選取一組明文,將明文在密鑰K的情況下進行加密,獲取對應的密文C,并且利用示波器采集加密過程中產生的能量信號并轉化為能量曲線。將采集到的曲線進行預處理,并把預處理后的曲線結合PRESENT算法的流程進行分析,進而確定算法的第30輪和第29輪的運行時間段,方便后續的故障注入。

步驟二 在智能卡運行期間進行電壓故障注入獲得錯誤密文。

(1)根據步驟一采集到的曲線,確定第30輪、29輪的位置,并且在這兩輪進行故障注入,進而得到錯誤密文C*。

(2)將正確密文和故障密文進行異或得到差分密文diffC。

(3)由故障傳播路徑,可以根據得到的差分密文diffC,通過P盒的逆運算P-1反推出第31輪的16個S盒的輸出差分diffP31。

(4)若攻擊者對每一個滿足條件的輸入差分都進行分析,會得到S盒輸入集合M{Sin1,Sin2…Sinn},由于S盒的輸入為4位,因此M集合的最大下標為16。表4是輸出差分固定的情況下,輸入差分和S盒輸入之間的關系表。

表4 PRESENT算法S盒輸入特征表

由表4可知,當輸出差分固定時,如果對單個S盒進行分析,那么集合M中會有16個不同的值,顯然這樣的攻擊是無效的。針對這一問題,提出如下的解決方法:

①由表2可知,若將連續相鄰的4個S盒分為1組,則1組S盒經過1輪P置換后會影響相同的4個S盒,因此可以采用并行處理的方式同時處理4個S盒,減少攻擊所需要的時間。

②由上述條件,攻擊者對1組即4個S盒同時進行差分分析,根據4個S盒已知的輸出差分(若其中的某些S盒的輸出差分為0則可忽略這些S盒),找到候選輸入差分交集G。假設有兩類輸出差分分別為1、4,則對應的輸入差分候選集為F(1)={3,5,7,B,D,F},F(4)={3,5,9,B,D,F},交集G={3,B,D,F}。結合表4、表5給出了F(1)與其他輸入差分候選集F(n)(2≤n≤15)交集的情況,通過尋找輸入差分的交集能夠減少Sin的搜索范圍。

表5 局部S盒輸入特征表

③由②可知,已經對S盒的輸入進行了篩選,若篩選出來的輸入差分包含了正確的輸入差分值,那么一定可以得到S盒的正確輸入,式(6)為S盒正確輸入的概率計算公式。

表6 S盒正確輸入概率表 單位:%

表6中Species代表4個S盒中正確輸入差分的種類,Correct代表當前S盒正確輸入出現的概率。Fault代表出現錯誤輸入的概率,No-Key代表不會得到輸入的概率,由表6可知若4個S盒中只有一類正確的輸入差分,那么正確的輸入差分一定包含在G中,則一定會出現正確輸入。若有兩類正確的輸入差分,則會有40.1%的概率出現正確的輸入。此時雖然得到錯誤輸入的概率為56.1%,但是在這56.1%概率中包含了15種錯誤的輸入,因此每種錯誤輸入的概率為3.74%,遠低于正確輸入的概率。同理三類正確輸入差分的正確輸入概率為10.8%,四類為1.5%。

(5)根據上述內容,對G集合中的候選輸入差分diffsin進行遍歷,由式(7)可以找出所有候選的S盒輸入值 Sin。

(6)由計算得到的Sin,根據式(8)可以恢復出該S盒對應的4比特位密鑰候選值。

(7)候選輸入篩選。首先設置一個長度為16的數組key[16][16],并且初值都0,key[16][16]={{0,0…0},{0,0…0}…{0,0…0}},數組key中的行代表第0～16個S盒,列下標表示16個可能的輸入值。將式(8)計算出的候選輸入,按照列下標匹配的方式存入到數組key中,并且對應位的數值加1。通過分析多條故障數據,找到二維數組每一行的最大值,最大值的下標就是當前S盒的正確輸入,從而恢復出第31輪的64位輪子密鑰。

步驟三 根據上述恢復出的第31輪的輪子密鑰,逆推可以得到第30輪的密文,重復(1)至(7)的步驟恢復出第30輪的輪子密鑰。利用,通過密鑰編排算法恢復出主密鑰K。

步驟四 主密鑰密鑰恢復。每一輪的主密鑰長度為80bits,記為k=[k79k78…k0],輪計數器r用二進制表示(r4r3r2r1r0)2,由密鑰擴展算法可知,K30經過左移61比特位后,此時第31輪80比特的最后16比特位為k＇=k34k33k32…k20k19,而該16比特位在K30的前64比特位中,由攻擊出的第30輪64比特密鑰K30,可以獲得k＇的具體值。經分析經過密鑰擴展算法k＇只有一位會產生變化即k34=k348r0。根據已經恢復k31的64比特密鑰以及上述推出的k＇,可以推出最后一輪的80比特主密鑰

式(10)中第一步為當前主密鑰的k19k18k17k16k15與輪計數器進行異或,之后進行S盒的逆運算,最后右移61比特從而得到第30輪的主密鑰。同理,可以推出初始的80比特主密鑰。通過上述對密鑰擴展算法的缺陷分析,攻擊者不用通過窮舉最后16 bits的方式也可恢復主密鑰,提高了主密鑰恢復效率。

4 攻擊實驗與分析

使用智能卡、VC Glitcher、Inspector、示波器等設備進行正確密文和故障密文的采集。選擇初始明文為0xc 0x7 0x3 0x9 0xd 0x7 0xe 0xa 0xf 0xa 0xe 0x4 0xe 0xd 0xa 0x3,初始密鑰為0xf 0xf 0xf 0xf 0xf 0xf 0xf 0xf 0xf 0xf 0xf 0xf 0xf 0xf 0xf 0xf 0xf 0xf 0xf 0xf,整個實驗過程包括信息采集、故障注入、故障分析、復雜度分析以及實驗結果分析。

4.1 數據采集

首先采集智能卡在運行時的能量曲線并且記錄正確的密文,圖3為示波器上采集到的能量曲線。

圖3 能量曲線

圖4為采集到的明文和密文信息,C7 39 D7 EA FA E4 ED A3為采集到明文信息,35 75 04 0B 4F D5 85 BC為采集到的正確密文信息,90 00代表標識位表示智能卡返回數據成功,其余數據代表對智能卡下發的指令。

圖4 正確密文信息

4.2 故障注入

對采集到的能量曲線首先進行信號處理,確定PRESENT算法第29輪、第30輪的時間。由圖3可知5000～5400 μs為第29輪、第30輪的時間。利用 VC Glitcher在PRESENT算法的第29輪、第30輪分別進行隨機故障注入,故障注入的具體位置和故障注入的字節數未知。圖5是故障注入后返回的部分故障密文,其中黑框部分為產生的故障密文。

圖5 故障密文

4.3 故障分析

根據攻擊方法,首先對第30輪的故障密文進行差分分析,恢復第31輪的16個S盒的密鑰,圖6是實驗結果圖。

圖6 第30輪故障密文分析

同理根據第29輪的故障密文恢復出第30輪的輪子密鑰,并且根據兩輪輪子密鑰恢復初始的80 bits主密鑰,圖7是實驗結果圖。

圖7 第29輪故障密文分析

通過式(10)可恢復初始80bits主密鑰為:15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15。

由上述實驗結果可知,輪密鑰攻擊平均時間為1000 ms,恢復出的主密鑰為15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15。與初始設定的主密鑰一致,達到了攻擊的目的,證明文中提出攻擊方案的有效性。

4.4 復雜度分析

根據故障傳播路徑對攻擊方法進行重新設計,相比于傳統的分析方法或者已有針對PRESENT算法的差分故障攻擊方法具有明顯的優勢。傳統的密鑰攻擊方法大多數采用的是窮舉密鑰,由于PRESENT算法的輪子密鑰長度為64bits,若采用直接窮舉密鑰搜索,則輪密鑰的攻擊復雜度為264。而文獻[9]則是采用依次擴展的方法,根據每一輪的中間匹配狀態來進一步的降低搜索空間,攻擊復雜度為231。根據PRESENT算法的故障傳播路徑,采用多字節故障模型的方法,通過輸入差分的交集來尋找正確密鑰。復雜度C如下:

其中sboxnum表示S盒的數量,值為16。diffnum代表每個S盒輸出差分一定的情況下的輸入差分數量,經計算分析diffnum的取值范圍為4≤diffnum≤8。keynum表示每個S盒輸入差分對應的候選輸入的個數,候選輸入的個數范圍為0≤keynum≤4。faultnum代表恢復該輪輪子密鑰所需要的故障密文數,經過實驗分析,平均300條故障密文就可以恢復當前的輪子密鑰。綜上所述,恢復出輪子密鑰的復雜度C=218。

5 結束語

利用優化后的差分故障攻擊方法,對寫有PRESENT算法的智能卡進行隨機故障注入,并且對得到的故障數據進行分析,實驗結果證明方法具有有效性。與現有的針對PRESENT算法的單字節故障注入相比,本文提出的方法沒有限定故障注入的位置和故障注入的數量,打破了以往研究對故障誘導的限制,降低了對故障注入設備的要求,為針對SPN結構分組密碼算法的故障攻擊提供了新思路。并且輪密鑰的攻擊復雜度由231降低到218,攻擊時間降低了19000 ms,效率也得到了極大的提高。