Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

安全论文每日读 2015.02.13

今天继续介绍密码学误用的分析检测论文,今天要介绍的论文题目很有趣,叫做Ron was wrong, Whit is right (IACR Cryptology ePrint Archive, 2012)

文章下载:https://eprint.iacr.org/2012/064.pdf

作者:Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung, Christophe Wachter(第一作者是著名的荷兰数学家Arjen Lenstra,在大整数分解研究方面赫赫有名,保持了目前为止RSA大整数最高分解记录768bit)

本篇论文对于网络上的公钥做了一个整理(论文的数据大部分来自2010年的EFF SSL repository.没有全网扫描收集),在收集到这个公钥之后,做了一系列安全的分析。作者的目的是想要看一下这些公钥是否遵循了一些基本的密码学安全要求,结果是令人吃惊的,发现了大量的问题(后面会提到,甚至会有RSA的e指数是1和偶数的情况……)。

发现的问题

  • 收集到的11.4 million个RSA模数中,26,965个是有问题的。论文中给出了X.509证书中的RSA公钥和PGP key中最常见的十个e。
    • X.509证书:在X.509证书中,绝大多数(98.4921%)的e指数都是推荐的65537,有0.76%用了e=17
    • 在PGP RSA key中,e指数是推荐的65537的比率为48.85%,e=17的比率是39.50%,出现了一些奇怪的如257,21和2127 + 3这样的情况,另外有8次e=1,两次e为偶数的情况(汗……)。
  • 共收集到11.7 million个公钥,其中包含6.4 million个不同的RSA模数,其他的是ElGamal key,DSA key还有ECDSA key。对这些key检查发现了小部分的weak key。
  • 收集的key中,有不同持有者共享同一个key的情况。在6.6 million个不同的X.509证书和PGP key中,0.27 million(4%) 共享了它们的RSA模数。6.4 million个不同的RSA模数中,71,052(1.1%)个出现了多次。ElGamal和DSA也有这个问题,但数量没这么多。
  • 分析数据还发现12934个不同RSA模数存在很大安全风险,可以直接获取到私钥。这些模数影响到21,419个X.509证书和PGP key。其中大部分证书已过期或使用MD5作为hash函数,但是仍有涉及到3201个模数的5250个证书有效。
  • 存在可被分解的RSA模数的情况,即不同的模数共享同一个素因子,通过求GCD的方式可以把它们都分解了。

总结一下,这篇文章内容非常丰富,里面非常实际地总结了各种weak key的情况,特别值得系统管理员和软件开发人员仔细阅读后想想是否犯了同样的错误。同时,也为研究人员提供了一个很好的样例,做研究不一定就抱着理论分析不放,去调研一下现实的情况同样非常有意义。