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

(1 中國科學(xué)院大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 北京 100049； 2 中國科學(xué)院信息工程研究所信息安全國家重點(diǎn)實(shí)驗(yàn)室， 北京 100093)(2020年1月10日收稿； 2020年5月12日收修改稿)

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

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

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

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

本文的主要貢獻(xiàn)如下：

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

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

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

1 相關(guān)工作

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

1.1 SRNG模型

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

1.2 基于操作系統(tǒng)平臺(tái)的典型SRNG設(shè)計(jì)

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

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

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

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

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

1)計(jì)算時(shí)間差：

(1)

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

2)選擇最小差：

(2)

3)計(jì)算熵值：

Ei=log2Δi.

(3)

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

1.3 安全性評(píng)估

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

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

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

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

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

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

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

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

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

2.1 安全假設(shè)

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

2.2 EM-SRNG設(shè)計(jì)

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

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

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

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

圖1 EM-SRNG架構(gòu)Fig.1 EM-SRNG architecture

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

2.2.1 熵源

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

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

2.2.2 熵監(jiān)控

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

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

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

2.2.3 后處理模塊

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

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

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

?初始化函數(shù)

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

算法1 初始化函數(shù)輸入:input:未處理序列輸出:V,C,counter:發(fā)生器內(nèi)部狀態(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可用于生成種子、更新內(nèi)部狀態(tài)V和C。SM3_df函數(shù)第2～3行，計(jì)算要求返回的數(shù)據(jù)長度與SM3輸出長度256的倍數(shù)關(guān)系，并將重播種計(jì)數(shù)器的值設(shè)為1。SM3_df函數(shù)第4～7行，根據(jù)返回?cái)?shù)據(jù)長度與256的關(guān)系，循環(huán)用SM3算法產(chǎn)生中間數(shù)據(jù)temp，并將每次的temp拼接起來。最后，從中間數(shù)據(jù)temp值中從左到右讀取要求返回長度的數(shù)據(jù)。

算法2 SM3_df算法輸入:input_string:輸入數(shù)據(jù)return_len:要求返回?cái)?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后處理擴(kuò)展算法的種子seed，并更新內(nèi)部狀態(tài)V和C。算法3展示種子更新函數(shù)的偽代碼，函數(shù)第1行，調(diào)用SM3_df函數(shù)來更新種子。種子更新函數(shù)第2～4行，更新V值為當(dāng)前種子值，然后調(diào)用SM3_df函數(shù)輸入16進(jìn)制01和當(dāng)前內(nèi)部狀態(tài)V值，返回結(jié)果是440 bit的C更新值，將重播種計(jì)數(shù)器值重設(shè)為1。

算法3 種子更新函數(shù)輸入:V,C,counter:RNG內(nèi)部狀態(tài)當(dāng)前值input:輸入數(shù)據(jù)輸出:新V,C,counter: 發(fā)生器內(nèi)部狀態(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作為新的內(nèi)部狀態(tài)END

?輸出函數(shù)

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

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

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

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

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

?初始化函數(shù)

初始化函數(shù)用于對(duì)基于SM4后處理擴(kuò)展算法的初始內(nèi)部狀態(tài)Key、V和counter進(jìn)行賦值。算法5展示初始化函數(shù)的偽代碼，種子seed(初始化和更新RNG內(nèi)部狀態(tài)的變量)長度為256 bit，調(diào)用SM4_df函數(shù)生成種子數(shù)據(jù)。初始化函數(shù)第2～3行，將初始Key和V值設(shè)為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ū)存放中間結(jié)果(SM4_CTR_Update算法第6行)。最后，SM4_CTR_Update算法的第7～8行，緩沖區(qū)temp最左邊的128 bit用來更新密鑰K，剩余的128 bit用來更新V。

算法5 初始化函數(shù)輸入:input: 未處理序列輸出:V,Key,counter: 發(fā)生器內(nèi)部狀態(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:要求返回?cái)?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為一個(gè)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ā)生器內(nèi)部狀態(tài)當(dāng)前值輸出:Key’,V’: 發(fā)生器內(nèi)部狀態(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內(nèi)部狀態(tài)當(dāng)前值輸出:V,Key,counter:發(fā)生器內(nèi)部狀態(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變量設(shè)置為0字符串。輸出函數(shù)第 2～4 行中，計(jì)數(shù)器V遞增，通過SM4算法密鑰Key加密V來輸出128 bit隨機(jī)數(shù)，然后根據(jù)請(qǐng)求長度截取部分?jǐn)?shù)據(jù)返回給應(yīng)用程序。輸出函數(shù)第5～6行中，調(diào)用 SM4_CTR_Update函數(shù)輸入additional_input、內(nèi)部狀態(tài)Key值和V值，返回結(jié)果Key和V的更新值，并將重播種計(jì)數(shù)器值加1。

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

算法9 輸出函數(shù)輸入:V,C,counter:RNG內(nèi)部狀態(tài)當(dāng)前值requested_len:請(qǐng)求的隨機(jī)比特長度輸出:returned_bits:返回給用戶的隨機(jī)數(shù)V’,Key’,counter:發(fā)生器內(nèi)部狀態(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 安全分析

下面，對(duì)所設(shè)計(jì)的EM-SRNG進(jìn)行安全性分析。

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

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

3 安全性和性能評(píng)價(jià)

本章，對(duì)所設(shè)計(jì)的軟件隨機(jī)數(shù)發(fā)生器進(jìn)行安全性和性能方面的評(píng)價(jià)，以驗(yàn)證該架構(gòu)的可靠性和實(shí)用性。

3.1 實(shí)驗(yàn)平臺(tái)

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

3.2 EM-SRNG熵源質(zhì)量

3.2.1 納秒級(jí)時(shí)間熵源

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

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

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

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

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

3.2.2 LRNG熵源

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

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

在實(shí)驗(yàn)中，我們觀察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熵池?cái)?shù)據(jù)質(zhì)量Fig.3 Data quality of LRNG entropy pool

3.2.3 評(píng)價(jià)結(jié)果

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

3.3 EM-SRNG輸出質(zhì)量

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

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

圖4 dev/urandom輸出質(zhì)量Fig.4 Output quality of dev/urandom

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

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

3.4 性能評(píng)估

在輸出質(zhì)量得到保證的前提下，更快的隨機(jī)數(shù)輸出速率能夠?yàn)橛脩籼峁└憬莸姆?wù)，及時(shí)滿足對(duì)隨機(jī)數(shù)的需求。為此，我們從隨機(jī)數(shù)輸出速率角度對(duì)性能進(jìn)行綜合評(píng)估。

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

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

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

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

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

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

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

4 結(jié)論

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

簡 報(bào)