一種側(cè)信道攻擊Rainbow簽名的算法

易海博

(深圳職業(yè)技術(shù)學(xué)院計算機工程學(xué)院 廣東 深圳 518055)

隨著量子計算機的不斷發(fā)展，RSA和ECC等公鑰密碼面臨著潛在威脅。文獻[1]提出的一種在多項式時間內(nèi)解決大整數(shù)因子分解和離散對數(shù)問題的量子算法表明量子計算機有能力破解RSA和ECC等公鑰密碼。但在公鑰密碼中存在少數(shù)幾類密碼算法不能被量子計算機攻破，它們是格密碼(Lattice-based cryptography)、哈希密碼(Hash-based cryptography)、基于編碼的密碼(code-based cryptography)以及多變量密碼(MQ cryptography)[2]，被統(tǒng)稱為后量子密碼(post-quantum cryptography)。

在后量子密碼中，多變量密碼基于的數(shù)學(xué)困難問題是求解一組有限域上的多變量二次(multivariate quadratic, MQ)方程組，它被證明是NP(nondeterministic polynomial)困難問題，并且目前量子計算機并無較好的求解方法。多變量密碼最早起源于20世紀(jì)80年代，第一種多變量密碼算法是MI(Matsumoto Imai)加密算法。在數(shù)字簽名算法方面，UOV(unbalanced oil-vinegar signature)、Rainbow、TTS(Tame transformation signature)等簽名被認(rèn)為是具有代表性的多變量簽名算法[3-5]。

由于UOV、Rainbow、TTS等簽名算法的抗量子計算攻擊能力，它們的軟件和硬件實現(xiàn)成為后量子密碼領(lǐng)域研究的熱點[6-12]。密碼算法的硬件實現(xiàn)可以廣泛運用于芯片領(lǐng)域，它除了要防御數(shù)學(xué)攻擊，還同時需要防御側(cè)信道攻擊。側(cè)信道攻擊基于密碼算法的硬件實現(xiàn)中泄露的信息進行破解，如能量消耗、電磁泄露、時間信息、聲音等。相應(yīng)的，常用的側(cè)信道攻擊方法包括時間攻擊[13]、能量攻擊[14]、電磁攻擊[15]、故障攻擊[16]等。

在側(cè)信道攻擊方法中，故障攻擊的原理是嘗試改變密碼系統(tǒng)運行的環(huán)境，如電壓、時鐘、溫度、光亮等，從而在密碼運算過程中造成故障，觀測相關(guān)變化，以達到破解密鑰的目的。一種常用的故障攻擊方法是對某一個寄存器使用激光束，導(dǎo)致寄存器的部分比特產(chǎn)生翻轉(zhuǎn)，即從0變成1或從1變成0。故障攻擊已經(jīng)成功在攻擊RSA簽名中實施[17]。

能量攻擊是常用的側(cè)信道攻擊方法，基于觀測密碼系統(tǒng)的能量變化而實現(xiàn)攻擊。常用的能量攻擊方法包括簡單能量攻擊SPA(simple power analysis)[18]和差分能量攻擊DPA(differential power analysis)[19]。原始DPA(mono-bit DPA)針對寄存器單個比特進行觀測，被擴展為multi-bit DPA，可以對某個中間運算結(jié)果的一組比特進行觀測[20]。文獻[20]對DPA進行再次擴展，即可以同時觀測多個運算結(jié)果的功耗，這種方法被稱為高階DPA攻擊。DPA攻擊需要基于能量模型實現(xiàn)，如漢明重量模型和漢明距離模型[21]。一般來說，漢明距離模型更適合CMOS(complementary metal oxide semiconductor)密碼系統(tǒng)攻擊。

這些側(cè)信道攻擊方法被證明對不少對稱密碼系統(tǒng)有效，如DES(data encryption standard)、AES(advanced encryption standard)等[22]。但是，在側(cè)信道攻擊研究領(lǐng)域，針對多變量公鑰密碼進行側(cè)信道攻擊的成功例子很少，只有側(cè)信道攻擊方法[23-24]、多變量公鑰密碼的一種故障攻擊方法[25]，且都只關(guān)注攻擊理論的研究和討論，并未涉及多變量密碼的核心結(jié)構(gòu)的攻擊，還需要在真實環(huán)境下進一步論證。分析多變量簽名算法的側(cè)信道安全性對發(fā)現(xiàn)算法的漏洞，提高算法的安全性有重要價值。本文將多變量簽名Rainbow作為目標(biāo)，實施側(cè)信道攻擊。

