Python-rsa中的签名伪造

2016-01-15 +6 335853人围观 ,发现 4 个不明物体 漏洞资讯

*本文中涉及到的相关漏洞已报送厂商并得到修复,本文仅限技术研究与讨论,严禁用于非法用途,否则产生的一切后果自行承担。


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

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

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

Bleichenbacher'06
RSA算法需要用三个参数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  <- 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)

发表评论

已有 4 条评论

取消
Loading...

特别推荐

推荐关注

填写个人信息

姓名
电话
邮箱
公司
行业
职位
css.php