Cryptanalysis

LCG 破解技術有多脆弱？

  • January 24, 2016

已經發布了破解 LCG 的技術，但在我看來，這些技術似乎非常脆弱——非常小的變化會增加非線性，從而使 LLL 算法等技術無法使用。或者，我錯了，這些變體仍然容易破解嗎？

背景

關於密碼學社區，讓我有些困惑的一件事是，人們似乎討厭 LCG 並在不費吹灰之力修復其缺陷的情況下將其註銷，但又喜歡 LFSR 並經常修復它們。

原始 LCG 和 LFSR都很弱

在 Schneier 的Applied Crypography (1996) 中，他寫到關於 LCG 的詛咒：

不幸的是，線性同餘生成器不能用於密碼學。它們是可以預測的。Jim Reeds ( 1977 , 1979a , 1979b ) 和 Joan Boyar ( 1982 )首先打破了線性同餘生成器。

$$ … $$ 其他研究人員擴展了 Boyar 的工作以打破任何多項式同餘生成器（Lagarias & Reeds 1988、Krawczyk 1989、Krawczyk 1992）。截斷線性同餘生成器也被破壞（Frieze et al 1984 , Hastad & Shamir 1985 , Frieze et al 1988），具有未知參數的截斷線性同餘生成器也是如此（Stern 1987 , Boyar 1989）。證據的優勢是同餘生成器對密碼學沒有用。

相比之下，這本書發出了關於 LFSR 的混合資訊，說了一些積極的話，比如：

由於簡單的回饋序列，大量的數學理論可以應用於分析 LFSR。密碼學家喜歡分析序列以說服自己它們的隨機性足以保證安全。LFSR 是密碼學中最常見的移位寄存器類型。

但也說：

另一方面，數量驚人的看似複雜的基於移位寄存器的生成器已被破解。當然，像美國國家安全域這樣的軍事密碼分析機構已經破解了更多。有時，一次又一次地看到簡單的建議是令人驚奇的。

最近，Schindler 2009同意後一個建議，他說：

因此，LFSR 不滿足要求 R2

$$ lack of predictability $$，並且它們絕對不適合敏感的加密應用程序。

更安全的變化……？

Applied Crypography的 RNG 章節的其餘部分主要關注 LFSR 變體，這些變體以復雜的非線性方式組合 LFSR，使它們更難以破解。

但在我看來，這是一個奇怪的對比，它完全不屑於改進 LCG 的嘗試，他說：

許多人檢查了線性同餘生成器的組合（Wichmann & Hill 1982，L’Ecuyer 1988）。結果在密碼學上不再安全，但組合具有更長的周期並且在某些隨機性測試中表現更好。

令我驚訝的是，與本書的其他大部分內容不同，這些主張沒有得到引用的支持。所引用的兩篇論文都根本沒有提到安全性或密碼學，那麼施奈爾從哪裡得到“結果不再是密碼學安全”的說法？

這很有趣，因為Knuth 1985提出了完全不同的主張，他說：

雖然我們已經看到線性同餘序列本身不會導致安全加密，但稍作修改就會破壞這裡介紹的方法。特別是，似乎沒有辦法破譯由經過混洗的線性同餘序列生成的高位序列

$$ … $$

當然，這些參考資料已經很老了，但我看到的大多數討論似乎都提到了 1980 年代和 1990 年代他們對 LCG 的解僱。

LCG 破解技術有多脆弱……？

所以，這（最終）導致了我的問題。這些破解 LCG 的技術到底有多脆弱？他們真的有致命的缺陷無法修復嗎？

讓我們用一些範例 C 程式碼來實現它：

#include <stdio.h>
#include <stdint.h>

int main()
{
    uint32_t result;
    uint64_t state = SEED;
    for (int i=0; i < 32; ++i) {
        state = state * MULT + INC;
        result = state >> 32;
        result ^= XOR;
        printf("0x%08x, ", result);
    }
    printf("\n");
}

案例 0：已知的一切

因此，如果我們設置SEED=0x35e647cfd3423fd0ull、MULT=0xc278c0d1c04a88d9ull和 INC=0 XOR=0，程序產生

