使用“自異或”輸出功能攻擊 LCG？
考慮一個普通的 LCG 模 $ 2^n $ 內部狀態為 $ n $ 位和輸出 $ n/2 $ 位，我們不是簡單地截斷狀態以產生輸出，而是取上位和下位 $ n/2 $ 狀態的位並將它們異或在一起。
$$ X_{i + 1} = A X_i + C \bmod{2^n} $$ $$ Y_i = (X_i / 2^{n/2}) \oplus (X_i \bmod 2^{n/2}) $$
這種偽隨機數發生器是否在某處的論文中進行過分析？什麼時候攻擊它的核心思想是什麼 $ n $ 是否很大（例如 64 或 128 位或更大）？我對輸出預測或狀態恢復中斷特別感興趣，但是有一個區分器也很好。我們可以假設 LCG 參數（乘數和增量）都是已知且奇數的。
由於增加了與狀態相關的非線性操作，因此在這種情況下，通常的方法（例如格）似乎無法應用。
我嘗試按以下方式解決此問題：
我們正在嘗試恢復初始狀態 $ X_0 $ . 我們可能會收集一些輸出 $ { Y_i } $ 並猜測 LSB $ X_0 $ . 這會立即修復所有其他的 LSB $ X_i $ 自從 $ X_{i + 1} \equiv X_i + 1 \pmod{2} $ , 從而固定了所有的上半部分的 LSB $ X_i $ 根據輸出函式的定義。
一些算術表明，對於所有 $ i \geq 0 $ 我們有
$$ X_i \equiv A^i X_0 + C \sum_{k = 0}^{i - 1} A^k \equiv A^i X_0 + C_i \pmod{2^n} $$
我們現在可以忽略上半部分 LSB 之外的每一位（T 函式屬性）並專注於第一個 $ n/2 + 1 $ 位。如果我們發現不存在剩餘的分配 $ n/2 - 1 $ 位 $ X_0 $ 這樣，對於所有人 $ Y_i $ 集， $$ \mathrm{MSB}[\left ( A^i X_0 + C_i \right ) \bmod{2^{n/2 + 1}}] = \mathrm{LSB} \left [ Y_i \right ] \oplus \left ( \left ( X_0 + i \right ) \bmod{2} \right ) \tag{1} $$ 那麼我們肯定猜錯了。可能有更好的方法來做到這一點，但我們可以檢查可滿足性兩次，一次使用我們的猜測，一次使用替代猜測，添加更多 $ Y_i $ 直到任一系統變得無法滿足，從而恢復兩個位 $ X_0 $ . 沖洗並在下一個最低有效位上重複，直到所有位 $ X_0 $ 原則上可以恢復。
徹底檢查可滿足性需要 $ O(2^{n/2}) $ 時間，所以如果我們需要 $ m $ 以最幼稚的方式通過這種方法恢復狀態最多需要時間 $$ O((n/2) \cdot 2^{n/2} \cdot m) $$ 這比暴力破解內部狀態要快得多（假設 $ m $ 是合理的；我沒有證據，但我懷疑 $ m $ 正比於或至少是多項式 $ n $ ）。它應該（幾乎）可行 $ n = 64 $ ，而 $ n = 128 $ 案子仍然遙不可及。
使用 SMT 求解器作為算法的一部分（我嘗試了 Z3 和 boolector）並沒有真正提供任何加速，實際上比窮舉搜尋要慢。這在直覺上是有道理的，因為乘以不同的 $ A^i $ 在位向量上是高度非線性的，因此求解器只會陷入擴展和處理不斷增長的指數數量的子句的困境。
我們能做得更好嗎？有哪些想法可以在這裡應用？
為了回答我自己的問題，經過一些研究和實驗，我想出了一個快速算法來打破這種結構（事實上，即使增量 $ C $ 未知）。
- 作為預處理步驟，找到一組 $ m $ 小重量 $ \lvert w_i \rvert < W $ 這樣
$$ \sum_{i = 1}^{m} w_i A^i \equiv 0 \pmod{2^{n/2 + k}} \tag{1} $$
在哪裡 $ k $ 是稍後定義的一些小整數。這樣的一組權重可以通過格基減少（通常在多項式時間內）相當有效地找到，例如在以下格基上執行 LLL：
$$ \begin{bmatrix} K A & K A^2 & \dots & K A^m & K \cdot 2^{n/2 + k} \ 1 & 0 & \dots & 0 & 0 \ 0 & 1 & \dots & 0 & 0 \ \vdots & \vdots & \ddots & \vdots & 0 \ 0 & 0 & \dots & 1 & 0 \end{bmatrix} $$
對於足夠大 $ K $ ，如 Lagarias 和 Odlyzko 所示。在實踐中，我們期望這樣的權重存在於
$$ m \log_2(W) \approx n/2 + k $$
- 猜低 $ k $ 位 $ X_0 $ , 並使用 LCG 屬性推導出較低的 $ k $ 一點一滴 $ X_i $ .
- 使用 $ Y_i $ 獲得較低的 $ k $ 全部的上半部分 $ X_i $ . 表示 $ X^_i $ 作為 $ X_i $ 屏蔽為僅包括那些猜測的高位，即 $ X^_i = 2^{n/2} \times \mathrm{guess} $ .
- 如果我們做一些基本代數，我們可以注意到下面的同餘式來自 (1)
$$ \sum_{i = 1}^{m} w_i \left [ X_{i + 1} - X_i \right ] \equiv 0 \pmod{2^{n/2 + k}} \tag{2} $$
- 由於 $ w_i $ 受 $ W $ 並且我們知道所涉及的變數的最高有效位，我們可以使用我們的近似這個和 $ X^*_i $ . 事實上，我們可以將其評估為 $ \pm 2 m W \cdot 2^{n/2} $ . 計算：
$$ Z = \sum_{i = 1}^{m} w_i \left [ X^_{i + 1} - X^_i \right ] \bmod{2^{n/2 + k}} $$
然後讓 $ \Delta $ 成為兩者之間的區別 $ Z $ 和 0 或 $ 2^{n/2 + k} $ , 取最接近的 $ Z $ .
- 如果 $ \Delta \geq 2mW \cdot 2^{n/2} $ ，我們對低位的猜測 $ X_0 $ 當然是不正確的。否則，它是正確的機率 $ 1 - 2mW \cdot 2^{-k} $ （這對分佈的一些假設 $ Y_i $ ，但在實踐中有效）。
- 全部嘗試 $ 2^k $ 針對不同輸出視窗的猜測 $ Y_i $ （相應調整，請注意，即使您將所有指數移動一個固定常數，關係 (1) 仍然成立）直到除一個以外的所有指數都未能通過步驟 6 中的測試。最終的候選猜測將是 $ X_0 $ .
- 重複所有步驟，依次猜測更高位 $ X_0 $ 直到整個內部狀態恢復。
事實證明這非常快 $ k $ 可以設置為不大於 $ \log_2{mW} $ ，以使步驟 6 中誤報的機率足夠小，例如 0.5；如果 $ k $ 太小，那麼我們就沒有提取任何資訊。
鑑於上述情況，我們應該嘗試強制 $ W $ 在步驟 1 中盡可能小以最小化位數 $ k $ 猜測，例如， $ W \approx 2 $ , $ m \approx n/2 + k $ 所以 $ k \approx \log_2(n) $ 表明這種攻擊應該很好地擴展 $ n $ .
我已經實現了這一點，它執行良好並成功恢復了預期的內部狀態 $ n = 128 $ .
也可以將其擴展到未知增量 $ C $ ，唯一改變的是我們需要猜測的低位 $ C $ 同時作為低位 $ X_0 $ 能夠執行第 2 步，其他一切都保持不變；我們恢復 $ C $ 和 $ X_0 $ 同時通過相同的過程。
參考
這種方法改編自“格子縮減：密碼分析者的工具箱”中描述的技術。這篇論文包含了更複雜的技術來解決類似的問題，並且可讀性很好。