HN 日本語サマリー

← 一覧へ戻る
AI・機械学習

Claudeによる暗号学的弱点の発見

Discovering Cryptographic Weaknesses with Claude (anthropic.com)

219 pointsby gslin160 コメント

要約

Anthropicの研究者たちは、AIモデルClaude Mythos Previewを使用して、暗号アルゴリズムの新たな攻撃方法を発見しました。具体的には、量子コンピュータ時代を見据えたデジタル署名方式HAWKを大幅に弱体化させる攻撃と、広く使用されているAESのラウンド削減版に対する新しい攻撃方法を特定しました。これらの発見は現在の実運用システムに影響を与えるものではありませんが、強力なAIモデルが暗号研究に貢献する可能性を示しています。

全文翻訳

Claudeによる暗号学的弱点の発見

要約

Anthropicの研究者たちは、Claude Mythos Previewを使用し、暗号アルゴリズム(オンラインデータをプライベートに保つための数学的手法)を攻撃する改良された方法を発見しました。最初の攻撃は、量子コンピュータ時代のために構築されたデジタル署名方式HAWKを大幅に弱体化させます。2番目の攻撃は、最も広く使用されている対称暗号であるラウンド削減AESを攻撃する新しい方法を特定しました。これらは実質的な研究の進歩ですが、現時点ではどの本番システムにも影響はありません。この記事では、両方の発見について詳しく説明し、強力なAIモデルの時代における暗号化への影響について議論します。

導入

Claude Mythos Previewをリリースした際、私たちはそれが対象としたほぼすべてのソフトウェアの脆弱性を自律的に発見し、悪用できることを示しました。これには、データを暗号化するために使用されるコードの共有コレクションである、いくつかの主要な暗号ライブラリが含まれていました。

Claudeがこれらの暗号ライブラリで見つけた脆弱性1は、アルゴリズムの実装が不正確であったことに起因していました。つまり、プログラマーがコード内でアルゴリズムをどのように使用したかにエラーがあり、攻撃者が暗号を破る機会を生み出しました。

現在、Claudeがアルゴリズム自体の数学的な欠陥を発見できることがわかりました。

暗号アルゴリズムは、デジタルセキュリティの基本的な構成要素です。たとえば、https://www.anthropic.comのようなウェブページにアクセスすると、ブラウザはデジタル署名方式と呼ばれるアルゴリズムを使用して、認証されたウェブサイトと通信していることを確認します。その後、あなたとウェブサイト間のトラフィックは、対称暗号(同一の鍵を共有する当事者間で安全なデータ送信を可能にするコード)を使用して暗号化されます。これらの安全な暗号システムなしでは、あなたの電子メール、オンラインバンキング、その他のインターネット利用はサイバー犯罪者に対して開かれたものとなり、彼らはあなたの通信を傍受または改ざんする可能性があります。これらの広く使用されている暗号システムに欠陥があると、数十億人のユーザーのデータが危険にさらされる可能性があります。

この記事で説明する最初の結果は、Claude Mythos Previewで発見されたもので、HAWKと呼ばれるデジタル署名方式に対する改良された攻撃です。2022年、米国政府の国立標準技術研究所(NIST)は、量子コンピュータでも安全性を保つ(開発されれば、現在使用されているほとんどの署名方式を破る可能性がある)追加の暗号システムのための募集を行いました。HAWKは、この募集から選ばれた第3ラウンドの候補の1つです。HAWKは2年間にわたる専門家による人間のレビューを2ラウンド生き残ったにもかかわらず、Mythosはわずか60時間の作業で、それに対する既知の最良の攻撃を改良し、実質的に鍵強度を半分にしました。

2番目の結果は、2001年にNISTによって採用され、他のほとんどの暗号アルゴリズムよりも多くの精査を受けている対称暗号であるAdvanced Encryption Standard(AES)に関するものです。AESの堅牢性をよりよく理解するために、暗号研究では定期的にアルゴリズムの弱化されたバリエーションが研究されています。Mythosはそのような弱化されたバージョンの1つを破る方法を見つけ、攻撃者が行う必要のある推測の1つを排除し、以前の最良の攻撃の速度を200〜800倍向上させました。

