劉 攀, 陳天宇, 馬 原, 吳鑫瑩, 呂 娜, 荊繼武

1. 中國科學(xué)院 信息工程研究所 信息安全國家重點(diǎn)實(shí)驗(yàn)室, 北京100093

2. 中國科學(xué)院 數(shù)據(jù)與通信保護(hù)研究教育中心, 北京100093

3. 中國科學(xué)院大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 北京100049

通信作者: 陳天宇, E-mail: chentianyu@iie.ac.cn

1 引言

隨機(jī)數(shù)發(fā)生器作為現(xiàn)代密碼學(xué)的基本原語之一, 其生成的隨機(jī)數(shù)具有廣泛的應(yīng)用, 如用于對稱或非對稱密碼算法的密鑰產(chǎn)生、“挑戰(zhàn)-響應(yīng)”協(xié)議方案中的一次性口令、電子簽名方案中的秘密信息,以及抵抗側(cè)信道分析攻擊等. 隨機(jī)數(shù)質(zhì)量的好壞直接關(guān)系到密碼算法和協(xié)議等密碼應(yīng)用的安全性. 如何產(chǎn)生高質(zhì)量的隨機(jī)數(shù)一直是密碼學(xué)領(lǐng)域長期關(guān)注的研究問題[1-9]. 按產(chǎn)生原理的不同,隨機(jī)數(shù)發(fā)生器(Random Number Generator, RNG) 主要分為非確定性隨機(jī)數(shù)發(fā)生器(NDRNG) 和確定性發(fā)生器(DRNG). NDRNG 通常是采集來自于物理或非物理現(xiàn)象的隨機(jī)性, 如電子噪聲、電磁輻射、系統(tǒng)中斷、鼠標(biāo)/鍵盤操作等, 進(jìn)而通過數(shù)字化處理等環(huán)節(jié)生成具有良好不可預(yù)測性的數(shù)據(jù); 而DRNG 則是采用確定性算法將一段隨機(jī)序列(即“種子”, 一般由NDRNG 產(chǎn)生) 擴(kuò)展成任意長度的序列. 按發(fā)生器形態(tài)分類, 又可分為硬件形態(tài)的隨機(jī)數(shù)發(fā)生器(硬件RNG) 和軟件形態(tài)的隨機(jī)數(shù)發(fā)生器(軟件RNG). 硬件RNG 通常在研制時(shí)需要投入較大的成本以實(shí)現(xiàn)生成高質(zhì)量的隨機(jī)數(shù), 并且硬件形態(tài)的產(chǎn)品更新迭代周期長. 隨著智能移動(dòng)終端、物聯(lián)網(wǎng)設(shè)備等便攜式設(shè)備的不斷普及, 以及軟件密碼模塊逐步興起和廣泛應(yīng)用, 傳統(tǒng)的硬件RNG 已不能完全滿足當(dāng)前的密碼應(yīng)用對隨機(jī)數(shù)服務(wù)的需求[10]. 因此, 以軟件形式產(chǎn)生隨機(jī)數(shù)成為各類系統(tǒng)平臺(tái)中最為常見的方法. 不同于硬件RNG, 我們將諸如運(yùn)行在Linux、Windows、Android、嵌入式操作系統(tǒng)等軟件平臺(tái)上以軟件形態(tài)呈現(xiàn)的隨機(jī)數(shù)發(fā)生器稱為軟件隨機(jī)數(shù)發(fā)生器(簡稱軟件RNG).

軟件RNG 目前已有許多較成熟的結(jié)構(gòu), 學(xué)者們對這些結(jié)構(gòu)的原理以及安全性進(jìn)行了大量深入的研究[7,11-16], 如何設(shè)計(jì)一個(gè)高質(zhì)量的軟件RNG 一直是密碼學(xué)領(lǐng)域的研究重點(diǎn). 一些研究工作為軟件RNG的設(shè)計(jì)給出了建議: Shamir 等人[1]在1983 年首次給出基于一個(gè)短的隨機(jī)種子生成偽隨機(jī)數(shù)的實(shí)例;Gutmann 等人[3]在1998 年給出了設(shè)計(jì)和實(shí)現(xiàn)一個(gè)隨機(jī)數(shù)發(fā)生器的較為全面的指南; 2005 年, Barak 等人[6]提出了一種穩(wěn)健的隨機(jī)數(shù)生成模型和架構(gòu). 此外, 一些研究工作針對典型操作系統(tǒng)平臺(tái)已有的軟件RNG 的結(jié)構(gòu)和原理等進(jìn)行了分析. Gutterman 等人[13]對Linux 內(nèi)核中的隨機(jī)數(shù)發(fā)生器結(jié)構(gòu)和安全性進(jìn)行了深入分析, 給出了Linux 內(nèi)核版本2.6.10 中的隨機(jī)數(shù)發(fā)生器結(jié)構(gòu), 并指出該版本的LRNG 無法完全滿足前向安全性等設(shè)計(jì)準(zhǔn)則. 2013 年, Strenzke 等人[14]分析了Android 中OpenSSL 所使用的隨機(jī)數(shù)發(fā)生器. 針對Windows 操作系統(tǒng)的隨機(jī)數(shù)發(fā)生器, Dorrendorf 等人[15]對Windows 內(nèi)核隨機(jī)數(shù)發(fā)生器CryptGenRandom 結(jié)構(gòu)進(jìn)行了分析, 隨后Alzhrani 等人在2015 年對Windows 內(nèi)核的隨機(jī)數(shù)發(fā)生器BCryptGenRandom 結(jié)構(gòu)進(jìn)行了研究[16]. 對于iOS、Mac 和FreeBSD 等操作系統(tǒng), 它們早期采用由Kelsey 等人設(shè)計(jì)的Yarrow 隨機(jī)數(shù)發(fā)生器[7], 隨后Ferguson 和Schneier 團(tuán)隊(duì)[17]對Yarrow 進(jìn)行了改進(jìn), 提出Fortuna 隨機(jī)數(shù)發(fā)生器, 一些操作系統(tǒng)使用Fortuna 發(fā)生器取代了Yarrow 發(fā)生器, 如FreeBSD.綜上, 本文總結(jié)了幾種典型操作系統(tǒng)平臺(tái)上軟件RNG 的基本結(jié)構(gòu)和產(chǎn)生原理, 并對隨機(jī)數(shù)生成機(jī)制進(jìn)行了對比分析. 在此基礎(chǔ)上, 進(jìn)一步梳理了軟件RNG 安全性分析的關(guān)注點(diǎn).

本文的組織結(jié)構(gòu)如下: 第2 節(jié)概述了軟件RNG 的相關(guān)知識, 包括軟件RNG 基本模型、安全性要求以及隨機(jī)數(shù)發(fā)生器安全性測試方法; 第3 節(jié)介紹了典型操作系統(tǒng)平臺(tái)上軟件RNG 的結(jié)構(gòu)和工作原理; 第4 節(jié)梳理了軟件RNG 安全性分析關(guān)注點(diǎn); 第5 節(jié)對本文研究工作進(jìn)行總結(jié).

2 相關(guān)知識

軟件RNG 的基本結(jié)構(gòu)模型. 通常來講, 基于外部熵源的軟件RNG 的基本結(jié)構(gòu)如圖1 所示, 主要包括熵源、處理函數(shù)、內(nèi)部狀態(tài)和輸出函數(shù). 熵源通過處理函數(shù)產(chǎn)生內(nèi)部狀態(tài), 通過控制條件(熵值充足的閾值、數(shù)據(jù)長度要求的閾值等) 執(zhí)行種子更新(重播種函數(shù)), 進(jìn)而完成內(nèi)部狀態(tài)的更新, 再由輸出函數(shù)產(chǎn)生隨機(jī)數(shù)據(jù). 其中:

· 熵源: 提供隨機(jī)性的來源, 又可分為兩類: 基于操作系統(tǒng)平臺(tái)的時(shí)鐘生成種子和外部隨機(jī)源提供種子, 外部隨機(jī)源有鼠標(biāo)/鍵盤的操作、網(wǎng)絡(luò)中斷、磁盤讀寫或NDRNG 提供的隨機(jī)數(shù)等.

· 處理函數(shù): 用于熵累積和更新內(nèi)部狀態(tài), 包括熵累積函數(shù)、播種(seed) 函數(shù)和重播種(reseed) 函數(shù).

