立即停止使用RSA

在Trail of Bits，我们评审过大量代码。从主流开源项目到激动人心的新专有软件，我们见识过一切。但这些系统都有一个共同点：出于某种难以解释的原因，人们似乎仍然认为RSA是一个值得使用的密码系统。让我为您节省时间和金钱直接说明——如果您带着使用RSA的代码库来找我们，您将需要支付我们解释为何应该停止使用它的一小时费用。

RSA本质上是一个脆弱的密码系统，包含无数普通软件工程师难以避免的陷阱。弱参数难以（甚至不可能）检查，其糟糕的性能迫使开发人员采取风险捷径。更糟糕的是，在发现20年后，填充预言机攻击仍然猖獗。虽然理论上可能正确实现RSA，但数十年的毁灭性攻击证明，这种壮举在实践中可能无法实现。

什么是RSA？

RSA是一种公钥密码系统，有两个主要用例。第一个是公钥加密，允许用户Alice发布公钥，让任何人向她发送加密消息。第二个用例是数字签名，允许Alice"签名"消息，使任何人都能验证消息未被篡改。RSA的便利之处在于签名算法基本上只是加密算法的反向运行。因此，在本文其余部分，我们通常将两者都称为RSA。

要设置RSA，Alice需要选择两个素数p和q，生成整数模N = pq的群。然后她需要选择公钥指数e和私钥指数d，使得ed = 1 mod (p-1)(q-1)。基本上，e和d需要互为逆元。

选择这些参数后，另一个用户Bob可以通过计算C = Mᵉ (mod N)向Alice发送消息M。Alice然后可以通过计算M = Cᵈ (mod N)解密密文。相反，如果Alice想要签名消息M，她计算S = Mᵈ (mod N)，任何用户都可以通过检查M = Sᵉ (mod N)来验证签名是否来自她。

这是基本概念。我们稍后会讨论填充——两个用例都必需——但首先让我们看看参数选择过程中可能出什么问题。

为自己设置失败

RSA要求开发人员在设置过程中选择相当多的参数。不幸的是，看似无害的参数选择方法会以微妙的方式降低安全性。让我们遍历每个参数选择，看看哪些陷阱等待着选择不当的人。

素数选择

RSA的安全性基于这样一个事实：给定一个（大）数N，它是两个素数p和q的乘积，对于不知道p和q的人来说，分解N是困难的。开发人员负责选择组成RSA模数的素数。与其他密码协议（只需选择一些随机字节就足够）的密钥生成相比，这个过程极其缓慢。因此，开发人员通常尝试生成特定形式的素数，而不是生成真正随机的素数。这几乎总是以糟糕告终。

有许多方法可以选择使分解N容易的素数。例如，p和q必须是全局唯一的。如果p或q在另一个RSA模数中被重用，那么使用GCD算法可以轻松分解两者。糟糕的随机数生成器使这种情况相当常见，研究表明2012年大约1%的TLS流量容易受到此类攻击。此外，p和q必须独立选择。如果p和q共享大约一半的高位，那么可以使用费马方法分解N。事实上，甚至素数测试算法的选择也会影响安全性。

也许最广为人知的素数选择攻击是RSALib中的ROCA漏洞，影响了许多智能卡、可信平台模块甚至Yubikeys。在这里，密钥生成仅使用特定形式的素数来加快计算时间。使用巧妙的数论技巧可以轻松检测以这种方式生成的素数。一旦识别出弱系统，素数的特殊代数特性允许攻击者使用Coppersmith方法分解N。更具体地说，这意味着如果坐在我旁边的工作人员使用智能卡访问私人文档，并在午餐时将其留在桌子上，我可以克隆智能卡并让自己访问他们所有敏感文件。

重要的是要认识到，在这些情况下，直觉上并不明显以这种方式生成素数会导致系统完全失败。素数的真正微妙的数论特性对RSA的安全性有重大影响。期望普通开发人员 navigate 这个数学雷区严重削弱了RSA的安全性。

私钥指数

由于使用大私钥会对解密和签名时间产生负面影响，开发人员有动机选择小的私钥指数d，特别是在智能卡等低功耗环境中。然而，当d小于N的四次方根时，攻击者可能恢复私钥。相反，鼓励开发人员选择大的d，以便可以使用中国剩余定理技术加速解密。然而，这种方法的复杂性增加了微妙实现错误的可能性，可能导致密钥恢复。事实上，我们去年夏天的一位实习生用我们的符号执行工具Manticore模拟了这类漏洞。

人们可能会在这里指出，通常设置RSA时，首先生成一个模数，使用固定的公钥指数，然后求解私钥指数。这可以防止低私钥指数攻击，因为如果总是使用推荐的公钥指数（下一节讨论），那么永远不会得到小的私钥指数。不幸的是，这假设开发人员实际上这样做。在人们实现自己的RSA的情况下，使用标准RSA设置程序的所有赌注都无效，开发人员经常做奇怪的事情，比如先选择私钥指数，然后求解公钥指数。

公钥指数

就像私钥指数情况一样，实现者希望使用小的公钥指数来节省加密和验证时间。在这种情况下通常使用费马素数，特别是e = 3、17和65537。尽管密码学家推荐使用65537，但开发人员经常选择e = 3，这给RSA密码系统引入了许多漏洞。

开发人员甚至使用e = 1，这实际上并不加密明文

