中方外爾序列PRNG的攻擊
在這個答案（現已刪除）中，提出了中間方形外爾序列 PRNG 作為 CSPRNG 屬性的說明。此 PRNG 由 Bernard Widynski 在Middle Square Weyl Sequence RNG ( arXiv, 2017 ) 中介紹。這並沒有聲稱加密安全，但該論文的 v5 推測“通過檢查輸出來確定內部狀態很困難”。
PRNG 有一個 128 位狀態，由兩個 64 位變數組成 $ x $ 和 $ w $ . PRNG 輸入包括初始 $ x_0 $ 和 $ w_0 $ , 和一個奇數值 $ s $ . 狀態的演變和 32 位偽隨機輸出 $ r_i $ 被定義（對於 $ i\ge0 $ ） 經過 $$ \begin{align} r_i&\gets x_i\bmod2^{32}\ w_{i+1}&\gets(w_i+s)\bmod 2^{64}\ x_{i+1}&\gets((x_i^2+w_{i+1})\bmod 2^{64})\ggg32 \end{align} $$ 在哪裡 $ \ggg32 $ 交換其 64 位左參數的一半。
[符號被修改，因此 $ r_0 $ 是輸出，為了與答案保持一致]
論文給出了參考C99實現（帶輸入 $ x_0=w_0=0 $ 和一定的 $ s $ ; 輸出開始於 $ r_1 $ )
uint64_t x = 0, w = 0, s = 0xb5ad4eceda1ce2a9; inline static uint32_t msws() { x *= x; x += (w += s); return x = (x>>32) | (x<<32); }假設我們有一個 $ r_i $ 為了 $ 0\le i\le9 $ . 如何有效地預測序列的其餘部分？那將是一個徹底的休息。
如果不可行，也歡迎使用較小的中斷（僅區分輸出與隨機，或需要更多明文，或僅適用於一小部分輸入）。
讓我們看看函式對內部狀態所做的計算。
當我們開始攻擊時，我們將變數的狀態表示為 $ x_0 = (a, b) $ 和 $ w_0 = (c, d) $ , 我將在哪裡使用符號 $ (i, j) $ 表示具有的 64 位數字 $ i $ 作為高 32 位，和 $ j $ 作為低 32 位（等等 $ a, b, c, d $ 每個是 32 位）。注意 $ x_0, w_0 $ 不必是 PRNG 的初始狀態，而是生成初始輸出時的狀態。
然後，上一步暴露 $ b $ （所以攻擊者知道這一點）。
然後，它平方 $ x_0 $ 模組 $ 2^{64} $ , 替換 $ x_0 = (a, b) $ 和 $ x_0^2 = (2 a b + (b^2 >> 32), b^2\ \bmod 2^{32}) $ . 正如攻擊者所知 $ b $ , 攻擊者可以用線性運算代替 $ x_0^2 = (h_0 a + h_2, h_1) $ ， 在哪裡 $ h_0, h_1, h_2 $ 是已知的（對攻擊者而言）常量（因為它給出了從先前狀態到新狀態的相同映射）。
然後，算法添加 $ w $ 至 $ x $ ，可以建模為：
$ x_0^2 + w_0 = (h_0 a + h_2 + c + \epsilon_0, h_1 + d) $ ， 在哪裡 $ \epsilon_0 $ 是 0 還是 1，取決於是否發生了低 32 位的進位。
然後，它添加常數 $ s $ 至 $ w $ , 這可以建模為 $ w + s = (c + s_{hi} + \epsilon_1, d + s_{lo}) $ ， 在哪裡 $ \epsilon_1 $ 是 0 還是 1，取決於是否發生了來自低 32 位的進位（並且 $ s = (s_{hi}, s_{lo}) $
然後，它旋轉 $ x $ , 給 $ x_1 = (h_1 + d, h_0a + h_2 + c + \epsilon_0) $ , 並輸出低 32 位 $ h_0a + h_2 + c + \epsilon_0 $ .
新狀態是 $ x_1 = (h_1 + d, h_0a + h_2 + c + \epsilon_0) $ 和 $ w_1 = (c + s_{hi} + \epsilon_1, d + s_{lo}) $ ; 也就是說，它是前一狀態的 4 個線性函式之一（取決於 $ \epsilon_0, \epsilon_1 $ )
繼續進行 3 次以上的迭代，結果狀態將仍然是初始狀態的少數已知線性函式之一；輸出也將是狀態的線性函式。通過四個輸出，攻擊者可以遍歷可能的 $ \epsilon $ 值，並求解初始狀態。如果你通過方程，你會發現你可以恢復 $ c, d $ 從第三和第四個輸出；使用價值 $ c $ 給你的價值 $ a $ 從第二個輸出（你得到 $ b $ 作為第一個輸出）。