NIST曲線シードの謎を解く：ECDSA起源にまつわる5つの誤解

25年もの間、NIST ECDSA曲線のシードは応用暗号の世界で最も有名な未解決事件のようなものでした。NSAがNISTに渡した、説明のない5つの一見ランダムな160ビットの値は、TLS接続からビットコインの取引まで、あらゆる署名の土台になっています。今週ついにこの事件が解決しました。その答えはほとんど拍子抜けするものです。シードは、1997年と1998年のUnixタイムスタンプをシードにした、Cライブラリのlrand48()ジェネレータの出力だったのです。それだけです。秘密のパスフレーズのハッシュも、特殊な仕掛けもありません。セキュリティの講座で「絶対に使うな」と教えられる、まさにそのsrand48(time(NULL))というパターンでした。

発見のきっかけは、ある好奇心旺盛な社員が問題を持ち込んだAnthropicの研究用モデルでした。このモデルは、公開された定数に1990年代の線形合同法ジェネレータ特有の統計的な特徴を見つけ、状態を逆向きにたどってカレンダーの日付にたどり着きました。私は長年暗号システムの監査をしてきたので、これが重要な意味を持つとわかっています。曲線が破られたわけではありません（破られていません）。しかし、業界が自信を持って信じていた複数の前提が崩れたのです。では、誤解を一つずつ見ていきましょう。

誤解1：説明のない定数は隠されたバックドアを意味する

この疑念は決して的外れではありませんでした。NISTが2000年にFIPS 186-2の曲線を公表したとき、それぞれの曲線にはシードが付いていて、そのハッシュが曲線の係数bを決めていました。NISTは「検証可能なランダム性」があると説明しましたが、シード自体をどう生成したかは言えなかった（あるいは言おうとしなかった）のです。KoblitzとMenezesはこの論争について一本の論文を書き、「A Riddle Wrapped in an Enigma（謎に包まれた謎）」という皮肉なタイトルをつけました。コミュニティにとって最も有力な手がかりは、NSAのJerry Solinasでした。彼は2015年に、入力は「Give Bob and Jerry a raise（BobとJerryに昇給を）」のような冗談めいた文言のハッシュだったと語っています。しかし彼は2023年に亡くなり、詳細が明らかになることはありませんでした。

陰謀論者にとっては耳の痛い真実があります。（私自身も時々そう思っていました。）説明がないことは、たいてい悪意ではなく、記録がないことを意味します。実際の生成プロセスは、開発者が小さなCプログラムを走らせ、デフォルトの擬似乱数生成器に時計から自動でシードを与え、使える曲線を生んだ最初の候補を採用するというものでした。P-256の公開シードは、1997年8月16日午前1時52分に開始された実行の、候補番号1,842番です。これは、数論的なトラップドアを仕込もうとする機関のやり方ではありません。深夜1時にエンジニアが、何か有効なものが出力されるまでループを回していた、というだけの話です。

インシデントレビューでは、こうしたパターンを数えきれないほど見てきました。原因不明の設定値、文書化されていないマジックナンバー、誰も説明できないデプロイ手順。そして事後検証で判明するのは、疲れたエンジニアがその場では合理的だと判断した近道だった、ということです。誰にも書き残されていなかっただけなのです。NSAの本当の罪はバックドアを仕込んだことではありません。暗号定数をドキュメントなしで全世界に配ってしまったことです。

誤解2：生成方法が分かったから、選定も誠実だったと証明された

ただ、今度は行き過ぎた反応もあります。今週の論評の多くは「ただのタイムスタンプだった」という事実をもって、完全な潔白が証明されたかのように扱っています。しかし違います。研究者たちも慎重にそう述べています。候補の生成方法が分かったところで、最終的な曲線がどう選ばれたかは何もわかりません。そして選定は数ヶ月にわたって行われ、1997年5月から1998年4月まで続いていたのです。

証拠は両方の解釈を許します。P-256の実行では、候補876番も同じパラメータ規則で構築された、適切なサイズの素数位数の曲線を生成していましたが、それは見送られました。公開されたのは候補1,842番です。P-224の実行では3つの有効な曲線が見送られ、ANSI X9.62の実行ではさらに7つが見送られました。記録に残った実行で到達できた候補しか見えず、見送られた候補の全履歴は分かりません。特定の希少な性質を持つ曲線を求める者がいれば、理屈の上では、その性質を持つ曲線が見つかるまでタイムスタンプを探索し、タイムスタンプについては一切口をつぐむこともできたはずです。「やったが何も言わない」という選択肢は、常に存在していたのです。

弱い曲線の研究を長年追ってきた私の見解はこうです。バックドア仮説は深手を負ったものの、正式に死んだわけではありません。見送られた候補の数は少なすぎて、もし恣意的に選んだのなら、弱い曲線は一般的で見つけやすいということになりますが、20年にわたる公開された暗号解析はそれを否定しています。これらの曲線をランダムな曲線と区別する識別器が公開されたことも一度もありません。とはいえ「既知の弱点はない」と「弱点がないことが証明されている」は別の主張です。誠実な立場は前者です。これは、まさに標準化のレベルで起きている仕様と実装のギャップの典型例です。仕様は「検証可能なランダム性」と言い、実装は「時計が示した値」だったのです。

