旁路信息的分級泄露模型與安全性分析

摘要：旁路攻擊是一種新的密碼分析方法，其利用了密碼設備在運算時泄漏的信息破解密碼系統。從信息泄露的一般性出發，提出了一種旁路信息分級泄露模型并給出其形式化描述。該模型將泄露信息分為算法級、指令級和邏輯門級泄漏。在此基礎上，對不同泄露級別上采用的防御方法的安全性進行分析比較，最后對抗旁路攻擊的安全芯片的設計給出建議。

關鍵詞：密碼芯片; 旁路攻擊; 分級泄漏模型

中圖分類號：TP301.6

文獻標志碼：A

文章編號：1001－3695(2008)06－1799－03

加密芯片以其良好的封閉性能，具有軟件和電路板級加密方式不可比擬的優勢，而廣泛應用于各種類型的密碼系統中。傳統意義上，加密芯片的安全性取決于其所采用的加密算法、認證方式以及工作協議的安全性，其安全性分析也往往是就以上幾點進行的。但是，一個實用的密碼芯片的安全性不僅僅與密碼算法的設計有關，還涉及到程序實現和硬件設計等多個方面。最近的研究表明，密碼芯片在計算過程中會泄露出各種與其運算相關的旁路信息，如執行時間、功耗、電磁輻射等[1~3]。攻擊者通過收集這些信息，結合統計分析方法就能快速地破解密碼系統。旁路攻擊的提出對密碼芯片的安全性已經構成了嚴峻的威脅，使得對密碼芯片抗旁路攻擊的安全設計研究成為當前的熱點。

1信息泄露與旁路攻擊

旁路信息泄露具有多樣化的特點，從信息泄露一般性出發，提出一種分級泄露模型并給出其形式化描述。在此基礎上，給出旁路攻擊模型的形式化描述。

1．1分級泄露模型

旁路信息是指密碼芯片在運算過程中泄露的各種信息，如執行時間、功耗、電磁輻射等信息。

為了分析旁路信息的特征，Macali等人首先提出了物理信息泄露模型[4]：

其中：P表示一臺物理圖靈機；A為與之對應的虛擬圖靈機；旁路信息泄露函數L將這部分聯系起來。在Macali模型的基礎上，Standaert等人給出了更直觀的描述，將泄露信息與電路、信號等物理實現關聯起來[5]。為了全面理解旁路信息，本文將算法級的泄露考慮進來，提出一種分級泄露模型，如圖1所示。該泄露模型將旁路信息分為三個抽象級別，即算法級泄露L(A)、指令級泄露L(O)和門級泄露L(G)。為了描述不同級別泄露信息之間的相互關系，本文采用BNF的形式化描述方法[6]。首先對使用的符號系統進行說明如表1所示。

其中：參數Si、Qj、Gk和∑分別表示圖靈機的相關運行狀態、操作指令、門電路和電路中所有的信號集合。

通過對泄露信息的形式化描述，本文從一般性的角度對不同類型的信息泄漏及其防御方法進行分析比較。

1．2旁路攻擊模型

旁路攻擊是一種非入侵式的密碼分析方法。攻擊者通過收集密碼芯片運算過程中的各種泄露信息，利用統計分析方法快速破解密碼系統。旁路攻擊過程可以分為兩個階段，即信號采集階段和旁路分析階段。

假設fK為與密鑰K相關的加密原語，(fK，L)為加密原語所對應的物理實現(fK，L)在信號采集階段，建立相應的采樣信號集合。在分析階段，利用統計方法從泄露信息中分析出密鑰信息，常用的統計方法包括假設檢驗、貝葉斯分類。

該統計實驗的時間復雜性為τ=τp+τc，旁路信息采樣次數為q=qp+qc。其中：τp、τc、qp、qc分別對應于信號采集階段和分析階段的時間和旁路信息采樣次數。

2分級防御策略