· 內(nèi)部狀態(tài): 用于存儲(chǔ)軟件RNG 使用或產(chǎn)生用途的所有參數(shù)、變量和其他存儲(chǔ)值, 包括管理數(shù)據(jù)(如安全性參數(shù)), 以及在運(yùn)行期間產(chǎn)生或修改的數(shù)據(jù).

· 輸出函數(shù): 用于對內(nèi)部狀態(tài)處理以生成隨機(jī)數(shù),常使用確定性密碼算法實(shí)現(xiàn),目前的軟件RNG 中使用的輸出函數(shù)有基于CTR 模式的分組密碼算法、密碼雜湊算法等.

圖1 基于外部熵源的軟件RNG 基本結(jié)構(gòu)Figure 1 Basic structure of software RNG based on external entropy sources

隨機(jī)數(shù)發(fā)生器設(shè)計(jì)的安全性要求. 對于一個(gè)安全的系統(tǒng)而言, 如果無法獲取高質(zhì)量的隨機(jī)序列, 那么可能會(huì)導(dǎo)致致命的安全性風(fēng)險(xiǎn). 對于一個(gè)軟件形式的隨機(jī)數(shù)發(fā)生器而言, 攻擊者被假定已知隨機(jī)數(shù)發(fā)生器的所有源程序代碼, 并且可能通過一些手段, 了解隨機(jī)數(shù)發(fā)生器部分內(nèi)部狀態(tài)的更新情況. 一些標(biāo)準(zhǔn)[18]或研究工作[6,19]針對軟件RNG 的安全性要求進(jìn)行探究, 認(rèn)為設(shè)計(jì)出來的軟件RNG 需要滿足以下安全性要求:

(1) 偽隨機(jī)性: 對于一個(gè)對發(fā)生器內(nèi)部狀態(tài)一無所知的觀測者而言, 發(fā)生器的輸出應(yīng)該是看上去隨機(jī)的, 即便觀測者完全控制了用于更新內(nèi)部狀態(tài)的數(shù)據(jù), 上述結(jié)論應(yīng)仍保持不變;

(2) 前向安全性: 對于一個(gè)攻擊者而言, 即便他獲取了發(fā)生器在某一特定時(shí)刻的狀態(tài), 也不能獲知在此之前任意時(shí)刻的輸出;

(3) 后向安全性: 對于一個(gè)攻擊者而言, 即便他獲取了發(fā)生器在某一特定時(shí)刻的狀態(tài), 也不能獲知在此之后任意時(shí)刻的輸出;

(4) 健全的熵估計(jì): 發(fā)生器能夠正確估計(jì)是否已收集到足夠的熵, 以確保觀測不到輸入的攻擊者無法有效地猜測輸出.

美國國家標(biāo)準(zhǔn)與技術(shù)研究院(NIST) 在SP800-90A[18]標(biāo)準(zhǔn)中對發(fā)生器如何滿足前向/后向安全性給出了建議: 在生成隨機(jī)數(shù)的過程中通過使用具有單向性的函數(shù)可以保證前向安全性; 而后向安全性僅能通過使用足夠的熵更新內(nèi)部狀態(tài)來實(shí)現(xiàn).

隨機(jī)數(shù)發(fā)生器的檢測技術(shù). 安全性檢測對于發(fā)生器整個(gè)生命周期而言是必不可少的. 目前, 安全性檢測方法大致可分為三類: 統(tǒng)計(jì)性質(zhì)測試、理論熵估計(jì)和統(tǒng)計(jì)熵估計(jì).

統(tǒng)計(jì)性質(zhì)測試的目的是檢查隨機(jī)數(shù)發(fā)生器的輸出序列是否存在明顯的統(tǒng)計(jì)缺陷, 屬于較為傳統(tǒng)的黑盒測試. 由于這類測試并不關(guān)注隨機(jī)數(shù)生成原理和發(fā)生器內(nèi)部結(jié)構(gòu), 而是只檢測輸出序列的統(tǒng)計(jì)性質(zhì)好壞, 因此具有很好的通用性和可操作性, 但無法對不可預(yù)測性進(jìn)行有效測量. 目前, 典型的統(tǒng)計(jì)測試方法有NIST 發(fā)布的SP800-22 標(biāo)準(zhǔn)[20]、L’Ecuyer 和Simard 提出的TestU01[21]、佛羅里達(dá)州立大學(xué)Marsaglia提出的Diehard 測試[22]、德國信息安全部門BSI 的AIS 20/AIS 31[23]標(biāo)準(zhǔn)以及我國發(fā)布的國家標(biāo)準(zhǔn)GB/T 32915-2016《信息安全技術(shù) 二元序列隨機(jī)性檢測方法》[24].

理論熵估計(jì)從隨機(jī)數(shù)發(fā)生器的結(jié)構(gòu)和工作原理出發(fā), 建立一套基于數(shù)學(xué)建模的白盒檢測方法. 相比于基于統(tǒng)計(jì)性質(zhì)的黑盒測試, 理論熵估計(jì)是通過數(shù)學(xué)建模的方式對特定結(jié)構(gòu)發(fā)生器的工作原理進(jìn)行刻畫, 然后通過熵計(jì)算來量化發(fā)生器輸出所含有的隨機(jī)性大小. 目前, 理論熵估計(jì)方法的研究尚集中在通用基礎(chǔ)結(jié)構(gòu)上, 如振蕩采樣結(jié)構(gòu). 對該結(jié)構(gòu)的熵估計(jì)研究主要圍繞兩個(gè)角度: 基于時(shí)間演變[25-27]和基于相位演變[28-30], 而二者在實(shí)質(zhì)上是具有等價(jià)性的, 只是衡量方法不同. 不過, 理論熵估計(jì)方法由于屬于白盒測試,對于特定結(jié)構(gòu)建立的模型的適用性十分有限, 并且有些發(fā)生器結(jié)構(gòu)尚未發(fā)現(xiàn)有合適的建模方法, 如基于混沌的NDRNG[31-33].

統(tǒng)計(jì)熵估計(jì)介于白盒測試和黑盒統(tǒng)計(jì)測試之間, 既遵從了利用“熵” 來量化輸出序列隨機(jī)性的檢測理念, 又采用統(tǒng)計(jì)測試方式使得測試過程通用化、簡潔化. 目前, 這類測試方法中的典型是NIST SP800-90B(簡稱90B) 標(biāo)準(zhǔn)[34], 對于非獨(dú)立同分布的數(shù)據(jù)而言, 90B 包含10 個(gè)計(jì)算待測序列隨機(jī)性(熵) 的熵估計(jì)器. 待測數(shù)據(jù)的熵是取10 個(gè)熵估計(jì)器計(jì)算結(jié)果的最小值. 當(dāng)待測試熵源的統(tǒng)計(jì)性質(zhì)(比如周期性) 符合或近似90B 測試包中某一項(xiàng)檢測的預(yù)期時(shí), 則通過90B 檢測可以得到較為準(zhǔn)確的熵估計(jì)結(jié)果.

3 基于通用平臺(tái)的軟件隨機(jī)數(shù)發(fā)生器

軟件形式的隨機(jī)數(shù)發(fā)生器廣泛應(yīng)用于PC 平臺(tái)和移動(dòng)終端平臺(tái). 下面, 將對Linux、Android、Windows、iOS 等典型操作系統(tǒng)平臺(tái)的軟件隨機(jī)數(shù)發(fā)生器的基本結(jié)構(gòu)和原理進(jìn)行介紹, 并對它們的實(shí)現(xiàn)機(jī)制進(jìn)行對比分析.

3.1 Linux 平臺(tái)軟件隨機(jī)數(shù)發(fā)生器

Linux 是目前最流行的開源項(xiàng)目之一, Linux 操作系統(tǒng)的隨機(jī)數(shù)發(fā)生器(LRNG) 是所有Linux 發(fā)行版內(nèi)核的一部分. LRNG 最早由Theodore Ts’o 在1994 年設(shè)計(jì)實(shí)現(xiàn), 其設(shè)計(jì)思想是基于操作系統(tǒng)事件的隨機(jī)性來生成隨機(jī)數(shù), 它的輸出幾乎用于所有的安全協(xié)議中, 如TLS/SSL 密鑰生成、TCP 的序列號生成、文件系統(tǒng)和電子郵件加密.

