一種帶有熵監(jiān)控功能的軟件隨機數(shù)發(fā)生器*

劉攀，陳天宇，呂娜，馬原，荊繼武

(1 中國科學院大學計算機科學與技術學院， 北京 100049； 2 中國科學院信息工程研究所信息安全國家重點實驗室， 北京 100093)(2020年1月10日收稿； 2020年5月12日收修改稿)

隨著信息技術的快速發(fā)展，密碼應用日益受到關注。RNG作為密碼算法、密碼協(xié)議等眾多密碼技術的安全基石，其輸出被稱為隨機數(shù)。隨機數(shù)被廣泛地用于對稱或非對稱密碼算法的密鑰產生、挑戰(zhàn)-響應方案中的挑戰(zhàn)值、數(shù)字簽名方案中的秘密信息，以及抗側信道分析攻擊等密碼應用中。按隨機性來源和生成原理的不同，RNG主要分為真隨機數(shù)發(fā)生器(true RNG,TRNG)和偽隨機數(shù)發(fā)生器(pseudo RNG,PRNG)[1]。TRNG是采集某些物理現(xiàn)象(如電路噪聲、核裂變)中的隨機成分，經數(shù)字化處理后生成隨機數(shù)。PRNG則是采用確定性算法(如LFSR[2]、馮.諾依曼后處理[3])將一段有限長的隨機序列(也稱為種子，通常由TRNG生成)擴展成任意長度的輸出序列。

TRNG又可細分為基于物理源的硬件RNG(hardware RNG, HRNG)和基于外部非物理源的軟件RNG(software RNG, SRNG)[4]。HRNG生成的數(shù)據(jù)通常具有良好的不可預測性，但隨著便攜式物聯(lián)網、智能移動終端等設備的不斷普及，傳統(tǒng)的HRNG存在硬件更新困難、開發(fā)成本高等問題，導致適用范圍受限，僅部分平臺可以調用HRNG接口[5]。此外，如果HRNG的器件出現(xiàn)老化或存在偏差等問題，也很難修復[6]。

目前，已有諸多系統(tǒng)平臺使用SRNG提供隨機數(shù)服務，如Linux 隨機數(shù)發(fā)生器(即LRNG)[7]、基于LRNG實現(xiàn)的Android系統(tǒng)的隨機數(shù)發(fā)生器(APRNG)[8]、iOS系統(tǒng)使用的Yarrow[9]、基于Yarrow設計的Fortuna隨機數(shù)發(fā)生器[10]，以及Windows內核的隨機數(shù)發(fā)生器CryptGenRandom[11]。由于SRNG中的熵源不可控，對后處理算法設計和實現(xiàn)的安全性要求較高，因此出現(xiàn)了許多針對SRNG設計實現(xiàn)的分析和攻擊。相關工作主要集中在熵源數(shù)據(jù)的安全性和后處理模塊內部狀態(tài)的安全性方面。在熵源數(shù)據(jù)安全性方面，攻擊者通過一些攻擊手段可以影響熵源數(shù)據(jù)的安全性，如return-to-libc攻擊[12]、return-oriented攻擊[13]等緩沖區(qū)溢出攻擊，通過構造函數(shù)并調用參數(shù)將原地址重定位到攻擊者的地址；熵源數(shù)據(jù)熵可能達不到預期需求，造成SRNG內部狀態(tài)泄漏、輸出數(shù)據(jù)可預測等安全風險，如OpenSSL的RNG中，Strenzke[8]指出若輸入數(shù)據(jù)熵不足，即使后續(xù)RAND add()函數(shù)會輸入新數(shù)據(jù)來增加熵，但仍存在RNG輸出數(shù)據(jù)存在低熵的隱患。在后處理模塊內部狀態(tài)的安全性方面，攻擊者利用Dual EC算法存在的參數(shù)后門[14-16]來泄露RNG的內部狀態(tài)，破壞RNG輸出序列的不可預測性。

綜合上述研究，我們發(fā)現(xiàn)，為提升SRNG設計和使用時的安全性，應重點考慮以下兩個方面：1)多種攻擊手段會影響熵源數(shù)據(jù)的安全，不安全的熵源數(shù)據(jù)會導致SRNG提供的隨機數(shù)服務存在嚴重安全隱患。因此，在SRNG實際運行時，對未處理序列的熵值(熵源數(shù)據(jù)的質量)進行在線監(jiān)控是必要的，并可在熵不足的情況下調用后處理模塊改善輸出序列的統(tǒng)計特性；2)如何設計實現(xiàn)具有高安全性的SRNG后處理擴展算法，以確保后處理模塊中內部狀態(tài)以及輸出序列的安全性?；谏鲜隹紤]，本文設計并實現(xiàn)了一種帶有熵監(jiān)控功能的軟件隨機數(shù)發(fā)生器(entropy monitoring SRNG, EM-SRNG)。

本文的主要貢獻如下：

1) 選取高精度時間序列作為熵源數(shù)據(jù)。由于讀取高精度系統(tǒng)時間的指令在取值、譯碼和執(zhí)行3個階段存在不確定性的時間誤差。EM-SRNG將納秒時間的末位數(shù)據(jù)作為架構中的未處理序列，其具有良好的不可預測、數(shù)據(jù)產生速率高等特點。雖然許多相關研究已將時間序列作為隨機源，但存在由于熵源事件頻繁發(fā)生而導致時間數(shù)據(jù)重復率和連續(xù)性較高的缺點，以LRNG為例，后續(xù)需要額外操作消除熵池數(shù)據(jù)之間的相關性。

2)提出一種基于NIST SP 800-90B測試套件的實時在線熵監(jiān)控機制，實時監(jiān)測EM-SRNG運行時熵源數(shù)據(jù)的質量，能夠基于熵量化未處理序列的質量，在設定熵閾值的情況下，對熵不足的未處理序列，能夠智能選擇調用后處理模塊，避免冗余的計算資源開銷。

3)實現(xiàn)高安全性的后處理模塊，以確保 EM-SRNG后處理模塊中內部狀態(tài)的安全性。EM-SRNG的后處理模塊基于中國自主研制的SM系列密碼算法設計而成，可選用基于SM3和SM4密碼算法設計的兩種后處理擴展算法，用于提高內部狀態(tài)的安全性以及改善輸出序列的統(tǒng)計特性。

