密钥泄露保护机制与可证明安全性

1、密钥泄露保护机制与可证明安全,陈克非 kfchen 2012.12.11,主要内容,密钥的泄露问题 主要几种密钥泄露保护方案 前向安全 密钥隔离 入侵回弹 Dodis密钥隔离加密方案 可证明安全基础回顾 密钥隔离的签名方案 并行密钥隔离方案 密钥隔离还可以做的事 可证安全=实际安全？ 几个例子带来的启示,问题的背景,在公钥密码体制中，用户的密钥起着非常重要的地位。密钥的泄漏是一个毁灭性的灾难，意味着将彻底失去系统的安全性保证。 由于病毒、木马或操作系统漏洞等引起密钥泄漏的情况越来越多；对于大量的移动用户，密码设备丢失的情况很难避免，进而导致密钥丢失。 电子现金系统中的密钥泄漏 ： 无法相信密钥

2、泄漏发生之后的未来时间内所有由该密钥所产生的电子现金； 也无法相信此前所有由该密钥所产生的电子现金 。 基于身份的密码体制中的密钥泄漏 ： 用户私钥 的泄漏，意味着对应的身份信息(如身份证号码，电话号码，邮件地址)需要修改，这在现实生活中非常棘手。,注：许多传统的密码使用和管理规定在 “民用密码”环境中很难实施。,基于身份的密码体制,提出：ShamirCrypto84 目的：避免传统公钥密码体制中因管理公钥证书所耗的大量运算代价和通讯开销 特点：用户的身份信息(如邮件地址/身份证号码)作为公钥 例子: 邮件地址作公钥的基于身份的加密系统,master-key,CA/PKG,Alice does

3、 not access a PKI,Authority is offline,Alice,Bob,如何处理基于身份的密钥泄漏问题是一项非常有意义的工作,如何应对密钥泄漏,加大因密钥泄漏而破坏系统安全性的难度： 将整个密钥分成若干个部分密钥并分别存放在多个设备中。这样即使敌手获得个别部分密钥也无法恢复出整个密钥，从而加大了敌手破坏系统安全性的难度 。 可能的技术手段： Secret Sharing Threshold Cryptosystem Proactive Cryptosystem 尽量减轻密钥泄漏带来的危害： 其思想是在保持公钥不变的前提下对密钥采取进化处理，在不同的时间片段内使用不同的

4、密钥。这样就使得泄漏个别时间片段的密钥不会产生全局性的影响，从而减轻密钥泄漏带来的危害。 可能的技术手段： Forward-Security Key-Insulated Intrusion-Resilient,一旦足够份额的部分密钥发生泄漏，系统仍将丧失安全,即使出现密钥泄漏，对系统的危害也可以降到最低,前向安全技术与局限,密钥隔离技术,最早由Dodis等人提出(Eurocrypt 02) 时间分N个片段, 公钥PK固定 引入物理安全”协助器”, 私钥分二部分： 临时私钥：由用户保存, SK0 协助器密钥：由协助器保存, HK 在每个时间片段t的开始： 用户与协助器的交互更新临时私钥 新的临时

5、密钥 SKt = UpdT(t, SKt-1,UIt ) 密钥隔离的安全目标： 在时间片段SKi1, SKi2, , Skit 发生泄漏时， 其它时间片段仍然是安全的,HK,不同类型的密钥隔离,(k, N)密钥隔离 完善密钥隔离(perfect key-insulation) 强密钥隔离(strong key-insulation) 无限制时间片段数目(unbounded number of time periods) 随机密钥更新(random-access key-updates) 安全密钥更新(secure key-updates),在允许最多k个时间片段发生密钥泄漏的前提下，其它N-k

