針對從右到左平方乘算法的RSA故障分析

陳財(cái)森， 杜家興， 喻 武， 鄧柳于勤

(1. 裝甲兵工程學(xué)院科研部，北京 100072; 2. 裝甲兵工程學(xué)院訓(xùn)練部，北京100072;3. 裝甲兵工程學(xué)院信息工程系，北京 100072)

針對從右到左平方乘算法的RSA故障分析

陳財(cái)森1， 杜家興1， 喻 武2， 鄧柳于勤3

(1. 裝甲兵工程學(xué)院科研部，北京 100072; 2. 裝甲兵工程學(xué)院訓(xùn)練部，北京100072;3. 裝甲兵工程學(xué)院信息工程系，北京 100072)

提出了針對從右到左平方乘算法實(shí)現(xiàn)的RSA故障分析算法，該算法利用多次在模冪運(yùn)算執(zhí)行過程中在不同指定位置對模數(shù)N注入故障獲得的故障簽名，通過密鑰搜索恢復(fù)出參與故障運(yùn)算的密鑰片斷，最終恢復(fù)完整密鑰。從理論上分析了該算法的復(fù)雜度，并通過仿真實(shí)驗(yàn)進(jìn)行了驗(yàn)證，得到了密鑰搜索空間和所需注入故障數(shù)目與一次攻擊恢復(fù)密鑰片斷長度之間的對應(yīng)關(guān)系。

旁路攻擊；故障分析；模冪運(yùn)算；從右到左平方乘算法；RSA

目前，隨著電子綜合信息系統(tǒng)在武器裝備自動化控制系統(tǒng)中的廣泛應(yīng)用，智能卡芯片作為密碼設(shè)備中的基礎(chǔ)設(shè)施，為武器系統(tǒng)安全提供了有力支撐，尤其是在設(shè)備安全認(rèn)證方面，RSA芯片發(fā)揮著重要作用，因此其安全性越來越被研究者們所關(guān)注。

隨著現(xiàn)代技術(shù)手段的不斷提高和廣泛應(yīng)用，單純從密碼算法數(shù)學(xué)結(jié)構(gòu)的角度研究密碼芯片安全性已經(jīng)遠(yuǎn)遠(yuǎn)不夠，還需要從密碼算法的實(shí)現(xiàn)角度來考慮其安全性問題。在實(shí)際應(yīng)用中，密碼算法通常在各種芯片上實(shí)現(xiàn)，如智能卡、加密存儲卡和加密機(jī)芯片等，密碼算法在這些芯片中產(chǎn)生的故障信息可能被攻擊者用來破解密碼。故障攻擊是指通過輻射、X光、微探測或改變電壓等方法在芯片中注入故障，依據(jù)從芯片泄漏的信息推算出密鑰的一種攻擊方式。1996年，Boneh等[1]首次提出了利用隨機(jī)硬件故障攻擊RSA簽名算法的攻擊思想；2002年，Aumuller等[2]針對采用中國剩余定理(Chinese Remainder Theorem, CRT)的RSA算法提出了差分故障攻擊算法；2013年，F(xiàn)ouque等[3]提出了基于蒙哥馬利乘法實(shí)現(xiàn)模冪運(yùn)算的RSA-CRT簽名算法的故障攻擊方案，并給出了3個針對小寄存器的故障模型；國內(nèi)研究者[4-5]多數(shù)是針對RSA-CRT算法的故障攻擊展開研究。

由于RSA-CRT算法實(shí)現(xiàn)過程較為復(fù)雜，因此在智能卡芯片的硬件實(shí)現(xiàn)過程中一般都采用執(zhí)行速度較快的“Right-to-Left(從右到左)”平方乘算法。由于原有針對RSA-CRT算法的故障分析方法對平方乘算法實(shí)現(xiàn)的RSA存在一定的不適用性，本文為此展開研究，依據(jù)模型參數(shù)，建立故障分析模型，給出在執(zhí)行模冪運(yùn)算過程中針對模數(shù)N注入隨機(jī)字節(jié)故障的攻擊算法。

1 RSA算法與故障攻擊模型

1.1 RSA公鑰密碼算法

RSA是使用公鑰(N,e)加密和私鑰d解密的公鑰加密系統(tǒng)。它使用的模數(shù)N是2個大素?cái)?shù)p和q的乘積(N=p×q)，指數(shù)e和d必須滿足e×d=1mod(p-1)(q-1)。加密運(yùn)算執(zhí)行C=memodN，解密運(yùn)算執(zhí)行m=CdmodN，可以看出其核心是模冪運(yùn)算m=CdmodN。一般RSA算法模冪運(yùn)算采用平方乘算法，分為“Left-to-Right(從左到右)”和“Right-to-Left” 2種算法，如圖1、2所示。

圖1 從左到右平方乘模冪算法

圖2 從右到左平方乘模冪算法

