陳 浩，王 韜，劉會(huì)英，周 平，馮曉云（.軍械工程學(xué)院 信息工程系，河北 石家莊050003；.南京理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京0094）

0 引 言

模加運(yùn)算［1］廣泛地應(yīng)用在流密碼，輕型分組密碼，哈希函數(shù)等設(shè)計(jì)中，對(duì)采用模加運(yùn)算的密碼算法安全性分析近年來已成為密碼分析學(xué)的研究熱點(diǎn)。Helix作為一種典型模加運(yùn)算結(jié)構(gòu)的流密碼，采用輪函數(shù)迭代，交叉使用逐位異或，模232加和循環(huán)移位3種運(yùn)算來提供復(fù)雜的非線性，增強(qiáng)算法安全性，對(duì)其安全性的研究對(duì)其他具有模加運(yùn)算結(jié)構(gòu)的密碼有很大的借鑒意義。

代數(shù)故障攻擊［2］由Courtois在eSmart 2010會(huì)議上首次提出，它用代數(shù)分析方法建立密碼算法代數(shù)方程組，利用注入故障獲取錯(cuò)誤密文，將故障差分轉(zhuǎn)化為等效方程組，然后通過求解方程組進(jìn)行密鑰恢復(fù)。目前代數(shù)故障攻擊處于起步階段，相關(guān)研究較少，主要有Mohamed等于2011年對(duì)流密碼Trivium 提出的代數(shù)故障攻擊［3］，攻擊僅需2個(gè)故障和420個(gè)密鑰流比特即可恢復(fù)Trivium 全部的內(nèi)部狀態(tài)，顯著的提高了故障信息的利用率。由于該方法僅針對(duì)Trivium 算法結(jié)構(gòu)，對(duì)具有模加運(yùn)算結(jié)構(gòu)的流密碼并不適用。

本文對(duì)Helix首次提出一種代數(shù)故障攻擊。針對(duì)算法中模232加運(yùn)算，提出一種通用的代數(shù)故障攻擊模型，并通過選擇明文和故障注入，建立Helix在該模型下的代數(shù)方程組，使用CryptoMiniSAT 解析器求解方程組恢復(fù)密鑰信息。實(shí)驗(yàn)結(jié)果表明，580次故障注入即可恢復(fù)Helix工作密鑰除最高位外的248比特信息，剩余8比特密鑰信息可以通過窮舉得到。

1 Helix算法簡介

Helix面向軟件實(shí)現(xiàn)，支持可變的密鑰長度 （最長256比特），使用長度為128 比特初始向量，以字為單位進(jìn)行運(yùn)算。

1.1 符號(hào)說明

為論述方便起見，基本符號(hào)見表1。

表1 基本符號(hào)及說明

1.2 Helix輪函數(shù)

Helix算法輪函數(shù)如圖1所示，由圖1可知輪函數(shù)交叉使用異或，模232加，循環(huán)移位運(yùn)算操作。

圖1 Helix輪函數(shù)結(jié)構(gòu)

1.3 Helix密鑰擴(kuò)展

Helix使用工作密鑰（K0，…，K7），初始向量（N0，…，N3），輪編號(hào)i和用戶密鑰U 的長度（U） （0≤（U）≤32）來進(jìn)行密鑰擴(kuò)展。整個(gè)密鑰擴(kuò)展分為兩步，第一步將用戶密鑰U 轉(zhuǎn)換為工作密鑰；第二步將工作密鑰轉(zhuǎn)換成輪子密鑰。

其中，i＝7，…，0。在第二步中，首先將初始向量擴(kuò)展成8個(gè)字Nk：＝（k mod 4）－Nk－4（mod 232），其中K＝4，…，7，則輪子密鑰由式（2）－式（4）產(chǎn)生

1.4 算法初始化

Helix在加密第一個(gè)明文P0前，從i＝－8開始運(yùn)行8輪輪函數(shù)，運(yùn)行到i＝－1時(shí)，完成初始化。初始值的設(shè)定是依照式 （5）－式 （7）來設(shè)定的