6、 个时间片段仍是安全的。,即(N-1,N)密钥隔离,协助器密钥的泄漏不会破坏系统的安全性,在下面情况下，时间片段t和t之外仍是安全的: 当临时私钥正在从t更新到t时，敌手对用户设备进行内存攻击，从而获得t和t的临时私钥以及其它一些更新信息,系统的时间片段总数目无需在系统建立阶段进行固定,临时密钥能从任意的时间片段t1更新到时间片段t2,密钥隔离技术与局限,入侵回弹的概念,在Crypto02上，Itkis和Reyzin提出了入侵回弹(Intrusion Resilient)的概念 入侵回弹系统在一定程度上将密钥泄漏的风险降至最低,入侵回弹机制与密钥隔离机制有着非常相似。不同的是：在入侵回弹的方案

7、中，协助器密钥本身也需要进行更新操作；,此外，在每一个时间片段内，用户私钥和协助器密钥还可以进行刷新(refresh)操作。,入侵回弹技术的优点,Non-Simultaneous key-exposure,即使协助器密钥和临时密钥都发生了泄漏，只要不是同时发生(simultaneous)，其它未发生密钥泄漏的时间片段仍然是安全的；就算协助器密钥和临时密钥同时发生了泄漏，这也只危害该时间片段及之后的安全性，而并不会危害此前的安全性。,入侵回弹技术与局限,Simultaneous key-exposure,密钥保护的机制总览,Key-Insulated,Intrusion-Resilient,Fo

8、rward-Security,基于身份的加密 体制的前向安全性,Dodis的密钥隔离(加密)方案,在DDH假设下，可以证明方案是语义安全的(semantic security),Y. Dodis et al. Key-insulated public-key cryptosystems Eurocrypt02, LNCS 2332,G: 密钥生成算法,U: 用户密钥更新算法,D: 解密算法,E: 加密算法,U*: 器件密钥更新算法,Dodis的密钥隔离(加密)方案,DDH假设下, 选择密文攻击下安全的密钥隔离方案,基于Cramer-Shoup方案的构造,G: 密钥生成算法,U: 用户密钥更新算

9、法,D: 解密算法,E: 加密算法,U*: 器件密钥更新算法,安全性证明的逻辑:不可区分,例：观察抛掷硬币，一个经典随机试验 硬币抛出前，结果完全不确定|pr(正)-pr(反)|=0 抛出后落地前，结果也许有倾向，但仍然无法确定 |pr(正)-pr(反)|=？ 硬币落地后，结果确定|pr(正)-pr(反)|=1 不可区分性(indistinguishable) 不存在概率多项式时间(ppt)算法区分两个不同事件 即adv= |pr(事件1)-pr(事件2)|=可以忽略 可以忽略意味着： 1/p(n) 例：“好”的随机数生成器G，产生输出应该与均匀分布U的是不可区分的，即不存在一个区分器D：,计

10、算能力受限，无法算出差异,看不出区别(破绽)就是安全,密码的困难问题vs不可区分,Symmetric ciphers AES ciphertexts Ek(m1), Ek(m2), , Ek(mn) PR uniform elements x1, x2, xn 0,1|E| R Finite fields Diffie-Hellman tuple (g, gx, gy, gxy) PR uniform tuple (g, gx, gy, gz) R Integers of the same length two-prime odd composite pq PR uniform odd com

11、posite n R Quadratic residuosity assumption (QRA): square x2 (mod n) (n is a random odd composite) PR uniform y n of positive Jacobi symbol mod n R,问询游戏:寻找蛛丝马迹,Malice和随机预言机O参与不可区分的选择明文攻击 攻击目标为密码体制E，消息/密文空间是M, C O固定E的一个密钥ke 攻击游戏（Malice vs. Oracle）： 1. Malice选m0, 或m1 O 2. Malice c=Eke(m0) if b=0； c=Ek

