「我的袖子裏沒有東西」數



密碼學中,「我的袖子裏沒有東西」數(英語:Nothing-up-my-sleeve number)是指那些在構造上沒有隱藏屬性嫌疑的數字。它們用於建立密碼函數,例如密碼雜湊函數密碼。這些演算法通常需要隨機常數來進行混合或初始化。密碼學家希望以一種方式選擇這些值,以證明這些常數的選擇不是出於惡意目的的,例如為演算法建立一個後門[1] 使用一種幾乎沒有調整空間的方法生成數字可以消除這些擔憂。一個例子是使用圓周率π的初始數字作為這些常數。使用小數點後數百萬位的π的數字通常不被認為可信,因為演算法設計者可能會因為可以利用它而選擇小數點的特定起點,這創造了一個隱藏的弱點。[2]

實數(例如πe和無理根)在其進位制中的各個位上的數字被認為以相等的頻率出現(參見正規數)。這些數可以被視為柯氏亂數的對立極端,因為後者看起來是隨機的,但資訊熵非常低。使用這些數的動機源於1975年美國政府的資料加密標準早期引發的爭議。該標準因其S盒中使用的常數沒有提供解釋而受到批評(儘管後來發現它們經過精心選擇以防止當時尚未公開的差分密碼分析攻擊)。因此,人們需要一種更透明的方法來生成用於密碼學的常數。[3]

藏在袖子裏的紙牌

「我的袖子裏沒有東西」是一句和魔術師有關的習語,他們在表演魔術之前總會先展開袖子以展示其中沒有東西。

例子

反例

  • Streebog英語Streebog的雜湊函數S盒號稱是隨機生成的,但經過逆向工程後證明,它是透過演算法生成的,存在一些弱點。[15]
  • 資料加密標準的常數由美國國家安全域提供。但後來發現,這些常數並非隨機,而是讓加密演算法能夠抵禦當時尚未公開的差分密碼分析攻擊。[3]
  • 雙橢圓曲線確定性隨機位元生成器NIST推薦的密碼學安全偽亂數生成器,2007年受到批評,因為推薦用於該演算法的常數選擇方式可能允許其作者根據過去生成值的樣本預測未來的輸出。[1] 2013年9月,《紐約時報》報道:「美國國家安全域前承包商斯諾登泄露的內部備忘錄顯示,美國國家安全域介入了2006年NIST標準中使用的一種亂數生成器,其中包含一個供美國國家安全域使用的後門」。[16]
  • P曲線是NIST為橢圓曲線加密制定的標準。這些曲線的係數是透過雜湊無法解釋的隨機種子英語random seed生成的,例如:
    • P-224: bd713447 99d5c7fc dc45b59f a3b9ab8f 6a948bc5.
    • P-256: c49d3608 86e70493 6a6678e1 139d26b7 819f7e90.
    • P-384: a335926a a319a27a 1d00896a 6773a482 7acdac73.

儘管沒有直接關係,但在雙橢圓曲線確定性隨機位元生成器後門曝光後,P曲線常數[17]的可疑之處引起了人們的擔憂[18],美國國家安全域所選的值使他們在尋找私鑰時更具優勢。[19]此後,許多協定和程式開始使用Curve25519作為NIST P-256曲線的替代方案。

I no longer trust the constants. I believe the NSA has manipulated them through their relationships with industry.

——Bruce Schneier,"The NSA Is Breaking Most Encryption on the Internet" (2013)[20]

局限性

伯恩斯坦和合作者證明,在生成橢圓曲線等密碼對象的複雜程式中,使用「我的袖子裏沒有東西」數字作為常數可能不足以防止插入後門。例如,有許多看似無害的簡單數學常數候選,如πe歐拉-馬斯刻若尼常數、√2、√3、√5、√7、log(2)、(1 + √5)/2、ζ(3)、ζ(5)、sin(1)、sin(2)、cos(1)、cos(2)、tan(1)或 tan(2)等都可能存在問題。對於這些常數,也有幾種不同的二進制表示方法可供選擇。如果使用常數作為隨機種子,還可以選擇大量雜湊函數候選值,如SHA-1、SHA-256、SHA-384、SHA-512、SHA3-256或SHA3-384。

如果對象選擇程式中有足夠多的可選參數,組合爆炸英語combinatorial explosion就能使可能的設計選擇和表面上簡單的常數的範圍足夠大,以便自動搜尋各種可能性,從而建造出具有所需後門特性的對象。[21]

