康步榮,張 磊,張 蕊,孟欣宇,陳 桐

1(軟硬件協(xié)同設計技術與應用教育部工程研究中心(華東師范大學),上海 2000 62)

2(華東師范大學 軟件工程學院,上海 20006 2)

3(密碼科學技術國家重點實驗室,北京 100 878)

迄今為止,大多數(shù)密碼原語的安全性都依賴于高質量的不可預測的隨機數(shù)[1?4].密碼學中,我們通常用偽隨機數(shù)生成器(pseudorandom nu mber generator,簡稱PRNG)來生成隨機數(shù).而實際上,很多人為因素會導致PRNG生成的隨機數(shù)不安全[1?3,5].通常,我們稱不安全的PRNG 為存在后門的PRNG(backdoored pseudorandom number generator,簡稱BPRNG).在信息安全領域,后門是指可以繞過安全控制而獲取對程序或系統(tǒng)訪問權的方法.后門的最主要目的就是方便以后再次秘密進入或者控制系統(tǒng).此處,我們所研究的后門主要是指存在于密碼組件PRNG 里的后門,這種后門使得PRNG 產(chǎn)生的用于密碼算法中的隨機數(shù),對于那些已知此后門的人來說是可預測的.知道后門的攻擊者因可預測隨機數(shù),他很可能會成功破解相應的密碼算法,這將嚴重地威脅到密碼算法的安全性.正如在2014年SXSW 大會(South B y Southwest Con ference)上斯諾登所言,攻擊者在攻擊加密算法時,真正受到攻擊的其實是加密算法中使用的PRNG,而非算法本身.所以,研究抵抗隨機數(shù)后門攻擊的密碼算法是非常有意義且有必要的.

說起對密碼算法的威脅,量子計算機也是其中之一.近年來,量子信息科學的研究和發(fā)展催生了量子計算機[6],而量子計算機的強大計算能力對傳統(tǒng)密碼算法,尤其是對公鑰密碼算法產(chǎn)生了嚴重威脅[6].例如,Shor 算法就是一個分解大整數(shù)問題和求解離散對數(shù)問題的有效量子算法[6,7].Shor 算法的出現(xiàn),嚴重威脅了基于大整數(shù)分解困難問題和離散對數(shù)困難問題的公鑰密碼算法,如RSA,ECC,ElGamal 算法等.文獻[6]總結了現(xiàn)有的量子算法及其對傳統(tǒng)公鑰密碼算法的威脅,并梳理了量子計算機在物理實現(xiàn)上的發(fā)展歷史及相應成果.到目前為止,雖然國際上很多著名的公司都紛紛加入量子計算機的研制之中,但距離通用的量子計算機的大規(guī)模使用還需要很長時間.因此,在量子計算機真正取代傳統(tǒng)計算機之前,隨機數(shù)后門攻擊成為威脅現(xiàn)有密碼算法的主要因素.研究抗隨機數(shù)后門攻擊的密碼算法是亟待解決的問題.

據(jù)統(tǒng)計,目前主要有兩類影響PRNG 工作過程的因素[1,2,5,8?10].

?第1 類影響因素是“漏洞”.例如,2006年9月~2008年5月發(fā)生在Debian Linux 操作系統(tǒng)上的安全漏洞,一名程序員刪除了OpenSSL 密碼庫里的部分代碼,導致該系統(tǒng)中PRNG 的種子密鑰僅剩15 位熵[11].信息論中,熵用來表示一個數(shù)的不確定性,熵越大,數(shù)的不確定性越高.隨后,傳輸層協(xié)議(transport layer security,簡稱TLS)和安全套接字層協(xié)議(secure sockets layer,簡稱SSL)被曝出其服務器的重要組件使用了有后門的PRNG 而使協(xié)議存在安全漏洞[12];

?第2 類影響因素被稱為“惡意顛覆”,其目的是減弱PRNG 生成隨機數(shù)的隨機性.一個典型的例子是雙橢圓曲線偽隨機數(shù)生成器Dual EC PRNG,Dual EC PRNG 是NSA 設計的一個偽隨機數(shù)生成器算法,由NIST 列入算法標準[1,2,5,8?10,13,14].此后,Dual EC P RNG 一直被廣泛使用,直至2014年,該算法被曝出存在后門,即生成的隨機數(shù)可預測[15].在實際應用中,Dual E C P RNG 被著名網(wǎng)絡公司Juniper N etwork 應用于其所生產(chǎn)的NetScreen VP N 路由器的操作系統(tǒng)中.在文獻[16]中,作者詳細分析了NetScreen VPN路由器所存在的該隨機數(shù)后門攻擊.

1 抗隨機數(shù)后門攻擊的對稱加密算法

對于加密算法,我們通常要求其能達到CPA(chosen plaintext attacks)安全性.然而,經(jīng)典的對稱加密算法(如AES,DES)未考慮該安全性.究其原因,這些算法為確定性加密算法.要實現(xiàn)CPA 安全性,加密算法必須為概率性算法,即算法中需引入隨機數(shù)(如加密模式中使用的初始化向量IV、消息填充等).然而,若在算法實現(xiàn)時使用存在后門的PRNG,則該加密算法將仍然無法達到CPA 安全.本節(jié)介紹抗隨機數(shù)后門的對稱加密算法.

1.1 Kamara-Katz系列對稱加密算法

1.2 需要進一步研究的問題

