Claude、25年来謎だったECDSA暗号曲線のシード値の起源を解明

概要

詳細

発見の経緯

ECDSAの標準曲線(P-192、P-224、P-256、P-384、P-521)の係数は、1997年当時にNSAのジェリー・ソリナス氏がANSI X9.62委員会に提供したシード値から導かれています。ソリナス氏は「ユーモラスな合言葉をハッシュ化したもの」と説明していたとされますが、実際にその合言葉を特定する試みはいずれも失敗していました。ソリナス氏は2023年に亡くなっており、本人からの追加説明は得られなくなっていました。

Claudeが使った手法

研究チームによると、Claudeはまず、1990年代のCライブラリに搭載されていた弱い疑似乱数生成器が使われたという仮説を立てました。その上で、シード値をビット単位でずらしながら、既知の乱数生成器34種の出力パターンと一致するかを検証するスキャナーを作成。一部のシード値で上位ビットが特徴的なパターンを示していることに気づき、Cライブラリの関数「lrand48」の出力と一致すると特定しました。

残っていた隠れたビットは総当たりで探索し、素数体曲線についてはビットの欠落分を格子基底簡約(LLL)という数学的手法で補って内部状態を復元しました。最終的に、乱数生成器を初期化した関数「srand48」に渡されたタイムスタンプを逆算し、素数体曲線は1997年5月から1998年4月ごろ、二値体曲線は1998年4月17日ごろに生成されたとみられることが分かりました。

分かったことと、まだ分からないこと

今回の解析で、シード値がハッシュ関数の出力ではなく、単純な乱数生成器とタイムスタンプから作られていたことが判明しました。Anthropicは、この生成方法が単純で誰でも再現できる点から、「曲線が意図的な弱点なしに選ばれたという見方を強めるもの」としています。

一方で、P-224・P-256・P-384・P-521などの曲線で使われる「基点」の生成方法は、依然として説明がついていません。また、複数の候補が条件を満たしていたにもかかわらず、なぜ特定の値が採用されたのかという選定基準も不明なままです。二値体曲線のシード値の一つ(B-163)についても、今回試した方法では解析できなかったといいます。Anthropicは、今回の発見が暗号の解読や新たな攻撃につながるものではなく、利用者が対応すべきことは何もないとしています。

賞金の寄付

今回の解明は、暗号研究者フィリッポ・バルソルダ氏が設けた「NIST Elliptic Curves Seeds Bounty」の対象でした。研究チームが獲得した賞金36,864ドルは、無料のSSL/TLS証明書を発行する非営利団体Internet Security Research Group(ISRG)に寄付されています。解析に使ったコードは、パブリックドメイン相当のライセンス(CC0 1.0)で公開されました。