1.5 算法加密過程

2 模2n 加代數(shù)故障攻擊模型

分析流密碼Helix算法結(jié)構(gòu)可知，Helix的安全性主要依賴模加運(yùn)算，因此對(duì)Helix的代數(shù)故障攻擊實(shí)質(zhì)就是對(duì)模加運(yùn)算的代數(shù)故障攻擊。本節(jié)對(duì)模加運(yùn)算提出了一種通用的代數(shù)故障攻擊模型，并給出了該模型下代數(shù)方程組的構(gòu)建。

2.1 代數(shù)故障攻擊一般過程

如圖2所示，對(duì)流密碼代數(shù)故障攻擊主要可分為3步：第一步，利用流密碼加密算法結(jié)構(gòu)建立關(guān)于內(nèi)部狀態(tài)或者密鑰的代數(shù)方程組；第二步，向流密碼加密算法引入隨機(jī)故障使中間狀態(tài)產(chǎn)生差分以獲取有關(guān)內(nèi)部狀態(tài)或者密鑰的額外信息，利用這些額外信息構(gòu)建新的關(guān)于內(nèi)部狀態(tài)或者密鑰的代數(shù)方程組；第三步，利用基于可滿足性問題［4］，基于偽隨機(jī)化問題［5］，基于Grbner［6］基等方法求解第一步和第二步構(gòu)建的方程組，進(jìn)而恢復(fù)內(nèi)部狀態(tài)或者初始密鑰信息。本文使用CryptoMiniSAT 解析器進(jìn)行密鑰求解，使用方法見文獻(xiàn) ［7］。

圖2 代數(shù)故障攻擊一般過程

2.2 故障模型

本文采用隨機(jī)單比特翻轉(zhuǎn)故障模型，即假設(shè)攻擊者具有下列能力：

（1）能夠正確運(yùn)行密碼算法，對(duì)明文信息P 進(jìn)行加密得到正確的密文C；

（2）能夠向密碼任意位置注入隨機(jī)單比特故障使密碼內(nèi)部狀態(tài)某個(gè)比特發(fā)生翻轉(zhuǎn) （0→1或1→0），并對(duì)明文信息P 加密得到錯(cuò)誤密文C′；

（3）能夠反復(fù)多次向密碼注入故障，并且能夠重啟密碼設(shè)備恢復(fù)初始狀態(tài)。

2.3 代數(shù)方程組構(gòu)建

由2.1節(jié)可知，對(duì)模加運(yùn)算的代數(shù)故障攻擊方程組構(gòu)建可分為兩步：根據(jù)模加運(yùn)算特點(diǎn)構(gòu)造代數(shù)方程組；注入隨機(jī)單比特故障，利用故障信息建立額外代數(shù)方程組；為了更好的說明代數(shù)方程組的構(gòu)建，首先給出模加運(yùn)算的定義。

定義 設(shè)X，Y，Z∈GF （2n），X＝ （xn－1，xn－2，…，x0），Y ＝ （yn－1，yn－2，…，y0），Z＝ （zn－1，zn－2，…，z0），x0，y0，z0分別表示X，Y，Z 的最低位，則GF （2n）上的模加運(yùn)算可表示為

（1）利用模加運(yùn)算特點(diǎn)構(gòu)造代數(shù)方程組；

根據(jù)文獻(xiàn) ［8］，可以將式 （8）等價(jià)轉(zhuǎn)換成GF（2）上的如式 （9）、式 （10）所示的方程組

其中，ci表示進(jìn)位，且有c0＝0，所以根據(jù)式 （9）、式（10）可以將GF（2n）上的模加運(yùn)算轉(zhuǎn)換成GF（2）上的代數(shù)方程組。

（2）利用故障信息構(gòu)建代數(shù)方程組；

一般而言，由于模加運(yùn)算在密碼算法結(jié)構(gòu)中的位置不同，向模2n加運(yùn)算結(jié)構(gòu)注入隨機(jī)單比特故障α∈GF（2n），α＝ （εn－1，εn－2，…，ε0），存在下列兩種情況：

