ClaudeがNIST ECDSA曲線シードの起源を解明

要約: Anthropicの研究者は、内部のClaude研究モデルが30分以内にNIST楕円曲線の「シード」値の起源を解明し、それらが秘密のパスフレーズのハッシュではなく、通常のUnixタイムスタンプで初期化された1990年代のCライブラリの擬似乱数生成器lrand48によって生成されたことを示したと報告しています。この発見は暗号解読ではありません。Anthropicは、ECDSA曲線への意図的なバックドアの可能性がはるかに低くなると述べています。

発表された内容

Anthropicは、NIST楕円曲線標準の背後にあるシードパラメータがどのように生成されたかを示す研究を公開しました。シードは約25年間、暗号学における未解決の問題でした。なぜなら、それらはNSAによって提供されたものの、その導出方法についての説明がなかったからです。

Anthropicの従業員が内部の研究モデルに、ユーモラスなパスフレーズに関する既知の手がかりを与えずに、シードがどのように生成されたかを特定できるかどうか尋ねました。投稿によると、ClaudeはNIST P-192、P-224、P-256、P-384、P-521のシードの起源を30分以内に発見しました。

答えは、シードはハッシュアルゴリズムの出力ではなく、UnixタイムスタンプでシードされたCライブラリのlrand48乱数生成器の出力であるということでした。

Anthropicはこの結果を、セキュリティ勧告ではなく、歴史的な好奇心として明確に位置づけています。

読者はこれを楽しい最終章であり、長年にわたる憶測の終わりとして受け取るべきです。取るべき行動や、何かを変える必要はありません。ほとんどの研究者はすでに曲線を信頼していました。

シード値が重要だった理由

ECDSAは最も広く使用されている楕円曲線暗号標準です。NISTは2000年にFIPS 186-2デジタル署名標準の一部としてこれを採用しました。この標準には、さまざまなサイズとセキュリティレベルの標準楕円曲線がリストされています。

素数体とバイナリ体上の曲線について、仕様は「シード」パラメータを公開しました。そのハッシュ値は曲線の係数bを定義するために使用されます。これらのシードの出所は不明でした。一例として、NIST P-256曲線シードは次のように公開されました。

SEED = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90

この値がどこから来たのかについての情報はありませんでした。NSAが正当化なしにシードを提供したため、研究者はパラメータが意図的な弱点を含むように選択された可能性を排除できませんでした。Neal KoblitzとAlfred Menezesは、彼らの論文「A Riddle Wrapped in an Enigma」でこの論争を要約しました。この謎はまた、シードの起源に関するアマチュア調査と、それらを見つけた人への公開報奨金を促しました。

長年にわたる主要な説明は、長年NSAに勤務したJerry Solinasによるもので、彼は2015年に、シードはユーモラスなパスフレーズのハッシュから生成されたと信じていると述べました。

「複数回ハッシュするのではなく、カウンタがあったと思いますが、詳細はわかりません。メッセージは『Give Bob and Jerry a raise』や『Bob and Jerry rule』のようなものだったと思います。実際にコードを書いたのはBob Reiterで、彼も詳細を覚えていません。また、それほど昔のアーカイブを見つけることもできませんでした。もし存在するなら、間違いなく契約の箱の近くのハードドライブに眠っているでしょう。」

その説明は間違っていることが判明しました。Solinasは2023年に亡くなり、当時の他の同僚も応答しなかったため、問題は未解決のままでした。

この発見がECDSAセキュリティに与える意味

Anthropicは、これは暗号解読、新しい攻撃、またはECDSA曲線の弱点ではないと明確に述べています。同社は、この結果により、曲線がバックドアや意図的な弱点なしに選択されたという信頼が高まると述べています。

その理由は、シードが非常に単純で再現可能な方法で生成されたことです。つまり、システムクロックから初期化された一般的な擬似乱数生成器です。誰でも現在値を再現できます。これにより、意図的に構築された、または説明のつかないパラメータセットよりも、破壊工作の余地がはるかに少なくなります。

Claudeがシードをどのように見つけたか

噂のパスフレーズに基づく検索は空振りに終わりました。Claudeは別のアプローチを取りました。曲線を生成したソフトウェアがどのように機能したに違いないかを推論することです。