到目前為止,關于抗隨機數(shù)后門攻擊的對稱加密算法的研究成果并不多,較為有效的算法僅有Kamara-Katz 系列對稱加密算法SKE1,SKE2.但是我們不難發(fā)現(xiàn),該算法的構造依賴于很強的假設條件.因為在算法實現(xiàn)過程中,很難保證所用的P函數(shù)和F函數(shù)是真正偽隨機的,所以除了偽隨機函數(shù)和偽隨機置換之外,還可以用哪些數(shù)學工具和密碼原語來構造抗后門攻擊的對稱密碼算法,是一個需要研究的問題.另外,Kamara-Katz 系列對稱加密算法相當于重新構造了一個對稱加密算法,而不是在現(xiàn)有對稱加密算法基礎上構造.如何構造實用的抗隨機數(shù)后門攻擊的對稱加密算法,即簡單改變現(xiàn)有密碼庫(如OpenSSL 庫)的使用方式即可實現(xiàn)抗后門攻擊,也是此研究領域的另一重要的有待解決的問題.這將大大減少密碼庫開發(fā)者的工作量,節(jié)省開發(fā)成本.

2 對沖公鑰加密算法H-PKE

對沖公鑰加密算法最早由Bellare 等人在2009年亞密會(ASIACRYPT)上提出[18].所謂對沖是指密碼算法滿足兩個層次的安全性.

?第1 層安全性是指在加密算法中所用隨機數(shù)是可靠的、高熵的情況下,算法可達到標準安全性(如IND-CPA,IND-CCA);

?第2 層安全性是指在加密算法中所用隨機數(shù)是不可靠的、低熵的情況下,算法依然可以滿足某些比標準安全性稍弱的安全性,而不是直接被攻破[2,3,18].

當對沖公開密鑰加密算法同時滿足上述兩個層次的安全性時,才說它是對沖安全的.對沖加密算法要求被加密的消息和加密時所用隨機數(shù)的聯(lián)合分布具有高熵.現(xiàn)有的對沖加密算法可以概括為3 類,即確定性公鑰加密(deterministic public-key e ncryption,簡稱 D-PKE)[2,18?20]、隨機再確定性公鑰加密算法(randomized-thendeterministic,簡稱RtD)[2,18]、填充再確定性公鑰加密(pad-then- deterministic,簡稱PtD)[2,18].本節(jié)討論對沖公鑰加密的含義和安全性概念,然后分別從上述3 個方面對現(xiàn)有方案進行總結和分析.

2.1 D-PKE算法

確定性公鑰加密算法最早是由Bellare 等人在2007年美密會(CRYPTO)上提出來的密碼學原語[19].在文獻[18]中,作者指出,確定性加密算法是構造對沖加密算法的一種方法.所謂確定性加密,本質上是指在算法設計中不使用隨機數(shù).他們指出,設計確定性公鑰加密算法存在兩個問題.

?首先,如果一個敵手得知該算法的明文消息是從一個小的明文空間中選取的,那么他可以很容易用窮舉法恢復出明文.為解決這個問題,他們要求算法的明文空間足夠大,并且具有高的最小熵;

?其次,因為在確定性公鑰加密算中不使用隨機數(shù),所以加密算法輸出的密文在某種程度上暴露了明文的部分信息.該問題的解決辦法是要求明文不依賴于公鑰,即明文和公鑰是相互獨立的.

文獻[19]中提出了兩個在隨機預言模型下的確定性公鑰加密算法實例:EwH 算法(encrypt-with-Hash,簡稱EwH)和RSA-DOAEP 算法(RSA-deterministic optimal asymmetric encryption padding,簡稱RSA-DOAEP).下面我們將對EwH 算法和RSA-DOAEP 算法分別進行討論.簡單來說,EwH 算法是先對用戶的公鑰、明文消息做一次Hash 操作,將Hash 值作為一個安全公鑰加密算法的隨機數(shù),并利用該公鑰加密算法生成最終密文.下面我們給出具體的EwH 加密算法.為方便描述,我們將EwH 算法記為EwH=(EwH.K,EwH.E,EwH.D),將任一安全公鑰密碼算法記為PKE=(PKE.K,PKE.E,PKE.D),哈希函數(shù)記為H:{0,1}*×{0,1}*→{0,1}*.

?密鑰生成算法EwH.K(1k):輸入安全參數(shù)k,該算法運行算法PKE.K(1k)→(pk,sk),輸出公私鑰對(pk,sk);

?加密算法EwH.E(pk,x):輸入公鑰pk和要加密的消息x,先計算H(pk,x)→R,再運行算法PKE.E(pk,x,R)→y,輸出密文y;

?解密算法EwH.D(y,pk,sk):輸入私鑰sk、公鑰pk和密文y,先計算PKE.D(sk,y)→x,H(pk,x)→R,再判斷等式PKE.E(pk,x,R)=y是否成立:若成立,輸出x;否則,輸出⊥.

在文獻[19]中,Bellare 等人也同時分析了確定性公鑰加密算法的安全性,給出了PRIV(privacy,簡稱PRIV)安全性的定義.PRIV 安全性要求一個攻擊者,已知一個明文向量所對應的確定性加密算法的密文,只要這個明文向量的每個分量有高的最小熵,則該攻擊者不能在多項式時間內(nèi)以不可忽略的概率猜出任何關于原明文的部分信息(部分信息不依賴于加密時所用的公鑰).證明結果表明:如果公鑰加密算法PKE=(PKE.K,PKE.E,PKE.D)是IND-CPA 安全的,則上述EwH 確定性加密算法滿足PRIV 安全性.

證明結果表明,上述確定性加密算法RSA-DOAEP 是PRIV 安全性.

