Desmedt 和 Odlyzko 的 RSA 簽名攻擊實用嗎？
我想了解 Desmedt 和 Odlyzko 對 RSA 簽名（以及後續工作）的攻擊如何變得實用。此攻擊描述了一種使用高斯消元法在新消息上偽造簽名的方法。問題是在應用私有指數之前對消息進行了雜湊處理，所以我可能遺漏了一些東西……為什麼這種攻擊實用？
謝謝你。
TL;DR：是的，在狹窄的或某些特定的確定性 RSA 填充上，不得使用。
對 RSA 簽名的 Desmedt 和 Odlyzko 攻擊
$$ DO1985 $$假設一個帶有附錄的確定性 RSA 簽名方案，對於 RSA 密鑰 $ (N,e,d) $ , 簽署消息 $ M $ 帶簽名 $ S=(H(M))^d\bmod N $ 對於一些公共功能 $ H $ 和 $ H(M)<2^k $ 和 $ k\ll\log_2(N) $ ，並驗證所謂的簽名 $ S $ 通過檢查 $ S^e\bmod N $ 火柴 $ H(M) $ . 該攻擊在計算上是可行的 $ H $ 一個 $ k $ -bit 加密雜湊，至少達到 $ k=200 $ $$ CNST2016 $$，我相信 $ k=256 $ ，也許更多。的大小 $ N $ 和 $ e $ 幾乎無關緊要。 攻擊計算消息的簽名 $ M_0 $ 由對手從許多其他消息的簽名中選擇 $ M_i $ 由對手選擇，以及公鑰 $ (N,e) $ . 所有這些消息必須服從一個約束：平滑；也就是說，它們的所有質因數都低於“平滑度”界限（可能除了與其他人共享的兩個較大的質因數之一 $ M_{i’} $ , $ i’\ne i $ （攻擊的這些大素數和兩個大素數變體與MPQS中的類似變體平行，請參閱
$$ LM1990 $$用於地標$$ AGLL1994 $$).
基本攻擊梳理了許多消息 $ M $ 找到這些 $ H(M) $ 其所有質因數均低於界限 $ B $ , 並形成一個大的稀疏矩陣，每個這樣的一行都有一行 $ M_i $ , 每個素數一列 $ p_j $ 以下 $ B $ ,素數的多重性 $ p_j $ 在 $ H(M_i) $ 在十字路口 $ c_{i,j} $ ，並且行數明顯多於列數。
通過高斯消元法或同樣效果的方法，找到係數 $ u_i\in\mathbb Z $ 對於每一行，這樣 $ \forall j,;0=\displaystyle\sum_{i\ge0}u_i,c_{i,j} $ ， 和 $ u_0=-1 $ . 它遵循 $ \displaystyle\prod_{u_i<0}H(M_i)^{-u_i};=;\prod_{u_i>0}H(M_i)^{u_i} $ ， 因此 $ H(M_0)\equiv\displaystyle\prod_{u_i\ne0,,i>0}H(M_i)^{u_i}\pmod N $ .
通過提高後者的權力 $ d $ , 簽名 $ S_0 $ 的 $ M_0 $ 可以從簽名中獲得 $ S_i $ 其他一些 $ M_i $ ， 作為
$$ S_0\equiv\prod_{(u_i\bmod e)\ne0,,i>0}S_i^{u_i};;\prod_{(u_i\bmod e)=0,,u_i\ne0}H(M_i)^{u_i/e}\pmod N $$ 高斯消元可以直接減少 $ S_i $ 需要以需要更多平滑為代價；這對小型企業來說更容易 $ e $ .
該攻擊是一種存在性偽造，但如果使用狹窄的確定性 RSA 簽名填充（與所有嚴格的安全準則相反），則可能完全實用。考慮一個假設的自動文件時間戳伺服器，它在接收到文件後使用 SHA-384 對其進行雜湊處理，然後使用 SHA-384 生成和簽名 $ S=(\operatorname{SHA-256}(M))^d\bmod N $ 一個消息 $ M $ 形式：
At 2017-09-21 09:12Z I received a file which SHA-384 hash in base64 is RpzByokphjFifbPgFhR2vFnqbHvqA283Ud8sN0ic61fxd5hyQdXo3VofgkrSb0fz對手想要某個文件向後加時間戳。她：
- 搜尋該文件的合適的過去日期和/或同樣有用的變體，以便消息 $ M_0 $ 伺服器將為該（該變體）文件生成的文件具有平滑的 SHA-256。
- 生成許多小文件/未來日期對，以便生成 $ M_i $ 具有平滑的 SHA-256。
- 進行 Desmedt 和 Odlyzko 攻擊的高斯消除類固醇部分，產生原始的子集 $ M_i $ 她需要簽名。
- 通過在適當的分鐘開始時詢問適當的小文件的時間戳來獲得他們的簽名。
- 成功！簽名為 $ M_0 $ 可以從上一步獲得的簽名中計算出來，並進行身份驗證 $ M_0 $ 作為伺服器沒有也不會產生的後向時間戳。
注意：攻擊不需要計算任何雜湊原像或發現任何衝突：所有 $ M_i $ 包含 $ M_0 $ 從它們相關的文件和日期確定，然後使用 SHA-256 進行散列，然後測試此散列的平滑度。
該攻擊需要相對較少的 SHA-384 計算，但需要許多 SHA-256 計算和快速測試它們是否平滑的方法（平滑很少見）。我相信大部分的計算工作都在那裡。
如果出現以下任一情況，攻擊就會被阻止：
- 散列很寬，理想情況下與 $ N $ 是; 這是RSA-FDH的確切策略，也被 RSASSA-PSS 使用，並且（以一種混蛋和偶爾失敗的方式）被 ad-hoc RSA 簽名方案使用。
- 簽名者在其簽名的內容中插入了一些不可預測的內容；這是機率簽名方案的策略，例如 RSASSA-PSS 和ISO/IEC 9796-2方案 2，以及它們的去隨機化變體。這也被一些負責任的證書頒發機構使用，當使用諸如 RSASSA-PKCS1-v1_5 之類的臨時 RSA 填充或像 SHA-1 之類的不太理想的散列時，它們會生成一個隨機或不可預測的證書序列號。
Desmedt 和 Odlyzko 襲擊
$$ DO1985 $$是對廣泛確定性 RSA 簽名填充的其他攻擊的子組件，包括第一次中斷$$ CHJ1999 $$（撤回的）ISO/IEC 9796:1991和中斷$$ CNST2016 $$ISO/IEC 9796-2方案 1 （又名 1997）。
參考：
- $$ DO1985 $$: Yvo Desmedt 和 Andrew M. Odlyzko；對 RSA 密碼系統和一些離散對數方案的選擇文本攻擊，在Crypto 1985 的程序中。
- $$ LM1990 $$: Arjen K. Lenstra, Mark S. Manasse; 在EuroCrypt 1990 的程序中使用兩個大素數進行因式分解。
- $$ AGLL1994 $$: Derek Atkins, Michael Graff, Arjen K. Lenstra, Paul C. Leyland；神奇的詞是 squeamish ossifrage，在AsiaCrypt 1994的會議記錄中。
- $$ CHJ1999 $$: Don Coppersmith, Shai Halevi, Charanjit Jutla；ISO 9796-1 和新的偽造策略，作為IEEE P1363 研究貢獻，1999 年分發。
- $$ CNST2016 $$：Jean-Sebastien Coron、David Naccache、Mehdi Tibouchi、Ralf-Philipp Weinmann： 《密碼學雜誌》中 ISO/IEC 9796-2 和 EMV 簽名的實用密碼分析，2016 年（ Crypto 2009 論文集的第一版）；第 3 節對應用於 RSA 簽名的 Desmedt 和 Odlyzko 攻擊進行了現代闡述。