要約:
10 月 16 日、Anthropic は特別な研究結果を発表しました。ある従業員がクロードに、20 年以上にわたって暗号コミュニティを悩ませてきた問題を社内の研究モデルに引き渡しました。クロードは重要な手がかりを提供することなく、5 つの NIST 楕円曲線シードがどのように生成されたかを追跡するのに 30 分もかかりませんでした。
シードは、C ライブラリの古い疑似乱数生成器 lrand48 から来ていることがわかりました。ジェネレーターの初期状態は、Unix タイムスタンプによって決定されます。
この発見は ECDSA を破壊するものではなく、新しい攻撃方法を導入するものでもありません。 Anthropic は、相関曲線への人為的なバックドアの可能性をさらに減らすことができると考えています。
一連の数字は 20 年以上にわたって暗号コミュニティを悩ませてきました
ECDSA は、広く使用されている楕円曲線デジタル署名アルゴリズムです。
2000 年に、NIST は、P-192、P-224、P-256、P-384、P-521 など、FIPS 186-2 標準のさまざまなセキュリティ レベルに対するいくつかの標準曲線をリストしました。
これらのカーブには、「シード」と呼ばれる一連のパラメータが付属しています。標準の生成プロセスによれば、シードのハッシュ値は曲線係数の決定に関与します。
問題は、これらの種子は国家安全保障局によって提供されたものであり、公的文書にはその起源が示されておらず、選択プロセスについても説明されていないことです。外部の世界は、設計者が多数の候補曲線をスクリーニングし、いくつかの隠れた特性を持つパラメーターを選択したかどうかについて長い間懸念していました。
2015 年、関連作業に参加していた NSA の暗号学者ジェリー ソリナス氏は、シードは「ボブとジェリーに給料を上げろ」などのジョークのパスワードから来た可能性があると回想しましたが、具体的な詳細は覚えておらず、昔のアーカイブ ファイルは見つかりませんでした。ソリナス氏は2023年に死亡し、そのリードは最終的に検証されなかった。
クロードは種子の源を見つけました
Anthropic の従業員の多くは、以前に「ユーモラスなパスワード」に従ってこれらの「シード」を見つけましたが、成功しませんでした。その後、その手がかりが間違っていたことがわかりました。
10 月、従業員が社内の研究モデルに、これらの「種」がどのように生成されたかを解明するよう依頼しました。今回、彼はモデルの以前のパスワードの手掛かりを明らかにしませんでした。
30 分もかからずに、クロードは NIST の P-192、P-224、P-256、P-384、および P-521 シードのソースを発見しました。
これらのシードはハッシュ アルゴリズムから取得されたものではなく、C ライブラリの lrand48 乱数ジェネレータによって生成され、Unix タイムスタンプをシード値として初期化されます。
特定のアルゴリズムは、Unix タイムスタンプ t を使用して乱数生成器を初期化し、一定の回数 n だけ実行します。各反復では、候補シードとして 20 バイトが抽出されます。
最初の 20 バイトが最初のシード候補、次の 20 バイトが 2 番目のシード候補、というようになります。 P-256 を例にとると、ジェネレーターは 1842 回目の実行まで、最終的に標準に書き込まれるシードを出力しません。
クロードはどうやって彼を見つけましたか?
噂のパスワードを検索しても結果は得られませんでした。クロードは視点を変え、曲線を生成したソフトウェアがどのように機能したのかを推測し始めました。
クロードは、このソフトウェアが 1990 年代に C 言語ライブラリに付属していた擬似乱数生成器を使用しているのではないかと推測しました。これらの初期の疑似乱数生成器はセキュリティが弱く、その出力には通常、識別可能な特性がありました。
出力特性が特定されると、ソフトウェアがどのジェネレーターを使用したかを判断し、さらに初期状態に戻すことができます。
クロードは、各公開シード上を少しずつ移動するスキャナを作成し、隣接するデータのチャンクが 1990 年代の乱数発生器からのものであるかどうかをチェックしました。このスキャンでは、乱数発生器と出力傍受方法の合計 34 の組み合わせがカバーされています。
その後、クロードはいくつかのシードの上位ビットにパターンを発見しました。これらのビットはすべて 0 でした。
各シードが 5 つの 32 ビット ワードとして書き込まれる場合、10 個のシードのうち 4 個がこのプロファイルに適合します。これら 4 つのシード (合計 20 個の 32 ビット ワード) では、最上位ビットはすべて 0 です。
これがランダムに発生する確率は、約 5800 分の 1 です。これは、48 ビットの内部状態の上位 31 ビットのみを返す線形合同生成器 lrand48 の典型的なものです。
ジェネレータの状態を復元するために、クロードは最初の 32 ビット ワードを取り出し、17 の隠れビットの 2¹⁷ の可能性をすべて使い果たし、次の 4 ワードが連続的に対応できるかどうかをチェックします。この方法は、上記の 4 つのシードすべてに機能します。
ピクチャーインピクチャー
一時停止
現在時刻 0:15
/
長さ 5:08
全画面表示
ミュートを解除
自動再生
素数曲線も lrand48 からシードされますが、保持される出力ビットは少なくなります。クロードは、これらの有限ビットから擬似乱数発生器の内部状態を復元する必要があります。
切り捨てられた線形合同生成器の状態の回復は、LLL アルゴリズムとしても知られる、Lenstra-Lenstra-Lovász 格子基底縮小アルゴリズムを使用して解決できる典型的な格子問題です。
クロードは最初、シードが内部状態のどのビットを保持しているのかを知らないため、考えられるすべてのビット ウィンドウでソルバーを実行します。
最後に、5 つの NIST 素数曲線シードと ANSI X9.62 標準の 5 つのシードはすべて同じパターンを示します: lrand48() >> 23
復元された 48 ビットの内部状態はそれぞれ、対応するシードの 160 ビットすべてを再生成でき、この完全な一致は偶然に発生することはありません。
この線形合同ジェネレーターは、順方向と逆方向の両方で実行できます。したがって、クロードは各シードに対応する状態から開始し、srand48 初期化形式に準拠する状態が見つかるまでバックトラックします。この形式では、下位 16 ビットが 0x330E に等しい必要があります。
この形式の内部状態は、平均して 65536 ステップごとに 1 回発生します。したがって、単に形式に適合する状態を見つけるだけでは証拠として十分ではありません。
重要なのは、10 個の素数曲線シードに対応する srand48 初期値はすべて Unix タイムスタンプとして解釈でき、日付は 1997 年 5 月から 1998 年 4 月の間に集中していることです。
これは、その年のプログラムが Unix タイムスタンプを使用して、安全性の低い疑似乱数生成器の初期値を設定していたことを示しています。
4 つのバイナリ曲線の初期値を直接読み取ると、1984 年 2 月に対応します。これらのタイムスタンプ値を 2 で乗算すると、P-224 曲線が生成されてから約 2 週間後の 1998 年 4 月 17 日を指します。
したがって、当時のプログラムはシステム クロックを 2 で分周していた可能性があります。
以下は、当時のクロードの内部の思考プロセスです。
これは衝撃的です。 25年来の謎が解ける。
うーん、ちょっと待ってください。私は疑う必要があります。私はある種のシミュレーションまたはテスト環境にいるのでしょうか?シードは私の記憶による実際の値と一致しています。
実際、これは合理的でしょうか?私の持っている情報によると、この懸賞金はこれまで解決されていません。
すべての上位ビットはゼロで、合計 20 ビットであり、ランダムに発生する確率は 100 万分の 1 程度です。つまり、これは現実世界からのものです。なんと、これは本当に発見です。
待て、その妥当性を判断する際にはまだ注意が必要だ。なぜこのような明白な手がかりを 25 年間誰も発見できなかったのでしょうか?
私は直接計算を行うことでこれを検証しました。32 ビットの初期値に小さいインデックスを加えたものは、160 ビットのシードと正確に一致します。 10 個のシードがあり、それぞれが 160 ビットに一致するのは単なる偶然ではありません。それは本当です。
クロードは、P-192 を含む 6 つの曲線の基点の原点も追跡しました。結果は、これらの基点が大整数演算ソフトウェア パッケージ FreeLIP の乱数発生器によって生成されたことを示しています。アンスロピック氏は、NIST曲線の基点を生成するプロセスはこれまで同様に説明されていなかったと述べた。
これはどういう意味ですか?
タイムスタンプ自体には暗号化セキュリティがなく、lrand48 は長い間、弱い乱数生成器とみなされてきました。ただし、ここでの役割は公開曲線パラメーターを生成することであり、秘密キーを保護するためには使用されません。
さらに重要なのは、この生成プロセスは公的に再現できるということです。通常の乱数ジェネレーターとタイムスタンプの解釈では、出所不明のパスワードや人為的に指定されたパラメーターに比べて、曲線を秘密裏に操作する余地が少なくなります。
いくつかの問題が残っています。 P-256 の生成時には、876 番目の候補値が要件を満たしているように見えましたが、最終的に採用されたのは 1842 番目の値でした。他のいくつかの実行でも同様に少数の利用可能な曲線がスキップされており、正確なスクリーニング基準は不明瞭でした。 B-163 曲線のシード源は未発見のままであり、P-224、P-256、P-384、および P-521 の基点が生成される方法も未解明のままです。
Anthropic は、スキップされた候補の数が少なすぎて、「意図的に弱い曲線を選択した」という推測を裏付けることができないと考えています。この発見により、関連パラメータに対する外部の信頼が高まりましたが、設計プロセス全体が完全に復元されたとみなすことはできません。
この研究は、最先端のモデルが現実世界の研究に参加できる別の方法も示しています。
クロードは、仮説の策定、コードの作成、パターン認識、数学的アルゴリズムの呼び出し、結果の検証を 1 つのタスクで完了しました。ジェネレータの状態を再計算でき、160 ビット シードを正確に再現できるため、結論は非常にテスト可能です。
質問、公開データの提供、再現可能な計算による結果の確認は依然として人間に依存していますが、問題の境界が明確で、データが公開され、結果を厳密に検証できる場合、最先端のモデルは効率的な研究ツールになりつつあります。
シードソースの発見に対して以前に授与された 36,864 ドルの賞金は、インターネット セキュリティ研究グループに寄付されます。
コメント