陳財(cái)森，蔡紅柳，陳 平，鄧柳于勤，于 茜

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

0 引 言

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

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

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

1.1 NTRU 算法介紹

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

1.1.1 密鑰產(chǎn)生

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

那么定義如下操作

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

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

同時(shí)定義兩種特殊類型的多項(xiàng)式：

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

1.1.2 加密操作

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

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

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

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

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

1.1.3 解密操作

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

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

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

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

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

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

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

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

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

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

2 針對(duì)一般NTRU 算法的計(jì)時(shí)攻擊算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

因?yàn)樗蠿i為0 或者1，把Xi移到公式的前面得：Xi＊（（f＊emodq）modp）＊（f－1modp），即Xim′（e）。

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

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

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

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

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

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

3.2 攻擊算法

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

（1）首先選擇一個(gè)值δ；

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

（3）重新計(jì)算并保存所有的時(shí)間蹤跡T（m′，e）；

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

（5）查找候選值；

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

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

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

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

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

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

3.3 密鑰驗(yàn)證

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

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

4 防御措施

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

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

5 結(jié)束語(yǔ)

本文介紹了NTRU 公鑰密碼算法加解密的工作原理，分析其算法基于簡(jiǎn)單的多項(xiàng)式乘法運(yùn)算，與其它公鑰密碼算法相比較，具有較高的執(zhí)行效率；同時(shí)對(duì)NTRU 算法的實(shí)現(xiàn)安全性進(jìn)行了分析，指出其存在遭受計(jì)時(shí)分析的安全漏洞，結(jié)合旁路攻擊的基本概念和原理，通過(guò)研究發(fā)現(xiàn)由于算法實(shí)現(xiàn)過(guò)程中由于哈希函數(shù)調(diào)用次數(shù)的不同會(huì)導(dǎo)致時(shí)間差異，給攻擊者提供了攻擊的可能性。分析了NTRU 算法實(shí)現(xiàn)的時(shí)間蹤跡，給出針對(duì)一般NTRU 的計(jì)時(shí)攻擊算法以及針對(duì)具體密鑰形式為f＝1＋2F 的攻擊算法。最后給出兩種抵御計(jì)時(shí)攻擊的措施，主要是基于消除哈希函數(shù)調(diào)用次數(shù)對(duì)輸入值的依賴關(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）.［陳財(cái)森，王韜，郭世澤，等.RSA 蹤跡驅(qū)動(dòng)指令Cache 計(jì)時(shí)攻擊研究 ［J］.軟件學(xué)報(bào)，2013，24 （7）：1683－1694.］