内在 ID PUF:后量子不确定性的解毒剂
您最近可能听说过很多关于量子计算对密码学的威胁。 如果是这样,您可能还有很多关于这种“量子威胁”是什么以及它将如何影响您的加密解决方案的问题。 让我们来看看有关量子计算及其对密码学的影响的一些最常见问题。
什么是量子计算机?
量子计算机不是速度非常快的通用超级计算机,也不能神奇地以大规模并行方式运行。 相反,它有效地执行独特的量子算法。 这些算法在理论上可以比任何传统计算机更有效地执行某些非常具体的计算。
然而,开发一台有意义的量子计算机,即在实践中可以胜过现代传统计算机的计算机,是异常困难的。 量子计算技术自 1980 世纪 2010 年代以来一直在发展,自 15 年代以来逐渐完善可操作的量子计算机。 然而,即使将当前的技术水平外推到未来,并假设传统计算机的指数级改进相当于摩尔定律,专家估计至少还需要 20 到 XNUMX 年才能使有意义的量子计算机成为现实。1,2
密码学的量子威胁是什么?
在 1990 年代,人们发现一些量子算法会影响某些传统密码技术的安全性。 两种量子算法引起了关注:
- Shor的算法,由 Peter Shor 于 1994 年发明,是一种有效的量子算法,用于分解大整数,并用于解决一些相关的数论问题。 目前,传统计算机还没有已知的有效因式分解算法,这一事实为几种经典的公钥加密技术提供了安全基础。
- 格罗弗算法,由 Lov Grover 于 1996 年发明,是一种量子算法,可以比传统计算机更快地二次方搜索通用函数的反函数。 在密码学术语中,搜索逆等同于暴力攻击(例如,对未知的密钥值)。 此类攻击的难度构成了大多数对称密码学原语的安全基础。
如果这些量子算法可以在有意义的量子计算机上执行,它们将影响当前密码技术的安全性。
对我的公钥加密解决方案有何影响?
到目前为止,当今最重要和最广泛使用的公钥原语是基于 RSA、离散对数或椭圆曲线密码学的。 当有意义的量子计算机开始运行时,所有这些都可以通过 Shor 算法有效地解决。 这将使当前使用的几乎所有公钥密码术都不安全。
对于受影响的公钥加密和密钥交换原语,这种威胁今天已经真实存在。 攻击者捕获并存储现在(或过去)交换的加密消息,可以在未来有意义的量子计算机运行时解密它们。 因此,直到今天传达的高度敏感和/或长期秘密已经处于危险之中。
如果您在不到 15 年的短期承诺中使用受影响的签名原语,则问题不那么紧迫。 然而,如果有意义的量子计算机可用,任何签名的价值将从那时起作废。 因此,您不应使用受影响的原语来签署仍需要在 15-20 年或更长时间内验证的长期承诺。
在过去的十年中,密码学社区设计了新的公钥基元,这些基元基于 Shor 算法(或任何其他已知的有效算法,量子或其他算法)无法解决的数学问题。 这些算法通常被称为后量子密码学。 NIST 最近宣布了对这些算法的选择以进行标准化。3
对我的对称加密解决方案有何影响?
设计良好的对称密钥原语的安全级别等同于暴力破解密钥所需的努力。 在传统计算机上,暴力破解密钥的工作量与密钥长度成正比。 当可以使用有意义的量子计算机时,Grover 算法可以二次方地加速蛮力攻击。 所需的努力仍然是指数级的,尽管只是密钥长度的一半。 因此,可以说 Grover 算法将任何给定长度算法的安全性降低了 50%。
但是,请记住一些重要事项:
- Grover 算法是一种最佳的蛮力策略(量子或其他),4 所以二次加速是最坏情况下的安全影响。
- 有强烈的迹象表明,不可能对 Grover 算法的执行进行有意义的并行化。2,5,6,7 在传统的暴力攻击中,使用的计算机数量加倍将使计算时间减半。 这种缩放对于量子计算机上的 Grover 算法是不可能的,这使得它在暴力攻击中的使用非常不切实际。
- 在 Grover 算法可用于对 128 位密钥执行现实世界的暴力攻击之前,量子计算机的性能必须得到极大提高。 非常现代的传统超级计算机几乎无法在实际可行的时间内(几个月)执行 128/2=64 位复杂度指数的计算。 根据他们目前的状态和进展速度,量子计算机要达到同样的水平还需要 20 多年的时间。6
目前,量子计算机对对称密码学的实际影响非常有限。 最坏的情况是,当前使用的原语的安全强度降低了 50%(其密钥长度),但由于 Grover 算法的局限性,这是对不久的将来过于悲观的假设。 将对称密钥的长度加倍以抵御量子暴力攻击是一种非常广泛的一揽子措施,肯定会解决问题,但过于保守。 今天,没有针对量子强化对称密钥加密的强制性建议,并且 128 位安全强度原语(如 AES-128 或 SHA-256)被认为现在和可预见的未来都可以安全使用。
对信息理论安全有影响吗?
信息论安全方法(也称为无条件或完美安全)是安全声明在数学上得到证明的算法技术。 一些重要的信息理论上安全的构造和原语包括 Vernam 密码、Shamir 的秘密共享、量子密钥分发8 (不要与后量子密码学混淆)、熵源和物理不可克隆函数 (PUF) 以及模糊承诺方案。9
因为信息论证明表明对手没有足够的信息来破坏安全声明,无论其计算能力如何——量子或其他——信息论安全的结构都不会受到量子威胁的影响。
内在 ID PUF:后量子安全不确定性的解毒剂
内在 ID SRAM PUF
支撑所有 Intrinsic ID 产品的核心技术是 SRAM PUF. 与其他 PUF 一样,SRAM PUF 会产生设备独特的响应,这些响应源于硅芯片生产过程中产生的不可预测的变化。 SRAM PUF 的操作基于几乎所有数字芯片中都可用的传统 SRAM 电路。
基于多年的持续测量和分析,Intrinsic ID 开发了非常准确地描述其 SRAM PUF 行为的随机模型10. 使用这些模型,我们可以确定 SRAM PUF 不可预测性的严格界限。 这些不可预测性界限以熵的形式表示,本质上是基本的,无法通过任何数量的计算、量子或其他方式来克服。
内在 ID Quiddikey
QuiddiKey 是基于SRAM PUF技术的硬件安全解决方案。 QuiddiKey 的核心组件是一个模糊承诺方案9 使用 SRAM PUF 响应保护根密钥并生成公共帮助数据。 信息论证明,辅助数据对根密钥的信息泄露为零,因此辅助数据公开对根密钥的安全性没有影响。
这种无泄漏证明——在数亿台设备上经过多年的现场部署而保持完好——依赖于系统使用的 PUF 作为熵源,如其随机模型所表达的那样。 QuiddiKey 首次使用其熵源初始化其根密钥,随后由模糊承诺方案保护。
除了模糊承诺方案和熵源之外,QuiddiKey 还基于经过认证的标准兼容结构实施加密操作,使用标准对称加密原语,特别是 AES 和 SHA-256。11 这些操作包括:
- 密钥派生函数(KDF),它使用受模糊承诺方案保护的根密钥作为密钥派生密钥。
- 确定性随机位生成器 (DRBG),最初由来自熵源的高熵种子播种。
- 密钥包装功能,本质上是一种经过身份验证的加密形式,用于使用从受模糊承诺方案保护的根密钥派生的密钥包装密钥来保护外部提供的应用程序密钥。
内在 ID:后量子世界的可靠安全性
QuiddiKey 的安全架构基于用于生成和保护根密钥的信息理论上安全的组件,以及用于其他密码功能的已建立的对称密码学。 信息理论上安全的结构不受量子攻击的影响。 量子威胁对对称密码学的影响非常有限,现在或在可预见的未来不需要任何补救措施。 重要的是,QuiddiKey 不部署任何易受量子攻击的公钥加密原语。
QuiddiKey 的所有变体都是量子安全的,并且符合推荐的后量子指南。 使用 QuiddiKey 的 256 位安全强度变体将提供强大的量子抵抗,即使在遥远的未来,但 128 位变体被认为在现在和可预见的未来使用是完全安全的。
有关此主题的更多详细信息,请参阅白皮书 “后量子世界中的本征 ID PUF”.
参考资料
- “后量子密码学报告”,NIST 信息技术实验室,NISTIR 8105,2016 年 XNUMX 月, https://nvlpubs.nist.gov/nistpubs/ir/2016/NIST.IR.8105.pdf
- “2021 年量子威胁时间表报告”,全球风险研究所 (GRI),M. Mosca 和 M. Piani,2022 年 XNUMX 月, https://globalriskinstitute.org/mp-files/quantum-threat-timeline-report-2021-full-report.pdf
- “PQC 标准化过程:宣布四名候选人进行标准化,加上第四轮候选人”,NIST 信息技术实验室,5 年 2022 月 XNUMX 日, https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4
- “Grover 的量子搜索算法是最优的”,C. Zalka,Phys。 修订版 A 60, 2746, 1 年 1999 月 XNUMX 日, https://journals.aps.org/pra/abstract/10.1103/PhysRevA.60.2746
- “重新评估 Grover 的算法”,S. Fluhrer,IACR ePrint 2017/811, https://eprint.iacr.org/2017/811.pdf
- “NIST 令人愉快的后量子惊喜”,Bas Westerbaan,CloudFlare,8 年 2022 月 XNUMX 日, https://blog.cloudflare.com/nist-post-quantum-surprise/
- “后量子密码学——常见问题解答:为了抵御量子计算机的威胁,我们现在应该将 AES 的密钥长度加倍吗? (11 年 18 月 18 日添加)”,NIST 信息技术实验室, https://csrc.nist.gov/Projects/post-quantum-cryptography/faqs
- “Quantum cryptography: Public key distribution and coin tossing”,CH Bennett 和 G. Brassard,IEEE 计算机、系统和信号处理国际会议论文集,1984 年 XNUMX 月, https://arxiv.org/abs/2003.06557
- “模糊承诺方案”,A. Juels 和 M. Wattenberg,第 6 届 ACM 计算机和通信安全会议论文集,1999 年 XNUMX 月, https://dl.acm.org/doi/pdf/10.1145/319709.319714
- “硅 PUF 的精确概率可靠性模型”,R. Maes,密码硬件和嵌入式系统国际研讨会论文集,2013 年, https://www.iacr.org/archive/ches2013/80860176/80860176.pdf
- NIST 信息技术实验室,密码算法验证程序 CAVP,验证 #A2516, https://csrc.nist.gov/projects/cryptographic-algorithm-validation-program/details?validation=35127