RSA署名を因数分解なしで偽造、1024-bitで1380コア年
Forging 1024-bit RSA signatures in nearly SNFS time [pdf]
RSAの安全性は因数分解の困難さに基づくとされるが、Jouxらが2007年に提案した攻撃を1024-bit RSAで実装。署名オラクルへの一時的アクセス後、因数分解せずに任意の署名を偽造できる。総計算量は1380 CPUコア年、オラクルクエリは2^32回。事前計算後は180コア年でオフライン偽造が可能。HSMをブラックボックス利用して鍵を抽出せずに成りすませた。RSAの実効セキュリティは因数分解ベースの推定より15〜30ビット低く、4096-bitでも128-bit安全ではない。
我々の攻撃は、一時的なオラクルアクセスと、法を因数分解するよりもはるかに控えめな計算リソースによって、攻撃者にその鍵ペアの任意の署名をオフラインで永久に偽造する能力を与える。
HNでの議論
15- tptacek
この研究について知っておくべき最も重要な点は、素晴らしいものではあるが、生のRSAオラクルへのアクセスに依存しているということだ。つまり、公開鍵と、対応する鍵で直接RSA演算を行えるAPIがある状況だ。アイデアとしては、その後オラクルへのアクセス、ひいては秘密鍵へのアクセスを失うが、オラクルとのセッションから将来の偽造に十分な情報を得ているというものだ。
したがって、単純な汎用のRSA-1024署名破りではなく、かなり状況依存だ。論文では（セクション5で）、実際のシナリオでそうした状況がどのように生じ得るかを詳しく述べている。
- nk_kolja
genericなmoduliや署名に対するsnfsアルゴリズムのことは知らなかった。とても素晴らしい。
理論的な結果は純粋に2007年のJouxらの論文によるものだ。
新しいのは実装と1024-bit rsa署名の偽造だ。
またAIは使っていないので、近いうちに高速化が期待できる。
今年rsaがこんなに狙われるとは本当に思っていなかった。これらの結果がアルゴリズムの改善に取り組む人々の動機付けになることを願っている！
- benmmurphy
論文の最後に素敵な詩がある