12、e(m1) if b=1, Oracle 选b=0,1,3. 收到c, Malice回答，0 or 1 Oracle 将Malice看作概率多项式时间(PPT)算法, 称作区分器 (Distinguisher),攻击/安全证明的思路： 试图能否从密码服务中获取有利于破解的信息,目的：测试能否看出不同密文的区别,例：攻击游戏,Adv表示区分Eke(m0)和 Eke(m1)的优势 Adv=|Prob0Malice(c= Eke(m0) - Prob0Malice(c= Eke(m1)| 概率空间包括Oracle, Malice以及E内的随机操作 Malice的猜测是有根据的，不但依赖c，还和m0,

13、 m1有关 改进的随机猜测 根据Oracle是公平掷硬币(概率1/2)来确定猜测值，则 Adv=|Prob0Malice(c) | c= Eke(m0) - Prob0Malice(c)| c= Eke(m1)| = |Prob0Malice(c) | c= Eke(m0) - (1-Prob0Malice(c)| c= Eke(m0)| Prob0Malice(c) | c= Eke(m0)= Adv,事件A: 0Malice(c) 事件B: c= Eke(m0) 概率公式： Pr(AB)=Pr(A|B)Pr(B),例：攻击游戏(续),前面表示一个算法在纯粹的公平硬币投掷(概率1/2)之上的

14、优势 若Adv0，则Malice的概率回答与公平投币有同分布 分析：Malice的优势不超过1/2（因Oracle以1/2 概率加密两个明文之一） 若Oracle以偏概加密（如1/4, 3/4），则 Adv=|1/4Prob0Malice(c) | c= Eke(m0) - 3/4 Prob0Malice(c)| c= Eke(m1)| Malice的优势可能超过1/2 此时，Malice从攻击 游戏中获利，得到正确猜出消息的优势。,优势Adv=的大小：”可忽略(negligible)” (n)是可忽略的，如果正多项式p(n)，N，使得n N时，保持 (n) , 衡量规约差异的数量指标 tig

15、htness gap =(T)/(T),更少的时间里，获得更大的优势,针对不同类型攻击的“游戏”设计,基本的手法：攻击者从收到密文猜测可能的明文 期望的结果：从先验知识和后期学习中得到帮助，以利于判定 攻击的区别：攻击者可以得到不同的密码服务，如选择明文、选择密文、自适应选择密文，。,密码协议是可证明安全：如果可以规约为一个困难数学问题求解，或破解某个密码原语(primitive),更强的安全性,Chosen-Ciphertext Security (Naor-Yung 1990, IND-CCA or lunchtime attack) Adaptive Chosen-Ciphertext

16、Security (Racko-Simon 1991, IND-CCA2 or small-hours attack, strongest and standard attacking model) 例：RSA-OAEP (Optimal Asymmetric Encryption Program,Bellare-Rogaway 1994) Randomised hash function padding combines the RSA function, mix different algorithmic structures to destroy nice algebraic prope

17、rties (such as multiplicativity) of the RSA function Output ciphertext is pseudo-random (IND) With added redundancy for integrity validating (CCA2) Reductionist proof of security based on Random Oracle RSA-OAEP是不多的IND-CCA2安全的实用密码体制,基于身份的密钥隔离签名IBKIS,将密钥隔离机制应用到基于身份的签名中，得到基于身份的密钥隔离签名(IBKIS)的概念 一个IBKIS方

18、案由如下六个算法组成：,IBKIS的安全模型-(k, N)密钥隔离安全,IBKIS的安全模型-强密钥隔离安全,IBKIS的安全模型-强密钥隔离安全,一个IBKIS方案,IBKIS方案的安全性(I),IBKIS方案的安全性(II),密钥隔离机制难以应对的场合(I),Dodis所提的密钥隔离机制难以应对某些场合：,为了减小发生密钥泄漏后的危害,将密钥更新的周期设置得尽可能短些,增加协助器暴露于不安全环境的机会,增加协助器密钥发生泄漏的几率,未达到强密钥隔离安全的方案：意味着该用户的所有临时私钥也发生泄漏！ 满足强密钥隔离安全的方案：只要再有一个临时私钥发生泄漏，该用户的所有临时私钥也发生泄漏！,密

19、钥隔离机制难以应对的场合(II),Home,Office,每天上午在家更新一次密钥,每天下午在办公室更新一次密钥,频繁的密钥更新，增加了协助器发生泄漏的机会！ 往返携带协助器，也增加了协助器发生泄漏的机会！,新的机制并行密钥隔离,为了应对Dodis密钥隔离机制难以适合的某些情况，日本学者Hanaoka等人在PKC06上提出 引入两个不同的协助器，交替更新临时私钥,Home,Office,每天上午在家更新一次密钥,每天下午在办公室更新一次密钥,即使更新频率增加为原来的两倍,协助器发生泄漏的几率仍不变 不用往返携带协助器，因而不会增加协助器发生泄漏的几率,(1)某些时间片段的密钥泄漏并不危害其它时

20、间片段的安全性； (2)在其中一个协助器发生密钥泄漏的前提下，即使某些时间片段的临时私钥发生了泄漏，其他时间片段仍安全； (3)即使两个协助器发生了泄漏，只要不发生临时私钥泄漏，所有时间片段内仍然安全,并行密钥隔离(II),Hanaoka等学者的并行密钥隔离机制只针对传统公钥密码体制 Hanaoka等学者构造的并行密钥隔离公钥加密方案只在随机预言机模型下可证明安全,能否将并行密钥隔离机制扩展到基于身份的密码体制中？ 能否构建一个基于身份的并行密钥隔离加密方案，并且在标准模型下可证明安全,基于身份的并行密钥隔离加密(IBPKIE),IBPKIE的安全模型-IND-ID-PKI-CCA2,IBPK

21、IE的安全模型-IND-ID-PKI-CCA2,IBPKIE的安全模型-IND-ID-sPKI-CCA2,IBPKIE方案的构建(I),平凡的尝试 直接把两个基于身份的密钥隔离加密(IBKIE)方案组合在一起，似乎就能构造出一个IBPKIE方案。,进行临时私钥更新时需要同时(而不是交替)使用两个协助器。 这样, 当临时私钥的更新频率增为原系统的两倍时，每个协助器密钥发生泄漏的几率也为原系统的两倍！,IBPKIE方案的构建(II),IBPKIE方案的安全性,密钥隔离还能做的事,针对不同安全模型下的密钥隔离机制 基于身份的密码 基于身份的密钥隔离加密 基于身份的密钥隔离签名 基于属性的密码 基于身

22、份的密钥隔离加密/签名 基于属性的密钥隔离加密/签名 基于属性的并行密钥隔离加密/签名 通用密钥隔离机制 给定一个密码算法转换成密钥隔离算法 不依赖于原算法的具体构造 其它。,基于身份的密钥隔离签密,另一只眼看“可证安全”,实例分析,同样得到”可证明”安全的情况下，由于规约“紧”的程度不同，得到的”实际安全性”效果可能有很大差异。 例：RSA签名 假设允许伪造者可以询问qsig = 230个签名，可以做qhash = 260个哈希询问，则即使求出RSA 的逆的概率是2-61这样小，按照上述结论我们能下的断言也只是说伪造者成功的概率为=q=(qsig + qhash) 这显然是不够的，因为这样的

23、保证是没有任何安全性可言的 为使得伪造者成功的概率尽可能的小，我们不得不要求尽可能的小，比如2-100，但这就意味着安全参数k要尽可能的大，即模数尽可能的大，这就影响了方案的有效性。,可证明安全实际安全？,一方面，可证明安全性得到越来越多的认可 没有经过可证明安全的新方案很难得到认可，RSA-OAEP已经成为工业标准 另一方面，可证明安全性到底能起多大作用一直有争议 有些可证明安全的密码，在实际中未必安全 Another Look at Provable Security Alfred Menezes在Eurocrypt 2012的特邀报告 http:/www.cs.bris.ac.uk/eu

24、rocrypt2012/Program/Weds/Menezes.pdf 从三个方面讨论了可证明安全性的问题 Tightness of the proof; Multi-user setting; Non-uniform complexity model.,证明中安全规约的紧致性,例(Menezes): Bellare-Rogaway proof for RSA-FDH (Full Domain Hash) in the random oracle model has a tightness gap of q Let the RSA modulus N be a 1024-bit intege

25、r. Assumption: The RSA problem cannot be (T, )-solved for T/ 280. Suppose that a (T, )-forger A of RSA-FDH makes at most q = 260 hash-queries. Then Bellare-Rogaway proof uses A to (T, /260)-solve the RSA problem Conclusion: RSA-FDH is (T, )-secure for T/ 220. The tightness gap is 260,多用户的消息认证码MAC,设

26、Hk : 0, 1 0, 1t 是MAC, 其中 k 0, 1r. MAC1不安全：没有密钥能产生”m, Hk(m)”对. 考虑多用户(multi-user setting)时MAC*的不安全 Let k1, k2, . . . , kn R 0, 1r. The adversary A has access to oracles for Hki . Her task is to produce (i,m, ), where 1 i n, Hki(m) = , and m was not queried to Hki 已知结果: if MAC1 is (T, )-secure, then MA

27、C* is (T, n )-secure. The tightness gap is n.,证明安全，但其实不安全,例:CMAC (Cipher-based MAC) 80bit keys,80bit tags, 用户数n=220. Choose密钥子集w=260, so that the attack takes time 260. Time-memory trade-off: With an offline computation of 260MAC computations, and 240 storage units, the adversary can find one of 220

28、 keys with an on-line search time of 240. Note: Speedup over the generic key-finding attack on MAC1 is by n. This is the nightmare scenario since the tightness gap translated to an actual practical attack. 此外，还有大量的例子，单用户应用是安全的，多用户情况则不然。,Non-Uniform Complexity Model,考虑HMAC-MD5 f : 0, 1128 0, 1512 0,

29、1128 ，MD5的压缩函数 HIV : 0, 1 0, 1128 ，MD5的迭代函数 定义NMACk1,k2(m) = f(k1,Hk2(m)0)，HMAC是单钥特例. 有关安全性的一些结果 Bellare-Canetti-Krawczyks (1996) security proof for NMAC (as a MAC scheme) assumed (i) f is a secure MAC scheme; and (ii) H is collision resistant. Wangs (2005) collision finding algorithm for MD5 render

30、ed the proof useless as a security guarantee for NMAC-MD5. Bellare (2006) gave a new proof for the security for NMAC as a pseudorandom function (prf). The proof only assumed that f is a secure prf.,Bellares proof in practice,可证明安全的思考,可证明安全仍然是重要的，至少是目前难得的一种见安全性定量化的方法； 安全性证明过程中的规约尽可能做得“紧”，松散的规约即使证明了“安

31、全性”，其“安全性”的实际意义会打折扣； 在进行安全性证明时，特别注意基本假设中的“困难问题/密码原语”的适用环境与要证明问题之间的差异； 现代密码设计离不开可证明安全性，但千万不要迷信被证明“安全性”的结果。,密码在云数据安全中应用,云计算环境下，数据应该以密文方式存放在数据中心 需要解决的问题有 1.用户可验证所存放数据的完整 2.支持加密云数据的高效检索 3.实现有条件加密云数据共享 可以采用的关键技术 1.数据可回取证明协议POR 数据抽查，大概率证明数据完整 2.可搜索加密和密文搜索 保持明/密文同态关联；搜索引擎结合基于密码的访问控制 3.代理条件转换加密 不需解密，将密文转成另一

32、些指定人群能够解密的数据,用密码技术解决云环境下数据安全与隐私，确保 “存得放心”、 “找得快速”、“用得方便”,某咨询公司为用户提供大量咨询报告，要求只有授权用户可以在线检索到相关的报告，进而浏览或下载。 挑战性问题： 数据数量巨大 实时访问权限 动态权限管理 任务目标：具有权限控制的搜索引擎,实例：一种带权限控制的搜索引擎,利用属性加密(ABE)实现对密文授权管理 不同用户对应不同属性：级别,部门,岗位,职责 不同属性组合出（逻辑运算）不同权限 不同权限对应不同的解密能力 根据解密能力反映出搜索到的内容不同,基本思路： 用户属性 解密能力 存取权限 搜索到不同的数据,Host,file storage,Data Center,User,Attribute Management Encryption Center File Search Center,You can see 4 buttons under the search box, some of them are for test: 1. Normal search: normal full