在2006 年, Gutterman 等人[13]開展了對LRNG 實(shí)現(xiàn)的分析(針對2004 年12 月24 日發(fā)布的Linux 內(nèi)核2.6.10 版本), 并給出了該內(nèi)核版本下LRNG 的通用架構(gòu)(見圖2). LRNG 生成隨機(jī)數(shù)主要由三個(gè)異步過程組成: (1) 采集作為熵源的系統(tǒng)事件, 從內(nèi)核內(nèi)部的各種事件收集系統(tǒng)熵(圖2 中的C), 系統(tǒng)事件包括鼠標(biāo)移動(dòng)、鍵盤操作、磁盤I/O、中斷; (2)對采集到的熵源數(shù)據(jù)進(jìn)行熵估計(jì)量化, 調(diào)用Add 函數(shù)將采集的熵增加到熵池中并更新熵池內(nèi)部狀態(tài)(圖2 中的A); (3) 響應(yīng)外部請求產(chǎn)生隨機(jī)數(shù), 調(diào)用Extract函數(shù)(圖2 中的E) 從熵池中提取熵并更新熵池內(nèi)部狀態(tài). 上述三個(gè)過程使用的唯一非線性密碼運(yùn)算是SHA-1 密碼雜湊算法. LRNG 的內(nèi)部狀態(tài)保存在三個(gè)熵池中, 包括圖2 中的主熵池(大小為512 字節(jié))、阻塞熵池(大小為128 字節(jié)) 和非阻塞熵池(大小為128 字節(jié)), 每個(gè)熵池都有一個(gè)熵值計(jì)數(shù)器(計(jì)數(shù)器值的類型為整數(shù), 取值范圍為[0, 熵池大小]). 熵源事件經(jīng)過量化和熵估計(jì)過程后, 會(huì)先將熵源數(shù)據(jù)加入主熵池; 當(dāng)主熵池熵滿時(shí), 將熵源數(shù)據(jù)加入阻塞熵池; 當(dāng)阻塞熵池熵滿時(shí), 再將熵源數(shù)據(jù)添加到主熵池, 按此順序循環(huán)將熵源數(shù)據(jù)添加入熵池. 對于這三個(gè)任意熵池, 當(dāng)有數(shù)據(jù)加入時(shí), 那么該熵池的熵值計(jì)數(shù)器值將相應(yīng)的增加; 反之則減少.

根據(jù)圖2 所示, LRNG 提供了三個(gè)隨機(jī)數(shù)輸出接口, 包括/dev/random、/dev/urandom 和get_random_bytes(). 其中, get_random_bytes() 僅在內(nèi)核內(nèi)部可用, 并且總是會(huì)返回請求的隨機(jī)數(shù)據(jù); 而/dev/random 和/dev/urandom 是從用戶空間訪問, 即便是非授權(quán)的用戶. /dev/random 接口對外提供的隨機(jī)數(shù)來源于阻塞熵池?cái)?shù)據(jù), 它輸出一個(gè)相對安全的隨機(jī)數(shù). 阻塞熵池每次在輸出隨機(jī)數(shù)之前, 會(huì)先檢查熵值計(jì)數(shù)器的值, 查看是否滿足輸出條件(即當(dāng)前熵值不小于請求的隨機(jī)比特長度), 若不滿足, 則調(diào)用Extract 函數(shù)從主熵池提取新數(shù)據(jù); 如果提取失敗, 則阻塞/dev/random 的請求. /dev/urandom 接口對外提供的隨機(jī)數(shù)來自非阻塞熵池?cái)?shù)據(jù), 從主熵池向非阻塞熵池傳輸數(shù)據(jù)的條件是主熵池?cái)?shù)據(jù)的熵值至少為192 比特. 只要非阻塞熵池不為空, 那么/dev/urandom 可以持續(xù)向用戶提供請求的隨機(jī)數(shù)據(jù).

圖2 早期內(nèi)核版本的Linux 隨機(jī)數(shù)發(fā)生器通用架構(gòu)Figure 2 General architecture of Linux random number generator of early kernel version

下面對早期內(nèi)核版本的LRNG 運(yùn)行機(jī)制的關(guān)鍵環(huán)節(jié)進(jìn)行介紹.

系統(tǒng)啟動(dòng)階段: LRNG 在計(jì)算機(jī)關(guān)機(jī)時(shí)會(huì)激活一個(gè)腳本, 這個(gè)腳本從/dev/urandom 中讀取512 個(gè)字節(jié)數(shù)據(jù)并將其寫到一個(gè)種子文件中保存起來. 當(dāng)系統(tǒng)再次啟動(dòng)時(shí), 腳本被重新激活, 把保存的512 字節(jié)數(shù)據(jù)再寫回到/dev/urandom. 通過這個(gè)操作, 使得關(guān)機(jī)和開機(jī)之間存在了一種延續(xù)性, 腳本文件的加入是為了確保Linux 啟動(dòng)時(shí)LRNG 內(nèi)部狀態(tài)的安全性.

熵采集: LRNG 采集四種熵源數(shù)據(jù), 分別為鼠標(biāo)移動(dòng)、鍵盤操作、硬盤I/O 操作和特殊中斷. 當(dāng)熵源事件發(fā)生時(shí), 系統(tǒng)會(huì)生成兩個(gè)32 比特字. 第一個(gè)字代表事件發(fā)生的時(shí)間; 第二個(gè)字代表事件類型, 通常是對鍵盤按鍵或鼠標(biāo)移動(dòng)等事件類型的編碼.

熵估計(jì): LRNG 利用熵源事件發(fā)生的時(shí)間來計(jì)算熵值, 其具體步驟如下:

熵池更新以及隨機(jī)數(shù)輸出: 內(nèi)核通過調(diào)用Add(pool,j,g) 函數(shù)來實(shí)現(xiàn)熵增加和熵池內(nèi)部狀態(tài)更新.其中, pool 表示哪個(gè)熵池將會(huì)加入新熵,j是該熵池中當(dāng)前位置的索引,g表示要加入熵池的數(shù)據(jù). LRNG通過調(diào)用Extract(pool, nbytes,j) 函數(shù)來提取隨機(jī)比特, 其中, pool 為待提取數(shù)據(jù)的熵池, nbytes 為要提取的隨機(jī)比特長度,j為當(dāng)前熵池中位置的索引, 每輪循環(huán)輸出10 字節(jié). 當(dāng)阻塞熵池和非阻塞熵池需要更新內(nèi)部狀態(tài)時(shí), 調(diào)用Extract 函數(shù)從主熵池提取數(shù)據(jù)加入到對應(yīng)熵池中.

隨著Linux 操作系統(tǒng)計(jì)算環(huán)境的變化和技術(shù)的演變, LRNG 在Linux 內(nèi)核版本4.8 中開始引入ChaCha20 DRNG 配合生成隨機(jī)數(shù). Müller 等人[35]從2018 年開始對不同內(nèi)核版本的LRNG 的實(shí)現(xiàn)機(jī)制和安全性進(jìn)行分析, 截止到2020 年4 月已遍歷了Linux 內(nèi)核版本從4.15 到5.5. 當(dāng)前, LRNG 的最新架構(gòu)如圖3 所示, LRNG 維護(hù)了兩個(gè)不同的熵池(blocking_pool 和input_pool, 而fast_pool 被認(rèn)為屬于中斷噪聲源) 和一個(gè)ChaCha20 DRNG 來收集、壓縮和熵保持, 以及五類熵源.

圖3 中熵池和ChaCha20 DRNG 與熵源之間的相互關(guān)系如下:

(1) 輸入熵池(input_pool): 輸入熵池是主要熵池, 它收集并壓縮來自硬件事件的熵, 熵池大小默認(rèn)為512 字節(jié), 主要目的是將采集的熵提供給阻塞熵池和ChaCha20 DRNG.

圖3 Linux 隨機(jī)數(shù)發(fā)生器新的架構(gòu)Figure 3 New architecture of Linux random number generator

(2) 阻塞熵池(blocking_pool): 也稱輸出熵池, 阻塞熵池從輸入熵池獲取真隨機(jī)數(shù)據(jù). 在用戶空間,可以通過/dev/random 設(shè)備文件接口或者帶有GRND_RANDOM 標(biāo)志的getrandom()系統(tǒng)調(diào)用訪問, 該熵池大小為1024 字節(jié).

(3) ChaCha20 DRNG: 從輸入熵池獲取種子數(shù)據(jù), 其內(nèi)部狀態(tài)為 512 比特, 而只有 256 比特(ChaCha20 的關(guān)鍵部分) 是由真隨機(jī)數(shù)據(jù)填充. 從用戶空間, 可以通過/dev/urandom 或者不帶標(biāo)志的getrandom() 系統(tǒng)調(diào)用訪問; 在內(nèi)核空間, 可以通過get_random_bytes() 函數(shù)訪問.

