Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

安全论文每日读 2015.02.12

从今天开始,我们将讨论一系列密码学误用的分析检测论文,首先介绍的是来自Usenix Security 2012年的论文 Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices.

论文下载地址:https://factorable.net/weakkeys12.extended.pdf

作者:Nadia Heninger, Zakir Durumeric, Eric Wustrow, J. Alex Halderman

单位:University of California, San Diego, The University of Michigan

Abstract

  • RSA和DSA会因为随机数发生器故障失效,这类问题在实际应用中的影响从未被研究过。本文对TLS和SSH服务器进行了大规模全网调查,发现脆弱密钥广泛存在。
  • 调查中0.75%的TLS证书因为密钥生成时不熵不足共享了秘钥,可以推测其他1.7%的采用相同实现的证书也存在这类问题。
  • 0.5%的TLS主机和0.03%的SSH主机RSA私钥可以被获取到,因为它们的公钥共享了重要的公因子(common factor)。同时能获取到1.03%的SSH主机的DSA私钥,因为不充分的签名随机性。
  • 本文对有漏洞的主机进行集群和调查,发现大部分是无意识的或者是嵌入式设备。
  • 对这些设备常用的三个软件组件进行实验,能重现漏洞并识别出导致这些漏洞的特定软件行为,包括Linux随机数发生器的一个boot-time entropy hole.

Introduction and Roadmap

  • 本文通过检查因特网中使用的公钥来测试随机数是否被安全产生。
  • 本文对TLS和SSH协议进行了因特网范围调查,扫描公开IPv4地址空间,从12.8 million主机中收集了5.8 million唯一TLS证书,从10.2 million SSH主机中收集了6.2 million 唯一SSH host key。本文的技术用不到24小时的时间就可以扫描整个地址空间。
  • 分析数据集发现不充分随机性相关的几种问题存在的证据。至少5.57%的TLS主机和9.60%的SSH主机以明显错误的方式使用了和其他主机相同的key。至少5.23%的TLS主机使用了制造商默认的key,另外0.34%由于随机数生成器故障产生了和其他主机相同的key。少数有漏洞的TLS证书被浏览器信任CA签名。
  • 通过利用在随机性不充分情况下使用RSA和DSA的已知漏洞可以计算出64,000(0.5%)的TLS主机和108,000(1.06%)的SSH主机的私钥。
  • 为了理解这些问题发生的原因,作者手工调查了上百个有漏洞的主机,它们是密钥最常重复的主机,私钥都已被获取到了。几乎所有的都是headless或者嵌入式系统。这些设备在第一次开机后自动生成key,和传统PC相比可能熵源有限。而对有问题的主机集群,发现这些都和某个制造商或者某种设备模型有关,说明这是特定的有缺陷的实现导致的。分析找出了这些有问题的制造商。
  • 分析有问题设备中使用的最常见的开源软件组件,查找根本原因。

Background

  • RSA review:1024bit的RSA模数本身很难分解,但是如果两个RSA模数有相同的素因子p,另外一个素因子不同,那么可以先求出这两个模数的最大公因子,从而可以分解他们,计算出对应私钥。求最大公因子只需要毫秒单位时间即可完成。
  • DSA review: DSA在签名操作中使用的短期密钥k不具备足够的熵时会失效。如果一个签名(r,s)的k已知,那么可以从签名和公钥中计算出私钥x: Calculating x

如果两条信息m1和m2使用的相同的短期密钥k签名得到(r1,s1)和(r2,s2),那么显然r1和r2相同,则可以计算出k:Calculating k

  • Attack Scenarios:本文描述的弱密钥漏洞可以用来攻击TLS和SSH协议,它们都是利用RSA或DSA来认证服务器的。
    • TLS、SSH:获得私钥后进行中间人攻击。

Methodology

  • Internet-wide scanning:
    • Host discovery:用Nmap 5 network exploration tool,扫描公开IPv4地址空间哪些主机的443和22端口是打开的。
    • Certificate and host-key retrieval:用python实现了一个Certificate fetcher。用C实现了一个SSH 客户端来收集SSH host key。
    • TLS certificate processing: 解析证书链。
  • Identifying vulnerable device models: TLS certificate issuer/subject; TCP/IP fingerprinting.
  • Efficiently computing all-pairs GCDs: Computing all-pairs GCDs efficiently

