Page 265 - 《软件学报》2021年第9期

康步荣 等:抗随机数后门攻击的密码算法 2889

16
将每一种可能性记做 X i ,i∈{1,…,2 }.然后,攻击者计算检验 Q i X d 去掉最后 16 位的值后剩余位的值是否等于 r 2
1 s
的值:如果相等,他可以继续计算 P = Q s 1 d = X = d i s ,从而成功恢复出状态值 s 2 .一旦攻击者恢复出正确的状态值
2
16
s 2 ,他就可以推算出所有后续的状态值和随机数.此次随机数后门攻击最多需要做 2 次运算,这对一个攻击者来
说不难做到.
随着 Dual EC PRNG 后门事件的曝光,如何构造抵抗随机数后门攻击的密码算法,已逐渐成为密码学界广
泛关注的一个重要话题.近几年,对于抗随机数后门攻击的密码算法的研究已经取得了一些有意义的结果,出现
了各种抗随机数后门攻击的对称和公钥密码算法.本文就其中的主要结果进行了总结整理,从抗随机数后门攻
击的对称加密算法、对冲公钥加密(hedged public-key encryption,简称 H-PKE)、基于随机性强化的方法、算法
替代攻击等几个研究方向分析了目前抗随机数后门攻击密码算法的研究现状.通过分析已有相关构造的特点,
我们指出,现有密码算法大多采用静态密码组件(如密钥生成器、PRNG 等).由于密码组件固化,这增加了算法设
计者在设计算法时有意隐藏后门的可能性.鉴于这一发现,本文探讨将交叉动态思想引入密码算法设计之中,实
现密码组件的动态组合优化;构造新型抗后门攻击密码算法,以达到抵抗后门攻击的目的.下面,我们对这些方
法逐一进行概括与分析.
本文第 1 节介绍随机数后门攻击对密码算法的安全威胁和几种造成随机数后门攻击的原因.第 2 节~第 5
节分别从抗随机数后门攻击的对称加密算法、对冲公钥加密算法、基于随机性强化的方法以及其他相关技术
等方面归纳相关研究方法的主要思想,并对各方法中需要进一步研究的问题进行分析.第 6 节对全文进行总结
与展望.

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

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

Kamara-Katz 系列对称加密算法在 2008 年由 Kamara 和 Katz 提出 [17] ,他们定义了两种新的对称加密算法
的安全性质:CRA(chosen-randomness attacks,简称 CRA)安全性和 CCRA(control chosen-randomness attacks,简称
CCRA)安全性.CRA 安全性是指:即使敌手能询问加密预言机并完全控制算法中使用的随机数生成器,敌手也不
能在多项式时间内恢复出给定密文所对应明文的任意部分信息.同时,作者还分析了 CRA 安全性和 CPA 安全性
的关系 [17] .由于 CRA 安全性允许敌手完全控制算法的随机数生成器,所以严格意义上,CRA 安全性比 CPA 安全
性更强.CCRA 安全性是指:即使敌手能询问加密预言机、解密预言机并完全控制算法中使用的随机数生成器,
敌手也不能在多项式时间内恢复出给定密文所对应明文的任意部分信息.同样,他们将 CCRA 安全性和 CCA
(chosen ciphertext attack,简称 CCA)安全性进行了对比 [17] .由于 CCRA 安全性允许敌手完全控制随机数生成器,
所以本质上,CCRA 安全性比 CCA 安全性更强.Kamara-Katz 系列对称加密算法(symmetric key encryption,简称
SKE)包括 SKE1 与 SKE2 [17] .
SKE1 为抗随机数后门攻击的固定长度输出的对称加密算法,所谓固定长度是指被加密的明文消息及所对
应密文的长度为固定值.该算法基于伪随机置换和伪随机函数构造.下面介绍 SKE1=(Gen,Enc,Dec)的具体算法.
k
k
• 密钥生成算法 Gen(1 ):输入安全参数 k,该算法选取 K 1 ,K 2 ←{0,1} ,输出对称密钥 K=〈K 1 ,K 2 〉;
k
• 加密算法 Enc K (m,r):输入要加密的消息 m、随机数 r←{0,1} 和对称密钥 K=〈K 1 ,K 2 〉,计算 c 2 =
c
F K 2 ()r ⊕ m ,输出密文 C = 〈= P K 1 (),r c 〉 .其中,F 表示伪随机函数,P 表示伪随机置换,F 和 P 的输入输出
2
1
都为 k 比特的固定长度;
• 解密算法 Dec K (c 1 ,c 2 ):输入密文 C=〈c 1 ,c 2 〉和对称密钥 K=〈K 1 ,K 2 〉,该算法计算 r = P − 1 ()c ,输出消息
K 1 1