Python-rsa中的签名伪造

通过看 python-rsa 的源代码，我们发现它存在一个漏洞，该漏洞是基于 Bleichenbacher'06 attack 研究出来的针对RSA签名伪造的一个简单的变种，是由于公钥指数太低导致的。

该漏洞可导致任意信息伪造签名，不过有一个前提是公钥需要有一个低指数，例如3。而幸运的是，虽然在python-rsa中e=65537已经写死在代码里了，但是这个库提供了很多选项来配置现有的密钥，这里就有可能把e设置成3。

接下来我们就来讲讲这个漏洞的背景和详细攻击方法，这也是我最喜欢的一种攻击方式, 因为它非常简练。如果你对这个漏洞有兴趣，那么不妨看下。

当你把RSA用于公共密钥算法进行加密时，你只需要发出(N, e)。例如，Alice要发送给你信息时候，她会用算法m^e mod N进行加密后发送给你，然后你可以通过(m ^ e) ^ d = m mod N对密文进行解密。数字签名是RSA算法的另一个广泛运用的地方：你可以用m^d mod N来签名一个信息，然后收件人用 (N, e)来执行(m ^ d) ^ e = m mod N。只有你有参数d，也就是说，你可以计算出(m ^ d) ^ e 的值进而计算出m的值。

你可能已经注意到了，事实上m并不是你要传递的那个任意信息。事实上它只能是一个数字，而且这个数字要比N小。因此，实际要加密任意一个信息时，我们经常会用对称加密算法（例如AES）加密数据，然后对这段信息产生的hash值（例如SHA2）进行签名。这样的就足够转化成一个比N小的数字。

最广泛被使用于RSA签名的方案 PKCS#1 1.5 是在10年前被设计出来的（并且依然普遍的被运用在一些传统的协议上，比如TLS和DNSSEC）。PKCS#1 1.5的签名原理是这样的：先计算出你要签名的信息的hash值，然后把它编码成像下面的例子一样：

00 01 FF FF ... FF FF 00 ASN.1 HASH

其中，ASN.1是有这段hash值的类型和长度混合后进行二进制编码得到。然后你用RSA算法对这段内容进行签名。可以看到FF字节其实是用来填充这段信息的，使他的长度和N一样。

BB'06的攻击思路就是：虽然在没有d的情况下几乎是不可能找到一个数字的e次方会正好等于以上提到的数据，但是我们可以得到一个近似的值，例如，在对目标信息开e次方根的时候，如果e足够小，那么结果将接近明文，如下例：

00 01 FF 00 ASN.1 HASH GARBAGE

如果验证函数没有检查hash值的末尾有没有补齐（没有足够填充足够FF字节），我们就可以伪造签名，这通过任何一个使用了很小的e的公共密钥对就能实现。正如你所见，由于对密文取e次方根，e又足够小，就不会经过这个系数，于是N与e就变得完全不相关，这对第二步的计算很有用（可以任意挑选一个key，例如3）

Bleichenbacher在展示对CRYPTO'06的残存会话的攻击过程中，提出了“笔和纸”方法来产生一个数字s，当对一个信息进行e次方的运算（e的值足够小）时，给要加密的信息加上一个前缀，就像 documented by Hal Finney 这篇文章记录的，这里就不多写了。但我更喜欢把它简化成立方根的方法。

在之前，OpenSSL和NSS 都很容易被这种方式攻击。当这种攻击手法的变种在其他库中被找到，就使得这种手法变成了密码学攻击中常用的手段。最近， BERserk 又攻击了NSS，所用的手法并没有与BB'06所用的差多少，都是通过ASN.1 bug在信息中间隐藏了e。 cryptopals 这个网站甚至对所有的BB'06进行收录成了“加密情报联盟”。

python-rsa漏洞

python-rsa漏洞是BB'06的一个简单的变种，因为这也是把一段hash值和ASN.1对象进行对比。

以下是verify()函数的源代码：

def verify(message, signature, pub_key):       blocksize = common.byte_size(pub_key.n)     encrypted = transform.bytes2int(signature)     decrypted = core.decrypt_int(encrypted, pub_key.e, pub_key.n)     clearsig = transform.int2bytes(decrypted, blocksize)       # If we can't find the signature  marker, verification failed.     if clearsig[0:2] != b('/x00/x01'):         raise VerificationError('Verification failed')       # Find the 00 separator between the padding and the payload     try:         sep_idx = clearsig.index(b('/x00'), 2)     except ValueError:         raise VerificationError('Verification failed')       # Get the hash and the hash method     (method_name, signature_hash) = _find_method_hash(clearsig[sep_idx+1:])     message_hash = _hash(message, method_name)       # Compare the real hash to the hash in the signature     if message_hash != signature_hash:         raise VerificationError('Verification failed')       return True def _find_method_hash(method_hash):       for (hashname, asn1code) in HASH_ASN1.items():         if not method_hash.startswith(asn1code):             continue           return (hashname, method_hash[len(asn1code):])       raise VerificationError('Verification failed')   HASH_ASN1 = {       'MD5': b('/x30/x20/x30/x0c/x06/x08/x2a/x86'              '/x48/x86/xf7/x0d/x02/x05/x05/x00/x04/x10'),     'SHA-1': b('/x30/x21/x30/x09/x06/x05/x2b/x0e'                '/x03/x02/x1a/x05/x00/x04/x14'),     'SHA-256': b('/x30/x31/x30/x0d/x06/x09/x60/x86'                  '/x48/x01/x65/x03/x04/x02/x01/x05/x00/x04/x20'),     'SHA-384': b('/x30/x41/x30/x0d/x06/x09/x60/x86'                  '/x48/x01/x65/x03/x04/x02/x02/x05/x00/x04/x30'),     'SHA-512': b('/x30/x51/x30/x0d/x06/x09/x60/x86'                  '/x48/x01/x65/x03/x04/x02/x03/x05/x00/x04/x40'), }

