一種對ＩＰＫＣ的ＥＳＡ攻擊及對策
2006-12-31 00:00:00余位馳何大可
計算機應用研究 2006年8期
(1.現代通信國家重點實驗室， 四川 成都 610041; 2.西南交通大學 計算機與通信學院， 四川 成都 610031; 3.西南交通大學 信息安全與國家計算網格實驗室， 四川 成都 610031)
摘 要：首先介紹了PPKC和IPKC的概念，然后對比了幾種典型攻擊方法對PPKC和IPKC安全性的不同影響。利用IPKC的特殊性，提出了一種專門針對IPKC的攻擊方法——錯誤探測攻擊方法(Errors Sniffing Attacks， ESA)；新型公鑰密碼方案NTRU是一種IPKC，因此必須研究其抵抗ESA攻擊的能力；設計了一種利用NTRU解密錯誤發起的ESA攻擊算法，該算法可以推測出私鑰 f 部分甚至全部的信息。最后提出了增強NTRU抵抗ESA攻擊的具體措施。
關鍵詞：公鑰密碼方案; 非完備公鑰密碼方案; 錯誤探測攻擊
中圖法分類號：TP393．08文獻標識碼：A
文章編號：1001-3695(2006)08-0129-04
Challenges and Solutions of ESA on NTRU
YU Wei chi 1，2， HE Da ke 3
(1.National Laboratory for Modern Communications， Chengdu Sichuan 610041， China; 2.School of Computer Communications Engineering， Southwest Jiaotong University， Chengdu Sichuan 610031， China; 3.Information Security National Grid Laboratory， Southwest Jiaotong University， Chengdu Sichuan 610031， China)
Abstract:The conceptions of PPKC and IPKC are introduced in this paper. Secure performances of PPKC and IPKC under different attacks are contrasted. A new type of attacks， Errors Sniffing Attacks(ESA) which work on IPKC only， are presented. Because NTRU is a typical IPKC， its performance of ESA resistance should be studied. Based on NTRU decryption failures， an ESA algorithm can explore partial even whole information of private keyf . In order to keep NTRU away from ESA， some suggestions are given at the end of this paper.
Key words:Public Key Crypto Scheme; Imperfect Public Key Cryptography Scheme(IPKCS); Error Sniffing Attacks(ESA)
1概述
傳統的公鑰密碼，如RSA，ECC等，只要一段明文能夠被正確加密，解密這段密文就一定可以恢復出原來的明文。但是基于格上的新型公鑰密碼方案，如AD[1]，GGH[2]和NTRU[3]，卻有一個共同的特點：即使一段明文能夠被正確加密，但是解密這段密文卻不一定能夠正確恢復出原來的明文。
定義1設 (sk，pk)是公鑰密碼方案“私鑰—公鑰”對，對明文m的加密運算為c=Epk (m)，對密文c的解密運算是Dsk(c)。如果對于任意的明文m都有m=Dsk(Epk(m)) 成立，則這個公鑰密碼方案是完備公鑰密碼方案（Perfect Public Key Cryptosystem，PPKC）；如果存在一些 m，使m≠Dsk(Epk(m))， 則這個公鑰密碼方案是非完備的公鑰密碼方案（Imperfect Public Key Cryptosystem，IPKC）。
目前已知的三個基于格上難題構造的新型公鑰密碼方案AD，GGH和NTRU都是IPKC。IPKC存在解密錯誤的現象并沒有引起這些方案設計者足夠的重視，他們一般為：解密錯誤現象給密碼方案帶來的問題主要是工作效率的問題，只要解密錯誤出現的概率比較小，那么這種小概率的解密失敗僅僅對密碼使用的效率略微有一些影響，對整個系統的安全性沒有任何影響。筆者認為這種觀點值得商榷。
2公鑰密碼典型攻擊方式對PPKC和IPKC不同的影響
一個經過PPKC加密的明文總是可以被正確地解密還原，但是一個經過IPKC加密的明文卻可能無法被正確恢復。實際系統中，為了確保解密者能夠獲得這個明文，IPKC加密方案必須采用一些其他附加的手段，如采用“檢錯—重傳”的協議，一旦發現解密錯誤，解密者就要求加密者選用新的隨機參數對該明文重新加密傳輸。采用“檢錯—重傳”協議雖然可以保證解密者獲得正確的明文，但是也帶來了新的問題：一個主動攻擊者總是可以知道IPKC何時發生了解密錯誤。如果攻擊者能夠準確獲知何時發生了解密錯誤這一信息，那么攻擊者就可以利用這個信息對IPKC系統進行分析，從中獲得系統的秘密信息。因此IPKC必須考慮這種由于解密錯誤導致信息泄露的可能。由于IPKC存在解密錯誤現象，因此抵抗一些典型的公鑰密碼攻擊的能力與PPKC略有差別。下面將討論幾種典型攻擊方式對PPKC與IPKC安全性的影響。選擇明文攻擊和選擇密文攻擊方法可以參考文獻[4]，反應攻擊方法可以參考文獻[5]。受到反應攻擊方法的啟示，結合IPKC的特點提出了解密錯誤探測攻擊方法。
2．1選擇明文攻擊(Chosen Plaintext Attacks，CPA)
所有的公鑰密碼方案都應該能夠有效抵抗選擇明文攻擊。典型的公鑰密碼方案都假定攻擊者擁有加密算法和被攻擊對象的公鑰。攻擊者可以任意加密任何明文來獲得相應的密文，通過觀察“明文—密文”對來推測系統的其他參數和信息。如果攻擊者可以通過這種方法獲得系統其他參數信息，如與公鑰相對應的私鑰信息或者是用于加密的隨機參數信息等，那么攻擊者的選擇明文攻擊就算取得了成功。另外，如果攻擊者可以找到特定密文對應的明文，那么攻擊者的選擇明文攻擊也算是取得了成功。
CPA不需要解密過程的參與。一個IPKC，如果沒有解密的參與，加密者不會知道自己送出的密文是否能夠導致解密錯誤的發生。因此，進行選擇明文攻擊時，IPKC不會比PPKC泄露出更多的信息。IPKC與PPKC抗選擇明文攻擊的能力一致。
2．2選擇密文攻擊(Chosen Cipher Attacks， CCA)
公鑰密碼方案還應該能夠抵抗選擇密文攻擊。假設攻擊者擁有CCA解密隨機預言模型，該模型對輸入的密文解密后返回相應的明文。同時假設該模型不返回攻擊者特定攻擊密文（如攻擊者截獲的某段密文）對應的明文。攻擊者精心設計密文，然后用CCA解密隨機預言模型解密這些密文，獲得相應的明文。攻擊者通過觀察這些“密文—明文”對來推測目標密文對應的明文，或者期待能夠發現系統的其他信息，這就是CCA。不論PPKC還是IPKC，用CCA解密隨機預言模型解密任意構造的密文，得到的結果可能有兩種：①返回一段明文；②返回該密文不能解密，輸出符號⊥。返回一段明文更利于攻擊者獲得更多的信息，因此攻擊者總是希望自己構造的密文能夠通過CCA解密隨機預言模型返回一段明文。
選擇密文攻擊可以分為CCA1和CCA2兩類[4]。一般認為，如果一個公鑰密碼方案在CCA2的攻擊下仍然能夠保證不可區分的安全特性（IND CCA2），則這個公鑰密碼方案就是安全的。但是，絕大多數公鑰密碼的原型都不能抵抗CCA。為了有效增加原型抵抗CCA的能力，一般都要將原型進行改進，最簡單有效的方法就是增加合理的隨機填充（Padding）方案。隨機填充使攻擊者在使用CCA解密隨機預言模型返回一段明文的概率大大降低，因此減少了系統泄漏信息的可能，從而增加了系統抵抗CCA的能力。在IPKC中，由于一個正確的密文也可能無法正確解密，因此CCA的攻擊者選擇的密文不能返回一段明文的概率理論上大于PPKC。因此IPKC抗CCA的能力略強于PPKC。盡管IPKC抗CCA能力略強于PPKC，但沒有填充方案的NTRU原型仍然不能抵抗CCA[6]。
2．3反應攻擊(Reaction Attacks，RA)
嚴格地說，反應攻擊是一種特殊的CCA，并且僅對一些公鑰密碼方案有效，如McEliece，AD，GGH和NTRU等[5，6]。據筆者所知，McEliece密碼方案是目前為止唯一可能受到RA的PPKC，因此本部分所說的PPKC特指McEliece密碼方案。
反應攻擊假設攻擊者擁有一個RA解密隨機預言模型，該模型對輸入的密文只返回兩種結果：①這個密文可以正確解密，輸出Yes；②這個密文不能正確解密，輸出No。在實際的系統中，通過觀察解密者是否發出了要求重新加密的信息，攻擊者可以準確知道自己選擇的密文是否引起了解密錯誤。因此可以認為RA的攻擊者在實際系統中擁有RA解密隨機預言模型。
攻擊者通常從一個可以正確解密的密文出發，把這個密文稍微作一些修改后送給RA解密隨機預言模型，通過觀測返回結果來分析獲得系統的其他信息。從本質上講，反應攻擊也是一種選擇密文攻擊。與普通意義上的選擇密文攻擊不同，攻擊者不需要知道自己構造的攻擊密文所對應的明文，僅僅需要知道攻擊密文是否正確地被解密，因此可以認為RA攻擊者能夠獲得的信息遠遠少于CCA攻擊者。
攻擊者希望從一個正確的密文出發，盡快地找到較多的使解密發生錯誤的不同竄改密文。在IPKC中，由于一個正確的密文也可能無法正確解密，因此IPKC比PPKC更快更多地返回給RA的攻擊者解密錯誤的實例。IPKC發生解密錯誤的概率越高，則IPKC抵抗RA的能力就比PPKC抵抗RA的能力越差。因此存在解密錯誤的NTRU密碼方案抵抗反應攻擊的能力理論上比沒有解密錯誤的McEliece的抵抗能力低。
文獻[6]中分析了反應攻擊對NTRU的影響。如果RA成功，那么可以獲得私鑰 f 系數為“+1”（或者“-1”）的位置信息。但是，文獻中忽略了NTRU是一種IPKC，沒有考慮NTRU本身可能發生解密錯誤的特性對反應攻擊的影響。文獻[6]中攻擊算法的第一步需要獲得一個密文 e ，但是筆者認為還應該再加上一個前提，即“并且這個密文 e 必須能被正確解密”，否則該算法無效。
2．4解密錯誤探測攻擊(Error Sniffing Attacks，ESA)
針對IPKC存在解密錯誤的特殊性現象，本文提出了一類特殊的攻擊方法：解密錯誤探測攻擊。假設攻擊者擁有加密算法和被攻擊對象的公鑰，并且攻擊者擁有一個ESA解密隨機預言模型，該模型的輸入由兩部分構成：①任意一段明文和隨機比特 (m;r) ；② (m;r)加密得到的密文e 。ESA解密隨機預言模型接收 (m;r)和e之后立刻解密e，然后檢測解密密文是否與輸入的明文m 一致。這個模型返回兩種結果：①一致，該明文沒有發現解密錯誤；②不一致，該明文發現了解密錯誤。顯然，如果攻擊的對象是PPKE，那么這種模型返回的結果永遠都是“沒有錯誤”。因此這種攻擊對PPKC無效。
與RA模型相類似，在ESA模型中，攻擊者從ESA解密隨機預言模型中獲得的信息遠遠小于CCA模型中攻擊者能夠得到的信息。與RA模型不同的是，RA是從任意一個正確的密文 e 出發，對這個密文進行微小的修改后，觀測解密是否能夠獲得成功；而ESA卻正好相反，攻擊者從一個正確加密但卻不能被正確解密的 (m;r)出發，對m或者r 進行微小的修改后，觀測新的密文能否被正確解密。RA攻擊者操作的對象是密文，ESA攻擊者操作的對象是明文 m或者隨機比特r 。
利用ESA解密隨機預言模型可以找到導致IPKC解密錯誤發生的明文和隨機比特 (m;r)。采用合適的方法修改(m;r) ，繼續利用ESA解密隨機預言模型觀測解密的結果，根據具體IPKC方案的結構特點，尋找出IPKC系統的私鑰或者其他的秘密信息。由于不同的IPKC導致解密錯誤的原因各不相同，因此ESA具體的分析方法也各不相同。
ESA模型就是要利用IPKC存在解密錯誤這種特殊現象來獲取IPKC的部分或者全部秘密信息。IPKC解密錯誤現象出現越頻繁，那么ESA的攻擊者就越容易獲得解密錯誤的實例，從而越有利于ESA的進行。
目前已知的IPKC方案，如AD，GGH和NTRU，在設計時都忽略了ESA這種利用解密錯誤發動的攻擊。這些IPKC方案的設計者們認為，只要將解密失敗的概率控制在足夠小的范圍，那么這種小概率的解密失敗只是給系統的效率帶來了一些影響，而與系統的安全性沒有關系。本文認為這種觀點值得商榷，一個IPKC密碼系統除了需要考慮其抗CPA，CCA和RA的能力，還必須考慮它抵抗ESA的能力。
3對NTRU的一種解密錯誤探測攻擊
文獻[7]中設計了一種針對NTRU的新型攻擊方法。由于這個攻擊利用NTRU解密錯誤的實例發起，因此是一個解密錯誤探測攻擊。這種攻擊大膽假設：如果解密錯誤發生，那么私鑰 g具有與r互反多項式相似的結構，f與m 互反多項式相似的結構。通過大量的數值計算驗證，這種攻擊方法能夠以一定的概率獲得成功。
筆者從中受到啟發，設計了一種對NTRU更具有一般性的ESA算法。假設攻擊者具有ESA解密隨機預言模型，注意這種假設是有依據的。為了徹底消除解密錯誤對系統的影響，NTRU設計者指出，當解密錯誤發生的時候可以采用兩種方法來糾正：①要求加密者產生新的一個隨機比特然后重新生成密文；②通過所謂的“中心化算法”來糾正解密產生的偏差。通過觀測解密者的響應消息或者響應時間，ESA的攻擊者幾乎總是可以得知自己送出去的密文是否發生了解密錯誤。因此可以認為ESA的攻擊者擁有ESA解密隨機預言模型。對NTRU進行ESA的算法（算法1）如下：
(1)通過ESA解密隨機預言模型窮搜索一個引起解密錯誤的 (m;r) 。
(2)利用ESA解密隨機預言模型檢測 (0;r)是否引起解密錯誤。如果引起了解密錯誤，那么修改r的隨機幾個比特，使得(m;r)引起解密錯誤，但是(0;r) 不引起解密錯誤。
(3) r保持不變，逐比特將m 中的非0比特改成0。每改1比特，就用ESA解密隨機預言模型檢測新的 (m;r)是否引起解密錯誤發生。如果改動后新的(m;r)沒有引起解密錯誤發生，那么恢復剛剛修改的那個比特。如果(m;r)保持引起解密錯誤的發生，那么就保留修改了的新m 。
(4)重復（3）直到任意修改 m一個非0比特，(m;r)都不會引起解密錯誤發生或者m 已經被修改成0。
(5)假設（4）得到的m=(m0，m1，…，mi，…，mN-1)，m+i表示把m的mi修改成“1”，m-i表示把m的mi修改成“-1”，m0i表示把m的mi修改成“0”，j表示某個固定的整數，j∈[1，…，N]，
①如果mi=1，那么fj-1=1。
②如果mi=-1，那么fj-1=-1。
③如果mi=0，
(6)輸出f′=(fi，f2，…，fN)，f′可能就是私鑰f的j 循環移位形式。
現在我們就來解釋一下這種攻擊的工作原理。文獻[8]中指出，解密失敗是由于 a=pr×h×f+m×f=(pr×h+m)f的寬度（多項式a中最大系數于最小系數之差）過大超過q。如果p，r，f和h不變，那么解密錯誤的發生取決于m。具體地說，如果解密錯誤發生，那么m×f中的某一項或者是幾項超大于q/2或者小于-q/2。算法中(3)和(4)將m修改成為剛好不發生解密錯誤的狀態，修改完成后的m存在一些非零項，如果任意繼續修改其中的一個，不防設為mi，都會導致解密錯誤的發生，這意味著多項式卷積m×f將有一項系數大于q/2或者小于-q/2，因此可以斷定fj-i=mi。m中的零項mi如果修改成1后沒有導致解密錯誤發生，則意味著m×f中沒有大于q/2或者小于-q/2的項，那么最有可能的情況就是fj-i=1，同理可以得出算法中fj-i=-1和f j-i=0的結論。最后算法輸出的f′可能就是NTRU私鑰f循環移位j 位后的形式。
4增加NTRU抵抗ESA的能力
盡管目前看來ESA還沒有給NTRU帶來致命的威脅，但是必須重視這種攻擊的潛在危害。ESA算法之所以能夠成功是由于IPKC類密碼方案存在解密失敗這個特點。如果能夠減少這類密碼方案出現解密失敗的概率或者即使發生了錯誤攻擊者也無從獲知，那么IPKC抵抗ESA的能力將會大大增強。基于這種思想，本文認為通過以下的措施可以明顯增加NTRU抵抗ESA的能力：
(1)采用更加合理的參數，使NTRU發生解密錯誤的概率進一步降低。隨著解密錯誤發生概率的進一步降低，算法①將花費更多的時間。如果這個時間同直接窮搜索私鑰f的時間相當，那么算法①也就沒有什么實際意義了。文獻[8]提出了保證NTRU沒有解密錯誤發生的理論界。需要注意的是，選擇安全合理的NTRU參數必須綜合權衡，完全沒有解密錯誤的NTRU可能抵抗其他類型的攻擊卻很弱。
(2)改進解密算法。我們設計了一種補償算法[8]可以完全并且高速地糾正NTRU解密錯誤。由于這種算法以增加存儲空間為代價，保證了解密高速進行；由于采用這種算法使得ESA的攻擊者無法獲知解密錯誤是否發生，因此攻擊者不能獲得ESA解密隨機預言模型。采用補償算法的NTRU可以有效抵抗ESA。
(3)在實際的系統中，限制同一個加密對象的通信次數，特別是限制使用同一對密鑰與同一個對象通信發生錯誤的次數。通過這一措施，將有效地防止攻擊者獲得ESA解密隨機預言模型，達到防止ESA的目的。由于NTRU的密鑰生成算法速度相當快，當解密者發現解密錯誤出現的頻率異常時，可以生成一對新的密鑰對，要求會話更新使用新的密鑰，從而避免了同一對密鑰泄漏過多的解密失敗信息。
5結論
本文比較了公鑰密碼攻擊一般模式對PPKC和IPKC的不同影響，提出了一種專門針對IPKC的新型攻擊方法——錯誤探測攻擊ESA。ESA通過搜尋解密失敗的實例，結合不同IPKC公鑰密碼解密失敗的原因，從中推測系統的秘密信息。本文還設計了一種針對NTRU的ESA算法，該算法可以恢復私鑰 f 的部分或者全部信息。最后針對ESA的特點提出了增加NTRU抵抗ESA的一些具體措施，這些措施略加修改也可以適用于其他的IPKC。
參考文獻：
[1]Miklos Ajtai， Cynthia Dwork. A Public Key Cryptiosystem with Worst Case/Average Case Equivalence[DB/OL]. ftp://ftp.eccc.uni trier.de:/pub/eccc/， 2005-05-01.
[2]O Goldreich， S Goldwasser， S Halevi. Public Key Cryptosystems from Lattice Reductions Problems[DB/OL]. ftp://ftp.eccc.uni trier.de:/pub/eccc/， 2005-05-01.
[3]Jeffrey Hoffstein， Jill Pipher， Joseph H Silverman. NTRU: A Ring based Public Key Cryptosystem[C]. Proc. of ANTS III， Springer Verlag， 1998.267-288.
[4]Wenbo Mao. Modern Cryptography: Theory and Practice[M]. Publishing House of Electronics Industry， 2004.
[5]C Hall， I Goldberg， B Schneier. Reaction Attacks Against Several Public Key Cryptosystems[EB/OL]. http://www.counterpane.com， 2005-05-01.
[6]Jeffrey Hoffstein， Joseph H Silverman. Protecting NTRU Against Chosen Ciphertext and Reaction Attacks[EB/OL]. http://www.ntru.com， 2005-0s5-01.
[7]Nick Howgrave Graham， Phong Q Nguyen，et al.The Impact of Decryption Failures on the Security of NTRU Encryption[C]. Santa Barbara: Advances in Cryptology， Proceedings of the CRYPTO2003， LNCS 2729， Springer Verlag， 2003.226-246.
[8]余位馳，繆祥華，何大可. NTRU譯碼錯誤研究[J]. 鐵道學報， 2005，27(5):61-66.
作者簡介：余位馳(1974-)，男，四川滎經人，博士研究生，主要研究方向為信息安全技術、密碼學等；何大可，男，博導。
注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
