“我的袖子里没有东西”数



密码学中,“我的袖子里没有东西”数(英语: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.