1 相關工作

本章首先介紹SRNG的基本模型，簡要闡述SRNG結構中各組成部分的功能。其次，介紹操作系統(tǒng)平臺SRNG的典型設計，包括LRNG、ARNG、iOS系統(tǒng)的Yarrow和基于Yarrow設計的Fortuna隨機數(shù)發(fā)生器，以及Windows內核的RNG。最后，介紹SRNG的安全性評估要求和評估方法。

1.1 SRNG模型

本文在參考德國BSI的AIS 20/31[17]和ISO/IEC 18031[4]的基礎上，梳理出SRNG的基本模型。SRNG模型主要包含熵源、初始化函數(shù)、內部狀態(tài)、種子更新函數(shù)和輸出函數(shù)，其隨機數(shù)生成基本原理如下：將熵源事件數(shù)字化后的未處理序列作為SRNG的輸入，首先將未處理序列輸入初始化函數(shù)，并開始內部狀態(tài)迭代，然后通過輸出函數(shù)對內部狀態(tài)進行更新，最后產生外部請求的隨機數(shù)。種子更新函數(shù)是利用熵源數(shù)據(jù)更新內部狀態(tài)，通過條件控制(如輸出數(shù)據(jù)長度達到上限)執(zhí)行種子更新操作。

1.2 基于操作系統(tǒng)平臺的典型SRNG設計

軟件隨機數(shù)發(fā)生器目前已有許多成熟的設計方案，按照操作系統(tǒng)平臺劃分，有Mac、Linux、Android和Windows內核所帶的隨機數(shù)發(fā)生器。

iOS和Mac OS X操作系統(tǒng)，使用由Kelsey等[9]設計完成的Yarrow發(fā)生器。Yarrow發(fā)生器內部包含快熵池和慢熵池，通過統(tǒng)計熵池中同種熵源事件類型的熵值，進而確定是否執(zhí)行更新內部狀態(tài)(重播種)操作。該發(fā)生器使用3種不同的熵估計方法計算不同熵源事件的熵值，并取3種熵估計方法中的最小值作為熵源的最終熵值。最后，通過基于計數(shù)器工作模式的分組算法作為后處理算法來產生隨機數(shù)。由于Yarrow 輸出序列的質量在很大程度上依賴于熵估計方法的準確性，為此Viega[10]在 Yarrow的基礎上，選擇去掉熵估計環(huán)節(jié)，通過多熵池保證至少有一個熵池積累足夠的熵來提供安全性，據(jù)此提出Fortuna隨機數(shù)發(fā)生器。Fortuna通過32個多熵池和新重播種策略更新RNG內部狀態(tài)。最后通過基于計數(shù)器工作模式的分組算法生成隨機數(shù)。

Android操作系統(tǒng)上，APRNG的熵源數(shù)據(jù)主要來源于Linux內核提供的隨機數(shù)。APRNG主要使用 OpenSSL密碼庫中隨機數(shù)發(fā)生器的3個應用程序函數(shù)接口：RAND_poll()是初始化內部狀態(tài)接口，RAND_add()是數(shù)據(jù)輸入接口，RAND_byte()是隨機數(shù)輸出接口。Windows操作系統(tǒng)上，Dorrendorf等[12]分析Windows內核的隨機數(shù)發(fā)生器CryptGenRandom的結構，其使用RC4對稱加密算法更新內部狀態(tài)。

Linux操作系統(tǒng)上，LRNG是目前應用最廣泛的RNG。LRNG包含主熵池、阻塞熵池和非阻塞熵池，每個熵池都含有熵值計數(shù)器，用來統(tǒng)計對應熵池中數(shù)據(jù)的熵值。LRNG從外界收集4種熵源事件，包括鼠標移動、敲擊鍵盤、中斷和磁盤輸入輸出操作，并將熵源事件類型編碼和事件發(fā)生時間添入熵池。

LRNG熵估計方法被稱為“三階時間差”方法，通過計算熵源事件發(fā)生的時間差估計熵值，計算方法具體如下：

1)計算時間差：

(1)

其中，ti表示熵源事件i發(fā)生的的時間。

2)選擇最小差：

(2)

3)計算熵值：

Ei=log2Δi.

(3)

此外，LRNG提供兩種接口獲取隨機數(shù)，一種內核層輸出接口get_random_bytes，另一種是用戶層/dev/random 或者/dev/urandom文件接口。/dev/random從阻塞熵池提取隨機數(shù)，阻塞熵池每次在輸出隨機數(shù)之前，會先判斷熵值計數(shù)器值是否達到設定的閾值，進而判斷是否輸出隨機數(shù)。/dev/urandom是從非阻塞熵池提取隨機數(shù)，若非阻塞熵池不空，則/dev/urandom接口可持續(xù)輸出隨機數(shù)。

1.3 安全性評估

對于SRNG，要求其能夠抵抗內部或者外部的攻擊。對于以軟件形式實現(xiàn)的隨機數(shù)發(fā)生器，攻擊者被假定已知隨機數(shù)發(fā)生器的設計目標和算法實現(xiàn)，并且通過一些攻擊手段，可以獲取發(fā)生器某一時刻的內部狀態(tài)的相關信息。因此，SRNG在設計和使用時，應保證滿足以下安全要求[18]：

1)偽隨機性(R1)：SRNG輸出的隨機數(shù)對外部觀察者來說應該是隨機的。采用密碼算法對原始數(shù)據(jù)進行混淆和擴散，可以滿足此安全要求。

2)前向安全性(R2)：對于一個攻擊者而言，即便他獲取了發(fā)生器在某一特定時刻的狀態(tài)，也不能獲知在此之前任意時刻的輸出。目前，使用單向函數(shù)(如散列函數(shù))可滿足R2要求。

3)后向安全性(R3)：對于一個攻擊者而言，即便他獲取了發(fā)生器在某一特定時刻的狀態(tài)，也不能獲知在此之后任意時刻的輸出。Barak和Halevi[18]對SRNG的后向安全性進行分析，指出在輸出函數(shù)是確定性算法的情況下，在用戶每次請求隨機數(shù)之間更新內部狀態(tài)，可以實現(xiàn)保證后向安全性的目的。