0x59502137, 0xb6152ece, 0xbbd2cb88, 0xef05249f, 0x3ec02cd5, 0x2b0eca82, 0x0a3120be, 0x5116f6fb, 0x8b06b68c, 0x01367995, 0xca5789bd, 0xa40f57ff, 0x5f6d75bb, 0x544951f7, 0x8f9e70c8, 0x74307957, 0x70aab16c, 0x0ec42e72, 0x9bb2a42d, 0x2c5aa6aa, 0xe3cff469, 0x37881c03, 0x8d7853ba, 0xd6beb049, 0xa9fc0e6e, 0xbbc5bd2b, 0x33462a03, 0xad508c7e, 0xe31313e9, 0xf30418ae, 0xbefc1b02, 0xc0134d22,

案例一：小案例

現在SEED是未知MULT=0xc278c0d1c04a88d9ull INC=0 XOR=0的，輸出是

0x8b1294a5, 0xae5cbf0d, 0x2da164bd, 0xcbe27c6d, 0x6d800d17, 0x8f576a33, 0x6ea4915b, 0x97ada3d5, 0x8ab31e5d, 0x0bb313d2, 0xfbee8ebf, 0xf1d09659, 0x5a54428e, 0x34d32f9a, 0xe800efdb, 0x5a313abd, 0x844a1328, 0xed9cf267, 0x5883910f, 0x7a44aa80, 0x0e34d575, 0x7e3453df, 0x2267bf41, 0x8c234c85, 0xa359f8b8, 0xf78f0126, 0x7902934e, 0x5ae97dc1, 0x1ba40108, 0x67f5ca64, 0x7aed8c5e, 0xceccf54b,

以上應該是微不足道的。即使是蠻力也是實用的，因為我們只需要搜尋 2^32 個可能的狀態。

案例 2：已知技術

現在SEED和INC是未知的，MULT=0xc278c0d1c04a88d9ull並且XOR=0，並且輸出是

0x8c005b3e, 0x27e3338e, 0x1bb199bb, 0x46449299, 0x4b747cca, 0x290032ca, 0x2a6e907f, 0x6b1bd36f, 0xab7f4d33, 0x9b7a73be, 0xe9ae522c, 0x171e7e55, 0x95b0dcd2, 0xd93e6986, 0xddd1a6d2, 0xf2e197e5, 0x8e621adc, 0x0ac2dd7e, 0x31fafcce, 0xc7e19a1a, 0x5f9b0788, 0x9f3a790e, 0xe0e76b17, 0x6fcf2716, 0x0106a4fb, 0x3e64838a, 0x508cc169, 0x690a7b96, 0xde80a6cc, 0xbbcc6546, 0x76e80fe9, 0x6683486d,

這也應該是可破解的，但我們需要使用文獻中的技術，因為蠻力方法是不可行的。我很想看到真正打破這一點併計算出下一個數字的程式碼。

案例 3：增加非線性（更難？）

現在SEED,INC和XOR是未知的, MULT=0xc278c0d1c04a88d9ull, 輸出是

0x5e3af925, 0x1b7f8e1a, 0x268c64d1, 0x4b614b92, 0xba6c7a4d, 0xe4103860, 0xfe373528, 0x768f9a04, 0xedab3415, 0x2605ff3f, 0xb01e70bb, 0xff65e40a, 0x50980bee, 0xe9fb0d78, 0xdf3754bd, 0x46cce80d, 0xfe1395ac, 0x2e663615, 0xdebea707, 0x4d2cd17d, 0x30f0c21c, 0xb15a64ee, 0x21d38d72, 0xbb8e8c6d, 0x114447d1, 0x5362837c, 0xed46a733, 0x37526997, 0xf7ac14c2, 0xc33e7134, 0x96a9d739, 0x3ee606ba

所以，這是我問題的癥結所在。這個變體比前一個變體難多少？根據我對破壞截斷 LCG 的標準技術的閱讀，這種增加的非線性是一個問題。我們可以取消 XOR，但這會破壞我們已經為取消增量所做的減法；我們可以取消其中一個，但不能同時取消。

（如果它仍然很容易，我的常量是什麼？想分享破壞它的實際程式碼嗎？）

案例4：更難嗎？

所以，現在SEED、INC和都是未知的，輸出XOR是MULT

