📡 Signal｜Claude、NIST 楕円曲線の種は1997年の乱数と特定

Anthropic のフロンティア・レッドチームは10月16日、同社の AI Claude が、米国立標準技術研究所 (NIST) の楕円曲線 P-192、P-224、P-256、P-384、P-521 の「種」(シード) がどう作られたかを突き止めたと発表した。種は、何かの文をハッシュにかけた値ではなかった。C 言語の標準ライブラリにある乱数の関数 lrand48 を、Unix 時刻 (1970年からの経過秒数) で初期化して出した値だった。

Anthropic：Claude が NIST の ECDSA 曲線の種の出どころを特定 (10月16日／P-192〜P-521 の種は lrand48 を Unix 時刻で初期化した出力、P-256 は 1997-08-16 の 1,842 番目の候補、「暗号の破綻ではない」、懸賞金 3 万 6,864 ドルは ISRG へ寄付、再現コードを確認)anthropic.com

これらの曲線は2000年に NIST の電子署名の標準 FIPS 186-2 に入った。種は米国家安全保障局 (NSA) が説明なしに提供したもので、出どころが分からないことが、26 年にわたり「裏口が仕込まれているのでは」という疑念の根になってきた。Anthropic は今回の結果を「暗号の破綻でも、新たな攻撃でも、曲線の弱点でもない」と明記し、種が単純で再現できる手順から出たと分かったことで、裏口の可能性は「はるかに低くなった」と書いている。

P-256 の種は、1997年8月16日に回した乱数だった

発表によると、Claude は社内の研究用モデルで、30 分足らずのうちに 5 つの素体上の曲線の種の出どころを見つけた。

手がかりは、種を 4 バイトずつの数に区切ると、最上位のビットが 0 になっている数が多いことだった。偶然そうなる確率は約 5,810 分の 1 で、1990 年代の乱数の関数が出す値の特徴と一致する。Claude はそこから、出力の一部だけが見えている状態で内部の状態を逆算する格子簡約という手法 (LLL アルゴリズム) を使い、乱数の関数の初期値を割り出した。

種は、20 バイトずつ順に取り出した候補の 1 つだった。Anthropic が公開したコードによる、曲線ごとの実行時刻 (協定世界時) は次のとおり。

P-192: 1997年5月18日 14時45分34秒
P-521: 1997年8月8日 1時12分4秒
P-256: 1997年8月16日 1時52分34秒 (1,842 番目の候補)
P-384: 1997年8月30日 14時50分8秒
P-224: 1998年4月3日 12時52分7秒

2 進体の上の曲線では、時刻がそのままだと1984年2月になる。2 倍すると1998年4月17日になるため、Anthropic は、種を作ったプログラムが時計の値を半分にしていた可能性を挙げる。

まだ解けていない部分

発表は、分からないことも並べている。P-224、P-256、P-384、P-521 と、2 進体の曲線の基準点 (計算の出発点になる点) がどう選ばれたかは説明できていない。2 進体の曲線の 5 本目にあたる B-163 の種も復元できていない。P-256 の 876 番目の候補のように、条件を満たすのに選ばれなかった候補がある理由も不明だ。

一方で、P-192 と、別の米国の標準 ANSI X9.62 に入っている 5 本の曲線については、基準点の出どころも分かった。こちらは多倍長整数のライブラリ FreeLIP の乱数の関数から出ていた。

暗号技術者の Filippo Valsorda 氏が呼びかけた懸賞金 3 万 6,864 ドルは、Let's Encrypt を運営する非営利団体 ISRG に寄付される。種と一部の基準点を再現する Python のコードは、著作権を放棄する CC0 で公開された。

ビットコインの曲線は別の系統

ビットコインとイーサリアムの署名が使うのは、今回の対象の P-256 系ではなく、secp256k1 という別の曲線だ。業界団体 SECG の標準 SEC 2 で定められ、式の係数は a = 0、b = 7 という小さな値に決め打ちされている。種から係数を導く方式ではないため、今回のような「種の来歴」という問いがもともと立たない。Anthropic の発表も secp256k1 には触れていない。

P-256 は、Web の暗号通信 (TLS) やパスキーなどの認証で広く使われる曲線だ。今回の結果はその出どころへの疑いの大きな部分を解いたが、基準点の謎は残っている。

AI が暗号の来歴を監査する

LiveMakers は10月17日の Signal で、Claude が楕円曲線を破る量子回路のゲート数を大きく減らした研究を取り上げた。2 日続けて出た 2 つの発表は、向きが逆だ。量子回路の研究は、暗号を破るのに要る費用の見積もりを下げた。今回の研究は、暗号の標準に埋め込まれた説明のない数字を、30 分で来歴まで読み解いた。

標準化の文書には、根拠が書かれないまま残った定数が少なくない。人の専門家が何年もかけて解けなかった問いを、AI が短時間で検証できるなら、古い標準の来歴の監査に要る費用は大きく下がる。疑いを晴らす方向にも、新しい弱点を見つける方向にも、同じ道具が働く。

次に見るもの

まず見るのは、この数週間のうちに、公開されたコードで種を再現した第三者の追試の報告が出るかだ。そのうえで、NIST が楕円曲線の推奨文書 SP 800-186 の改訂の際に、種の来歴について注記を加えるかを確認する。残る B-163 の種と P-256 の基準点の謎を、誰が先に解くかも手がかりになる。

ことば

種 (シード) — 楕円曲線の係数を作る時の出発点になる数。種をハッシュ関数にかけて係数を決める方式では、種の出どころが説明できれば「作り手が都合のよい曲線を選んでいない」ことの裏付けになる。NIST の曲線は、その説明が 26 年間なかった。
lrand48 — C 言語の標準ライブラリにある疑似乱数の関数。初期値が同じなら同じ数列を出すため、初期値 (今回は Unix 時刻) が分かれば出力を再現できる。1990 年代の UNIX 系の環境で広く使われていた。
secp256k1 — ビットコインとイーサリアムの署名に使われる楕円曲線。SECG の標準 SEC 2 で定められ、係数は a = 0、b = 7。種から係数を作る方式ではない。

🔗 一次ソース