1）已知注入的隨機(jī)故障α，正確輸出Z 和錯(cuò)誤輸出Z′；

圖3 第一種情況

如圖3所示，故障值α和正確和錯(cuò)誤輸出Z 和Z′均已知，則根據(jù)故障信息可以得到如式 （11）所示的方成組

同式 （8），我們可以將式 （11）轉(zhuǎn)化成GF（2）上的代數(shù)方程組，如式 （12）所示

2）已知注入的隨機(jī)故障α，正確輸出和錯(cuò)誤輸出差分ΔZ；

設(shè)ΔZ＝β，β＝ （δn－1，δn－2，…，δ0），如圖4 所示，已知正確輸出和錯(cuò)誤輸出的差分β則可以得到如式 （13）

圖4 第二種情況

同式 （8），將式 （14）等價(jià)轉(zhuǎn)化成GF（2）上的代數(shù)方程組，得到如下式 （15）－式 （17）

綜合上述兩種情況可以構(gòu)建模加運(yùn)算在GF（2）上的代數(shù)方程組，通過多次故障注入，可以構(gòu)建足夠多的代數(shù)方程組，對(duì)方程組進(jìn)行求解可以恢復(fù)X，Y 的值。值得指出的是，由文獻(xiàn) ［9］知，雖然式 （11）所對(duì)應(yīng)的方程組系統(tǒng)包含了全部X，Y 的比特信息，但由于方程中的最高位不提供任何解的信息，因此通過求解式 （11）可以恢復(fù)X，Y全部的前n－1比特信息，式 （13）所對(duì)應(yīng)的方程組系統(tǒng)只包含了X，Y 的前n－1比特信息，因此同樣只能恢復(fù)X，Y 的前n－1比特信息。

3 Helix代數(shù)故障攻擊

對(duì)Helix的代數(shù)故障攻擊可分為3步，第一步在Helix第i（i＞8）輪，選擇不同明文Pi的值得到不同的密鑰流，使用本文2.3節(jié)提出的方法構(gòu)建代數(shù)方程組求解出C 值；第二步通過在指定位置注入隨機(jī)故障求取D 的值，進(jìn)而求出密鑰Xi，1的值；第三步，根據(jù)密鑰擴(kuò)展算法，重復(fù)第一步第二步恢復(fù)出全部的密鑰信息；下面將詳細(xì)論述上面的攻擊過程。

3.1 恢復(fù)C 值

步驟1 隨機(jī)選擇明文Pi，運(yùn)行密碼設(shè)備得到相應(yīng)的密鑰流，則有式 （18）成立

步驟2 重啟密碼設(shè)備，改變明文Pi使新的明文滿足P′i＝PiΔ得到新的密鑰流 （）′，則有式 （19）成立

對(duì)式 （18）和式 （19）求差分可以得到式 （20）

在式 （20）中令φ＝PiA 則可將式 （20）轉(zhuǎn)換為式（21）

顯然式 （21）與2.3節(jié)中的式 （9）對(duì)應(yīng)，采用2.3節(jié)中的方法將式 （21）轉(zhuǎn)換成二元域上的方程組。

步驟3 改變步驟2中的Δ值并重新執(zhí)行步驟2，構(gòu)建足夠多的代數(shù)方程組；

步驟4 對(duì)步驟1～步驟3構(gòu)建的代數(shù)方程系統(tǒng)進(jìn)行求解，恢復(fù)φ，B，C；

3.2 恢復(fù)密鑰Xi，1

步驟1 使用3.1節(jié)明文Pi，運(yùn)行密碼設(shè)備得到密鑰流Zi＋10，則有

步驟2 如圖5 所示，保持明文不變，在E 處注入隨機(jī)比特故障m，得到新的密鑰流 （）′，則有

因?yàn)閆，Z′和C 均已知，且根據(jù)文獻(xiàn) ［10］可以得到定理：

定理［10］對(duì)于本文2.3節(jié)中式 （8），若在X 上發(fā)生的單比特故障α，則α＝2l成立的充要條件為