關于確定性加密算法的研究還有一些其他的研究結果,例如在文獻[20]中,Boldyreva 等人在文獻[19]的基礎上繼續(xù)研究了確定性公鑰加密算法的設計及安全性定義,他們發(fā)現(xiàn)了確定性公鑰加密和有損限門函數(shù)之間的聯(lián)系.他們利用有損限門函數(shù),給出了在標準模型下滿足PRIV-CPA 安全性(即,在PRIV 安全性的基礎上允許攻擊者進行加密預言機詢問)的確定性公鑰加密算法的一般性構造思想.為了更好地描述該算法,他們提出了一個新的密碼原語,隱藏全域哈希模式的確定性公鑰加密算法(deterministic encryption with hidden universal-Hash mode,簡稱DEHUHM);其次,他們將該PRIV-CPA 安全的算法構造進行了擴展,給出了PRIV-CCA 安全的確定性加密算法的一般性構造.另外,文獻中還基于抗目標碰撞哈希函數(shù)、DDH 困難問題給出了兩個具體的確定性加密算法實例.

2.2 RtD算法

Bellare 等人在文獻[18]中介紹了對沖公鑰密碼算法RtD,RtD 基本思想是:對消息m先用一個概率性加密算法進行加密,輸出密文C′,再用一個確定性加密算法對C′進行加密,輸出最終密文C.同時,他們定義了一個新的對沖公鑰加密算法的安全性質,即選擇分布攻擊下的不可區(qū)分性(indistinguishability under c hosen-distribution attacks,簡稱IND-CDA).在被加密的明文消息和相應隨機數(shù)的聯(lián)合分布是高熵的條件下,一個對沖公鑰加密算法才能滿足IND-CDA 安全性.Bellare 等人表示:IND-CDA 安全性本質上是對PRIV 安全性的一種變形,兩者的關系是適應性IND-CDA 安全性比PRIV 安全性強,而非適應性IND-CDA 安全性等價于PRIV 安全性.下面給出具體的RtD=(RtD.P,RtD.K,RtD.E,RtD.D)構造.為方便起見,我們將隨機性公鑰密碼算法記為RPKE=(RPKE.P,RPKE.K,RPKE.E,RPKE.D),將確定性公鑰密碼算法記為DPKE=(DPKE.P,DPKE.K,DPKE.E,DPKE.D).

?參數(shù)生成算法RtD.P(1k):輸入安全參數(shù)k,先運行算法RPKE.P(1k)→Parr,得到隨機性公鑰密碼算法RPKE 的系統(tǒng)參數(shù)Parr;再運行算法DPKE.P(1k)→Pard,得到確定性公鑰密碼算法DPKE 的系統(tǒng)參數(shù)Pard,輸出(Parr,Pard);

?密鑰生成算法RtD.K(1k):輸入安全參數(shù)k,運行算法RPKE.K(Parr)→(pkr,skr)和DPKE.K(Pard)→(pkd,skd),輸入算法的公私鑰對(pk=(pkr,pkd),sk=(skr,skd));

?加密算法RtD.E((pkr,pkd),m,r):輸入公鑰pk=(pkr,pkd)、被加密消息m和一個隨機數(shù)r,先計算RPKE.E(pkr,m,r)→c,再計算DPKE.E(pkd,c||10l)→C,輸出密文C.其中,l=nd?|c|?1,nd表示DPKE 算法的明文長度,0l表示有l(wèi)個0;

?解密算法RtD.D(C,(skr,skd)):輸入私鑰sk=(skr,skd)和密文C,計算DPKE.D(skd,C)→c,RPKE.D(skr,c)→m,輸出m.

證明結果表明:若公鑰加密算法RPKE=(RPKE.P,RPKE.K,RPKE.E,RPKE.D)是IND-CPA 安全的,則上述RtD構造滿足IND-CDA 安全性.

2.3 PtD算法

PtD 也是Bellare 等人在文獻[18]中提出的一種構造對沖公鑰加密算法的方法.所謂的PtD 加密是指先對消息m進行填充,輸出m′,再用一個確定性加密算法對m′進行加密,輸出最終的密文C.下面介紹具體的PtD=(PtD.P,PtD.K,PtD.E,PtD.D)加密算法,我們將確定性公鑰密碼算法記為:DPKE=(DPKE.P,DPKE.K,DPKE.E,DPKE.D).

?參數(shù)生成算法PtD.P(1k):輸入安全參數(shù)k,運行確定性加密算法的參數(shù)生成算法DPKE.P(1k)→Pard,輸出確定性公鑰加密算法的系統(tǒng)參數(shù)Pard;

?密鑰生成算法PtD.K(Pard):輸入系統(tǒng)參數(shù)Pard,運行確定性公鑰加密算法的密鑰生成算法DPKE.K(Pard)→(pkd,skd),輸出公私鑰對(pkd,skd);

?加密算法PtD.E(pkd,m,r):輸入系統(tǒng)參數(shù)Pard、隨機數(shù)r、明文m,運行確定性公鑰加密算法DPKE.E(pkd,r||m)→C,輸出密文C;

?解密算法PtD.D(C,skd):輸入密文C,私鑰skd,運行解密算法DPKE.D(skd,C)→m,輸出消息m.

證明結果表明,上述對沖加密算法PtD=(PtD.P,PtD.K,PtD.E,PtD.D)滿足IND-CDA 安全性.