当e = 3或类似的小数字时，许多事情可能出错。低公钥指数通常与其他常见错误结合，允许攻击者解密特定密文或分解N。例如，Franklin-Reiter攻击允许恶意方解密两个由已知固定距离相关的消息。换句话说，假设Alice只向Bob发送"chocolate"或"vanilla"。这些消息将通过已知值相关，并允许攻击者Eve确定哪些是"chocolate"，哪些是"vanilla"。一些低公钥指数攻击甚至导致密钥恢复。如果公钥指数小（不仅仅是3），知道密钥几位信息的攻击者可以恢复剩余位并破解密码系统。虽然许多这些e = 3对RSA加密的攻击通过填充缓解，但实现自己RSA的开发人员以惊人高的速率未能使用填充。

在存在低公钥指数的情况下，RSA签名同样脆弱。2006年，Bleichenbacher发现一种攻击，允许攻击者在许多RSA实现中伪造任意签名，包括Firefox和Chrome使用的实现。这意味着来自易受攻击实现的任何TLS证书都可能被伪造。这种攻击利用了许多库使用小公钥指数并在处理RSA签名时省略简单填充验证检查的事实。Bleichenbacher的签名伪造攻击如此简单，以至于它成为密码学课程中常用的练习。

参数选择困难

所有这些参数攻击的共同点是，可能参数选择的范围远大于安全参数选择的范围。开发人员 expected 自己 navigate 这个充满风险的选择过程，因为除了公钥指数外，所有参数都必须私下生成。没有简单的方法来检查参数是否安全；相反，开发人员需要非密码学家不应期望的数学知识深度。虽然使用带填充的RSA可能在存在坏参数时拯救您，但许多人仍然选择使用损坏的填充或根本不用填充。

无处不在的填充预言机攻击

正如我们上面提到的，仅仅开箱即用地使用RSA并不完全有效。例如，引言中阐述的RSA方案如果同一明文被加密多次，将产生相同的密文。这是一个问题，因为它将允许对手从上下文中推断消息内容而无法解密。这就是为什么我们需要用一些随机字节填充消息。不幸的是，最广泛使用的填充方案PKCS #1 v1.5通常容易受到称为填充预言机攻击的攻击。

填充预言机相当复杂，但高层思想是向消息添加填充要求接收方执行额外检查——消息是否正确填充。当检查失败时，服务器抛出无效填充错误。这一条信息足以缓慢解密选定的消息。这个过程很繁琐，涉及数百万次操作目标密文以隔离导致有效填充的变化。但那个错误消息是最终解密选定密文所需的一切。这些漏洞特别糟糕，因为攻击者可以使用它们恢复TLS会话的预主密钥。有关攻击的更多细节，请查看这个优秀的解释器。

对PKCS #1 v1.5的原始攻击早在1998年由Daniel Bleichenbacher发现。尽管已有20多年历史，这种攻击今天继续困扰许多真实世界系统。这种攻击的现代版本通常涉及比Bleichenbacher最初描述的稍复杂的填充预言机，例如服务器响应时间或在TLS中执行某种协议降级。一个特别令人震惊的例子是ROBOT攻击，如此糟糕以至于一组研究人员能够用Facebook和PayPal的密钥签名消息。有些人可能认为这实际上不是RSA的错——底层数学没问题，人们只是在几十年前搞砸了一个重要标准。问题是，自1998年以来，我们有一个具有严格安全证明的标准填充方案OAEP。但几乎没有人使用它。即使他们使用，OAEP以难以实现而闻名，并且通常容易受到Manger的攻击，这是另一种可用于恢复明文的填充预言机攻击。

这里的根本问题是使用RSA时需要填充，这种增加的复杂性使密码系统面临巨大的攻击面。消息是否正确填充的单一比特信息可能对安全性产生如此大的影响，使得开发安全库几乎不可能。TLS 1.3不再支持RSA，因此我们预计未来这类攻击会减少，但只要开发人员继续在自己的应用程序中使用RSA，就会有填充预言机攻击。

那么应该使用什么代替？

人们通常更喜欢使用RSA，因为他们认为它在概念上比有些令人困惑的DSA协议或月球数学椭圆曲线密码学（ECC）更简单。但虽然直观上可能更容易理解RSA，但它缺乏这些其他更复杂系统的误用抵抗性。

首先，一个常见的误解是ECC超级危险，因为选择坏曲线可能完全沉没您。虽然曲线选择对安全性有重大影响是事实，但使用ECC的一个好处是参数选择可以公开完成。密码学家做出所有困难的参数选择，以便开发人员只需生成随机字节数据用作密钥和随机数。开发人员理论上可以构建具有可怕参数的ECC实现，并未能检查无效曲线点等事项，但他们倾向于不这样做。一个可能的解释是ECC背后的数学如此复杂，以至于很少有人有足够信心实际实现它。换句话说，它恐吓人们使用由知道他们在做什么的密码学家构建的库。另一方面，RSA如此简单，以至于可以（糟糕地）在一小时内实现。

其次，任何基于Diffie-Hellman的密钥协商或签名方案（包括椭圆曲线变体）不需要填充，因此完全回避填充预言机攻击。考虑到RSA在避免这类漏洞方面记录非常差，这是一个重大胜利。

Trail of Bits推荐使用Curve25519进行密钥交换和数字签名。加密需要使用称为ECIES的协议完成，该协议结合椭圆曲线密钥交换和对称加密算法。Curve25519旨在完全防止其他曲线可能出错的一些事情，并且性能非常好。更好的是，它在libsodium中实现，该库具有易于阅读的文档并适用于大多数语言。