鷺羽 凹非寺にて
量子位 | 公式アカウントQbitAI
朝から、AI業界がまた騒然としています。。。
他意はない。AIのこの波の解題ラッシュは、すでに暗号学界の二十年以上前の古い問題にまで遡ってしまったのだ。
全員バトルロイヤル、今回は番ですね。Claude——
たった今、Anthropicの発表によると、Claudeは30分もかからず，NIST標準の5本の楕円曲線のシード生成方法を解明した。
この業界で20年以上使われてきた数字は、かつて暗号学の標準に書き込まれたこともあるが、最初にどう選ばれたのかは、誰もはっきり説明できなかった。
人々は当事者さえ突き止めた。手がかりはある一言を指していた。「BobとJerryに昇給を与える」のパスワードハッシュ演算。
すると劇的な展開がやってきた。Claudeはこう言った：とんでもない間違いだ！
本当の答えは、時間90年代のパソコン用時計。
さらに、この未解決の謎は、賞金の提供者による独立した再検証も受けている。
30分で解き明かす暗号学の未解決事件
事情の発端は、身元を「確認する」ための技術から語らなければならない。
ECDSA「、正式名称は楕円曲線デジタル署名アルゴリズム（ECDSA）です。」
受信者は、データが名乗る署名者によって署名されたものであるか、また署名後に改変されていないかを確認できます。2000年、米国国立標準技術研究所（NIST）によりFIPS 186-2デジタル署名標準に採用されました。
このアルゴリズムを使用する前に、曲線P-192、P-224、P-256、P-384、P-521を含むいくつかの公開数学パラメータを先に選定しておく必要がある。
論争はそれらの種子上。
シードは、曲線パラメータを生成する出発材料と理解できます。シードを入手し、標準で規定された手順に従って計算すれば、後続のパラメータが一致するかどうかを検証できます。
しかしなぜ、この種だけが，そもそも誰も知らない。
当時シードを提供したJerry Solinas自身もすでに記憶があいまいになっており、おおよそ、彼らがおそらく昇給をめぐるジョークのパスフレーズを数字に変換し、そこにカウンタを加えたということを覚えているだけだという。
そこでこの20年以上、皆がこの方向で推測を続けており、暗号エンジニアのFilippo Valsordaも発表した手配書、これら五組の種子の前身を探すよう大々的に呼びかけました。
いずれも自然消滅に終わったが、ついにClaude動き出した。
Anthropicの説明によれば、社員がこの問題を内部の研究モデルに渡した際、昇給の合言葉の手がかりについては伝えていなかったという。
そこでClaudeは自ら推測し、これらの数字はおそらく〜から来たのではないかと考えた90年代のC言語ライブラリ内の擬似乱数生成器。
なぜなら、この種のプログラムが生成する数字は雑然と見えるものの、背後には固定の法則が存在するからです。法則さえ見抜ければ、生成過程を逆算するチャンスがあります。
その後、Claudeは一つのスキャナー公開されたシード内のバイナリ数字を1桁ずつずらしながら調べ、34種類の生成器と出力切り出し方法の組み合わせをテストした。
その結果、4つのシードをそれぞれ5つの32ビット整数に分解すると、これら20個の整数の最上位ビットは、なんと全部が0でした。
事件は解決しました。犯人はおそらくlrand48乱数生成器。
lrand48は内部に48ビットの整数を保持しており、呼び出しごとにこの整数に固定定数を掛け、さらに別の定数を加え、最後に結果の下位48ビットのみを残して次の状態とします。
しかし出力結果はそのうちの上位31ビットのみで、32ビットに収める場合、残りは0で埋めるしかない。
マシンを見つけた後、ClaudeはさらにLLL格基約簡アルゴリズムを用いて、種が切り詰められた状態から復元した。
残る問題はひとつだけ、最初にどう起動したのかということだ。
初期化を担当する関数はsrand48と呼ばれ、入力値を48ビット状態の上位32ビットに置き、下位16ビットを固定で0x330Eに設定した上で、漸化式に沿って逆算し、その目標がUnixタイムスタンプ。
に向けられる。これらの初期化入力は一様に1997年5月から1998年4月。
に集中していた。つまり、ある時刻を整数に変換し、ジェネレータに渡し、決められた方法で数字を取り出せば、標準の中のシードを再び得ることができる。
P-256を例にとると、対応する初期化時刻は1997年8月16日、UTC時間01:52:34である。
この時刻からジェネレータを実行し、第1842組目の候補を取ると、得られたのはまさにC49Dで始まるあのシードだった。残りの4組も一つ一つ対応した。
もちろん、A社も、この結果ですべての歴史的な空白が埋まったわけではないと述べている。
研究者らが発見したところによれば、当時のプログラムは、条件を満たしているように見えた候補曲線をいくつかスキップしており、その理由は依然不明である。また、B-163のシードや、一部の曲線の基点の生成方法についても、まだ説明が得られていない。
ただし、この新しい結果は、これらの曲線に潜在的なセキュリティ脆弱性が一切存在しないことも意味しており、安心して利用できる。
参考リンク：
[1]
https://www.anthropic.com/research/ecdsa-curve-origins
[2]
https://x.com/sweis/status/2111165738836717980
[3]
https://words.filippo.io/seeds-bounty/