旁路攻擊的防御策略沿著兩條不同線索：a)，減少密碼芯片的泄露信號強度，使得攻擊者無法獲取有效的泄漏信息；b)降低泄漏信息與內部運算的相關性。

結合分級泄露模型，下面從三個方面對防御策略進行分析。

其中：集合R包含了所有與密鑰K運算相關的狀態，而集合N包含所有與密鑰運算無關的狀態。

密鑰相關集R包含n個狀態時，攻擊者需要對這n個點的泄漏信息進行采樣，并建立泄漏信號腳本leak={l1，l2，…，ln}。算法級防御的基本思想是使攻擊者無法準確地獲取集合R所對應的泄漏信息leak。因此，可以通過在算法中插入隨機的時延，使得密鑰相關狀態在運行時間上不確定，進而使得攻擊者無法準確地獲取集合R的泄漏信息。

2）指令級防御

不同的指令在計算時具有不同的泄露特征，如功耗、執行時間等。由于指令的執行與密鑰的選擇緊密相關，因此攻擊者只需要能區分不同的指令就能推測出密鑰。對于算法A，其密鑰K與指令泄露信息之間的關系如(5)所示：

簡單旁路攻擊正是利用了指令泄露特征的不同對密碼系統進行攻擊。例如ECC密碼算法的加法與倍乘運算，RSA密碼算法的乘法和平法運算的泄漏信息不同，攻擊者利用這一特征成功地破解沒有保護的ECC密碼算法與RSA算法[7]。

指令級防御的主要思想是：減少指令運算與密鑰的相關性，使得攻擊者無法根據指令的泄漏特征直接推測出密鑰信息。常見的防御方法，比如構造與密鑰無關的指令執行序列[8]或使用泄漏無差異的運算指令[9]。

3）寄存器、邏輯門級防御

寄存器級的信息泄露主要表現在寄存器狀態由0→1或1→0跳變時，對外泄露的信息存在差異性。不同于指令級的泄漏，寄存器級的泄漏反映的是執行的數據與密鑰的相關性。攻擊者可以通過寄存器的狀態變遷，結合統計分析方法破解密碼系統。例如，沒有保護的AES密碼算法的輪密鑰加運算，如圖2(a)所示，攻擊者可以通過分析寄存器運算時泄漏的功耗進行攻擊。

為了防御差分攻擊，通常采用掩碼技術[10]屏蔽寄存器狀態變化的真實情況，如圖2(b)所示。隨著掩碼數目的增加，攻擊者需要通過復雜的高階攻擊破解密碼系統[11]。對于高階攻擊的防御，文獻[12]提出了一種改進掩碼的防御方法。

邏輯門在電路實現上，由于輸入的不同，電路輸出存在一定差異性。文獻[13]提出采用掩碼技術的邏輯門實現方法，但是最近的研究表明即使采用掩碼技術的門級防御方法也會遭到旁路攻擊[14]。

為了防御門級電路的攻擊，通常采用具有恒定輸出的穩態電路，如DDL電路[15]。圖3給出了輸出恒定的與門電路實現，無論輸入a、b為何值，其電路輸出均對應兩個互補的狀態c、。因此，具有恒定輸出的穩態電路，從硬件設計上減少了由輸入/輸出的差異造成的信息泄漏，從而有效地防御了旁路攻擊。

3抗旁路攻擊的安全設計建議

根據分級泄露模型，密碼芯片的抗旁路攻擊安全設計可以從不同的泄漏級別上進行考慮。算法級和指令級防御策略主要以改變泄漏信息和內部運算的相關性為目的。其防御方法具有易于實現、代價小的優點，但是針對不同的密碼算法，需要采用不同的防御方法；電路級的防御則是通過改變信息泄露行為，以減少泄漏信息量為目標。其優點是安全性高且適合于不同的算法。其缺陷是防御開銷大。因此，從安全性的角度出發，可以通過以下的策略對旁路攻擊進行防御：

