來自 FIPS 140-1 的隨機性測試問題以及與 140-2 的比較

在FIPS 140 -1 中有 4 個統計隨機數生成器測試（單比特測試、撲克測試、執行測試和長期執行測試。然後 FIPS 140-2 出現並據說收緊了這些測試的標準。我會在此處提供更改的簡短摘要：

單比特測試

計算 20,000 比特流中的個數。用 X 表示這個數量。

FIPS 140-1: The test is passed if 9,654 < X < 10,346.
FIPS 140-2: The test is passed if 9,725 < X < 10,275.

撲克測試

將 20,000 比特流分成 5,000 個連續的 4 比特段。計算並儲存 16 個可能的 4 位值的出現次數。將 f(i) 表示為每個 4 位值 i 的個數，其中 0 ≤ i ≤ 15。

評估以下內容：X = (16/5000) * (SUM i=0 -> i=15

$$ f(i) $$^2) - 5000

FIPS 140-1: The test is passed if 1.03 < X < 57.4.
FIPS 140-2: The test is passed if 2.16 < X < 46.17.

執行測試

一次執行被定義為全 1 或全 0 的連續位的最大序列，它是 20,000 位樣本流的一部分。應計算並儲存樣本流中所有長度 (>= 1) 的執行的發生率（對於連續的零和連續的一）。

1. 如果發生的執行次數（長度為 1 到 6）都在下面指定的相應間隔內，則測試通過。這對於零和一都必須成立；也就是說，所有 12 個計數必須位於指定的間隔內。
2. 如果發生的執行次數（長度為 1 到 6）都在下面指定的相應間隔內，則測試通過。這對於零和一都必須成立；也就是說，所有 12 個計數必須位於指定的間隔內。出於此測試的目的，大於 6 的執行被視為長度為 6。

FIPS 140-1：

Length of Run   Required Interval
1  2267-2733
2  1079-1421
3  502-748
4  223-402
5  90-223
6+ 90-223

FIPS 140-2：

Length of Run   Required Interval
1  2343–2657
2  1135–1365
3  542-708
4  251-373
5  111-201
6+ 111-201

長跑測試

在 20,000 位的樣本上，如果沒有長執行，則測試通過。

FIPS 140-1: A long run is defined to be a run of length 34 or more (of either zeros or ones).
FIPS 140-2: A long run is defined to be a run of length 26 or more (of either zeros or ones). 

因此，總的來說，通過測試的標準似乎有所縮小。不過我有幾個問題：

1. 在 FIPS 140-2 中，這些測試列在第 57 頁，但被刪除了。即有一條貫穿所有文本的線。為什麼是這樣？在草案 140-3 中，測試根本沒有出現..？
2. 如果通過更窄/更嚴格的標準，將測試標準從 140-1 縮小到 140-2 是否會產生更好和更強的 RNG？還是因為允許的差異較小而使其變弱？
3. 對於執行測試，在執行此操作並檢查執行是否在所需的時間間隔內時，例如 2343–2657 是包含還是不包含？那麼如果執行是 2343或2657 是通過還是失敗？

Q1：為什麼要取消這些測試？

這些測試在目前 FIPS 140-2的第 57-58 頁中被刪除，因為它們不再是目前 FIPS 140-2 標準的一部分，因為這些頁面所屬的 2002 年 12 月 3 日的更改通知 2。

我對刪除這些測試的理由的猜測是

• 人們意識到使用這些 RNG 測試和邊界的原則是不健全的：

  1. 在測試加密安全偽 RNG 時，“ 使用已知答案的加密算法測試 ”（4.9.1）就足夠了，而對 PRNG 輸出的統計測試只是一個麻煩：它可以報告的唯一錯誤是誤報（否則當打算測試實現時，CSPRNG 的定義就會被破壞）！
  2. 在測試真正的 RNG 時，事實是很難製作一個通過這些測試（尤其是 FIPS 104-2 中的測試）並具有良好可靠性的物理 TRNG 源，而實際 TRNG 源和測試點之間沒有一些調節，特別是如果您考慮到過程和溫度變化（在現場，您經常會以比完美 RNG 預測的高得多的速度出現故障）。這可以修復，例如在 TRNG 之後插入 LFSR，但是 TRNG 源的故障通常不會被規定的測試擷取！

