标题: 关于python-rsa签名伪造漏洞(CVE-2016-1494)的讨论

创建: 2016-06-14 17:14
更新:
链接: https://scz.617.cn/misc/201606141714.txt

这个洞是Filippo Valsorda发现的:

Bleichenbacher'06 signature forgery in python-rsa (CVE-2016-1494) - [2016-01-05]
https://blog.filippo.io/bleichenbacher-06-signature-forgery-in-python-rsa/
https://gist.github.com/FiloSottile/9a1832541a7d01237ad6

这种错误实现在校验签名时接受:

s^e mod n="00 01 GARBAGE 00 ASN.1 HASH"

要求GARBAGE中不包含00。

CVE-2016-1494与BB2006的思想是一致的，验证RSA签名时对c^e产生的结果进行了某
种格式解析，而不是简单的memcmp()，在复杂的格式解析过程中留下了安全漏洞。
Bleichenbacher曾经也是贝尔实验室的，后来去了Google。

原文有篇中文直译版:

http://www.freebuf.com/news/92976.html

感觉像是在Google Translate基础上强行翻译的，有很多细节上的错误，不推荐。

相比之下，另有一篇中文意译版还不错，推荐阅读:

CVE-2016-1494 (python-rsa)漏洞详解 - uncleheart [2016-04-12]
http://www.freebuf.com/articles/terminal/101200.html
http://www.pengyanhao.com/183.html

这篇比较实在，对Filippo Valsorda给出的攻击代码还做了某些改进。作者是对付
BCTF 2016中一道题时折腾这个漏洞的。我是无意中看到作者这篇才引起了对BB2006
及其各种变种的兴趣，感谢uncleheart的分享。

在此就上文内容讨论一下，双引号中内容出自上文:

--------------------------------------------------------------------------
1. "在这里我说明一下，原文作者的文章出现了一个错误"

这个地方，Filippo Valsorda没有说错，他说的是BB2006的模板及原理。是那篇中文
直译版没翻译对，仔细看英文原文就能确认。

2. "我并没有找到一种合适的方法快速求出当e=65537时的根"

如果我没有理解错的话，uncleheart的潜台词是，如果他找到了快速求65537次方根
的办法，CVE-2016-1494还可以对付e=65537。

我想说的是，对形如"00 01 ..."的前缀求e次方根，当e=65537时，n最少1004448位，
现实世界中不可能有这么大的n。n不够大时，"s^e mod n"不等于"s^e"，运算从整数
域回到了有限域，BB2006及其变种全部失效。换句话说，现实世界中CVE-2016-1494
永远无法对付e=65537。

实测下面这些参数有解:

n=1024,e=3,md5
n=2048,e=3,md5
n=2048,e=7,md5

n=1024,e=3,sha1
n=2048,e=5,sha1
n=4096,e=7,sha1
n=8192,e=17,sha1
n=8192,e=23,sha1

n=2048,e=3,sha256
n=8192,e=17,sha256

n=2048,e=3,sha384
n=8192,e=13,sha384

n=2048,e=3,sha512
n=8192,e=11,sha512

可以看出，"n=2048,e=3"适用于所有HASH类型。

3. "待签名信息的二进制最后一位需要为1"

这个限制的数学本质是，对于高次同余方程x^r≡a(mod 2^k):

设r、k均为正整数，a为整数，若r、a均为奇数，则x^r≡a(mod 2^k)恰有一解。

Filippo Valsorda所示办法在e比较大时，效率太低，用数学方式求解高次同余方程
更普适，还能对付a为偶数的情形。
--------------------------------------------------------------------------

从2006年到2016年，10年间出现了很多BB2006的变种。CVE-2016-1494其实只是下面
这种变种的同型:

Why the exponent 3 error happened - Hal Finney [2006-09-17]
http://www.mail-archive.com/cryptography@metzdowd.com/msg06693.html

Hal Finney在此揭示了一种错误实现，接受:

x="00 01 00 GARBAGE HASH"

CVE-2016-1494相比之下，变化不大，接受:

x="00 01 GARBAGE 00 ASN.1 HASH"，要求GARBAGE中不包含00。

如果抽象一下，它们都接受:

x="apart || gpart || bpart"

其中apart、bpart相对固定，gpart相对任意。因此上述二者的求解算法是相容的。

BB2006及其变种不是教条式的结论，比如什么只能攻击e=3，但也不是天马行空式的，
比如幻想攻击e=65537之流。完全取决于模板x等于什么以及n有多大，x不同n不同，
所能容忍的e的上限就会不同。

比如:

x="00 01 00 GARBAGE HASH"
n=4096
hashtype=sha1
e=17

e=17就是此时的上限。"n=4096,e=17,sha1"在现实世界中是存在的，不是幻想或纯理
论上的存在，这种情况下就是安全漏洞。

我还见过有人在问如何攻击e=41，当然他没说模板x是什么，但想必他在现实世界中
碰上了新的BB2006变种。

可以预见，BB2006变种将在相当长的时间段内继续存在于现实世界，且不说蠢才代代
有的问题，要知道战场很多的，不是一处。