0xc325ad70, 0x5ac2c779, 0xafa3561b, 0xa39f9107, 0x256264b5, 0x8d07c2e8, 0x55d53f9e, 0xb090eacc, 0x8b5a28a9, 0xa5e2a296, 0xc0650347, 0x0718efdb, 0x66c331c5, 0xd00236cf, 0x22118dc5, 0x4f9d67d0, 0xa6793bfe, 0x00ad774d, 0xd8337c8f, 0x49aab5b3, 0x96e419c8, 0xd6a9385b, 0x47108063, 0xde06326f, 0x2d4cd28c, 0xb0f97be8, 0x494f5df1, 0x8d53de30, 0x0eee9cbc, 0x9ea6beb1, 0xbefa03b6, 0x5a3d1fea,

這有多難打破？（如果它仍然很容易，我的常量是什麼？想分享破壞它的實際程式碼嗎？）

以前的 StackExchange 問題

我知道之前的討論here、here和here，但是這些答案都與這個問題不匹配，它們解決了特定類型LCG有多弱的問題（通常從一個容易破壞的例子開始），而不是脆性所使用的技術。

更新：問題澄清

（一些使用者想以“太寬泛”來結束我的原始問題，所以我澄清了它，解決了這個問題。）

所以，要清楚，我的問題是：

我知道案例 1 很簡單，案例 2 已經發布了解決它的技術。但是，我的問題是：

  • 是否有任何有效的已知技術可以破解案例 3 或 4？如果是這樣，它們是什麼？
  • 是否有破解案例 2 的實現程式碼。

我希望這足夠直截了當，可以回答，或者讓人們說“我在密碼學方面做了很多工作，但我不知道答案”。

此答案解決了問題中的案例 1 和案例 2 以提供基線，而案例 3（這是我最感興趣的案例）未解決。

案例一，零增量

在這種情況下，我們將考慮一個簡單的 Lehmer 風格的 LCG（又名 MCG），帶有一個種子 $ s_1 $ , 乘數 $ a $ 和 $ b $ 狀態位和 $ r $ 位返回。模數 $ M = 2^b $ , 內部狀態為 $ s_1, a s_1, a^2 s_1, a^3 s_1, a^4 s_1, \ldots \mod M $ . 輸出值由整數除以產生 $ m = 2^{b-r} $ .

如果我們說已知的高位是 $ h_1, h_2, h_3, h_4, \ldots $ 未知的低位是 $ l_1, l_2, l_3, l_4, \ldots $ ，因此我們可以說：

$$ \begin{eqnarray*} s_1 & = & h_1 m+l_1 \mod M\ a s_1 & = & h_2 m+l_2 \mod M\ a^2 s_1 & = & h_3 m+l_3 \mod M\ & \vdots & \end{eqnarray*} $$ 在給定的範例中， $ a = 14013162247670106329 $ , $ b = 64 $ , $ r = 32 $ , $ M = 2^{64} $ , $ m = 2^{32} $ .

LLL 配方

在 LLL 公式中，我們將採用方程

$$ \begin{eqnarray*} M s_1 & = & 0 \mod M\ a s_1 - s_2 & = & 0 \mod M\ a^2 s_1 - s_3 & = & 0 \mod M \end{eqnarray*} $$ 並將它們表示為格子 $ L $ 其中每一行 $ L_i . (s_1, s_2, s_3) = 0 $ .

$$ L = \left( \begin{array}{ccc} M & 0 & 0 \ a & -1 & 0 \ a^2 \bmod M & 0 & -1 \end{array} \right) $$ 在範例中，這變為

$$ \left( \begin{array}{ccc} 18446744073709551616 & 0 & 0 \ 14013162247670106329 & -1 & 0 \ 9716750713725077489 & 0 & -1 \ \end{array} \right) $$ 如果我們應用晶格縮減（例如，LatticeReduce在Mathematica中），我們得到：

$$ \left( \begin{array}{ccc} 238170 & 2443922 & 662052 \ -2629560 & 974809 & -465865 \ 341923 & -550461 & 2727218 \ \end{array} \right) $$ 這告訴我們

