抗随机数后门攻击的密码算法∗

康步荣,张 磊,张 蕊,孟欣宇,陈 桐

1(软硬件协同设计技术与应用教育部工程研究中心(华东师范大学),上海 2000 62)

2(华东师范大学 软件工程学院,上海 20006 2)

3(密码科学技术国家重点实验室,北京 100 878)

迄今为止,大多数密码原语的安全性都依赖于高质量的不可预测的随机数[1−4].密码学中,我们通常用伪随机数生成器(pseudorandom nu mber generator,简称PRNG)来生成随机数.而实际上,很多人为因素会导致PRNG生成的随机数不安全[1−3,5].通常,我们称不安全的PRNG 为存在后门的PRNG(backdoored pseudorandom number generator,简称BPRNG).在信息安全领域,后门是指可以绕过安全控制而获取对程序或系统访问权的方法.后门的最主要目的就是方便以后再次秘密进入或者控制系统.此处,我们所研究的后门主要是指存在于密码组件PRNG 里的后门,这种后门使得PRNG 产生的用于密码算法中的随机数,对于那些已知此后门的人来说是可预测的.知道后门的攻击者因可预测随机数,他很可能会成功破解相应的密码算法,这将严重地威胁到密码算法的安全性.正如在2014年SXSW 大会(South B y Southwest Con ference)上斯诺登所言,攻击者在攻击加密算法时,真正受到攻击的其实是加密算法中使用的PRNG,而非算法本身.所以,研究抵抗随机数后门攻击的密码算法是非常有意义且有必要的.

说起对密码算法的威胁,量子计算机也是其中之一.近年来,量子信息科学的研究和发展催生了量子计算机[6],而量子计算机的强大计算能力对传统密码算法,尤其是对公钥密码算法产生了严重威胁[6].例如,Shor 算法就是一个分解大整数问题和求解离散对数问题的有效量子算法[6,7].Shor 算法的出现,严重威胁了基于大整数分解困难问题和离散对数困难问题的公钥密码算法,如RSA,ECC,ElGamal 算法等.文献[6]总结了现有的量子算法及其对传统公钥密码算法的威胁,并梳理了量子计算机在物理实现上的发展历史及相应成果.到目前为止,虽然国际上很多著名的公司都纷纷加入量子计算机的研制之中,但距离通用的量子计算机的大规模使用还需要很长时间.因此,在量子计算机真正取代传统计算机之前,随机数后门攻击成为威胁现有密码算法的主要因素.研究抗随机数后门攻击的密码算法是亟待解决的问题.

据统计,目前主要有两类影响PRNG 工作过程的因素[1,2,5,8−10].

•第1 类影响因素是“漏洞”.例如,2006年9月~2008年5月发生在Debian Linux 操作系统上的安全漏洞,一名程序员删除了OpenSSL 密码库里的部分代码,导致该系统中PRNG 的种子密钥仅剩15 位熵[11].信息论中,熵用来表示一个数的不确定性,熵越大,数的不确定性越高.随后,传输层协议(transport layer security,简称TLS)和安全套接字层协议(secure sockets layer,简称SSL)被曝出其服务器的重要组件使用了有后门的PRNG 而使协议存在安全漏洞[12];

•第2 类影响因素被称为“恶意颠覆”,其目的是减弱PRNG 生成随机数的随机性.一个典型的例子是双椭圆曲线伪随机数生成器Dual EC PRNG,Dual EC PRNG 是NSA 设计的一个伪随机数生成器算法,由NIST 列入算法标准[1,2,5,8−10,13,14].此后,Dual EC P RNG 一直被广泛使用,直至2014年,该算法被曝出存在后门,即生成的随机数可预测[15].在实际应用中,Dual E C P RNG 被著名网络公司Juniper N etwork 应用于其所生产的NetScreen VP N 路由器的操作系统中.在文献[16]中,作者详细分析了NetScreen VPN路由器所存在的该随机数后门攻击.

1 抗随机数后门攻击的对称加密算法

对于加密算法,我们通常要求其能达到CPA(chosen plaintext attacks)安全性.然而,经典的对称加密算法(如AES,DES)未考虑该安全性.究其原因,这些算法为确定性加密算法.要实现CPA 安全性,加密算法必须为概率性算法,即算法中需引入随机数(如加密模式中使用的初始化向量IV、消息填充等).然而,若在算法实现时使用存在后门的PRNG,则该加密算法将仍然无法达到CPA 安全.本节介绍抗随机数后门的对称加密算法.

