如果在明文中添加了計數器，則具有固定 IV 的 CBC 模式是否安全？
在對較早的相關問題的回答中，我注意到使用與消息加密本身相同的分組密碼和密鑰加密隨機數（例如順序計數器）是NIST SP 800-38A中描述的推薦方法之一，附錄 C，為 CBC 模式加密生成不可預測的 IV。
我進一步指出，事實上，這在數學上等同於使用全零 IV 並在應用 CBC 模式加密之前簡單地將隨機數（填充到完整密碼塊）添加到明文。
但是，在對另一個答案的評論中，有人指出，如果攻擊者可以選擇隨機數，那麼這種構造是微不足道的 CPA 不安全的（如 Rogaway 在本文的第 4 節中指出的那樣）。（當然，可以說，如果你的 nonce 可能被攻擊者控制，那麼你真的應該使用像SIV這樣的完全防止 nonce 濫用的模式，而不是 CBC。）
也就是說，讓我們藉此機會希望一勞永逸地解決這個問題：
- 假設 nonce 值是唯一的並且是根據一些不受攻擊者控制的固定公共計數器序列生成的，就是上面描述的加密方案（即將 nonce 填充到完整的密碼塊，將其添加到明文中，然後加密結果使用 CBC 模式和全零 IV）實際上 IND-CPA 安全嗎？
- 如果是這樣，是否有公開的證據證明這一點？如果沒有，IND-CPA 模型下是否存在不假設攻擊者可以選擇隨機數的已知攻擊？
- 與使用隨機 IV 的標準 CBC 模式相比，定量安全性（例如，攻擊者的優勢作為加密預言查詢數量的函式）如何？AFAICT，兩者基本上只在生日範圍內是安全的，但更詳細的分析可能會很有用。
- 作為獎勵，如果隨機數被填充到某個小於完整密碼塊的固定長度怎麼辦？生成的方案是否仍然是 IND-CPA 安全的（當然，假設 nonce 不會溢出）如果是，這如何影響可以安全加密的消息數量？
- 假設 nonce 值是唯一的並且是根據一些不受攻擊者控制的固定公共計數器序列生成的，就是上面描述的加密方案（即將 nonce 填充到完整的密碼塊，將其添加到明文中，然後加密結果使用 CBC 模式和全零 IV）實際上 IND-CPA 安全嗎？
是的，與傳統 CBC 一樣，基於 nonce 的 CBC 具有合理的 IND-CPA 安全範圍。
- 如果是這樣，是否有公開的證據證明這一點？如果沒有，IND-CPA 模型下是否存在不假設攻擊者可以選擇隨機數的已知攻擊？
是的：下面有一個已發表的證明。 （我把它留給提問者來指定場地限制，以排除網際網路上的假名羽毛狀吹捧者。）
- 與使用隨機 IV 的標準 CBC 模式相比，定量安全性（例如，攻擊者的優勢作為加密預言查詢數量的函式）如何？AFAICT，兩者基本上只在生日範圍內是安全的，但更詳細的分析可能會很有用。
從數量上看，安全性隨著查詢次數乘以塊數而下降，因為密文連結塊有可能與隨機數重合。 但是 CBC 本身的安全性已經隨著區塊總數的平方而下降，這已經大於這個值了（除非每條消息都是一個區塊長）。
- 作為獎勵，如果隨機數被填充到某個小於完整密碼塊的固定長度怎麼辦？生成的方案是否仍然是 IND-CPA 安全的（當然，假設 nonce 不會溢出）如果是，這如何影響可以安全加密的消息數量？
只要 nonce 是不同的，如何格式化 nonce 就無關緊要。 關鍵是在下面的情況（2）中， $ m_{n_1,i+1} \oplus f(\cdots \oplus m_{n_1,i}) $ 是均勻隨機的，因此它與任何固定隨機數重合的機率相等。雖然以隨機數表示 $ n_0 $ ，證明實際上只假設輸入密碼的第一個塊是唯一的。
細節。 一次攻擊 $ A $ 在密碼上是送出序列的隨機算法 $ m_0, m_1, \dots, m_{q-1} $ 的 $ q $ 查詢（可能是自適應的），最多可查詢 $ \ell $ 塊長，到加密預言機；對於最後兩個查詢，oracle 僅返回其中一個的加密，由公平的拋硬幣決定，如果它猜對了硬幣落在哪個面，則攻擊獲勝。攻擊的 IND-CPA 優勢 $ A $ 被定義為$$ \operatorname{Adv}^{\operatorname{IND-CPA}}_{\mathcal O}(A) := |\Pr[A(\mathcal O)] - 1/2|, $$在哪裡 $ \Pr[A(\mathcal O)] $ 是成功機率 $ A $ 在甲骨文上 $ \mathcal O $ . （假設預言機知道如何計算。）
固定塊大小 $ b $ . 每一條消息 $ m_n = m_{n,0} \mathbin| m_{n,1} \mathbin| \cdots $ 將是整數 $ b $ 位塊。對於一個函式 $ F $ 和一個街區 $ \mathit{iv} $ ， 定義$$ \operatorname{CBC}F(\mathit{iv}, m_n) := F(\mathit{iv} \oplus m{n,0}) \mathbin| F(F(\mathit{iv} \oplus m_{n,0}) \oplus m_{n,1}) \mathbin| \cdots. $$
在傳統的 CBC 模式下，隨機函式 $ F\colon {0,1}^b \to {0,1}^b $ 塊，回答查詢 $ n^{\mathit{th}} $ 資訊 $ m_n $ , 加密預言機樣本 $ \mathit{iv}_n $ 均勻隨機地揭示$$ \operatorname{TCBC}_F(m_n) := \mathit{iv}_n \mathbin| \operatorname{CBC}_F(\mathit{iv}_n, m_n). $$ 成功機率 $ \Pr[A(\operatorname{TCBC}_F)] $ 任何攻擊 $ A $ 與傳統的 CBC 相比，它受標準 CBC 定理的限制：對於均勻隨機 $ f $ ,$$ \Pr[A(\operatorname{TCBC}_f)] \leq 1/2 + O(q^2 \ell^2/2^b). $$ 為了允許解密，通常將傳統的 CBC 實例化為 $ F = E_k $ 對於分組密碼 $ E $ 和一個統一的隨機密鑰 $ k $ ; 標準置換換功能替換引理只是添加 $ O(q^2/2^b) $ 到機率。
定義以下替代方案，其中 $ G\colon {0,1}^b \to {0,1}^b $ 是塊的另一個隨機函式：回答查詢 $ n^{\mathit{th}} $ 資訊 $ m_n $ , 神諭揭示$$ \operatorname{NCBC}_{F,G}(m_n) := G(n) \mathbin| \operatorname{CBC}_F(G(n), m_n). $$ 如果 $ F = G $ ， 叫它 $ \operatorname{NCBC}_F $ . 考慮以下情況：
- $ G = g $ 是均勻隨機函式 $ g $ 獨立於 $ F $ . 顯然，這與傳統的 CBC 模式相同 $ F $ ，因為每個輸出 $ g(n) $ 是獨立的均勻隨機的不同的 $ n $ 就像 $ \mathit{iv}n $ ， 所以$$ \Pr[A(\operatorname{NCBC}{F,g})] = \Pr[A(\operatorname{TCBC}_F)]. $$
- $ F $ 和 $ G $ 是相同的均勻隨機函式 $ f $ . 只有在以下情況下，這種情況才能與前一種情況區分開來 $ n_0 $ 恰逢 $ m_{n_1,i+1} \oplus f(\cdots \oplus m_{n_1,i}) $ 對於一些 $ n_0 $ , $ n_1 $ , $ i $ 在送出給預言機的消息中，發生機率為 $ O(q^2 \ell/2^b) $ 在哪裡 $ \ell $ 是平均查詢長度。因此，如果 $ R $ 是這個巧合的事件， $$ \begin{align*} \Pr[A(\operatorname{NCBC}f)] &= \Pr[A(\operatorname{NCBC}f) \mathrel| R] \Pr[R] \ &\quad + \Pr[A(\operatorname{NCBC}f) \mathrel| \lnot R] \Pr[\lnot R] \ &\leq \Pr[R] + \Pr[A(\operatorname{NCBC}f) \mathrel| \lnot R] \ &= O(q^2 \ell/2^b) + \Pr[A(\operatorname{NCBC}{f,g})]. \end{align*} $$ （讀者練習：寫下一個具體的公式 $ \Pr[R] $ . 為了更簡單，替換 $ m{n_1,i+1} \oplus f(\cdots \oplus m{n_1,i}) $ 通過，說， $ m{n_1,i+1} \oplus f(n_1\mathbin|i) $ ：確保不同的輸入 $ f $ 只能提高連結值之一與隨機數之一重合的機率，並且每個輸出 $ f $ 在不同的輸入上是獨立的均勻隨機的。）
- $ F = G = \pi $ 對於均勻隨機排列 $ \pi $ . 通過關於用均勻隨機排列代替均勻隨機函式的標准定理，對於任何算法 $ A $ 製造 $ q $ 查詢， $$ \begin{align*} \Pr[A(\operatorname{NCBC}_\pi)] &\leq \Pr[A(\operatorname{NCBC}_f)] + q(q - 1)/2^{b + 1} \ &= \Pr[A(\operatorname{NCBC}f)] + O(q^2/2^b). \end{align*} $$ （或者，可以使用更好但不太標準的界限 $ \Pr[A(\operatorname{NCBC}\pi)] \leq \delta \cdot \Pr[A(\operatorname{NCBC}_f)] $ 在哪裡 $ \delta = (1 - (q - 1)/2^b)^{-q/2} $ .)
- $ F = G = E_k $ 對於一個統一的隨機密鑰 $ k $ 和一個分組密碼 $ E $ . 之間的距離 $ \Pr[A(\operatorname{NCBC}{E_k})] $ 和 $ \Pr[A(\operatorname{NCBC}\pi)] $ 是PRP的優勢 $ \operatorname{Adv}^{\operatorname{PRP}}E(A’) $ 的 $ A’(\phi) := A(\operatorname{NCBC}\phi) $ 區分分組密碼 $ E $ 來自均勻隨機排列；想必 $ E $ 被多年的密碼分析選擇為所有合理數字的這個距離設置一個自信的界限 $ q \ell $ 分組密碼評估。
因此，對基於 nonce 的 CBC 生成的攻擊的成功機率 $ q $ 平均長度查詢 $ \ell $ 受以下限制：
$$ \begin{align*} \Pr[A(\operatorname{NCBC}{E_k})] &\leq \Pr[A(\operatorname{NCBC}\pi)]
- \operatorname{Adv}^{\operatorname{PRP}}_E(A’) \ &\leq \Pr[A(\operatorname{NCBC}_f)]
- O(q^2/2^b)
- \operatorname{Adv}^{\operatorname{PRP}}E(A’) \ &\leq \Pr[A(\operatorname{NCBC}{f,g})]
- O(q^2 \ell/2^b)
- O(q^2/2^b)
- \operatorname{Adv}^{\operatorname{PRP}}_E(A’) \ &= \Pr[A(\operatorname{TCBC}_f)]
- O(q^2 \ell/2^b)
- \operatorname{Adv}^{\operatorname{PRP}}_E(A’) \ &\leq 1/2 + O(q^2 \ell^2/2^b)
- O(q^2 \ell/2^b)
- \operatorname{Adv}^{\operatorname{PRP}}_E(A’) \ &= 1/2 + O(q^2 \ell^2/2^b)
- \operatorname{Adv}^{\operatorname{PRP}}_E(A’), \end{align*} $$
或者
$$ \begin{equation} \operatorname{Adv}^{\operatorname{IND-CPA}}{\operatorname{NCBC}{E_k}} \leq O(q^2 \ell^2/2^b)
- \operatorname{Adv}^{\operatorname{PRP}}_E(A’), \end{equation} $$
即與具有分組密碼的傳統CBC基本相同 $ E $ .