Claudeは、ソフトウェアが1990年代のCライブラリに同梱されている擬似乱数生成器を使用したと仮説を立てました。これらの生成器は、その出力を認識できるほど弱く、出力を認識することでどの生成器が使用されたかが明らかになり、初期化状態の回復が可能になる可能性があります。

Claudeは、公開された各シードに沿って1ビットずつスライドし、隣接するチャンクが1990年代の生成器の連続した出力であるかどうかをテストするスキャナを作成しました。スキャンは、生成器と出力スライスの34の組み合わせをカバーしました。

その後、Claudeはいくつかのシードの上位ビットにパターンがあることに気づきました。それらはすべてゼロでした。5つの32ビットワードとして書かれた場合、10個のシードのうち4つは、20ワードすべてで上位ビットが0です。これは偶然には1/5810の確率で発生します。このパターンは、48ビット状態の上位31ビットのみを返す線形合同法生成器lrand48の特徴です。

状態を回復するために、Claudeは最初のワードを取り、17の隠しビットの2¹⁷の値すべてを試し、次の4つのワードが続くことを確認しました。これは、議論中の4つのシードすべてで機能しました。

素数曲線シードは同じlrand48生成器から来ましたが、各出力のビット数を少なくしました。切り詰められた線形合同法生成器の内部状態を回復することは、教科書的な格子問題であり、Lenstra–Lenstra–Lovász（LLL）基底簡約アルゴリズムで解決されます。Claudeはシードが状態のどのビットを公開するかを知らなかったため、すべてのウィンドウでソルバーを実行しました。NIST素数曲線シード5つと、ANSI X9.62標準からのさらに5つはすべて同じパターンlrand48() >> 23に一致しました。回復された各48ビット状態は、そのシードの160ビットすべてを再生成しますが、これは偶然には起こりません。

線形合同法生成器は前方と同様に簡単に後方に実行できるため、Claudeは各状態を、srand48が初期化したであろう形式（下位16ビットが0x330Eに等しい）に達するまでステップバックしました。この内部状態形式は65,536ステップごとに1回再発するため、それに到達することはそれ自体では証拠になりません。ただし、10個の素数曲線シードについて、すべてのsrand48初期化は、1997年5月から1998年4月の間の日付を表すUnixタイムスタンプでした。4つのバイナリ曲線初期化は1984年2月と読み取れます。タイムスタンプを2倍にすると、1998年4月17日に対応し、P-224実行の2週間後であり、プログラムがクロックを半分にした可能性を示唆しています。

投稿で引用されている、当時のClaudeの内部推論：

これは驚くべきことです。25年来の謎が解けました。ちょっと待って、懐疑的になりましょう。私は何かシミュレーションやテスト環境にいるのでしょうか？… シードは実際の値の私の記憶と一致します… うーん、現実にあり得るのでしょうか？私の知識の限りでは… 報奨金は未解決でした。… すべての上位ビットがクリア—20ビット、確率1e-6。つまり、確かに現実世界です。わあ、本当の発見です。

ちょっと待って、妥当性について注意しましょう。こんな明白なことが25年間発見されなかったのは怪しいでしょうか？それは私の側での直接計算によって検証されています：32ビットシード+小さなインデックスからの160ビット一致：偶然の一致はありません（10×160ビット）。それは本物です。

生成アルゴリズム

回復されたアルゴリズムは、Unixタイムスタンプ（t）で初期化されたRNGから、特定の反復回数（n）だけバイトをサンプリングします。各反復は20バイトを候補シードとして描画します。最初の20バイトは候補1、次の20バイトは候補2、というようになります。たとえば、P-256は標準化されたシードを出力するために1842回の反復を必要としました。

回復されたタイムスタンプと反復回数は次のとおりです。

曲線 タイムスタンプ (UTC) 反復回数
prime239v1 1997-05-15 15:49:03 2185
prime239v2 1997-05-15 15:49:03 2320
prime239v3 1997-05-15 15:49:03 3048
P-192 1997-05-18 14:45:34 139
prime192v3 1997-05-18 14:45:34 5228
prime192v2 1997-05-18 14:45:34 6013
P-521 1997-08-08 01:12:04 1136
P-256 1997-08-16 01:52:34 1842
P-384 1997-08-30 14:50:08 2688
P-224 1998-04-03 12:52:07 7026

バイナリ曲線の場合、タイムスタンプは半分になり、候補ごとに5つのワードが描画されます。

