針對NTRU 公鑰密碼算法的計時分析研究

陳財森，蔡紅柳，陳 平，鄧柳于勤，于 茜

（1.裝甲兵工程學(xué)院 科研部，北京100072；2.裝甲兵工程學(xué)院 信息工程系，北京100072；3.裝甲兵工程學(xué)院 基礎(chǔ)部，北京100072）

0 引 言

密碼學(xué)分析學(xué)家對NTRU［1］提出了各種各樣的攻擊，例如窮舉攻擊、碰撞攻擊、多次傳輸攻擊和基于格攻擊等，但是這些攻擊方式都是試圖從數(shù)學(xué)的角度破解密鑰，實現(xiàn)難度極大甚至不可行。以Kocher為代表的密碼分析學(xué)家提出了一種從密碼實現(xiàn)角度出發(fā)的破解方式，通過獲取密碼加解密執(zhí)行過程中所泄露信息推算出密鑰的攻擊方式，稱之為旁路攻擊［3］，其中泄露的信息包括消耗的時間、功耗、電磁或故障信息等。計時攻擊［4，5］是旁路攻擊的一種，指攻擊者通過測量密碼算法執(zhí)行過程中消耗的時間信息推算出密鑰的一種攻擊方式，由于不需要特殊的設(shè)備且不需與攻擊目標(biāo)接觸，具有操作簡單、可行性高的特點，是目前旁路攻擊研究領(lǐng)域的熱點之一。

本文以NTRU 算法為研究對象，介紹算法實現(xiàn)加解密的原理以及密鑰參數(shù)的選擇，分析算法執(zhí)行的時間蹤跡，對其旁路安全性進(jìn)行分析。研究結(jié)果發(fā)現(xiàn)NTRU 算法實現(xiàn)過程中，基于不同的輸入所調(diào)用哈希函數(shù)的次數(shù)存在差異，這些差異信息會導(dǎo)致執(zhí)行時間的差異，從而存在泄漏密鑰信息的安全威脅。首先給出針對基于哈希函數(shù)調(diào)用數(shù)目變化的計時攻擊算法，然后針對一般NTRU 算法和密鑰形式為f＝1＋2F 的實現(xiàn)算法，分別給出相應(yīng)的計時攻擊算法和驗證算法，最后依據(jù)存在的安全漏洞給出抵御計時攻擊的措施。

1 NTRU 算法及其旁路安全性分析

1.1 NTRU 算法介紹

為了便于理解NTRU 算法的旁路安全性分析，下面簡單介紹算法的密鑰產(chǎn)生、加密操作、解密操作以及算法實現(xiàn)原理。

1.1.1 密鑰產(chǎn)生

與其它公鑰密碼算法不同，NTRU 是基于商環(huán)R ＝Z［X］／（XN－1）上運算的算法。環(huán)R 中的乘法定義為卷積“＊”（convolution multiplication）：設(shè)f，g ∈R。

那么定義如下操作

其中f＊g 中xk系數(shù)為

稱f＊g是模q 的，指f，g 及f＊g中所有單項式系數(shù)均為模q的，即將f，g 及f＊g 視作R ＝Z［X］／（XN－1）的元素?？勺C明當(dāng)q 是素數(shù)時，R 具有可逆性，即對F ∈R，存在F＊∈R 滿足：F＊F＊≡1（modq）。

同時定義兩種特殊類型的多項式：

最后得到NTRU 的私鑰f 和g，而公鑰h計算如下

1.1.2 加密操作

加密使用了兩個哈希函數(shù)，表示為G 和H。實際中依據(jù)要求的安全等級，經(jīng)常以多種方式使用SHA－1 或者SHA－256 （secure hash algorithms）。加密步驟如下［7］：

（1）選擇加密的明文M，將其編碼為βN 形式：M ∈βN ；

（2）利用哈希函數(shù)G 隨機填充M，產(chǎn)生嚴(yán)格符合dr的二元多項式：r＝G（M）∈βN（dr）；

（3）計算m′，表示為：m′＝M ⊕H（r＊hmodq）。

最后獲得密文e：e＝（r＊h＋m′）modq。

1.1.3 解密操作