為保證SRNG滿足以上安全性要求，提供高質量的隨機數(shù)服務，SRNG的安全性檢測是必不可少的。目前，常用的RNG安全性評估方法包括：黑盒統(tǒng)計檢測、理論熵估計和統(tǒng)計熵估計。

黑盒統(tǒng)計檢測是傳統(tǒng)的隨機性檢測手段。由于早期熵評估的困難，人們一直在采用后驗檢測的方法對輸出序列進行檢測來判定隨機數(shù)發(fā)生器的隨機性。所謂隨機性的后驗檢測，就是先假設熵是滿的(完全真隨機)，則輸出序列應該滿足多種統(tǒng)計分布，通過檢測輸出序列是否滿足這些統(tǒng)計分布判斷序列是否完全真隨機。目前有很多統(tǒng)計測試套件被廣泛認可和使用，如NIST發(fā)布的 SP 800-22[19]、TestU01[20]、佛羅里達州立大學Marsaglia開發(fā)的Diehard測試[21]和《GB/T 32915—2016 信息安全技術 二元序列隨機性檢測方法》[22](中國的隨機性統(tǒng)計檢測標準)。由于黑盒統(tǒng)計測試并不關注隨機數(shù)生成原理和發(fā)生器內部結構，而是只檢測輸出序列的質量，因此具有很好的通用性和可操作性。

理論熵估計是在完全了解隨機數(shù)發(fā)生器內部結構和產生原理的情況下，通過建立數(shù)學模型的方法對輸出序列的熵進行理論計算。這種測試方法一般用于對硬件隨機數(shù)發(fā)生器的理論安全性進行證明。

統(tǒng)計熵估計是介于理論熵估計和黑盒統(tǒng)計檢測二者之間的RNG安全測評方法。一方面，該方法繼續(xù)沿用當前最受推崇的隨機數(shù)檢測方式——“熵評估”來指導檢測技術的設計與實施；另一方面，該方法采用黑盒統(tǒng)計檢測的工作模式，使得其對任何結構和產生原理的發(fā)生器都具有較好的通用性。目前，這類測試方法中的典型是NIST SP 800-90B(簡稱“90B”)[23]。

2 帶有熵監(jiān)控功能的SRNG架構

2.1 安全假設

本文假設攻擊者無法破壞Linux內核的安全性，并且不考慮側信道攻擊。Linux內核的安全體現(xiàn)在對代碼段和數(shù)據(jù)段的保護。目前，已有方案可以對Linux內核的代碼段和數(shù)據(jù)段進行保護，如集成OSck[24]，一個能夠檢測內核rootkit是否對操作系統(tǒng)數(shù)據(jù)存在惡意修改的系統(tǒng)；或者使用KI-MON[25]，基于硬件事件觸發(fā)的內核完整監(jiān)控平臺；它們可以保護內核數(shù)據(jù)段，保證內核數(shù)據(jù)的正確性。TF-BIV[26]依賴散列值對二進制文件的完整性進行校驗，在保證散列函數(shù)是安全的前提下，可以對內核靜態(tài)代碼進行完整性保護。本文EM-SRNG的熵源事件發(fā)生于Linux內核中，Linux內核的安全性可以保證數(shù)據(jù)源產生的安全性。

2.2 EM-SRNG設計

我們設計了一種帶有熵監(jiān)控功能的軟件隨機數(shù)發(fā)生器(EM-SRNG)，架構如圖1所示，包含熵源、熵監(jiān)控和后處理3個模塊，其中熵監(jiān)控模塊可分為熵估計和熵判斷兩個環(huán)節(jié)，熵判斷的結果決定主熵池數(shù)據(jù)是否進入后處理模塊進行處理。下面詳細闡述EM-SRNG輸出隨機數(shù)的步驟：

1)“納秒級”時間熵源采集：以操作系統(tǒng)平臺“納秒級”時間數(shù)據(jù)作為熵源進行采集和數(shù)字化處理。由于讀取高精度系統(tǒng)時間的指令在取指、譯碼和執(zhí)行階段存在不確定性的時間誤差，使得納秒時間數(shù)據(jù)具有良好的隨機性。納秒時間數(shù)據(jù)的不確定性可以作為EM-SRNG隨機性的來源。EM-SRNG熵源模塊設計原理見2.2.1小節(jié)。

2)熵估計熵池數(shù)據(jù)：對主熵池數(shù)據(jù)所含信息量進行估計。EM-SRNG在線熵估計環(huán)節(jié)基于NIST SP 800-90B統(tǒng)計測試套件實現(xiàn)，可實時計算主熵池數(shù)據(jù)的保守熵估計，即在最差情況下主熵池數(shù)據(jù)所含熵值，從而避免高估熵值帶來的危害。EM-SRNG熵估計環(huán)節(jié)設計原理見2.2.2小節(jié)。

3)熵判斷和后處理：熵判斷模塊會將來自于熵估計器的測量值和預設的熵閾值相比較，根據(jù)測量值和閾值的大小關系，判斷未處理序列是否需要進入后處理模塊(對應不同的熵池，熵池1的數(shù)據(jù)無需進入后處理模塊；熵池2的數(shù)據(jù)需要進入后處理模塊處理)以改善輸出序列的統(tǒng)計特性，從而有效降低了由于調用后處理模塊而造成的資源開銷，同時保證了EM-SRNG的輸出質量。后處理模塊基于中國商用密碼算法設計而成，分別應用SM3雜湊算法和SM4分組算法，具有高可靠性、提供前向安全性和后向安全性等特點。SM3雜湊算法和SM4分組算法是中國典型的商用密碼算法，同時SM3算法又是ISO/IEC國際標準，SM3和SM4算法可用于后處理模塊設計方案中。EM-SRNG后處理模塊設計原理見2.2.3小節(jié)。

圖1 EM-SRNG架構Fig.1 EM-SRNG architecture