(4) 熵源: 共有五種熵源, 各個(gè)熵源的特征如下:

(a) 設(shè)備驅(qū)動(dòng)程序可以通過add_device_randomness API 提取設(shè)備驅(qū)動(dòng)程序開發(fā)者認(rèn)為包含某些隨機(jī)性的數(shù)據(jù), LRNG 采集該類熵源數(shù)據(jù)但并不計(jì)算和統(tǒng)計(jì)其熵值, 而只是為了用于混淆內(nèi)部狀態(tài);

(b) Linux 內(nèi)核為硬件隨機(jī)數(shù)發(fā)生器實(shí)現(xiàn)了驅(qū)動(dòng)程序, 這些硬件隨機(jī)數(shù)發(fā)生器可以通過add_hwgenerator_randomness API 提供真隨機(jī)數(shù)據(jù), 該類硬件隨機(jī)數(shù)發(fā)生器只有在特定的設(shè)備中可用, 即并不是所有的硬件設(shè)備都有此類硬件隨機(jī)數(shù)發(fā)生器;

(c) 用戶輸入設(shè)備(如鍵盤、鼠標(biāo)等) 可以通過add_input_randomness API 提取熵, 像按鍵或鼠標(biāo)移動(dòng)等事件所獲得的數(shù)據(jù)在事件到達(dá)時(shí)同時(shí)使用add_timer_randomness 函數(shù)獲取時(shí)間戳作為補(bǔ)充熵源;

(d) 通過add_disk_randomness API 獲取硬件設(shè)備事件(如硬盤的讀寫操作) 的隨機(jī)性, 與用戶輸入設(shè)備熵源相似, LRNG 通過調(diào)用add_timer_randomness 函數(shù)為每個(gè)磁盤事件添加一個(gè)時(shí)間戳, 需要注意的是, 并不是所有的設(shè)備都有硬盤, 如果使用固態(tài)驅(qū)動(dòng)器(如SSD), 那么此情況下將不提供熵;

(e) 當(dāng)中斷到達(dá)時(shí), LRNG 會(huì)被add_interrupt_randominess API 觸發(fā), 對于每個(gè)接收到的中斷, LRNG 會(huì)獲得一個(gè)時(shí)間戳和補(bǔ)充數(shù)據(jù), 并將這些數(shù)據(jù)輸入到處理中斷的CPU 所在的快熵池(fast_pool). 為了保持性能, 需要使用fast_pool 而不是直接將數(shù)據(jù)注入到input_pool中. 因?yàn)? 接收和處理中斷是性能非常關(guān)鍵的代碼路徑, 正常的工作負(fù)載每秒會(huì)觸發(fā)數(shù)百到數(shù)千個(gè)中斷, 而復(fù)雜的操作會(huì)顯著降低系統(tǒng)性能.

上述列出的熵池(輸入熵池和阻塞熵池) 都可以看作是獨(dú)立的隨機(jī)數(shù)發(fā)生器. 其中, 輸入熵池與熵源一同構(gòu)成一個(gè)NDRNG; 阻塞熵池可以看作是一個(gè)獨(dú)立的DRNG, 并通過輸入熵池進(jìn)行播種; ChaCha20 DRNG 是第三個(gè)隨機(jī)數(shù)發(fā)生器, 也是通過輸入熵池進(jìn)行播種. 輸入熵池只會(huì)將數(shù)據(jù)輸入到阻塞熵池或者ChaCha20 DRNG,也就是說使用者無法直接從輸入熵池獲取數(shù)據(jù). 從圖2 到圖3 的演變可以看出, LRNG在實(shí)現(xiàn)架構(gòu)上發(fā)生了顯著的變化, 而這種變化的最終目的是為了產(chǎn)生更安全的隨機(jī)數(shù).

3.2 Android 平臺(tái)軟件隨機(jī)數(shù)發(fā)生器

2013 年, Kim 等人[36]針對操作系統(tǒng)版本為Android ICS 4.0.4 (內(nèi)核版本為3.0.15) 的內(nèi)核PRNG和基于此實(shí)現(xiàn)的OpenSSL PRNG (簡稱APRNG) 的原理進(jìn)行了分析, 并以生成SSL 連接過程中的nonce 值為例, 給出APRNG 生成隨機(jī)數(shù)的主要過程(見圖4). 根據(jù)圖4 可以看出, 在隨機(jī)數(shù)生成的過程中, 每個(gè)環(huán)節(jié)的主要熵源數(shù)據(jù)如下:

(1) LRNG: utsname、ktime 和CBN. utsname 包含有關(guān)系統(tǒng)和內(nèi)核的信息, 共六個(gè)元素, 包括sysname、nodename、domainname、芯片和內(nèi)核的版本、編譯內(nèi)核的時(shí)間. 因此, 如果在同一時(shí)間段內(nèi)發(fā)布這些元件, 那么這些元件信息是相同的. ktime 是系統(tǒng)啟動(dòng)后的納秒級時(shí)間; CBN(Comuputed Block Number) 定義為從系統(tǒng)啟動(dòng)到啟動(dòng)Zygote 初始化期間, 在/dev/urandom中計(jì)算的隨機(jī)分組總數(shù)(每個(gè)分組10 字節(jié)), 該值取決于設(shè)備型號、操作系統(tǒng)版本和通信提供商,通常在100 到250 之間.

(2) Zygote: UID、PID、Time 和Buffer. 其中,UID 為應(yīng)用程序ID,源碼中是4 字節(jié),但在Android中設(shè)置為0; PID 為應(yīng)用進(jìn)程ID, 根據(jù)應(yīng)用程序運(yùn)行的順序, 按順序分配, PID 在源碼中有15比特的復(fù)雜度, 然而Android 的初始化流程和廠商內(nèi)置的應(yīng)用是按順序執(zhí)行, 因此Zygote PID小于3000, 并且對于相同型號的設(shè)備PID 接近固定值. Time 是指gmt_unix_time(UNIX 時(shí)間戳), 單位為秒, 由于應(yīng)用程序的時(shí)間幾乎等于ClientHello 包中的時(shí)間, 因此可以對該時(shí)間值進(jìn)行準(zhǔn)確的預(yù)測. 一旦系統(tǒng)啟動(dòng), Zygote 模塊也會(huì)啟動(dòng), 因此Zygote Time 可以近似等于系統(tǒng)啟動(dòng)時(shí)間. Buffer 是RAM 中存儲(chǔ)的RAND_byte() 輸出的現(xiàn)有值, 它的復(fù)雜性取決于在調(diào)用RAND_byte() 的函數(shù)中如何對其進(jìn)行定義和初始化. 用于生成ClientHello nonce 的Buffer 初始化為零, 因此可以將其視為一個(gè)常數(shù).

(3) Application APRNG: PID、Time 和Buffer, 其含義與(2) 中相同.

APRNG 在Android 平臺(tái)應(yīng)用廣泛, Android 繼承于Linux, 它的內(nèi)核PRNG 是基于LRNG 實(shí)現(xiàn),從上述三種熵源可以看出主要以LRNG 的/dev/urandom 接口的輸出作為主要熵源, 但對于Android 終端而言, 其缺少像PC 平臺(tái)中LRNG 的部分熵源, 如鼠標(biāo)移動(dòng)、磁盤操作等. 因此, APRNG 的熵源的隨機(jī)性高度依賴系統(tǒng)啟動(dòng)時(shí)從Android 內(nèi)核PRNG(dev/urandom) 中讀取的數(shù)據(jù).

圖4 Android OpenSSL 隨機(jī)數(shù)發(fā)生器Figure 4 Android OpenSSL random number generator

APRNG 的主要接口函數(shù)包括: RAND_poll()、RAND_add() 和 RAND_byte(). 其中, RAND_poll() 使用熵源數(shù)據(jù)初始化隨機(jī)數(shù)發(fā)生器的內(nèi)部狀態(tài), 從操作系統(tǒng)隨機(jī)源 (例如,Linux 的/dev/urandom 設(shè)備、UID、PID 和 Time 等) 提取熵并將其添加到隨機(jī)數(shù)發(fā)生器中;RAND_add(Buf,N,Entropy), 將Buf 數(shù)組中N 字節(jié)數(shù)據(jù)混合到APRNG 中, Entropy 代表Buf 數(shù)據(jù)的熵估計(jì)值; RAND_byte(Buf,N), 生成N 字節(jié)的隨機(jī)數(shù)并加入到Buf 數(shù)組中.