NTRU 解密操作同樣采用兩個哈希函數(shù)G 和H。具體操作步驟如下：

（1）解密算法首先恢復(fù)m′：m′＝（（f＊emodq）modp）＊modp；

（2）恢復(fù)明文M：M ＝m′⊕H（e－m′modq）；

（3）最后進(jìn)行驗證，一旦計算出M 和m’就可以重新構(gòu)造出盲化值r：r＝G（M），驗證 （m’，e）是否為NTRU加密結(jié)果：e＝（r＊h＋m′）modq。

1.1.4 算法實現(xiàn)原理

為了更好地理解整個算法函數(shù)是如何工作的，本節(jié)介紹解密原理。我們計算的多項式a滿足

由于選擇的多項式p＊r＊g＋f＊m′中f，g，r，m′等系數(shù)的絕對值都很小，所以p＊r＊g＋f＊m′系數(shù)的絕對值相對于q也很小，由于q ≥p，因此可以認(rèn)為p＊r＊g＋f＊m′的系數(shù)已在（1，q）之間，因而有：a ＝p＊r＊g ＋f＊m′。

1.2 NTRU 算法的旁路安全性分析

從旁路安全性分析的角度出發(fā)，簡單分析NTRU 算法執(zhí)行過程可能存在的安全漏洞。由Paul Kocher提出的計時攻擊主要利用密碼設(shè)備運行時的時間特征，推導(dǎo)出私鑰的一種攻擊方式。類似于竊賊通過觀察他人保險柜撥號盤的時間長短來猜測密鑰［3］。

NTRU 算法實現(xiàn)過程中，由于G 函數(shù)調(diào)用SHA 的次數(shù)依賴于G 的輸入，通過測量解密執(zhí)行時間，攻擊者可能觀測到關(guān)于G 函數(shù)的輸入，這樣可獲得關(guān)于私鑰f 的泄露信息。哈希函數(shù)調(diào)用請求由信息／密文對 （m′，e）創(chuàng)建的隨機值r的次數(shù)對于不同的信息對可能不同。每一次哈希函數(shù)調(diào)用需要的總時間也不一樣，因此攻擊者可嘗試檢測出解密密文e時調(diào)用多少次哈希函數(shù)，這樣給攻擊者創(chuàng)造了破解私鑰的機會［6，7］。

2 針對一般NTRU 算法的計時攻擊算法

2.1 執(zhí)行時間蹤跡分析

為了更好地解釋計時攻擊，定義了一個時間蹤跡的概念。第1.2節(jié)中調(diào)用的隨機值r，每次構(gòu)造它都需要使用哈希調(diào)用信息對 （m′，e），針對不同的信息對調(diào)用的次數(shù)不同，因此哈希調(diào)用的時間存在差異。依據(jù)這一點差異，攻擊者可能通過檢測時間差異判斷解密密文e過程中調(diào)用哈希函數(shù)的次數(shù)。實際上，存在一個數(shù)K，計算r時調(diào)用哈希函數(shù)的次數(shù)不是K 就是K＋1［6］。同時根據(jù)解密算法，定義對于每一個信息對 （m′，e）的輸出為

定義β（m′，e）∈｛0，1｝，則當(dāng)構(gòu)造r（m′，e）時最多調(diào)用K 次哈希函數(shù)，則設(shè)為0，如果調(diào)用次數(shù)多于K 則為1，可以循環(huán)得到（Xim′，Xie），i＝0，1，…。最后給出時間蹤跡的完整定義，它的二進(jìn)制表示形式如下

時間蹤跡表示對于每一個信息對 （m′，e）所請求的哈希調(diào)用次數(shù)，依據(jù)這一點，我們可以得知兩對信息對具有相同時間蹤跡的概率和分別調(diào)用哈希函數(shù)的次數(shù)。設(shè)P表示對于一個隨機信息對 （m1’，e1）最多請求K 次哈希調(diào)用的概率，則1－P 表示其它隨機信息對 （m2’，e2）最少請求K＋1次哈希函數(shù)調(diào)用的概率。如果P值足夠大，那么兩個信息對具有相同的時間蹤跡的概率相當(dāng)小。更準(zhǔn)確的描述如下

