Google DeepMindは、人間の監督下で動作するAIエージェントが、1024ビットRSA暗号システムへの攻撃コストを下げる2つの手法を発見したと発表しました。
カリフォルニア大学サンディエゴ校およびInriaの暗号研究者と共同で実施した今回の研究により、旧式のRSA-1024に対する攻撃は、従来の想定より少ない計算量で実行できることが示されました。
「実際には、今回の成果が影響するのは時代遅れの1024ビットRSAシステムだけです。ほぼ例外なく2048ビット以上の鍵を使う現代の暗号化プロトコルは、引き続き安全です」。Google DeepMindのVPで、Google Cloudのチーフサイエンティストを務めるPushmeet Kohli氏はこう述べています。
1つ目の発見は、デジタル署名とパディングに関するものです。パディングとは、多くの署名規格がメッセージを固定のブロックサイズに揃えるために付加する、あらかじめ決められたデータを指します。パディングが偽造を難しくすることは知られていましたが、署名対象を攻撃者が選べる場合にどこまで有効かは、はっきりしていませんでした。
DeepMindは、その有効性が、署名対象ブロックのうち攻撃者が制御できる割合によって決まると突き止めました。「攻撃者がブロックのおよそ半分以上を制御できる場合、パディングはまったく防御になりません」と、Kohli氏は説明しています。
併せて公開された論文によると、この結果は、ハードウェアセキュリティモジュール（HSM）など暗号デバイスのPKCS#11署名インターフェースが使用するPKCS#1 v1.5形式に当てはまります。
サンドボックス環境でのテストでは、エージェントが同じ1024ビット鍵を対象に、過去の学術的な偽造攻撃を再実行しました。その結果、CPU時間は3.5分の1に削減されました。最初の偽造に要したのは391 CPUコア年で、元の研究の1,380 CPUコア年を大きく下回ります。
2つのAIエージェントは、偽造計算の設計、実行、デバッグを4日足らずで完了しました。人間の研究者とのやり取りは約20通のメッセージで、大半は承認でした。なお、鍵の素因数分解には成功していません。素因数分解には、50万〜100万コア年が必要と推定されています。
攻撃者が制御できるブロックの割合が小さい場合（32バイトのハッシュなど）は、偽造がより難しくなります。それでもDeepMindは、理論上の見積もりで、1024ビット鍵に対する従来の最良手法の約1,600倍優れたアルゴリズムを見いだしました。
2つ目の発見は、同じサイズの多数のRSA鍵を素因数分解するケースに関するものです。この場合、攻撃者は最初に行う大規模な計算のコストを、すべての鍵で分担できます。
DeepMindのエージェントが考案したアルゴリズムを使うと、1024ビット鍵を1つ追加で素因数分解するコストが、従来の最良手法と比べて平均で約30分の1になります。ただし、この理論的な見積もりは、鍵1つを素因数分解するのと同程度のコストがかかる初期計算を前提としています。また、この手法は実装されていません。
研究者らは、署名攻撃では秘密鍵を復元できないと指摘しています。攻撃には事前に約40億回の署名クエリが必要で、メッセージを内部でハッシュするデバイスには通用しません。
「これらの成果は、AIが数学と計算を変える新時代において、暗号の困難性を固定的な前提として扱えないことを示しています。AIを使ってこれまでの前提を厳密に検証していくことが、現代の暗号の安全性を保つことにつながります」とKohli氏は述べています。
翻訳元: https://www.securityweek.com/google-deepminds-ai-agents-make-1024-bit-rsa-keys-cheaper-to-attack/