由定理1可以得到故障值m，顯然式 （22）、式 （23）對(duì)應(yīng)2.3節(jié)中的第一種情況，采用2.3節(jié)中的方法將其傳換成二元域上代數(shù)方程組；

步驟3 重啟密碼設(shè)備，并保持明文不變，重新執(zhí)行步驟1和步驟2，構(gòu)建足夠多的代數(shù)方程組；

圖5 對(duì)Helix的代數(shù)故障攻擊

步驟4 對(duì)步驟1～步驟3構(gòu)建的代數(shù)方程系統(tǒng)進(jìn)行求解，恢復(fù)Xi，1；

3.3 恢復(fù)密鑰Xi，0

步驟1 使用3.1節(jié)明文Pi，運(yùn)行密碼設(shè)備得到相應(yīng)的密鑰流Zi＋10

步驟2 如圖5 所示，保持明文不變，在G 處注入隨機(jī)比特故障n，得到新的密鑰流 （）′

因?yàn)橛墒?（19）可以計(jì)算出B 和B′，根據(jù)定理可以計(jì)算得到故障n，所以式 （24）和式 （25）同樣對(duì)應(yīng)于2.3節(jié)中的第一種情況，將其轉(zhuǎn)換成二元域上的方程組。

步驟3 重啟密碼設(shè)備，并保持明文不變，重新執(zhí)行步驟1和步驟2，構(gòu)建足夠多的代數(shù)方程組；

步驟4 對(duì)步驟1～步驟3 構(gòu)建的代數(shù)方程組進(jìn)行求解，恢復(fù)Xi，0；

3.4 恢復(fù)其余密鑰信息

由本文1.3節(jié)Helix密鑰擴(kuò)展算法可知，可以對(duì)連續(xù)八輪i，i＋1，i＋2，i＋3，i＋4，i＋5，i＋6，i＋7 （其中i滿足i mod8＝0）輪加密進(jìn)行攻擊，由于用戶密鑰長度（U）未知，因此由3.1節(jié)方法只能恢復(fù)工作密鑰K0，K2，K3，K4，K6，K7共6個(gè)密鑰，采用3.2節(jié)方法可以恢復(fù)剩下兩個(gè)工作密鑰K1，K5，至此恢復(fù)了Helix的全部工作密鑰K0，K1，K2，K3，K4，K6，K5，K7。

4 仿真實(shí)驗(yàn)結(jié)果及分析

在普通PC 機(jī) （CPU 為AMD Athlon （tm）64Processor 3000＋，內(nèi)存為1G）上，使用C＋＋語言、CryptoMin－iSAT 軟件實(shí)現(xiàn)了Helix的代數(shù)故障攻擊仿真實(shí)驗(yàn)，其中故障誘導(dǎo)得到錯(cuò)誤密文采用計(jì)算機(jī)軟件模擬完成。下面給出某次Helix代數(shù)故障攻擊過程：

（1）產(chǎn)生一個(gè)隨機(jī)明文P＝21646C726F77202C6F6C6C6 54816，初始向量N＝6665646362613938373635343332313016，用戶密鑰U＝78696C654816，則正常運(yùn)行密碼設(shè)備生成的正確密文C＝0DF2232C80C5A0827AB9274C6C16；生成的工作密鑰K＝39113251F5857A359FB69B734A2803F4DA15F16D20 D61C8FD2A1A3CB7AD71E6C16。

（2）根據(jù)3.1節(jié)中方法，通過選擇明文P 恢復(fù)C 值；

（3）根據(jù)3.2節(jié)中方法，注入隨機(jī)故障恢復(fù)Xi，1；

（4）根據(jù)3.3節(jié)中方法，注入隨機(jī)故障恢復(fù)密鑰Xi，0

（5）根據(jù)密鑰擴(kuò)展算法恢復(fù)其余密鑰信息，結(jié)果見表2。

表2 Helix代數(shù)故障攻擊結(jié)果