式 （1）推導(dǎo)過程為：已經(jīng)知道時間蹤跡的二進(jìn)制表示長度為N。假設(shè)P是第i個位置為0概率，1－P為第i個位置為1的概率。那么對于兩個隨機的時間蹤跡第一個位置為相同值的概率為

如果兩個時間蹤跡是完全一樣的話，那么它們所有位置的值都是一樣的 （0或者1）。因此我們有

時間蹤跡是針對NTRU 算法計時攻擊時密鑰的一樣表現(xiàn)形式。

2.2 基于哈希函數(shù)調(diào)用數(shù)目變化的攻擊算法

為了更好地解釋計時攻擊原理，假設(shè)兩個角色A 和B，他們之間相互交換信息，直到其中一個人決定扮演攻擊者嘗試獲取另外一個人的私鑰，這些都是通過計時攻擊方式實現(xiàn)的。假設(shè)B 為攻擊者，他先選擇一個密文集合ε，表示為一個多項式mod q的集合。同時選擇一序列代表性信息M，M 包含大多數(shù)A 構(gòu)造的信息，即有如下方式

此外假設(shè)A 構(gòu)造的信息中包含在集合M 中的概率非常大。在開始執(zhí)行攻擊的有效部分之前，B 對于每一個信息對 （M，ε）構(gòu)造對應(yīng)的時間蹤跡表。換句話說，他構(gòu)造了一個可查找的二進(jìn)制表

攻擊從B向A 發(fā)送一些隨機的e∈ε開始。一旦密文被發(fā)送，B就開始測量A 解密它的時間。主要的思想是攻擊者不需要關(guān)注他偽造的密文是否在不合格檢測之后被拒絕。他唯一要做的事情就是檢測時間信息。通過這些時間信息，攻擊者能夠推測哈希函數(shù)調(diào)用的次數(shù)。換句話說，他便得知形 式 如 下 的 值m′：｛（（f＊emodq）modp）＊（f－1modp）：e∈ε｝，其中 （p＝2）。

攻擊者不知道m(xù)′（e）的值，只知道β（m′（e），e）的值，用來對比從A 獲取的觀測值與B先前構(gòu)造的存儲在表中的值。為此B在時間蹤跡表中需要N－1 個項。其它值在發(fā)送如下的多項式之后獲得

每一個密文發(fā)送之后攻擊者獲得β（m′（Xie），Xie）的值，for i＝0，1，2，…，N－1。

隨機選取一項m′（Xie），由于得知m′（e）是均等的，給出m′（Xie）的適合表達(dá)式

因為所有Xi為0 或者1，把Xi移到公式的前面得：Xi＊（（f＊emodq）modp）＊（f－1modp），即Xim′（e）。

B 現(xiàn)在擁有（m′（e），e）的時間蹤跡T（m′（e），e）。下一步要做的工作就是在先前構(gòu)造的列表中尋找與之匹配概率較大的項。B 獲取兩個多項式e m′和A 解密e時獲得第二個 多 項 式 m′。這 里 攻 擊 者 只 需 要 計 算 m′＊f ≡（f＊emodq）modp，其中e和m′是已知的。

攻擊者如何獲取A 的密鑰：私鑰f 將依賴于e的特殊形式，例如，如果ε 得元素只是包含非常少的非零系數(shù)，那么等式m′＊f ≡（f＊emodq）modp 可能給出涉及f 系數(shù)與非零系數(shù)之間間隔的信息。接下來描述一個特殊集合ε，當(dāng)密鑰f形式為f ＝1＋2F 時，將導(dǎo)致實際的哈希函數(shù)計時攻擊。

3 針對密鑰形式為f＝1＋2F 的攻擊算法

3.1 高精度計時技術(shù)

由于NTRU 算法執(zhí)行速度快，運行時所需要的時鐘周期數(shù)小，因此其它噪聲對其真實執(zhí)行時間的影響系數(shù)大，需要精度高的測量技術(shù)。系統(tǒng)定時器 （包括讀取測量值所需要的時間在內(nèi)）提供大約5 ms的精度，這對應(yīng)500 Hz系統(tǒng)的2000多個脈沖。在高精度測量時，系統(tǒng)定時器是不適合的，這里需要用到Pentium 系統(tǒng)的處理器具有的時間戳計數(shù)器，執(zhí)行RDSTC 指令，通過測量CPU 的時間周期來表示執(zhí)行時間［9］。由于系統(tǒng)運行存在系統(tǒng)本身以及其它進(jìn)程的干擾，影響測量執(zhí)行時間的精確度，可以采用多次測量取平均值的方法。