EM-SRNG提供bool random_srng(int length, char* random_buffer)函數(shù)接口生成應用程序請求的length長度的隨機數(shù)，隨機數(shù)存儲于緩沖區(qū)random_buffer中，返回給應用程序。返回值是布爾類型，若返回true，代表輸出序列是經EM-SRNG后處理模塊計算得到的數(shù)據(jù)；否則，輸出序列未經EM-SRNG后處理模塊的處理。EM-SRNG的后處理模塊可選用基于SM3雜湊算法和SM4分組算法的兩種后處理擴展算法，開發(fā)人員可自主選擇使用何種后處理擴展算法。

2.2.1 熵源

EM-SRNG熵源來自Linux高精度納秒級時間。在Linux操作系統(tǒng)用戶空間下，讀取系統(tǒng)時間主要通過讀內核中xtime全局變量。xtime從CMOS電路中獲取系統(tǒng)時間，是文件中timespec結構體變量，精確度是ns。

由于受CPU型號、溫度和電壓等物理因素以及CPU指令中斷、進程調度、亂序執(zhí)行和指令預測的影響，指令在取指、譯碼和執(zhí)行3個階段都存在不確定性的時間誤差，時間誤差在納秒級。所以軟件讀取高精度系統(tǒng)時間存在隨機偏差，使得其無法被敵手或用戶影響。因此，在EM-SRNG設計方案中，我們選取納秒級時間序列作為熵源數(shù)據(jù)。此外，熵源數(shù)據(jù)的產生速率也是SRNG設計方案中關注的一大方面，SRNG要求熵源數(shù)據(jù)采集過程簡單。目前，Linux操作系統(tǒng)已為用戶空間提供了讀取系統(tǒng)時間的函數(shù)接口，其讀取系統(tǒng)時間數(shù)據(jù)的速率較快。

2.2.2 熵監(jiān)控

熵監(jiān)控功能由兩個獨立的環(huán)節(jié)協(xié)同完成，即熵估計環(huán)節(jié)和熵判斷環(huán)節(jié)。EM-SRNG的熵估計環(huán)節(jié)基于NIST SP 800-90B測試包設計而成，用于在發(fā)生器運行時對主熵池中數(shù)據(jù)的在線熵檢測，實時監(jiān)測未處理序列熵值的變化。

本方案選用NIST SP 800-90B測試包設計發(fā)生器中在線熵估計器，這種基于最小熵的統(tǒng)計測試方法有3點好處：1)最小熵是一種保守的熵估計方法，適用于評價面向較高安全需求的隨機數(shù)服務，例如在操作系統(tǒng)環(huán)境下，經常使用操作系統(tǒng)的隨機數(shù)發(fā)生器產生的數(shù)據(jù)作為確定性隨機數(shù)發(fā)生器的種子；2)由于非物理熵源的行為特征難以用特定概率分布刻畫，因此很難采用理論建模方式量化SRNG的熵值；3)統(tǒng)計熵評估方法既從熵的角度評價SRNG質量，又可以用編程語言快速實現(xiàn)，且執(zhí)行效率高，對計算資源消耗低。

熵判斷是根據(jù)熵池中數(shù)據(jù)的熵值與閾值的關系來進行不同通路的選擇。熵判斷是為了確保EM-SRNG的輸出質量，在熵源數(shù)據(jù)達不到要求質量的前提下，對熵源數(shù)據(jù)經過后處理模塊混淆。而在熵源數(shù)據(jù)達到要求質量的情形下，直接輸出隨機數(shù)，減少密碼計算對資源的浪費，提高EM-SRNG整體性能。而在LRNG設計方案中，無論熵池數(shù)據(jù)的質量如何，從熵池輸出時，數(shù)據(jù)都將經過確定性密碼算法處理后才能作為隨機數(shù)，這種做法很容易造成冗余的資源開銷。

2.2.3 后處理模塊

EM-SRNG的后處理模塊包含兩種后處理擴展算法，分別基于SM3和SM4密碼算法進行設計，用于實現(xiàn)對未處理序列的混淆和擴散，開發(fā)人員可自主選擇使用哪種后處理擴展算法。下面，本節(jié)將詳細介紹兩種后處理擴展算法的設計方案。

1)基于SM3的后處理擴展算法

基于SM3后處理算法的內部狀態(tài)由變量V(比特串V，在每次調用SRNG時更新值)，C(長度為440 bit的比特串C，為隨機數(shù)發(fā)生器的內部狀態(tài)變量)和counter(重播種計數(shù)器)組成，其中V和C長度相等。通過判斷counter值，來確定是否更新種子(seed，初始化和更新RNG內部狀態(tài)的變量)和內部狀態(tài)。參考SRNG基本架構，基于SM3后處理擴展算法分為3個部分：初始化函數(shù)、種子更新函數(shù)和輸出函數(shù)。

?初始化函數(shù)

初始化函數(shù)用于對基于SM3后處理擴展算法的初始內部狀態(tài)進行賦值。算法1展示初始化函數(shù)的偽代碼，種子seed長度為440 bit(在不同密碼應用場景中可調整種子長度)，將未處理序列作為SM3_df函數(shù)的輸入，可生成440 bit的種子數(shù)據(jù)。實驗中我們根據(jù)EM-SRNG熵估計環(huán)節(jié)對主熵池數(shù)據(jù)的熵值計算結果來決定輸入的未處理序列長度，以此保證初始化函數(shù)中的輸入序列input有256比特熵。初始化函數(shù)第2～3行，將初始V值設定為調用SM3_df函數(shù)輸入未處理序列返回的值，初始C設定為調用SM3_df函數(shù)輸入16進制00和當前V值返回的結果。最后將重播種計數(shù)器的初始值設定為1。

算法1 初始化函數(shù)輸入:input:未處理序列輸出:V,C,counter:發(fā)生器內部狀態(tài)初始值BEGIN1: seed=SM3_df(input,440)2: V=seed3: C=SM3_df(0x00‖V, 440)4: counter =1END

算法2展示SM3_df的偽代碼，SM3_df可用于生成種子、更新內部狀態(tài)V和C。SM3_df函數(shù)第2～3行，計算要求返回的數(shù)據(jù)長度與SM3輸出長度256的倍數(shù)關系，并將重播種計數(shù)器的值設為1。SM3_df函數(shù)第4～7行，根據(jù)返回數(shù)據(jù)長度與256的關系，循環(huán)用SM3算法產生中間數(shù)據(jù)temp，并將每次的temp拼接起來。最后，從中間數(shù)據(jù)temp值中從左到右讀取要求返回長度的數(shù)據(jù)。