在2017年的美密會上,Boldyreva 等人從實際出發(fā),研究了在密碼庫OpenSSL 中可實現(xiàn)的對沖加密算法以及對沖加密算法的安全性質[2].他們定義了兩個新的對沖安全性質,即 MM-CCA(message-message s ecurity against ch osen c iphertext a ttack)和MMR-CCA(message-message-randomness security against chos en ciphertex t attack).作者指出,第2.2 節(jié)、第2.3 節(jié)中所述的IND-CDA 安全性等價于MMR-CPA 安全性(message-messagerandomness security against chosen plaintext attack).文獻[18]的研究結果已經(jīng)表明:RtD算法和PtD算法在滿足一定約束條件時可達到IND-CDA 安全性,即MMR-CPA 安全性.所以在文獻[2]中,Boldyreva 等人將該結果進行擴展,研究了RtD 算法和PtD 算法相應的CCA 安全性.證明結果表明,對于RtD 算法,當確定性算法選用RSA-DOAEP 時,算法可達到MM-CPA 和IND-CPA 安全;當概率性算法選用關聯(lián)數(shù)據(jù)的單射加密算法,則算法可達到MMR-CCA 和IND-CCA 安全性.而對于PtD 算法,當確定性算法選用RSA-DOAEP 時,算法可滿足MM-CCA 和IND-CCA 安全性.同時,文獻[2]中的作者還基于關聯(lián)數(shù)據(jù)的可驗證加密算法和陷門置換函數(shù)構造了一個混合加密算法,并給出安全性分析.結果表明,該混合加密算法可滿足MMR-CCA 和IND-CCA 安全性.他們的另一研究結果表示,RSA-OAEP 算法在隨機預言模型中可達到MM-CCA 安全性.這在實際應用中非常有意義,因為RSA-OAEP 包含在現(xiàn)有很多密碼庫中,可直接訪問現(xiàn)有密碼庫的中的高級程序接口而易于實現(xiàn).

2.4 有待深入研究的問題

關于對沖公鑰加密算法,我們總結了如下幾個需要進一步研究的問題.

1)現(xiàn)有對沖公鑰加密算法都依賴隨機預言模型,而該模型是密碼學中的一個理想化模型,現(xiàn)實世界中并不存在.如何構造基于標準模型下的對沖公鑰機密算法,將是值得繼續(xù)研究的一個方向;

2)目前,關于對沖公鑰加密算法的安全性研究存在一個一般性問題,就是沒有一個安全性質可以適用于所有的對沖公鑰加密算法.所以,研究對沖公鑰加密算法的一般性安全性質是值得探索的方向;

3)對沖公鑰加密算法通常要求明文消息和相應隨機數(shù)(或隨機填充值)的聯(lián)合分布是高熵的.若明文空間較小,對沖公鑰加密算法的安全性等價于隨機數(shù)生成算法的安全性.因此,設計明文空間較小情況下,抗后門攻擊的對沖公鑰加密算法,是一個值得探索的方向.

3 基于隨機性強化的方法

本節(jié)討論基于隨機性強化的抗隨機數(shù)后門攻擊方法.目前,基于隨機性強化的方法可以概括為3 類,即nonce-based 公鑰加密算法(nonce-based public-key encryption,簡稱N-PKE)[1,4,21,22]、對沖的nonce-based 公鑰加密算法(hedged nonce-based public key encryption,簡稱HN-PKE)[3]、Dodis 隨機數(shù)生成算法[5].以下對這3 種方法分別進行總結.

3.1 N-PKE算法

Nonce-based 公鑰加密算法的發(fā)展可以追溯到2002年,Rogaway 在關聯(lián)數(shù)據(jù)的可驗證加密方案中首次引入了nonce 的概念[21].2004年,Rogaway 首次提出nonce-based 對稱加密方案[4].2006年,Rogaway 和Shrimpton 細化了nonce 的概念[22].他們表示:packet sequence numbers 即可作為一個nonce,并且強調(diào)nonce-based 加密思想可以有效抵抗隨機數(shù)后門攻擊.2016年,Bellare 和Tackmann 提出了nonce-based 公鑰密碼算法[1].

在文獻[1]中,Bellare 和Tackmann 定義了nonce-based 公鑰密碼算法應滿足的安全屬性,并給出了具體構造和安全性分析.相比于傳統(tǒng)公鑰密碼算法,nonce-based 公鑰密碼算法中需要使用兩個額外的密碼組件,即nonce生成器(nonce generator,簡稱NG)和對沖提取器(hedged extractor,簡稱HE).

?前者的輸入為安全參數(shù)k、nonce selectorη和當前狀態(tài)值St,輸出為nonce 值n和下一個狀態(tài)值St′;

?后者輸入為安全參數(shù)k,種子密鑰xk、消息M和noncen,輸出一個隨機數(shù)r.

Bellare 和Tackmann 分別給出了HE 在隨機預言模型和標準模型下的構造方法[1].

在隨機預言模型下HE 的構造,需把HE 看作隨機預言機RO.假設k是種子密鑰的長度,l是HE 的輸出長度,HE.Keys={0,1}k,HE.Dom={0,1}*×{0,1}*,HE.Rng={0,1}l,其中,HE.Dom是(n,M)的取值空間.HE 可定義為映射HE:HE.Keys×HE.Dom→HE.Rng.具體HE 的構造為HERO(xk,(n,M)),其中,xk為種子密鑰,n∈{0,1}*為nonce 值,M∈{0,1}*表示消息.為保證構造的安全性,HE 需視作RO,即HERO(xk,(n,M))=RO((xk,(n,M)),l).

標準模型下,HE 的構造基于偽隨機函數(shù)PRF(pseudorandom function)和AXUHF(almost XOR universal Hash function).將PRF 記為映射F:F.Keys×({0,1}*×{0,1}*)→{0,1}l,將AXUHF 記為映射H:H.Keys×H.Dom→{0,1}l.其中,F.Keys和H.Keys分別表示PRF 和AXUHF 的密鑰空間,H.Dom?{0,1}*表示nonce 值的取值空間.假設種子密鑰為xk、nonce 值為n∈H.Dom、消息為M∈{0,1}*,標準模型下HE 的構造如下.

?先將xk分為兩部分,即xk→(hk,fk),其中,hk和fk分別屬于H.Keys和F.Keys;

?分別執(zhí)行PRF 和AXUHF,即H(hk,n)→z1,F(fk,(M,n))→z2;

?最終,HE 的輸出為z1⊕z2∈{0,1}l.

