Technology

電子署名の標準楕円曲線5種、時刻から生成用データを再現

この記事のポイント

  1. 実現したこと

    NISTの標準楕円曲線5種について、生成用シードをUnixタイムスタンプから再現できるようになった。

  2. 実現の仕組み

    疑似乱数生成器lrand48の出力に残るビットの特徴を探し、LLL基底簡約で内部状態を復元した。

  3. 得られた結果

    Anthropicによると、NISTとANSI X9.62の計10種で、復元した状態から各シードの160ビットすべてが一致した。

  4. 従来との違い

    由来不明だったシードに、時刻で初期化した乱数生成器と候補の反復回数による具体的な再現手順が得られた。

明るい机上に、無数字の時計と空白の暦、5枚の楕円曲線図、色分けした乱数片、斜め格子から整った格子への変化、20個の色ブロックのシードが矢印で順につながる編集イラスト。
AI生成画像

電子署名に使う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の解読や新しい攻撃、曲線の弱点を見つけたものではなく、利用者が対応を変更する必要はないとしている。