您本可以发明那个蓝牙攻击 - Trail of Bits博客

2018年8月1日
攻击, 密码学

近期一个严重的蓝牙漏洞受到了广泛关注。这是Biham和Newman的重大发现。鉴于BLE在厌恶打补丁的物联网世界中的流行，该漏洞具有严重的影响。然而，它异常清晰和简单。与许多椭圆曲线漏洞不同，普通人完全可以理解这个漏洞及其利用方式。这是一个概念上易于理解的攻击的酷炫应用。

本文描述了该漏洞、如何利用它，以及它如何在蓝牙协议中具体发生。但首先，让我们快速学习椭圆曲线和无效曲线点攻击。

什么是椭圆曲线？

这是一个相当误导人的名称。在密码学中，“椭圆曲线”既不是椭圆形的，也不是连续曲线。相反，它是(x, y)坐标的集合，其中x和y在0和p之间，p是素数，且y² = x³ + ax + b mod p，外加一个额外的“无穷远点”，其行为反直觉地类似于零；将其加到任何东西上，都会得到相同的数。图1显示了这样一条曲线，其中y² = x³ - x，x和y的范围从0到71。（技术上，x和y定义在有限域上，但当p是素数时，所有相同阶p的有限域都是同构的，因此我们的定义是等价的）。

图1：一条椭圆曲线（密码学中使用）

椭圆曲线有一些有用的属性：

• 您可以用看起来很像常规加法的规则将椭圆曲线点相加：x + y = y + x, x + (y + z) = (x + y) + z, 等等。这是因为曲线上的点形成一个阿贝尔群。您可以在下面的图2中看到这种加法的可视化。
• 一个点可以通过将其自身加n次来乘以某个自然数（称为n）。
• 对于每个点(x, y)，都有一个逆点(x, -y)，使得任何点加上其逆点等于无穷远点。
• 最值得注意的是，如果您在上述方程中很好地选择a、b和n，乘以一个常规数是一个陷门函数：给定一个点P和一个数n，计算一个点Q使得Q = n * P非常容易，但给定一个点P和一个点Q，找到n使得Q = n * P极其困难。这个简单的硬度假设让我们构建了许多密码算法。

图2：加法及无穷远点（注意：这些插图使用连续曲线进行可视化，但这仍然不是我们实际使用的）

通常，椭圆曲线算法围绕特定曲线编写。各方交换曲线上的点和标量，并使用它们进行如上定义的计算。然而，当这些算法暴露于不满足曲线方程的(x, y)对时，问题就会出现，这些可以被利用来执行所谓的“无效曲线点攻击”。

什么是无效曲线点攻击？

记住，一个点是一对(x, y)，使得对于某些a、b和n，有y² = x³ + ax + b mod n。然而，如果该方程不成立，(x,y)就是一个无效曲线点。相当多的密码算法要求用户提供一个曲线点，并默认该点是有效的且方程成立。在对其进行数学运算之前未能验证接收到的曲线点是否在曲线上，与违反密码学末日原则相差不远，并具有类似的后果。

在椭圆曲线方案中，秘密通常是一个常规数字（记住，找到n使得Q = n * P是困难问题）。当攻击者可以发送一个未验证的点，该点乘以n并查看结果时，他们可以利用缺乏验证来学习密钥。通常，攻击者可以选择属于与算法指定曲线不同的曲线上的点，该曲线上的点非常少。

例如，攻击者可能选择一个不在曲线上且y坐标为零的点。任何这样的点，当加到自身上时，必须等于无穷远点。我们知道这一点，因为我们通过将y坐标乘以负一来计算逆点，但零乘以负一还是零，因此任何y坐标为零的点都是其自身的逆点。因此，当我们将它加到自身上时，结果必须是无穷远点。

如果攻击者选择这样的点，那么通过查看秘密乘以该曲线上的某个点，他们可以学习秘密是偶数还是奇数！输入点是两个可能点之一。将其加到自身上将得到另一个点。因此，如果秘密是输入的点，则数字是奇数；否则，是偶数。我们可以提交类似的点，当乘以三时等于无穷远点以学习秘密模3，当乘以五时等于无穷远点以学习秘密模5，依此类推，直到我们可以使用中国剩余定理计算实际秘密。

