多数のゼロを含むRSA鍵の因数分解

新たなカテゴリーの弱いRSA鍵——大量のゼロを含む鍵——に関する興味深い研究が発表されました。こうした鍵が実環境に実際に存在することも明らかになっています。

badkeysプロジェクトは、公開鍵に既知の脆弱性がないかチェックするオープンソースのサービスです。このツールの開発過程で、Hannoは証明書透明性（CT）ログ、インターネット全域のTLS・SSHスキャン、PGP鍵など、さまざまな公開ソースから膨大な数の実世界の鍵を収集しました。このデータセットから予想外にスパースなRSAモジュラスを検索したところ、図1に示すパターンを持つ多数の鍵が実環境に存在することを発見しました。

いずれのパターンにも、ランダムに見えるデータの間に、規則的な間隔でゼロのブロックが複数挿入されています。パターン1は、YahooやVerizonを含む複数の大規模組織に発行された証明書のCTログや、NetAppソフトウェアを実行する一部のデバイスで確認されました。これらの証明書はすでに有効期限が切れていますが、調査結果は各社と共有しました。どの製品がこのような鍵を生成した原因なのかを特定しようと試みましたが、回答は得られませんでした。パターン2はEnterpriseDTのCompleteFTPソフトウェアを実行しているSSHホストで確認されました。この脆弱性は、バージョン10.0.0­12.0.0（2016年12月～2019年3月）で生成されたRSA鍵と、バージョン10.0.0­23.0.4（2016年12月～2023年12月）で生成されたDSA鍵に影響します。

これらの脆弱性が影響を与えるホストはインターネット全体のごく一部にとどまりますが、より重要な示唆は、独立して実装された暗号システムが同様の形で失敗しているという点です。他の実装にも同じバグが含まれている可能性があり、この特定の失敗パターンに特化した暗号解析アルゴリズムを整備することには十分な意義があります。

記事自体は推測を避けていますが、私なりの見解を述べたいと思います。これは、私が2013年に書いたような、意図的に設計されたバックドアである可能性があります。何らかの政府機関がこのクラスのRSA鍵を解読する手法を見つけ出し、さまざまなプロバイダーを説得してユーザーに配布させた——そう考えることもできます。