加州大學聖地牙哥分校的研究人員開發了一種改進的RSA演算法攻擊技術，無需分解RSA素數，也無需恢復私鑰，即可偽造數位簽章。據估計，攻擊一個1024位元RSA金鑰所需的運算資源相當於在單一處理器核心上耗費1380年的運算時間。利用該大學現有的集群，研究人員僅用了五個月的時間就確定了產生偽造RSA簽名所需的參數（該實驗未使用AI加速器或GPU，但使用這些設備可以顯著縮短計算時間）。相較之下，傳統的分解方法需要在單一處理器核心上耗費5萬到500萬年的運算時間才能重建一個RSA-1024私鑰。
發動攻擊需要能夠重複發送請求來對攻擊者產生的資料進行簽名，例如，透過存取授權服務或硬體安全模組 (HSM)。要確定 RSA-1024 的參數，只需傳送 232³² 個這樣的請求；而要攻擊 Privacy Pass 協定中使用的 RSA-2048 金鑰，則只需 243⁴³ 個請求。收到簽章資料數組後，便會開始漫長的參數計算過程（RSA-1024 大約需要 265⁶⁵ 次運算）。一旦計算出這些參數，攻擊者就可以為任何資料建立偽造的簽名，每個簽名在單核上大約需要 180 小時的計算時間。
此方法僅適用於加密前未使用格式化或填入的 RSA 簽章。包括 Privacy Pass 協定中使用的盲簽實作在內的所有盲簽實作都容易受到此攻擊。大多數常用的 RSA 實現，包括 PKCS#1v1.5 和 RSA-PSS（用於 TLS 和 SSH），都使用了填充，因此不會受到此攻擊。
RSA 加密是基於將一個大數取模冪的運算。公鑰包含模數和冪。模數由兩個只有私鑰持有者知道的隨機素數產生。本文提出的方法是基於 2007 年發表的一項研究，該研究表明，在不知道秘密因子的情況下，提取加密訊息的根並取公鑰指定的冪，比分解因子本身消耗的資源更少。
研究人員利用一種專門的基於篩選方法的數域方法（SNFS），將破解 RSA-1024 密鑰的複雜度降低到 265 次運算，從而使對現代叢集的實際攻擊成為可能。對於 2048 位元 RSA 金鑰，複雜度估計為 290 運算，理論上大型企業或情報機構可以做到。對於 4096 位元金鑰，複雜度為 2119 次運算，目前在實務上尚無法實現，但低於美國國家安全局 (NSA)、美國國家標準與技術研究院 (NIST) 和歐洲網路與資訊安全局 (ENISA) 建議的最低 2128 次運算的要求。
來源： opennet.ru