1 Rainbow簽名硬件實現(xiàn)

在多變量公鑰密碼中，Rainbow簽名是油醋簽名家族的一員，可以被看成多層的UOV簽名。

1.1 Rainbow方案的選擇

在Rainbow的所有安全方案中，本文選取了一種常用的方案Rainbow(10,10,4,3,10)作為硬件實現(xiàn)方案。它的安全級別達到802，在多項式時間內(nèi)無法被數(shù)學(xué)分析攻擊。Rainbow(10,10,4,3,10)由4層油醋結(jié)構(gòu)組成。本文選定的Rainbow簽名方案的參數(shù)如表1所示。簽名生成包括第一次仿射變換、中心映射變換和第二次仿射變換，如圖1所示。

表1 Rainbow簽名方案

假定消息的散列值是 y (y0, y1, … ,y26)，它的長度是27字節(jié)，其中 y0, y1, … ,y26是 G F(28)的元素。而且，簽名是 x (x0, x1, … ,x36)，它的長度是37字節(jié)，其中x0, x1, … ,x36是 G F(28)的元素。

圖1 Rainbow簽名生成過程

為了對消息的散列值 y (y0, y1, … ,y26)簽名，需要進行如下計算：

式中，F(xiàn)是一個中心映射變換；L1和L2是兩個可逆的仿射變換。

首先計算可逆仿射L1的逆變換：是可逆仿射變換的結(jié)果，的長度是27字節(jié)。L1的逆變換的形式為：

式中，A是規(guī)模為27×27的矩陣；b是維度為27的向量，A和b都被當(dāng)作密鑰來運算。

中心映射變換F由27個多變量多次多項式( f0, f1, … , f26)組成，它有如下形式：

中心映射F是4層的油醋結(jié)構(gòu)，由27個多變量多次多項式組成，即 ( f0, f1, … , f26)被分成4層：

fi|i = 0 ,1,… ,9 ，共10個多項式；

fi|i = 1 0,11,12,13，共4個多項式；

fi|i = 1 4,15,16，共3個多項式；

fi|i = 1 7,18,… ,2 6，共10個多項式。

F的27個多變量多次多項式 ( f0,f1, … , f26)的定義為：

式中，Vi是醋變量；Oi是油變量；OiVj是油變量和醋變量的組合；ViVj是醋變量和醋變量的組合；ijα、ijβ、iγ、iδ和η是多變量多次多項式的系數(shù)，被當(dāng)作私鑰使用，η是常數(shù)。

多變量多次多項式包括5項，最高次數(shù)不超過二次，若將醋變量的數(shù)值代入多變量多次多項式，它將變換成關(guān)于油變量的一次多項式。通過4層的多項式系數(shù)求值和求解線性方程組，計算獲得

1.2 Rainbow簽名實現(xiàn)

為了攻擊的普遍性，Rainbow簽名實現(xiàn)基于原始方案，不采用優(yōu)化手段。本文利用狀態(tài)機的方式實現(xiàn)Rainbow簽名設(shè)計，使用硬件描述語言Verilog作為編程語言，Xilinx公司開發(fā)的FPGA(fieldprogrammable gate array)工具ISE(integrated software environment)9.1作為編程工具，實現(xiàn)平臺選取的是Xilinx FPGA。在FPGA測試通過后，將Verilog代碼加載至Synopsis Design Compiler，簽名所需時間為102.8 μs，等效門數(shù)約為15 490。

Rainbow簽名的仿射變換由矩陣向量乘法和向量加法組成，中心映射變換由求解線性方程組和多項式系數(shù)求值組成。

下面是有限域加法、乘法、求逆和高斯消元運算的具體實現(xiàn)細節(jié)。