シードは、大学院生がやるような方法で生成されていました。標準的な擬似乱数生成器とシステムの時計です。問題になったのは数学ではなく、文書が欠けていたことなのです。

誤解3：弱い古い擬似乱数生成器も、一度しか使わなければ無害

これはsrand(time(NULL))と打ち込んだことのあるエンジニア全員が、背筋を伸ばすべき誤解です。25年にわたる謎の霧は、lrand48()の一つの設計上の性質が原因でした。このジェネレータは、48ビットの状態のうち上位31ビットしか返さないため、出力ワードの最上位ビットは必ずゼロになります。32ビットワードとして見ると、10個のバイナリ曲線シードのうち4個で、20個連続したワードの最上位ビットがすべてゼロになっていました。一様分布を仮定すると、この事象の確率は約58,000分の1です。このパターンは、見ようとさえすれば誰の目にも見えたはずです。

そこからの攻撃は、拍子抜けするほど安上がりです。バイナリ曲線の状態を復元するには、最初の出力ワードを取り、隠れた下位2^17ビットを総当たりし、次の4ワードが続くかを確認するだけです。計算は数ミリ秒で済みます。素数曲線の場合、シードは出力ごとに少ないビット数しか保持していなかったので、状態の復元には古典的な切り詰められた線形合同法への攻撃が必要でした。これを格子問題としてモデル化し、LLLの基底簡約をかけるのです。文字通り教科書的な手法です。状態さえ手に入れば、線形合同法は順方向と同じくらい簡単に逆方向にも動くので、srand48の初期化形式（下位ビットが0x330Eに等しい）が現れるまで逆にたどり、シードに使われたタイムスタンプを読み取ればよいのです。

# The whole mystery, reproduced
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, ""   # state set by srand48(t)
for i in range(per * n):
x = (0x5DEECE66D * x + 0xB) % 2**48   # one lrand48 step
if i >= per * (n - 1):
out += "%0*X" % (width, x >> shift)
return out
# P-256: run started 1997-08-16 01:52:34 UTC, candidate 1842
print(candidate(unix("1997-08-16 01:52:34"), 1842, 20, 40, 2))
# -> C49D360886E704936A6678E1139D26B7819F7E90  (the published NIST seed)

この教訓は標準化団体の枠を超えて当てはまります。あなたが出力する「ランダムに見える」値はすべて、それを生成したジェネレータの指紋を持っています。セッショントークン、リクエストID、ソルト、ファイル名、どれも同じです。そのジェネレータが線形合同法や梅森ツイスターであれば、わずかな出力から内部状態が再構築でき、その前後に生成したものすべてが予測可能になります。25年前の、ノイズに見せかけたファイル内での一度きりの使用が、完全に逆算されたのです。攻撃者に観測されうる用途で非暗号学的な乱数生成器を使っているコードをレビューするとき、今後はこの事例を引き合いに出すつもりです。

誤解4：「何も隠していない」数値が本当の防御だったことはない

「何も隠していない（nothing-up-my-sleeve）」という考え方は、円周率の桁のような明らかに無害なものから定数を導くことで、設計者の自由度を制限するためのものです。定数が公開された厳密な手順から導かれることを示せれば、そこにトラップドアを忍び込ませる余地はなかったことになります。NISTのシードは、手順が秘密だったため、自由度の制限がわからないという点で手続き上の検査に失敗していました。しかし、今回の件が本当に暴いたのは、袖の検査がうまくいっているときでさえ、私たちが思っていたより弱いということです。

「タイムスタンプから検証可能にランダムに生成された」とは実際に何を意味するのか、考えてみてください。妥当な期間のタイムスタンプが持つエントロピーは約31ビットです。誰であっても（元の作者も含めて）何百万ものタイムスタンプを試し、何百万もの候補曲線を生成して、欲しいものだけを、無害に見えるシードとともに公開できます。秘密の弱点を持つ曲線が百万分の1の確率で存在するなら、タイムスタンプの総当たりで午後の間に一つ見つけられてしまいます。シードはその数値がどこから来たかを証明しますが、なぜその一つが選ばれたのかはほとんど説明しません。パスフレーズのハッシュを使う方式も同じで、Solinasの冗談めいた文言についての噂が完全に安心材料にならなかったのもそのためです。