1.1 Kamara-Katz系列对称加密算法

1.2 需要进一步研究的问题

到目前为止,关于抗随机数后门攻击的对称加密算法的研究成果并不多,较为有效的算法仅有Kamara-Katz 系列对称加密算法SKE1,SKE2.但是我们不难发现,该算法的构造依赖于很强的假设条件.因为在算法实现过程中,很难保证所用的P函数和F函数是真正伪随机的,所以除了伪随机函数和伪随机置换之外,还可以用哪些数学工具和密码原语来构造抗后门攻击的对称密码算法,是一个需要研究的问题.另外,Kamara-Katz 系列对称加密算法相当于重新构造了一个对称加密算法,而不是在现有对称加密算法基础上构造.如何构造实用的抗随机数后门攻击的对称加密算法,即简单改变现有密码库(如OpenSSL 库)的使用方式即可实现抗后门攻击,也是此研究领域的另一重要的有待解决的问题.这将大大减少密码库开发者的工作量,节省开发成本.

2 对冲公钥加密算法H-PKE

对冲公钥加密算法最早由Bellare 等人在2009年亚密会(ASIACRYPT)上提出[18].所谓对冲是指密码算法满足两个层次的安全性.

•第1 层安全性是指在加密算法中所用随机数是可靠的、高熵的情况下,算法可达到标准安全性(如IND-CPA,IND-CCA);

•第2 层安全性是指在加密算法中所用随机数是不可靠的、低熵的情况下,算法依然可以满足某些比标准安全性稍弱的安全性,而不是直接被攻破[2,3,18].

当对冲公开密钥加密算法同时满足上述两个层次的安全性时,才说它是对冲安全的.对冲加密算法要求被加密的消息和加密时所用随机数的联合分布具有高熵.现有的对冲加密算法可以概括为3 类,即确定性公钥加密(deterministic public-key e ncryption,简称 D-PKE)[2,18−20]、随机再确定性公钥加密算法(randomized-thendeterministic,简称RtD)[2,18]、填充再确定性公钥加密(pad-then- deterministic,简称PtD)[2,18].本节讨论对冲公钥加密的含义和安全性概念,然后分别从上述3 个方面对现有方案进行总结和分析.

2.1 D-PKE算法

确定性公钥加密算法最早是由Bellare 等人在2007年美密会(CRYPTO)上提出来的密码学原语[19].在文献[18]中,作者指出,确定性加密算法是构造对冲加密算法的一种方法.所谓确定性加密,本质上是指在算法设计中不使用随机数.他们指出,设计确定性公钥加密算法存在两个问题.

•首先,如果一个敌手得知该算法的明文消息是从一个小的明文空间中选取的,那么他可以很容易用穷举法恢复出明文.为解决这个问题,他们要求算法的明文空间足够大,并且具有高的最小熵;

•其次,因为在确定性公钥加密算中不使用随机数,所以加密算法输出的密文在某种程度上暴露了明文的部分信息.该问题的解决办法是要求明文不依赖于公钥,即明文和公钥是相互独立的.

文献[19]中提出了两个在随机预言模型下的确定性公钥加密算法实例:EwH 算法(encrypt-with-Hash,简称EwH)和RSA-DOAEP 算法(RSA-deterministic optimal asymmetric encryption padding,简称RSA-DOAEP).下面我们将对EwH 算法和RSA-DOAEP 算法分别进行讨论.简单来说,EwH 算法是先对用户的公钥、明文消息做一次Hash 操作,将Hash 值作为一个安全公钥加密算法的随机数,并利用该公钥加密算法生成最终密文.下面我们给出具体的EwH 加密算法.为方便描述,我们将EwH 算法记为EwH=(EwH.K,EwH.E,EwH.D),将任一安全公钥密码算法记为PKE=(PKE.K,PKE.E,PKE.D),哈希函数记为H:{0,1}*×{0,1}*→{0,1}*.

•密钥生成算法EwH.K(1k):输入安全参数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 安全性要求一个攻击者,已知一个明文向量所对应的确定性加密算法的密文,只要这个明文向量的每个分量有高的最小熵,则该攻击者不能在多项式时间内以不可忽略的概率猜出任何关于原明文的部分信息(部分信息不依赖于加密时所用的公钥).证明结果表明:如果公钥加密算法PKE=(PKE.K,PKE.E,PKE.D)是IND-CPA 安全的,则上述EwH 确定性加密算法满足PRIV 安全性.

