瞻博网络双EC事件的教训（2018）

斯蒂芬·Checkoway，雅各布·马西米维奇，克里斯蒂娜·加曼，约书亚·弗里德，莎南·科尼，马修·格林，纳迪亚·亨宁格，拉尔夫·菲利普·温曼，埃里克·雷斯科拉，ACM霍夫·沙汉姆通讯社，2018年11月，第一卷61 No. 11，第148-155页10.1145 / 3266291注释2015年12月，Juniper Networks宣布了多个安全漏洞，这些漏洞来自ScreenOS（其NetScreen虚拟专用网络（VPN）路由器的操作系统）中未经授权的代码。这些漏洞中最复杂的是被动VPN解密功能，可通过更改双椭圆曲线（EC）伪随机数生成器使用的参数之一来启用。

在本文中，我们描述了针对此事件进行的ScreenOS随机性和VPN密钥建立协议子系统的完全独立分析的结果。虽然已知Dual EC对可以选择椭圆曲线参数的攻击者是不安全的，但Juniper在2013年声称ScreenOS包含了针对此类攻击的对策。我们发现，与瞻博网络的公开声明相反，自2008年以来，ScreenOS VPN的实施一直容易受到攻击者的被动利用，攻击者选择了双EC曲线点。此漏洞的出现是由于瞻博网络对策中的缺陷以及一系列的变化所致。在2008年发布的单个版本中同时引入了Dual EC和Dual EC。通过修改固件以安装我们自己的参数，我们在真实的NetScreen设备上演示了该漏洞，并且表明可以隔离被动地解密单个VPN会话而无需观察任何其他网络流量。该事件是一个重要的例子，说明了如何在实践中失败随机数生成，工程设计和验证的准则。此外，它对设计一种安全的“例外访问”或“密钥托管”方案的可行性提出了进一步的怀疑，这种方案是美国和其他地方的执法机构考虑的。

Juniper在2015年12月宣布，“内部代码审查”显示“ ScreenOS中存在未经授权的代码，可能使知识渊博的攻击者解密VPN连接”。对此，瞻博网络发布了修补版本的ScreenOS，该操作系统为受影响的NetScreen设备提供了动力，但拒绝透露有关入侵和漏洞的任何进一步信息。

在瞻博网络的咨询之后，包括我们团队在内的全球安全研究人员立即开始检查ScreenOS固件，以发现瞻博网络已修补的漏洞。他们发现，使ScreenOS加密易碎的更改只不过替换了Juniper伪随机数生成器中的一些嵌入式常量。导致攻击者能够解密连接的原因是Juniper的设计决策，即使用NSA设计的Dual EC伪随机数生成器（PRNG）。 4，4，12对偶EC的问题在于，攻击者知道输入参数（Q）之一相对于生成器点的离散对数，并且能够从PRNG观察少量连续字节，然后计算发电机的内部状态，从而预测所有未来的输出。因此，至关重要的是，Q的离散对数保持未知。 ScreenOS代码的更改将Juniper选择的Q替换为攻击者选择的Q。

从一个角度来看，瞻博网络事件只是一个特别复杂的软件漏洞，就其自身而言，这很有趣。但是，更重要的是，它阐明了“例外访问”技术这一有争议的主题，该技术将使执法人员能够访问加密数据的明文。任何特殊访问系统的关键组成部分都限制了对授权人员的访问，最常用的方法是在执法人员已知的一个或多个密钥下加密目标密钥材料，然后将其严格控制。在ScreenOS中使用Dual EC可以创建实际上是一个例外的访问系统，其中Q作为公共密钥，而Q的离散日志作为私有解密密钥。从历史上看，对特殊访问系统的分析一直集中在控制解密密钥的难度上。在ScreenOS的特定情况下，我们不知道是否有人可以访问相应的密钥，但瞻博网络事件清楚地说明了另一种风险：攻击者修改了系统的特殊访问功能，以用以下方式替换授权的公钥：她的控制权，从而将旨在供执法人员使用的特殊访问系统转变为对攻击者有效的系统。

