BlackHalo logo
Published on

Claude破解ECDSA曲线种子起源之谜

Authors
  • Name
    ahlCVA
    anthropic.com
ECDSA椭圆曲线密码学示意图
头图来源: 来源页面

背景:ECDSA曲线的种子谜团

ECDSA(椭圆曲线数字签名算法)是最广泛使用的椭圆曲线密码学标准。它于2000年被NIST采纳为FIPS 186-2数字签名标准的一部分,其中列出了一组不同大小和安全级别的标准椭圆曲线。对于素域和二元域曲线,规范发布了一个“种子”参数,其哈希值用于定义曲线的系数b。这些种子的来源一直是一个长期悬而未决的问题,因为它们是由NSA提供,没有任何解释或理由。

例如,NIST P-256曲线的种子是:SEED = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90,没有任何关于它来自何处的信息。密码学家Neal Koblitz和Alfred Menezes曾撰写了一篇名为“A Riddle Wrapped in an Enigma”的优秀总结,讨论了种子值的历史和争议。这一谜团引发了业余爱好者对种子起源的调查,并设立了寻找种子的赏金。

最著名的说法是,长期供职于NSA的Jerry Solinas使用一个幽默的密码短语的哈希值生成了种子:“我相信有一个计数器,而不是多次哈希,但我不知道细节。消息大致是‘给Bob和Jerry加薪’或‘Bob和Jerry统治’之类的。实际上是Bob Reiter编写了代码,他也不记得细节了。我们也无法找到那么久以前的档案。如果它们存在,无疑就在某个硬盘上,旁边放着约柜。”Solinas于2023年去世,其他当时的同事也没有回应,使得这些种子最初如何派生的问题仍然悬而未决。

Claude发现种子

一些Anthropic员工曾根据关于种子是幽默短语哈希值的线索尝试寻找种子,但都没有成功。事实证明这个线索是错误的。

2026年10月,一位好奇的Anthropic员工向内部研究模型提问,希望它能在不给出线索的情况下找出这些种子是如何生成的。在不到半小时的时间里,Claude发现了NIST P-192、P-224、P-256、P-384和P-521种子的起源。它们根本不是任何哈希算法的结果,而是C库的lrand48随机数生成器的输出,该生成器以Unix时间戳作为种子!

使用的算法是从由Unix时间戳(t)初始化的随机数生成器(RNG)中采样字节,进行一定次数的迭代(n)。每次迭代抽取20字节作为候选种子。因此,前20字节是候选1,接下来的20字节是候选2,依此类推。例如,P-256需要1842次迭代才能输出标准化的种子。

发现的意义

这并不是密码学上的突破、新的攻击或ECDSA曲线的弱点。事实上,这让我们更加确信曲线的选择没有后门或故意弱点。多年来,人们一直对NIST曲线参数的起源持怀疑态度。它们被提交给NIST时没有提及如何选择,让人们猜测它们是否可能被设计成带有故意的后门。这些发现使得这种可能性大大降低。

种子是以一种非常简单的方式生成的:一个基于时钟初始化的常见伪随机数生成器,任何人都可以重现。这为颠覆留下了更少的空间,我们可以确信参数是安全的。

发现过程

虽然基于谣言对短语的搜索一无所获,但Claude尝试了不同的角度:预测生成曲线的软件可能的工作方式。Claude猜测软件使用了1990年代C库附带的伪随机数生成器(PRNG)。这些旧PRNG很弱,其输出可以被识别出来。识别出输出将揭示使用了哪种PRNG,并可能恢复其初始化状态。

Claude编写了一个扫描器,沿着每个已发布的种子一次滑动一位,并测试相邻块是否是1990年代生成器的连续输出。扫描覆盖了34种生成器和输出切片的组合。此时,Claude注意到某些种子高位中的模式:它们全是零。如果写为五个32位字,十个种子中有四个的所有20个字的高位都是0。这种情况随机发生的概率是1/5810。这是线性同余生成器lrand48的特征,它只返回48位状态的高31位。一旦知道要寻找什么,这个模式用肉眼就能看出来。