证明结果表明,上述确定性加密算法RSA-DOAEP 是PRIV 安全性.

关于确定性加密算法的研究还有一些其他的研究结果,例如在文献[20]中,Boldyreva 等人在文献[19]的基础上继续研究了确定性公钥加密算法的设计及安全性定义,他们发现了确定性公钥加密和有损限门函数之间的联系.他们利用有损限门函数,给出了在标准模型下满足PRIV-CPA 安全性(即,在PRIV 安全性的基础上允许攻击者进行加密预言机询问)的确定性公钥加密算法的一般性构造思想.为了更好地描述该算法,他们提出了一个新的密码原语,隐藏全域哈希模式的确定性公钥加密算法(deterministic encryption with hidden universal-Hash mode,简称DEHUHM);其次,他们将该PRIV-CPA 安全的算法构造进行了扩展,给出了PRIV-CCA 安全的确定性加密算法的一般性构造.另外,文献中还基于抗目标碰撞哈希函数、DDH 困难问题给出了两个具体的确定性加密算法实例.

2.2 RtD算法

Bellare 等人在文献[18]中介绍了对冲公钥密码算法RtD,RtD 基本思想是:对消息m先用一个概率性加密算法进行加密,输出密文C′,再用一个确定性加密算法对C′进行加密,输出最终密文C.同时,他们定义了一个新的对冲公钥加密算法的安全性质,即选择分布攻击下的不可区分性(indistinguishability under c hosen-distribution attacks,简称IND-CDA).在被加密的明文消息和相应随机数的联合分布是高熵的条件下,一个对冲公钥加密算法才能满足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).

•参数生成算法RtD.P(1k):输入安全参数k,先运行算法RPKE.P(1k)→Parr,得到随机性公钥密码算法RPKE 的系统参数Parr;再运行算法DPKE.P(1k)→Pard,得到确定性公钥密码算法DPKE 的系统参数Pard,输出(Parr,Pard);

•密钥生成算法RtD.K(1k):输入安全参数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和一个随机数r,先计算RPKE.E(pkr,m,r)→c,再计算DPKE.E(pkd,c||10l)→C,输出密文C.其中,l=nd−|c|−1,nd表示DPKE 算法的明文长度,0l表示有l个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).

•参数生成算法PtD.P(1k):输入安全参数k,运行确定性加密算法的参数生成算法DPKE.P(1k)→Pard,输出确定性公钥加密算法的系统参数Pard;

•密钥生成算法PtD.K(Pard):输入系统参数Pard,运行确定性公钥加密算法的密钥生成算法DPKE.K(Pard)→(pkd,skd),输出公私钥对(pkd,skd);

•加密算法PtD.E(pkd,m,r):输入系统参数Pard、随机数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 等人从实际出发,研究了在密码库OpenSSL 中可实现的对冲加密算法以及对冲加密算法的安全性质[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 节、第2.3 节中所述的IND-CDA 安全性等价于MMR-CPA 安全性(message-messagerandomness security against chosen plaintext attack).文献[18]的研究结果已经表明:RtD算法和PtD算法在满足一定约束条件时可达到IND-CDA 安全性,即MMR-CPA 安全性.所以在文献[2]中,Boldyreva 等人将该结果进行扩展,研究了RtD 算法和PtD 算法相应的CCA 安全性.证明结果表明,对于RtD 算法,当确定性算法选用RSA-DOAEP 时,算法可达到MM-CPA 和IND-CPA 安全;当概率性算法选用关联数据的单射加密算法,则算法可达到MMR-CCA 和IND-CCA 安全性.而对于PtD 算法,当确定性算法选用RSA-DOAEP 时,算法可满足MM-CCA 和IND-CCA 安全性.同时,文献[2]中的作者还基于关联数据的可验证加密算法和陷门置换函数构造了一个混合加密算法,并给出安全性分析.结果表明,该混合加密算法可满足MMR-CCA 和IND-CCA 安全性.他们的另一研究结果表示,RSA-OAEP 算法在随机预言模型中可达到MM-CCA 安全性.这在实际应用中非常有意义,因为RSA-OAEP 包含在现有很多密码库中,可直接访问现有密码库的中的高级程序接口而易于实现.

2.4 有待深入研究的问题

关于对冲公钥加密算法,我们总结了如下几个需要进一步研究的问题.

1)现有对冲公钥加密算法都依赖随机预言模型,而该模型是密码学中的一个理想化模型,现实世界中并不存在.如何构造基于标准模型下的对冲公钥机密算法,将是值得继续研究的一个方向;