在本文中，我们试图讲述该事件的故事，通过对数十年前将近十年的ScreenOS固件版本进行取证反向工程以及在NetScreen硬件上进行的实验验证，将其拼凑在一起。我们首先提供有关Dual EC本身的背景知识，然后研究它在ScreenOS中的使用方式以及导致严重漏洞的原因，然后研究事件本身的历史，最后考虑我们可以从中学到什么教训故事。

密码系统通常包括确定性PRNG，这些PRNG将少量秘密内部状态扩展为旨在与真正随机性无法区分的值流。能够预测PRNG输出的攻击者通常能够破坏依赖于它的任何协议实现，例如，通过能够预测加密密钥（应保持秘密）或随机数（通常应保持不可预测）。

Dual EC是由美国国家标准技术研究院（NIST）标准化的加密PRNG，其基于椭圆曲线上的运算。 Dual EC具有三个公共参数：椭圆曲线和曲线上的两个点，称为P和Q。ScreenOS使用椭圆曲线P-256并将P设置为NIST特别出版物800-90中指定的P-256的标准生成器。 4该标准还指定了要使用的Q，但是ScreenOS使用Juniper自己的椭圆曲线点Q代替。定义P-256的有限域大约有2 256个元素。 P-256上的点由满足椭圆曲线方程的256位数字对（x，y）组成。 Dual EC的内部状态是单个256位数字s。

令x（·）为返回椭圆曲线点的x坐标的函数； ||串联lsb n（·）是按大端顺序返回其输入的最低有效n个字节的函数；而msb n（·）是返回最高有效n字节的函数。从初始状态S 0开始，对Dual EC实现的一次调用将生成32个伪随机字节输出和一个新状态S 2，如下所示：

2007年，Shumow和Ferguson证明了16，双EC受到了一个对手的状态重建攻击，该对手知道值d使得P = dQ并可以观察到单个输出值。关键的见解是将点s 1 Q与d相乘得到内部状态x（d·s 1 Q）= x（s 1 P）= s2。尽管s 1 Q本身未知，但32B的30B它的x坐标（即r 1）构成输出的前30B，攻击者可以猜测剩余的字节；椭圆曲线点的x坐标确定其y坐标直到符号。

假设攻击者知道Q的离散对数，那么主要的困难就是恢复完整的输出值。仅知道部分价值的攻击者必须详尽搜索其余部分。随着r 1的字节越少，候选者的数量呈指数增长，并且恢复少于26B难以解决。在ScreenOS中，总是使用Dual EC一次生成32B的输出，因此攻击很简单。当在Juniper的实现中有r 1的30B可用时，攻击者必须考虑2 16个候选点。从攻击者的角度来看，这是最佳情况。

重要的是，就众所周知而言，Dual EC对知道P和Q但不知道d的攻击者是安全的，因为恢复d将需要计算离散对数的能力，这通常会破坏椭圆曲线密码学。

清单1显示了在ScreenOS 6.2.0r1版中实现PRNG的函数的反编译源代码； 6.2和6.3系列的其他版本中具有相同的功能。它由两个PRNG组成，即Dual EC和ANS X9.31（附录A.2.4；参考文献2）。

请注意，二进制文件中不存在诸如函数名和变量名之类的标识符。我们根据对每个符号的表观功能的分析来分配这些名称。同样，编译/反编译过程不会保留特定的控制流构造。例如，第21行的for循环实际上可能是while循环或Juniper源代码中的某些其他构造。但是，反编译的确保留了原始代码的功能。为了清楚起见，我们省略了确保X9.31生成器未生成重复输出的联邦信息处理标准（FIPS）检查。

浅读prng_generate（）函数表明Dual EC仅用于生成X9.31 PRNG的密钥，并且X9.31的输出返回到调用方（在输出全局缓冲区中）。第2节中描述的Dual EC漏洞需要原始Dual EC输出，因此无法应用。的确，Juniper 8在2013年的知识库文章中对此进行了准确说明。 （我们将在第6节中进一步讨论该知识库文章。）

在此阅读中，偶尔会调用prng_reseed（）函数来重新设定X9.31 PRNG状态。此函数调用Dual EC生成器，将其输出定向到32B缓冲区输出。从此缓冲区，它为X9.31生成器提取种子和密码密钥。使用X9.31作为种子时，prng_generate（）函数一次将X9.31输出的8B（第23行）转换为输出，直到生成32B的输出为止（行2126）。每次调用x9_31_generate_block都会更新种子缓冲区中的X9.31种子状态。