算法2 SM3_df算法輸入:input_string:輸入數(shù)據(jù)return_len:要求返回數(shù)據(jù)的長度輸出:requested_bits:返回輸入長度的數(shù)據(jù)BEGIN1: temp=NULL2: len=「retum_len256?3: counter=0x014: FOR i=1 to len do5: temp=temp‖SM3(counter‖return_bits_len‖input_string)6: counter=counter+17: END FOR8: requested_bits=the Leftmost return_len length data of tempEND

?種子更新函數(shù)

種子更新函數(shù)用于更新基于SM3后處理擴展算法的種子seed，并更新內部狀態(tài)V和C。算法3展示種子更新函數(shù)的偽代碼，函數(shù)第1行，調用SM3_df函數(shù)來更新種子。種子更新函數(shù)第2～4行，更新V值為當前種子值，然后調用SM3_df函數(shù)輸入16進制01和當前內部狀態(tài)V值，返回結果是440 bit的C更新值，將重播種計數(shù)器值重設為1。

算法3 種子更新函數(shù)輸入:V,C,counter:RNG內部狀態(tài)當前值input:輸入數(shù)據(jù)輸出:新V,C,counter: 發(fā)生器內部狀態(tài)更新值BEGIN1: seed=SM3_df(0x02‖input‖V, 440)2: V=seed3: C=SM3_df(0x01‖V, 440)4: counter=15: 返回V,C,counter作為新的內部狀態(tài)END

?輸出函數(shù)

隨機數(shù)輸出函數(shù)用來產生每次請求所需要的隨機數(shù)據(jù)。算法4展示輸出函數(shù)的偽代碼，對V進行SM3運算生成256 bit的隨機數(shù)。V的更新取決于前一時刻狀態(tài)的V、C和counter值。

算法4 輸出函數(shù)輸入:V,C,counter:RNG內部狀態(tài)當前值輸出:returned_bits:返回給用戶的隨機數(shù)V,C,counter:發(fā)生器內部狀態(tài)更新值BEGIN1: returned_bits=SM3(V)2: H=SM3(0x03‖V)3: V=(V+H+C+counter)mod 24404: counter =counter+15:返回RNG新內部狀態(tài)和returned_bitsEND

為提高內部狀態(tài)的安全性，基于SM3后處理擴展算法每調用一次輸出函數(shù)最多產生256 bit數(shù)據(jù)。當請求隨機數(shù)長度小于256 bit時，會對數(shù)據(jù)進行截取；當請求隨機數(shù)長度大于256 bit時，會循環(huán)調用輸出函數(shù)，在每次調用輸出函數(shù)后都會調用種子更新函數(shù)來輸入新的熵，以此避免相同內部狀態(tài)循環(huán)產生過多中間數(shù)據(jù)的安全隱患。

2)基于SM4的后處理擴展算法

基于SM4后處理算法的內部狀態(tài)由V(計數(shù)器)、Key(密鑰)和counter(重播種計數(shù)器)組成，V和Key的長度均設為128 bit，與SM4算法標準的要求保持一致。參考SRNG基本架構，基于SM4后處理擴展算法亦分為3個部分：初始化函數(shù)、種子更新函數(shù)和輸出函數(shù)。

?初始化函數(shù)

初始化函數(shù)用于對基于SM4后處理擴展算法的初始內部狀態(tài)Key、V和counter進行賦值。算法5展示初始化函數(shù)的偽代碼，種子seed(初始化和更新RNG內部狀態(tài)的變量)長度為256 bit，調用SM4_df函數(shù)生成種子數(shù)據(jù)。初始化函數(shù)第2～3行，將初始Key和V值設為0，將Key、V和種子seed作為SM4_CTR_Update函數(shù)的輸入。

?種子更新函數(shù)

算法8展示種子更新函數(shù)的偽代碼，利用輸入更新種子，繼而更新的種子通過SM4_CTR_Update函數(shù)來更新Key和V，并將counter值重置為1。SM4_CTR_Update算法的第2行和第3行通過SM4加密算法保證緩沖區(qū)temp有256 bit數(shù)據(jù)。接下來，先緩沖區(qū)temp數(shù)據(jù)和外部輸入的seed數(shù)據(jù)異或，然后在緩沖區(qū)存放中間結果(SM4_CTR_Update算法第6行)。最后，SM4_CTR_Update算法的第7～8行，緩沖區(qū)temp最左邊的128 bit用來更新密鑰K，剩余的128 bit用來更新V。

算法5 初始化函數(shù)輸入:input: 未處理序列輸出:V,Key,counter: 發(fā)生器內部狀態(tài)初值BEGIN1: seed=SM4_df(input,256)2: V=01283: Key=01284: (Key, V)=SM4_CTR_Update (seed,Key,V)5: counter=1END

算法6 SM4_df算法輸入:input_string:輸入數(shù)據(jù)return_len:要求返回數(shù)據(jù)的長度輸出:requested_bits:返回return_len長度的數(shù)據(jù)BEGIN1: L=input_string長度/82: N=return_len長度/83: S=L‖N‖input_string‖0x804: WHILE(S的長度模128不為0) do5: S=S ‖ 0x006: END WHILE7: temp=NULL8: i=0 注:i為一個32位整數(shù)9: K=0x0001020304…0F10: WHILE(temp長度小于256) do 11: IV =i ‖ 09612: temp=temp ‖ CBC_MAC (K, (IV‖S))13: i=i+114: END WHILE15: K=the Leftmost 128bit data of temp16: X=the Rightmost 128bit data of temp 17: temp=NULL18: WHILE(temp長度小于return_len長度) do19: X=SM4(K,X)20: temp=temp‖X21: requested_bits=tempEND