2)目前,关于对冲公钥加密算法的安全性研究存在一个一般性问题,就是没有一个安全性质可以适用于所有的对冲公钥加密算法.所以,研究对冲公钥加密算法的一般性安全性质是值得探索的方向;

3)对冲公钥加密算法通常要求明文消息和相应随机数(或随机填充值)的联合分布是高熵的.若明文空间较小,对冲公钥加密算法的安全性等价于随机数生成算法的安全性.因此,设计明文空间较小情况下,抗后门攻击的对冲公钥加密算法,是一个值得探索的方向.

3 基于随机性强化的方法

本节讨论基于随机性强化的抗随机数后门攻击方法.目前,基于随机性强化的方法可以概括为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 随机数生成算法[5].以下对这3 种方法分别进行总结.

3.1 N-PKE算法

Nonce-based 公钥加密算法的发展可以追溯到2002年,Rogaway 在关联数据的可验证加密方案中首次引入了nonce 的概念[21].2004年,Rogaway 首次提出nonce-based 对称加密方案[4].2006年,Rogaway 和Shrimpton 细化了nonce 的概念[22].他们表示:packet sequence numbers 即可作为一个nonce,并且强调nonce-based 加密思想可以有效抵抗随机数后门攻击.2016年,Bellare 和Tackmann 提出了nonce-based 公钥密码算法[1].

在文献[1]中,Bellare 和Tackmann 定义了nonce-based 公钥密码算法应满足的安全属性,并给出了具体构造和安全性分析.相比于传统公钥密码算法,nonce-based 公钥密码算法中需要使用两个额外的密码组件,即nonce生成器(nonce generator,简称NG)和对冲提取器(hedged extractor,简称HE).

•前者的输入为安全参数k、nonce selectorη和当前状态值St,输出为nonce 值n和下一个状态值St′;

•后者输入为安全参数k,种子密钥xk、消息M和noncen,输出一个随机数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 的构造基于伪随机函数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;

•分别执行PRF 和AXUHF,即H(hk,n)→z1,F(fk,(M,n))→z2;

•最终,HE 的输出为z1⊕z2∈{0,1}l.

Nonce-based 公钥加密算法基于一个传统安全的公钥加密算法设计[1].下面介绍具体的nonce-based 公钥加密算法.为方便起见,我们将其记做NPKE=(NKg,NSKg,NEnc,NDec),将所用的传统安全的公钥加密算法记为PE=(PE.Kg,PE.Enc,PE.Dec).一个nonce-based 公钥加密算法包括如下4 个基本算法.

•密钥生成算法NKg(1k):输入安全参数1k,运行算法(pk,sk)←PE.Kg(1k),输出公私钥对(pk,sk);

•种子密钥生成算法NSKg(1k):输入安全参数1k,输出种子密钥xk;

•加密算法NEnc(pk,M,xk):输入公钥pk、消息M、种子密钥xk,先运行NG 算法生成nonce 值n,即(n,St′)←NG(η,St),其中,nonce selectorη和NG 的当前状态值St是加密者自己选取的,St′表示NG 的下一个状态值;再运行HE 算法生成随机数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 签名方案的设计基于一个传统的数字签名算法.下面介绍具体的nonce-based 签名算法,为方便起见,我们将其记做NDS=(NDS.Kg,NDS.Sig,NDS.Vrf),将所用的传统签名算法记为DS=(DS.Kg,DS.Sig,DS.Vrf).一个nonce-based 公钥加密算法包括如下3 个基本算法.

