新思科技
Ansys

新思科技 PUF:應對後量子不確定性的解方

您最近可能經常聽到有關量子運算對密碼學構成威脅的說法。若是如此,您心中想必也有許多疑問,例如這個「量子威脅」究竟是什麼,以及它將如何影響您的密碼學解決方案。讓我們一起來探討有關量子運算及其對密碼學影響的一些常見問題。

什麼是量子電腦?

量子電腦並不是速度極快的通用超級電腦,也無法以神奇的大規模平行方式運作。相反地,它能有效執行獨特的量子演算法。理論上,這些演算法執行某些特定運算的效率,可以遠高於任何傳統電腦。

然而,要開發出具有實用價值的量子電腦(即在實務上能夠超越現代傳統電腦的量子電腦)極為困難。量子運算技術自 1980 年代開始發展,而可運作的量子電腦則在 2010 年代以後逐漸獲得改善。不過,即使將目前的尖端技術水準推算至未來,並假設其具備等同於傳統電腦摩爾定律的指數級成長,專家仍預估至少需要 15 到 20 年的時間,具實用價值的量子電腦才能成為現實 (1), (2)。

什麼是對密碼學的量子威脅?

在 1990 年代,人們發現某些量子演算法可能會影響特定傳統密碼學技術的安全性。有兩個量子演算法引發了關注:

  1. 秀爾演算法 (Shor's algorithm) 由彼得·秀爾 (Peter Shor) 於 1994 年發明,是一種用於對大整數進行質因數分解及解決少數相關數論問題的高效量子演算法。目前,傳統電腦尚無已知的有效因數分解演算法,而這正是數種經典公開金鑰密碼學技術的安全基礎。
  2. 格羅弗演算法 (Grover's algorithm) 由洛夫·格羅弗 (Lov Grover) 於 1996 年發明,是一種搜尋通用函數反函數的量子演算法,其速度比傳統電腦呈二次方倍數快。在密碼學術語中,搜尋反函數相當於進行暴力破解攻擊(例如針對未知的密鑰值)。這類攻擊的難度構成了大多數對稱密碼學原語的安全基礎。

如果這些量子演算法能夠在具實用價值的量子電腦上執行,將會影響現行密碼學技術的安全性。

對我的公開金鑰密碼學解決方案有何影響?

迄今為止,最重要且最廣泛使用的公開金鑰原語是基於 RSA、離散對數或橢圓曲線密碼學。當具實用價值的量子電腦投入運作時,秀爾演算法可以有效破解所有這些技術。這將導致目前使用的幾乎所有公開金鑰密碼學失去安全性。

對於受影響的公開金鑰加密和金鑰交換原語而言,此威脅在今天已經是現實。攻擊者若攔截並儲存現在(或過去)交換的加密訊息,日後當具實用價值的量子電腦投入運作時便能將其解密。因此,迄今所通訊的高度機密及/或長期機密資料已經面臨風險。

如果您在少於 15 年的短期承諾中使用受影響的簽章原語,問題則較不急迫。然而,一旦具實用價值的量子電腦問世,任何簽章的價值將自該時起歸零。因此,您不應將受影響的原語用於需要維持 15 到 20 年或更長時間內仍可驗證的長期承諾簽章。

在過去十年中,密碼學界設計了新的公開金鑰原語,這些原語基於無法被秀爾演算法(或任何其他已知的有效演算法,無論是量子或其他演算法)解決的數學問題。這些演算法通常被稱為後量子密碼學。美國國家標準暨技術研究院 (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)

由於資訊理論證明表明,無論攻擊者的運算能力為何(無論是否為量子運算),攻擊者都沒有足夠的資訊來破解安全性主張,因此具資訊理論安全性的結構不會受到量子威脅的影響。

新思科技 PUF:應對後量子安全不確定性的解方

新思科技 SRAM PUF

支撐所有新思科技 PUF 產品的核心技術是 SRAM PUF。與其他 PUF 類似,SRAM PUF 會產生源自矽晶片生產過程中不可預測變化的裝置專屬回應。SRAM PUF 的運作基於實際上所有數位晶片中皆可取得的傳統 SRAM 電路。

基於多年的持續量測與分析,新思科技已開發出能極為精確描述其 SRAM PUF 行為的隨機模型 (10)。透過這些模型,我們可以判定 SRAM PUF 不可預測性的嚴格界限。這些不可預測性界限以熵來表示,是基礎且無法透過任何運算規模(無論是否為量子運算)來克服。

新思科技 PUF 

新思科技 PUF 是一項基於 SRAM PUF 技術的硬體安全解決方案。新思科技硬體 PUF 的核心元件是以 SRAM PUF 回應保護根金鑰並產生公開輔助資料的模糊承諾方案 (9)。經資訊理論證明,輔助資料不會洩漏關於根金鑰的任何資訊,因此輔助資料公開的事實不會對根金鑰的安全性造成任何影響。

這種無洩漏證明(在數億個裝置上經過多年的實際部署仍保持完整)依賴系統所使用的 PUF 作為熵源,如其隨機模型所示。新思科技硬體 PUF 使用其熵源首次初始化其根金鑰,隨後由模糊承諾方案進行保護。

除了模糊承諾方案和熵源之外,新思科技硬體 PUF 還實作了基於經過認證且符合標準之結構的密碼學運算,並採用標準對稱密碼學原語,特別是 AES 和 SHA-256。(11) 這些運算包括:

  • 金鑰衍生函數 (KDF),使用受模糊承諾方案保護的根金鑰作為金鑰衍生金鑰。
  • 確定性亂數位產生器 (DRBG),最初由來自熵源的高熵種子進行種子設定。
  • 金鑰包裝功能(本質上為經過驗證的加密),用於使用衍生自受模糊承諾方案保護之根金鑰的金鑰包裝金鑰,來保護外部提供的應用程式金鑰。

新思科技安全 IP:適用於後量子時代的經驗證安全性

新思科技 PUF 的安全架構基於用於產生和保護根金鑰的具資訊理論安全性元件,以及用於其他密碼學功能的既有對稱密碼學。具資訊理論安全性的結構對量子攻擊具有免疫力。量子威脅對對稱密碼學的影響有限,目前或可預見的未來皆不需要任何修補。重要的是,新思科技 PUF 未部署任何具量子脆弱性的公開金鑰密碼學原語。

新思科技 PUF 的所有變體均具備量子安全性,且符合建議的後量子準則。使用 256 位元安全強度變體的新思科技 PUF 將在遙遠的未來提供強大的量子抵抗力,而 128 位元變體在目前及可預見的未來也被認為是絕對安全的。 

 

參考案例

  1. “Report on Post-Quantum Cryptography”, NIST Information Technology Laboratory, NISTIR 8105, April 2016, https://nvlpubs.nist.gov/nistpubs/ir/2016/NIST.IR.8105.pdf
  2. “2021 Quantum Threat Timeline Report”, Global Risk Institute (GRI), M. Mosca and M. Piani, January, 2022, 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 Information Technology Laboratory, July 5, 2022, 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, October 1, 1999, 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, July 8, 2022, 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 Information Technology Laboratory, https://csrc.nist.gov/Projects/post-quantum-cryptography/faqs
  8. “Quantum cryptography: Public key distribution and coin tossing”, C. H. Bennett and G. Brassard, Proceedings of the IEEE International Conference on Computers, Systems and Signal Processing, December, 1984, https://arxiv.org/abs/2003.06557
  9. “A fuzzy commitment scheme”, A. Juels and M. Wattenberg, Proceedings of the 6th ACM conference on Computer and Communications Security, November, 1999, 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 Information Technology Laboratory, Cryptographic Algorithm Validation Program CAVP, validation #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.

結束聊天

關閉此視窗將清除您的聊天紀錄並結束本次會話。您是否確定要結束這次聊天? ```