近年來, 隨著移動(dòng)智能終端的快速發(fā)展, 移動(dòng)智能終端逐漸配備越來越多的傳感器(如加速度計(jì)、磁力計(jì)、陀螺儀、環(huán)境溫度/濕度傳感器等), 這些傳感器可以采集移動(dòng)設(shè)備周邊環(huán)境和設(shè)備用戶行為等信息,而這些數(shù)據(jù)具有一定的不確定性. 由于該方法不需要額外的硬件支持, 與移動(dòng)智能終端具有高度融合, 因此國外的一些研究工作開始關(guān)注于從移動(dòng)智能終端(如Android 移動(dòng)智能終端) 傳感器所采集的數(shù)據(jù)中提取隨機(jī)性來生成隨機(jī)數(shù)[37-39].

3.3 Windows 平臺(tái)軟件隨機(jī)數(shù)發(fā)生器

Windows 操作系統(tǒng)密碼庫提供了一些Windows 應(yīng)用程序開發(fā)人員可以使用的功能, 像加解密、密鑰存儲(chǔ)、雜湊函數(shù)、簽名、隨機(jī)數(shù)生成等. Crypto API (CAPI) 及其隨機(jī)數(shù)生成機(jī)制是在Windows XP和更早版本的Windows 系統(tǒng)中引入的(Windows 95 中首次引入). Crypto API 中的隨機(jī)數(shù)生成函數(shù)CryptGenRandom 使用了四個(gè)SHA-1 函數(shù), 這些函數(shù)通過系統(tǒng)熵進(jìn)行播種[15]. 內(nèi)部生成器函數(shù)使用RC4 密碼算法向用戶端發(fā)送生成的隨機(jī)數(shù), 并使用MD4 密碼雜湊算法接收用戶提供的附加熵. 由于在Windows XP 和Windows 2000 的WRNG 中發(fā)現(xiàn)嚴(yán)重漏洞, 促使微軟在Windows Vista、Windows 8等新版本的系統(tǒng)中引入了一個(gè)新的密碼庫CNG (Cryptography API: Next Generation)[40]. Gutterman等人[15]的研究給出了CNG 的整體架構(gòu)(見圖5), 主要由BCrypt 和NCrypt 組成, 其中BCrypt 提供密碼原語(如隨機(jī)數(shù)發(fā)生器、雜湊函數(shù)、簽名、加解密等), 支持用戶模式和內(nèi)核模式; NCrypt 提供密鑰存儲(chǔ)功能, 僅支持用戶模式. 基于BCrypt 的新的隨機(jī)數(shù)生成函數(shù)BCryptGenRandom 為基于CTR 模式的分組密碼算法實(shí)現(xiàn)的DRNG.

圖5 CNG 的整體結(jié)構(gòu)Figure 5 Whole structure of CNG

CNG 函數(shù)和接口位于內(nèi)核和用戶模式, CNG.SYS 是位于內(nèi)核模式的一個(gè)密碼模塊, 為Windows內(nèi)核組件和內(nèi)核模式的應(yīng)用提供密碼服務(wù). 2015 年, 在Alzhrani 等人[16]的研究工作中給出了有關(guān)Windows 8 中CNG 隨機(jī)數(shù)生成機(jī)制較為詳細(xì)的介紹. 在Windows 8 中,內(nèi)核模式的密碼庫CNG.SYS(如圖6 所示) 可以通過四個(gè)邏輯接口訪問, 包括CNG BCrypt、Legacy API、SystemPrng Interface 和Entropy API. Entropy API 邏輯接口用于采集由熵源產(chǎn)生的真隨機(jī)數(shù)據(jù), 為CNG.SYS 中的DRNG 提供熵. CNG.SYS 產(chǎn)生的隨機(jī)數(shù)用作用戶或內(nèi)核PRNG 的種子, 并通過SystemPrng 邏輯接口提供. 相比于CryptGenRandom 函數(shù), BCryptGenRandom 除了采集系統(tǒng)數(shù)據(jù)作為熵源外, 也支持采集寄存器數(shù)據(jù)、可信平臺(tái)模塊(TPM) 生成的數(shù)據(jù)(如果TPM 可用)、系統(tǒng)時(shí)間、RDRAND CPU 指令輸出的隨機(jī)數(shù)(如果CPU 支持) 等作為熵源.

圖6 CNG 邊界Figure 6 CNG boundaries

文獻(xiàn)[16] 中給出Windows 8 系統(tǒng)在啟動(dòng)階段和運(yùn)行階段的熵生成方法: (1) 系統(tǒng)啟動(dòng)階段: 啟動(dòng)時(shí), 通過Windows 操作系統(tǒng)加載程序獲得一個(gè)初始熵值, 采集的熵源包括: 寄存器值、TPM 生成的隨機(jī)數(shù)(如果TPM 可用)、當(dāng)前系統(tǒng)時(shí)間、OEM0 ACPI 表內(nèi)容、RDRAND CPU 指令的輸出(如果設(shè)備支持)、UEFI 隨機(jī)數(shù)發(fā)生器輸出(如果從UEFI 固件啟動(dòng))、CPU 計(jì)時(shí)和管理員提供的注冊表值的可選內(nèi)容. 然后, 通過SHA-512 對采集的原始熵源數(shù)據(jù)進(jìn)行處理. (2) 啟動(dòng)后運(yùn)行階段: 除啟動(dòng)階段的熵源數(shù)據(jù)外, Windows 熵池同時(shí)填充其他三個(gè)額外熵源數(shù)據(jù): 高精度CPU 時(shí)鐘計(jì)數(shù)器值、TPM 輸出、RARAND CPU 指令, 這三類熵源數(shù)據(jù)被輸入到熵池但不使用雜湊函數(shù). 由于Windows 系統(tǒng)的源碼不公開, 因此關(guān)于Windows RNG 的相關(guān)研究較少. 2019 年10 月, 微軟發(fā)布了一項(xiàng)有關(guān)Windows 10 RNG 簡要介紹的白皮書[41], 據(jù)該白皮書介紹, Windows 10 RNG 的重播種機(jī)制如下: 在系統(tǒng)啟動(dòng)時(shí), 第一次初始化種子是在系統(tǒng)啟動(dòng)后1 秒執(zhí)行, 后面每次重播種的時(shí)間間隔是原來的三倍, 即在后續(xù)的第3 秒、第9 秒、第27 秒等都會(huì)進(jìn)行重播種操作, 時(shí)間間隔不斷增加直到達(dá)到閾值, 目前該閾值是3600 秒(1 小時(shí)). 此外, 與Linux RNG 一樣, Windows RNG 的輸出函數(shù)也是基于CTR 模式的AES 分組密碼算法實(shí)現(xiàn)的DRNG(遵循NIST SP800-90A 標(biāo)準(zhǔn)).

3.4 其他平臺(tái)軟件隨機(jī)數(shù)發(fā)生器

Yarrow 隨機(jī)數(shù)發(fā)生器由Kelsey 等人[7]提出, 應(yīng)用于iOS、Mac 和FreeBSD 等操作系統(tǒng)上. 由于Yarrow 隨機(jī)數(shù)發(fā)生器輸出序列的質(zhì)量在很大程度上依賴于熵估計(jì)方法的準(zhǔn)確性, 為此Viega 等人[17]在Yarrow 的基礎(chǔ)上, 選擇去掉了熵估計(jì)環(huán)節(jié), 通過多熵池來保證至少有一個(gè)熵池積累足夠的熵來提供安全性, 提出了Fortuna 隨機(jī)數(shù)發(fā)生器. 下面介紹Yarrow 和Fortuna 隨機(jī)數(shù)發(fā)生器的基本結(jié)構(gòu)和設(shè)計(jì)思想.

3.4.1 Yarrow 隨機(jī)數(shù)發(fā)生器

Yarrow 隨機(jī)數(shù)發(fā)生器的基本框架如圖7 所示, 其產(chǎn)生隨機(jī)數(shù)主要包括以下三個(gè)環(huán)節(jié): (1) 熵采集器采集熵源數(shù)據(jù)并添加入熵池(包含快熵池和慢熵池) 中, 熵池統(tǒng)計(jì)同種熵源事件類型的熵值; (2) 重播種控制器檢查熵池?cái)?shù)據(jù)熵值是否達(dá)到閾值, 若達(dá)到, 則執(zhí)行重播種操作產(chǎn)生新的密鑰; (3) 輸出單元產(chǎn)生請求所需長度的隨機(jī)數(shù).