選擇的有限域是8GF(2)，域的不可約多項式是有限域加法使用8GF(2)的加法運算；有限域乘法使用多項式基的一般乘法。假定a(x)和b(x)是8GF(2)的元素，那么c(x)=(a(x) × b(x) )mod f(x)是兩者的乘積，其中 f(x)是GF(28)的不可約多項式。計算多項式相乘的結(jié)果，即 s0, s1, … ,s14：

模運算為：

c(x)(c7, c6, c5, … ,c0)是a(x)和b(x)的乘積，本文采用了基于費馬小定理的求逆方法，假定β是GF(28)的元素，求逆過程如下：

計算 β2, β4, β8, β16, β32, β64和 β128可以并行進行， β-1是它們的乘積；需要求解4個線性方程組，這些方程組的系數(shù)矩陣的規(guī)模分別是10×10、4×4、3×3和10×10。本文采取有限域的高斯消元法作為求解線性方程組的方法：

在主元所在列選擇一個非零元素作為主元；交換當(dāng)前行與主元所在行的所有的元素，若當(dāng)前行是主元所在行則不交換；對當(dāng)前行所有的元素做歸一操作；對當(dāng)前行下面所有的元素做消元操作；結(jié)束本次迭代，重新選取下一列開始下一輪迭代；直到所有迭代完成，系數(shù)矩陣成為一個等效的上三角矩陣；接著使用回溯替代的方法對增廣矩陣進行替代；完成回溯替代后，增廣矩陣的最右一列(即常數(shù)項組成的向量)是線性方程組的解。

2 Rainbow簽名側(cè)信道攻擊

2.1 總體方案

現(xiàn)有技術(shù)中，較少對Rainbow簽名進行側(cè)信道安全性分析，在一定程度上阻礙了Rainbow簽名的廣泛應(yīng)用。針對Rainbow的側(cè)信道分析可以分為對仿射變換L1、中心映射變換F、仿射變換L2的分析。

仿射變換L1：差分能量分析；中心映射變換F：故障分析結(jié)合差分能量分析；仿射變換L2：差分能量分析。圖2對Rainbow的分析方法基于差分能量分析和故障分析。

圖2 Rainbow分析過程

2.2 分析第一個仿射變換

對于第一個仿射變換，采用差分能量分析。假定y(y0, y1, … ,ym-1)是待簽名的消息，是仿射變換=Ay+b的結(jié)果，A是m×m的矩陣，b是長度為m的向量，A和b是密鑰。以計算 ai′j= aij× yi為例，aij是A第i行第 j列的元素(密鑰)，yi是y第i個元素(消息)，ai′j是有限域乘法結(jié)果，均是有限域GF(2k)的元素。建立基于漢明距離的多比特差分能量分析模型(以下簡稱漢明距離模型)，那么攻擊aij的思路如下：

向量b的攻擊方法也可以采用漢明距離模型，以計算 bi′ =yi′ +bi為例，向量 y ′ 是 y′=Ay的運算結(jié)果，′是 y ′的第i個元素(可以計算得出)，bi是向量b的第i個元素(密鑰)，′是有限域加法結(jié)果。攻擊bi的思路如下：

2.3 分析中心映射變換

對于中心映射變換，建立基于故障分析的模型。假定 x0, x1, … ,xn-1是Rainbow在中心映射變換時需要隨機生成的變量，使用強光或渦流，基于BSR(bit set or reset)方法引入故障，使這些變量固定成預(yù)設(shè)值即這樣，簽名在每次運行時，產(chǎn)生的隨機變量是預(yù)設(shè)值。

對于密鑰 αij和運算Vj′=αijVj， 令D = Vj， R = Vj′， E = αij，通過故障攻擊，將Vj固定為預(yù)設(shè)值，再基于 H (D ⊕R)采用漢明距離模型分析密鑰；

對于密鑰 δi和運算Vj′ = αijVj+ δi， 因 為=αijVj，令 D = Vj′， R = Vj′ ′ ，E= δi， 通 過故障 攻擊，將Vj固定為預(yù)設(shè)值，再基于 H (D ⊕R)采用漢明距離模型分析密鑰；

