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

2020-03-01 273浏览

  • 1.使用全同态加密构造数据安全方案 的安全风险 彭峙酿 360 漏洞挖掘与利用高级专家
  • 2.
  • 3.大纲 介绍全同态密码 介绍全同态密码库SEAL 全同态密码库的安全问题(SEAL为例) 针对全同态密码的CCA攻击 针对PSI协议的数据恢复攻击 全同态密码的电路隐私问题 编码安全问题 解决办法 其他问题 总结
  • 4.
  • 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倍明密文扩展
  • 18.
  • 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 leakagehttps://github.com/edwardz246003/danger-of-using-homomorphicencryption/blob/master/CCA_attack.py
  • 39.其他攻击 本地数据库Y 使用全同态加密X 发送加密的X给服务器 计算得到加密的X∩Y . 大多数HE没有 发送加密的X∩Y给呵护 客户解密得到X∩Y 也会得到Y的信息
  • 40.
  • 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微信公众账号 关注大会微信公共账号，及时了解大会动态、 日程及每日更新的案例！ 关注公众号获得 更多案例实践