CTF-Wiki 密碼學安全僞隨機數生成器（CSPRNG）完全指南：從 next-bit test 到 CTF 實戰

文档网络安全教程【免费下载链接】ctf-wikiCome and join us, we need you!项目地址https://gitcode.com/gh_mirrors/ct/ctf-wiki点击查看免费下载導讀本文基於 CTF-Wiki 密碼學專欄中 csprng.md 一文系統梳理密碼學安全僞隨機數生成器CSPRNG的定義、應用場景、安全需求與設計分類。文中將結合倉庫內 PRNG 基礎介紹、流密碼體系以及 LFSR、LCG 等具體生成器的 CTF 實戰案例幫助讀者理解「爲什麼普通的隨機數不能直接用於密碼學」掌握判別 CSPRNG 的核心準則next-bit test、前向安全並能在 CTF 賽題中識別出僞隨機數設計缺陷並加以利用。什麼是密碼學安全僞隨機數生成器密碼學安全僞隨機數生成器cryptographically secure pseudo-random number generatorCSPRNG也稱爲密碼學僞隨機數生成器cryptographic pseudo-random number generatorCPRNG是一種特殊的僞隨機數生成器。與普通僞隨機數生成器不同它需要滿足一系列額外的必要特性以便於適合密碼學應用。要理解 CSPRNG 的定位首先要回顧普通 PRNG 的性質。在 prng/intro.md 中僞隨機數生成器被定義爲用來生成「接近於絕對隨機數序列的數字序列」的算法又稱爲確定性隨機位生成器deterministic random bit generatorDRBG。PRNG 依賴於一個初始值種子來生成僞隨機數序列只要種子確定生成序列就完全確定因此它產生的序列並非真正隨機。據此隨機數可以按「隨機性、不可預測性、不可重現性」三種性質的嚴格程度分爲三類類別隨機性不可預測性不可重現性弱僞隨機數✅❌❌強僞隨機數✅✅❌真隨機數✅✅✅一般來說密碼學中使用的隨機數是第二種——強僞隨機數。CSPRNG 正是這一類具備「不可預測性」的生成器在種子未知的前提下攻擊者即使觀察到大量的歷史輸出也無法在計算上可行地推斷出後續輸出。密碼學的哪些環節離不開隨機數CSPRNG 之所以重要是因爲密碼學的很多方面都需要隨機數。原文明確列舉了以下典型場景密鑰生成對稱密鑰、非對稱密鑰對的產生都需要高質量隨機數密鑰一旦可預測整個密碼體制便形同虛設初始化向量IV用於分組密碼的 CBC、CFB、OFB 模式IV 必須不可預測否則分組密碼的語義安全性會被破壞nonce用於防止重放攻擊以及分組密碼的 CTR 模式等nonce 重複或可預測會導致密鑰流重用一次一密one-time pad一次性便箋本的安全性完全依賴於密鑰流的不可預測性若用可預測的僞隨機序列替代一次一密將退化爲可破解的普通異或加密簽名方案中的鹽salt如 ECDSA、RSASSA-PSS 等簽名方案在生成隨機數或鹽時若隨機數泄漏或可預測可能直接導致私鑰恢復。在倉庫的密碼學體系中這些場景與 流密碼 密切相關流密碼逐字節或逐比特處理信息密鑰長度與明文相同且密鑰派生自一個較短密鑰派生算法通常就是一個僞隨機數生成算法。僞隨機數生成算法生成的序列隨機性越強明文中的統計特徵就被覆蓋得越好——這正是 CSPRNG 在流密碼中扮演的核心角色。CSPRNG 的兩大安全需求毫無疑問CSPRNG 的要求比一般 PRNG 要高得多。一般而言CSPRNG 的要求可以分爲兩類。需求一通過統計隨機性測試next-bit testCSPRNG 必須通過next-bit test下一位預測測試。也就是說知道了一個序列的前 k 個比特攻擊者不可能在多項式時間內以大於 50% 的概率預測出下一個比特位。這裏特別值得提及的是姚期智曾在 1982 年證明如果一個生成器可以通過 next-bit test那麼它也可以通過所有其他的多項式時間統計測試。這意味着next-bit test 是一個「一票否決」式的充分性判據——只要確認生成器通過了 next-bit test就無需再逐一檢驗其他統計測試如 NIST 隨機性測試套件中的頻率測試、遊程測試等這在理論上極大簡化了 CSPRNG 的安全性論證。需求二抵抗足夠強攻擊者的狀態泄漏攻擊CSPRNG 還必須能夠抵抗足夠強的攻擊當生成器的部分初始狀態或者運行時的狀態被攻擊者獲知時攻擊者仍然不能夠獲取泄漏狀態之前生成的隨機數。這一性質在現代密碼學中被稱爲「前向安全」forward secrecy或「後向不可預測性」。直觀理解真實系統中攻擊者常有機會獲知部分內部狀態如通過內存泄漏、臨時漏洞、側信道等途徑。一個合格的 CSPRNG 在狀態被部分暴露後仍然要保證歷史輸出不泄漏。這對生成器的狀態更新函數提出了要求——狀態更新必須是單向的one-way且不同輸出之間不能存在可逆的推導關係。CSPRNG 的三大設計分類就目前而言CSPRNG 的設計可以分爲以下三類基於密碼學算法以密文或哈希值爲輸出來源例如基於分組密碼的 CTR/OFB 模式構造、基於哈希函數的迭代構造如 HMAC-DRBG。此類設計的安全性歸約到底層密碼學原語的安全性上是目前工程實現的主流如 Linux 內核 getrandom 的內部構造、各語言標準庫 CSPRNG。基於數學難題依賴某個數學問題的計算困難性典型如基於離散對數、大整數分解或格問題構造的僞隨機生成器其安全性歸約到對應數學難題。倉庫中的 離散對數、格密碼 等章節提供了這類數學難題的背景知識。某些特殊目的的設計針對特定場景如流密碼密鑰流生成而專門設計的生成器。典型的例子是基於反饋移位寄存器的構造——包括 LFSR線性反饋移位寄存器 與 NFSR非線性反饋移位寄存器以及 RC4 等特殊設計的流密碼。從 PRNG 到 CSPRNG倉庫中的判定線索理解「什麼樣的行爲會讓生成器失去 CSPRNG 資格」是 CTF 密碼題解題的關鍵能力。在 prng/intro.md 中原文總結了普通僞隨機數生成器常見的問題這些問題恰恰是「僞裝成 CSPRNG」的生成器在 CTF 中被攻破的根源在某些種子的情況下其生成的隨機數序列的週期會比較小生成大數時分配不均勻連續值之間關聯密切知道後續值可以知道之前的值直接違反「前向安全」輸出序列的值的大小很不均勻。一個生成器只要暴露出上述任一問題就無法通過 next-bit test也就不能稱爲 CSPRNG。CTF 中常見的套路正是題目使用一個「看起來很安全」的 PRNG甚至取名爲SecurePrng但其內部實質是線性同餘生成器LCG或小級數 LFSR輸出可被數學方法或暴力枚舉恢復。實戰案例一2016 Google CTF woodman——偽裝成安全 PRNG 的 LCG在 lcg/challenge.md 中題目給出了一個猜數遊戲背後的生成核心代碼如下class SecurePrng(object): def __init__(self): # generate seed with 64 bits of entropy self.p 4646704883L self.x random.randint(0, self.p) self.y random.randint(0, self.p) def next(self): self.x (2 * self.x 3) % self.p self.y (3 * self.y 9) % self.p return (self.x ^ self.y)這個生成器雖然名爲SecurePrng但它的兩個內部狀態分別是x (2x3) mod p與y (3y9) mod p的 LCG 迭代輸出只是兩者異或。它既不具備不可預測性LCG 的內部線性關係使狀態可被數學求解也完全不滿足 next-bit test。解法上猜出前兩輪相對容易概率約 0.25拿到兩輪輸出後可以使用 Z3 約束求解器還原初始的 x 和 y進而預測後續所有輸出。題解還給出了一種更精妙的從低比特位向高比特位逐位枚舉的恢復方法其核心觀察是加法、減法、乘法、取模運算中結果第 i 比特位的值只受參與運算數的該比特位及更低比特位影響僅依賴低位的進位/借位異或運算a ^ b c中c 的第 i 比特位只受 a、b 該比特位的影響。由於 p 是 33 比特可以先猜出兩次輸出再從低位到高位枚舉第一次迭代後 x 的對應比特位利用異或關係反推 y並對取模「減了多少次」進行枚舉逐步收斂出真實狀態。這種「逐比特拆解」技巧在面對由線性運算組合成的僞隨機輸出時非常通用。實戰案例二LFSR 與 NFSR 系列——小狀態空間的暴力枚舉與相關攻擊流密碼的密鑰流生成常使用反饋移位寄存器。在 lfsr.md 中LFSR 的反饋函數形式爲 $a_{in}\sum_{j1}^{n}c_ja_{in-j}$其特徵多項式與聯結多項式直接決定了序列週期與結構。n 級 LFSR 的最長週期爲 $2^n-1$排除全零狀態達到最長週期的序列稱爲 m 序列。這一數學結論直接給出了 CTF 攻擊的邊界2018 強網杯 streamgame1flag 長度僅 19 比特直接暴力枚舉即可恢復2018 CISCN 初賽 oldstreamgame初態爲 32 比特可以逐比特推導第 32 個輸出比特由前 31 個輸出比特與種子第 1 比特決定也可以用矩陣變換方法在 Sage 中求解線性方程組恢復初始狀態2018 強網杯 streamgame3採用類似 Geffe 生成器的非線性組合見 nfsr.md三個 LFSR 的輸出經非線性函數組合。由於輸出與第一個、第三個 LFSR 的相關概率均爲 0.75可以使用相關攻擊暴力枚舉第一個和第三個 LFSR 的輸出統計其與實際輸出序列的符合率接近 75% 者即爲正確狀態第二個 LFSR 再單獨暴力枚舉。這些案例共同說明只要生成器的狀態空間不夠大、狀態更新缺乏單向性或組合函數存在統計相關性它就不滿足 CSPRNG 的兩大需求攻擊者總能找到多項式時間的恢復方法。總結如何從 CTF 與工程兩個角度評判 CSPRNG歸納起來評判一個僞隨機數生成器是否「密碼學安全」可以遵循以下檢查清單能否通過 next-bit test給出任意長度前綴是否存在多項式時間算法以顯著優於 50% 的概率預測下一位若存在如 LCG 的連續性、LFSR 的線性關係則不合格是否具備前向安全狀態泄漏後歷史輸出是否仍然不可恢復若狀態更新可逆如x (2x3) mod p這類線性映射則不合格是否屬於三大設計範疇之一基於密碼學算法加密/哈希、基於數學難題、或經嚴格論證的特殊設計若只是「看起來隨機」的普通 PRNG如 Mersenne Twister、xorshift、WELL 等見 prng/intro.md 所列的通用生成器則不能用於密碼學。在 CTF 解題中這個檢查清單的反向使用尤其有效先判斷題目用到的生成器屬不屬於 CSPRNG若不屬於再根據其具體構造LCG、LFSR、組合生成器、特殊設計流密碼選擇對應的攻擊手段——Z3 約束求解、逐比特枚舉、矩陣求逆、相關攻擊或直接暴力枚舉配合本文所述的需求與分類框架即可系統化地完成此類題目。深入閱讀CSPRNG 原文本文的主體內容來源PRNG 介紹隨機性三性質、弱/強僞隨機數分類與 PRNG 常見問題流密碼介紹CSPRNG 在流密碼中的角色定位LCG 題目2016 Google CTF woodman線性同餘生成器的逐比特恢復實戰LFSR 與 NFSR反饋移位寄存器類生成器的數學基礎與強網杯、CISCN 系列賽題RC4 特殊設計流密碼另一類特殊目的設計的生成器案例。赞分享文档网络安全教程【免费下载链接】ctf-wikiCome and join us, we need you!项目地址https://gitcode.com/gh_mirrors/ct/ctf-wiki点击查看免费下载相关推荐偽隨機數生成器PRNG深度解析從隨機性定義、週期到密碼學安全CTF Wiki 密碼學專題偽隨機數生成器PRNG深度解析從隨機性定義、週期到密碼學安全CTF Wiki 密碼學專題 本文是 CTF Wiki 密碼學體系中「流密碼」分支的核心前文档网络安全教程ctf-wiki 密碼學實戰RSA 模數相關攻擊從原理到 CTF 利用ctf wiki 密碼學實戰RSA 模數相關攻擊從原理到 CTF 利用 本指南以 ctf wiki 倉庫中 rsa_module_attack.md http文档网络安全教程以太坊智能合約隨機數安全攻防ctf-wiki 區塊鏈題目中的僞隨機數利用與回滾攻擊實戰以太坊智能合約隨機數安全攻防ctf wiki 區塊鏈題目中的僞隨機數利用與回滾攻擊實戰 本篇技術指南以 ctf wiki 倉庫中 以太坊隨機數漏洞分析 htt文档网络安全教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考