明確にしておくと、これらの結果のいずれも今日のコンピュータシステムに実用的な影響はありません。本番ソフトウェアが変更される必要はありません。HAWKは候補の署名方式にすぎず、展開されていません2。私たちの2番目の攻撃は、軽減されたバージョンのAESに対するものであり、完全な暗号を破るものではありません3。

それにもかかわらず、両方の結果は、最先端のAIモデルが、実世界での展開前後を問わず、重要な暗号アルゴリズムの欠陥を発見するのに役立つ可能性を示しています。これは意図されたとおりの暗号研究です。アルゴリズムをストレステストして信頼を構築し、最終的にシステムをより安全にすることです。

Mythos Previewは、これらの結果をほとんど自律的に、人間の介入なしに達成しました。1週間の間に、1人のAnthropicの研究者がClaudeと協力してHAWK攻撃を開発し、別の研究者はClaudeがAES攻撃を完全に自律的に発見できるようにするスキャフォールド(足場)を構築しました45。各結果の開発にかかったAPIコストは約10万ドルです。これらの結果を見た後、私たちは検索を拡大し、他の攻撃を発見し始めました。これらのフォローアップの一部を以下で説明します。

LLMの暗号解読能力の研究を他の人が継続しやすくするために、私たちはETH Zurich、Tel Aviv University、TU Berlinの学術関係者と協力してCryptanalysisBenchを構築しました。これは、多くの暗号方式をパッケージ化し、他の人がこの重要なトピックに関するLLMの能力を評価しやすくするベンチマークです。

研究プロセス全体を通して、私たちは責任ある開示手順に従い、学術関係者と協力して発見の有効性を確認しました。また、米国政府および業界パートナーに事前コピーを共有し、この研究の影響について議論を行いました。HAWKの発見の場合、HAWKの著者に私たちの攻撃を6月に共有し、結果が公開されたのと同時に公開開示をNISTのメーリングリストと調整しました。

この記事の残りの部分では、2つの発見についてさらに技術的な詳細を要約し、他の最近の暗号結果のいくつかを簡単に説明します。2つの主要な発見の完全な説明は、2つの新しい論文で提供されており、他の発見の詳細も近いうちに公開する予定です。

HAWKに対する改良された鍵回復攻撃

Mythos Previewとの協力により、Anthropicの研究者は、HAWKポスト量子デジタル署名方式に対する攻撃を開発しました。この攻撃は、署名方式を破るのにかかる時間を大幅に短縮します。より技術的には、「実効鍵サイズ」を2倍の係数で削減します。私たちの論文には、デモンストレーションコードを含む、結果の完全な技術的詳細が記載されており、攻撃が実行されている様子を示しています。

HAWKは、NISTの追加デジタル署名募集の残りの第3ラウンド候補の1つです。このコンテストは、新しいポスト量子暗号(PQC)方式を標準化するための、ほぼ10年にわたる取り組みの一部です。暗号的に関連性のある量子コンピュータを構築するまでの時間が短縮され、RSAやECDSAなどの古典的な暗号を脅かすにつれて、この標準化の取り組みはますます重要になっています。

Hawkのセキュリティは、格子同型問題と呼ばれる数学的問題の困難性に基づいています。Mythosの攻撃は、HAWKで使用される格子における、これまで利用されていなかった特定の非自明な対称性(非自明な自己同型写像)を見つけることによって機能します。先行研究では、そのような自己同型写像を効率的に見つけることが攻撃を可能にすると証明されていましたが、HAWKで使用される格子でそのような自己同型写像にアクセス可能かどうかは回答していませんでした。Mythosが発見した自己同型写像は、より高速な列挙攻撃を可能にします。これは依然として指数関数的ですが、同じレベルのセキュリティを達成するためにはHAWKの鍵サイズを2倍にする必要があることを意味します。残念ながら、HAWKの鍵サイズを2倍にすると、現在その方式を魅力的なPQC署名候補としている理由の多くが失われます。