$$ \begin{eqnarray*} 238170 s_1 + 2443922 s_2 + 662052 s_3 & = & 0 \mod M \ -2629560 s_1 + 974809 s_2 + -465865 s_3 & = & 0 \mod M \ 341923 s_1 + -550461 s_2 + 2727218 s_3 & = & 0 \mod M \end{eqnarray*} $$ 從某種意義上說，這是“更好”的，因為它是更好的線性方程組，但對於實際解決手頭的問題，我發現它沒有用，因為我的方程求解器（Mathematica）即使我們不要使用晶格縮減。

直接解決方案

給定我們的方程，我們可以在Mathematica中寫出，

SolveMCG[a_, b_, r_, h1_, h2_, h3_] := 
With[{M = 2^b, m = 2^(b - r)}, 
 Solve[{    s == l1 + h1 m,
          a s == l2 + h2 m + k2 M, 
        a^2 s == l3 + h3 m + k3 M,
        l1 >= 0, l1 < m,
        l2 >= 0, l2 < m, 
        l3 >= 0, l3 < m},
       Integers]]

然後執行

SolveMCG[14013162247670106329, 64, 32,
        2333250725, 2925313805, 765551805]

產生以下結果（大約百分之一秒）：

{{k2 -> 7612682177356138107, 
 k3 -> 106677750491238099311986697652283092078,
 l1 -> 3882613991, l2 -> 3819575247, l3 -> 2041194103,
  s -> 10021235561125903591}}

在這裡，它正確地推斷出低位和初始種子，我們只使用三個 32 位輸出就完成了。

實際上，三個輸出可以說是矯枉過正。實際上，我們幾乎可以只使用兩個輸出來解決它！給定類似的定義：

SolveMCG[a_, b_, r_, h1_, h2_] := 
With[{M = 2^b, m = 2^(b - r)}, 
 Solve[{  s == l1 + h1 m,
        a s == l2 + h2 m + k2 M, 
        l1 >= 0, l1 < m,
        l2 >= 0, l2 < m}, 
       Integers]]

跑步

SolveMCG[14013162247670106329, 64, 32, 2333250725, 2925313805]

（我們甚至可以用Wolfram Alpha解決），給出

{{k2 -> 7612682176901725222, l1 -> 3284430794, l2 -> 491393594, 
 s -> 10021235560527720394},
{k2 -> 7612682177356138107, l1 -> 3882613991, l2 -> 3819575247,
 s -> 10021235561125903591}}

唯一的問題是，在這種情況下，我們有兩個系統解決方案（第二個是我們真正想要的）。

三個輸出為我們提供了一個唯一的解決方案（在這種情況下），實際上我們仍然有一個具有三個輸出的唯一解決方案，即使我們下降到 24 位。

當我們進一步減少輸出位數時，看看會發生什麼很有趣。對於 64 位狀態的 16 位輸出，我們需要四個輸出來找到唯一的解決方案。同樣，12 位輸出需要 6 個輸出，10 位輸出需要 7 個，8 位輸出需要 8 個（在 0.5 秒內求解），4 位輸出需要 16 個（但需要一分鐘才能求解！）。後面的這些情況很有趣，因為一些作者聲稱，如果我們只返回 LCG 就可以是安全的 $ \log_2 b $ 位，但是 $ \log_2 64 = 6 $ 那時我們仍然可以輕鬆解決問題。

但也許這些說法在現實中有一定的根據——3 位輸出需要 22 個輸出（不是那麼多），但需要 76 分鐘才能解決，這讓我猜測解決 2 位輸出會需要將近兩個月的時間，而且（如果我的推斷是正確的！），如果我們只取高位，Mathematica大約需要 50 億年才能解決。哎喲!

案例 2，未知增量

這裡的訣竅是觀察如果

$$ \begin{eqnarray*} s_2 & = & a s_1 + c \mod M\ s_3 & = & a s_2 + c \mod M\ s_4 & = & a s_3 + c \mod M\ & \vdots & \end{eqnarray*} $$ 然後 $$ \begin{eqnarray*} s_2 - s_1 & = & ((a - 1) s_1 + c) \mod M\ s_3 - s_2 & = & a ((a - 1) s_1 + c) \mod M\ s_4 - s_3 & = & a^2 ((a - 1) s_1 + c) \mod M\ & \vdots & \end{eqnarray*} $$ 換句話說，如果我們取連續值之間的差異，我們將再次擁有 Lehmur 風格的 LCG。 一個問題是，減去截斷的高位可能不會產生與減去實際值然後截斷相同的結果（由於缺少借位），因此我們必須稍微搜尋一下。但這很容易做到：

