Factoring RSA Keys With TLS Perfect Forward Secrecy

rsa atack ssl

Florian Weimer,Red Hat technical report,2015 原文
这篇报告讨论了RSA-CRT故障攻击的历史和解决对策，并针对TLS中RSA-CRT的攻击进行了本地测试和主动扫描。

RSA-CRT Optimization

1. Attacks on RSA-CRT

y = S(x) = xd mod N 

y1 = y mod P = y e*e^-1mod(P-1)mod P = xdP mod P
y2 = y mod Q = y e*e^-1mod(Q-1)mod Q = xdQ mod Q

y = y2 + h * q,其中 h = (y1-y2)*(1/q mod p)mod p

Bellcore attack(1996) needs one correct and one faulty signature of same message
计算y1时出错

y = y2 + q*(y1-y2)*(1/q mod p)mod p
y' = y2 + q*(y1'-y2)*(1/q mod p)mod p

gcd(y-y', n) = q

计算y2出错也可得到gcd(y-y'',n) = p

Arjen Lenstra attack(1996) only one faulty signature
计算y1时出错

y' = y2 + q*(y1'-y2)*(1/q mod p)mod p
y'e  = x mod q
q divides y'e-x,but p does not

gcd(y'^e-x , n) = q

计算y2出错也有gcd(y''^e-x , n) = p
y1、y2同时出错就不行了

可能导致Lenstra Attack的Fault
* 使用的大整数运算库可能产生错误结果 CVE-2014-3570 BN_sqr
* 多个线程间的对数据访问的竞争条件导致的数据错误
* CPU中计算单元的错误
* 在完整性检查通过后，私钥中的关键部分损坏
* CPU caches,main memory bit errors (rowhammer?overflow?)

Countermeasures:
签名后检查签名是否正确 y^e = x

rsa blinding
签名前乘上一个随机数，防止timing attack,但是并不影响Lenstra attack

RSA in TLS

(EC)DHE-RSA
RSA用来对DH参数签名
确定性的padding PKCS#1 v1.5 签名 （加密填充是随机的）

h := H(M) 
m := 0x01||0xFF||...||0xFF||0x00||ASN.1||h 

ASN.1是hash函数用ASN.1表示的标识符，消息M的签名即m^d mod N

RSASSA-PSS：Probabilistic Signature Scheme

The experiment

本地测试：修改OpenSSL的代码，给签名的值根据时间随机添加一个数，移除了对签名正确性的检查
爬虫扫描 “a novel way to discover side-channel vulnerabilities”、

target selection：

• 基于域名： Hubert Kario, Rapid7 Sonar,
  25 million host names -> 8 million with forward secrecy
  1.7 billion TLS handshakes -> 1.4 billion with forward secrecy

• 基于IP ： ZMap ServerKeyExchange
  32 million IP -> 10 million with forward secrecy

• 基于证书：
  26,000 targets in that category, with about 40 million forward secrecy handshakes

实验结果

从证书中的字段推测出厂商
Citrix: TLS-terminating load balancer, old replaced
Hillstone: 200+ keys leak,firmware update
Alteon/Nortel：unable to complete the majority of handshakes successfully
Viprinet: key was corrupted in memory
Fortine: two key leaks in over 90 million TLS handshakes
BEJY:custon Java implementation of SSL

Citrix、Hillstone、ZyXEL确认使用了Cavium的硬件
Hillstone、ZyXEL使用了Cavium提供的custom OpenSSL -> patch SDK

签名错误但是密钥恢复失败的原因

• 公私钥不匹配
• 分解一个损坏的公钥
• No-op RSA :Viprinet 尽管公钥里e=65537,但是签名的值和明文相同，所以e=d=1
• Zero RSA：签名的值为0
  RSA-CRT加固检测到了错误，没有把结果写到调用者的buffer中，调用者忽略了签名过程的失败，发送了没有写过的buffer

Browser behavior

签名错误时浏览器的反应

silent retry掩盖了服务器端的问题

Impact on other protols

IPsec
实验中发现的问题都来自VPN设备。 Internet Key Exchange ，need active participation
SSH、 DNSSEC

总结

问题产生的原因：
1. RSA-CRT实现没有检查签名是否正确
2. TLS中RSA签名使用确定性的填充
3. 前向安全性被部署地更加广泛
4. 浏览器掩盖了服务器的问题