如果输入的是以下的数据，从代码中可以看到，这个函数会接收所有结构里的数据

00 01 XX XX ... XX XX 00 ASN.1 HASH

如上面的内容中，XX不能是00字节。在处理这个地方的代码，程序是找到了00 01前缀后的下一个00，如下：

sep_idx = clearsig.index(b('/x00'), 2)

我们的目标信息三次方后有00 01这样的前缀，以及后缀（00 ASN.1 HASH）。前缀很容易得到（只要求立方根），所以我们直接从后缀入手。我们用事先构造好的信息s和他的立方c 。我们从第0位开始算起，第0位是在最右边，最重要的一位。

我们的方法最重要的原理是跳过s中的第N位使得同样也能跳过c中的第N位，并且使得所有从0——N-1的数字都不受影响。如果你无法想象到这些，下图有一个“pen-and-paper”操作的每一步步骤。利用这一特性，我们可以简单的通过从右开始遍历这个后缀的二进制位从而建立S，然后翻转s中的这个位，无论这个位在c中是不是我们想要的。

让我们看看一下例子：查找s中的位数，立方后得以1010101101结尾的c。

9876543210  <- Indexes   s:     0000000001  <- Initial s  c:     0000000001  <- Bit 0 an 1 match, skip  tgt:   1010101101  <- Target suffix of c   s:     0000000001  c:     0000000001  <- Bit 2 doesn't match, flip in s  tgt:   1010101101   s:     0000000101  c:     0001111101  <- Bit 3 matches, skip  tgt:   1010101101   s:     0000000101  c:     0001111101  <- Bit 4 doesn't, flip in s  tgt:   1010101101   s:     0000010101  c: 10010000101101  <- Bit 7 doesn't match, flip in s  tgt:   1010101101   s:     0010010101  c: ...00110101101  <- Bit 8 doesn't match, flip in s  tgt:   1010101101   s:     0110010101  c: ...10010101101  <- Bit 9 doesn't match, flip in s  tgt:   1010101101   s:     1110010101  c: ...01010101101  <- Done!  tgt:   1010101101   1110010101 ^ 3 = 101101111101011111101010101101                                         ^^^^^^^^^^

通过上面的计算我们就能得到结果。如果我们的签名是以1110010101结尾，立方后的结尾将是1010101101。如果我们用同样的流程处理后缀是00 ASN.1 HASH 我们将得到我们伪造的签名的最后面的一个部分。

相比较而言前缀就比较容易构造：只需要计算00 01 XX XX …的立方根，其中XX 是随机的字节，需要注意的是，这个字节要和公钥的长度一样。这没法得到一个准确的立方根，但它在计算出来的前两个字节已经足够精确了。（这一步和BB'06的一毛一样）

接下来只需要通过截断len(sig_suffix)字节来连接前缀和后缀就可以。后缀很短，因此，改变他将会影响到两个高位字节的立方值，同时，如果我们在最左边加上一个字节，并不会影响到后缀。

最后的问题：在立方值里面必须没有其他的00字节。比较懒的处理方法：用不同的随机字节来重复计算前缀，知道不存在00字节。

安全加密实践

知道了这个漏洞在过去的10年里如何疯狂的被利用，你也许会想RSA签名验证是一个很大的问题，并且我们一直被这个错误限制住，至少在PKCS#1 1.5中是这样的。

尽管PKCS#1 1.5具有被攻击危险，但是只要这么做就可以完美的安全的验证：把节解析已编码过的签名换一个，换成可以验证完整填充、ASN.1 和hash值的算法，然后对比用户和攻击者的不同。这一点AGL 和 tqbf 表达的比我好。这样就完美的杀死攻击者攻击你的机会。极端情况下，有一些很快速的计算算法来算出RSA的，即使在e=65537的情况，所以没有理由把自己暴露在e=3这么小数值的算法中。

最后这里是提交的CVE漏洞 CVE-2016-1494 和提交的 补丁 。

* 参考来源 filippo.io ，编译/东二门陈冠希，转载请注明来自FreeBuf黑客与极客（FreeBuf.COM）