您能否解释Bleichenbacher对PKCS＃1 v1.5的CCA攻击？

#1 楼

当使用PKCS＃1 v1.5使用RSA加密某些内容时，将首先填充要加密的数据，然后将填充后的值转换为整数，然后应用RSA模幂（具有公用指数）。解密后，将应用模块化指数（具有私有指数），然后删除填充。 Bleichenbacher攻击的核心依赖于一个oracle：该攻击在某处存在某个系统的情况下起作用，在给定加密消息长度的字节序列的情况下，该系统可以判断解密是否会产生某种具有正确填充格式或不是。

例如SSL / TLS服务器。在最初的握手中，客户端应该在某个时候生成一个随机密钥（“主密码”），并使用服务器的公共密钥对其进行加密，然后发送。服务器解密该值，获取主密码前的机密，然后从该主机密码前的密钥计算用于其余连接的对称加密的密钥。使用该标准进行指导，客户端发送ClientKeyExchange（其中包含加密的主密码），然后依次发送ChangeCipherSpec和Finished；这最后一条消息使用派生的对称密钥加密，并且其内容由服务器验证。

如果客户端向服务器发送正确长度的随机字节序列，而不是向服务器发送正确加密的主机密，则服务器在大多数情况下会以一条错误消息响应，提示“我试图解密您的ClientKeyExchange内容，但这失败了，其中没有适当的填充”。但是，碰巧的是，在应用了模幂运算后，随机字符串可能会产生一些东西，看起来确实像是预先掌握了正确填充的机密。在这种情况下，服务器不会抱怨ClientKeyExchange，而是抱怨Finished消息，该消息将被错误地加密。

这就是攻击者想要的信息：解密后发送的字节序列是否看起来正确填充。


让我们看一下更多技术细节。在RSA中，令$ n $为公共模数。假设$ M $是要用$ n $加密的消息（对于SSL，$ M $是主密码，长度为48个字节）。用于加密的PKCS＃1 v1.5填充包括在左侧添加一些字节，以便填充后的总长度等于$ n $。例如，如果服务器的公共密钥是2048位RSA密钥，则$ n $的长度为256字节，因此填充的$ M $也应具有256字节的长度。

正确填充的消息$ M $具有以下格式：

0x00 0x02 [some non-zero bytes] 0x00 [here goes M]

，因此字节序列将以值0的字节开始，然后是值2的字节，然后是应该具有随机值（但不能为零），然后是值0的字节，然后是$ M $本身。调整非零字节的数量，以使总长度等于$ n $的长度。解密后，服务器将查看前两个字节，并要求它们按该顺序等于0x00和0x02。然后它将扫描值0的下一个字节，从而跳过所有随机非零字节。这样，可以清楚地删除填充。

因此，如果客户端发送一个随机的字节串，则它的概率大约在$ 2 ^ {-15} $和$ 2 ^ {-17之间} $遵循PKCS＃1填充格式（即前两个字节为0x00 0x02的概率，此后至少有一个字节的值为0；确切的概率取决于$ n $的长度和值）。

攻击情形如下：有一个SSL服务器，它将根据是否找到正确的PKCS＃1填充发送不同的错误消息。或者，可以通过其他一些信息泄漏来区分这两种情况（例如，如果填充正确，服务器将花费更长的时间进行响应）。他观察到ClientKeyExchange，因此他看到了加密的消息$ c $。他知道$ c = m ^ e \ pmod n $，其中$ e $是公共指数，而$ m $是该连接的已填充主密码。他想恢复$ m $或至少包含在$ m $中的主密码，因为这将使他能够计算用于连接的对称密钥。将启动与服务器的许多连接。对于每个连接，攻击者都会生成一个值$ s $并将值$ c'= cs ^ e \ pmod n $发送为ClientKeyExchange。服务器对此解密，并获得$ m'=（cs ^ e）^ d \ pmod n $（$ d $是私有指数），它等于$ ms \ pmod n $。在大多数情况下，此$ ms $值将无法正确填充（不会以0x00 0x02开头，也不会包含额外的0x00）。但是，以低但不可忽略的概率（大约每30000至130000次尝试一次），幸运的是$ ms \ pmod n $值看起来会被填充。如果真是这样，则服务器的行为会将该事实通知攻击者。攻击者随后了解到，对于此值$ s $（攻击者知道，因为他选择了它），则$ ms \ pmod n $在特定范围内（以字节编码时，以0x00 0x02开头的整数范围使用big-endian约定）。

其余的攻击将再次尝试，并精心选择了随机值$ s $。每次服务器响应“这是正确的PKCS＃1填充”时，这都会提供一些信息，有助于攻击者缩小对$ m $的猜测。总共经过数百万次连接后，攻击者学会了足够的知识来精确地确定$ m $，从而产生了主密码之前的机密。一旦您知道RSA填充的工作原理，剩下的只是数学，这并不难。

为了防止这种攻击，SSL服务器不会通知客户端有关填充问题的信息。如果解密由于填充不正确而失败，则服务器将继续使用随机的主密码（此错误将在处理Finished消息时发生真正的错误）。 PKCS＃1 v1.5填充（用于加密）是它不是很冗余；实际上，随机字节是随机的，没有任何特定的强制值。这就是允许以很小但不可忽略的概率“随机填充”随机字节序列的原因。较新的PKCS＃1版本描述了一种新的填充类型，称为OAEP，它使用哈希函数添加大量内部冗余，这使得随机字符串与填充格式匹配非常不可能。这样可以防止Bleichenbacher的进攻。不幸的是，SSL仍然使用PKCS＃1 v1.5。