•密钥生成算法NDS.Kg(1k):输入安全参数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 的当前状态值St是加密者自己选取的,St′表示NG 的下一个状态值;再运行HE 算法生成随机数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 节)的对冲安全性质,即:当nonce-based 公钥加密算法中所用的随机数存在后门时,算法不是直接被攻破,而是仍然可以满足某些弱的安全性.文献[3]中,作者将第2.2 节介绍的对冲安全性质IND-CDA 进行了扩展,在其基础上定义了一个新的适用于nonce-based 公钥加密算法的安全性质IND-CDA2(chosen-ciphertext securit y against chosen-distribution attack);并且他们指出,IND-CDA2 安全性比IND-CDA 安全性更强.IND-CDA2 安全性要求nonce-based 公钥加密算法中对冲提取器HE 的种子密钥、被加密明文消息以及随机数的联合分布有高的最小熵.对冲的nonce-based 公钥加密算法需要同时满足IND-CDA2,NBP1,NBP2 这3 种安全性.除此之外,文献[3]中还分析证明了IND-CDA2 与NBP1/NBP2 之间的关系,他们的证明结论表示,NBP1/NBP2⇏IND-CDA2,IND-CDA2⇏NBP1/NBP2.Huang 等人表示,第3.1 节介绍的nonce-based 公钥加密算法即可视作在随机预言模型下HN-PKE 的算法构造.他们着重研究了nonce-based 公钥加密算法的对冲安全性质,证明结果表明,noncebased 公钥加密算法在随机预言机模型下满足IND-CDA2 安全性.

另外,Huang 等人考虑了 HN-PKE 在标准模型下的算法构造,并提出了一个具体的 NtD(nonce-thendeterministic)加密算法[3].所谓的NtD 算法是指:先用nonce-based 公钥加密算法N-PKE(详见第3.1 节)对明文消息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):输入安全参数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):输入安全参数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 产生;

•解密算法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随机数生成算法

在文献[5]中,Dodis 等人详细介绍了Dual E C P RNG 中后门攻击的原理.同时,他们表示,可以用密钥封装算法和公钥加密算法来构造BPRNG.即,将密钥封装算法和公钥加密算法的输出看作BPRNG 生成的随机数.

除此之外,他们还提出了一种用于增强PRNG 输出随机性的函数,将该函数定义为“免疫”函数,用fseed表示.“免疫”函数的工作原理是:将可能存在后门的PRNG 生成的可能不安全的可预测随机数做为“免疫”函数fseed的输入,将函数fseed的输出作为最终的随机数.

这种情况下,如何判断“免疫”函数作用的有效性是个重要问题.文献[5]中给出了一种验证方法:存在一个攻击者A,他试图构造一个带有后门的PRNG,然后使用“免疫”函数fseed对该PRNG 进行免疫.如果A能成功构造一个带有后门的PRNG,并绕过fseed,则表明函数fseed为无效免疫;否则,表明fseed有效免疫.在这个验证过程中,根据攻击者已知“免疫”函数fseed相关信息的程度不同,Dodis 等人将免疫模型分为3 种:公开免疫模型、半隐私免疫模型和隐私免疫模型.其中:公开免疫模型是指攻击者A构造带有后门的PRNG 之前就已知函数fseed的seed值,也就是说,攻击者已知函数fseed;半隐私免疫模型是指A构造带有后门的PRNG 之后才已知seed;隐私免疫模型是指A构造带有后门的PRNG 前后都未知seed.Dodis 等人的研究结果表明:在公开免疫模型下,存在后门的PRNG 是不能被免疫的,即不存在免疫函数fseed.在半隐私免疫模型下,Dodis 等人分别考虑了针对随机预言模型和标准模型的免疫函数.他们指出:在随机预言模型下,可将随机预言机RO(random orac le)看作免疫函数,即fseed=RO;在标准模型下,可用通用计算萃取器UCE(universal computational extractor)作为免疫函数,即fseed=UCE;在隐私免疫模型下,Dodis 等人指出:可将伪随机函数PRF 作为免疫函数,即fseed=PRF.

3.4 需要进一步研究的问题

基于随机性强化的抗随机数后门攻击方法本质上是一种门限机制,即随机数的生成依赖多个密码组件.当单个或若干个密码组件存在后门时,只要某个密码组件是安全可靠的,仍然可以得到安全的随机数.虽然门限机制可有效解决后门攻击问题,然而现有方案还存在如下问题.

1)在nonce-based 公钥加密算法中,一个新的密码组件HE 被用于增强随机性.然而,根据文献[1]中所给HE 的定义可以看出,HE 的实例化依赖于随机预言机RO 或者依赖于AXUHF 和PRF.而RO 是密码学中的一个假设,现实世界并不存在.此外,作者并没给出随机预言模型下,HE 的具体构造.因此在实际应用中,如何实现该类HE 还需进一步研究.在标准模型下,HE 的实例化依赖于AXUHF 和PRF,而现有已实现的AXUHF,PRF 等密码学工具中是否存在类似于Dual EC PRNG 随机数后门攻击,也还有待研究;