Vulnerabilities

  • Repeated keys:本文发现7,770,232 个TLS主机和6,642,222个SSH主机和其它某个主机使用相同的key。对使用相同公钥的证书和host key集群,并手工对集群中的代表进行了分析,发现这些证书或者host key与特点制造商或组织有关。共享密钥的原因:(1)共享主机;(2)不同的TLS证书都属于同一个组织。排除这些因素然后把剩余共享密钥集群归因到几类问题上。
    • Default keys:制造商默认密钥是预先配置在设备固件里的,给定模型的所有设备都会共享同一密钥除非用户更改。这些设备的私钥还可能可以通过逆向工程获取。
    • Repeated keys due to low entropy: 密钥生成时的熵不够也会导致主机共享相同密钥。发现43,852个TLS主机使用了重复密钥。27,545个包含重复密钥的证书是自签名的。所有577个CA签发的证书都识别为Iomega StoCenter network storage设备。SSH主机无法区分默认key或者重复key,但是9.6%的key因为这些原因之一重复了。
  • Factorable RSA keys:如果RSA模数和另外一个密钥共享了某一个素因子也证明了熵不足的问题。本文计算了所有不同RSA模数对的GCD。11,170,883个不同的RSA模数获得了2314个不同的素因子,能被16,717个不同的公钥除尽。这能得到23,576(0.4%)个TLS证书的私钥。分析者,仅有两个可分解的TLS证书是由浏览器信任的CA签发的且都已过期。对数据集中的factorable key集群分析,与repeated key方法类似。
  • DSA signature weaknesses: DSA签名中的重复短期密钥问题。如果两条不同消息使用相同短期密钥签名,那么长期私钥可以立即被计算出来。收集了9,114,925个签名其中4,365个包含了和其他至少一个签名相同的r值,可用于计算私钥。集群分析与前类似。

Experimental Investigation

  • Weak entropy and the Linux RNG:部分有问题的key是Linux系统产生的,本文研究了Linux的随机数发生器(RNG)。
    • Entropy sources:作者对Linux 2.6.35内核实验发现Linux操作系统已经不从IRQ timings收集熵了,移除IRQ这样的熵源很可能会恶化headless and embedded devices 上的RNG问题,因为这样的设备通常缺乏人为输入。如果IRQ被移除,那么这些设备上的唯一熵源可能就是启动时间(the time of boot)了。
    • Experiment:为了测试Linux的/dev/urandom 在类似嵌入式网络设备在初始启动时的条件下是否会产生重复输出,作者对2.6.35内核进行了修改,对RNG做了插桩并禁用了特定熵源来模拟一个没有工作时钟的低端机器的冷启动。实验发现/dev/urandom的输出完全是可预测会重复的。
    • Boot-time entropy hole:由于实验中禁掉的熵源在嵌入式等设备上可能就不存在,特别是第一次启动的时候。也就意味着这时存在一个启动时熵洞,至少对于单核系统,Linux的urandom是完全可预测的,如果进程在这个窗口期产生长期密钥或者维护他们自己的entropy pool,那么这些key就存在问题。在Fedora, Red Hat Enterprise Linux和CentOS Linux系统上,OpenSSH是默认安装的,host key在第一次启动时就生成了。实验测试发现RHEL 5和6确实是有这样的问题的。
  • Factorable RSA keys and OpenSSL:研究发现一些设备会易于产生有相同因子的密钥,其中一个因子被其它很多密钥共享,但是另一个因子却没有。原因可能是密钥生成过程中entropy pool更新了,所以有一个因子一样,后面的因子不同了。
    • OpenSSL RSA key generation:OpenSSL生成key的时候会在entropy pool中混合入当前时间的秒数、进程号、还可能有未初始化的目标缓冲区内容等。因此,有多个key共享一个素因子的原因可能是很多设备是在相同时间状态下开始密钥生成过程的,随着时间推移,后面产生的因子就不同了。如果秒数不变,那么生成的key都是相同的。如果生成p的时候时间变化了,p和q都会不同;如果生成q的时候时间变化了,p同,q不同。
    • Experiment:修改了OpenSSL 1.0.0g来控制密钥生成时所有entropy输入,来生成key查看控制不同输入生成的key是否相同。
  • DSA signature weaknesses and Dropbear:
    • DSA签名漏洞表明熵问题不仅在密钥生成阶段有影响,对正常使用中的服务器软件运行时行为也有影响。本文研究了Dropbear,一种流行的轻量级SSH实现,它维护自己的entropy pools seeded from the operating system at launch. 这就可能存在问题,同时,可能OS的熵足够了,但是SSH后台程序没有。
    • Dropbear 0.55在生成短期密钥时是根据内部熵池的输出生成,它会维护一个静态计数器,并把它的结果hash到pool state里,除计数器外没有别的随机性了知道计数器溢出,所以如果两个Dropbear服务器seeded with the same value from urandom,签名随机性就相同了。

Discussion

  • RSA vs DSA in the face of low entropy: 针对RSA的攻击仅是用来恢复明文或者伪造签名,但是还不知道任何攻击能利用伪造的RSA签名恢复出私钥。但是DSA漏洞可以得到私钥,危害更大。且调查发现由于DSA签名被攻破的SSH主机被由于可分解RSA key的多。
  • /dev/(u)random as a usability failure: Linux文档写着“urandom不应该被用来生成长期GPG/SSL/SSH密钥”,但是在文本检查的所有开源实现中,都默认使用urandom来生成密钥。而对开发者的邮件和论坛调查显示,这种情况是由于大家认为使用random太保守了,且他们认为urandom的输出已经足够安全,这是错误的。