首先，也是最重要的一点，索引（在第21行的prng_generate（）中调用X9.31 PRNG的循环的控制变量）是全局变量。如果调用prng_reseed（）函数，则将其设置为32，结果是，每当重新播种PRNG时，循环开始时索引就已经大于31，因此不会执行对X9.31 PRNG的调用。一种

其次，在默认配置中，one_stage_rng（）始终返回false，因此始终调用prng_reseed（）。那么，在默认配置中，永远不会调用X9.31循环。 （有一个未公开的ScreenOS命令，设置了密钥one-stage-rng，该命令使one_stage_rng（）始终返回true；运行此命令会引发另一个PRNG漏洞，将在本文的完整版本中进行讨论。5）

第三，prng_reseed（）碰巧将输出全局缓冲区用作双EC输出的暂存区，然后才将输出的一部分复制到其他保存X9.31种子和密钥的全局缓冲区。这是prng_generate（）函数应该用X9.31输出填充的全局缓冲区，但是失败。当呼叫者在输出中寻找PRNG输出时，他们发现原始的Dual EC输出为32B。

为了进行比较，清单2显示了在瞻博网络进行改造之前，ScreenOS 6.1中PRNG函数的反编译源代码。在ScreenOS 6.1中，循环计数器的索引是局部变量而不是全局变量。 X9.31 PRNG每10,000个调用从系统熵中重新填充，而不是从每个调用中从Dual EC重新填充。 PRNG输出放置在调用者提供的缓冲区中，而不是全局变量中。

此外，ScreenOS 6.1 PRNG子系统一次产生20B，而不是ScreenOS 6.2和6.3中的32B。我们将在下一部分中讨论这种差异的重要性。

ScreenOS实施Internet协议安全性（IPsec）VPN协议。要选择保护VPN会话的密钥，客户端和ScreenOS设备将执行Internet密钥交换（IKE）7、11握手。

在添加了Dual EC（第2节）并修改了PRNG子系统以公开原始Dual EC输出（第3节）的ScreenOS 6.2版本中，Juniper对IKE实施进行了一系列更改，从而使知道攻击者的攻击者成为可能。双EC密钥d，用于解密VPN连接。在这些部分的其余部分中，我们将对IKE的相关功能进行简要说明，然后说明这些更改的影响。

IKE及其后继IKEv2是基于Diffie-Hellman的传统握手协议，其中两个终结点（称为发起者和响应者）建立了一个安全关联（SA），该安全关联由参数和一组用于加密流量的密钥组成。 IKE有点不同寻常，包括两个阶段：

阶段1建立了一个“ IKE SA”，该SA与端点关联，但与非IKE网络流量的任何特定类别无关。在此阶段，双方交换Diffie-Hellman（DH）份额和随机数，它们被合并以形成派生密钥。可以通过各种方式对端点进行身份验证，包括签名密钥和静态配置的共享机密。

第2阶段建立保护非IKE流量（通常为IPsec）的SA。此阶段的IKE消息受到在第一阶段建立的密钥的保护。此阶段可能涉及DH交换，但也可能仅包括随机数的交换，在这种情况下，子SA密钥是从第一阶段中建立的共享机密中得出的。

IKEv2将这些阶段分别称为“初始交换”和“ CREATE_CHILD_SA”。为简单起见，在本文的其余部分中，我们将使用IKEv1阶段1 /阶段2术语。

以ScreenOS为响应者的IKE攻击将按以下步骤进行：（1）在第一阶段使用响应者随机数，计算Dual EC状态； （2）预测响应者的DH私钥，并使用它来计算IKE SA的DH共享秘密，该IKE SA用于生成第一组密钥； （3）使用这些流量密钥解密第二阶段流量，以恢复发起者和响应者的现时和公钥； （4）通过运行双EC转发（最佳情况）或使用新的响应者随机数重复双EC攻击，来恢复响应者的私钥； （5）使用响应者的私钥和发起者的公钥来计算第二阶段SA的共享密钥，从而计算出业务密钥； （6）使用流量密钥解密VPN流量。

