電子署名に使うNISTの標準楕円曲線5種で、由来不明だった生成用シードを時刻から再現する方法が見つかった。Anthropicによると、内部研究用AIモデルClaudeが疑似乱数生成器の状態を復元し、標準値との一致を確かめた。
曲線を決めるシード自体の由来を探る
楕円曲線を使う電子署名方式ECDSAの標準では、公開されたシードという生成用データのハッシュ値を、曲線の係数bの決定に使う。シードから係数を求める関係は示されていたが、シード自体をどう作ったかは説明されていなかった。
Anthropicによると、内部研究用AIモデルClaudeは、P-192、P-224、P-256、P-384、P-521のシードを再現する方法を見つけた。これらの値は、Unixタイムスタンプで初期化したCライブラリーの疑似乱数生成器lrand48の出力に一致した。
最上位ビットの偏りから乱数生成器を絞る
Claudeは、公開シードの中に疑似乱数生成器の連続出力が残っているかを調べた。シードを1ビットずつずらして検査する走査処理を作り、生成器と出力の切り出し方を組み合わせた34通りを試した。
手掛かりになったのは、4件のシードを32ビット語に区切ると、各語の最上位ビットがすべて0になる特徴だった。lrand48は48ビットの内部状態のうち上位31ビットを返すため、この偏りが生成器の特定につながった。
切り出された出力から内部状態を復元する
素体上の曲線のシードでは、lrand48の出力のさらに一部だけが使われていた。Claudeは、出力の切り出し位置を変えながら、格子の基底を簡約するLLL基底簡約アルゴリズムを適用し、見えていない部分を含む内部状態を復元した。
Anthropicによると、NISTの5種とANSI X9.62の5種は、いずれもlrand48の出力を23ビット右シフトする取り出し方に一致した。復元した各48ビット状態からは、対応するシードの160ビットすべてを再生成できた。
初期化時刻と候補番号で標準値に到達
Claudeは、復元した内部状態を逆向きにたどり、初期化関数srand48が作る形式まで戻した。10種の素体上の曲線で得られた初期化値は、いずれも1997年5月から1998年4月までの日付を表すUnixタイムスタンプになった。
再現手順では、その時刻で生成器を初期化し、20バイトずつ候補シードを作る。P-256では、1,842番目の候補が標準シードと一致した。
Anthropicは、この一致を標準曲線の生成過程を説明する成果と位置付けている。ECDSAの解読や新しい攻撃、曲線の弱点を見つけたものではなく、利用者が対応を変更する必要はないとしている。