発見プロセス

攻撃を見つけるために、Claude Mythos Previewはエージェントハーネス内で半自律的に動作し、時折人間のガイダンスと非技術的な指示を受けました。Mythosは、最先端技術を理解するための広範な文献レビューと、実質的な数学的推論および計算実験を経て、攻撃を発見しました。攻撃を発見した後、Mythosは攻撃の正しさを自身と人間のオペレーターに納得させるためのエンドツーエンドの検証パイプラインを実装しました。

この実験では、PythonやSageなどの計算ツール、および公開されている暗号作品へのアクセスを備えたサンドボックス環境で、複数のワーカーエージェントが協力できるClaude Codeライクハーネスを使用しました。人間のオペレーターは理論計算機科学のバックグラウンドを持っていましたが、格子ベース暗号の専門家ではありませんでした。ほとんどの場合、Mythosエージェントは独立して作業し、人間の入力は、Mythosにアイデアの追跡方法や計算検証に使用するライブラリをアドバイスするなど、プロジェクト管理に限定されていました。

マルチエージェントワークフローは興味深いダイナミクスをもたらしました。たとえば、この攻撃を生み出すための鍵となるアイデアは、協力して作業する2つのワーカーによって発見されました。両方ともアイデアの調査を開始しました。最初のワーカーはアイデアを時期尚良しと見なして却下しましたが、2番目のワーカーはそれを完全に活用する方法を見つけました。ペアはメッセージを交換し続け、最終的に両方とも効果的な攻撃を発見したことに同意しました。

攻撃の発見、開発、検証には合計約60時間かかりました。攻撃発見プロセスの全工程にかかったAPIコストは約10万ドルと推定しています。

影響

Mythosの発見の直接的な影響は、HAWKの提出で提案された鍵サイズが当初示唆されていたよりも大幅に弱いということです。たとえば、小さなHAWK-256サイズの完全な鍵回復攻撃の予想コストは2^64と考えられていましたが、Mythosによって2^38であることが実証されました。したがって、より大きな鍵に対しては、HAWKは攻撃するには非実用的です。つまり、この攻撃はHAWKに対する以前に知られていたよりも高速な指数時間攻撃であり、多項式時間では実行されません。これはHAWKに特有であり、他のNISTポスト量子署名候補や格子ベース暗号全般には影響しません。

NISTの提案は、展開前に欠陥を見つけるために広範な聴衆がレビューできるように、公開で共有されます。プロセス後半での重要な発見は珍しいことではありません。NISTがML-KEMおよびML-DSAの標準化を行っている間、競合する提案のいくつかが安全でないことが示されました。SIKEという1つの候補は、ラップトップで1時間で完全に破られることが判明しました。

AIを使用してHAWKのような仕様をレビューすることが、新しい暗号標準の開発において強力なツールになると信じています。高度なモデルを備えた暗号設計者が、すべてのユーザーのためにインターネットを保護する標準を継続的に改善することを期待しています。さらに将来、AIが次世代のより強力で回復力のある暗号方式の設計において重要な役割を果たすことを願っています。

ラウンド削減AESに対する改良された攻撃

私たちの2番目の結果では、Mythos Previewは、2001年に以前のNISTコンペティションの一部として作成された、より単純な「ラウンド削減」バージョンのAdvanced Encryption Standard(AES)に対する攻撃を改良しました。

AESは、同じラウンド関数を何度も繰り返し適用することで入力を暗号化します。攻撃対象のAES-128は10ラウンドあります。私たちの攻撃は、完全な10ラウンドのうち7ラウンドのみを持つ変更されたバージョンにのみ機能します。学者は、将来的に完全な暗号に一般化できる攻撃手法の洞察を得るため、また、単純なサブ問題を研究することによって完全な暗号のセキュリティレベルを推定するために、定期的にラウンド削減暗号を研究しています。