另外為了克服二度運行的問題，能夠得到精確的測量結(jié)果，需要多次測量執(zhí)行時間。需要注意一點，每次運行必須是在相近的條件與相近的環(huán)境下執(zhí)行的。但是這些條件和環(huán)境在現(xiàn)實中是無法滿足的。磁盤高速緩存、CPU 的Cache、轉(zhuǎn)換后被緩沖區(qū) （TLB）與分支變化使得時間的測量復(fù)雜化，因為程序的重復(fù)運行極大地降低了運行時間。由于訪問Cache時，會發(fā)生命中和失效兩種情況，其中前者的訪問時間會比后者的訪問時間短，盡管時間差異不多，但是對于需要精確測量執(zhí)行時間時，這仍然是不可忽略的。TLB同樣類似的問題。最終我們利用文獻(xiàn) ［10］的建議，對多次測量的樣本量進(jìn)行排序，再取中間的1／3值的平均值，作為算法的執(zhí)行時間。

3.2 攻擊算法

從第1節(jié)中我們已經(jīng)了解到在大多數(shù)情況下，參數(shù)p的值為2，這意味著q是奇數(shù)，也就是說私鑰f具有如下的形式［8］：f＝1＋2F，對于一些二進(jìn)制多項式F∈βN（dF）。

（1）首先選擇一個值δ；

（2）設(shè)ε＝｛ei＝λ＋λXi：1≤i≤（N－1／2）｝且M ＝βN（0＜d ≤δ）；

（3）重新計算并保存所有的時間蹤跡T（m′，e）；

（4）向A 發(fā)送Xjei，j＝0，1，…，N－1，并計算解密時間，確定時間蹤跡T（m′（ei），ei）；

（5）查找候選值；

（6）通過結(jié)果值m′（ei）重構(gòu)F。

我們還要從步驟 （2）找出m′（e）的可能值，因此分析A 的 解 密 過 程，得 知A 首 先 計 算［6］

因此對于a的第j個系數(shù)具有如下的形式

在執(zhí)行a mod 2之后我們獲得0或1的值，由于λ和q都是奇數(shù)，在約簡步驟之后我們得到

那么可以更明確地定義m′（ei）為

這樣就產(chǎn)生了關(guān)于F的部分信息

3.3 密鑰驗證

初始集合ε相對小的話可以減少重復(fù)計算。確認(rèn)一個時間蹤跡與攻擊者數(shù)據(jù)庫中的ei是高概率匹配的。但是如果發(fā)現(xiàn)時間蹤跡是唯一的，那么B 可能需要檢驗它實際上已經(jīng)確認(rèn)的正確的ei。為此我們注意到如果把ei＝λ＋λXi解密為m′，那么設(shè)變換的形式為＝（λ＋2）＋λXi，or λ＋λXi，or…。

或者確實有許多多項式λ1＋λ2Xi，系數(shù)為λ1和λ2甚至整數(shù)接近于q／4并且滿足λ1＋λ2＞q／2。B因此選擇其中一個可能的，計算解密原始ei獲得m′相應(yīng)的時間蹤跡T（m′，），然后重新提交重新計算時間蹤跡。如果測量的結(jié)果和計算的時間蹤跡匹配的話，那么他已經(jīng)確認(rèn)猜測m′。否則的話需要對做進(jìn)一步的調(diào)整。

4 防御措施

從上文我們已經(jīng)了解計時攻擊是如何泄露NTRU 算法的私鑰信息的，同時也知道這種攻擊方式是基于對于不同的密文，可能需要調(diào)用不同次數(shù)的哈希函數(shù)的事實。盡管我們已經(jīng)給出針對形式為f＝1＋2F的私鑰的攻擊算法，理論上可以假設(shè)對于大多數(shù)的密鑰存在類似的攻擊方式。