由圖1、2可知:2種算法執(zhí)行時(shí)需要同樣次數(shù)的平方和乘法運(yùn)算；但算法2總是用固定的m值做乘法。 Berzati等[6]提出了針對算法1的故障分析算法，但是由于算法2中第(2)步的平方與模乘運(yùn)算是2個獨(dú)立的過程，從硬件方面來說，它們可被并行實(shí)現(xiàn)，減小了算法運(yùn)算的時(shí)鐘周期，從而提高了算法的運(yùn)算速度，因此本文采用算法2來實(shí)現(xiàn)模冪運(yùn)算。

1.2 故障攻擊模型

執(zhí)行一次故障攻擊，首先需要對算法和故障影響進(jìn)行分析研究。除了考慮如何注入故障外，還要考慮如何利用故障的結(jié)果獲取有用信息，因此需要建立一個注入故障與故障對算法產(chǎn)生影響之間關(guān)系的模型。故障按類型分為永久故障和暫時(shí)故障[7]：前者指故障一旦注入，則永久對攻擊對象產(chǎn)生破壞；而后者只是使攻擊對象執(zhí)行某些計(jì)算時(shí)暫時(shí)出錯，如使用電磁輻射、微探測或電壓變化等手段。影響故障攻擊模型的主要參數(shù)有故障注入位置、注入時(shí)機(jī)、故障大小和故障數(shù)目等。依據(jù)這些參數(shù)，本文建立針對算法2的故障攻擊模型，如圖 3所示。

圖3 故障攻擊模型

圖3虛線框給出了針對算法2中運(yùn)算步驟(2)可能發(fā)生故障的4個位置。Berzati等[6]在文獻(xiàn)[8-9]的基礎(chǔ)上擴(kuò)展了故障模型，在模冪運(yùn)算執(zhí)行過程中，對模數(shù)N注入故障，修改其值，在錯誤的模數(shù)下執(zhí)行剩余的操作，而不是在模冪運(yùn)算執(zhí)行前注入故障，導(dǎo)致整個執(zhí)行都是在錯誤模數(shù)情況下完成。攻擊模型為：假設(shè)攻擊者在執(zhí)行算法2 從0到n-1的過程中，從第j個循環(huán)操作開始對模數(shù)N注入1個隨機(jī)字節(jié)故障(即控制故障注入的時(shí)機(jī)t)，故障數(shù)目為1，故障類型為暫時(shí)故障，故障大小為字節(jié)故障(影響模數(shù)N中1個字節(jié)的值)。

2 針對從右到左平方乘模冪算法的故障攻擊

2.1 故障注入

故障攻擊不僅可以在硬件上通過激光、微探針、瞬態(tài)時(shí)鐘、瞬態(tài)電源、瞬態(tài)外部電場、光輻射和渦旋電流等故障注入手段實(shí)現(xiàn)，還可以通過利用計(jì)算機(jī)軟件模擬技術(shù)進(jìn)行仿真來實(shí)現(xiàn)[3]。目前，注入故障的方式主要有2大類：1)攻擊者利用被攻擊模塊執(zhí)行密碼計(jì)算期間發(fā)生的計(jì)算故障，這類故障既可以是攻擊者刻意誘導(dǎo)所為，也可以是密碼設(shè)備受到異常環(huán)境作用等因素的影響所致；2)攻擊者通過向被攻擊模塊注入惡意的非法輸入數(shù)據(jù)等信息而實(shí)施的故障誘導(dǎo)。本文重點(diǎn)考慮1)類故障注入方式。針對算法2的執(zhí)行過程，利用激光或微探針的方式對模數(shù)N對應(yīng)的寄存器實(shí)施干擾，使其在執(zhí)行過程中發(fā)生1個字節(jié)故障，具體故障注入后的結(jié)果變換過程如下。

(1)

(2)

(3)

2.2 密鑰分析算法

(4)

圖4 RSA算法故障攻擊流程

圖5 RSA算法密鑰恢復(fù)過程

RSA算法故障攻擊流程：

1) 對于從右到左平方乘模冪算法實(shí)現(xiàn)的RSA算法，當(dāng)密鑰d從右邊d0開始執(zhí)行到dj-1時(shí)都是正確執(zhí)行的；

RSA算法密鑰恢復(fù)步驟：

3 仿真實(shí)驗(yàn)結(jié)果與復(fù)雜度分析

3.1 仿真實(shí)驗(yàn)結(jié)果與對比分析

表1 不同密鑰長度對應(yīng)的執(zhí)行時(shí)間和操作時(shí)間

表2 RSA故障攻擊仿真實(shí)驗(yàn)結(jié)果

從表2可以看出：當(dāng)增加一次恢復(fù)的密鑰片斷長度時(shí)，雖然能夠減小注入故障數(shù)目，但是在匹配密鑰片斷時(shí)卻需要更大的密鑰搜索空間。如果一次恢復(fù)的密鑰片斷長度太短，在實(shí)際注入故障時(shí)，會增大故障注入時(shí)機(jī)的難度，而且太大的注入故障數(shù)目有可能造成攻擊對象的永久性破壞，因此有必要對攻擊算法的復(fù)雜度進(jìn)行分析。

