NIST 800-90B /Non-IID track - min-entropy result > 8 for 8-bit symbol
我正在根據 NIST 800-90B Non-IID 軌道對雜訊源進行分析。因此，我在數據記錄上應用了 non-iidmain.py 腳本，它提供了以下輸出：
reading 1000000 bytes of data Read in file ../some_data_rec.bin, 1000000 bytes long. Dataset: 1000000 8-bit symbols, 256 symbols in alphabet. Output symbol values: min = 0, max = 255 Running entropic statistic estimates: - Most Common Value Estimate: p(max) = 0.00424421, min-entropy = 7.88029 - Collision Estimate: p(max) = 0.0119504, min-entropy = 6.3868 - Markov Estimate (map 6 bits): p(max) = 9.06705e-222, min-entropy = 5.73662 - Compression Estimate: p(max) = 0.00790364, min-entropy = 6.98327 - t-Tuple Estimate: p(max) = 0.006, min-entropy = 7.38082 - LRS Estimate: p(max) = 0.00389867, min-entropy = 8.0028 ....我想知道的是LRS Estimate的輸出，它提供了****8.0028的最小熵。字母表中的符號定義為 256，即一個字節。那麼，一個字節/8 位的單個符號怎麼可能提供比它能夠描述的更多的熵呢？我預計一個字節的最大熵值應該是 8 位？
這裡有三個獨立的合理問題。
- LRS 估計是什麼意思？
- 軟體是否正確計算？
- 像這樣愚蠢的熵估計工具對您的目標有用嗎？
設置是我們假設從黑盒中出來的數據的*特定係列生成過程。*生成過程的家庭都非常簡單。例如：
- 黑盒子裡的小鬼擲出一個 256 面的骰子，面的機率未知 $ p_i $ 獨立於字元串中的每個八位字節。
- 黑匣子中的 gremlin 通過具有未知發射機率的隱馬爾可夫模型從未知狀態發射輸出 $ e_i $ 和轉移機率 $ t_{ij} $ .
這些模型中的每一個都有一定的最小熵度量，它由參數的選擇決定，例如 $ p_i $ . NIST 工具與任何其他熵估計工具一樣，通過擬合參數並在具有擬合參數的模型的特定情況下評估或估計最小熵的上限來估計最小熵。顯然 8.0028 是八位字節最小熵的上限。我們怎麼去那裡？
為了解決 (1)，LRS 估計意味著什麼，LRS 估計器假設了一個生成過程，如下所示：
- 黑匣子裡的一個小鬼有一頂帽子 $ d $ 上面有不同長度的字元串， $ i^{\mathit{th}} $ 字元串有 $ n_i $ 副本。它洗牌並拉出一根繩子以添加到輸出中；然後它重複。
估計器的工作原理是根據數據中重複和不重複的連續子字元串來猜測可能在帽子中的幾個字元串，並使用這些字元串的頻率作為它們出現機率的估計值。（計算的完整細節在 NIST SP800 90A，§6.3.6 中。）根據這些機率，它使用標準產生最小熵的估計 $ -\max_i \log p_i $ 公式。
它沒有考慮輸出中的所有連續子串（它們存在組合爆炸），因此它忽略了一些機率空間，因此略微低估了它確實考慮的每個子串的機率，這具有略微高估的效果min-entropy——這可以解釋為什麼它似乎會產生每八位字節剛剛超過 8 位的熵率。
現在，為了解決（2），軟體是否正確實現了它？ 這是 codereviews.se 的問題，如果您想確保假設的模型和機率估計器是合理的並且 NIST 的意圖是什麼，那麼可能是 stats.se 的問題。
最後，**要解決（3），這是否對您的目標有用，**答案不是很大。如果出現這些模式，它將檢測數據中的某些模式系列。像您的樣本中的 LRS 估計這樣的高估計沒有用：它們只是意味著這種特定模式沒有出現。低估計表明，NIST 的某個人甚至沒有考慮您的特定雜訊源，可以預測其輸出並獲得相當大的成功機會。這通常是不好的跡象。 所以不要擔心 LRS 的略大於 8-bits-per-octet 的估計：擔心馬爾可夫模型的 ~5-bits-per-octet 估計！ 您的設備是否在具有更可預測的發射機率的內部狀態之間交替？
您真正需要做的是從對手的角度研究相關物體的物理特性，並嘗試找到最好的方法來預測輸出，了解您的特定雜訊源是如何工作的。然後計算該模型的熵。如果它高於 NIST 的所有估計值，那麼要麼你有一個幸運的樣本，要麼 NIST 的某個人甚至不知道你在做什麼，他比你更擅長研究你的雜訊源。
我感覺到你的痛苦。看看如何解釋 NIST 測試文件的熵結果？. 這個問題非常受歡迎（-3 票），但對於熵的異常沒有提供令人信服的答案 $ \pi $ 文件。
測試套件清楚地以位/字節顯示它的輸出。我得到了最長重複子串測試估計 = 8.5665 ，不得不撓頭。顯然這是不可能的。它與壓縮測試估計值 = 0.0828647 相比很差。 那是兩個數量級。拼寫錯誤也令人擔憂。
Recommendation for the Entropy Sources Used for Random Bit Generation中的評估公式 可能很好，但我只能得出這個軟體是褲子的結論。曾是一個
$$ assert $$聲明太多要問？除了標題中出現的首字母縮寫詞 NIST 之外，無法保證這些工具能夠可靠地工作。該軟體特別聲明沒有。您還會發現 C++ 實現給出的值與 Python 完全不同。熵不能是 Pythonic。 我得出的結論是，該軟體不可靠，因此對於加密使用不安全。如果您研究了許多關於熵生成和真隨機數生成器的論文，您將很難找到正在使用的該軟體的單個實例。我沒有找到任何參考資料。這是反對它的強有力的軼事證據。我已將其刪除，並將改用強大的壓縮工具進行熵測量。它們非常適合尋找相關性，因為這是它們存在的理由
PS。我還問過 GitHub 上的 NIST 工具是否可靠地測量熵？但沒有人感興趣。
聚苯乙烯。看看我對如何解釋 NIST 測試文件的熵結果的回答？ 在論文和連結中，您會找到對 11 甚至 21 位/字節的熵率的參考。馬爾可夫模型在混淆時喜歡輸出 21。這只是表明在程式碼實現中沒有使用嚴謹性。對 90B 的獨立調查得出的明確結論是，它們完全不可靠，並且非常不適合現實世界的熵。