Nonce-based 公鑰加密算法基于一個傳統(tǒng)安全的公鑰加密算法設計[1].下面介紹具體的nonce-based 公鑰加密算法.為方便起見,我們將其記做NPKE=(NKg,NSKg,NEnc,NDec),將所用的傳統(tǒng)安全的公鑰加密算法記為PE=(PE.Kg,PE.Enc,PE.Dec).一個nonce-based 公鑰加密算法包括如下4 個基本算法.

?密鑰生成算法NKg(1k):輸入安全參數(shù)1k,運行算法(pk,sk)←PE.Kg(1k),輸出公私鑰對(pk,sk);

?種子密鑰生成算法NSKg(1k):輸入安全參數(shù)1k,輸出種子密鑰xk;

?加密算法NEnc(pk,M,xk):輸入公鑰pk、消息M、種子密鑰xk,先運行NG 算法生成nonce 值n,即(n,St′)←NG(η,St),其中,nonce selectorη和NG 的當前狀態(tài)值St是加密者自己選取的,St′表示NG 的下一個狀態(tài)值;再運行HE 算法生成隨機數(shù)r,即r←HERO(xk,M,n);再運行算法PE.Enc進行加密操作,即C←PE.Enc(pk,M,r);最后輸出密文C;

?解密算法NDec(sk,C):輸入私鑰sk和密文C,運行算法M←PE.Dec(sk,pk,C),輸出消息M.

對于nonce-based 公鑰加密算法,若一個攻擊者想攻破該算法,他需要同時獲得nonce 和種子密鑰的值[1].文獻[1]中,Bellare 和Tackmann 定義了兩個nonce-based 公鑰加密算法的安全性質,即NBP1(nonce-based privacy 1)和NBP2(nonce-based privacy 2).

?NBP1 是指攻擊者未知用戶的種子密鑰時,只要消息和nonce 不重復,攻擊者就不能攻破nonce-based公鑰加密算法;

?NBP2 是指攻擊者已知用戶種子密鑰時,只要nonce 不可預測,攻擊者就不能攻破密碼算法.

Bellare 和Tackmann 指出:對于上述NPKE 算法,若其采用標準模型下的HE 和標準模型下可證明安全的PE算法,則NPKE 算法在標準模型下滿足NBP1 和NBP2 安全性;否則,只要NPKE 中采用了隨機預言模型下的HE 或PE,則NPKE 在隨機預言模型下滿足NBP1 和NBP2 安全性[1].

另外,Bellare 和Tackmann 還研究了nonce-based 簽名方案,并對其安全性進行分析和證明[1].Nonce-based 簽名方案的設計基于一個傳統(tǒng)的數(shù)字簽名算法.下面介紹具體的nonce-based 簽名算法,為方便起見,我們將其記做NDS=(NDS.Kg,NDS.Sig,NDS.Vrf),將所用的傳統(tǒng)簽名算法記為DS=(DS.Kg,DS.Sig,DS.Vrf).一個nonce-based 公鑰加密算法包括如下3 個基本算法.

?密鑰生成算法NDS.Kg(1k):輸入安全參數(shù)1k,運行算法(sk,vk)←DS.Kg(1k),輸出簽名密鑰sk,驗證密鑰vk

以及種子密鑰xk;

?簽名算法NDS.Sig(1k):輸入簽名密鑰sk、種子密鑰xk、消息M,先運行NG 算法生成nonce 值n,即(n,St′)←NG(η,St),其中,nonce selectorη和NG 的當前狀態(tài)值St是加密者自己選取的,St′表示NG 的下一個狀態(tài)值;再運行HE 算法生成隨機數(shù)r,即r←HERO(xk,M,n);再運行算法DS.Sig進行簽名操作,運行算法s←DS.Sig(sk,M,r),輸出簽名s;

?驗證算法NDS.Vrf(1k):輸入驗證密鑰vk、消息M和簽名s,若等式NDS.Vrf(vk,M,NDS.Sig(sk,xk,M,n))=1,則表示簽名認證成功;否則,輸出錯誤符號⊥.

文獻[1]中定義了nonce-based 簽名算法的兩個安全性質,即NBUF1(nonce-based unforgeability 1)和NBUF2(nonce-based unforgeability 2).

?NBUF1 是指:只要種子密鑰保密的情況下,不論nonce 值是否可預測,則nonce-based 簽名算法都能滿足不可偽造性;

?NBUF2 是指:種子密鑰泄露的情況下,只有nonce 值不可預測時,nonce-based 簽名算法才能滿足不可偽造性.

Bellare 和Tackmann 指出:對于上述NDS 算法,若其采用標準模型下的HE 和標準模型下可證明安全的DS算法,則NDS 算法在標準模型下滿足NBUF1 和NBUF2 安全性;否則,只要NDS 中采用了隨機預言模型下的HE 或DS,則NDS 在隨機預言模型下滿足NBUF1 和NBUF2 安全性[1].

3.2 HN-PKE算法

