新思科技
Ansys

Synopsys PUF:应对后量子时代不确定性的解药

您最近可能听到了很多关于量子计算对密码学构成威胁的讨论。如果是这样,您可能也会有很多疑问:究竟什么是“量子威胁”,它将如何影响您的密码学解决方案?让我们一起来探讨几个关于量子计算及其对密码学影响的最常见问题。

什么是量子计算机?

量子计算机既不是速度极快的通用超级计算机,也无法以海量并行的方式神奇地运行。相反,它能高效执行独特的量子算法。理论上,这些算法执行某些特定计算的效率要远高于任何传统计算机。

然而,要开发出真正意义上的量子计算机(即在实践中能够胜过现代传统计算机的量子计算机)极其困难。量子计算技术自 20世纪 80年代以来一直在发展,2010年代以来可操作的量子计算机也在逐步改进。不过,即使将当前的技术水平推向未来,并假设其具有相当于传统计算机摩尔定律的指数级改进,专家估计,真正意义上的量子计算机要成为现实仍至少需要 15 到 20 年的时间 (1), (2)。

密码学面临的量子威胁是什么?

在 20世纪 90年代,人们发现某些量子算法可能会影响某些传统密码学技术的安全性。以下两种量子算法引发了人们的担忧:

  1. 秀尔算法(Shor's algorithm)由彼得·秀尔(Peter Shor)于 1994 年发明,是一种用于大整数分解和求解几个相关数论问题的高效量子算法。目前,传统计算机尚无已知的有效大整数分解算法,而这正是几种经典公钥密码学技术安全性的基础。
  2. 格罗弗算法(Grover's algorithm)由洛夫·格罗弗(Lov Grover)于 1996 年发明,是一种量子算法,其搜索通用函数逆向的速度比传统计算机呈二次方级提升。在密码学中,搜索逆向等同于暴力破解攻击(例如针对未知的密钥值)。此类攻击的难度构成了大多数对称密码学基元安全性的基础。

如果这些量子算法能够在真正意义上的量子计算机上执行,将会对当前密码学技术的安全性产生影响。

对我的公钥密码学解决方案有什么影响?

迄今为止,最重要且应用最广泛的公钥基元毫无疑问基于 RSA、离散对数或椭圆曲线密码学。当真正意义上的量子计算机投入运行后,所有这些都可以通过秀尔算法得到高效求解。这将导致当前几乎所有正在使用的公钥密码学变得不再安全。

对于受影响的公钥加密和密钥交换基元,这种威胁在今天已经成为现实。攻击者如果捕获并存储现在(或过去)交换的加密消息,将来在真正意义上的量子计算机投入运行后就可以对其进行解密。因此,截至目前通信中涉及的高机密性和/或长期机密信息已经面临风险。

如果您在少于 15 年的短期承诺中使用受影响的签名基元,那么这个问题尚不那么紧迫。然而,如果真正意义上的量子计算机投入使用,任何签名的价值从那一刻起都将失效。因此,您不应将受影响的基元用于需要保持 15 年或更长时间可验证性的长期承诺的签名。

在过去十年中,密码学界设计了新的公钥基元,这些基元基于无法被秀尔算法(或任何其他已知的有效算法,无论是量子算法还是其他算法)解决的数学问题。这些算法通常被称为后量子密码学。NIST 最近公布了一系列用于标准化的此类算法 (3)。

对我的对称密码学解决方案有什么影响?

设计良好的对称密钥基元的安全级别相当于暴力破解密钥所需的工作量。在传统计算机上,暴力破解密钥的工作量与密钥长度呈直接指数关系。当使用真正意义上的量子计算机时,格罗弗算法可以将暴力破解攻击的速度提高到二次方级。所需的工作量虽然仍呈指数级,但仅对应密钥长度的一半。因此可以说,格罗弗算法将任意给定长度算法的安全性降低了 50%。

然而,有一些重要事项需要牢记:

  • 格罗弗算法是一种最优的暴力破解策略(无论是量子算法还是其他算法)(4),因此二次方级的速度提升是最坏情况下的安全性影响。
  • 有强烈的迹象表明,对格罗弗算法的执行进行有意义的并行化是不可能的 (2)、(5)、(6)、(7)。在传统的暴力破解攻击中,将所使用的计算机数量翻倍会将计算时间缩减一半。这种扩展性对于量子计算机上的格罗弗算法来说是不可能的,这使得它在暴力破解攻击中的应用变得不切实际。
  • 在利用格罗弗算法对 128 位密钥实施现实世界的暴力破解攻击之前,量子计算机的性能必须得到极大的提升。现代传统超级计算机在实际可行的合理时间内(几个月),几乎无法完成复杂度相当于 128/2=64 位指数的计算。根据其当前的状态和发展进度,量子计算机要达到这一水平还需要远超 20 年的时间 (6)。

目前,量子计算机对对称密码学的实际影响非常有限。在最坏的情况下,当前使用基元的安全强度会降低 50%(根据其密钥长度),但由于格罗弗算法的局限性,对于不久的将来而言,这是一个过于悲观的假设。将对称密钥长度加倍以抵御量子暴力破解攻击是一项非常广泛的全面措施,肯定能解决问题,但未免过于保守。目前,尚无关于抗量子加固对称密钥密码学的强制性建议,诸如 AES-128 或 SHA-256 等 128 位安全强度的基元被认为在当前及可预见的未来可以安全使用。

这会对信息论安全性产生影响吗?

信息论安全方法(也称为无条件安全或完美安全)是指其安全性声明经过数学证明的算法技术。一些重要且具备信息论安全特性的结构和原语包括:Vernam 密码、Shamir 秘密共享、量子密钥分发(8)(切勿与后量子密码学相混淆)、熵源和物理不可克隆函数(PUF)以及模糊承诺方案(9)。

由于信息论证明表明攻击者没有足够的信息来破解安全性声明(无论其计算能力如何——无论是量子计算还是其他计算),因此具备信息论安全特性的结构不会受到量子威胁的影响。

Synopsys PUF:应对后量子安全不确定性的解决方案

Synopsys SRAM PUF

支撑所有 Synopsys PUF 产品的核心技术是 SRAM PUF。与其他 PUF 一样,SRAM PUF 生成的器件唯一响应源自硅芯片生产过程中产生的不可预测变异。SRAM PUF 的运行基于几乎所有数字芯片中都可轻松获取的常规 SRAM 电路。

基于多年持续的测量与分析,Synopsys 开发了能够极其准确地描述其 SRAM PUF 行为的随机模型(10)。利用这些模型,我们可以确定 SRAM PUF 不可预测性的严格界限。这些不可预测性界限以熵的形式表示,属于基础特性,无法通过任何计算能力(无论是量子计算还是其他计算)来克服。

Synopsys PUF 

Synopsys PUF 是一种基于 SRAM PUF 技术的硬件安全解决方案。Synopsys 硬件 PUF 的核心组件是一个模糊承诺方案(9),该方案使用 SRAM PUF 响应保护根密钥并生成公开的辅助数据。经信息论证明,辅助数据不会泄露关于根密钥的任何信息,因此辅助数据公开这一事实对根密钥的安全性没有任何影响。

这种无泄露证明(在数亿台设备上经过多年实际部署得以保持完整)依赖于系统中使用的 PUF 作为熵源(如其随机模型所示)。Synopsys 硬件 PUF 使用其熵源首次初始化根密钥,随后该根密钥由模糊承诺方案进行保护。

除模糊承诺方案和熵源外,Synopsys 硬件 PUF 还使用标准对称密码原语(特别是 AES 和 SHA-256)实现基于已认证标准合规结构的密码操作(11)。这些操作包括:

  • 密钥派生函数(KDF),它使用由模糊承诺方案保护的根密钥作为密钥派生密钥。
  • 确定性随机比特生成器(DRBG),最初由来自熵源的高熵种子进行播种。
  • 密钥封装功能(本质上是认证加密),用于使用由模糊承诺方案保护的根密钥派生的密钥封装密钥来保护外部提供的应用密钥。

Synopsys 安全 IP:面向后量子时代的经验证的安全技术

Synopsys PUF 的安全架构基于用于生成和保护根密钥的信息论安全组件,以及用于其他密码功能的成熟对称密码学。信息论安全结构能够抵御量子攻击。量子威胁对对称密码学的影响是有限的,现在或在可预见的未来均无需采取任何修复措施。重要的是,Synopsys PUF 未部署任何易受量子攻击的公钥密码原语。

Synopsys PUF 的所有变体均具备抗量子攻击能力,并且符合推荐的后量子指南。使用 256 位安全强度变体的 Synopsys PUF 将在遥远的未来依然提供强大的抗量子能力,同时 128 位变体也被认为在目前及可预见的未来使用是完全安全的。 

 

参考资料

  1. “Report on Post-Quantum Cryptography”,NIST 信息技术实验室,NISTIR 8105,2016 年 4 月,https://nvlpubs.nist.gov/nistpubs/ir/2016/NIST.IR.8105.pdf
  2. “2021 Quantum Threat Timeline Report”,Global Risk Institute (GRI),M. Mosca 和 M. Piani,2022 年 1 月,https://globalriskinstitute.org/mp-files/quantum-threat-timeline-report-2021-full-report.pdf
  3. “PQC Standardization Process: Announcing Four Candidates to be Standardized, Plus Fourth Round Candidates”,NIST 信息技术实验室,2022 年 7 月 5 日,https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4
  4. “Grover’s quantum searching algorithm is optimal”,C. Zalka,Phys. Rev. A 60, 2746,1999 年 10 月 1 日,https://journals.aps.org/pra/abstract/10.1103/PhysRevA.60.2746
  5. “Reassessing Grover’s Algorithm”,S. Fluhrer,IACR ePrint 2017/811,https://eprint.iacr.org/2017/811.pdf
  6. “NIST’s pleasant post-quantum surprise”,Bas Westerbaan,CloudFlare,2022 年 7 月 8 日,https://blog.cloudflare.com/nist-post-quantum-surprise/
  7. “Post-Quantum Cryptography – FAQs: To protect against the threat of quantum computers, should we double the key length for AES now? (added 11/18/18)”,NIST 信息技术实验室,https://csrc.nist.gov/Projects/post-quantum-cryptography/faqs
  8. “Quantum cryptography: Public key distribution and coin tossing”,C. H. Bennett 和 G. Brassard,IEEE 计算机、系统与信号处理国际会议论文集,1984 年 12 月,https://arxiv.org/abs/2003.06557
  9. “A fuzzy commitment scheme”, A. Juels 和 M. Wattenberg,《Proceedings of the 6th ACM conference on Computer and Communications Security》,1999 年 11 月, https://dl.acm.org/doi/pdf/10.1145/319709.319714
  10. “An Accurate Probabilistic Reliability Model for Silicon PUFs”,R. Maes,《Proceedings of the International Workshop on Cryptographic Hardware and Embedded Systems》,2013 年, https://www.iacr.org/archive/ches2013/80860176/80860176.pdf
  11. NIST 信息技术实验室,密码算法验证计划 CAVP,验证编号 #A2516, https://csrc.nist.gov/projects/cryptographic-algorithm-validation-program/details?validation=35127
Ask BETA This experience is in beta mode. Please double check responses for accuracy.

结束聊天

关闭此窗口将清除您的聊天记录并结束本次会话。您是否确定要结束本次聊天?