圖7 Yarrow 隨機(jī)數(shù)發(fā)生器的基本框架Figure 7 General framework of Yarrow random number generator

下面對Yarrow 隨機(jī)數(shù)發(fā)生器的各個(gè)組件功能進(jìn)行介紹.

熵采集: Yarrow RNG 的熵源包括鍵盤/鼠標(biāo)操作、網(wǎng)絡(luò)數(shù)據(jù)包到達(dá)時(shí)間等隨機(jī)事件. 熵采集器先從熵源收集數(shù)據(jù)并對熵源數(shù)據(jù)進(jìn)行雜湊運(yùn)算, 再將處理后的數(shù)據(jù)交替放入Yarrow RNG 的兩個(gè)熵池中(快熵池和慢熵池). 其中, 快熵池提供密鑰的頻繁重播種, 當(dāng)熵估計(jì)較準(zhǔn)確時(shí), 快熵池可以確保密鑰泄露時(shí)間盡可能的短; 慢熵池提供一種相對保守的密鑰重播種方案, 即便出現(xiàn)高估熵的情形, 慢熵池仍可以做到其聲稱安全的重播種.

熵估計(jì): Yarrow 隨機(jī)數(shù)發(fā)生器沒有直接指定具體的熵估計(jì)方法, 只提供了熵測量的總體方案. 對熵源數(shù)據(jù)分別應(yīng)用三種熵測量方法: (1) 第一種方法是系統(tǒng)內(nèi)置熵源事件的熵估計(jì)值, 如定義鼠標(biāo)移動(dòng)事件的熵值是4 比特; (2) 第二種方法是用專門的熵估計(jì)器來估計(jì)熵值; (3) 第三種方法是將熵源數(shù)據(jù)長度乘以一個(gè)小于1 的常數(shù)因子(文獻(xiàn)[7] 中建議為0.5) 的值作為熵估計(jì)值. 最后, 比較這三種測量方法得到的熵值,將最小值作為熵估計(jì)的最終值.

重播種: 用于更新熵池, 以免密鑰泄露使隨機(jī)數(shù)發(fā)生器的內(nèi)部狀態(tài)受到安全威脅. 對Yarrow 發(fā)生器而言, 如果快熵池中任何一種熵源的熵累加值達(dá)到閾值, 則進(jìn)行重播種操作, 即使用當(dāng)前密鑰和快熵池?cái)?shù)據(jù)來產(chǎn)生新的密鑰; 如果慢熵池有任意k類熵源的熵累加值達(dá)到閾值, 則進(jìn)行重播種操作, 此時(shí)使用當(dāng)前密鑰、快熵池?cái)?shù)據(jù)和慢熵池?cái)?shù)據(jù)來產(chǎn)生新的密鑰. 以Yarrow-160 為例, 快熵池閾值是100 比特, 慢熵池重播種操作要求至少兩種熵源的熵累加值都達(dá)到160 比特. 重播種操作結(jié)束后, 需要將對應(yīng)熵池中熵估計(jì)值重置為0. Yarrow-160 使用SHA-1 算法對滿足重播種條件的熵池?cái)?shù)據(jù)進(jìn)行運(yùn)算.

輸出單元: Yarrow 發(fā)生器輸出單元是基于CTR 模式的3DES 密碼算法實(shí)現(xiàn), 并設(shè)置了輸出門限, 即記錄已輸出的隨機(jī)數(shù)組數(shù). 當(dāng)輸出單元的輸出組數(shù)達(dá)到輸出門限時(shí), 將隨機(jī)數(shù)發(fā)生器下一步輸出的K比特作為新密鑰. 以Yarrow-160 為例, 輸出單元的輸出門限為10.

3.4.2 Fortuna 隨機(jī)數(shù)發(fā)生器

Fortuna 隨機(jī)數(shù)發(fā)生器生成隨機(jī)數(shù)包含三個(gè)主要過程: (1) 計(jì)算機(jī)重啟時(shí), 讀取種子文件內(nèi)容作為發(fā)生器初始的內(nèi)部狀態(tài), 確保啟動(dòng)時(shí)發(fā)生器能夠正常生成隨機(jī)數(shù); (2) 熵采集器采集熵源事件數(shù)據(jù)并將其添加到熵池中; (3) 輸出單元生成隨機(jī)數(shù), 輸出單元會(huì)檢查是否滿足重播種條件, 若滿足, 則執(zhí)行重播種操作并更新密鑰; 若不滿足, 則不更新密鑰; (4) 最后將密鑰和計(jì)數(shù)器值作為CTR 模式分組密碼算法的輸入來生成隨機(jī)數(shù). Fortuna 發(fā)生器為每種熵源設(shè)定編號(范圍從0 到255), 該發(fā)生器包含32 個(gè)熵池, 熵池編號依次從0 到31, 記作P0,P1,··· ,P31. 下面對Fortuna 發(fā)生器的關(guān)鍵功能組件的工作原理進(jìn)行介紹.

啟動(dòng)階段: 每次重啟計(jì)算機(jī)時(shí), 直接讀種子文件來初始化發(fā)生器內(nèi)部狀態(tài). 從安全角度考慮, 種子文件需要更新. 最簡單的辦法是當(dāng)計(jì)算機(jī)關(guān)機(jī)時(shí), 將發(fā)生器內(nèi)部狀態(tài)寫入種子文件. 但由于機(jī)器可能出現(xiàn)異常關(guān)閉情形, 所以發(fā)生器需要在固定時(shí)間間隔內(nèi)重寫種子文件, 例如, 每隔十分鐘重寫種子文件. 當(dāng)?shù)谝淮螁?dòng)發(fā)生器時(shí), 沒有種子文件用于重播種操作, 例如, 剛出廠的計(jì)算機(jī)需要發(fā)生器生成初始管理密鑰, 但同一工廠批量生產(chǎn)的同一型號計(jì)算機(jī)的配置相同, 并且裝載了相同的數(shù)據(jù). 為了增加安全性, 這些裝載數(shù)據(jù)不能當(dāng)作隨機(jī)數(shù)發(fā)生器的初始狀態(tài), 只能累積足夠的熵源數(shù)據(jù)來觸發(fā)重播種操作, 這可能需要很長時(shí)間. 在這種情況下, Viega 等人建議用外部隨機(jī)源來創(chuàng)建初始種子文件, 如軟件安裝期間讓測試人員移動(dòng)鼠標(biāo)來收集初始熵源數(shù)據(jù).