2018年,Huang 等人在文獻[3]中首次將對沖公鑰加密和nonce-based 公鑰加密相結合,提出了對沖的noncebased 公鑰加密算法.從本質上講,對沖的nonce-based 公鑰加密著眼于研究nonce-based 公鑰加密算法(詳見第3.1 節(jié))的對沖安全性質,即:當nonce-based 公鑰加密算法中所用的隨機數(shù)存在后門時,算法不是直接被攻破,而是仍然可以滿足某些弱的安全性.文獻[3]中,作者將第2.2 節(jié)介紹的對沖安全性質IND-CDA 進行了擴展,在其基礎上定義了一個新的適用于nonce-based 公鑰加密算法的安全性質IND-CDA2(chosen-ciphertext securit y against chosen-distribution attack);并且他們指出,IND-CDA2 安全性比IND-CDA 安全性更強.IND-CDA2 安全性要求nonce-based 公鑰加密算法中對沖提取器HE 的種子密鑰、被加密明文消息以及隨機數(shù)的聯(lián)合分布有高的最小熵.對沖的nonce-based 公鑰加密算法需要同時滿足IND-CDA2,NBP1,NBP2 這3 種安全性.除此之外,文獻[3]中還分析證明了IND-CDA2 與NBP1/NBP2 之間的關系,他們的證明結論表示,NBP1/NBP2?IND-CDA2,IND-CDA2?NBP1/NBP2.Huang 等人表示,第3.1 節(jié)介紹的nonce-based 公鑰加密算法即可視作在隨機預言模型下HN-PKE 的算法構造.他們著重研究了nonce-based 公鑰加密算法的對沖安全性質,證明結果表明,noncebased 公鑰加密算法在隨機預言機模型下滿足IND-CDA2 安全性.

另外,Huang 等人考慮了 HN-PKE 在標準模型下的算法構造,并提出了一個具體的 NtD(nonce-thendeterministic)加密算法[3].所謂的NtD 算法是指:先用nonce-based 公鑰加密算法N-PKE(詳見第3.1 節(jié))對明文消息m進行加密生成m′,再選擇一個確定性加密算法D-PKE 對m′進行加密,生成最終密文C.具體的NtD 算法包含4 個基本算法,分別是密鑰生成算法NDKg、種子生成算法NDSKg、加密算法NDEnc、解密算法NDDec,我們將其記為NtD=(NDKg,NDSKg,NDEnc,NDDec).為方便起見,我們將N-PKE 算法記為NPKE=(NKg,NSKg,NEnc,NDec),將D-PKE 算法記為DPKE=(DKg,DEnc,DDec).具體的NtD 加密算法介紹如下.

?密鑰生成算法NDKg(1k):輸入安全參數(shù)1k,首先運行N-PKE 算法的密鑰生成算法NKg(1k)→(pkn,skn),生成N-PKE 算法的公私鑰對;其次運行D-PKE 算法的密鑰生成算法DKg(1k)→(pkd,skd),生成D-PKE算法的公私鑰對;最后輸出NtD 算法的公鑰pk=(pkn,pkd),私鑰sk=(skn,skd);

?種子生成算法NDSKg(1k):輸入安全參數(shù)1k,運行N-PKE 算法的種子生成算法NSKg(1k)→xk,輸出種子密鑰xk;

?加密算法NDEncpk(M,n,xk):輸入公鑰pk=(pkn,pkd)、消息M、一個nonce 值n,先運行N-PKE 算法的加密算法NEnc(pkn,xk,M,n)→y,再運行D-PKE 算法的加密算法DEnc(pkd,y)→C,輸出密文C,其中,nonce由NG 產(chǎn)生;

?解密算法NDDecsk(C):輸入私鑰sk=(skn,skd)和密文C,先運行D-PKE 算法的解密算法DDec(skd,C)→y,再運行N-PKE 算法的解密算法NDec(skn,y)→M,輸出消息M.

證明結果表明:當確定性加密算法DPKE=(DKg,DEnc,DDec)在標模下滿足適應性CCA 安全性時,NtD 算法在標模下滿足NBP1,NBP2,IND-CDA2 安全性.

3.3 Dodis隨機數(shù)生成算法

在文獻[5]中,Dodis 等人詳細介紹了Dual E C P RNG 中后門攻擊的原理.同時,他們表示,可以用密鑰封裝算法和公鑰加密算法來構造BPRNG.即,將密鑰封裝算法和公鑰加密算法的輸出看作BPRNG 生成的隨機數(shù).

除此之外,他們還提出了一種用于增強PRNG 輸出隨機性的函數(shù),將該函數(shù)定義為“免疫”函數(shù),用fseed表示.“免疫”函數(shù)的工作原理是:將可能存在后門的PRNG 生成的可能不安全的可預測隨機數(shù)做為“免疫”函數(shù)fseed的輸入,將函數(shù)fseed的輸出作為最終的隨機數(shù).

這種情況下,如何判斷“免疫”函數(shù)作用的有效性是個重要問題.文獻[5]中給出了一種驗證方法:存在一個攻擊者A,他試圖構造一個帶有后門的PRNG,然后使用“免疫”函數(shù)fseed對該PRNG 進行免疫.如果A能成功構造一個帶有后門的PRNG,并繞過fseed,則表明函數(shù)fseed為無效免疫;否則,表明fseed有效免疫.在這個驗證過程中,根據(jù)攻擊者已知“免疫”函數(shù)fseed相關信息的程度不同,Dodis 等人將免疫模型分為3 種:公開免疫模型、半隱私免疫模型和隱私免疫模型.其中:公開免疫模型是指攻擊者A構造帶有后門的PRNG 之前就已知函數(shù)fseed的seed值,也就是說,攻擊者已知函數(shù)fseed;半隱私免疫模型是指A構造帶有后門的PRNG 之后才已知seed;隱私免疫模型是指A構造帶有后門的PRNG 前后都未知seed.Dodis 等人的研究結果表明:在公開免疫模型下,存在后門的PRNG 是不能被免疫的,即不存在免疫函數(shù)fseed.在半隱私免疫模型下,Dodis 等人分別考慮了針對隨機預言模型和標準模型的免疫函數(shù).他們指出:在隨機預言模型下,可將隨機預言機RO(random orac le)看作免疫函數(shù),即fseed=RO;在標準模型下,可用通用計算萃取器UCE(universal computational extractor)作為免疫函數(shù),即fseed=UCE;在隱私免疫模型下,Dodis 等人指出:可將偽隨機函數(shù)PRF 作為免疫函數(shù),即fseed=PRF.