为了恢复状态,Claude取第一个字,尝试所有2¹⁷个隐藏的17位值,并检查接下来的四个字是否匹配。这对于所有四个讨论中的种子都有效。素域曲线的种子来自同一个lrand48生成器,但保留了每个输出的更少位。Claude必须从这些位中恢复PRNG的内部状态。事实证明,恢复截断的线性同余生成器状态是一个教科书式的格问题,可以用Lenstra–Lenstra–Lovász(LLL)算法解决。

Claude不知道种子可能显示状态的哪些位,因此它在每个窗口上运行求解器。五个NIST素域曲线种子加上来自ANSI X9.62标准的另外五个种子都具有相同的模式:lrand48() >> 23。每个恢复出的48位状态都能重新生成其种子全部的160位,这绝非偶然。

这个线性同余生成器向前和向后运行一样容易,因此对于每个种子,Claude将状态向后步进,直到它达到由srand48初始化时的形式,低16位等于0x330E。这种形式的内部PRNG状态每65536步出现一次,因此仅此一点并不能作为证据。然而,对于十个素域曲线种子,每次srand48初始化都是一个Unix时间戳,对应1997年5月至1998年4月之间的日期。四个二元域曲线的初始化读数为1984年2月。将时间戳加倍后,它们对应1998年4月17日,即P-224运行两周后。因此,程序可能将时钟减半。

Claude还发现了一些基点

每个曲线还带有一个基点G,这是每个ECDSA公钥倍乘的固定点。上面找到的种子并不决定这个G,因此另一个问题出现了:这些基点是生成的呢?在检查种子的同时,Claude还发现了一些基点的来源。1997年5月生成的六个曲线(P-192和五个ANSI X9.62示例曲线prime192v2、prime192v3和prime239v1至v3)的基点来自Arjen Lenstra的长整数算术包FreeLIP中的随机数生成器。早期版本的Victor Shoup的NTL库也附带了相同的代码。

方法很简单:用一个小整数初始化生成器。丢弃七个输出。从26位输出中生成候选x坐标,模p降阶。重复步骤3直到x在曲线上。Claude发现生成器种子是:P-192为20000,prime239v1至v3分别为20420、20507和20509,prime192v2和v3分别为20512和20517。据我们所知,此前没有NIST基点被解释过。P-224、P-256、P-384和P-521的基点不符合这个公式;我们无法解释它们是如何选择的。

未解问题

并非每个20字节的候选种子都能生成可行的曲线,而且我们观察到一些可能可行的曲线被跳过了。例如,P-256的已发布种子是候选序号1842,但同一次运行中的候选876也给出了一个具有正确大小且参数选择与已发布曲线相同的素数阶曲线。P-224的运行跳过了三个这样的曲线,ANSI X9.62示例曲线背后的两次运行跳过了另外七个(见图)。我们不知道使用了什么标准,或者这是否是一个无意的产物。因为跳过的候选数量很小,我们认为选择弱化曲线的说法不成立。那将意味着弱化曲线很常见且易于找到。

从原则上讲,仍然可能通过搜索随机数生成器的时间戳来选择这些曲线以具有特定属性。然而,只有当你打算公开时间戳作为种子无辜生成的证据时,你才需要这样做。数字中没有显示有多少次运行。还有一个种子我们无法恢复。第五个二元种子B-163不符合Claude尝试的任何方法,仍然无法解释。最后,我们不知道P-224、P-256、P-384和P-521的基点是生成生成的。NIST二元曲线也是如此。

赏金

发现种子的36864美元赏金将捐赠给互联网安全研究组织(ISRG)。

人员

这项工作由Anthropic的John Wood、Henry de Valence、Ava Howell、Zack Voase、Lucy Sweet、Amir Omidi、Paul Crowley、Iain McGinniss、Nicholas Carlini和Steve Weis进行。我们衷心感谢已故的Jerry Solinas,他以幽默的态度面对被称为“邪恶的网络迷因”和“NSA妖怪中的Yo La Tengo”。还要感谢Filippo Valsorda组织了NIST椭圆曲线种子赏金。

重现代码

Anthropic在文章中提供了Python代码,使用lrand48算法和Unix时间戳即可重现所有种子。

原标题:Claude reveals ECDSA curve origins。 HN 原始发布时间:2026年10月17日星期六。当前记录为 1024 分、374 条评论。

阅读原文 · 查看 HN 讨论