隨機 CTR 初始計數器值的策略
Alice 有一個秘密密鑰，她用它來加密 CTR 模式下的消息。CTR 模式極易被計數器重用，而 Alice 有一個問題：她的記憶力很差，沒有筆可以寫下任何東西。她有足夠好的記憶力來發送一條消息，但在消息之間，她有時會忘記她使用過的計數器值。她的前臂上紋著鑰匙。她沒有一塊手錶可以給她一個方便的非重複輸入。她有一個平衡的硬幣，她可以翻轉它來生成隨機數。她想確保她不會重複使用計數器值，因為 Eve 潛伏在周圍，使異或事物成為一種愛好，她甚至可以建議一些明文供 Alice 加密。
換句話說，我有一個嵌入式設備，它在 ROM 中有一些程式碼和一個密鑰，還有一個硬體 RNG，但沒有時鐘（不像讓計數器 (CTR) 模式對應用程序狀態失去具有強韌性）並且沒有持久的可重寫儲存（不像CTR 模式具有激進的密鑰輪換策略的隨機數）。該設備使用 ROM 中的一個密鑰發出使用 AES-CTR 加密的消息。這些消息的完整性超出了這個問題的範圍。設備可能隨時斷電，並且在那個時候，它失去了對先前計數器值的跟踪。它通常會在重置之間發送許多消息，但在某些情況下，攻擊者可能會安排在不合時宜的時間切斷電源。
避免計數器重用的最佳策略是什麼，以及在多少流量之後計數器重用的機率變得不可忽略？例如，我可以為每條消息生成一個新的初始計數器，或者在每次重置時生成一個新的初始計數器。我可以從目前計數器值開始每條消息，或者使用諸如 96 位隨機性和從 0 開始的每條消息計數器之類的方案。（沒有消息超過 $ 2^{32}-2 $ 塊長。）這是否會影響碰撞機率？
讓 $ 2^m $ 是塊中的平均消息長度。
- 當對每個塊的整個 128 位 IV 使用獨立的隨機數時，您會期望在 $ 2^{64} $ 塊，即 $ 2^{64-m} $ 消息。（但是您將數據大小增加了一倍。）
- 當使用 96 位 nonce 和 32 位計數器時，您會期望在之後的 nonce 衝突 $ 2^{48} $ 消息。這比上面的好，如果 $ m > 16 $ 當然更有效，因為生成的隨機數更少。
- 當為後續塊遞增的消息使用 128 位初始隨機數時，數學變得有點棘手。兩個的機率 $ 2^m $ -block 消息得到重疊的計數器範圍大約是 $ 2^{-(128-m-1)} $ 因為當第二條消息具有初始隨機數時它們重疊 $ 2^m $ 在任一方向的第一個。這至少意味著 $ 2^{64 - (m+1)/2} $ 消息，這比上述任何一個都好，如果 $ 1 < m < 32 $ .
確切的消息長度分佈會影響可以發送多少塊與消息，但通常消息大小的實際最大值不會比平均值大幾個數量級，因此改變 $ m $ 上面以反映這將給出最壞情況的估計。 4. 讓下一條消息從前一個隨機數繼續，直到重置與上述相同，但更長的“消息”等於在重置之間發送的所有消息的串聯。和 $ 2^k $ 重置之間的消息至少 $ 2^{64-(m+k+1)/2} $ 碰撞前的預期會話，即 $ 2^{64-(m-k+1)/2} $ 消息，如果 $ k>0 $ .
但是，如果您假設攻擊者可以控制重置發生的時間，情況會變得更糟。在每條消息之後，攻擊者可以導致重置（如果在不久的將來沒有碰撞）或讓計數器繼續其碰撞之旅。重用 $ k $ 從上面來看，對於攻擊者可以預期的正常重置頻率，兩次重置將有大約 $ 2^{-(128-m-k)} $ 碰撞的機會，因此碰撞前的預期重置次數約為 $ 2^{64-(m+k)/2} $ ，這比上一個選項更糟糕。 5. 使用 96 位隨機數和 32 位計數器結構，但要跟踪前一條消息的結束位置。只要在由 nonce 定義的 32 位塊內有消息空間，選擇 IV 以便它從前一個消息結束的地方繼續。如果塊用完或自上一條消息以來設備已重置，則隨機選擇一個新的。
在最好的情況下，你的東西 $ 2^{32-m} $ 每個隨機數的消息並且僅在之後才發生衝突 $ 2^{48+32-m}=2^{80-m} $ 塊，這比上述任何一個都好。即使在最壞的情況下，攻擊者會在每條消息後重置設備，您也可以保證 $ 2^{48} $ 碰撞前的預期消息。
在實踐中，我會選擇 32 位計數器，無論是否優化以從先前的消息繼續 - 即上面的 2. 或 5.。沒有比這更糟糕的攻擊了 $ 2^{48} $ 消息和數學很容易。