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

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

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/NBP2iIND-CDA2,
IND-CDA2iNBP1/NBP2.Huang 等人表示,第 3.1 节介绍的 nonce-based 公钥加密算法即可视作在随机预言模
型下 HN-PKE 的算法构造.他们着重研究了 nonce-based 公钥加密算法的对冲安全性质,证明结果表明,nonce-
based 公钥加密算法在随机预言机模型下满足 IND-CDA2 安全性.
另外,Huang 等人考虑了 HN-PKE 在标准模型下的算法构造,并提出了一个具体的 NtD(nonce-then-
[3]
deterministic)加密算法 .所谓的 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 加密算法介绍如下.
k
k
k
• 密钥生成算法 NDKg(1 ):输入安全参数 1 ,首先运行 N-PKE 算法的密钥生成算法 NKg(1 )→(pk n ,sk n ),
k
生成 N-PKE 算法的公私钥对;其次运行 D-PKE 算法的密钥生成算法 DKg(1 )→(pk d ,sk d ),生成 D-PKE
算法的公私钥对;最后输出 NtD 算法的公钥 pk=(pk n ,pk d ),私钥 sk=(sk n ,sk d );
k
k
k
• 种子生成算法 NDSKg(1 ):输入安全参数 1 ,运行 N-PKE 算法的种子生成算法 NSKg(1 )→xk,输出种子
密钥 xk;
• 加密算法 NDEnc pk (M,n,xk):输入公钥 pk=(pk n ,pk d )、消息 M、一个 nonce 值 n,先运行 N-PKE 算法的加
密算法 NEnc(pk n ,xk,M,n)→y,再运行 D-PKE 算法的加密算法 DEnc(pk d ,y)→C,输出密文 C,其中,nonce
由 NG 产生;
• 解密算法 NDDec sk (C):输入私钥 sk=(sk n ,sk d )和密文 C,先运行 D-PKE 算法的解密算法 DDec(sk d ,C)→y,
再运行 N-PKE 算法的解密算法 NDec(sk n ,y)→M,输出消息 M.
证明结果表明:当确定性加密算法 DPKE=(DKg,DEnc,DDec)在标模下满足适应性 CCA 安全性时,NtD 算法
在标模下满足 NBP1,NBP2,IND-CDA2 安全性.
3.3 Dodis随机数生成算法
在文献[5]中,Dodis 等人详细介绍了 Dual EC PRNG 中后门攻击的原理.同时,他们表示,可以用密钥封装算
法和公钥加密算法来构造 BPRNG.即,将密钥封装算法和公钥加密算法的输出看作 BPRNG 生成的随机数.
除此之外,他们还提出了一种用于增强 PRNG 输出随机性的函数,将该函数定义为“免疫”函数,用 f seed 表
示.“免疫”函数的工作原理是:将可能存在后门的 PRNG 生成的可能不安全的可预测随机数做为“免疫”函数 f seed
的输入,将函数 f seed 的输出作为最终的随机数.
这种情况下,如何判断“免疫”函数作用的有效性是个重要问题.文献[5]中给出了一种验证方法:存在一个攻
击者 A,他试图构造一个带有后门的 PRNG,然后使用“免疫”函数 f seed 对该 PRNG 进行免疫.如果 A 能成功构造一
个带有后门的 PRNG,并绕过 f seed ,则表明函数 f seed 为无效免疫;否则,表明 f seed 有效免疫.在这个验证过程中,根据
攻击者已知“免疫”函数 f seed 相关信息的程度不同,Dodis 等人将免疫模型分为 3 种:公开免疫模型、半隐私免疫
模型和隐私免疫模型.其中:公开免疫模型是指攻击者 A 构造带有后门的 PRNG 之前就已知函数 f seed 的 seed 值,
也就是说,攻击者已知函数 f seed ;半隐私免疫模型是指 A 构造带有后门的 PRNG 之后才已知 seed;隐私免疫模型
是指 A 构造带有后门的 PRNG 前后都未知 seed.Dodis 等人的研究结果表明:在公开免疫模型下,存在后门的
PRNG 是不能被免疫的,即不存在免疫函数 f seed .在半隐私免疫模型下,Dodis 等人分别考虑了针对随机预言模型
和标准模型的免疫函数.他们指出:在随机预言模型下,可将随机预言机 RO(random oracle)看作免疫函数,即
f seed =RO;在标准模型下,可用通用计算萃取器 UCE(universal computational extractor)作为免疫函数,即 f seed =UCE;
在隐私免疫模型下,Dodis 等人指出:可将伪随机函数 PRF 作为免疫函数,即 f seed =PRF.