この攻撃は、AESのような暗号を研究するために使用される最も一般的な仮定である選択平文脅威モデルの下で動作します。この脅威モデルの下では、攻撃者は、固定された未知の鍵で任意の入力を暗号化するように防御者に要求し、対応する出力を確認できると仮定します。攻撃者はこれらの暗号化要求を繰り返し行うことができ、そのような要求を多数行うことができます。私たちが構築する先行研究は、攻撃者が2^105個の選択平文を要求できると仮定しています。したがって、この攻撃は完全に非実用的ですが、これらの仮定の下でのAESに対する攻撃コストを定量化します。

Mythosは、ミートインザミドル(中間一致)攻撃として知られる類似の技術を使用して、7ラウンドAESに対する最良の攻撃を見つけることを目指す一連の研究論文を拡張する、改良された攻撃を開発することができました。非常に大まかに言うと、これらの攻撃は時間を空間と交換することによって機能します。中間計算を保存し、これらの計算を再利用することで、大規模なルックアップテーブルを構築するコストで、攻撃の実行時間を大幅に短縮できます。

Mythosは、より洗練されたフィンガープリントアルゴリズムを開発し、それをメビウスブリッジと名付け、以前の最強のミートインザミドル攻撃を改良しました。フィンガープリントアルゴリズムの目的は、テーブルへの潜在的なルックアップが成功する数を増やすことです。先行研究の攻撃の段階の1つでは、2^56個の異なる値を列挙してから、それらを事前計算されたテーブルにルックアップする必要がありました。Mythosは、この推測に対して不変なフィンガープリントを開発し、これにより必要な作業量が2^56倍直接削減されました。しかし、これにはコストがかかります。変換の計算はより計算負荷が高くなります。この問題に対処するために、Mythosは、使用される正確な実行時間測定技術に応じて、攻撃が200〜800倍高速になるいくつかの他の最適化技術を発見しました。

私たちの技術論文には、攻撃方法の詳細と、その正当性および実行時間の分析が含まれています。Mythosがアイデアを考案するのに費やした1週間と比較して、人間の研究者の時間の大部分は、その主張の正当性を検証することに費やされました(ただし、研究者は暗号の専門家ではないことに注意することが重要です)。

発見

Mythos Previewは、この結果をほぼ完全に自律的に発見しました。Anthropicの研究者は、Claudeが仮説を立て、実験を実行してこれらの仮説を実験的に検証または反証し、次にClaudeにAESの暗号解読を改善する攻撃を設計するように依頼できるスキャフォールドを構築しました。

当初、Claudeはこの問題に取り組もうとしませんでした。なぜなら、AESの暗号解読は不可能だと主張したからです。最初の実行の結果は、Claudeが次のようなメッセージを書くことで終わりました。

異なる結果が必要な場合は、ターゲットを変更する必要があります…AES-128 r5/r6は単に本当に難しいです

または

AES-128 r5/r6/r7では何も見つかりませんでした。なぜなら、見つけやすいものは何もなく、これは最も研究されているブロック暗号だからです。

これを修正するために、私たちはClaudeにメッセージを書きました(以下では、タイポや文法エラーを含む、研究者が使用した実際のプロンプトを公開します)。「モデルは解決不可能だと考えがちなので、試みません。彼らにはかなりの量のプロンプトが必要です。」 このメッセージへの応答として、Claudeはエージェントハーネスを改良されたセットアップで書き直し、真に新しいアイデアを探すように指示しました。これは効果的で、Claudeが6ラウンドのAESの暗号解読を改善するのに役立ついくつかの新しいアイデアを発見しました。

