米カリフォルニア大学サンディエゴ校と仏Inriaの研究チームが、1024ビットRSAの署名を、秘密鍵の素因数を求めることなく偽造する大規模計算に成功した。
ただし、攻撃には、秘密鍵を使ってパディング処理前のRSA演算を行わせ、その結果を一時的に大量取得できることが条件となる。いったん必要な情報を集めれば、その後HSMなど秘密鍵を保持する装置へアクセスできなくなっても、同じ鍵による新たな署名を自力で生成できる。
これは2007年に提案された攻撃手法を実際に1024ビットRSAへ適用した成果であり、通常使われているRSA署名を誰でも破れるようになったという話ではない。
それでも、「秘密鍵を装置の外へ出さなければ、署名する能力も外へ持ち出されない」という設計上の前提を見直す材料にはなる。
5カ月、1,380コア年を使って何を実証したのか
Laura Shea氏、Nadia Heninger氏ら5人による論文「Forging 1024-bit RSA signatures in nearly SNFS time」は、9月20日付のプレプリントとして公開された。現時点では査読前の研究成果だ。
著者らは攻撃に使った実装も公開している。研究チームの説明によると、1024ビットRSAに対する計算は8月31日に完了した。
実証にかかった期間は約5カ月。使用した計算量の合計は1,380 CPUコア年だった。
「コア年」は、CPUコア1基を1年間連続して使った場合に相当する計算量を表す。実際には多数のCPUで並列処理しているため、1,380年間計算を続けたという意味ではない。また論文では仮想CPUコアを基準に集計しており、物理CPUのコア数ともそのまま対応しない。
内訳を見ると、対象となる公開鍵について事前に行う計算に約1,200コア年を使った。
さらに、同じ秘密鍵に対して約2^32回、つまり約43億回のRSA秘密鍵演算を問い合わせた。その結果を使い、後から選んだメッセージに対する署名をオフラインで1件生成するために、さらに約180コア年を要した。
秘密鍵演算への問い合わせには、鍵を内部に保持したまま暗号処理を行うハードウェアセキュリティモジュール（HSM）が使われた。
この実験は、準備さえ終われば署名を瞬時に大量生成できることを示したものではない。 新しい署名を偽造するたびに、なお相当量の計算が必要になる。
重要なのは、必要な照会を終えた後はHSMへ再び問い合わせる必要がない点だ。
秘密鍵そのものを装置から抜き出したわけではない。それでも、HSMへのアクセスを失った後に、同じ秘密鍵で検証できる署名を新たに作れるようになった。
研究チームは比較のため、1024ビットRSAを通常の方法で素因数分解するには50万〜100万CPUコア年程度が必要になるとの見積もりを挙げている。
今回の1,380コア年はそれを大幅に下回る。ただし、両者を同じハードウェアと条件で実測した比較ではないうえ、今回の攻撃には秘密鍵演算へ大量に問い合わせられるという追加条件がある。
2007年の手法で、素因数分解を避ける
RSAの公開鍵には、二つの大きな素数を掛け合わせて作った整数が含まれている。
この整数を素因数分解できれば秘密鍵を導き出せるため、RSAの安全性は一般に、最も高速な素因数分解アルゴリズムの一つである一般数体ふるい法（GNFS）に必要な計算量を基準に評価されてきた。
今回の研究が利用したのは、Antoine Joux氏、David Naccache氏、Emmanuel Thomé氏が2007年に提案した別の攻撃手法だ。
研究チームは数体ふるい法の計算ソフトウェア「CADO-NFS」を拡張し、これまで公開実装がなかった攻撃を実際の1024ビットRSA鍵に対して動作させた。
今回の新しさは、理論上知られていた攻撃経路を、実際に必要な計算資源や処理時間まで示せる規模で実証したことにある。
この攻撃では、攻撃者が指定した数に対してRSAの秘密鍵演算を行い、その結果を返してくれる機能が必要になる。暗号研究では、こうした機能を「署名オラクル」と呼ぶ。
ただし、一般的な署名APIそのものがあればよいわけではない。
通常のRSA署名では、メッセージのハッシュ値をPKCS#1 v1.5やRSA-PSSといった規則に従って符号化し、その後に秘密鍵演算を行う。
今回必要なのは、こうしたパディングや形式チェックを署名装置側で行わず、攻撃者が選んだ値そのものに秘密鍵演算を適用して結果を返す機能だ。
研究チームは、そこから得られた大量の応答と、事前計算で集めた数論的な関係を組み合わせることで、RSAの法となる整数を素因数分解することなく、後から指定した対象への署名を計算できるようにした。
計算量は、特殊な形を持つ整数の素因数分解に使われる「特殊数体ふるい法（SNFS）」に近い水準まで下がる。ただし、攻撃対象となるRSA鍵そのものがSNFS向けの特殊な形を持っている必要はない。
もちろん、計算量が小さな多項式時間になったわけではない。依然として非常に大きな計算資源を必要とする準指数時間の攻撃だ。
また、公開鍵を入手しただけで実行できる攻撃でもない。
そもそも、RSAの秘密鍵演算を逆算することと、公開鍵の法を素因数分解することが数学的に同じ難しさであるとは、一般には証明されていない。今回の結果は、その間に存在する別の攻撃経路を実際の規模で示したものといえる。
PSSを使っていても違いが出る、通常署名とブラインド署名
通常のRSA署名では、署名する側がPKCS#1 v1.5やRSA-PSSの規則に従って入力を整え、その後に秘密鍵演算を行う。
研究者らは、このような一般的な利用方法では、今回の攻撃に必要な署名オラクルが提供されないため、通常のRSA署名に対する実用的な攻撃にはならないと説明している。
一方、署名する側に内容を見せずに署名を受け取る「ブラインド署名」では事情が異なる。
RFC 9474で定められた方式では、署名を依頼するクライアント側がRSA-PSSの符号化を行ったうえで値をブラインド化し、内容が分からない状態でサーバーへ送る。
サーバーは、その値に対して秘密鍵演算を行う。クライアントが後からブラインド化を解除すると、通常のRSA-PSS署名として検証できる署名が得られる。
つまり、RSA-PSSを使っているかどうかだけでは、今回の攻撃が成立するかは決まらない。
重要なのは、秘密鍵を持つ側が入力の内容や形式を確認せず、利用者が選んだ値に対してRSA秘密鍵演算を行うかどうかだ。
| 利用形態 | 秘密鍵演算へ渡される入力 | 今回の攻撃条件との関係 |
|---|---|---|
| 通常のPKCS#1 v1.5／RSA-PSS署名 | 署名側が規定の形式へ符号化した値 | 通常の署名APIからは必要なオラクルを利用できない |
| HSMのraw RSA API | 呼び出し側が選んだ値 | 利用権限と十分な回数の照会が得られれば条件を満たす |
| Privacy Passの公開検証型 | クライアントが符号化・ブラインド化した値 | ブラインドRSA署名のため、攻撃モデルの条件に合う |
| Privacy Passの非公開検証型 | RSAとは異なるVOPRF方式の入力 | 今回のRSA攻撃の対象外 |
この表は、論文第7節に記された攻撃条件を、RFC 9474の第4節・第7.2節と、Privacy Passを定めるRFC 9578の第5〜6節に照らして整理したものだ。
Privacy Passには、トークンの発行者だけが検証できる方式と、公開鍵を使って誰でも検証できる方式がある。後者では2048ビットのブラインドRSAが利用される。
最終的な署名がRSA-PSSとして検証できることと、署名サーバーが任意の入力に対するRSA秘密鍵演算を提供するかどうかは、別の問題だ。
また、この分類は、各方式が研究上の攻撃モデルに当てはまるかどうかを整理したものであり、実際のサービスで攻撃が成功したという意味ではない。
攻撃には同じ鍵への大量の問い合わせと、大規模な事前計算が必要になる。
さらに、RSAを使っていない方式が今回の攻撃対象外だからといって、その方式の安全性全般が保証されるわけでもない。
2048ビット以上は、実証ではなく計算上の推定
研究チームは、1024ビットRSAで得た実測結果をもとに、より長いRSA鍵に対して同じ攻撃を行った場合の計算量も推定している。
論文第6節と図7で示された比較は次の通りだ。
| RSA鍵長 | 素因数分解を基準にした安全性 | 今回の攻撃モデルで推定される安全性 | 必要な照会回数 |
|---|---|---|---|
| 1024ビット | 80ビット | 約65ビット | 約2^32回 |
| 2048ビット | 112ビット | 約90ビット | 約2^43回 |
| 3072ビット | 128ビット | 約105ビット | 約2^51回 |
| 4096ビット | 144〜152ビット | 約119ビット | 約2^57回 |
ここでいう安全性の「ビット」はRSA鍵そのものの長さとは異なる。
安全性がbビットであれば、概念的には攻撃に約2^b規模の計算が必要になる、という尺度だ。
1024ビットRSAについては実際に攻撃が行われ、その結果はこの推定とおおむね対応した。一方、2048ビット以上については計算上の外挿であり、研究チームが実際に署名を偽造したわけではない。
著者ら自身も、計算量の式に含まれる定数項や、1024ビットという規模で理論上の漸近的な増え方に十分近づいているかは分からないと認めている。
今回選んだ計算パラメーターが最適だったとも限らない。
そのため、「4096ビットRSAでも128ビット相当の安全性に届かない」という数字は、今回の署名オラクルを利用できるという攻撃条件と、論文で用いた推定方法の下で解釈する必要がある。
2048ビットRSAの場合、計算量の推定は約2^90まで下がる一方、必要な秘密鍵演算への問い合わせ回数は約2^43回、約8.8兆回に達する。
ブラインド署名を実際に攻撃する場合には、対象となる公開鍵を事前に知り、同じ秘密鍵が使われている間にこれだけの応答を集める必要がある。
したがって、1ユーザーあたりの発行回数制限やレート制限、秘密鍵をどの程度の頻度で更新するかといった運用条件が、攻撃の現実性を大きく左右する。
Privacy PassのRSA方式が理論上今回の攻撃モデルに当てはまるからといって、現在の計算資源で直ちに実サービスのトークンを偽造できるという意味ではない。
「従来考えられていた安全性の余裕が小さくなる可能性がある」という研究上の指摘と、「現実のサービスを実際に攻撃できるか」という問題は分けて評価する必要がある。
HSMが秘密鍵を守っても、署名する能力まで守れるとは限らない
HSMは、秘密鍵を装置の外へ出さずに暗号処理や署名を行うために広く利用されている。
今回の実証が示したのは、秘密鍵そのものがHSM内部で安全に保管されていても、利用できる秘密鍵演算の種類によっては、HSMへのアクセスを失った後にも、その鍵で新しい署名を作れる能力が攻撃者に残り得るということだ。
つまり、「秘密鍵を外へ持ち出させないこと」と、「秘密鍵を使ってどのような計算を許可するか」は、別々に設計しなければならない。
例えば、アプリケーション側でRSA署名用のパディング処理を済ませ、HSMには加工済みの値に対するRSA秘密鍵演算だけを任せる構成を考える。
もしアプリケーションが侵害された際、攻撃者が任意の値をHSMへ送り込めるのであれば、秘密鍵そのものを取り出せなくても今回のような攻撃条件に近づく可能性がある。
これは論文が指摘するraw RSA APIの性質から導かれる設計上の問題だ。
したがって、「HSMを使っている」という情報だけでは、今回の攻撃に対して安全かどうかを判断することはできない。HSMがどのAPIを公開し、入力をどこまで検証し、同じ鍵への問い合わせをどの程度許しているかを見る必要がある。
安全性を評価する際には、「何をもって攻撃成功とするか」という違いにも注意が必要だ。
ブラインドRSA署名の安全性で使われる「one-more RSA」という仮定は、n回のRSA秘密鍵演算を問い合わせただけで、それを上回るn＋1個の有効な結果を得ることが難しい、という性質を扱う。
一方、今回の攻撃は大量の問い合わせを行った後、その結果を利用して、後から選んだ対象への新しい署名を作る。
研究チームは「one-more RSAを素因数分解より高速に破った」と主張しているわけではない。むしろ、実際のシステムで守りたい性質と、従来の安全性証明で想定する攻撃モデルとの間にずれがあると指摘している。
著者らがブラインドRSAを運用する事業者に提案している対策は、短期的には秘密鍵の更新頻度を高めること、中期的にはより長いRSA鍵へ移行することだ。
さらに、クライアントが内容を明かすことなく「入力が正しい形式である」と証明するゼロ知識証明を導入することや、将来的には耐量子暗号方式へ移行することも挙げている。
RFC 9474でも、こうした証明を導入できる可能性には触れているが、具体的な方式までは規定していない。
耐量子暗号への移行を機に署名基盤を見直す際には、鍵長や秘密鍵の保管場所だけでなく、秘密鍵を持つ装置がどのような入力を受け付け、何回まで演算を許可するのかも確認する必要がある。
一時的に秘密鍵を使う権限を得た相手が、その権限を失った後にも何らかの署名能力を持ち続けられるのか。
今回の実証は、その問いをRSAの運用設計に突きつけた成果といえる。
