RSS トレイル・オブ・ビッツ ブログ
フォロー
多項式を用いた「ショートスリーブ」RSA鍵の因数分解
研究者たちは、一部のRSA秘密鍵には0に強く偏ったビットが存在し、それを検出し迅速に素因数分解できることを発見しました。badkeysプロジェクトのHanno Böck氏と共に、彼らはこの特性を持つ数百のユニークな鍵を発見し、過去のデータを分析してこの問題を時系列で追跡しました。これらの鍵における0ビットのパターンはしばしば高度に構造化されており、パターンを悪用するための多項式ベースの暗号解読技術の開発を可能にしました。研究者たちは、繰り返し現れる0ビットブロックを持つRSAモジュラスの2つのパターンを特定しました。一方のパターンは未解明のままで、もう一方はCompleteFTPファイル転送ソフトウェアの古いバージョンのbig-integerコードにおける型不一致に起因することが判明しました。CompleteFTPのバグは脆弱な短袖DSA鍵も生成し、研究者たちはインターネットスキャンから603のユニークなRSA秘密鍵と74のDSA鍵を回収しました。badkeysプロジェクトは、既知の脆弱性について公開鍵をチェックするオープンソースサービスであり、実世界の鍵のデータセットを検索することで、研究者たちは実際に多数の鍵にこれらのパターンが存在することを発見しました。研究者たちはCompleteFTPの脆弱性をリバースエンジニアリングし、それが肢のサイズとRNG出力のサイズの不一致によって引き起こされたことを発見しました。この脆弱性は、CompleteFTPチームが脆弱な鍵を自動的にチェックし、鍵の再生成が必要な場合にユーザーに警告するアップデートをリリースした後に封じ込められました。研究者たちはまた、整数を多項式として表現することによって整数を素因数分解する技術を開発しました。これは一般的なRSAモジュラスを素因数分解するために使用できます。これらの脆弱性の発見は、実践的な研究の重要性と、潜在的な弱点を特定し対処するために暗号実装の継続的な監視の必要性を浮き彫りにしています。