熵采集: Fortuna 發(fā)生器最多允許256 種熵源事件, 如用戶鼠標(biāo)/鍵盤操作、麥克風(fēng)采集的噪聲等, 將收集來的熵源數(shù)據(jù)添加到32 個(gè)熵池中. 最簡單的方案是由熵采集器決定熵源數(shù)據(jù)加入哪個(gè)熵池, 但這種方案存在安全隱患, 因?yàn)樾枰{(diào)用某些函數(shù)把事件傳遞給采集器, 攻擊者可能也會(huì)對這些函數(shù)做額外調(diào)用.為保證每種熵源數(shù)據(jù)在熵池中分布更均勻, Fortuna 熵采集器將采集到的每種熵源數(shù)據(jù)循環(huán)添加到32 個(gè)熵池中.

重播種操作: 相比于Yarrow 發(fā)生器, Fortuna 采取了新的重播種策略來更新內(nèi)部狀態(tài). 進(jìn)行重播種的條件是第一個(gè)熵池P0中數(shù)據(jù)長度大于設(shè)定的最小熵池空間(一般是64 字節(jié)), 并且距離上一次重播種時(shí)間超過100 毫秒, 當(dāng)這兩個(gè)條件同時(shí)滿足時(shí), 則執(zhí)行重播種操作. 具體重播種規(guī)則如下: 將重播種操作編號記作r, 熵池編號記作i. 當(dāng)2i整除r, 則熵池i包含在第r次重播種操作中. 由此可知,P0每次都參與重播種,P1每隔一次參與重播種,P2每隔四次參與重播種. 每一次完成重播種操作后, 清空參與重播種熵池的數(shù)據(jù).

輸出單元: 輸出單元通過基于CTR 模式的分組密碼算法計(jì)算后生成隨機(jī)數(shù), 內(nèi)部狀態(tài)包含256 比特的分組密鑰和128 比特的計(jì)數(shù)器. 當(dāng)外部請求生成隨機(jī)數(shù)時(shí), 輸出單元調(diào)用密碼算法生成偽隨機(jī)數(shù). 在每個(gè)請求完成后, 輸出單元會(huì)額外產(chǎn)生一個(gè)256 比特的隨機(jī)數(shù), 將其作為CTR 模式的分組密碼算法的新密鑰.

3.5 各平臺(tái)軟件隨機(jī)數(shù)發(fā)生器設(shè)計(jì)的比較

下面從熵源、熵池、熵估計(jì)、重播種機(jī)制、隨機(jī)數(shù)輸出單元等方面,給出了Linux、Android、Windows、iOS 等幾種典型操作系統(tǒng)平臺(tái)的軟件隨機(jī)數(shù)發(fā)生器設(shè)計(jì)的比較(見表1). 綜合來看, LRNG 是這幾種典型操作系統(tǒng)平臺(tái)中應(yīng)用最為廣泛的軟件隨機(jī)數(shù)發(fā)生器, 因?yàn)锳ndroid 平臺(tái)的APRNG 也是基于LRNG 實(shí)現(xiàn)的. 此外, 由于Linux 是開源項(xiàng)目, 因此對LRNG 開展的相關(guān)研究也較多. 實(shí)際上, 各種典型操作系統(tǒng)平臺(tái)的軟件隨機(jī)數(shù)發(fā)生器設(shè)計(jì)都基本遵循圖1 給出的基本結(jié)構(gòu), 只是在軟件RNG 的具體設(shè)計(jì)和實(shí)現(xiàn)上有一定的差異. 在熵源的選取上, 軟件隨機(jī)數(shù)發(fā)生器的熵源基本上都是源于操作系統(tǒng)數(shù)據(jù)或平臺(tái)外設(shè)輸入的隨機(jī)性, 或者平臺(tái)所支持的一些硬件隨機(jī)數(shù)發(fā)生器的輸出; 在熵估計(jì)方法上, 由于系統(tǒng)數(shù)據(jù)或平臺(tái)外設(shè)輸入屬于非物理熵源, 各典型平臺(tái)的軟件RNG 都有自己的熵估計(jì)方案; 為了保證后向安全性, 各平臺(tái)軟件RNG 設(shè)計(jì)方案中采用了不同的(重) 播種機(jī)制.

表1 不同平臺(tái)軟件隨機(jī)數(shù)發(fā)生器的比較Table 1 Comparison of software random number generators in different platforms

4 安全性分析關(guān)注點(diǎn)

由于軟件RNG 在Linux、Android、Windows 等操作系統(tǒng)平臺(tái)具有廣泛應(yīng)用, 其安全性也日益受到人們的關(guān)注. 根據(jù)以往的研究工作, 軟件RNG 安全性研究的關(guān)注點(diǎn)主要集中在以下幾個(gè)方面:

· 有效熵源的選取;

· 面向熵源的熵估計(jì)技術(shù)準(zhǔn)確度;

· 其他安全關(guān)注點(diǎn), 如前向/后向安全性、拒絕服務(wù)攻擊、運(yùn)行環(huán)境的安全性.

針對這些設(shè)計(jì)或使用上的安全關(guān)注點(diǎn), 在過去的一二十年內(nèi)人們研究發(fā)現(xiàn)軟件RNG 產(chǎn)生的隨機(jī)數(shù)存在被預(yù)測的可能性, 進(jìn)而導(dǎo)致用到這些隨機(jī)數(shù)服務(wù)的密碼應(yīng)用系統(tǒng)存在被破解的風(fēng)險(xiǎn). 進(jìn)一步地,APRNG 實(shí)現(xiàn)源碼和算法并不公開, 只對外提供了調(diào)用接口, 且APRNG 的熵源數(shù)據(jù)主要來源于LRNG dev/urandom 接口產(chǎn)生的數(shù)據(jù). WRNG 目前已將BCryptGenRandom 取代CryptGenRandom, 但沒有對BCryptGenRandom 設(shè)計(jì)和實(shí)現(xiàn)算法進(jìn)行分析的相關(guān)研究內(nèi)容. Yarrow 發(fā)生器應(yīng)用于早期Mac 操作系統(tǒng)平臺(tái)中, Fortuna 是對Yarrow 的改進(jìn), 去掉了熵估計(jì)模塊. 鑒于LRNG 是目前使用最為廣泛的軟件形態(tài)隨機(jī)數(shù)發(fā)生器之一, 而且Linux 操作系統(tǒng)的開源性, 使得LRNG 的設(shè)計(jì)原理和安全性一直備受研究人員的關(guān)注. 本節(jié)將結(jié)合LRNG, 圍繞以上三個(gè)方面的安全性分析關(guān)注點(diǎn)進(jìn)行闡述.

4.1 有效熵源的選取

軟件RNG 熵源的選取通?；谲浖脚_(tái)上已有的硬件(如CPU、磁盤) 或外設(shè)(如鍵盤、鼠標(biāo)), 以及可以采集平臺(tái)所處運(yùn)行環(huán)境參數(shù)的器件(如傳感器) 等, 而并非專門設(shè)計(jì)的硬件電路(如振蕩器). 雖然一些通用操作系統(tǒng)平臺(tái)在經(jīng)歷多次迭代更新后,可以支持硬件RNG 的輸出(如RDRAND 指令)或TPM輸出等作為補(bǔ)充熵源, 彌補(bǔ)操作系統(tǒng)中隨機(jī)數(shù)服務(wù)熵不足的問題. 但是, 不同的計(jì)算機(jī)體系架構(gòu)導(dǎo)致了熵源種類的不同, 即便體系架構(gòu)相似, 不同場景下的熵源活躍程度也不盡相同. 因此, 在不同平臺(tái)、不同場景下調(diào)用軟件RNG 服務(wù)時(shí), 熵源的熵供給能力差異很大, 這也導(dǎo)致軟件RNG 存在從熵源獲取到的隨機(jī)性質(zhì)量存在差異甚至無法得到保證的問題.

例如, 個(gè)人電腦或者移動(dòng)智能終端平臺(tái)通常接有鍵盤、鼠標(biāo)等外設(shè), 且有豐富的傳感器, 則熵供給能力較強(qiáng); 而路由器等網(wǎng)路設(shè)備的主要熵源是網(wǎng)絡(luò)中斷, 不具備其他隨機(jī)性來源, 則熵供給能力一般, 正如Gutterman 等人[13]所分析的, 像OpenWRT 無線路由器所含有的熵源是非常有限的(缺乏硬件外設(shè)鍵盤、鼠標(biāo)等的支持), 這類設(shè)備上唯一的LRNG 熵源是網(wǎng)絡(luò)中斷, 而敵手是容易對網(wǎng)絡(luò)中斷進(jìn)行觀測的. 此外, 目前廣泛使用的固態(tài)硬盤無法和傳統(tǒng)磁盤一樣提供足夠的熵源.

那么, 如何結(jié)合操作系統(tǒng)平臺(tái)自身特點(diǎn), 選取合適的熵源為軟件RNG 提供充足的隨機(jī)性, 是軟件RNG 能否對外提供高質(zhì)量隨機(jī)數(shù)服務(wù)的關(guān)鍵. 而盡可能多發(fā)掘并使用不同種類的熵源, 可從一定程度上緩解熵源隨機(jī)性不足的問題, 像LRNG 和Windows RNG 在版本更新中都努力嘗試引入更豐富的熵源.

4.2 面向熵源的熵估計(jì)技術(shù)準(zhǔn)確度

