彭峙酿 使用全同态加密构造数据安全方案的安全风险

CodeWarrior

2019/07/08 发布于 编程 分类

GIAC2019 

文字内容
1. 使用全同态加密构造数据安全方案 的安全风险 彭峙酿 360 漏洞挖掘与利用高级专家
3. 大纲 介绍全同态密码 介绍全同态密码库SEAL 全同态密码库的安全问题(SEAL为例) 针对全同态密码的CCA攻击 针对PSI协议的数据恢复攻击 全同态密码的电路隐私问题 编码安全问题 解决办法 其他问题 总结
5. 密文域处理 数据安全问题变得越来越严峻 数据安全、隐私已成为公众关心的重要问题 各国政府出台相应的法律 能否运用加密技术解决问题 将数据加密后再发送给云端 允许云在加密的数据上进行:搜索/修改/处理 数据 数据在云端始终保持加密状态 云服务器无法解密数据内容
6. 密文域处理 加密请求处理 用户加密查询请求给云端 允许云处理用户的请求 云端返回加密的处理结果 用户解密得到结果
7. 同态加密:加法同态 a, b a+ b 相加 加密 加密 E(a), E(b) 相加 E(a) RSA加密支持同态加法 E(b) E(a+b)
8. 同态加密:乘法同态 a, b axb 相乘 加密 加密 E(a), E(b) 相乘 E(a) E(b) Elgamal加密算法支持同态乘法 E(ab)
9. 全同态加密 x1, …, xn F(x1,...,xn) 计算 加密 加密 E(x1),…, E(xn) 计算 F(E(x1),…, E(xn))=E(f(x1,…xn)) 2009年,gentry设计出第一个全同态加密算法
10. 使用同态加密保护数据:比喻 1. 把金子放进玻璃箱 2. 锁住箱子,藏起钥匙 3. 让工人隔着手套操作 4. 解锁箱子,得到珠宝
11. 同态加密的应用场景 外包计算 对加密数据的机器学习 云存储,云计算服务 可以分为两类: 数据隐私,函数公开 数据隐私,函数也隐私
12. 数据隐私, 函数公开 数据要求保持隐私 要计算的函数是公开的
13. 疾病预测 数据隐私, 函数公开 所有数据使用病人的密钥进行加密 云端根据医生的要求进行加密数据计算 云端将加密的预测结果返回给病人
14. 数据隐私, 函数隐私 数据和函数都需要保持隐私 电路隐私: 要求同态密码方案能够保持要计算的函数f的隐私性
15. 全同态密码库
16. SEAL介绍 微软研究院发布、维护的全同态密码库 2015年首次发布,目前版本为3.3 地址:https://GitHub.com/Microsoft/SEAL 标准C++开发 两种全同态方案:BFV和CKKS 简单易用 有详细的用例和注释
17. SEAL性能 CryptoNets (2016) MNIST手写数字图片识别 每小时6万识别,16个每秒 99%+的准确率 FPGA、GPU可再提速100-1000倍 我们的实验 逻辑回归预测 5分钟处理1万数据 相比直接使用sklearn慢300倍 一亿个0到100的浮点数相加 860毫秒;8倍明密文扩展
19. Ring-LWE问题 多项式环 R=Zq[x]/(x^n+1) 给定: a1, b =a1 · s+e1 a2, b2=a2 · s+e2 … ak, b3=ak · s+ek 1 要求找到: s s是R上的随机值 ei 非常小 为了便于理解,可认为所有变量为 整数
20. 判定性Ring-LWE问题 多项式环 R=Zq[x]/(x^n+1) 给你: a1, b1 a2, b2 … ak, bk 挑战: 是否存在s 和足够小的 e1, … , ek 满足bi=ai · s+ei
21. BFV方案密钥生成 私钥生成: 随机抽样私钥 s∈ χ 公钥生成(s): 随机抽样 a ∈ Rq, e ∈ χ pk0 = −(a · s + e) pk1= a Ring-LWE对 s 无法被解出
22. BFV加密 encrypt(m): 抽样 u ∈ Rq , e1 e2 ∈ χ c0= pk0 · u + e1 + ∆ · m, c1= pk1 · u + e2 替换 pk为 (−(a · s + e), a) c0= −(a · s + e) · u+e1+ ∆ · m, c0 =-w · s +e1+e · u+ ∆ · m , 判定性Ring-LWE 对 (无法与随机值区分) 可认为消息被随机值混淆 换一种形式看密文: f(x)=c0+c1*x c1= a · u + e2 c1= w + e2
23. Decrypt(c): BFV解密 f(x)=c0+c1 · x 替换 x 为 s f(s)=c0+c1 · s 替换 c 为 =([-w · s +e1+e · u+ ∆ · m ]q, [w + e2]q) f(s)=-w · s +e1+e · u+ ∆ · m + (w + e2) · s =e1+e · u+e2 ·s+ ∆ · m 远小于∆ 可恢复出m 简单结论: f(s)= v + ∆ · m 其中 v 远小于 ∆
24. 同态加法 同态加法: 密文1: f1(x) 密文2: f2(x) 相加: f3(x)=f1(x)+f2(x) 因为: E(m ) f1(s)=v1+ ∆ · m1 f2(s)=v2+ ∆ · m2 那么f3(x): f3(s)=f1(s)+f2(s)=v1+v2+ ∆ · (m1+m2) =v3+ ∆ · (m1+m2) 1 E(m2) E(m1+m2)
25. 同态乘法 同态乘法: 密文1: f1(x) 密文2: f2(x) 相乘: f3(x)=f1(x)*f2(x) 因为: f1(s)=v1+ ∆ · m1 E(m1) E(m2) f2(s)=v2+ ∆ · m2 那么f3(x): f3(s)=f1(s)*f2(s)=v1 · v2+ ∆ · (v1 · m2+ v2· m1)+∆2 · m1 · m2 除以 ∆ : f3(s)/ ∆= v3+ ∆2· (m1 · m2) E(m1·m2)
26. 以上是简化版本的BFV算法 但足够让我们理解全同态的问题 更多BFV算法的细节 Brakerski, Z.: Fully homomorphic encryption without modulus switching fro classical gapsvp. In: CRYPTO 2012 - Volume 7417. pp. 868–886 (2012) Fan, J., Vercauteren, F.: Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, Report 2012/144 (2012) 简化版的BFV: https://github.com/edwardz246003/danger-of-using-homomorphicencryption/blob/master/BFV.py
27. BFV方案安全问题 将消息m加密为多项式f(x) 将s带入来进行解密 f(s)=v+Δ · m 消息被Ring-LWE对混淆 能够区分密文 → 能够解决 Ring-LWE问题 可证明安全: IND-CPA → Ring-LWE 选择明文攻击 如果能再IND-CPA模型下攻破BFV,则能攻破Ring-LWE
28. IND-CCA? 选择密文攻击 攻击者能够访问解密机 BFV 并不能抵抗IND-CCA攻击 所有的实用全同态方案都不能抵抗IND-CCA攻击 全同态的性质看上去与IND-CCA冲突 关于IND-CCA的全同态方案的理论研究 Chosen-Ciphertext Secure Fully Homomorphic Encryption 没有全同态密码方案能够在IND-CCA模型下保证安全
29. IND-CCA 为什么需要IND-CCA 在很多场景中,攻击者能访问解密机 IND-CCA目前已经是加密算法的标准需求 全同态密码的应用场景通常更需要IND-CCA安全 外包计算看似处于CPA模型 用户和云端之间有丰富的数据流动 多方参与和数据交换 任何解密后的数据流向云端: 将打破CPA模型, 需要 CCA 安全!
30. 单次查询攻击 假设攻击者可以查询解密机一次 这在很多场景中合理 攻击者要求解密恶意密文f(x) f(x)=c0+c1x 其中 c0=0, c1=Δ 解密机带入s 得到: f(s)=Δs 得到密文:s (密钥) 攻击者可通过单次解密查询,恢复密钥 非常危险 其他的全同态方案面临相同的问题 https://eprint.iacr.org/2014/535
31. 攻击示例 https://github.com/edwardz246003/danger-of-using-homomorphicencryption/blob/master/CCA_attack.py
32. 解决办法 不要在任何明文数据会泄露给操作者的场景中使用 全同态密码 否则,相当于没有加密。 如何才能确保没有数据泄露? SEAL中将加入新的缓解措施。
33. 私有集合交集计算(PSI) 不泄露任何其他信息
34. 应用: 私有通讯录匹配 私有通讯录匹配在端到端加密的通讯软件上 如signal
35. 使用同态密码构造PSI(CCS17) 本地数据库Y 加密通讯录X 发送加密后的X给服务器 与本地数据库Y,进行同态计算 得到加密后的X∩Y 发送加密后的X∩Y 给用户 解密得到X∩Y
36. 该场景下的CCA攻击 将X∩Y 明文发送给服务器 用户得到X∩Y后 发现X∩Y 在使用signal 添加他们为好友 信息泄露 服务器可发起CCA攻击! 客户与服务器之间总是有很多不经意的数据流 使用全同态密码要十分小心
37. 1比特信息泄露的后果 与之前的CCA attack 用户会检查解密结果是否为0 只会泄露1比特信息给服务器 可以使用1比特信息泄露恢复1比特密钥 攻击者无需查询解密机 任何1比特信息泄露,将转换成1比特密钥泄露 全同态密码方案的安全性将指数下降 1比特信息泄露在显示生活中不可避免
38. 攻击实例(1比特信息泄露) Any 1bit information leakage will lead to 1 bit key leakage https://github.com/edwardz246003/danger-of-using-homomorphicencryption/blob/master/CCA_attack.py
39. 其他攻击 本地数据库Y 使用全同态加密X 发送加密的X给服务器 计算得到加密的X∩Y . 大多数HE没有 发送加密的X∩Y给呵护 客户解密得到X∩Y 也会得到Y的信息
41. SEAL的电路隐私 SEAL 不提供电路隐私 SEAL手册中有提及 最佳实践:噪音混淆 给计算结果添加足够的噪音 SEAL中没有噪音混淆的标准接口 普通程序员无法实现噪音混淆 提供噪音混淆的困难性 需要知道我们到底需要多少噪音,这实际上也是需要 保护的信息:( 电路隐私问题目前是全同态密码方案的通用性问题 没有通用性的解决方案
42. 解决办法 修正版的PSI 协议(CCS2018) https://eprint.iacr.org/2018/787 解决PSI问题(非通用性解决方案) 对于全同态密码的电路隐私问题 目前需要密码专家来审计具体实现 格密码方面的专业知识 SEAL 团队考虑提供一个通用接口
43. SEAL中的编码信息泄露 全同态方案在多项式环上工作 要处理的明文通常是:数字、字符串 需要将他们转换到多项式环上 SEAL的编码方案(IntegerEncoder) 将整数编码到多项式环上 多与一映射 信息泄露!
44. 整数编码问题示例 百万富翁问题: https://github.com/edwardz246003/danger-of-using-homomorphicencryption/blob/master/millionaire.py
45. 解决办法 编码问题也影响其他全同态方案 密码方案可能有安全证明, 但是编码方案没有 不要使用SEAL的整数编码器(不理解安全模型时) IntegerEncoder 只能认为是一个实例工具 可以使用BatchEncoder 和 CKKSEncoder
46. 其他安全问题 全同态加密方案不能提供常见的加密安全属性 全同态加密方案不是可认证加密方案 不能保证数据的完整性 攻击者可以利用全同态性质修改数据内容 不要使用全同态加密直接进行数据传输、数据存储 全同态密码需要标准 微软目前在做相关标准 建议将安全协议相关内容纳入
47. 全同态可以计算任意函数? x1, …, xn F(x1,...,xn) 计算 加密 加密 E(x1),…, E(xn) 加密 F(E(x1),…, E(xn))=E(f(x1,…xn)) 任意函数在全同态中意味着:任意的加法和乘法 任意的加法和乘法,并不表示你可以在数据上运行任意程序 你不能直接进行数据对比 (不支持if语句)
48. 更新比喻 1. 把金子放进不透明的箱子 2. 锁住箱子,藏起钥匙 3. 让工人隔着手套操作(蒙上眼罩) 4. 解锁箱子,得到珠宝
49. 总结 全同态密码在具有很好的应用场景 近年来性能提高了很多 全同态密码并非万能的 它不能计算任意的函数 使用全同态密码会有很多安全隐患 现阶段没有安全易用的基础库 实现需要被密码专家审计 实际应用比学术论文的模型更复杂,安全问题更严峻 密码社区需要更多关注具体场景中的安全问题
50. 致谢 感谢 Kim Laine of Microsoft Research Chen Hong of Alibaba Gemini Lab 对本议题的帮助与建议
51. 谢 谢!
52. 欢迎关注msup微信公众账号 关注大会微信公共账号,及时了解大会动态、 日程及每日更新的案例! 关注公众号获得 更多案例实践