如表2所示，攻擊可以恢復(fù)工作密鑰K0～K7除最高1位的所有248比特，且實(shí)驗(yàn)結(jié)果同真實(shí)密鑰一致，攻擊成功，剩下的8比特密鑰信息可以通過窮舉得到。

圖6表示恢復(fù)C 值，Xi，1，Xi，0所需選擇明文次數(shù)和故障注入次數(shù)。結(jié)果表明，攻擊恢復(fù)密鑰Xi，1所需的故障注入次數(shù)較多約為260次，恢復(fù)Xi，1所需的故障注入次數(shù)較少僅需10次，而恢復(fù)C 值所需明文選擇次數(shù)為100次，所以總的故障注入總數(shù)為580 （10×6＋260×2）次。

圖6 實(shí)驗(yàn)恢復(fù)C 值，Xi，1，Xi，0結(jié)果

5 結(jié)束語

本文首次將代數(shù)故障攻擊應(yīng)用在Helix流密碼上，提出了一種對(duì)模加運(yùn)算通用的代數(shù)故障攻擊模型，詳細(xì)介紹了該模型下代數(shù)方程組的構(gòu)建，給出了整個(gè)攻擊過程。

實(shí)驗(yàn)結(jié)果表明，580次故障注入可以恢復(fù)Helix工作密鑰除最高位的248比特信息，剩余8比特信息可以通過窮舉得到。本文所提出的對(duì)模加方程的代數(shù)故障攻擊模型具有通用性強(qiáng)，求解方便等優(yōu)點(diǎn)，可以為其他具有模加運(yùn)算結(jié)構(gòu)的流密碼和分組密碼的代數(shù)故障攻擊提供一定的參考。

［1］ZHENG B，GUAN J.Differential characteristic probability of added Key on modulo 2noperation ［J］.Journal of Electronics＆Information Technology，2009，31 （11）：2708－2712 （in Chinese）.［鄭斌，關(guān)杰.“與密鑰模2n加運(yùn)算”的差分性質(zhì)研究 ［J］.電子信息學(xué)報(bào)，2009，26 （2）：132－136.］

［2］Courtois N，Ware D，Jackson K.Fault－algebraic attacks on inner rounds of DES ［C］／／eSmart，2010：22－24.

［3］Mohamed M，Bulygin S.Using SAT solving to improve differential fault analysis of trivium［J］.International Journal Security and Its Applications，2012，6 （1）：29－37.

［4］Faure G，Nieuwenhuis R，Oliveras A，et al.SAT modulo the theory of linear arithmetic：Extract，inexact and commercial solvers［G］.LNCS 4996：SAT，2008：77－90.

［5］Yossed O，Mario K，Thomas P，et al.Side－channel analysis in the presence of errors［C］／／CHES.USA：California，2010：428－442.

［6］Sugita M，Kawazoe M，Imai H.Relation between XL algorithm and Grbner basis algorithms ［EB／OL］.http：／／eprint.iacr.org／112，2010.

［7］LI Junru，GU Dawu.Differential fault analysis on PRESENT［C］／／China Crypt，2009：3－13 （in Chinese）.［李卷孺，谷大武.PRESENT 算法的差分故障攻擊 ［C］／／中國密碼學(xué)會(huì)，2009：3－13.］

［8］Courtois N，Debraize B.Algebraic description and simultaneous linear approximations of addition in snow 2.0 ［C］／／ICICS，2008：328－344.

［9］LI Shenhua.Cryptanalysis of two symmetric encryption algorithms ARIA and Salsa20 ［D］.Jinan：Shandong University Doctoral Dissertation，2008：42－50 （in Chinese）.［李 申 華.對(duì)稱密碼算法ARIA 和Salsa20的安全性分析 ［D］.濟(jì)南：山東大學(xué)博士學(xué)位論文，2008：42－50.］

［10］ZHANG Zhongya.Security analysis on block－like type stream ciphers［D］.Zhengzhou：PLA Information Engineering University Master Dissertation，2011：47－49 （in Chinese）.［張中亞.類分組型序列密碼算法的安全性分析 ［D］.鄭州：解放軍信息工程大學(xué)碩士論文，2011：47－49.］