現代の望ましい方法は、厳密な曲線構築です。公開された一連のセキュリティ基準を満たす最小の係数を選び、探索を始める前に選定規則を固定しておくのです。Curve25519の背後にある考え方であり、Dan Bernsteinの厳密性に関する議論が、コミュニティの曲線評価の方法を大きく変えました。悪意ある定数に対する本当の防御は、巧妙な導出の物語ではありませんでした。探索空間を小さくし、基準を事前に公開し、隠れた性質が隠れたままにならないよう、十分な数の独立した目で数学を検証することです。定数を監査するとは、それをふるいにかけた過程を監査することです。だからこそ、ここでの未解決の問い（見送られた候補、P-256などの未説明の基点、いまだ特定されていないB-163のシード）は、祝賀ムードの中で葬り去られることなく、記録に残して開かれたままにしておくべきなのです。

誤解5：LLMは丸暗記するだけで、独自の暗号解析はできない

これは一番痛い誤解です。私自身もある程度これを信じていたからです。この未解決問題は、公開された36,864ドルの懸賞金と、熟練したアマチュアからの真剣な注目にもかかわらず、四半世紀にわたって解かれずにいました。Anthropicの研究者の何人かも自ら取り組み、「面白いフレーズのハッシュ」という手がかりを追いましたが、成果は得られませんでした。その後、噂を渡されずに問われた社内の研究用モデルが、30分足らずで別の角度から取り組みました。ハッシュへの入力を推測するのではなく、どのソフトウェアがシードを生成したのかを問い、1990年代のCライブラリの擬似乱数生成器を仮定し、各シードを走査して、生成器と出力の切り出しの34通りの組み合わせを試すスキャナを書きました。そして最上位ビットがゼロになるパターンを見つけ、切り詰められた出力に格子攻撃を適用し、状態をカレンダーの日付まで逆にたどりました。

このワークフローが何であるかに注目してください。これは想起ではありません。答えはどの学習データにも含まれていませんでした。答えはどこにも存在しなかったからです。これは仮説の生成、ツールの利用、検証の組み合わせであり、暗号解析の作業の実際の形そのものです。モデルは実行の途中で自分の健全性も確認していました。これはシミュレートされたテスト環境ではないか、こんなに明白なものが25年間も見つからずに残っているだろうか、32ビットのシードから一致した160ビットは偶然を排除するだろうか、といった具合です。この自己懐疑こそ人間のアナリストに求めたいものですし、正直なところ、人間のアナリストの中にはそれを省いてしまう人もいます。このサイトでは以前から、これらのモデルが実際に何をしているかについての誤解を検証してきましたが、今回のケースは明快なデータ点です。LLMは、ベンチマークだけでなく、現実世界の成果物に対して多段階の法医学的な推論を実行できるようになったのです。

実務家からの公正な反論は、出自（プロヴナンス）についてです。モデルはLCGの状態復元やLLLを発明したわけではありません。何十年にもわたる、名前のある研究者も名前のない研究者も含めた公開された暗号解析の上に立っており、そのアプローチにどの論文が影響したのかを示すことはできません。それを気にする人ほどには、私はそれを気にしていません。スキャナ、検証コード、再現スクリプトはすべて公開されています。チームの人間が問いを立て、結果を検証しました。役割分担を正直に評価しましょう。機械は疲れを知らない仮説探索を担当し、人間は判断と説明責任を担当しました。36,864ドルの懸賞金をInternet Security Research Groupに渡したことは、この件を締めくくる見事な方法でした。

セキュリティ監査にとっての意味

では、現場のエンジニアにとってこれはどういう意味があるのでしょうか。今後の監査へのアプローチで、私が考えている具体的な変化がいくつかあります。第一に、プロトコルやコードベース内のすべてのマジックナンバーを、自然の事実ではなく法医学的な証拠物として扱うことです。「ランダムだから」という答えを受け入れる前に、どのジェネレータがそれを生み出しえたのかを問い、構造的な指紋（上位ビットの偏り、線形合同法に由来する連続ワードの相関、タイムスタンプとして妥当な状態の復元）を確認してください。この作業のためのツールは、今ではごく簡単に手に入ります。

第二に、定数を公開するなら、ジェネレータも公開することです。ソースコード、正確な入力、正確な環境を。再現可能な手順のない「検証可能なランダム性」は、25年にわたる疑念と、あなたの遺産に対する懸賞金を買うだけです。第三に、P-256は引き続き使い続けてください。今回の発見は曲線への信頼を下げるどころか高めています。そして楕円曲線にとって本当の脅威モデルは、1997年のワークステーションの時計ではなく、量子ハードウェアという現実的な脅威です。ただし、未解決の問いは正直に読み取ってください。説明のつかない基点や見送られた候補は未決の問題であり、成熟したセキュリティの仕事とは、それらを帳簿に残し続けることです。

最も深い教訓は、組織の記憶についてです。Jerry Solinasは、昇給についての冗談を覚えていましたが、それは結局誤りでした。彼自身の言葉によれば、記録はおそらく契約の箱の近くのハードドライブにあるようなものでした。今日私たちが真実を知っているのは、出力そのものが、自白するのに十分な構造を保持していたからにすぎません。あなたのシステムは今この瞬間も、出荷するすべてのIDやトークン、定数の中で、自らの自白を書き残しています。それが誇れるものを告白するよう、確かめておいてください。