SolveLCG[a_, b_, r_, lh1_, lh2_, lh3_, lh4_] := 
   Flatten[Table[SolveMCG[a, b, r, h1, h2, h3],
                {h1, Mod[{lh2 - lh1 - 1, lh2 - lh1}, 2^(b - r)]},
                {h2, Mod[{lh3 - lh2 - 1, lh3 - lh2}, 2^(b - r)]},
                {h3, Mod[{lh4 - lh3 - 1, lh4 - lh3}, 2^(b - r)]}], 3]

對於我們的問題，執行

SolveLCG[14013162247670106329, 64, 32,
        2348833598, 669201294, 464624059, 1178899097]

生產

{{k2 -> 8533036703073522045, k3 -> 5916822271048598914, 
 l1 -> 111392721, l2 -> 2094520361, l3 -> 3114664641, 
 s -> 11232778258835814353}}

這個結果並不能完全解決問題，因為它只計算差異的低位，而沒有告訴我們原始種子的低位。儘管如此，它會讓我們非常接近 RNG 的輸出。

但是請注意，我們的減法技術在案例 3 中被異或打敗了。

另外，請注意，在我嘗試Mathematica之前，我嘗試使用幾個 ILP 求解器（例如lp_solve、GLPK和Mathematica的LinearProgramming），但成功率要低得多。ILP 求解器在可行解的數量很大的優化中效果最好。在這種情況下，只有一個可行的解決方案，而 LP 不會幫助求解器找到它，因此求解器在沒有幫助的情況下無法找到解決方案，這相當於告訴他們答案。唉，Mathematica的Solve函式沒有說明它是如何找到解決方案的。

這是一項正在進行的工作，主要是試圖解決問題中的案例 3，因為案例 2 的問題在另一個答案中得到了處理，並且已經過深入研究：

我將首先建立線性同餘生成器的特性：LCG 的狀態遠離 $ t $ 步驟由簡單的關係連結（複雜性獨立於 $ t $ 如果我們知道乘數），當使用迭代密碼建構的 CSPRNG 時，複雜度會隨著 $ t $ . 結合對 LCG 內部狀態的直接部分暴露，這就是為什麼從密碼學的角度來看 LCG 通常被認為是差的原因。

讓 $ \forall j\in\mathbb N,\ s_{j+1}=\big(s_j\cdot a+c\big)\bmod M $ 是 LCG 的遞推關係。它遵循

$ \ \ \ \ \ \forall j\in\mathbb N,\ s_{j+2}=\big(s_j\cdot a^2+c\cdot(a+1)\big)\bmod M $

$ \ \ \ \ \ \forall j\in\mathbb N,\ s_{j+3}=\big(s_j\cdot a^3+c\cdot(a^2+a+1)\big)\bmod M $

並通過歸納

$$ \forall j\in\mathbb N,\forall t\in\mathbb N,\ s_{j+t}=\big(s_j\cdot a^t+c\cdot{a^t-1\over a-1}\big)\bmod M $$ 這可以從目前狀態導出未來狀態，而無需顯式計算中間步驟；進一步，如果 $ \gcd(a,M)=1 $ （因為它應該）這個方程連結狀態遙遠 $ t\in\mathbb Z $ 方程的步驟 $ s_{j+t}=s_j\cdot a_t+c\cdot b_t\bmod M $ ， 和 $ a_t $ 和 $ b_t $ 乘法器的簡單已知函式 $ a $ ， 和 $ t $ .

對於案例 3 的具體解決方案，措辭如下（與 $ M=2^{64} $ , $ a=\text{c278c0d1c04a88d9}_{16} $ , 未知 64 位INC= $ c $ , 未知 32 位XOR= $ x $ 和 32 個連續輸出），一個值得嘗試的想法是在布爾可滿足性框架中建構問題的表達式。我猜想這樣做是有利的

  • 通過合併許多關係使問題嚴重過度指定 $ s_{j+t}=s_j\cdot a_t+c\cdot b_t\bmod M $ 和 $ a_t $ 和 $ b_t $ 預先計算（希望 SAT 求解器能夠利用額外的關係）；
  • 也許改變變數 $ c $ 相當於 $ c’ $ 稍微簡化了乘法常數 $ b_t $ ;
  • 也許在某種程度上修剪給定，以便相應地修剪大小。