算法7 SM4_CTR_Update算法輸入:seed:長度為256比特的比特串Key,V:發(fā)生器內部狀態(tài)當前值輸出:Key’,V’: 發(fā)生器內部狀態(tài)更新值BEGIN1: temp=NULL2: WHILE(temp長度小于256) do3: output_block=SM4(Key, V)4: temp=temp‖ouput_block5: END WHILE6: temp=temp⊕seed7: Key’=the Leftmost 128bit data of temp8: V’=the Rightmost 128bit data of tempEND

算法8 種子更新函數(shù)輸入:V,Key,counter:RNG內部狀態(tài)當前值輸出:V,Key,counter:發(fā)生器內部狀態(tài)更新值BEGIN1: seed=SM4(entropy_input,256)2: (Key,V)=SM4_CTR_Update(seed,Key,V)3: counter =1END

?輸出函數(shù)

算法9展示輸出函數(shù)的偽代碼，第1行將additional_input變量設置為0字符串。輸出函數(shù)第 2～4 行中，計數(shù)器V遞增，通過SM4算法密鑰Key加密V來輸出128 bit隨機數(shù)，然后根據(jù)請求長度截取部分數(shù)據(jù)返回給應用程序。輸出函數(shù)第5～6行中，調用 SM4_CTR_Update函數(shù)輸入additional_input、內部狀態(tài)Key值和V值，返回結果Key和V的更新值，并將重播種計數(shù)器值加1。

此外，Cohney等[27]對NIST SP 800-90A中基于計數(shù)器工作模式的分組密碼算法實現(xiàn)的確定性隨機數(shù)發(fā)生器提出緩存攻擊模式。為了提高安全性，本方案中基于SM4實現(xiàn)的后處理算法每調用一次輸出函數(shù)最多產生128 bit數(shù)據(jù)。當請求長度超過128 bit時，會循環(huán)調用輸出函數(shù)，而每次調用輸出函數(shù)后都會立即更新內部狀態(tài)，以此避免同一狀態(tài)循環(huán)產生過多中間數(shù)據(jù)的安全隱患。

算法9 輸出函數(shù)輸入:V,C,counter:RNG內部狀態(tài)當前值requested_len:請求的隨機比特長度輸出:returned_bits:返回給用戶的隨機數(shù)V’,Key’,counter:發(fā)生器內部狀態(tài)更新值BEGIN1: additional_input =02562: V=(V+1) mod 21283: output_block=SM4 (Key, V)4: returned_bits=the Leftmost requested_len length data of output_block5: (Key’, V’)=SM4_CTR_Update (addi-tional_input, Key, V)6: counter =counter+17: 返回Key’,V’和returned_bitsEND

2.3 安全分析

下面，對所設計的EM-SRNG進行安全性分析。

對于R1要求而言，我們所設計的軟件隨機數(shù)發(fā)生器從以下3個方面確保輸出數(shù)據(jù)的質量。首先，納秒級時間熵源產生的未處理序列對于外部觀察者而言不可獲知。一方面時間同步很難實現(xiàn)，另一方面讀取的納秒級時間存在不確定性的時間誤差，此誤差不受敵手和用戶影響；其次，我們會對未處理序列進行熵測量來評估隨機性；最后，經過熵檢測達到預設熵閾值的數(shù)據(jù)，準許輸出；對于熵不足的未處理序列，EM-SRNG工作機制會對數(shù)據(jù)執(zhí)行后處理運算，以提升數(shù)據(jù)的統(tǒng)計性質和每比特的熵值。保證EM-SRNG輸出的隨機數(shù)有較好的統(tǒng)計特性。由此，EM-SRNG滿足偽隨機性要求。對于R2要求而言，我們設計的EM-SRNG后處理模塊實現(xiàn)了基于SM3和SM4的后處理算法。此外，由于LRNG輸出函數(shù)采取先更新內部狀態(tài)后輸出隨機數(shù)的狀態(tài)更新策略，造成LRNG不提供前向安全性[7]。而基于SM3和SM4后處理擴展算法中的輸出函數(shù)都是采用先輸出隨機數(shù)后更新內部狀態(tài)的更新策略。由此，EM-SRNG滿足前向安全性要求。

對于R3要求而言，我們設計的EM-SRNG的后處理模塊包含種子更新函數(shù)，其作用是通過新輸入的未處理序列更新SRNG中的種子以及內部狀態(tài)。每次調用輸出函數(shù)后，會立即執(zhí)行種子更新函數(shù)。攻擊者即使獲取了某一時刻發(fā)生器的內部狀態(tài)，但種子更新函數(shù)的輸入數(shù)據(jù)會帶來新的熵，使得攻擊者難以準確預測出EM-SRNG之后時刻的內部狀態(tài)信息，從而難以泄露之后時刻EM-SRNG的輸出。由此，EM-SRNG滿足后向安全性要求。

3 安全性和性能評價

本章，對所設計的軟件隨機數(shù)發(fā)生器進行安全性和性能方面的評價，以驗證該架構的可靠性和實用性。

3.1 實驗平臺

本文設計的EM-SRNG實現(xiàn)在64位Ubuntu操作系統(tǒng)的臺式機上，其系統(tǒng)版本為16.04.9，內核版本為4.4.0，編譯器版本為5.4.0，內存為4 GB。LRNG熵池數(shù)據(jù)來源于64位Ubuntu操作系統(tǒng)的臺式機上，其系統(tǒng)版本為16.04.11，內核版本為4.14.102，編譯器版本為5.4.0，內存為4 GB。

3.2 EM-SRNG熵源質量

3.2.1 納秒級時間熵源

在實驗中，我們觀察了9位納秒級時間序列，發(fā)現(xiàn)前4位重復數(shù)據(jù)過多，并存在一定規(guī)律性，而后5位數(shù)據(jù)的自相關性和均勻性較好，特別是最后一位數(shù)據(jù)其基本不相關。因此，最終選取納秒級時間最后一位作為未處理序列。

在實驗中，利用90B測量了1 000次納秒級時間最后一位數(shù)據(jù)的比特熵，每次數(shù)據(jù)長度為106字節(jié)。如圖2所示，橫坐標代表熵值范圍(0～1)，縱坐標代表頻數(shù)，納秒時間最后一位數(shù)據(jù)的比特熵集中在0.75～0.9。

圖2 納秒時間末位數(shù)據(jù)比特熵Fig.2 Bit entropy of the last data in nanosecond time

