對“額外”蒙哥馬利減少的 RSA 時序攻擊
在“時間攻擊的實際實現”中，作者利用了時間差異，這種時間差異源於以蒙哥馬利形式相乘時發生的“額外減少”。在實現了這個攻擊的玩具範例之後，我想我明白了。我創建了兩組消息，一組包含消息 $ m $ 在哪裡 $ m^3 $ 不需要額外減少（ $ M1 $ ) 和另一組 $ m^3 $ 確實需要額外減少（ $ M2 $ ）。然後我增加了一個平方和乘法算法，以利用蒙哥馬利乘法，同時跟踪在求冪過程中發生的額外減少的數量。
這個快速的實驗似乎確實表明，其中的集合 $ m^3 $ 不需要額外減少（ $ M1 $ ) 平均而言，額外減少的次數會少於另一組。然而，這兩個平均值的差異將遠大於一個。大多數論文似乎表明他們利用的時間攻擊依賴於時間差異一個額外的減少（例如第 7.1 節）。
我相信我在這裡看到了攻擊，但這並不是作者描述的確切情況。聽起來作者建議依賴於蒙哥馬利乘法的平方乘冪算法將使用 $ n $ 集合中消息的額外減少 $ M1 $ 和 $ n+1 $ 集合中消息的額外減少 $ M2 $ 直覺上這對我來說沒有意義。我誤解了這次攻擊嗎？
**編輯：**在將我的攻擊程式碼與其他人進行比較後，我發現我對攻擊理解得很好，我的實驗也有所不同。我的結果與原始論文結果之間的差異是由於我選擇了蒙哥馬利參數。的價值 $ R $ 用於將數字放在蒙哥馬利形式中可能會對每次乘法所需的減少次數產生重大影響。
蒙哥馬利乘法
定理（蒙哥馬利，1985 年）。 對於任何奇數 $ N $ 和任何整數 $ 0 \le T < N2^k $ ，一個有：$$ T 2^{-k} \equiv \frac{T + UN}{2^k} \pmod N $$在哪裡 $ U = T N’ \bmod 2^k $ 和 $ N’ = -N^{-1} \bmod 2^k $ . 此外，一個有：$$ \begin{cases} T+UN \propto 2^k\ 0\le \frac{T + UN}{2^k} < 2N\end{cases} $$
最後 2 個屬性表明 $ R:=T2^{-k} \bmod{N} $ 可以分兩步計算：
- $ R \gets \frac{T+UN}{2^k} $
- 如果 $ R \ge N $ 然後 $ R \gets R - N\qquad $ （額外減法）
蒙哥馬利算術表示整數 $ 0\le x <N $ 作為 $ \tilde{x} = x2^k \bmod N $ . 它定義了兩個代表的蒙哥馬利乘法 $ \tilde{x} $ 和 $ \tilde{y} $ 作為$$ \tilde{x} \otimes \tilde{y} := (\tilde{x}\cdot\tilde{y})2^{-k} \bmod N\tag{*} $$ 觀察讓 $ z= x\cdot y \bmod N $ , 一個有 $ \tilde{z} \equiv (x\cdot y)2^k \equiv (\tilde{x}\cdot \tilde{y})2^{-k} \equiv \tilde{x} \otimes \tilde{y}\pmod N $ .
定時攻擊
假設每個蒙哥馬利乘法，cf。方程。( $ ^* $ )，是使用上述兩步過程完成的。我們看到這取決於 $ \tilde{x} $ 和 $ \tilde{y} $ , 可能有一個額外的減法來得到結果 $ \tilde{z} $ 在範圍內 $ [0, N) $ .
為了修正想法，假設計算 $ S = m^d \bmod N $ 使用平方和乘法算法進行。該攻擊可以很容易地適應其他求冪算法。該算法將消息作為輸入 $ m $ 和私人指數 $ d = (d_{\ell-1}, \dots, d_0)_2 $ .
- $ R_0 \gets \tilde{1} $ ; $ R_1 \gets \tilde{m} $
- 為了 $ i=\ell-1 $ 向下 $ 0 $ 做
- $ \quad R_0 \gets R_0 \otimes R_0 $
- $ \quad $ 如果 $ d_i = 1 $ 然後 $ R_0 \gets R_0 \otimes R_1 $
- 比以前
- 返回 $ \tilde{R_0} $
攻擊者的目標是恢復 $ d $ . 觀察平方和乘法算法處理的位 $ d $ 從左到右。
讓 $ d = (d_{\ell-1}, \dots, d_0)_2 $
在步驟 $ j $ , 攻擊者
- 已經知道位 $ d_{\ell-1}, d_{\ell-2}, \dots, d_{j+1} $
- 猜測下一位是 $ d_j=1 $
- 選擇 $ T $ 隨機消息 $ m_1, \dots, m_T $ 併計算$$ X_t = m_t^{(d_{\ell-1}, d_{\ell-2}, \dots, d_{j+1},1)_2} \bmod N\quad\text{for $1\le t \le T$} $$
- 準備兩套$$ \mathcal{S}_0 = {m_t \mid \text{subtraction}}\quad\text{and}\quad \mathcal{S}_0 = {m_t \mid \text{no subtraction}} $$
- 播放集合中的所有消息 $ \mathcal{S}_0 $ 並獲得平均執行時間 $ \tau(\mathcal{S}_0) $ 求冪；對 $ \mathcal{S}_1 $ 並獲得 $ \tau(\mathcal{S}_1) $
- 如果 $ \tau(\mathcal{S}_0) - \tau(\mathcal{S}_1) \not\approx 0 $ 然後 $ d_j=1 $ （猜測是正確的）；如果 $ \tau(\mathcal{S}_0) - \tau(\mathcal{S}_1) \approx 0 $ 然後 $ d_j=0 $ （猜測不正確）
迭代攻擊以找到 $ d_{j-1},\dots $
在上面的描述中，設置 $ \mathcal{S}_0 $ 表示一組消息，使得在迭代中有一個額外的減法 $ i=j $ 在平方和乘法算法的第 4 步（即蒙哥馬利乘法 $ R_0 \otimes R_1 $ ) 用於計算 $ X_t $ ; 放 $ \mathcal{S}_0 $ 表示在迭代中沒有額外減法的消息集 $ i=j $ 用於計算 $ X_t $ .
請注意，攻擊者可以評估指數 $ X_t $ 據她所知，她自己 $ d_{\ell-1}, d_{\ell-2}, \dots, d_{j+1} $ . 此外，由於 $ d_j $ 假定為 $ 1 $ , 這個求冪的最後一個操作 $ X_t $ 將是蒙哥馬利乘法 $ R_0 \otimes R_1 $ （即，第 4 步在迭代時執行 $ i=j $ ).
正確性
如果 $ d_j=1 $ 然後是集合中消息求冪的平均時間 $ \mathcal{S}_0 $ 將大於集合中消息求冪的平均時間 $ \mathcal{S}_1 $ 因為總有一個額外的減法 $ \mathcal{S}_0 $ .
如果 $ d_j=0 $ 然後是集合中消息求冪的平均時間 $ \mathcal{S}_0 $ 或在集合中 $ \mathcal{S}_1 $ 將（大致）相同，因為兩組之間的排序看起來是隨機的。請記住，攻擊者做出了猜測 $ d_j = 1 $ .
真巧，我昨天實施了這個攻擊！
我現在正在執行它，我可以告訴你，每一步的差異大約是 1 減少（正如論文所建議的那樣）。例如，請參閱我的日誌，了解 96 位密鑰的第 6 位到第 8 位：
bit 6: avg M2 (#111)= 1.2072072072072073, avg M1 (#99889)= 0.1684369650311846 [1, 1, 1, 1, 1, 1, 1] bit 7: avg M2 (#99)= 0.18181818181818182, avg M1 (#99901)= 0.16957788210328226 [1, 1, 1, 1, 1, 1, 1, 0] bit 8: avg M2 (#98)= 1.1938775510204083, avg M1 (#99902)= 0.16858521350923905 [1, 1, 1, 1, 1, 1, 1, 0, 1]如您所見，在設置為 1 的第 6 位和第 8 位中，M2 和 M1 的平均值大約相差 1 次減少（我的概念驗證測量的是目前的減少量，而不是時間），而在第 5 位中，設置為0，幾乎沒有區別。
據我了解，攻擊的想法是，在每一步（即，在每個位猜測上），攻擊者將樣本劃分為那些需要減少該特定步驟（M2）的樣本，以及那些不需要（ M1)。您似乎認為這意味著 M2 中的消息除了在目前步驟中隔離的消息外，往往會有更多的減少。然而，從我得到的數字來看，情況似乎並非如此：在每一步，只有 0.1% 的樣本需要減少（例如，在第 6 位，100000 個樣本中只有 111 個），這表明這種減少實際上是非常罕見的，所以大多數樣本對於整個冪運算都會有 0、1 或 2 次減少。
訣竅是，如果您能夠辨識減少發生的時刻（在攻擊中是通過計算每個樣本的所有平方和乘法運算來實現的），那麼您就有了一個告訴樣本的標準分開。因此，最可能的結果是 M2 和 M1 之間的差異僅是由於目前步驟存在減少。