9月24日、Ars Technicaが「There's a new way to break RSA that's faster than anything we've seen before」と題した記事を公開した。RSAのブラインド署名実装に対し、従来の安全性見積もりを大幅に下回るコストで署名偽造が可能な新手法が発表された。現時点では「直ちに危険」ではないが、暗号コミュニティが長年よりどころにしてきた安全性の前提が根底から崩された点で、インパクトは小さくない。
研究を主導したのはNadia Heninger（UCSDほか）らのチームだ。今回の発見が衝撃的なのは、量子コンピュータでも特殊なハードウェアでもなく、AIもGPUも使わない手作業の実装で達成された点にある。「これらのツールを活用すれば、セキュリティレベルはほぼ確実にさらに下がる」とHeningerは述べており、今回の数字はある意味で「保守的な上限」にすぎない。
攻撃の核心——ブラインド署名が持つ「オラクル性」
ブラインド署名（Blind Signature）とは、署名者がメッセージの内容を知らないまま署名できる仕組みで、匿名認証などのプライバシー保護技術に広く用いられる。この仕組みには本質的な弱点がある。署名サーバーが「特定のクエリに対してyes/noで応答してしまう」オラクルとして機能してしまう点だ。大量の問い合わせを繰り返すことで、署名者の秘密鍵に関する情報を少しずつ収集できる。
研究チームはこの性質に「Special Number Field Sieve（特殊数体篩法）」を組み合わせた。数体篩法は大きな整数の因数分解に使われる古典的な手法だが、今回はRSA署名のオラクルと組み合わせることで、秘密鍵を直接因数分解するのではなく、署名クエリへの応答パターンから鍵情報を間接的に絞り込むという新しい経路での攻撃を実現した。
数字で見る脅威の規模
従来、1024ビットRSA鍵の因数分解には約2⁸⁰回の演算と50万〜100万CPUコア年が必要とされていた。今回の手法では、ブラインド署名の偽造に必要な演算量が2⁶⁵回・約1,380コア年まで低下した。鍵長ごとのセキュリティレベルをまとめると以下のとおりだ。
| 鍵長 | 従来の安全性レベル（推定） | 今回の攻撃後 |
|---|---|---|
| 1024ビット | 約2⁸⁰ | 2⁶⁵ |
| 2048ビット | 約2¹¹² | 2⁹⁰ |
| 4096ビット | 約2¹⁴⁰ | 2¹¹⁹ |
※従来の安全性レベルはNISTガイドラインに基づく一般的な推定値。今回の攻撃後の数値は研究チームによる試算。
実際に狙われるシステムはどこか
この攻撃が有効なのは、PKCSやPSSパディングを使用しない「テキストブックRSA」のブラインド署名実装に限定される。テキストブックRSAとは、教科書に載るような「素のRSA」であり、現在普及しているRSAの大多数が採用するPKCS#1 v1.5またはRSA-PSSパディングとは異なる。パディングは暗号文にランダム性を加えることでこうした攻撃への耐性を持ち、パディングありの実装に対しては今回の手法は実質的な脅威にならない。
問題となるのは、テキストブックRSAのブラインド署名を実際に使い続けているシステムだ。代表例として挙げられているのがPrivacy Pass——ユーザーが身元を明かさずに認証できるIETF標準プロトコルで、AppleとCloudflareをはじめ多数の組織が採用している。
Privacy Passへの攻撃を成立させるには、攻撃者がサーバーを侵害した上で2⁴³件（約8.8兆件）の署名を生成する必要がある。Heningerはこれを「Cloudflareが公表している1日あたりのネットワークトラフィックと同程度の規模だ」と指摘した。膨大な数に見えるが、大規模サービスのインフラレベルでは現実の範囲内であるという意味だ。多くのPrivacy Pass実装は鍵を定期ローテーションしており、攻撃成功の可能性は大幅に低下するが、完全に排除できるわけではない。
「実用的な脅威は小さい」——それでも意味するものは大きい
論文の著者たちと他の暗号研究者は口をそろえて「現実的な脅威は限定的だ」と強調する。攻撃の前提条件（サーバーの侵害＋大量署名の生成）が揃うケースは現実には少なく、パディングなしのテキストブックRSAを使い続けているシステムも多くはない。
ただし、テキストブックRSAの安全性の見積もりが、誰も想定していなかった形で大幅に引き下げられたという事実は重い。暗号の安全性は「現時点で破られていない」ではなく「現在知られている最良の攻撃に対して十分なコストがかかる」という前提で成立している。その前提が崩れたことは、RSAから離脱する動きをさらに加速させる可能性がある。NISTが推進する耐量子暗号（Post-Quantum Cryptography）標準化は量子コンピュータへの対策として始まったが、今回の研究は「古典的な計算機によるRSA攻撃もまだ進化している」という現実を改めて示した形だ。
詳細はThere's a new way to break RSA that's faster than anything we've seen beforeを参照していただきたい。