3.2 復(fù)雜度分析

圖6 算法復(fù)雜度分析曲線

4 結(jié)論

本文對從右到左平方乘模冪算法實(shí)現(xiàn)的RSA故障分析進(jìn)行了研究，結(jié)果表明：簡單的平方乘法迭代給故障攻擊提供了可能性，采用對模冪運(yùn)算執(zhí)行過程中的模數(shù)N注入隨機(jī)字節(jié)故障的手段，建立故障模型，利用密鑰空間搜索恢復(fù)密鑰片斷，通過多次執(zhí)行故障注入,最終恢復(fù)完整密鑰，對從左到右平方乘模冪算法實(shí)現(xiàn)RSA故障分析具有一定的借鑒作用。但同時(shí)從實(shí)驗(yàn)結(jié)果可以看出：在進(jìn)行軟件仿真時(shí)，由于是軟件實(shí)現(xiàn)，執(zhí)行速度較快，因此執(zhí)行所消耗的時(shí)間都是可以忍受的。而在實(shí)際攻擊中，具有8位CPU的智能卡微控制器通常都不能在數(shù)分鐘的時(shí)間內(nèi)執(zhí)行一次RSA計(jì)算，因此如何將此攻擊算法運(yùn)用于實(shí)際是將來值得研究和關(guān)注的。此外，本文僅對模型中可能出現(xiàn)故障的一種情況展開分析，實(shí)際應(yīng)用中故障的情況多變，因此下一步將對其他故障情況進(jìn)行研究和分析。

[1] Boneh D, DeMillo R A, Lipton R J. On the Importance of Checking Cryptographic Protocols for Faults[J]. Lecture Notes in Computer Science, 1997,1233:37-51.

[2] Aumuller C, Bier P, Fischer W, et al. Fault Attacks on RSA with CRT:Concrete Results and Practical Countermeasures[C]∥Kaliski B S, Koc C K, Paar C.Proceedings of CHES 2002 4th International Workshop, Redwood Shores. CA, USA:Springer,2002:260-275.

[3] Fouque P A, Guillermin N, Delphine L, et al. Attacking RSA-CRT Signatures with Faults on Montgomery Multiplication[J]. Journal of Cryptographic Engineering, 2013, 3(1): 59-72.

[4] 祝力. 公鑰密碼及其故障分析研究[D]. 上海:上海交通大學(xué), 2007.

[5] 王紅勝,宋凱,張陽,等.針對基于中國剩余定理RSA算法的光故障攻擊分析[J]. 微電子學(xué)與計(jì)算機(jī), 2012, 29(1): 38-41.

[6] Berzati A, Canovas C, Dumas J G, et al. Fault Attacks on RSA Public Keys: Left-to-right Implementations are also Vulnerable[C]∥Fischlin M. Proceedings of the Cryptographers’Track at the RSA Conference 2009. San Francisco,USA:Springer,2009:414-428.

[7] Schmidt J M. Differential Fault Analysis[EB/OL]. (2008-06-16)[2014-09-01].http://www.a-sit.at/pdfs/DFA-Report.pdf

[8] Brier E, Chevallier-Mames B, Ciet M, et al. Why One Should Also Secure RSA Public Key Elements[J]. Lecture Notes in Computer Science, 2006,4249:324-338.

[9] Seifert J P. On Authenticated Computing and RSA-based Authentication[C]∥Proceedings of 12th ACM Conference on Computer and Communications Security.New York: Association for Computing Machinery,2005:122-127.

(責(zé)任編輯:尚彩娟)

Fault Analysis on RSA with Right-to-left Square and Multiply Algorithm

CHEN Cai-sen1, DU Jia-xing1, YU Wu2, DENG Liu-yu-qin3

(1. Department of Science Research, Academy of Armored Force Engineering, Beijing 100072, China;2. Department of Training, Academy of Armored Force Engineering, Beijing 100072, China;3. Department of Information Engineering, Academy of Armored Force Engineering, Beijing 100072, China)

This paper proposes an algorithm of fault analysis on RSA with “right-to-left” square and multiply algorithm, using the faulty signature which is the result of injecting fault into modulusNat different appointed location repeatedly during module exponentiation, recovering a key segment which is used during the faulty computation by searching secret key, and finally recovering the whole private key. The complexity of this algorithm is analyzed by a theoretical analysis and software simulations experiment, and the relationship-mapping between the researching key samples space, needed fault number and the length of key segment which is recovered in one time is proposed.

side channel attack; fault analysis; module exponentiation; right-to-left square and multiply algorithm; RSA

1672-1497(2015)01-0081-05

2014- 09- 28

國家自然科學(xué)基金資助項(xiàng)目(61402528)

陳財(cái)森(1983-)，男，助理研究員，博士。

TN918

A

10.3969/j.issn.1672-1497.2015.01.016