參考資料

  1. ^ 1.0 1.1 Bruce Schneier. Did NSA Put a Secret Backdoor in New Encryption Standard?. Wired News. 2007-11-15 [2023-08-02]. (原始內容存檔於2012-09-19). 
  2. ^ 2.0 2.1 Blowfish Paper. [2023-07-31]. (原始內容存檔於2011-09-06). 
  3. ^ 3.0 3.1 Bruce Schneier. Applied Cryptography, second edition, John Wiley and Sons, 1996, p. 278.
  4. ^ RFC 1321 Sec. 3.4
  5. ^ FIPS 180-2: Secure Hash Standard (SHS)頁面存檔備份,存於互聯網檔案館) (PDF, 236 kB) – Current version of the Secure Hash Standard (SHA-1, SHA-224, SHA-256, SHA-384, and SHA-512), 1 August 2002, amended 25 February 2004
  6. ^ Revision of NEWDES, Robert Scott, 1996. [2023-07-31]. (原始內容存檔於2012-11-08). 
  7. ^ Henri Gilbert; M. Girault; P. Hoogvorst; F. Noilhan; T. Pornin; G. Poupard; J. Stern; S. Vaudenay. Decorrelated Fast Cipher: an AES candidate (PDF/PostScript). 1998-05-19 [2023-07-31]. (原始內容存檔於2008-04-09). 
  8. ^ A. Biryukov; C. De Cannière; J. Lano; B. Preneel; S. B. Örs. Security and Performance Analysis of ARIA (PostScript) (報告). Version 1.2—Final Report. Katholieke Universiteit Leuven. 2004-01-07 [2023-07-31]. (原始內容存檔於2011-07-16). 
  9. ^ Rivest, R. L. The RC5 Encryption Algorithm (PDF). Proceedings of the Second International Workshop on Fast Software Encryption (FSE) 1994e: 86–96. 1994 [2023-08-02]. (原始內容 (PDF)存檔於2007-04-17). 
  10. ^ Ramos-Calderer, Sergi; Bellini, Emanuele; Latorre, José I.; Manzano, Marc; Mateu, Victor. Quantum search for scaled hash function preimages. Quantum Information Processing. 2021-05-10, 20 (5): 180. doi:10.1007/s11128-021-03118-9. 
  11. ^ Dunkelman, Orr, Nathan Keller, and Adi Shamir. A practical-time attack on the A5/3 cryptosystem used in third generation GSM telephony. Cryptology ePrint Archive. 2010 [2023-08-02]. (原始內容存檔於2023-06-09). 
  12. ^ 存档副本 (PDF). [2016-05-07]. (原始內容 (PDF)存檔於2016-06-11). 
  13. ^ src/lib/libc/crypt/bcrypt.c - diff - 1.3. cvsweb.openbsd.org. [2022-07-05]. (原始內容存檔於2022-07-05). 
  14. ^ hash - Why is the BCrypt text "OrpheanBeholderScryDoubt". Information Security Stack Exchange. [2022-07-05]. (原始內容存檔於2023-07-10) (英語). 
  15. ^ Biryukov, Alex; Perrin, Léo; Udovenko, Aleksei. Reverse-Engineering the S-box of Streebog, Kuznyechik and STRIBOBr1 (Full Version). Iacr-Eurocrypt-2016. 2016 [2019-03-26]. doi:10.1007/978-3-662-49890-3_15. (原始內容存檔於2023-08-02). 
  16. ^ Perlroth, Nicole. Government Announces Steps to Restore Confidence on Encryption Standards. The New York Times. 2013-09-10 [2013-09-11]. (原始內容存檔於2015-04-23). 
  17. ^ SafeCurves: Introduction. [2017-05-02]. (原始內容存檔於2017-09-05). 
  18. ^ Maxwell, Gregory. [tor-talk] NIST approved crypto in Tor?. 2013-09-08 [2015-05-20]. (原始內容存檔於2014-10-02). 
  19. ^ SafeCurves: Rigidity. safecurves.cr.yp.to. [2015-05-20]. (原始內容存檔於2015-05-22). 
  20. ^ "I no longer trust the constants.", The NSA Is Breaking Most Encryption on the Internet - Schneier on Security. www.schneier.com. [2021-04-10]. (原始內容存檔於2021-04-10). 
  21. ^ How to manipulate curve standards: a white paper for the black hat 互聯網檔案館存檔,存檔日期2016-03-08. Daniel J. Bernstein, Tung Chou, Chitchanok Chuengsatiansup, Andreas Hu ̈lsing, Eran Lambooij, Tanja Lange, Ruben Niederhagen, and Christine van Vredendaal, September 27, 2015, accessed June 4, 2016
  • Eli Biham, Adi Shamir, (1990). Differential Cryptanalysis of DES-like Cryptosystems. Advances in Cryptology – CRYPTO '90. Springer-Verlag. 2–21.