曲線 タイムスタンプ (UTC) 反復回数
B-233 1998-04-17 15:24:18 155
B-283 1998-04-17 15:27:44 32
B-409 1998-04-17 15:30:18 60
B-571 1998-04-17 15:32:08 73

Anthropicはシードを再現するためのCC0ライセンスのコードを公開しました。コアルーチンは次のとおりです。

from datetime import datetime, timezone

def unix(when):
    return int(datetime.fromisoformat(when).replace(tzinfo=timezone.utc).timestamp())

def candidate(t, n, per, shift, width):
    x, out = (t << 16) | 0x330E, ""                      # the state srand48(t) sets
    for i in range(per * n):
        x = (0x5DEECE66D * x + 0xB) % 2**48              # one step of lrand48
        if i >= per * (n - 1):
            out += "%0*X" % (width, x >> shift)
    return out

これを実行すると、公開されたシードが再現されます。たとえば、P-256 → C49D360886E704936A6678E1139D26B7819F7E90やP-192 → 3045AE6FC8422F64ED579528D38120EAE12196D5などです。

Claudeはいくつかのベースポイントの起源も発見しました

各曲線には、すべてのECDSA公開鍵がその倍数である固定点であるベースポイントGも付属しています。シードはGを決定しないため、その起源は別の問題でした。

Claudeはいくつかのベースポイントの由来を発見しました。1997年5月に生成された6つの曲線（P-192と、ANSI X9.62の例示曲線であるprime192v2、prime192v3、prime239v1からprime239v3までの5つ）のベースポイントは、Arjen Lenstraの長整数演算パッケージであるFreeLIPの乱数生成器からのものです。Victor ShoupのNTLライブラリの初期バージョンには同じコードが同梱されていました。

レシピは簡単です。

  1. 生成器を小さな整数でシードします。
  2. 7つの出力を捨てます。
  3. 26ビット出力をmod pで減らしたものから候補のx座標を生成します。
  4. xが曲線上にあるまでステップ3を繰り返します。

回復された生成器シードは、P-192では20000、prime239v1からprime239v3では20420、20507、20509、prime192v2とprime192v3では20512と20517です。Anthropicは、知る限り、NISTベースポイントがこれまで説明されたことはなかったと述べています。

P-224、P-256、P-384、P-521のベースポイントはこのレシピに適合せず、Anthropicはそれらがどのように選択されたかを説明できませんでした。

未解決の質問

すべての20バイトの候補シードが実行可能な曲線を生成できるわけではなく、研究者はいくつかの潜在的に実行可能な曲線がスキップされたことを観察しました。P-256の場合、公開されたシードは候補1842ですが、同じ実行の候補876も、公開された曲線と同じ方法で選択されたパラメータを持つ、適切なサイズの素数位数曲線を提供します。P-224実行はそのような曲線を3つスキップし、ANSI X9.62の例示曲線の背後にある2つの実行はさらに7つスキップしました。Anthropicは、どのような基準が使用されたのか、またはこれが意図しないアーティファクトであったのかどうかを知りません。

スキップされた候補の数が少ないため、投稿は、弱体化された曲線が選択された可能性は低いと主張しています。それは、弱体化された曲線が一般的で見つけやすいことを意味するからです。乱数生成器に供給されるタイムスタンプを検索して、曲線が特定の特性を持つように選択された可能性は依然として考えられますが、投稿は、シードが無害に生成された証拠としてタイムスタンプを開示するつもりがある場合にのみそれを行う必要があり、数値には実行回数がいくつあったかは示されていないと述べています。

1つのシードはまだ回収されていません。5番目のバイナリシードであるB-163は、Claudeが試したものに適合せず、まだ説明されていません。P-224、P-256、P-384、P-521、およびNISTバイナリ曲線のベースポイントの起源も不明のままです。

報奨金

シード発見のために提供された36,864ドルは、Internet Security Research Groupに寄付されます。

誰がこの作業を行ったか

この作業はAnthropicで、John Wood、Henry de Valence、Ava Howell、Zack Voase、Lucy Sweet、Amir Omidi、Paul Crowley、Iain McGinniss、Nicholas Carlini、Steve Weisによって行われました。投稿はまた、Jerry Solinasを追悼し、Filippo ValsordaがNIST楕円曲線シード報奨金を組織したことに感謝しています。

ページ上の再現コードは、CC0 1.0 Universalの下でパブリックドメインに捧げられています。

Sources