對于密鑰 βij和運算Vi′=βijVi， 令 D=Vi，R = Vi，′ E = βij，通過故障攻擊，將Vi固定為預(yù)設(shè)值，再基于 H (D ⊕R)采用漢明距離模型分析密鑰；

對于密鑰 γi和運算Vi′=γiVi， 令D = Vi，R= Vi′i′ ，E = γi，通過故障攻擊，將Vi固定為預(yù)設(shè)值，再基于 H (D ⊕R)采用漢明距離模型分析密鑰；

根據(jù)上述分析，中心映射變換通過建立故障分析模型，固定隨機變量，結(jié)合差分能量分析，攻擊獲得全部密鑰。

2.4 分析第二個仿射變換

向量d的攻擊方法也可以采用漢明距離模型，以計算 di′ =xi′ +di為例，向量 x ′是x′=的運算結(jié)果，′是 x ′的第i個元素(可以計算得出)，di是向量d的第i個元素(密鑰)，di′是有限域加法結(jié)果。攻擊di的思路如下：

至此，完成了所有密鑰的分析。

3 實 驗

1) 依據(jù)第2節(jié)描述的Rainbow簽名算法，使用Verilog編程語言實現(xiàn)了簽名電路，通過Xilinx的FPGA EDA工具ISE軟件，下載至Xilinx FPGA開發(fā)板上驗證簽名過程。

2) 在FPGA測試通過后，將Verilog代碼加載至安裝在Redhat操作系統(tǒng)上的Synopsis Design Compiler編譯環(huán)境，編譯運行。

3) 將Synopsis Design Compiler生成的電路文件加載至ModelSim(Mentor的VHDL和Verilog混合評估器)仿真，PrimeTime(Synopsys的電路功耗評估工具)評估功耗。

通過輸入2 000條消息，進行Rainbow簽名，使用ModelSim仿真，通過PrimeTime進行功耗采集，獲得2 000條功耗曲線。然后，基于側(cè)信道攻擊模型，采用計算機集群，建立分布式功耗分析平臺并分析功耗。首先，構(gòu)建4個集合：功耗曲線集合、密鑰運算集合、密鑰時間集合、密鑰猜測值集合。再基于密鑰時間集合將功耗曲線集合中的曲線分成多個時間段，每個時間段應(yīng)包含盡可能少的密鑰運算，每個時間段的曲線各自組成一個集合；基于密鑰運算集合，為每個時間段曲線集合限定參與運算的密鑰；為每個密鑰在密鑰猜測值集合內(nèi)猜測一個的值，基于漢明距離模型分析功耗，若猜測值在最后計算的曲線對應(yīng)位置出現(xiàn)尖峰，則將該值記錄為該密鑰的分析結(jié)果。

圖3 實驗過程

通過以上方法，使用分布式功耗分析平臺分析獲得Rainbow的所有密鑰的分析結(jié)果，經(jīng)過驗證全部正確，證明本文的實驗?zāi)軌蛲耆テ芌ainbow簽名。實驗流程如圖3所示。

4 結(jié) 束 語

本文提出了一種基于差分能量分析和故障分析的側(cè)信道分析算法，將Rainbow作為目標(biāo)，實施側(cè)信道攻擊。故障分析用于固定Rainbow的中心映射變換的隨機變量，結(jié)合差分能量分析可攻擊Rainbow所有的密鑰。實現(xiàn)了Rainbow簽名電路，然后使用Synopsis Prime Time進行功耗采集，對采集的2 000條功耗曲線進行分析和計算，獲取了所有的密鑰。實驗結(jié)果表明了需要對Rainbow進行側(cè)信道攻擊保護。在未來的工作中，將設(shè)計基于掩碼或隱藏的方法對Rainbow進行保護。

本文的研究工作得到了深圳市知識創(chuàng)新計劃基礎(chǔ)研究項目(JCYJ20170306144219159)，深圳市戰(zhàn)略新興和未來產(chǎn)業(yè)發(fā)展資金產(chǎn)業(yè)服務(wù)體系扶持計劃項目(20170502142224600)，深圳職業(yè)技術(shù)學(xué)院校級科研項目(601722K20018)的資助，在此表示感謝！