• 人們意識到，在某些無人值守的應用程序中強制執行這些測試“ 在模組通電時 ”（至少需要 4 級）是不切實際的，尤其是智能卡（誠然不針對 4 級），其中：

  1. 不能有操作員重置“RNG 測試失敗”條件。
  2. 可能有數百個設備（智能卡為數百萬個），這意味著在強制測試中結合 1 個和誤報的現場故障數量是不可接受的。
  3. 此外，在設備的正常（或至少實際上是不可避免的）操作中，智能卡每秒可能會意外啟動數次；我目睹了應用程序關閉/打開任何無法辨識的接觸式智能卡的電源，就像沒有明天一樣，當非接觸式智能卡放在一些完全合理的ISO/IEC 14443或NFC閱讀器前面時，也會發生這種情況。因此，需要對“ 加電 ”進行一些創造性的重新定義，暗示打算使用而不是僅僅建立運營權力。
  4. 我們希望在通電後快速做好準備。

因此，如果您在更改通知 2 之前按照 FIPS 140-1 或 FIPS 140-2 的字母進行了某些操作，那麼即使它執行良好，它也必然會在某個時候報告失敗（並停止執行，除非是有時不切實際的人為行為）；如果發生最可能和最危險的現場故障原因（TRNG 源卡住、幾乎卡住或其他非工作狀態，如與電源紋波同步），這種令人遺憾的情況並不是一個很好的保險，它會停止工作。將誤報率降低到最低限度的嘗試往往會嚴重加劇讓有危險缺陷的設備執行的風險。

Q2：這些變化是一種改進嗎？

取消規定的測試是一個很大的改進。現在，有能力的實施者至少能夠製造出在沒有缺陷時可靠執行，並在出現缺陷時可靠地停止執行的東西。並且添加允許以犧牲實際現場安全為代價通過認證的條件（如 LFSR）的動機已經消失。以前，對於一些完美的 TRNG 源（比如有幾個百分比的偏差，這在 CSPRNG 之後很好），規定的內容不能成為防止 TRNG 源可能存在缺陷的主要防禦措施。RNG 認證的所有現代方法，如AIS31，認識到需要在調節之前訪問 TRNG 源，或/和源模型，並調整測試（包括在第一個失敗時進行更全面的測試）。

從 FIPS 140-1 到 FIPS 140-2 的測試限制的更改以及更改通知 1 使每個測試顯著更加嚴格（因此在用於測試無條件 TRNG時更加不切實際，並且即使對於條件之一或 CSPRNG）。我想我記得讀過或聽說過（對於不確定的非參考的不精確性），至少這些變化中的一些也與測試不獨立的事實有關（因此，如果 20000 4 個測試中的位來自相同或不同的執行，後者顯著增加了誤報率）。執行測試中接受水平的變化在 FIPS 140-2 變更通知 1（之前的 FIPS 140-2）中進行的記錄（第 54 頁）被記錄為“ 更正 ”，這似乎是可信的。請注意，對於 FIPS 140-2 的執行測試，該問題給出了FIPS 140-2 的錯誤邊界表，而沒有更改通知 1。

更新：正如雨披在評論中指出的那樣，假陽性率從 FIPS 140-1 到 FIPS 140-2 (CN1) 的增加是驚人的，假設一個完美的來源，在單比特測試中超過一百倍：$$ 1-\sum_{i=9,655}^{10,345}{20,000\choose i}/2^{20,000}\approx1/974,603\text{ for FIPS 140-1} $$ $$ 1-\sum_{i=9,726}^{10,274}{20,000\choose i}/2^{20,000}\approx1/9,662\text{ for FIPS 140-2} $$ 更糟糕的是，如果將良好來源定義為偏差小於某個門檻值的來源（物理 TRNG 的合理要求），則誤報率可能會從 FIPS 140-1 界限的罕見到 FIPS 140-2 的完全破壞界限；這可能有助於做出正確的決定並完全取消測試。

Q3：執行測試的界限是否包含在內？

也許這可以通過計算失敗的機率來確定，無論是否有為真正的隨機源給出的間隔限制，並查看是否出現了一些整數。

但為什麼要關心？對條件 RNG（包括任何 CSPRNG）的輸出進行統計測試是沒有意義的；自 2002 年末以來，它並不是必不可少的橡皮圖章。雖然必須對未調節的 TRNG 源進行統計測試（並且 FIPS 140-1 和 2 中的測試相當可靠），但 FIPS 140-1 以及更多 FIPS 140-2 的接受水平通常過於苛刻，除非有一些備份策略（例如重做一個更完整的測試；請注意，重做相同的測試會極大地改變其原始接受水平的含義）。

引用自：https://crypto.stackexchange.com/questions/15052