為進一步提高未處理序列的質量，在保證輸出速率的情況下，按固定間隔取納秒級時間最后一位數(shù)據(jù)作為未處理序列。分別按間隔1、2、3、4位取數(shù)，重復實驗500次。其平均比特熵結果如表1所示，我們發(fā)現(xiàn)按固定間隔取數(shù)據(jù)會增加熵值?？紤]到時間效率及比特熵增長情況，我們按固定3位數(shù)的間隔取納秒級時間序列的最后1位數(shù)據(jù)作為未處理序列。

表1 固定間隔數(shù)據(jù)的比特熵Table 1 Bit entropy of fixed interval data

3.2.2 LRNG熵源

實驗對比測試了LRNG熵池數(shù)據(jù)的熵值。由于Linux內核源碼對外開放，我們對Linux內核進行編譯，將Linux用于填充熵池的元數(shù)據(jù)結構體作為系統(tǒng)日志信息填充至Linux的系統(tǒng)的環(huán)形緩沖區(qū)中，其中元數(shù)據(jù)結構體中包含jiffies(記錄系統(tǒng)的時鐘中斷次數(shù))、cycles(CPU時鐘周期數(shù))和num(熵源事件類型)3部分。經過對LRNG源碼分析后，可知LRNG會先將元數(shù)據(jù)結構體的3部分數(shù)據(jù)進行拼接，然后將數(shù)據(jù)添加入熵池中。

利用Linux系統(tǒng)的dmesg命令配合過濾條件讀取系統(tǒng)環(huán)形緩沖區(qū)中關于熵池元數(shù)據(jù)的特定內容并重定向至特定文件用于后續(xù)處理。對重定向文件進行分析，發(fā)現(xiàn)主熵池中jiffies數(shù)據(jù)以及num數(shù)據(jù)的重復率較高。由于Linux熵估計方法是對jiffies數(shù)據(jù)進行“3階時間差”計算，過多重復jiffies值會造成某些熵源數(shù)據(jù)的熵值為0。

在實驗中，我們觀察LRNG主熵池的元數(shù)據(jù)，并通過NIST SP 800-90B測量了200組cycles數(shù)據(jù)的比特熵，每次數(shù)據(jù)長度為106字節(jié)，如圖3所示，發(fā)現(xiàn)cycles熵值集中在0.7～0.76。

圖3 LRNG熵池數(shù)據(jù)質量Fig.3 Data quality of LRNG entropy pool

3.2.3 評價結果

根據(jù)3.2.1和3.2.2小節(jié)的分析，分別對納秒級時間序列和LRNG熵池數(shù)據(jù)進行測量。從原理上分析，LRNG熵池中存在jiffies和num數(shù)據(jù)的重復率較高的問題，導致LRNG熵池中每條數(shù)據(jù)存在過多的冗余數(shù)據(jù)。雖然LRNG會通過確定性密碼算法消除冗余數(shù)據(jù)的影響，但冗余數(shù)據(jù)依然會造成計算資源的浪費。而我們對納秒級時間數(shù)據(jù)進行仔細分析和選取，盡量確保進入EM-SRNG熵池的數(shù)據(jù)不存在冗余數(shù)據(jù)。從實驗結果分析，本方案中的熵源是納秒級時間序列，按3位時間間隔只取納秒級時間序列的最后一位，其比特熵平均值大約是0.883 1。我們亦對LRNG熵池中cycles變量值進行了測試，其比特熵集中在0.7～0.76。經實驗數(shù)據(jù)分析可得，本方案中熵源質量高于LRNG的熵源質量。

3.3 EM-SRNG輸出質量

本文EM-SRNG熵判斷環(huán)節(jié)的閾值設定為0.92(參考LRNG dev/urandom輸出序列的熵值，在不同應用場景中可適當調整閾值)，如果未處理序列比特熵達到0.92，那么直接作為隨機比特輸出。否則經過后處理模塊處理后再輸出。本方案后處理模塊包括基于SM3的后處理算法和基于SM4的后處理算法。我們使用90B對EM-SRNG輸出序列的比特熵進行重復測試，發(fā)現(xiàn)EM-SRNG中通過基于SM3后處理擴展算法和基于SM4后處理擴展算法輸出序列的比特熵都集中在0.93～0.95。

LRNG為用戶提供兩個接口來獲取隨機數(shù)，在實驗中我們利用90B測試了1 000次dev/urandom文件輸出的106字節(jié)隨機數(shù)的比特熵。如圖4所示，橫坐標代表比特熵，縱坐標代表頻數(shù)?？芍猟ev/urandom輸出數(shù)據(jù)的比特熵集中在0.92～0.94。由于LRNG非阻塞熵池和阻塞熵池的隨機數(shù)輸出原理有差異，dev/random數(shù)據(jù)來源于阻塞熵池，阻塞熵池輸出要求是該熵池數(shù)據(jù)熵值達到閾值，而dev/urandom數(shù)據(jù)來源于非阻塞熵池，只要非阻塞熵池存在數(shù)據(jù)，那么dev/urandom數(shù)據(jù)就會存在。所以，可知dev/urandom讀取隨機數(shù)速率遠遠高于dev/random。由下文3.4小節(jié)分析得到的dev/random輸出速率，從dev/random讀取1 000字節(jié)隨機數(shù)需要大約20 s。90B建議待測序列長度為106字節(jié)，而從dev/random讀取106字節(jié)數(shù)據(jù)大約需要20 000 s(接近6 h)。由于從dev/random讀取106字節(jié)數(shù)據(jù)所耗時間長，我們在實驗中收集了從dev/random文件接口讀取的10組100萬字節(jié)數(shù)據(jù)，經過90B測試，其輸出數(shù)據(jù)比特熵集中在0.94～0.95。

圖4 dev/urandom輸出質量Fig.4 Output quality of dev/urandom

根據(jù)表2總結可得，本文提出的EM-SRNG的隨機數(shù)輸出質量與LRNG dev/random提供的數(shù)據(jù)質量相當，而略好于LRNG的dev/urandom提供的數(shù)據(jù)質量。

表2 對比EM-SRNG和LRNG的輸出質量Table 2 Comparison of EM-SRNG and LRNG output quality

