秘密鍵を復元せずに署名を偽造するRSAへの新たな攻撃
RSAの研究者らは、公開法を因数分解することも秘密鍵を復元することもなく、1,380 CPUコア年を使って1024ビットの署名偽造を完了した。
この結果はRSAへの新たな攻撃に衝撃的な見出しを与えるものだが、基礎となるアルゴリズム自体は2007年にさかのぼる。実際の進歩は、理論的手法をフルスケールの計算として実行し切った実装にある。
この区別は重要だ。なぜなら、この攻撃があらゆるRSA導入を破るわけではないからである。標的となるのは、一時的にパディングされていない生のRSA演算へのアクセスを提供するシステムだ。標準化されたエンコーディングを用いる現代的な署名は、実証された攻撃モデルの範囲外にある。
Bruce Schneierによる攻撃評価は、この中心的な逆転を的確に捉えている。これは実在する暗号解析上の成果だが、RSA秘密鍵を抽出するための万能な手法ではない。
RSAへの新たな攻撃で実際に変わったこと
研究者らは、見過ごされてきた2007年のアルゴリズムを、実際の署名対象に対する完了済みの1024ビット署名偽造へと転換した。
Laura Shea、Miro Haller、Adam Suhl、Nadia Heninger、Emmanuel Thoméは、UC San DiegoとInriaが関与する共同研究を通じてこの攻撃を実装した。1024ビットの計算は2026年8月31日に完了した。
チームは9月に論文と関連コードを公開した。公開資料では、この成果をほぼ特別数体ふるい法の時間で実行された署名偽造と説明している。
この名称は、攻撃の漸近的性能を指す。数体ふるい法は、大きな整数の因数分解を含む、難しい数論計算のためのアルゴリズム群である。
一般数体ふるい法、すなわちGNFSは、通常のRSA法を因数分解する既知の古典的手法として最速である。特別数体ふるい法、すなわちSNFSは、対象問題に利用可能な代数的構造がある場合に、より優れた性能を発揮する。
新たな実装は、攻撃の一部を実質的により高速なカテゴリーへ移している。ただし、RSA暗号解析を容易な問題や多項式時間問題に変えたわけではない。
研究者らによると、この計算には1,380 CPUコア年が費やされた。並列処理により、この総作業量は学術計算クラスター上で数か月の実時間へと短縮された。
それでも大規模な取り組みである。しかしチームは、同じ1024ビット法の因数分解には50万から100万CPUコア年が必要になると見積もっている。
これらの見積もりを、普遍的な金銭的コストと直接置き換えることはできない。ハードウェア、ソフトウェア、メモリー、ネットワーク、実装上の選択はいずれも実際の運用費に影響する。
それでも、中心となる技術的成果は明確だ。必要なオラクル条件のもとでは、RSA署名の偽造は、対応する法を因数分解するよりはるかに少ない計算量で可能になりうる。
オラクルとは、攻撃者が選んだ入力に対して暗号操作を実行し、結果を返すシステムである。この場合、攻撃者には生のRSA署名または復号操作への一時的なアクセスが必要となる。
このアクセスが永続する必要はない。公開鍵に結びついた大規模な事前計算を終えると、攻撃者は追加の有効な出力をオフラインで生成できるようになる。
この永続性により、この結果は通常の署名サービス悪用より重要になる。攻撃者は元のオラクルへのアクセスを失った後も、偽造能力を保持できる。
チームの研究者向け解説によれば、この能力は実用上の影響という点で秘密鍵の窃取に似ている。ただし、実際の秘密因子が復元されたことを意味するものではない。
研究者らは実装と中間データも公開した。この透明性により、ほかの暗号研究者は前提条件を再現し、エンジニアリング上の判断を検証し、提案された対策をテストできる。
したがって、今回のニュースとなる出来事は完了した計算である。それを可能にした数学は、約19年前から公開されていた。
2007年のアルゴリズムが今重要になる理由
この実装は新たな数学的近道を導入したわけではないものの、特定の攻撃モデルにおけるRSAの安全性見積もりを変える。
Antoine Joux、David Naccache、Emmanuel Thoméは、基礎となる手法を2007年の論文で説明した。彼らは、RSA数を法とする特定の根の計算が、その数の因数分解より容易になる条件を研究した。
単純化して言えば、RSAは合成数を法とするべき乗を適用する。秘密操作は、秘密鍵を知らなければ計算不能であるべき根を計算する。
2007年の研究は、選択されたオラクル応答が高速な攻撃に十分な構造を明らかにしうることを示した。著者らは、選択的偽造から万能偽造能力までの結果を説明している。
この結果は、攻撃者が通常のRSA公開鍵を受動的に観測するだけで、直ちに署名を偽造できることを意味したわけではない。慎重に構造化された秘密鍵操作への反復的なアクセスが必要だった。
2026年まで、1024ビット規模で完全なプロセスを公に実証した者はいなかった。大規模な暗号解析計算には、論文に記載された計算量の式以上のものが必要となる。
研究者は適切な多項式選択を構築し、関係式を収集し、膨大なデータセットを処理し、疎な線形代数を実行し、最終的な復元を完了しなければならない。小さな非効率も、数か月にわたる作業では増幅されうる。
新チームはこれらの段階を接続し、1024ビットの標的に対して結果を実証した。その実装の多くは、数体ふるい法計算向けの確立されたソフトウェアスイートであるCADO-NFSを基盤としている。
理論と実装のこの違いは、RSAへの新たな攻撃において中心的である。アルゴリズムは既知だったが、実用上の定数とエンジニアリング要件は不確かなままだった。
完了した計算は、これらの未知数を証拠へと変える。偽造と因数分解の計算上の隔たりが、単なる漸近的な好奇心ではないことを示している。
実証された標的について、研究者らは攻撃コストを約2^65回の演算と見積もっている。これを、同等の1024ビットRSA法の因数分解に必要な約2^80の作業量と対比している。
より大きな鍵については、脆弱なオラクルモデルのもとで、2048ビットRSAに対して約2^90、4096ビットRSAに対して約2^119の作業量を見積もっている。
これらのより大規模な攻撃は完了していない。これらは、アルゴリズム、測定された実装性能、予想されるスケーリング挙動から導かれた予測である。
安全性強度はシステムを破るのに必要と見込まれる作業量を測るため、これらの予測は注目に値する。NISTは、Sビットの安全性強度をおおよそ2^S回の基本演算と定義している。
ただし、これらの数値はRSA鍵のあらゆる利用ではなく、露出した構成に適用される。プロトコルのエンコーディング、アクセス制御、レート制限、鍵の有効期間は、いずれも実効的な安全性の一部であり続ける。
比較には文脈も必要だ。2^90の計算は、望ましい理論的マージンを下回るとしても、完了した1024ビット実験よりはるかに困難である。
研究者らは、2^80の計算より約1,000倍の作業量が必要になると述べている。対応する1024ビットの因数分解作業を完了した公的チームはまだ存在しない。
したがって、この結果が圧力をかけるのは現在の本番システムよりもセキュリティモデルである。設計者は、生のRSA操作に対して因数分解が常に最良の攻撃見積もりを与えるとは、もはや想定できない。
この修正は、ハードウェアセキュリティモジュール、ブラインド署名プロトコル、特殊なインターフェースにとって重要である。これらのシステムは、許可できる内容を制限しようとしながら、秘密RSA操作を公開することがある。
周辺プロトコルが必要なオラクルを提供する場合、GNFSだけに基づく鍵長の見積もりは安全性を過大評価しうる。この実装は、設計者がその分析を見直す具体的な理由を与えている。
RSAへの新たな攻撃は鍵復元ではなく偽造である
この攻撃は、選択入力条件下で署名能力を破るが、公開情報からRSA秘密鍵を導出するものではない。
RSA鍵には公開法と公開指数に加え、法の秘密素因数から導かれる秘密値が含まれる。従来の因数分解攻撃は、それらの因子を求めることを目指す。
それらを復元すれば、攻撃者は実際の秘密鍵を得る。その鍵は、プロトコルの詳細に従う範囲で、影響を受けるRSA構成により認可されたあらゆる操作を支援できる。
この署名偽造手法は別の経路をたどる。生のRSAオラクルからの応答を使用し、後の根計算を支えるデータを準備する。
攻撃者はまず、パディングされていない秘密鍵操作を実行するデバイスまたはプロトコルに一時的にアクセスする。攻撃者は特別に選んだ多数の値を送信し、応答を記録する。
その後の事前計算では、数体ふるい法の変種を用いて代数的関係を探す。十分な関係式が収集されると、攻撃者はそれらを組み合わせ、選択した出力を偽造できる。
高価な計算の大部分は公開鍵に依存する。この段階の後、個々の偽造を生成するコストは大幅に低下する。
この結果は、防御側の観点では秘密鍵窃取に似ている可能性がある。権限のない第三者が、正規の公開鍵で検証される署名を生成できるようになるためだ。
それでも、仕組みと範囲は異なる。公開法は因数分解されておらず、秘密指数も必ずしも復元されていない。
この区別はインシデント対応に影響する。影響を受けた鍵を置き換えれば、通常の侵害後と同様、その公開鍵による将来の検証は停止する。
脆弱性評価にも影響する。必要とされる生の署名インターフェースがないシステムは、RSA証明書を使用しているだけで脆弱になるわけではない。
この研究を「RSA鍵」の破綻と呼ぶと、こうした境界が曖昧になりうる。証明書または公開鍵だけから始まる受動的攻撃を示唆しかねない。
実証された攻撃にはさらに多くの条件が必要だ。選択された生のRSA結果を返す対話的なソースと、そのソースが消えるか鍵がローテーションされる前に十分な問い合わせが必要となる。
研究者らの完全版論文は、この貢献をほぼSNFS時間での署名偽造として位置付けている。この表現は、結果と計算量改善の両方を正確に示している。
また、別の一般的な誤解も防ぐ。劣指数時間は、多項式時間、瞬時、あるいは低コストを意味しない。
多項式時間アルゴリズムは、入力サイズの固定べき乗でスケールする。劣指数時間アルゴリズムは多項式時間アルゴリズムより速く増大するが、完全な指数時間アルゴリズムよりは遅い。
SNFSとGNFSはいずれも劣指数時間のカテゴリーに属する。この攻撃が高速なのは、困難な計算を排除するからではなく、定数と構造がより有利だからである。
完了した実験ではGPUではなくCPUが使われた。研究者らは、コード最適化に人工知能を使用しなかったとも述べている。
GPUと追加の実装作業により性能を改善できると、彼らは考えている。これは妥当な研究の方向性だが、この実験で測定された結果ではない。
したがって、劇的なGPU高速化に関する主張は依然として推測の域を出ない。数体ふるい法のワークロードには複数の段階があり、各段階は専用ハードウェアに異なる反応を示す。
実証されたベンチマークは、チームが実際に実装した環境での1,380 CPUコア年である。将来これより低い数値が示されるなら、それは再現可能なコードと完了した測定から得られるべきだ。
これが本稿の主要な緊張関係である。この研究は因数分解に基づく想定を覆す意味のある成果である一方、汎用的なRSA鍵復元手法ではない。
実際の露出範囲は狭いが、ゼロではない
通常のパディング付きRSA署名は実証された攻撃対象ではない一方、raw署名インターフェースは直ちに見直すべきです。
現代のRSA署名では通常、制限のないメッセージに対して秘密指数を直接適用しません。まず、定義済みの署名方式を用いてメッセージダイジェストをエンコードします。
RSASSA-PSSはRSA演算の前にランダム化された形式を加えます。PKCS #1 v1.5は、識別子とパディングを備えた構造化された決定的エンコードを使用します。
こうしたエンコードにより、攻撃者が署名対象として任意の生整数を選ぶことは防がれます。この制約が、新たな実装に必要となるオラクルの挙動を阻止します。
研究チームによれば、PSSまたはPKCS #1 v1.5を使用する一般的なRSA署名に対して、この攻撃は実行可能には見えません。Schneierも実用面では同じ結論に達しています。
つまり、一般的な証明書、TLS認証署名、署名済みソフトウェア、トークンが自動的に危険にさらされるわけではありません。管理者は結論を出す前に、実際のアルゴリズムとインターフェースを確認すべきです。
鍵長だけでは脆弱性の有無は判断できません。raw署名APIの背後にある2048ビット鍵は、検証済みPSS署名に限定された同じ鍵とは異なる露出を持ちます。
最も明確に見直すべき候補は、rawな秘密鍵演算を許可するハードウェアセキュリティモジュールのインターフェースです。アプリケーションは、モジュール外で独自プロトコルを実装するため、このようなアクセスを要求することがあります。
この柔軟性は、モジュールが提供するはずだった境界を弱める可能性があります。秘密鍵がデバイスから出ることはなくても、利用可能な操作が署名オラクルになり得ます。
ブラインド署名は、その目的自体が署名者から隠されたコンテンツへの署名を含むため、より慎重な分析が必要です。クライアントはメッセージを変換し、署名を取得した後、ブラインディング係数を取り除きます。
この設計は、プライバシー保護型認証やデジタルキャッシュの用途を支えます。同時に、クライアントが秘密鍵で処理される値に影響を及ぼすインターフェースも生み出します。
現代のブラインドRSAプロトコルには、エンコードと検証の要件が追加されています。現行のblind-signature standardでは、クライアントが準備したメッセージにRSA-PSSエンコードを用います。
ただし、署名サーバーは依然としてブラインド化された代表値に対してRSA秘密演算を実行します。新たな論文は、このようなインターフェースが発行時に必要なrawオラクルをどのように露出し得るかを分析しています。
Privacy Passは頻繁に引き合いに出されるユースケースです。これは、サービスが発行と後の利用を結び付けずに検証できる匿名トークンを、クライアントが取得できるようにします。
AppleとCloudflareは、プライバシーサービスやチャレンジ回避システムでPrivacy Pass関連技術を利用してきました。とはいえ、それですべての導入環境が悪用可能だと示されるわけではありません。
稼働中のサービスに対する攻撃が成功するには、適切な構成、安定した公開鍵、そして十分な数の受理されるオラクルクエリが必要です。運用上の制御は計算条件を変え得ます。
研究者らは、2048ビットのブラインドRSA鍵を攻撃するには、はるかに大規模なオフライン計算に加え、約2^43回のオラクルクエリが必要だと見積もっています。
このクエリ数は8兆回を超えます。個々の利用者にとっては膨大な数ですが、大規模な分散サービスは、集計規模ではこれに匹敵するトラフィックを処理しています。
レート制限により、1つのアカウント、デバイス、ネットワーク、または認証情報に紐付くリクエストを制限できます。悪用検知によって、異常に反復的な発行パターンを特定することも可能です。
鍵のローテーションは、利用可能な収集期間を短縮します。攻撃者が十分な応答を集める前にサービスがRSA鍵を置き換えれば、それまでのクエリを新しい鍵へ単純に引き継ぐことはできません。
したがって、短い鍵エポックは攻撃者の運用コストを引き上げます。ただし、数学そのものを変えるわけではなく、プロトコルレベルの防御を完全に代替するものでもありません。
研究者らは、中期的にはゼロ知識証明がより強力な対策になり得ると示唆しています。このような証明は、隠されたメッセージを明かさずにクライアント入力を制約できます。
より長いRSA鍵も攻撃コストを増やしますが、論文はこのオラクルモデルにおける安全性余裕に疑問を呈しています。著者らは4096ビットでも128ビット未満の強度と見積もっています。
これは、攻撃者が今すぐ4096ビット署名を偽造できるという意味ではありません。2^119という見積もりは、完了した1024ビットの計算をなお大きく上回ります。
ただし、プロトコル設計者は、より大きな鍵だけを唯一の長期的な答えと見なすべきではないことを意味します。脆弱なインターフェースは、より高いコストで同じ構造的問題を残し得ます。
大半の組織にとって、適切な対応は緊急停止ではなく棚卸しです。セキュリティチームはRSA鍵を特定し、許可されているすべての秘密鍵操作を把握すべきです。
暗号化、通常の署名、ブラインド署名、証明書発行、トークン署名、独自のHSM呼び出しを区別する必要があります。各経路は異なる攻撃面を露出します。
チームは、アプリケーションが汎用的なモジュラーべき乗演算ではなく、名前付きの署名メカニズムを要求していることを確認すべきです。また、署名済みオブジェクトを受け入れる前に、不正なエンコードを拒否する必要があります。
現行のNIST key-management guidanceでは、1024ビットRSAは現代の保護要件に対してすでに時代遅れと見なされています。この実験は、残存する導入環境を撤廃すべき理由をさらに一つ加えます。
1024ビットのraw署名サービスには緊急の是正が必要です。標準的な2048ビットPSS導入環境は同じ即時の指摘には該当しませんが、より広範な移行計画は依然として重要です。
防御側が次に注視すべきこと
次の3つのシグナルは、独立した再現、プロトコル固有の分析、実装における測定可能な変更です。
まず、暗号学者は1024ビット計算を独立して再現し、論文のスケーリング見積もりを検証すべきです。再現により、報告されたコストに重要なすべての段階が含まれているかを検証できます。
また、予測を強める、あるいは弱める実装上のボトルネックも明らかになる可能性があります。再現可能なコストが低ければ、露出したraw署名インターフェースへの懸念は高まります。
実質的により高いコストが判明しても、概念上の結果が消えるわけではありません。運用上の脅威は限定され、より大きな鍵に関する見積もりの緊急性は下がります。
次に、標準化団体とプロトコル設計者は、ブラインドRSA構成についての分析を公表すべきです。ブラインディングによって署名者が処理する対象が変わる場合、「パディング」に関する一般論だけでは不十分です。
重要な問いは、具体的なプロトコルが論文で想定されるオラクル応答を攻撃者に与えるかどうかです。クエリ認証と鍵ローテーションも、この評価に含めなければなりません。
Privacy Passの導入環境は、プライバシー目標、繰り返されるトークン発行、広く分散したクライアントを組み合わせるため、特に注意を要します。公開設計レビューは、理論上の露出と到達可能な攻撃を切り分けることができます。
より強力な入力証明を要求するプロトコル改訂は、研究者らの警告を裏付けるでしょう。一般的な導入環境が必要なオラクルを拒否するという説得力ある証明があれば、この結果の実用的な範囲は狭まります。
第三に、防御側はHSMベンダーと暗号ライブラリに注目すべきです。ドキュメント、APIのデフォルト、監査規則、非推奨通知は、業界がこの知見をどう解釈しているかを示します。
HSMは鍵素材を保護しながらも、危険な操作を露出することがあります。ベンダーはraw RSA呼び出しを制限し、クエリ制御を追加し、またはメカニズム固有のインターフェースを推奨する可能性があります。
ライブラリ保守者も低レベルAPIを厳格化する可能性があります。rawな秘密指数べき乗演算を非推奨にすれば、開発者が露出した署名オラクルを誤って構築する可能性を減らせます。
これらのシグナルのいずれも、すべてのRSA証明書を直ちに放棄する必要性を意味しません。実証された攻撃は、受動的な観測を通じて標準化されたパディング付き署名には到達しません。
RSAは、暗号学的に意味のある量子コンピュータという別の長期的問題にも直面しています。耐量子移行プログラムはすでに、組織がレガシーアルゴリズムへの依存を減らす機会を与えています。
NISTは2024年に最初の耐量子署名アルゴリズムを標準化しました。それでも、証明書、ハードウェア、プロトコル、運用ツールを一体で変更する必要があるため、移行には数年を要します。
この新たな攻撃は、システム全体を再設計せずにアルゴリズムを置き換えられる暗号アジリティの計画を後押しします。互換性テストを省略したり、影響を受けないシステムを緊急変更したりする根拠にはなりません。
セキュリティ責任者は、今すぐ4つの具体的な問いを投げかけるべきです。1024ビットRSAをまだ使用しているサービス、rawな秘密鍵操作を露出しているサービス、ブラインドRSAを実装しているサービス、または1つの鍵を異常に長期間保持しているサービスはありますか。
「はい」であれば、プロトコルレビュー、ログ分析、移行スケジュールを開始すべきです。すでに秘密鍵が抽出されたという根拠のない主張を招くべきではありません。
The New Attack Against RSAが重要なのは、古い理論的警告を完了済みの計算へと置き換えた点です。その実用的な境界も同じく重要です。
この結果を、暗号学上の前提とインターフェース設計を検証する試験として扱ってください。自社システムがどの操作を露出しているかを確認し、その後、対応を決める前に再現結果とプロトコル固有の知見を追跡してください。