軟件RNG 一般基于密碼算法設(shè)計(jì)對種子進(jìn)行擴(kuò)展來產(chǎn)生隨機(jī)數(shù), 種子的不確定性由外界輸入的熵源數(shù)據(jù)決定. 美國NIST SP800-90A 標(biāo)準(zhǔn)推薦了生成隨機(jī)數(shù)的擴(kuò)展算法, 包括基于密碼雜湊算法、基于對稱密碼算法等結(jié)構(gòu). 保證軟件RNG 達(dá)到所聲稱的安全強(qiáng)度的前提, 是要確保輸入的熵需要滿足一定要求,而對于熵的量化估計(jì)研究則成為重點(diǎn). 相比而言, 在傳統(tǒng)硬件平臺(tái)上的熵源結(jié)構(gòu)一般較為清晰, 隨機(jī)行為(stochastic behavior) 比較穩(wěn)定, 選用合適的現(xiàn)有熵估計(jì)模型理論或統(tǒng)計(jì)熵估計(jì)方法就可以對熵進(jìn)行較為準(zhǔn)確的估計(jì), 從而保證所設(shè)計(jì)的發(fā)生器輸入的熵滿足要求. 但是, 對于軟件平臺(tái), 軟件RNG 的隨機(jī)性來源大多是行為難以確定的非物理事件, 如鍵盤鼠標(biāo)的操作、磁盤讀寫狀態(tài), 而使用一個(gè)模型或統(tǒng)計(jì)方法對這些事件的熵進(jìn)行刻畫或估量是困難的. 而且, 這些熵源的隨機(jī)行為并非是穩(wěn)態(tài)的, 包含的熵值會(huì)隨著時(shí)間而變化, 也有可能在一段時(shí)間內(nèi)受到物理環(huán)境或人為因素影響導(dǎo)致熵值變低, 這就會(huì)使得隨機(jī)數(shù)發(fā)生器內(nèi)部的狀態(tài)可破解, 進(jìn)一步預(yù)測出輸出的隨機(jī)數(shù).

目前現(xiàn)有的熵估計(jì)方法都無法針對軟件RNG 中基于非物理事件的熵源進(jìn)行有效的熵估計(jì), ISO/IEC 18031 和德國AIS 20/31 標(biāo)準(zhǔn)中使用的理論建模的方法也需要熵源是物理的、平穩(wěn)的; SP800-90B 統(tǒng)計(jì)熵估計(jì)方法也需要熵源是穩(wěn)態(tài)的, 但并沒有給出機(jī)制來判斷穩(wěn)態(tài)或非穩(wěn)態(tài). 雖然在LRNG 中給出了一個(gè)簡潔的熵估計(jì)方法, 但被指出存在明顯低估問題[35]. 在早期的Mac 系統(tǒng)中的軟件RNG (即Yarrow 發(fā)生器結(jié)構(gòu)) 也曾經(jīng)有過熵估計(jì)部件, 但也因?yàn)闇?zhǔn)確性原因在后續(xù)版本中移除了. 因此, 如何對軟件RNG 的熵源進(jìn)行準(zhǔn)確熵估計(jì), 目前仍是一個(gè)亟待解決的問題.

4.3 其他安全關(guān)注點(diǎn)

除了上述軟件RNG 的安全性分析關(guān)注點(diǎn)外, 安全性方面的其他關(guān)注點(diǎn)還包括前向/后向安全性、拒絕服務(wù)攻擊、運(yùn)行環(huán)境的安全性等.

前向/后向安全性. 在早期的LRNG 版本中, 若攻擊者獲取到了LRNG 在某個(gè)時(shí)刻的內(nèi)部狀態(tài), 則恢復(fù)該狀態(tài)出現(xiàn)之前的LRNG 輸出是存在可能的. 在文獻(xiàn)[13] 所針對的Linux 內(nèi)核版本上, 當(dāng)時(shí)的LRNG被分析出無法完全滿足前向安全性的要求, Gutterman 等人利用內(nèi)部狀態(tài)更新函數(shù)啟動(dòng)機(jī)制的缺陷, 以及更新函數(shù)不具備單向性問題, 他們在已知當(dāng)前發(fā)生器內(nèi)部狀態(tài)前提下計(jì)算出上一時(shí)刻的內(nèi)部狀態(tài), 并完成了對之前時(shí)刻輸出的恢復(fù). 隨后, Gutterman 等人對LRNG 內(nèi)部工作機(jī)制給出優(yōu)化建議以保證其前向安全性. 文獻(xiàn)[19] 的研究工作中, Lacharme 等人對LRNG 的設(shè)計(jì)加以改進(jìn), 從而使LRNG 設(shè)計(jì)可以阻止Gutterman 等人提出的攻擊.

拒絕服務(wù)攻擊. 文獻(xiàn)[13] 中提出了兩種不同的拒絕服務(wù)攻擊. 第一種是通過/dev/random 直接讀取相應(yīng)數(shù)據(jù). 由于當(dāng)時(shí)的LRNG 版本對調(diào)用隨機(jī)數(shù)服務(wù)的用戶沒有任何限制, 也沒有制定優(yōu)先級策略, 從而導(dǎo)致其他用戶可能在很長一段時(shí)間無法獲取到隨機(jī)數(shù)據(jù). 另一種是持續(xù)不斷地通過/dev/urandom 讀取非阻塞熵池中的數(shù)據(jù), 使得LRNG 輸入熵池中的熵來不及補(bǔ)充, 進(jìn)而間接地造成阻塞熵池中的熵難以累計(jì), 致使/dev/random 面臨拒絕服務(wù)的問題. 在Linux 內(nèi)核4.8 版本上, 設(shè)計(jì)者們開始使用ChaCha20 DRNG 來取代非阻塞熵池, 從而消除了這個(gè)問題. ChaCha20 DRNG 每5 分鐘完成一次重播種, 這一機(jī)制使得內(nèi)部的熵供給和后向安全性得到改善. 此外, 如Lacharme 等人所述, 在后期內(nèi)核版本的LRNG 輸入熵池中專門為/dev/random 留存了一部分含熵?cái)?shù)據(jù), 并且外界是無法通過對ChaCha20 DRNG 的操作來獲取這部分留存數(shù)據(jù)的, 從而降低了/dev/random 受到拒絕服務(wù)攻擊的風(fēng)險(xiǎn).

運(yùn)行環(huán)境的安全性. 軟件RNG 的安全性與其所處運(yùn)行環(huán)境的安全性有著直接的關(guān)系. 在BSI 團(tuán)隊(duì)的研究報(bào)告[35]中指出, LRNG 的安全需要依賴于安全的Linux 內(nèi)核和內(nèi)核運(yùn)行環(huán)境, 如果一個(gè)攻擊者可以觀察到LRNG 的內(nèi)部狀態(tài)或者熵源的行為, 那么LRNG 的熵將不存在. 只有通過主機(jī)執(zhí)行平臺(tái)對LRNG 提供一個(gè)安全域, 才能實(shí)現(xiàn)對LRNG 的內(nèi)部狀態(tài)等環(huán)節(jié)的保護(hù), 例如, 保證執(zhí)行環(huán)境的物理安全、通過適當(dāng)?shù)难a(bǔ)丁管理機(jī)制確保Linux 內(nèi)核及時(shí)進(jìn)行安全更新、為LRNG 使用可信的執(zhí)行環(huán)境(如使用可信硬件) 等.

5 結(jié)束語

隨機(jī)數(shù)發(fā)生器所產(chǎn)生的隨機(jī)數(shù)為密碼算法、密碼協(xié)議、數(shù)字簽名等密碼技術(shù)提供基礎(chǔ)的安全保障. 隨著智能移動(dòng)終端、物聯(lián)網(wǎng)設(shè)備等便攜式設(shè)備的不斷普及和移動(dòng)互聯(lián)網(wǎng)、物聯(lián)網(wǎng)等技術(shù)的快速發(fā)展, 以及軟件密碼模塊在我國逐步興起和廣泛應(yīng)用, 傳統(tǒng)的硬件RNG 已不能完全滿足當(dāng)前密碼應(yīng)用對隨機(jī)數(shù)服務(wù)的需求, 軟件RNG 的設(shè)計(jì)成為未來重要的發(fā)展趨勢. 本文主要總結(jié)了目前較為典型的操作系統(tǒng)平臺(tái)上所使用的軟件形式隨機(jī)數(shù)發(fā)生器的基本結(jié)構(gòu)和隨機(jī)數(shù)產(chǎn)生原理, 并從熵源的隨機(jī)性質(zhì)量、熵源的熵估計(jì)技術(shù)準(zhǔn)確度、前向/后向安全性等方面對這些發(fā)生器的安全性進(jìn)行分析. 該工作全面地梳理了典型操作系統(tǒng)上的隨機(jī)數(shù)發(fā)生器設(shè)計(jì)與實(shí)現(xiàn), 以及安全性問題分析, 對我國未來軟件形式的隨機(jī)數(shù)發(fā)生器的設(shè)計(jì)與檢測、標(biāo)準(zhǔn)規(guī)范的研制等工作具有重要的參考意義.