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

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

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

0 引 言

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

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

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

1.1 NTRU 算法介紹

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

1.1.1 密鑰產生

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

那么定義如下操作

其中f＊g 中xk系數為

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

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

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

1.1.2 加密操作

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

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

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

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

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

1.1.3 解密操作

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

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

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

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

1.1.4 算法實現原理

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

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

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

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

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

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

2.1 執行時間蹤跡分析

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

定義β（m′，e）∈｛0，1｝，則當構造r（m′，e）時最多調用K 次哈希函數，則設為0，如果調用次數多于K 則為1，可以循環得到（Xim′，Xie），i＝0，1，…。最后給出時間蹤跡的完整定義，它的二進制表示形式如下

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

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

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

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

2.2 基于哈希函數調用數目變化的攻擊算法

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

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

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

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

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

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

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

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

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

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

3.1 高精度計時技術

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

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

3.2 攻擊算法

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

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

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

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

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

（5）查找候選值；

（6）通過結果值m′（ei）重構F。

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

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

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

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

這樣就產生了關于F的部分信息

3.3 密鑰驗證

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

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

4 防御措施

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

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

5 結束語

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

［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 蹤跡驅動指令Cache 計時攻擊研究 ［J］.軟件學報，2013，24 （7）：1683－1694.］