2)第3.3 节所述的“免疫”函数的实现也存在上述类似的问题.现有“免疫”函数的实现依赖于RO,UCE 或PRF.RO 和UCE 都在密码学中的一个假设,而已实现的PRF 中是否存在随机数后门攻击等问题,还有待研究.此外,作者也未给出具体的免疫函数;

3)在文献[3]中,作者考虑了对冲公钥加密算法在标准模型下的构造,并提出了NtD 对冲公钥加密算法(详见第3.3 节).该算法的安全性依赖于完全适应性CCA 安全的确定性加密算法,然而如何构造适应性CCA 安全的确定性加密算法,目前还是一个开放问题[3].

4 其他相关技术

上述抗随机数后门攻击密码算法侧重于算法层面的安全性.在实际应用中,攻击者可在算法实现时设计后门来破坏密码系统的安全性,其中最典型的为算法替代攻击.本节首先阐述算法替代攻击基本原理,随后介绍现有抵抗算法替代的方法.

4.1 算法替代攻击

算法替代攻击(algorithm substitution attacks,简称ASA)最早由Young 等人在1997年欧密会(EUROCRYPT)上提出[23],该攻击也称为颠覆攻击(substitution attac ks,简称SA).相较于在算法中设计后门,算法替代攻击着重于在密码算法实现过程中插入后门.通常来说,密码系统中使用的密码算法的安全性是经过严格的安全性分析的.然而在实际应用中,这些密码系统的使用模式是“黑盒”模式[24],即用户并不知晓其内部构造.这使得攻击者可恶意设计算法的使用模式,在特殊情况下,用新算法覆盖掉原有算法,同时,新算法即使面对相当密集的黑盒测试也会看起来完全安全.在文献[25]中,作者指出,所有依赖第三方软件库或硬件设备的密码系统均可能遭受算法替代攻击.

算法替代攻击的基本原理是:攻击者在密码算法从理论转化为现实过程中,将原诚实可靠的实现算法替换成一个已被植入秘密信息的替代算法[26].植入的秘密信息只有敌手可见,通常称为后门信息.攻击者可利用该后门信息与输出结果的联系来恢复系统的秘密信息(如密钥、随机数等),从而破坏系统的安全性.ASA 攻击要求对于除攻击者以外的任意用户来说,替代算法与诚实算法的输出分布结果是不可区分的.随着对算法替代攻击的不断研究,如何有效抵御算法替代攻击也成为一个新的问题.最简单的防算法替代攻击的策略是采用确定性密码算法[8],如文献[8,25−27]中所建议的加密方案、本文第2.1 节中所介绍的确定性加密算法等.因确定性加密算法具有唯一密文属性,攻击者若在算法实现时插入后门,其攻击行为将很容易被检测到.然后,如第2.1 节所述,为保证算法的安全性,确定性加密算法要求明文空间足够大,并且具有高的最小熵.

近年来,针对概率性密码算法的ASA 防御策略的研究也取得了一定的进展,目前大致分为两类:第1 类被称作为抗盗密密码学(cliptography)[28],详见第4.2 节;第2 类被称为逆向防火墙[29,30],详见第4.3 节.

4.2 抗盗密密码学

抗盗密密码学的概念最初是由Alexander 和Tang 等人[25]提出的,旨在防止盗密攻击(kleptographic)下[20],概率性密码算法免受算法替代攻击的威胁.抗盗密密码学借鉴了模块化的设计思想,即原密码算法可划分成不同的算法组件(子模块),每个算法组件可独立执行.此外,抗盗密密码学采用有威慑力的可信第三方实体——看门狗”(watchdog)来检测每个算法组件是否遭受算法替代攻击.抗盗密密码学的关键在于如何划分算法组件,文献[28]中的“split-program”模块化方法根据算法执行过程中是否需要使用随机数而将整个算法分成两个模块:确定性算法组件(例如确定性加密算法)和概率性算法组件(例如随机数生成算法、密钥生成算法).两个模块独立执行,具体的,先执行概率性算法组件,并将执行结果输入到一个散列函数中,再将经过该函数作用过的结果输入到确定性算法组件去执行.由于原算法被分为多个独立组件,因此攻击者需对所有组件一一替换.模块化设计的思想在于增加了攻击者替换原算法的难度,散列函数的作用则在于增加随机数的熵值和不确定性.此外,Alexander 等人在文献[28]基础上提出了“double-split”方法[31,32].该方法在“split-program”划分的基础上,将概率性算法组件分为两个子组件.子组件独立且并发执行,执行结果级联后输入散列函数.后续执行过程与文献[28]类似.

