UCSDのHeninger教授ら、因数分解なしでRSA署名を偽造する新攻撃

カリフォルニア大学サンディエゴ校（UCSD）のNadia Heninger教授を筆頭著者とする研究チームが、古典コンピューターだけでRSAの安全性を大きく引き下げる新たな攻撃手法を発表した。米Ars Technicaが伝えた。鍵を割り出すのではなく、署名を偽造するというアプローチで、暗号研究者の間に驚きが広がっている。

これまでRSAの正当な署名を作るには、まず大きな整数を因数分解して秘密鍵を得る必要があると考えられてきた。Heninger教授によれば、1024ビット鍵でも1本あたり数千万ドル規模の計算が必要で、2048ビットは手が届かないとされていた。今回の手法では、1024ビット鍵に対する署名偽造が学術用のCPUクラスターで数カ月、約1380コア年で完了した。因数分解に必要とされる50万〜100万コア年と比べ、桁違いに少ない。2048ビット、4096ビットの鍵についても、各国機関が求める128ビット相当の安全性を下回る水準まで下がるという。チームはAIやGPUを使わず手作業でコードを書いており、それらを使えばさらに下がる可能性が「ほぼ確実」だとしている。

技術的には、2007年に示された数体ふるい法の変種「特殊数体ふるい」を、問い合わせにyes/noで答える「オラクル」に対して適用する。大量の問い合わせで情報を集め、署名を組み立てる仕組みだ。このため、平文にデータを加えるPKCSやPSSのパディングを使う実装ではオラクルが存在せず、攻撃は成り立たない。現在使われているRSAの大半はこれらのパディングを採用している。

影響を受けうるのは、パディングを使わない「ブラインド署名（教科書的RSA）」を使う仕組みだ。代表例は、身元を明かさずに認証するプロトコル「Privacy Pass」で、AppleやCloudflareなどが利用している。攻撃にはサーバー側を掌握したうえで大量の署名を生成させる必要があり、教授はその量がCloudflareが1日に処理すると公表している通信量と同程度だと説明する。多くの実装は鍵を定期的に更新しており、リスクは大きく下がるが、ゼロになるわけではない。

AllurityのKarsten Nohl氏は「査読で結果が確認されれば概念上の大発見だ」と評価する。研究者らは現実の脅威は小さいと強調するが、RSAの安全性は因数分解の難しさに等しいという前提が崩れたことの意味は大きい。量子計算機への備えとして進む耐量子暗号への移行を、さらに急ぐ理由が加わった形だ。