说真的，停止使用RSA

在Trail of Bits中，我们回顾了大量代码。从主要的开源项目到激动人心的新专有软件，我们都见识过了。但所有这些系统的一个共同点是，出于某种莫名其妙的原因，人们似乎仍然认为RSA是一个很好的密码系统。让我为你节省一点时间和金钱，直接告诉我们-如果你带着一个使用RSA的代码库来找我们，你将为我们解释为什么你应该停止使用它所需的时间付费。

RSA是一种本质上脆弱的密码系统，它包含了无数的步枪，一般的软件工程师是无法避免的。弱参数即使不是不可能，也很难检查，而且其糟糕的性能迫使开发人员走危险的捷径。更糟糕的是，甲骨文攻击在被发现20年后依然猖獗。虽然在理论上正确实现RSA可能是可能的，但数十年的毁灭性攻击证明，这样的壮举在实践中可能是无法实现的。

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

要设置RSA，Alice需要选择两个素数p和q，这两个素数将生成模N=pq的整数组。然后，她需要选择公共指数e和私有指数d，使得ed=1mod(p-1)(q-1)。基本上，e和d需要相互倒置。

一旦选择了这些参数，另一个用户Bob就可以通过计算C=Me(ModN)向Alice发送消息M。然后，Alice可以通过计算M=Cd(ModN)来解密密文。相反，如果Alice想要签署一条消息M，她会计算S=Md(ModN)，任何用户都可以通过检查M=Se(ModN)来验证该消息是否由她签名。

这就是基本理念。稍后我们将介绍填充(这两种用例都很重要)，但首先让我们看看在参数选择过程中会出什么问题。

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漏洞，它影响了许多智能卡、可信平台模块，甚至Yubikey。这里，密钥生成只使用特定形式的素数来加快计算时间。用巧妙的数论技巧检测这种方式产生的素数是微不足道的。一旦识别出弱系统，素数的特殊代数性质允许攻击者使用Coppersmith的方法来分解N。更具体地说，这意味着如果工作时坐在我旁边的人使用智能卡，允许他们访问私人文档，而他们在午餐时把智能卡放在桌子上，我就可以克隆智能卡，并允许我自己访问他们所有的敏感文件。

重要的是要认识到，在这些情况下，直觉上都不是显而易见的，以这种方式生成素数会导致完全的系统故障。素数的微妙数论性质对RSA的安全性有很大影响。期望普通开发人员在这个数学雷区导航严重破坏了RSA的安全性。

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

人们可能会把我叫到这里，指出通常在设置RSA时，首先生成一个模数，使用固定的公共指数，然后求出私有指数。这可以防止低私有指数攻击，因为如果您总是使用推荐的公共指数之一(在下一节中讨论)，那么您将永远不会得到一个小的私有指数。不幸的是，这假设开发人员真的这么做了。在人们实现自己的RSA的情况下，就使用标准RSA设置过程而言，所有的赌注都是错误的，开发人员经常会做一些奇怪的事情，比如首先选择私有指数，然后再为公共指数求解。

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

当e=3或类似的小数字时，很多事情都可能出错。低公开指数通常与其他常见错误结合在一起，从而允许攻击者解密特定密文或因数N。例如，Franklin-Reiter攻击允许恶意方解密通过已知固定距离关联的两条消息。换句话说，假设Alice只给Bob发送“巧克力”或“香草”。这些消息将通过一个已知值进行关联，并允许攻击者确定哪些是“巧克力”，哪些是“香草”。一些低公开指数攻击甚至导致密钥恢复。如果公开指数很小(不只是3)，知道密钥的几位的攻击者可以恢复剩余的位并破解密码系统。虽然许多针对RSA加密的e=3攻击都可以通过填充来缓解，但实现自己RSA的开发人员未能以惊人的速度使用填充。

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

