1. Claude reveals ECDSA curve origins (www.anthropic.com)
Claude 揭示 ECDSA 曲线种子起源
背景与长期的谜团
ECDSA(椭圆曲线数字签名算法)是目前应用最广泛的加密标准之一。在 NIST(美国国家标准与技术研究院)于 2000 年发布的 FIPS 186-2 标准中,为了定义椭圆曲线的系数 $b$,规定使用一个“种子”(seed)参数的哈希值。然而,这些种子是由 NSA(美国国家安全局)提供的,其来源和生成逻辑一直缺乏解释。由于缺乏透明度,密码学界长期以来一直担心这些种子可能包含蓄意的后门。
Claude 的发现
Anthropic 的研究人员利用内部研究模型 Claude 破解了这一长达 25 年的谜团。Claude 发现,NIST P-192、P-224、P-256、P-384 和 P-521 的种子并非复杂的哈希算法产物,而是使用了 20 世纪 90 年代 C 语言库中常见的 lrand48 伪随机数生成器(PRNG),并以 Unix 时间戳 作为初始种子(seed)生成的。
生成逻辑非常简单:通过 lrand48 生成随机数,每 20 个字节作为一个候选种子,直到找到符合要求的参数。
安全意义
这一发现并非加密算法的破绽或弱点。相反,它增强了人们对这些曲线安全性的信心。由于生成方式极其简单且透明(使用常见的 PRNG 和时钟),这大大降低了通过种子植入复杂、隐蔽后门的可能性。研究人员认为,这标志着多年来关于 NIST 曲线参数来源猜想的终结。
技术实现路径
Claude 通过以下技术手段完成了这一发现:
- 模式识别:Claude 猜测软件使用了 90 年代的旧版 PRNG。它编写扫描器检测种子数据,发现部分种子在高位比特(top bits)上呈现出全零的特征。这是
lrand48的典型特征,因为该生成器仅返回 48 位状态中的前 31 位。 - 状态恢复:针对截断的输出,Claude 利用 Lenstra–Lenstra–Lovász (LLL) 格基约减算法 解决了线性同余生成器的状态恢复问题,从而找回了完整的 48 位内部状态。
- 时间戳回溯:通过将生成器状态向前回溯,Claude 成功找到了对应的
srand48初始化值,这些值均对应于 1997 年至 1998 年间的 Unix 时间戳。
关于基点(Base Points)的研究
除了种子,每个曲线还包含一个基点 $G$。Claude 的调查结果如下:
- 已解释的部分:部分曲线(如 P-192 及 ANSI X9.62 的示例曲线)的基点可以追溯到 Arjen Lenstra 的 FreeLIP 或 Victor Shoup 的 NTL 库,通过特定的生成步骤得出。
- 未解的部分:P-224、P-256、P-384 和 P-521 的基点生成方式仍未被破解。此外,二进制种子 B-163 也依然是一个谜。
遗留问题
尽管核心种子问题已解决,但仍存在一些开放性问题:
- 候选者筛选:在生成过程中,程序跳过了一些同样符合条件的潜在候选种子(例如 P-256 跳过了第 876 个候选者),其筛选标准尚不明确。
- 潜在的筛选意图:虽然目前没有证据表明这是为了植入弱点,但无法完全排除通过搜索特定时间戳来寻找具有特定属性曲线的可能性。
其他信息
针对此次发现 NIST 曲线种子所设立的 36,864 美元奖金将捐赠给 Internet Security Research Group (ISRG)。