a)對于密碼芯片的軟/硬件實現，盡可能地使用固件(firmware)或恒穩態DDL電路的形式減少信息泄露的風險。

b)對密碼算法的運行狀態進行有效劃分，對于關鍵信息如密鑰相關狀態集，通過掩碼技術、隱指令技術、插入隨機時延等方法屏蔽真實的泄漏信息，從而降低泄漏與運算的相關性，以此防御旁路攻擊。

此外，從密鑰管理的角度，提供安全的密鑰更新技術，如一次一密，使得攻擊者在密鑰的生存期內無法破

解該密碼也是一種有效的旁路攻擊防御手段。

4結束語

密碼芯片的旁路信息泄漏已經對密碼系統的安全構成了嚴峻的威脅，而對信息泄漏模型的研究和分析則有助于制定安全的防御策路。針對密碼芯片泄漏信息的多元化特點，本文從一般性的角度出發，提出一種形式化的旁路信息分級泄漏模型。在此基礎上，討論了不同級別的泄漏信息的威脅及相應的防御策略。最后給出了密碼芯片的安全設計的建議。

參考文獻：

[1]KOCHER P. Timing attacks on implementations of Diffie－Hellman， RSA， DSS， and other systems[C] //Proc of CRYPTO’96. [S.l.]: Springer－Verlag， 1996:104－113.

[2]KOCHER P， JAFFE J， JUN B. Differential power analysis[C] //Proc ofCRYPTO’99. [S.l.]: Springer－Verlag， 1999:388－397.

[3]AGRAWAL D. The EM side channels[C] //Proc of CHES 2002. [S.l.]: Springer－Verlag， 2003:29－45.

[4]MICALI S， REYZINL. Physically observable cryptography[C] //Proc of TCC. 2004:278－296.

[5]STANDAERT F X， MALKIN T G， YUNG M. A formal practice－oriented model for the analysis of side－channel attacks. version 1.4[EB/OL]. [2006－12－04]. http: //eprint.iacr.org/2006/139.pdf.

[6]NAUR， PETER.Revised report on the algorithmic language ALGOL 60[J]. Communications of the ACM， 1960，3(5):299－314.

[7]OSWALD E. Enhancing simple power－analysis on elliptic curve crypto－systems[C] //Proc of CHES 2002. [S.l.]: Springer－Verlag， 2003:82－97.

[8]OKEYA K， TAKAGI T. A more flexible countermeasure against side channel attack using window method[C] //Proc of CHES 2003. [S.l.]: Springer－Verlag， 2003:397－410.

[9]JOYE M， QUISQUATER J J. Hessian elliptic curves and side－channel attacks[C] //Proc of CHES 2001. [S.l.]: Springer－Verlag， 2001: 402－410.

[10]STANDAERT F X， PEETERS E. On the masking countermeasure and high order power analysis attacks[C] //Proc of International Conference on Information Technology. 2005:562－567.

[11]JOYE M. On second－order differential power analysis[C] //Proc of CHES. [S.l.]: Springer－Verlag， 2005:293－308.

[12]AKKAR M L， GOUBIN L. A generic protection against high－order differential power analysis[C] //Proc of FSE 2003. [S.l.]: Springer－Verlag， 2003:192－205.

[13]ISHAI Y， SAHAI A， WAGNER D. Private circuits:securing hardware against probing attacks[C] //Proc of Advances in Cryptology－CRYPT 2003. [S.l.]: Springer－Verlag， 2003:463－481.

[14]MANGARD S， POPP T， GAMMEL B. Side－channel leakage of masked CMOS gates[C] //Proc of CT－RSA. 2005:351－365.

[15]TIRI K， HWANG D， et al. A side－channel leakage free coprocessor IC in 0.18um CMOS for embedded AES－based cryptographic and biometric processing[C] //Proc of ACM/IEEE Design Automation Conference (DAC). 2005:222－227.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文