jitterentropy 程式庫是由 Stephan Mueller 所編寫,可從 https://github.com/smuellerDD/jitterentropy-library 取得,您可以在 http://www.chronox.de/jent.html 找到。在 Zircon 中,這個 API 可做為簡單的熵來源,用於種子系統 CPRNG。
本文件描述並分析兩種 (獨立) 的時基誤差設定選項:
- 是否要使用變數,在雜訊產生函式中使用虛擬隨機疊代次數。
- 是否使用時基誤差內部處理處理常式對原始雜訊樣本進行後處理。
我考慮這些基本設定選項,因為這會影響到時基誤差使用的基本程序。我會將這些參數與可調整的參數進行比較 (例如,未隨機選擇用於循環次數的精確值,或是時基線內部使用的暫存記憶體大小),因為可維護參數對基特熵收集熵的影響並不大,只有收集的資料量和所需時間。
本文結尾已有全部結論,但總結來說,我們應該避免選擇虛擬隨機疊代號碼,以及使用時製後處理資料。
時基誤差簡述
作者的說明文件可透過 HTML 表單 (http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.html) 取得,並以 PDF 格式取得,網址為 http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.pdf。簡單來說,程式庫會從 CPU 指示時間碼的變化中隨機收集位元。
Jitterentropy 會透過 64 位元號碼呈現隨機狀態,這些數字受到許多此類函式的影響,最終做為輸出隨機使用。
噪音來源有兩個,這兩個來源都是執行速度較慢的程式碼區塊,且精確的執行階段是測量出精確的執行階段 (使用系統時鐘,需要略為奈秒的解析)。完成這些程式碼區塊的確切時間將有所不同。我們會測試這些時間,確保這些時間不可預測。雖然我們無法完全確定它們能夠確實存在,但測試結果 (包括下方結果) 確實很振奮。不過請注意,本文件旨在不證明我們預估時誤差的最小熵,而是要討論上述兩種設定選項。
做為雜訊來源使用的第一個程式碼區塊是會耗用大量 CPU 的 LFSR 迴圈,請在 jent_lfsr_time
函式中實作。LFSR 邏輯的重複次數是由 kernel.jitterentropy.ll
cmdline 控制 (「ll
」代表「LFSR 迴圈」)。如果值為 ll = 0
,則會使用虛擬隨機計數,否則會使用 ll
的值。查看原始碼時,外部迴圈會根據 ll
參數重複。內部迴圈每次執行 XOR 時,從最近的時間樣本中有一個位元執行 XOR 時,走 64 步。以這種方式透過 LFSR 傳遞時間範例可做為處理步驟,通常結尾是隨機時間步。如熵品質測試文件所述,測試 CPU 時間變化的熵內容時,請務必略過這項處理作業。另外,啟用處理作業也會在某些情況下增加可疑的數量預估值 (請參閱「處理原始樣本的影響」一節)。
第二個雜訊來源是 jent_memaccess
函式的記憶體存取迴圈。系統會根據 kernel.jitterentropy.ml
cmdline (「ml
」代表「記憶體迴圈」) 重複記憶體存取迴圈,再次將值設為 0 時,就會啟用虛擬隨機迴圈計數,所有非零值都會覆寫虛擬隨機計數。每個實際記憶體存取迴圈的疊代都會讀取及寫入相對較大的記憶體區塊,然後分割成每個大小 kernel.jitterentropy.bs
位元組的 kernel.jitterentropy.bc
多個區塊。清除目前的文件時的預設值是 bc = 1024
和 bs = 64
;最新的預設值應記錄在 cmdline 文件中。為了進行比較,時基誤差原始碼中的預設值是 bc = 64
和 bs = 32
,詳情請參閱此處定義。根據 jent_memaccess
函式上方的註解,記憶體總大小應大於目標機器的 L1 快取大小。令人困惑:bc = 64
和 bs = 32
會產生 2048 個位元組的記憶體大小,遠比大多數 L1 快取小得多 (我找不到大於 0 位元組,但小於 4 KB 的 CPU)。使用 bs = 64
和 bc = 1024
會產生 64 KB 的記憶體,通常足以溢位 L1 資料快取。
選項 1:虛擬迴圈計數
基特相關資訊最初的設計,就是為了讓兩個雜訊產生函式執行偽隨機次數。具體來說,jent_loop_shuffle
函式會混合 (1) 從高解析度時鐘讀取的時間,以及 (2) 時基線內部隨機狀態讀取的時間,以決定雜訊來源的執行次數。
我們新增了覆寫這些虛擬迴圈計數的功能,並測試了包含及未覆寫值時,記載的效能。如要進一步瞭解這些結果,請參閱「虛擬隨機循環次數的影響」一節,但摘要說明:統計資料測試顯示,虛擬迴圈計數比預期多出的熵多。這會讓我相信這些較高的熵計數,因此建議使用較低的預估值,並優先使用確定性迴圈計數為虛擬隨機。
Jitterentropy 隨機資料處理
如上所述,時基線可以處理隨機資料,使資料看起來「更隨機」。具體而言,這類處理作業應減少 (及理想) 從均勻分佈中隨機資料的偏差,並減少 (理想地移除) 隨機位元組之間的任何相互關聯。
想要產生已處理樣本的主要功能為 jent_gen_entropy
,這是由 jent_read_entropy
透過迴圈呼叫,以產生任意大量的隨機位元組。基本上,jent_gen_entropy
會在迴圈中呼叫雜訊函式 64 次。每次 jent_lfsr_time
叫用都會將雜訊測量結果混合到時基誤差隨機狀態。
進行 64 次疊代後,隨機狀態在 jent_stir_pool
中會選擇性地「堆疊」,並採用「mixer」值「混合」值,實際取決於時基誤差狀態。如原始碼中所述,這項作業無法增加或減少集區中的熵 (因為 XOR 是偏誤),但有機會改善隨機狀態的統計外觀。
原則上,叫用雜訊來源函式會產生 64 倍的熵,最多可達隨機狀態所能保存的 64 位元上限。這假設 jent_lfsr_time
中的混合作業經過加密處理。我並非加密分析的專家,但 LFSR 本身並非加密編譯的 RNG,因為 64 位元 LFSR 會顯示 64 位元 LFSR 的完整狀態,之後所有值都能輕鬆運算。我無法確定 LFSR 發生變動時,將時間測量 (XOR) 到 LFSR「底部」的時間測量配置更安全。如果沒有仔細的加密編譯檢查這種配置 (我知道所有人都可能存在,但我沒有在時基誤差說明文件中提及的方法),我將傾向使用未處理的樣本,並以已知有效的方式 (例如 SHA-2) 將這些樣本混合到我們的系統熵集區。
也就是說,我對已處理的資料樣本執行 NIST 測試套件。我的結果會顯示在下方「處理原始範例的影響」一節。
測試程序
執行熵來源品質測試的程序已記錄在熵品質測試文件中。
這些初步結果收集在 Raspberry Pi 3 的 Zircon 偵錯版本上,這是由 now-obsolete 專案所建構的 18358de5e90a012cb1e042efae83f5ea264d1502 修訂版本:https://fuchsia.googlesourcetio.googlesourcerta[t1502]。以下標記是在建構時在我的 local.mk
檔案中設定:
ENABLE_ENTROPY_COLLECTOR_TEST=1
ENTROPY_COLLECTOR_TEST_MAXLEN=1048576
我使用下列核心 cmdline 針對 Pi 上的偵錯核心進行網路啟動後,執行了啟動時間測試,測試了 $ML
、$LL
和 $RAW
的值:
kernel.entropy-test.src=jitterentropy
kernel.jitterentropy.bs=64
kernel.jitterentropy.bc=1024
kernel.jitterentropy.ml=$ML
kernel.jitterentropy.ll=$LL
kernel.jitterentropy.raw=$RAW
測試結果和分析
偽隨機迴圈計數的影響
原始資料
遵循時基誤差原始碼中的邏輯 (搜尋 MAX_FOLD_LOOP_BIT
和 MAX_ACC_LOOP_BIT
),虛擬迴圈計數在這些範圍內會有所不同:
ml: 1 .. 128 (inclusive)
ll: 1 .. 16 (inclusive)
我已在這個資料表中納入 NIST 套件的整體最小熵估計值,以及兩個貢獻的預估值:壓縮估計值和馬可夫估計值。NIST 最低熵預估值為至少 10 項不同的預估值,包括這兩個值。壓縮估計值通常是具有確定循環迴圈計數的時基誤差原始樣本中最小,而馬可夫估計值通常最低,與其他設定相較。
ml |
ll |
最小熵 (位元 / 位元組) | 壓縮預估 | Markov 估計值 |
---|---|---|---|---|
random (1 .. 128) | random (1 .. 16) | 5.77 | 6.84 號 | 5.77 |
128 | 16 | 1,620 | 1,620 | 3.60 |
1 | 1 | 20 萬 | 20 萬 | 84 萬 |
換句話說,改變迴圈計數時,會與一律使用虛擬隨機範圍最大值的確定性版本相較,將原始樣本的最小熵量估計值增加 4.15 位元 (或 250%)。
數據分析
虛擬迴圈計數值,是由每個雜訊函式新增一個額外時間樣本來決定。首先,這些時間樣本不受雜訊函式時間測量結果影響,因為迴圈計數時間樣本之間的落差可預測到雜訊函式時間測量結果。因此,您很難假設他們會增加輸出資料的最小熵。其次,我們非常難想像,迴圈計數樣本與雜訊函式時間測量結果的隨機量約為 250%,因為兩者都依賴相同的雜訊來源,但由於第一個迴圈計數時間樣本可能會從隨機的執行時間變小,因此可能從啟動系統執行測試所需的隨機時間裡稍微提高。
因此,我認為虛擬迴圈計數已足以「操作」在 NIST 套件中「無法取得」特定統計測試和預測式測試的特定套件,但是,這是根據特定知識編寫的預測器測試,能充分準確地預測輸出的虛擬迴圈數量。對專門指定我們程式碼的對手來說,我認為虛擬迴圈計數的「真」最小熵 (約介於 0.20 至 1.62 位元之間),是兩個確定性測試的邊界內。
使用虛擬亂數會導致我們做出額外決定:我們是否以保守的方式估計實際熵內容,是否以每位元組 0.20 位元的速率進行討論 (當虛擬隨機計數函式一律選擇 ml = 1
和 ll = 1
時?如果我們抱持保守的態度,就會花更多時間收集必要的熵;如果審查過程過於寬鬆,就可能會有安全漏洞。最終,這會在安全性 (偏好保守熵估計值) 和效率 (偏好最為合理的熵估算) 之間做出取捨。
處理原始樣本的影響
原始資料
我重複以上報告的三個測試,但開啟時基誤差內部處理功能 (在 kernel.jitterentropy.raw = false
,而非預設值 true
)。為了方便起見,下表在前三列同時包含了原始範例結果 (從以上複製而來),以及底部三列經過處理的結果 (新增新增)。
ml |
ll |
原始 | 最小熵 (位元 / 位元組) | 壓縮預估 | Markov 估計值 |
---|---|---|---|---|---|
random (1 .. 128) | random (1 .. 16) | true | 5.77 | 6.84 號 | 5.77 |
128 | 16 | true | 1,620 | 1,620 | 3.60 |
1 | 1 | true | 20 萬 | 20 萬 | 84 萬 |
ml |
ll |
原始 | 最小熵 (位元 / 位元組) | 壓縮預估 | Markov 估計值 |
---|---|---|---|---|---|
random (1 .. 128) | random (1 .. 16) | false | 歐元 | 歐元 | 歐元 |
128 | 16 | false | 5.78 號 | 歐元 | 5.78 號 |
1 | 1 | false | 5.77 | 6.71 號 | 5.77 |
數據分析
後處理後的最小熵估計值均等同 (最多因隨機性可輕易得知的細微變化),而且等於含虛擬迴圈計數的原始樣本的最小熵估計值。
提醒您,基特熵的處理熵是由 64 個獨立的隨機資料樣本組成,並混合在 64 位元內部狀態緩衝區中。每個原始範例都會對應至 raw = true
資料表中的範例。特別是,合併 64 個樣本與 ml = 1
和 ll = 1
後,處理這些樣本會產生 (5.77 * 8) = 每 8 個位元組 46.2 位元的熵,因為這將造成 (46.2 / 64) = 0.72 位元樣本值與每個未處理的熵位元數為 0.72 位元。
此引數適用於 ml = 1
、ll = 1
、raw = false
測量,但「不會」適用於 ml = 128
、ll = 16
、raw = false
。特別是,將 64 原始樣本與 ml = 128
和 ll = 16
合併在原則上 (1.64 * 64 / 8) = 每個處理的位元組具有 13.1 位元的熵,唯一例外是每位元組 8 位元的硬性限制。
有趣的是,最低的熵估算器會從壓縮估計值切換至馬可夫估算器。我的理論是,後續處理的額外「混淆」足以「通過」壓縮估算。如果時基線處理處理常式中有加密編譯安全漏洞,您或許可以編寫類似的 Estimator,藉此找出較小較小的熵。如果我們使用一般用途測試決定要收集多少原始樣本,以便擁有 256 的最小熵,但攻擊者使用目標攻擊,那麼我們的系統熵庫的熵可能比預期低。這是安全漏洞。
如果時基線處理處理常式的弱點強度極低,實際上或許會降低基特熵內部集區的「true」熵。ml = 1
和 ll = 1
的算術引數顯示,我們無法信任 NIST 測試套件來準確測量所處理資料的實際最小熵,因此可能確實會減少最小熵,而我們的工具只能偵測損失。這麼做會讓前段說明的安全漏洞更加嚴重。
結論
Jitterentropy 的虛擬迴圈數量最好能帶來可觀的益處,如果使用這種迴圈必須強制我們進行安全/效率的取捨,除非能呈現明顯的證據,否則偽隨機性時間確實會大幅增加熵預估次數,而非只犧牲 NIST 調整套件,我們應採用確定性循環的理想效能。
時基線的處理程序也是不易的,因為 (據我所知) 我們並未接受足夠的加密編譯分析和測試,因此值得信任。此外,我們無法透過 NIST 測試套件直接測量經過後處理的資料中的最小熵,因此一旦發生加密編譯安全漏洞,我們便無法輕易偵測到。我認為應該改為依賴 Zircon CPRNG 中的熵 (以 SHA-2 為基礎) 的程式碼,並停用時基線處理功能。
待辦事項
- 針對不同的 Zircon 版本重複執行以上回報的測試,並確定熵預估值維持一致。
- 針對不同平台和目標重複測試 (注意:x86 目標目前無法在早期啟動期間存取系統時鐘,因此早期啟動熵測試和早期啟動 CPRNG 種子尚未支援 x86 上的時基誤差)。
自動執行測試及產生本文件中的報表。具體來說,測試應比較:
- 虛擬迴圈計數與各種確定性迴圈計數值的比較
- 原始樣本與已處理的資料