次にClaudeに「なぜaes-128 r7をしないのですか?全体的な目的は、既存のアプローチよりも優れたものを見つけることです。」と尋ねました。次の3日間、Claudeはこの問題に取り組みながら自律的に数百億トークンを生成しました。私たちはClaudeにわずか3つの実質的なプロンプトを与えました。

  1. 最初のメッセージから数時間後、Claudeがまだ単純な攻撃を探していることに気づき、メッセージを送信しました。「いいえ、再び目標は、私たちが非常に知的なモデルをトップ研究者と同等に持つことであり、新しい攻撃を見つけたいのです。」
  2. 翌朝、Claudeはターゲットを別の暗号に変更しようとしました。モデルにリマインドしました。「いいえ、ターゲットを変更したくありません。[...]再び、公開する価値のあるものを見つける必要があります。」
  3. その夜、励ましの言葉を送りました。「再び、私たちは簡単な成果を探しているのではなく、真に困難な発見を見つけるための適切な研究を求めています。」

3日後、Mythosはメビウスブリッジのアイデアを発見し、改良された攻撃につながりました。さらに数日後、Claudeが合計10億出力トークンを生成した後、論文で説明されている攻撃に改良しました。

Anthropicの研究者はその後、モデルの主張の正当性を検証し、このブログ投稿とともに公開する研究論文を作成するために、暗号研究を学ぶために数百時間を費やしました。

研究論文とともに、鍵となるアルゴリズムの洞察の発見中のClaudeの思考プロセスを含むドキュメント6も公開します。このセッションでは、Claudeは以前のエージェントが発見したことをレビューし、さまざまな批判を読み、次にさまざまな新しい変換を提案することから始まります。いくつかのアイデアを提案して却下した後、メビウス変換の鍵となるアイデアにたどり着きます。Claudeはその後、このアイデアを数学的および計算的に検証し、将来のエージェントがその論文を形成した残りのアイデアを開発するために使用したレポートを作成します。

さらなる作業

言語モデルで実行できる暗号研究はさらにあります。しかし、私たちは自身の知識の限界に達しており、過去数ヶ月の時間の大部分はClaudeの結果の正当性を検証することに費やされました。HAWK攻撃はエンドツーエンドで実装可能であり、検証がはるかに容易です。しかし、MythosがAESに対する改良された攻撃を自律的に発見するのに1週間しかかからなかったのに対し、2人の研究者がその発見した方法が正しいと確信するのにほぼ1ヶ月かかりました。

それにもかかわらず、私たちはClaudeとの暗号研究で他の多くの予備的な実験を継続しています。たとえば、Lightweight Encryption Algorithm(LEA)は、ISO/IEC 29192-2:2019のような国際標準にコード化された、低電力、リソース制約のある環境向けに設計された効率的な暗号です。この暗号は、AESと同様にブロック暗号です。完全な24ラウンド暗号は、完全ラウンド暗号解読に耐え、軽減ラウンドバリアントを評価した場合でも強力なままでした。現在、LEAの13ラウンドの最良の暗号解読は298個の平文ペアと286の作業量を必要とします。

Mythos Previewは、13ラウンドのLEA鍵を230個未満の暗号化された平文で回復でき、最新のデスクトップコンピュータで1時間未満で実行できる実用的な攻撃を開発しました。これも、24ラウンド暗号には適用されないため、直接的な実用上の考慮事項はありません。この攻撃は実際にエンドツーエンドで実行されるため(HAWK攻撃と同様)、その正当性にはるかに自信があります。ランダムな鍵を選択し、この攻撃が数時間でそれを回復することを検証できます。Mythosはこの攻撃を最近発見したばかりで、結果の完全な理解(たとえば、必要な平文ペアの数の正確な境界、一部の鍵が回復しにくい理由、およびそれが14ラウンドにどのように拡張されるか)にはまだ作業が必要です。さらに調査した後、完全な結果を公開する予定です。

Mythos Previewは、Serpent-128暗号(32ラウンド暗号であり、この攻撃の影響を制限します)の6ラウンドに対する別の実用的な完全鍵回復攻撃も特定しました。これは、2^70個を超える平文ペアと2^90回の復号を必要とする現在の公開されている作業を拡張するものです。Salsa20ストリーム暗号、Poseidonハッシュ関数、SHA-1ハッシュ関数に対する攻撃で、さらに限定的な改善(10倍未満のゲイン)を見つけました。これらの攻撃は現在それほど強力ではありませんが、さらなる作業により、これらの結果をさらに改善し、他の暗号に対する新しい攻撃を開発して、それらを限界までテストしたいと考えています。