3.4 需要進一步研究的問題

基于隨機性強化的抗隨機數(shù)后門攻擊方法本質上是一種門限機制,即隨機數(shù)的生成依賴多個密碼組件.當單個或若干個密碼組件存在后門時,只要某個密碼組件是安全可靠的,仍然可以得到安全的隨機數(shù).雖然門限機制可有效解決后門攻擊問題,然而現(xiàn)有方案還存在如下問題.

1)在nonce-based 公鑰加密算法中,一個新的密碼組件HE 被用于增強隨機性.然而,根據(jù)文獻[1]中所給HE 的定義可以看出,HE 的實例化依賴于隨機預言機RO 或者依賴于AXUHF 和PRF.而RO 是密碼學中的一個假設,現(xiàn)實世界并不存在.此外,作者并沒給出隨機預言模型下,HE 的具體構造.因此在實際應用中,如何實現(xiàn)該類HE 還需進一步研究.在標準模型下,HE 的實例化依賴于AXUHF 和PRF,而現(xiàn)有已實現(xiàn)的AXUHF,PRF 等密碼學工具中是否存在類似于Dual EC PRNG 隨機數(shù)后門攻擊,也還有待研究;

2)第3.3 節(jié)所述的“免疫”函數(shù)的實現(xiàn)也存在上述類似的問題.現(xiàn)有“免疫”函數(shù)的實現(xiàn)依賴于RO,UCE 或PRF.RO 和UCE 都在密碼學中的一個假設,而已實現(xiàn)的PRF 中是否存在隨機數(shù)后門攻擊等問題,還有待研究.此外,作者也未給出具體的免疫函數(shù);

3)在文獻[3]中,作者考慮了對沖公鑰加密算法在標準模型下的構造,并提出了NtD 對沖公鑰加密算法(詳見第3.3 節(jié)).該算法的安全性依賴于完全適應性CCA 安全的確定性加密算法,然而如何構造適應性CCA 安全的確定性加密算法,目前還是一個開放問題[3].

4 其他相關技術

上述抗隨機數(shù)后門攻擊密碼算法側重于算法層面的安全性.在實際應用中,攻擊者可在算法實現(xiàn)時設計后門來破壞密碼系統(tǒng)的安全性,其中最典型的為算法替代攻擊.本節(jié)首先闡述算法替代攻擊基本原理,隨后介紹現(xiàn)有抵抗算法替代的方法.

4.1 算法替代攻擊

算法替代攻擊(algorithm substitution attacks,簡稱ASA)最早由Young 等人在1997年歐密會(EUROCRYPT)上提出[23],該攻擊也稱為顛覆攻擊(substitution attac ks,簡稱SA).相較于在算法中設計后門,算法替代攻擊著重于在密碼算法實現(xiàn)過程中插入后門.通常來說,密碼系統(tǒng)中使用的密碼算法的安全性是經(jīng)過嚴格的安全性分析的.然而在實際應用中,這些密碼系統(tǒng)的使用模式是“黑盒”模式[24],即用戶并不知曉其內(nèi)部構造.這使得攻擊者可惡意設計算法的使用模式,在特殊情況下,用新算法覆蓋掉原有算法,同時,新算法即使面對相當密集的黑盒測試也會看起來完全安全.在文獻[25]中,作者指出,所有依賴第三方軟件庫或硬件設備的密碼系統(tǒng)均可能遭受算法替代攻擊.

算法替代攻擊的基本原理是:攻擊者在密碼算法從理論轉化為現(xiàn)實過程中,將原誠實可靠的實現(xiàn)算法替換成一個已被植入秘密信息的替代算法[26].植入的秘密信息只有敵手可見,通常稱為后門信息.攻擊者可利用該后門信息與輸出結果的聯(lián)系來恢復系統(tǒng)的秘密信息(如密鑰、隨機數(shù)等),從而破壞系統(tǒng)的安全性.ASA 攻擊要求對于除攻擊者以外的任意用戶來說,替代算法與誠實算法的輸出分布結果是不可區(qū)分的.隨著對算法替代攻擊的不斷研究,如何有效抵御算法替代攻擊也成為一個新的問題.最簡單的防算法替代攻擊的策略是采用確定性密碼算法[8],如文獻[8,25?27]中所建議的加密方案、本文第2.1 節(jié)中所介紹的確定性加密算法等.因確定性加密算法具有唯一密文屬性,攻擊者若在算法實現(xiàn)時插入后門,其攻擊行為將很容易被檢測到.然后,如第2.1 節(jié)所述,為保證算法的安全性,確定性加密算法要求明文空間足夠大,并且具有高的最小熵.

近年來,針對概率性密碼算法的ASA 防御策略的研究也取得了一定的進展,目前大致分為兩類:第1 類被稱作為抗盜密密碼學(cliptography)[28],詳見第4.2 節(jié);第2 類被稱為逆向防火墻[29,30],詳見第4.3 節(jié).

4.2 抗盜密密碼學

