陳財(cái)森,蔡紅柳,陳 平,鄧柳于勤,于 茜
(1.裝甲兵工程學(xué)院 科研部,北京100072;2.裝甲兵工程學(xué)院 信息工程系,北京100072;3.裝甲兵工程學(xué)院 基礎(chǔ)部,北京100072)
密碼學(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í)攻擊的措施。
為了便于理解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′。
從旁路安全性分析的角度出發(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]。
為了更好地解釋計(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)形式。
為了更好地解釋計(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í)攻擊。
由于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í)間。
從第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的部分信息
初始集合ε相對(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)整。
從上文我們已經(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í)需要增加填充位。
本文介紹了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.]