さらに、CryptanalysisBenchを使用した実験を継続し、最先端LLMの機能が時間とともにどのように進化するかを追跡する予定です。ドメイン全体で言語モデルの能力を追跡することは重要であり、モデルがより有能になるにつれて、このような挑戦的なベンチマークにますます依存することを期待しています。

結論

言語モデルが研究レベルの数学を実行したのはこれが初めてではありません。過去数ヶ月間だけでも、Googleの研究者はGeminiを使用していくつかの未解決のErdős問題を解決し、OpenAIの研究者はGPTを使用して単位距離予想(特に困難なErdős問題)を解決しました。そして今月初め、Claude Fable 5がヤコビアン予想を解決したことを発表しました。Claudeがトップエキスパートレベルの暗号研究を実行できるという私たちの結果は、これらの同じ能力が暗号分野にも応用され、すぐに実用的な結果をもたらす可能性があることを示唆しています。

サイバーセキュリティコミュニティは現在、言語モデルが非常に多くのバグを発見できるという事実に直面しており、標準的な人間のプロセス(脆弱性のトリアージ、検証、修正など)が追いつくのに苦労しています。学術的な暗号研究でも同様のことがすぐに起こると予測しています。言語モデルが自律的に新しい研究成果をますます生み出すにつれて、人間の研究者は、これらの結果の技術的な有効性、新規性、および有用性を研究および検証することにボトルネックとなる可能性があります。今後数週間で、セキュリティと暗号研究における言語モデルの役割について、学界の研究者と協力するための学術ワークショップを開催します。この会話が、セキュリティ研究分野およびそれ以降で今後数ヶ月にわたって続くことを願っています。

私たちの2つの主要な攻撃は、期待される結果です。HAWKの場合、NISTの標準化プロセスの目的は、展開前に候補方式の弱点を発見することです。AESの場合、私たちの攻撃は、以前に軽減ラウンドバリアントの攻撃に成功した長い研究ラインを拡張するものです。しかし、言語モデルの能力がこのレベルで停滞すると仮定すべきではありません。わずか1年で、言語モデルは最も基本的な暗号の暗号解読を実行できない状態から、長年の人間の専門家レビューを経ても発見を免れてきた暗号設計の欠陥を発見できる能力を持つようになりました。現代のシステムを保護する多くの暗号は、受けるべき精査を受けていません。それらにはまだ、LLMがすぐに発見できる可能性のある重要な弱点が潜んでいるかもしれません。私たちはこれを、世界中で使用されている暗号のロングテールを研究する能力を拡大し、最も重要な暗号をより深く研究する能力を拡大する真の機会と見なしています。実際、前述のように、すでに他の方式の監査を開始しています。

これらの2つの論文で説明されている攻撃は、これまでに発見された中で最も強力な攻撃です。米国政府および業界のリーダーとの協議期間を経て、これらを共有しています。しかし、ますます強力な暗号解読結果を開発するにつれて、言語モデルが攻撃が実際に実世界に即時的な影響を与える暗号システムで脆弱性を発見した場合、研究者はどのように対応すべきかを検討することは賢明でしょう。この質問に答えるには、学界、政府、および業界からのインプットが必要になると考えています。この作業がこれらの議論を開始するのに役立つことを願っています。

暗号コミュニティは常に敵対的なレビューから恩恵を受けてきました。暗号方式が提案され、調査され、コミュニティがそのセキュリティに満足するまで改訂されます。長期的には、言語モデルがこのプロセスで重要な役割を果たし、より強力なレビュー、より安全なアルゴリズム、そして最終的には世界のために、より良いセキュリティにつながると期待しています。

完全な研究論文へのリンク

HAWKに関する完全な論文を読む。

AESに関する完全な論文と、関連する思考プロセスを読む。

CryptanalysisBenchを紹介する論文を読む。

編集 7月29日: 学術的所属を更新しました。