伪造Python-rsa中的签名_python教程_开发教程

通过看python-rsa的源代码，我们发现它存在一个漏洞，该漏洞是基于Bleichenbacher'06 attack研究出来的针对RSA签名伪造的一个简单的变种，是由于公钥指数太低导致的。
该漏洞可导致任意信息伪造签名，不过有一个前提是公钥需要有一个低指数，例如3。而幸运的是，虽然在python-rsa中e=65537已经写死在代码里了，但是这个库提供了很多选项来配置现有的密钥，这里就有可能把e设置成3。
接下来我们就来讲讲这个漏洞的背景和详细攻击方法，这也是我最喜欢的一种攻击方式, 因为它非常简练。如果你对这个漏洞有兴趣，那么不妨看下。
Bleichenbacher'06RSA算法需要用三个参数N,e和d产生一个密钥对。如果你想对一个数m进行加密或解密，就要先对m进行乘方运算，然后再分别与e和d进行模运算（mod）产生m的密文或者明文。如果你把d当成保密密钥并且公开e和N，攻击者是很难通过公开的e和N推算出d并完成d的功能（因为开根号和对数运算很难通过程序模块实现）。
当你把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)
在这里并没有检查填充的内容是否是FF字节。这就意味着我们可以把不完整的立方根隐藏在00 01前缀和00分隔符之间。这样的变种在文献中经常被提到的，实际上他是BERserk攻击的一个子集。有很多种方法可以有效的利用它，这里使用的方法是最非常直观的一种方法。
我们的目标信息三次方后有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
通过上面的计算我们就能得到结果。如果我们的签名是以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这么小数值的算法中。(责任编辑：最模板)