使計數器 (CTR) 模式對應用程序狀態失去具有強韌性

計數器 (CTR) 模式是一種分組密碼操作模式，具有一些理想的品質（無填充、並行加密和解密），但代價是當非唯一計數器阻塞時會嚴重失敗（隨機數與計數器結合作為分組密碼的輸入）被使用。我想分享我的想法，即即使存在應用程序狀態失去（重新安裝等）可能導致非唯一隨機數的情況下，如何使計數器塊合理地唯一。如果我的想法被證明是合理的，也許它們會對其他人有所幫助。

根據NIST 指南的附錄 B，計數器塊應該是一個在不考慮消息邊界的情況下遞增的簡單計數器（“第一種方法”），或者它應該是隨每條消息更改的隨機數和計數器的組合（“第二種方法”）。這兩種方法都是合理的，但是如果由於應用程序重新安裝或其他原因導致計數器和/或隨機數的歷史失去怎麼辦？

對於 16 字節塊大小的密碼，例如 AES，我建議使用具有以下佈局的計數器塊：

NNNNNN0CCCCCCCCC

六個“N”是隨機數，然後是“0”，一個零字節，最後是九個“C”作為計數器字節。考慮以下用於獲取 nonce 的虛擬碼：

static last_nonce = 0
synchronized get_nonce()
   if (last_nonce == 0)
       last_nonce = get_last_nonce_from_db() // returns 0 on failure
   local nonce = last_nonce + 1
   local since_epoch = get_time_since_epoch_in_msecs()
   if (nonce < since_epoch)
       nonce = since_epoch
   last_nonce = nonce
   return nonce

對於每個新消息，計數器（“C”）字節是隨機的。增量函式只是將整個 16 字節計數器塊視為 16 字節大端整數，其中最右邊的字節首先遞增。這就是 Java 的 CounterMode.increment() 似乎這樣做的方式。這種方法應該具有以下特性：

1. 在數據庫完好無損的正常情況下，nonce 始終是唯一的。在這種情況下，“0”確保消息在與下一個可能的隨機數發生衝突之前至少有 256* *10 - 256 9 個塊。
2. 如果數據庫被重置（這可能是從備份中恢復數據庫，恢復數據庫系統上的快照等，並結合重新啟動應用程序），系統時間應確保唯一的隨機數。
3. 如果兩個數據庫都被重置並且系統時間被恢復，那麼九個隨機計數器字節應該確保兩個單塊消息與相同的 nonce 衝突（具有共同的計數器塊）的機率僅為 256**9 分之一。隨著消息變得更長，可能性變得更糟。

所以它應該在正常情況下正常工作，但在降級情況下仍然表現合理。

我知道這很長，但我想清楚地解釋它。我也意識到其中一些利用了現有的概念（我認為以我對系統時間所做的方式獲得一個唯一的遞增值類似於通常為唯一標識符所做的），但我對如何將這些概念應用於點擊率。

在系統時間重置的情況下，僅依靠塊計數器的隨機化實際上更有可能導致隨機數衝突。隨著消息長度的增加，這種情況只會變得更糟。如果 PRNG 將系統時間作為輸入，或者沒有足夠的種子熵，這種情況會進一步加劇。隨機數中的靜態 0 字節也沒有理由。

一個 48 位時間（以毫秒為單位）計數器、一個 48 位隨機值和一個 32 位計數器比從 0 開始的每個數據塊遞增嗎？

這為每毫秒提供了 9000 年的唯一隨機數，在系統時間重置的情況下隨機碰撞的機率為 280 萬億比 1，並且每個隨機數的最大數據限制為 64GB。這也使隨機數遞增的程式碼更簡單，因為它從 0 開始，並且只是一個 32 位無符號整數。

上面的值是近似值，但接近並提供了具有給定位大小的周期的合理範例。

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