3.4 性能評估

在輸出質量得到保證的前提下，更快的隨機數(shù)輸出速率能夠為用戶提供更便捷的服務，及時滿足對隨機數(shù)的需求。為此，我們從隨機數(shù)輸出速率角度對性能進行綜合評估。

本文EM-SRNG的隨機數(shù)輸出時間包括未處理序列的生成時間、90B在線熵估計環(huán)節(jié)時間和后處理模塊(基于SM3后處理擴展算法和基于SM4后處理擴展算法)時間。在EM-SRNG輸出100萬字節(jié)隨機數(shù)據(jù)的前提下，EM-SRNG按固定3位數(shù)間隔讀取100萬字節(jié)納秒級時間序列末位數(shù)據(jù)大約需要8 ms時間，EM-SRNG熵監(jiān)控模塊中的90B熵估計環(huán)節(jié)大約需要2 s?；赟M3后處理擴展算法和基于SM4后處理擴展算法輸出106字節(jié)數(shù)據(jù)時間集中在100～300 ms。由此，發(fā)現(xiàn)EM-SRNG輸出100萬字節(jié)隨機數(shù)的時間主要消耗在熵監(jiān)控模塊，需要大約2 s的時間。

LRNG為用戶提供接口獲取隨機數(shù)，用戶可以通過讀取dev/urandom文件或者dev/random文件來獲取隨機數(shù)。dev/random接口要求阻塞熵池的熵值達到閾值，然后再輸出隨機數(shù)據(jù)，為此dev/random輸出隨機數(shù)需要時間較長。圖5展示5 000次調用dev/random輸出1 000字節(jié)隨機數(shù)需要的時間，以μs為單位。從圖5中可以直觀地看到dev/random產生1 000 bit時間大約是15～25 s。有少量時間高于或者低于15～25 s的范圍，是由于dev/random的輸出時間取決于LRNG主熵池數(shù)據(jù)達到閾值的時間，如果主熵池數(shù)據(jù)的熵值較快達到閾值，那么輸出1 000字節(jié)的時間就會相應變短；反之，輸出1 000字節(jié)的時間就會變長。

圖5 dev/random產生1 000 bit數(shù)據(jù)的時間Fig.5 Dev/random time to produce 1 000 bit of data

由于LRNG熵源事件頻繁發(fā)生，導致添加到LRNG主熵池的jiffies時間數(shù)據(jù)重復率或者連續(xù)性較高。在這種情況下，LRNG“3階時間差”熵估計方法計算的熵值會較低，造成阻塞熵池中熵計數(shù)器值增速較慢，最終影響到dev/random文件接口的輸出速率。相比而言，dev/urandom輸出速率總體遠遠高于dev/random輸出速率。

EM-SRNG輸出100萬字節(jié)的隨機數(shù)大約需要2 s，而dev/urandom文件接口輸出100萬字節(jié)數(shù)據(jù)大約僅需要10 ms，EM-SRNG輸出速率慢于dev/urandom大約200倍。EM-SRNG在2 s時間內大約可以生成106字節(jié)的隨機數(shù)據(jù)，而dev/random文件接口在2 s時間內大約可以生成100字節(jié)的隨機數(shù)據(jù)，EM-SRNG輸出速率快于dev/random大約104倍。LRNG非阻塞熵池輸出隨機數(shù)不考慮熵池數(shù)據(jù)的熵值，將非阻塞熵池數(shù)據(jù)經過確定性密碼算法處理后生成的數(shù)據(jù)直接存儲于dev/urandom文件中，而阻塞熵池利用熵閾值條件控制dev/random的輸出。EM-SRNG和dev/random都通過熵閾值條件控制隨機數(shù)的輸出，而EM-SRNG輸出速率遠高于dev/random。EM-SRNG產生隨機數(shù)的時間主要消耗在熵估計環(huán)節(jié)，如果EM-SRNG缺乏熵監(jiān)控模塊，那么其生成隨機數(shù)的時間是未處理序列生成時間和后處理模塊處理時間之和，則EM-SRNG與dev/urandom的輸出速率屬于同一量級。

在隨機數(shù)輸出速率方面，如表3所示，EM-SRNG的數(shù)據(jù)產生速率比LRNG的dev/random高4個數(shù)量級左右，但由于在結構中嵌入了基于90B統(tǒng)計套件進行在線熵估計，使得EM-SRNG的速率比LRNG的dev/urandom要慢近200倍。如果EM-SRNG缺乏熵監(jiān)控模塊，那么其輸出速率與LRNG的dev/urandom屬于同一量級。綜上分析可得，我們設計的EM-SRNG輸出速率是較快的。

表3 EM-SRNG與LRNG輸出速率對比Table 3 Comparison of EM-SRNG and LRNG output rates byte/s

4 結論

隨著便攜式物聯(lián)網、智能移動終端等設備的不斷普及，軟件隨機數(shù)發(fā)生器具有廣闊的應用場景。然而，熵源的隨機性不足以及SRNG內部狀態(tài)的泄露會影響SRNG的安全性。為此，針對基于非物理源的軟件隨機數(shù)發(fā)生器的安全性設計，本文提出一種帶有熵監(jiān)控功能的軟件隨機數(shù)發(fā)生器(EM-SRNG)架構。EM-SRNG選用高精度納秒時間作為熵源，并將納秒時間的末位數(shù)據(jù)作為未處理序列，其具有良好的不可預測性和產生速率高的特點。并且，基于代碼優(yōu)化后的NIST SP 800-90B統(tǒng)計測試套件，EM-SRNG設計了嵌入式在線的熵估計器，可以對熵池數(shù)據(jù)質量進行實時地熵監(jiān)測。隨著商用密碼算法的不斷推廣，EM-SRNG后處理模塊基于中國SM系列密碼算法設計而成，可選用基于SM3和SM4算法設計的兩種后處理擴展算法。在實驗方案中，我們對EM-SRNG進行了安全性和性能方面的評估，從熵源質量、輸出質量和輸出速率3個方面，對EM-SRNG和LRNG進行了對比分析。實驗結果表明EM-SRNG可以提供良好的隨機數(shù)服務。

簡 報