抗盜密密碼學的概念最初是由Alexander 和Tang 等人[25]提出的,旨在防止盜密攻擊(kleptographic)下[20],概率性密碼算法免受算法替代攻擊的威脅.抗盜密密碼學借鑒了模塊化的設計思想,即原密碼算法可劃分成不同的算法組件(子模塊),每個算法組件可獨立執(zhí)行.此外,抗盜密密碼學采用有威懾力的可信第三方實體——看門狗”(watchdog)來檢測每個算法組件是否遭受算法替代攻擊.抗盜密密碼學的關鍵在于如何劃分算法組件,文獻[28]中的“split-program”模塊化方法根據(jù)算法執(zhí)行過程中是否需要使用隨機數(shù)而將整個算法分成兩個模塊:確定性算法組件(例如確定性加密算法)和概率性算法組件(例如隨機數(shù)生成算法、密鑰生成算法).兩個模塊獨立執(zhí)行,具體的,先執(zhí)行概率性算法組件,并將執(zhí)行結果輸入到一個散列函數(shù)中,再將經(jīng)過該函數(shù)作用過的結果輸入到確定性算法組件去執(zhí)行.由于原算法被分為多個獨立組件,因此攻擊者需對所有組件一一替換.模塊化設計的思想在于增加了攻擊者替換原算法的難度,散列函數(shù)的作用則在于增加隨機數(shù)的熵值和不確定性.此外,Alexander 等人在文獻[28]基礎上提出了“double-split”方法[31,32].該方法在“split-program”劃分的基礎上,將概率性算法組件分為兩個子組件.子組件獨立且并發(fā)執(zhí)行,執(zhí)行結果級聯(lián)后輸入散列函數(shù).后續(xù)執(zhí)行過程與文獻[28]類似.

目前,抗盜密密碼學只是初具雛形,有關的潛在應用場景還值得進一步研究,譬如利用該方法構造一個collusion-free 的協(xié)議[33].此外,該方法主要考慮無狀態(tài)算法[34].在一些實踐中,算法可能是有狀態(tài)的[28],例如計數(shù)器模式加密.如何擴展到有狀態(tài)的算法,還值得深入研究.

4.3 逆向防火墻

傳統(tǒng)防火墻用于內(nèi)網(wǎng)和外網(wǎng)的隔離,它按照系統(tǒng)管理員預先定義好的規(guī)則來控制數(shù)據(jù)包的進出,以阻擋來自外網(wǎng)的入侵,保障內(nèi)網(wǎng)的安全.密碼逆向防火墻(cryptographic r everse fi rewalls,簡稱CRF)的概念最初是由Mironov 等人在2015年的歐密會上提出的[35].密碼逆向防火墻旨在防止機密信息從內(nèi)網(wǎng)遭受入侵(密碼算法存在算法替代攻擊)的主機中泄露出去,其基本思想在于重隨機化[36,37?39].密碼逆向防火墻的關鍵在于設計/找到合適的加密算法,該算法能確保公鑰/密鑰或是密文被重隨機化后,接收方仍能正確解密.例如:在公鑰密碼體制中,發(fā)送者用公鑰加密生成的密文從內(nèi)網(wǎng)發(fā)出時,為防止加密算法被替換為植入后門信息的算法而破環(huán)算法安全性,密文會被密碼逆向防火墻重隨機化后發(fā)給接收者,接收者可直接解密該密文.密碼逆向防火墻也可基于公鑰/密鑰重隨機化[40],該類方法旨在抵抗攻擊者在公鑰中植入后門信息.此時要求選擇的加密算法具有密鑰可延展性(key m alleable),即,接收者可把使用重隨機后的公鑰加密的密文映射到用原始公鑰加密的密文[41,42].找到擁有這樣的可重隨機化特性的加密算法并設計相應的密碼逆向防火墻,是當下的主要研究內(nèi)容.

目前為止,密碼逆向防火墻仍有一些問題亟待解決,其中包括文獻[35]中提到的缺少前向安全性以及相對低效(當下的方案需要對整個明文進行加密).所以,尋找前向安全的高效密碼逆向防火墻方案,將成為日后的研究方向之一.

5 總結與展望

抗隨機數(shù)后門攻擊密碼算法經(jīng)過幾年的研究,已經(jīng)取得了一些有意義的成果.本文全方位地就其中的主要成果進行梳理總結,包括抗隨機數(shù)后門攻擊的對稱加密算法、對沖公鑰加密算法、基于隨機性強化的方法以及其他相關技術目前的研究現(xiàn)狀,分析了相關構造的特點,并指出目前相關技術研究過程中所面臨的問題.總體來說,現(xiàn)有成果大多是從理論層面分析了抗隨機數(shù)后門攻擊的解決方案,而可實現(xiàn)的抗隨機數(shù)后門攻擊的密碼算法仍然是需要進一步研究的主要方向.

現(xiàn)有的密碼算法大多采用靜態(tài)密碼組件(如密鑰生成器、PRNG 等)設計,這增加了算法在實現(xiàn)過程中被植入隨機數(shù)后門的可能性.動態(tài)密碼組件的使用,將能更有效地防止攻擊者在算法中植入后門.例如,研究動態(tài)與交叉動態(tài)技術是未來抗隨機數(shù)后門密碼算法的一個研究方向:前者的基本思想在于對消息用多個動態(tài)變化的密碼算法作用于該消息,并且其中的隨機數(shù)生成算法使用不同的算法;后者的基本思想在于對多個動態(tài)變化的隨機數(shù)生成算法產(chǎn)生的隨機數(shù)進行一些運算(如異或等),將運算后的結果用于理論上安全的密碼算法中.直觀上,這兩種技術可有效抵抗隨機數(shù)后門攻擊,然而如何對他們的安全性進行形式化分析還有待探討.另外,目前抗隨機數(shù)后門攻擊密碼算法的研究成果主要集中在加密算法方面,而在密鑰協(xié)商協(xié)議、簽名算法、簽密算法等方面的研究較少.因此,抗隨機數(shù)后門攻擊的密鑰協(xié)商協(xié)議、簽名算法、簽密算法等方向都是未來的研究方向.最后,現(xiàn)有的抗隨機數(shù)后門攻擊密碼算法大多數(shù)只能在隨機預言模型下得到證明,在標準模型下可證明安全的抗隨機數(shù)后門攻擊密碼算法為數(shù)不多.標準模型下,高效的抗隨機數(shù)后門攻擊密碼算法還待進一步研究.