目前,抗盗密密码学只是初具雏形,有关的潜在应用场景还值得进一步研究,譬如利用该方法构造一个collusion-free 的协议[33].此外,该方法主要考虑无状态算法[34].在一些实践中,算法可能是有状态的[28],例如计数器模式加密.如何扩展到有状态的算法,还值得深入研究.

4.3 逆向防火墙

传统防火墙用于内网和外网的隔离,它按照系统管理员预先定义好的规则来控制数据包的进出,以阻挡来自外网的入侵,保障内网的安全.密码逆向防火墙(cryptographic r everse fi rewalls,简称CRF)的概念最初是由Mironov 等人在2015年的欧密会上提出的[35].密码逆向防火墙旨在防止机密信息从内网遭受入侵(密码算法存在算法替代攻击)的主机中泄露出去,其基本思想在于重随机化[36,37−39].密码逆向防火墙的关键在于设计/找到合适的加密算法,该算法能确保公钥/密钥或是密文被重随机化后,接收方仍能正确解密.例如:在公钥密码体制中,发送者用公钥加密生成的密文从内网发出时,为防止加密算法被替换为植入后门信息的算法而破环算法安全性,密文会被密码逆向防火墙重随机化后发给接收者,接收者可直接解密该密文.密码逆向防火墙也可基于公钥/密钥重随机化[40],该类方法旨在抵抗攻击者在公钥中植入后门信息.此时要求选择的加密算法具有密钥可延展性(key m alleable),即,接收者可把使用重随机后的公钥加密的密文映射到用原始公钥加密的密文[41,42].找到拥有这样的可重随机化特性的加密算法并设计相应的密码逆向防火墙,是当下的主要研究内容.

目前为止,密码逆向防火墙仍有一些问题亟待解决,其中包括文献[35]中提到的缺少前向安全性以及相对低效(当下的方案需要对整个明文进行加密).所以,寻找前向安全的高效密码逆向防火墙方案,将成为日后的研究方向之一.

5 总结与展望

抗随机数后门攻击密码算法经过几年的研究,已经取得了一些有意义的成果.本文全方位地就其中的主要成果进行梳理总结,包括抗随机数后门攻击的对称加密算法、对冲公钥加密算法、基于随机性强化的方法以及其他相关技术目前的研究现状,分析了相关构造的特点,并指出目前相关技术研究过程中所面临的问题.总体来说,现有成果大多是从理论层面分析了抗随机数后门攻击的解决方案,而可实现的抗随机数后门攻击的密码算法仍然是需要进一步研究的主要方向.

现有的密码算法大多采用静态密码组件(如密钥生成器、PRNG 等)设计,这增加了算法在实现过程中被植入随机数后门的可能性.动态密码组件的使用,将能更有效地防止攻击者在算法中植入后门.例如,研究动态与交叉动态技术是未来抗随机数后门密码算法的一个研究方向:前者的基本思想在于对消息用多个动态变化的密码算法作用于该消息,并且其中的随机数生成算法使用不同的算法;后者的基本思想在于对多个动态变化的随机数生成算法产生的随机数进行一些运算(如异或等),将运算后的结果用于理论上安全的密码算法中.直观上,这两种技术可有效抵抗随机数后门攻击,然而如何对他们的安全性进行形式化分析还有待探讨.另外,目前抗随机数后门攻击密码算法的研究成果主要集中在加密算法方面,而在密钥协商协议、签名算法、签密算法等方面的研究较少.因此,抗随机数后门攻击的密钥协商协议、签名算法、签密算法等方向都是未来的研究方向.最后,现有的抗随机数后门攻击密码算法大多数只能在随机预言模型下得到证明,在标准模型下可证明安全的抗随机数后门攻击密码算法为数不多.标准模型下,高效的抗随机数后门攻击密码算法还待进一步研究.