所有这些参数攻击的共同点是，可能的参数选择范围比安全参数选择范围大得多。开发人员预计将独自驾驭这一令人担忧的选择过程，因为除了公共指数之外，所有的选择都必须由私人产生。没有简单的方法来检查参数是否安全；相反，开发人员需要深入的数学知识，这不应该是非密码学家所期望的。虽然使用带填充的RSA可能会在出现错误参数的情况下节省您的时间，但许多人仍然选择使用损坏的填充或根本不使用填充。

正如我们上面提到的，仅仅使用RSA开箱即用并不是很有效。例如，如果同一明文被多次加密，则引言中列出的RSA方案将产生相同的密文。这是一个问题，因为这会让对手在无法解密的情况下从上下文中推断出消息的内容。这就是我们需要用一些随机字节填充消息的原因。不幸的是，最广泛使用的填充方案PKCS#1v1.5经常容易受到所谓的填充先知攻击。

填充先知是相当复杂的，但是高级思想是向消息添加填充需要接收者执行额外的检查-消息是否被正确填充。当检查失败时，服务器抛出无效填充错误。这一条信息足以慢慢解密一条选定的消息。该过程是乏味的，并且涉及对目标密文进行数百万次操作以隔离导致有效填充的改变。但这条错误消息就是最终解密所选密文所需的全部信息。这些漏洞特别糟糕，因为攻击者可以利用它们来恢复TLS会话的预主密码。有关此次攻击的更多细节，请查看这篇出色的解说员。

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

这里的根本问题是，当使用RSA时，填充是必要的，而这种增加的复杂性使密码系统面临巨大的攻击面。消息是否正确填充的一丁点信息都可能对安全性产生如此大的影响，这一事实使得开发安全的库几乎是不可能的。TLS 1.3不再支持RSA，因此我们可以预期在未来会看到更少的此类攻击，但只要开发人员继续在他们自己的应用程序中使用RSA，就会有填充Oracle的攻击。

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

首先，一种常见的误解是，ECC是超级危险的，因为选择一条糟糕的曲线会让你完全沉没。虽然曲线选择确实对安全性有重大影响，但使用ECC的一个好处是参数选择可以公开进行。密码学家做出了所有困难的参数选择，因此开发人员只需要生成随机字节的数据就可以用作密钥和随机数。从理论上讲，开发人员可能会使用糟糕的参数构建ECC实现，并且无法检查无效曲线点之类的东西，但他们往往不会这样做。一个可能的解释是，ECC背后的数学是如此复杂，以至于很少有人有足够的信心真正实施它。换句话说，它恐吓人们使用由知道自己在做什么的密码学家建立的库。另一方面，RSA非常简单，可以在一个小时内(很差地)实现它。

其次，任何基于Diffie-Hellman的密钥协议或签名方案(包括椭圆曲线变体)都不需要填充，因此完全避开了填充先知攻击。考虑到RSA在避免此事件方面的记录非常糟糕，这是一次重大胜利

BITS建议使用Curve25519进行密钥交换和数字签名。加密需要使用名为ECIES的协议来完成，该协议将椭圆曲线密钥交换与对称加密算法相结合。Curve25519的设计完全避免了其他曲线可能出现的一些问题，而且性能非常好。更棒的是，它是用libNa实现的，它有易于阅读的文档，并且可以在大多数语言中使用。

RSA是安全通信发展的一个重要里程碑，但最近二十年的密码学研究已经使其过时。用于密钥交换和数字签名的椭圆曲线算法早在2005年就已标准化，此后已集成到直观且防误用的库中，如lib钠。RSA在今天仍然被广泛使用，这一事实既表明密码学家没有充分阐明RSA固有的风险，也表明开发人员高估了他们成功部署RSA的能力。

安全社区需要开始考虑这是一个群体免疫问题--虽然我们中的一些人可能能够通过设置或实现RSA这一极其危险的过程，但向开发人员发出的例外信号是，在某种程度上仍然建议使用RSA。尽管StackExchange和Github Readme上有许多警告和警告，但很少有人相信他们会搞砸RSA，所以他们肆无忌惮地行事。最终，用户将为此买单。这就是为什么我们都需要同意，在2019年使用RSA是完全不可接受的。没有例外。