在掌握NTRU 實現(xiàn)算法計時攻擊漏洞的基礎(chǔ)上，給出相應(yīng)的防御措施。攻擊的漏洞是基于不同的密文解密時調(diào)用哈希函數(shù)的次數(shù)不一樣。這里可以假設(shè)哈希函數(shù)調(diào)用的最大次數(shù)為Kmax，這種情況下一個隨機密文需要少于Kmax次哈希調(diào)用，設(shè)為k次，使其再執(zhí)行Kmax－k額外哈希函數(shù)調(diào)用。這種方式使得對于所有的密文調(diào)用哈希函數(shù)的次數(shù)一樣，從而可以避免此類攻擊。不過此種方式會降低算法的執(zhí)行效率。另外一種方式是填充操作，將填充系數(shù)與哈希函數(shù)調(diào)用次數(shù)相混合，使其填充的每個位影響哈希調(diào)用次數(shù)的每個位。因為填充必須仔細(xì)考慮并顧及安全級別，例如有80位填充80位的安全，因此增加安全級別同時需要增加填充位。

5 結(jié)束語

本文介紹了NTRU 公鑰密碼算法加解密的工作原理，分析其算法基于簡單的多項式乘法運算，與其它公鑰密碼算法相比較，具有較高的執(zhí)行效率；同時對NTRU 算法的實現(xiàn)安全性進(jìn)行了分析，指出其存在遭受計時分析的安全漏洞，結(jié)合旁路攻擊的基本概念和原理，通過研究發(fā)現(xiàn)由于算法實現(xiàn)過程中由于哈希函數(shù)調(diào)用次數(shù)的不同會導(dǎo)致時間差異，給攻擊者提供了攻擊的可能性。分析了NTRU 算法實現(xiàn)的時間蹤跡，給出針對一般NTRU 的計時攻擊算法以及針對具體密鑰形式為f＝1＋2F 的攻擊算法。最后給出兩種抵御計時攻擊的措施，主要是基于消除哈希函數(shù)調(diào)用次數(shù)對輸入值的依賴關(guān)系。

［1］Hermans J，Vercauteren F，Preneel B.Speed records for NTRU ［M］.Berlin：Springer Berlin Heidelberg，2010：73－88.

［2］Li J，Pan Y，Liu M，et al.An efficient broadcast attack against NTRU ［C］／／Proceedings of the 7th ACM Symposium on Information，Computer and Communications Security，2012：22－23.

［3］Venkateswarlu S，Teja G S，Deepa G M，et al.Breaking cryptosystem’s through cache based timing side channel attack［J］.International Journal of Dvanced Research in Computer Science and Software Engineering，2013，3 （5）：82－86.

［4］Chen C S，Wang T，Tian J J.Improving timing attack on RSA－CRT via error detection and correction strategy ［J］.In－formation Sciences，2013，232：464－474.

［5］Chen C S，Wang T，Kou Y Z，et al.Improvement of tracedriven I－cache timing attack on the RSA algorithm ［J］.Journal of Systems and Software，2013，86 （1）：100－107.

［6］Kamal A A，Youssef A M.A scan－based side channel attack on the NTRU encrypt cryptosystem ［C］／／Seventh International Conference on Toulouse：Reliability and Security.IEEE，2012：402－409.

［7］Zheng X，Wang A，Wei W.First－order collision attack on protected NTRU cryptosystem ［J］.Microprocessors and Microsystems，2013，37 （6）：601－609.

［8］Lei X，Liao X.NTRU－KE：A lattice－based public key exchange protocol ［J］.IACR Cryptology ePrint Archive，2013：718.

［9］Demme J，Martin R，Waksman A，et al.Side－channel vulnerability factor：A metric for measuring information leakage［J］.ACM SIGARCH Computer Architecture News，2012，40（3）：106－117.

［10］CHEN Caisen，WANG Tao，GUO Shize，et al.Research on trace drive instruction cache timing attack on RSA ［J］.Journal of Software，2013，24 （7）：1683－1694 （in Chinese）.［陳財森，王韜，郭世澤，等.RSA 蹤跡驅(qū)動指令Cache 計時攻擊研究 ［J］.軟件學(xué)報，2013，24 （7）：1683－1694.］