这不是使用无效曲线点找出密钥的唯一方法，但可能是最容易理解的，并且已在现实生活中用于破解Oracle和Google的TLS库。

虽然最近对蓝牙的攻击不像上述示例那么简单，但概念上非常相似，并使用了相同的小子群限制技术来实现密钥泄露。

蓝牙攻击是如何工作的？

蓝牙协议使用椭圆曲线Diffie-Hellman来商定加密的共享密钥。正确使用Diffie-Hellman算法非常困难。细微的错误可能会危及整个系统的安全性。在这种情况下，协议确实需要曲线点验证，但仅针对x坐标。这是一个看起来足够无辜的错误，以至于十年未被注意到。它让聪明的攻击者可以破解整个系统。

椭圆曲线Diffie-Hellman是一个简单的算法。假设Alice和Bob想要商定某个秘密。双方都有一个秘密数字，并且有一个共同商定的椭圆曲线上的“基点”。

Alice将基点乘以她的秘密数字发送给Bob，Bob将基点乘以他的秘密数字发送给Alice。然后，Alice将Bob的消息乘以她的秘密数字，Bob将Alice的消息乘以他的秘密数字。如果我们称点为P，秘密为a和b，Alice发送给Bob P * a，Bob发送给Alice P * b。然后Alice计算(P * b) * a（共享秘密），Bob计算(P * a) * b（相同的数字）。

即使攻击者Chuck可以看到任一消息，他也不能推导出a或b，也不能组合P * a和P * b来得到秘密，因此他完全运气不好！然而，当Chuck可以修改消息而不仅仅是查看它们时，问题就出现了。由于y坐标无效，Chuck可以将其修改为始终为零。

记住，如果一个点的y坐标为零，如果您将其乘以一个随机数，它有50%的机会是无穷远点，50%的机会是原始点，没有机会是其他任何东西。

将这一切放在一起，如果Chuck将Alice和Bob发送给彼此的其中一个点(x, y)替换为(x, 0)，那么Alice或Bob将其乘以他们的密钥时，有50%的机会他们得到无穷远点，50%的机会他们得到(x, 0)。如果Chuck替换两个中间消息，有25%的机会Alice和Bob同意密钥是无穷远点，没有机会他们同意任何其他密钥。这意味着要么ECDH失败，Alice和Bob必须重试（给Chuck另一个机会），要么Chuck知道密钥并可以读取和插入消息。

如何避免这样的漏洞？

从所有这些中最重要的收获不是关于这个特定攻击的任何东西；而是整个这类攻击是完全可预防的。一些更具体的建议：

• Diffie-Hellman是一个异常危险的算法来实现。您几乎肯定不想首先使用它（参考Latacora的优秀密码学正确答案）。如果您发现有人使用它，您有很大机会找到漏洞。严肃地说，几乎没有人需要这个，而且正确实施极其困难。
• 对ECDH使用X25519，对ECDSA使用Ed25519。在这些曲线上，任何32字节字符串都是有效的曲线点；因此无效曲线点是不可能的。
• 如果您的输入可能无效并且您正在对其执行密码操作，请在执行任何其他操作之前进行验证。

我故意省略了自行验证点的说明，因为这对于博客文章的结论来说是一个过于微妙的话题。如果您对这类事情感兴趣，您可以参考这篇论文。如果您想练习利用这类漏洞（以及一些更酷的漏洞），您应该查看Cryptopals第8组。如果您已经以做这类事情为乐，请联系我们。我们很乐意与您合作。

如果您喜欢这篇文章，请分享： Twitter LinkedIn GitHub Mastodon Hacker News

页面内容
什么是椭圆曲线？
什么是无效曲线点攻击？
蓝牙攻击是如何工作的？
如何避免这样的漏洞？
近期帖子
使用Deptective调查您的依赖项
系好安全带，Buttercup，AIxCC的评分回合正在进行中！
使您的智能合约超越私钥风险成熟
Go解析器中意想不到的安全隐患
我们从审查Silence Laboratories的首批DKLs23库中学到了什么
© 2025 Trail of Bits。
使用Hugo和Mainroad主题生成。