暫定草圖：

  • 會心 $ a $ , 計算 $ a_t $ , $ b_t $ 為了 $ 0<|t|<32 $ , 這樣 $ s_{j+t}=s_j\cdot a_t+c\cdot b_t\bmod M $ ，使用上面的公式；

  • 挑選 $ r $ 不同的價值觀 $ j_p\in{1,32} $ 對應的索引 $ s_j $ 我們保持（通過我們需要的熵參數 $ 5\le r\le32 $ ，因此我們至少有與未知數一樣多的給定位；我會嘗試從 $ r\approx8 $ ); 對於給定的 $ r $ ，有利的是，至少有一些 $ a_{j_p-j_q} $ 具有低漢明權重；

  • 選擇一些奇怪的 64 位 $ z $ 所以至少有一些漢明權重 $ b’t=z^{-1}\cdot b_t\bmod M $ 非常低；我們將使用 $ c’=z\cdot c\bmod M $ 而不是INC/ $ c $ 作為增量的未知數，方程變為 $ s{j+t}=s_j\cdot a_t+c’\cdot b’_t\bmod M $ ;

  • 分配 SAT 變數：

    • 64 個變數 $ c’ $ ,
    • 32 個變數XOR/ $ x $ （注意這些變數是高 32 位 $ s_{j_p} $ 在給定的極性變化範圍內）；
    • 每個低 32 位的 32 個變數 $ r $ 狀態 $ s_{j_p} $ 採摘

  • 表達 $ r\cdot(r-1) $ 關係 $ s_{j_p}=s_{j_q}\cdot a_{j_p-j_q}+c’\cdot b’_{j_p-j_q}\bmod M $ 為了 $ p\ne q $ 作為二進制變數之間的關係，翻譯成 SAT 子句：

    • 模組化減少是完全免費的，因為 $ M=2^{64} $ ;
    • 乘以已知常數 $ a_{j_p-j_q} $ 和 $ b’{j_p-j_q} $ 很簡單，減少到二進制加法 $ s{j_p} $ 或者 $ c’ $ ;
    • 我們的基本建構塊是具有 3 個輸入和 2 個輸出的全二進制加法器 $ S=(I_0\wedge I_1\wedge I_2)\vee(I_0\wedge\overline{I_1}\wedge\overline{I_2})\vee(I_1\wedge\overline{I_2}\wedge\overline{I_0})\vee(I_2\wedge\overline{I_0}\wedge\overline{I_1}) $ 和 $ C=(I_0\wedge I_1)\vee(I_1\wedge I_2)\vee(I_2\wedge I_0) $ , 雖然有些加法器不需要 $ C $ 輸出與否 $ I_2 $ 輸入;
    • 對於我們需要的每個關係 $ 65\cdot32 $ 二進制加法器（一個很好的選擇 $ j_p $ 和 $ z $ 稍微削減）；
    • 對於每個加法器，我們最多需要 2 個額外變數（每個使用的輸出一個，除了那些有點 $ s_{j_p} $ );
    • 特別是在低位會有一些重複的變數，我們可以刪除它們；

  • 提供給最先進的 SAT 求解器，並希望它吐出解決方案！

由此產生的系統顯然保持可管理的規模；但我不能證明它可以有效地解決，沒有嘗試！

引用自：https://crypto.stackexchange.com/questions/20495

相關問答

Cryptanalysis

有沒有辦法在去中心化網路中生成不可預測的隨機數？

  • September 5, 2014
檢視問答
Cryptanalysis

使用 MD5 初始化隨機數生成器是否安全？

  • October 20, 2022
檢視問答
Cryptanalysis

從線性同餘生成器預測值

  • March 20, 2022
檢視問答
Cryptanalysis

為什麼 FBI 要求 Apple 幫助解密 iPhone？

  • February 1, 2022
檢視問答
Cryptanalysis

如果我只知道輸出的模數，是否可以破解線性同餘生成器？

  • December 13, 2021
檢視問答
Attack

窮舉搜尋算法的時間複雜度

  • July 27, 2021
檢視問答