但是，尽管从原理上讲这很简单，但是存在许多实际的复杂性和潜在的实现决策，这可能使这种攻击更容易或更困难（甚至不切实际），如下所述。

为了使Dual EC状态重构成为可能，攻击者需要的不仅仅是看到原始的Dual EC输出。她需要至少一个椭圆曲线点的x坐标的26B才能恢复Dual EC状态；较少的字节将不足（第2节）。

幸运的是，如第二部分所述，ScreenOS的Dual EC实现返回的32B的前30B属于单个点的x坐标。幸运的是，对于攻击者，ScreenOS的PRNG子系统在调用时也返回32B，如第3节所述，它们是Dual EC调用返回的32B。最后，ScreenOS发出的IKE随机数为32B长，是由单个PRNG调用产生的。总结一下：在ScreenOS 6.2和6.3中，IKE随机数始终由一个点的X坐标的30B和下一点的X坐标的2B组成，这是Shumow-Ferguson重建的最佳情况。

在这一点上值得扩展。 IKE标准允许在8到256B之间的任何随机数长度（第5节；参考文献7）。 Adrian等人在互联网上对IKE响应者进行了扫描。 3发现多数使用20B随机数。对于长度超过20B的随机数，我们尚无任何加密优势。 ScreenOS 6.1发送了20B随机数，并且正如我们在第3节中所述，它的PRNG子系统每次调用生成20B。在ScreenOS 6.2中，瞻博网络引入了Dual EC，重新编写了PRNG子系统以一次生成32B，并修改了IKE子系统以发送32B随机数。

知道了Juniper点Q的d并观察到ScreenOS设备生成的IKE随机数的攻击者可以在生成随机数时重新计算设备的Dual EC状态。她可以向前滚动该状态以预测后续的PRNG输出，尽管不能回滚以恢复较早的输出。 ScreenOS使用其PRNG生成IKE Diffie-Hellman份额，因此攻击者将能够预测她所看到的随机数后生成的DH私钥，并计算使用这些IKE握手建立的VPN连接的会话密钥。

当攻击者的网络分路器靠近ScreenOS设备并且可以观察到许多IKE握手时，这种情况显然适用。但是，如果攻击者的网络分流器更接近VPN客户端，该怎么办？她可能只观察到一个VPN连接。如果在DH共享之后生成了连接的临时数，则攻击者将无法恢复该会话的密钥。

粗略地阅读ScreenOS IKE代码似乎可以排除单连接攻击：包含DH份额的KE有效载荷确实在包含随机数的Nr载荷之前进行了编码。

但是，对于攻击者而言，ScreenOS方便地包含了一个预生成功能，该功能可以维护可用于新IKE连接中的现时和DH密钥池，从而减少了握手延迟。池化机制非常复杂，似乎旨在确保始终有足够的密钥可用，同时避免在设备上花费过多的运行时间。

为每个受支持的有限域DH组（MODP 768，MODP 1024，MODP 1536和MODP 2048）以及（在版本6.3中）为每个受支持的椭圆曲线组维护独立的先进先出（FIFO）队列。 ECP 256和ECP 384）。这些队列的大小取决于已为任何给定组启用的VPN配置的数量。例如，如果为组启用了单个配置，则该组的队列大小为2。现时队列的大小设置为所有DH队列的总大小的两倍。启动时，系统将所有队列填满。每秒运行一次的后台任务会将一个条目添加到未满的队列中。如果在相应的队列为空时需要随机数或DH份额，则动态生成新值。

队列按优先级顺序填充。至关重要的是，nonce队列被分配了最高优先级。随后是按加密强度降序排列的组（ECP 384降至MODP 768）。这意味着在许多（但不是全部）情况下，IKE握手的现时早于该握手的DH份额就从Dual EC输出流中提取出来，从而使单连接攻击变得可行。

图1显示了生成值的（某种程度上是理想的）序列，其中的数字表示在IKE阶段1交换之前和之后生成队列条目的顺序。图1a显示了启动后的情况：前四个值用于填充随机数队列，后两个值用于生成DH份额。因此，当交换发生时，它将值1用于随机数，将值5用于密钥，从而使攻击者可以从值1导出Dual EC状态，然后向前进行计算以找到DH份额。在阶段1交换后（消耗DH份额）

......