寫在最前面

主要在 哈工大密碼學課程 張宇老師課件 的基礎(chǔ)上學習記錄筆記。

內(nèi)容補充：駱婷老師的PPT
《introduction to modern cryphtography》–Jonathan Katz, Yehuda Lindell（現(xiàn)代密碼學——原理與協(xié)議）中相關(guān)章節(jié)
密碼學復(fù)習筆記 這個博主好有意思

初步筆記，如有錯誤請指正

快速補充一些密碼相關(guān)的背景知識

---

私鑰加密與偽隨機性 第二部分

1. 本節(jié)課學習另外兩種私鑰加密安全理論：選擇明文攻擊（CPA）下不可區(qū)分性、選擇密文攻擊（CCA）下不可區(qū)分性以及相關(guān)的密碼學原語、假設(shè)、構(gòu)造和證明。這些攻擊更好的刻畫了現(xiàn)實世界中敵手的能力，相應(yīng)的密碼學方案也是目前真正在實際使用的。

2. 目錄：流加密與CPA，CPA安全加密方案，操作模式，CCA安全加密方案

流加密與CPA

3. 流加密方案（Stream Cipher）

   • 首先介紹當有多個消息需要被傳遞時，如何利用之前學習的基于PRG的加密方案來保護消息。
   • 思路：受一次一密方案的啟發(fā)，通過將變長消息與密鑰的異或來加密
   • 流加密方案：通過將多個消息“拼成”一個消息，與偽隨機的比特流（密鑰流）異或來加密
   • 密鑰流：由一個變長的偽隨機生成器產(chǎn)生
   • 優(yōu)點：邏輯簡單，比分組密碼更快
   • 缺點：難以做到安全

4. 采用流加密方案的安全多重加密

   • 同步模式：用一個流中不同部分分別加密各個消息；
   • 異步模式：以密鑰和初始向量一起作為輸入來產(chǎn)生流，每個明文的加密采用相同的密鑰和不同的初始向量
     • 初始向量（Initial Vector），$IV$是隨機選取的并且是公開的；其生成是隨機的并不受控制，但生成后并不保密；密鑰的生成是隨機的并不受控制，但生成后也要保密。
   • 兩種模式差異：
     • 同步模式適合持續(xù)通信場景，例如語音；異步模式適合間斷通信場景，例如即時消息。

5. 流密碼的安全性

   1. 現(xiàn)狀：沒有標準化和流行的方案，安全性仍有疑問，例如在802.11中WEP協(xié)議的RC4，線性反饋移位寄存器（Linear Feedback Shift Registers）；
   2. 警告：不要使用任何流加密方案，如果一定需要的話，采用由分組加密方案構(gòu)造的。
   3. eStream項目致力于設(shè)計安全的流密碼

6. 相關(guān)密鑰：真實世界例子

   • 用于多重加密的密鑰（初始向量和密鑰對）必須是獨立的。否則，前面的攻擊就會生效；
   • 對于802.11b WEP的若干攻擊：
     • WEP為異步模式，$\mathsf{Enc}(m_i):=?I{V}_i,G(I{V}_i\Vert k)\oplus m_i?$
     • $IV$長度為24比特，在$2^{24}\approx$ 16M 幀后$IV$會產(chǎn)生重復(fù)；
     • 在一些WiFi網(wǎng)卡上，在電源重啟后$IV$重置為0；
     • $I{V}_i=I{V}_{i?1}+1$. 對于RC4，在40,000幀后可以恢復(fù) $k$ ；

多重加密

7. 多重加密（Multiple Encryptions）

   • 在一次一密中，一個密鑰不可以用于對多個消息的加密；否則，就是不安全的。如果敵手能夠獲得用同一個密鑰加密后的多個密文，則之前的方案都是不安全的；為此，我們需要新的加密方案來防御這樣的攻擊。
   • 多個明文的加密實驗${\mathsf{PrivK}}_{\mathcal{A},\Pi }^{\mathsf{mult}}(n)$，當一次加密多個明文時，竊聽者敵手能夠區(qū)分出兩組明文嗎？
   • 一個敵手$\mathcal{A}$與一個挑戰(zhàn)者$\mathcal{C}$進行3輪交互：
     1. $\mathcal{A}$選擇兩個長度相同、內(nèi)容不同明文向量${\vec{M}}_0=(m_0^1,\dots ,m_0^t)$, ${\vec{M}}_1=(m_1^1,\dots ,m_1^t)$，其中兩個向量中同一位置的明文長度相同$?i,|m_0^i|=|m_1^i|$，發(fā)送給$\mathcal{C}$；
     2. $\mathcal{C}$根據(jù)密鑰生成算法生成一個新密鑰$k\leftarrow \mathsf{Gen}(1^n)$，一個隨機比特 b ← { 0 , 1 } b \gets \{0,1\} b←{0,1}。對向量${\vec{M}}_b$中每個明文加密 $c^i\leftarrow {\mathsf{Enc}}_k(m_b^i)$ 得到一個密文向量 $\vec{C}=(c^1,\dots ,c^t)$ ，并發(fā)送給$\mathcal{A}$；
     3. $\mathcal{A}$輸出對所加密明文向量的猜測$b^{\prime }$，若$b=b^{\prime }$，則$\mathcal{A}$成功；否則，失敗；
   • 這與之前的單個消息不可區(qū)分實驗類似的，區(qū)別在于用同一個密鑰加密的多個消息。敵手可以獲得多個明文的密文，比單個明文不可區(qū)分實驗中的敵手有更強的能力。

8. 多重加密安全定義

   • $\Pi$ 是竊聽者出現(xiàn)時不可區(qū)分的多重加密方案，如果任意PPT的敵手$\mathcal{A}$, 存在可忽略的函數(shù)$\mathsf{negl}$ 使得

     $\mathrm{Pr}\left[{\mathsf{PrivK}}_{\mathcal{A},\Pi }^{\mathsf{mult}}(n)=1\right]\le \frac{1}{2}+\mathsf{negl}(n).$

   • 根據(jù)這個定義，來分析迄今學習的密碼學方案是否是多重加密不可區(qū)分的？

9. 攻擊確定性加密方案

   • 問題：如果一個加密方案中加密算法是確定性的，即同一個明文會被同一個密鑰加密成同一個密文，那么該加密方案是多重加密安全的嗎？
   • 攻擊：對于確定性加密方案，敵手可以構(gòu)造$m_0^1=m_0^2$ 并且 $m_1^1\ne m_1^2$，然后當$c^1=c^2$，輸出 $b^{\prime }=0$，否則 $b^{\prime }=1$。
   • 因此，確定性加密方案不是多重加密安全的，我們需要新的密碼學原語來防御多重加密攻擊。接下來，我們介紹一種更強的攻擊，其涵蓋了多重加密攻擊。只要防御了這個新定義的攻擊，也就同時防御了多重加密攻擊。

CPA安全加密方案

10. 選擇明文攻擊（Chosen-Plaintext Attacks (CPA)）（思考）

    • 敵手具有獲得其所選擇明文對應(yīng)的密文的能力。

    • 第二次世界大戰(zhàn)中的例子：美國海軍密碼分析學家相信密文“AF”表示日語中的“中途島”；但美國將軍不認為中途島會遭到攻擊（？這里沒看懂）；美國海軍密碼分析學家發(fā)送了一個明文，中途島淡水供給不足；日本軍隊截獲的明文，并發(fā)送了一段密文，“AF”淡水不足；美國軍隊派出三艘航空母艦并且取勝。

    • 這里例子里，美國海軍密碼分析學家選擇了明文并得到了密文。

CPA安全實驗、預(yù)言機訪問（oracle access）

11. CPA安全實驗

    • CPA不可區(qū)分實驗 ${\mathsf{PrivK}}_{\mathcal{A},\Pi }^{\mathsf{cpa}}(n)$:
      1. 挑戰(zhàn)者生成密鑰 $k\leftarrow \mathsf{Gen}(1^n)$；（這里與竊聽者不可區(qū)分實驗相比，密鑰的生成提前了，這是為了下一步提供加密預(yù)言機）
      2. $\mathcal{A}$ 被給予輸入 $1^n$ 和對加密函數(shù) ${\mathsf{Enc}}_k(?)$的預(yù)言機訪問（oracle access） ${\mathcal{A}}^{{\mathsf{Enc}}_k(?)}$ ，輸出相同長度 $m_0,m_1$ ；
      3. 挑戰(zhàn)者生成隨機比特 b ← { 0 , 1 } b \gets \{0,1\} b←{0,1}，將挑戰(zhàn)密文 $c\leftarrow {\mathsf{Enc}}_k(m_b)$ 發(fā)送給 $\mathcal{A}$；
      4. $\mathcal{A}$ 繼續(xù)對 ${\mathsf{Enc}}_k(?)$的預(yù)言機的訪問，輸出$b^{\prime }$；如果$b^{\prime }=b$，則$\mathcal{A}$成功${\mathsf{PrivK}}_{\mathcal{A},\Pi }^{\mathsf{cpa}}=1$，否則 0。
    • 敵手對加密函數(shù)預(yù)言機訪問是指，敵手以任意明文作為輸入，可以從預(yù)言機得到對應(yīng)密文。此處，密鑰是已經(jīng)提前生成的，因此才能通過加密函數(shù)預(yù)研機得到密文，但仍對敵手保密。預(yù)言機是一個形象的比喻，它是一個黑盒，只接收輸入并返回輸出；訪問者不需要了解其內(nèi)部構(gòu)造。
    • 該實驗與竊聽者不可區(qū)分實驗的區(qū)別在于，敵手可訪問加密預(yù)言機，在實驗過程中始終可以，包括在產(chǎn)生兩個明文階段，以及在收到挑戰(zhàn)密文后猜測被加密明文階段，獲得任意明文被同一密鑰加密的密文；而且密文是逐個獲得，可以根據(jù)之前的明文和密文對來“適應(yīng)性地”構(gòu)造新的查詢。
    • CPA敵手比多重加密的敵手更“強大”，因為多重加密敵手是可以一次性地獲得一組密文，而CPA敵手可以根據(jù)已經(jīng)獲得的明文和密文“多次適應(yīng)性地”再次獲得密文。

12. CPA安全

    • $\Pi$ 是CPA不可區(qū)分加密方案 (CPA安全的)，如果任意概率多項式時間算法$\mathcal{A}$，存在可忽略的函數(shù)$\mathsf{negl}$使得，

      $\mathrm{Pr}\left[{\mathsf{PrivK}}_{\mathcal{A},\Pi }^{\mathsf{cpa}}(n)=1\right]\le \frac{1}{2}+\mathsf{negl}(n)$

    • 定理：CPA安全也是多重加密安全的。證明略。直覺上，CPA敵手比多重加密敵手更強大。

    • 之前的方案也難以實現(xiàn)CPA安全；

    • 多重加密安全意味著CPA安全？（作業(yè)）顯然是否定的。那么，思考兩種安全定義的區(qū)別成為解題的關(guān)鍵。

操作模式

偽隨機函數(shù)PRF

13. 偽隨機函數(shù)（Pseudorandom Function）概念

    • 為了實現(xiàn)CPA安全，之前的PRG提供的隨機性不夠用了，需要新的數(shù)學工具為加密提供額外的隨機性。為此引入偽隨機函數(shù)（PRF），是對偽PRG的泛化：PRG從一個種子生成一個隨機串，PRF從一個key生成一個函數(shù)；
    • 帶密鑰的函數(shù)Keyed function F : { 0 , 1 } ? × { 0 , 1 } ? → { 0 , 1 } ? F : \{0,1\}^* \times \{0,1\}^* \to \{0,1\}^* F:{0,1}?×{0,1}?→{0,1}?
      • F k : { 0 , 1 } ? → { 0 , 1 } ? F_k : \{0,1\}^* \to \{0,1\}^* Fk?:{0,1}?→{0,1}?, $F_k(x)\stackrel{\text{def}}{=}F(k,x)$
      • 兩個輸入到一個輸出，看上去像，但不是加密函數(shù)；輸入key，得到一個一輸入到一輸出的函數(shù)；
    • 查表Look-up table $f$: { 0 , 1 } n → { 0 , 1 } n \{0,1\}^n \to \{0,1\}^n {0,1}n→{0,1}n 需要多少比特信息存儲？
      • 查表是一個直接描述輸入與輸出間映射的表格，一個條目對應(yīng)一個輸入與一個輸出；當該映射是隨機產(chǎn)生的，是一個真隨機函數(shù)；
    • 函數(shù)族Function family ${\mathsf{Func}}_n$: 包含所有函數(shù) { 0 , 1 } n → { 0 , 1 } n \{0,1\}^n \to \{0,1\}^n {0,1}n→{0,1}n. $|{\mathsf{Func}}_n|=2^{n?2^n}$
      • 一個PRF是函數(shù)族中一個子集，key確定下的PRF是函數(shù)族中一個元素，一個查表是函數(shù)族中一個元素；
    • 長度保留Length Preserving: ${?}_{key}(n)={?}_{in}(n)={?}_{out}(n)=n$；密鑰長度與函數(shù)輸入、輸出長度相同為$n$；沒有特殊說明時，只討論長度保留的函數(shù)；

14. 偽隨機函數(shù)定義

    • 直覺上，一個PRF生成的帶密鑰的函數(shù)與從函數(shù)族中隨機選擇的真隨機函數(shù)（查表）之間是不可區(qū)分的；然而，一個真隨機函數(shù)具有指數(shù)長度，無法“預(yù)先生成”，只能“on-the-fly”（邊運行、邊生成）的使用，引入一個對函數(shù)$\mathcal{O}$的確定性的預(yù)言機訪問（oracle access）$D^{\mathcal{O}}$。
    • 這里的預(yù)言機是一個抽象的函數(shù)。訪問預(yù)言機，就是給出任意輸入，得到該函數(shù)的輸出。訪問預(yù)言機的能力不包括了解正在訪問的預(yù)言機具體內(nèi)部構(gòu)造。
    • 一個帶密鑰的函數(shù)是一個偽隨機函數(shù)（PRF），對任意PPT區(qū)分器$D$，$\left|\mathrm{Pr}[D^{F_k(?)}(1^n)=1]?\mathrm{Pr}[D^{f(?)}(1^n)=1]\right|\le \mathsf{negl}(n)$，其中$f$是${\mathsf{Func}}_n$中隨機函數(shù)。
      • 這里區(qū)分器$D$是一個算法，可以訪問預(yù)言機，但并不知道預(yù)言機背后是什么。
      • 這里不可區(qū)分性關(guān)鍵是，對真隨機查表和偽隨機函數(shù)，區(qū)分器輸出相同結(jié)果概率的差異。區(qū)分器輸出1或0本身沒有，也無需，有特定語義。
    • PRF和PRG的關(guān)系在后面會學習，可以由PRG來構(gòu)造PRF。

15. PRF例題

    • 問題一個固定長度的一次一密方案是一個PRF嗎？
    • 對于一個PRF，在密鑰保密和沒有預(yù)言機訪問時，給指定輸入，能以不可忽略的概率猜測輸出相關(guān)信息嗎？
    • 如果是PRF，則給出該函數(shù)與查表的相似性；否則，給出一個區(qū)分器可以區(qū)分出該函數(shù)不是隨機的。

16. 以PRF實現(xiàn)CPA安全

    • 新隨機串 $r$，每次新生成一個隨機串；
    • $F_k(r)$: $|k|=|m|=|r|=n$. 長度保留；
    • $\mathsf{Gen}$: k ∈ { 0 , 1 } n k \in \{0,1\}^n k∈{0,1}n.
    • $\mathsf{Enc}$: $s:=F_k(r)\oplus m$, $c:=?r,s?$. 密文包括兩部分新隨機串，以及異或輸出；
    • $\mathsf{Dec}$: $m:=F_k(r)\oplus s$.
    • 定理：上述方案是CPA安全的。

17. 從PRF到CPA安全的證明

    • 思路：從PRF的區(qū)分器算法$\mathcal{D}$規(guī)約到加密方案敵手算法$\mathcal{A}$，區(qū)分器$\mathcal{D}$作為敵手$\mathcal{A}$的挑戰(zhàn)者，敵手$\mathcal{A}$實驗成功時區(qū)分器$\mathcal{D}$輸出1。分兩種情況，當輸入真隨機函數(shù)$f$時，相當于一次一密；當輸入偽隨機函數(shù)$F_k$時，為加密方案。
    • 規(guī)約：$\mathcal{D}$輸入預(yù)言機，輸出一個比特；$\mathcal{A}$的加密預(yù)言機訪問通過$\mathcal{D}$的預(yù)言機$\mathcal{O}$來提供，$c:=?r,\mathcal{O}(r)\oplus m?$；$\mathcal{D}$輸出1，當$\mathcal{A}$在實驗中成功。
      • 這里有兩個預(yù)言機：$\mathcal{D}$訪問的預(yù)言機$\mathcal{O}$，$\mathcal{A}$訪問的加密預(yù)言機${\mathsf{Enc}}_k$，后者不能直接訪問前者的預(yù)言機。

18. 從PRF到CPA安全的證明（續(xù)）

    • 考慮真隨機函數(shù)$f$的情況，分析不可區(qū)分實驗成功概率$\mathrm{Pr}[{\mathsf{PrivK}}_{\mathcal{A},\tilde{\Pi }}^{\mathsf{cpa}}(n)=1]=\mathrm{Pr}[\mathsf{Break}]$。敵手$\mathcal{A}$訪問加密預(yù)言機可以獲得多項式$q(n)$個明文與密文對的查詢結(jié)果并得到隨機串和pad { < r i , f ( r i ) > } \{ \left< r_i, f(r_i) \right> \} {?ri?,f(ri?)?}；當收到挑戰(zhàn)密文$c=?r_c,s:=f(r_c)\oplus m_b?$時，根據(jù)之前查詢結(jié)果中隨機串是否與挑戰(zhàn)密文中隨機串相同，分為兩種情況：

      • 當有相同隨機串時，根據(jù)$r$可以得到$f(r_c)$，$m_b=f(r_c)\oplus s$，但這種情況發(fā)生的概率$q(n)/2^n$是可忽略的；
      • 當沒有相同隨機串時，輸出是隨機串，相當于一次一密，成功概率=1/2；

    • $\mathrm{Pr}[D^{F_k(?)}(1^n)=1]=\mathrm{Pr}[{\mathsf{PrivK}}_{\mathcal{A},\Pi }^{\mathsf{cpa}}(n)=1]=\frac{1}{2}+\epsilon (n).$

    • $\mathrm{Pr}[D^{f(?)}(1^n)=1]=\mathrm{Pr}[{\mathsf{PrivK}}_{\mathcal{A},\tilde{\Pi }}^{\mathsf{cpa}}(n)=1]=\mathrm{Pr}[\mathsf{Break}]\le \frac{1}{2}+\frac{q(n)}{2^n}.$

    • $\mathrm{Pr}[D^{F_k(?)}(1^n)=1]?\mathrm{Pr}[D^{f(?)}(1^n)=1]\ge \epsilon (n)?\frac{q(n)}{2^n}.$ 根據(jù)偽隨機函數(shù)定義，$\epsilon (n)$ 是可忽略的.

    • 小結(jié)：通過規(guī)約將$\mathcal{A}$的不可區(qū)分實驗成功的概率與$D$的區(qū)分器實驗輸出1的概率建立等式；分析輸入真隨機函數(shù)預(yù)言機時$D$輸出1的概率（即不可區(qū)分實驗成功概率）是1/2+一個可忽略函數(shù)；根據(jù)PRF的定義，輸入偽隨機函數(shù)預(yù)言機時$D$輸出1的概率（1/2+$\epsilon (n)$）與輸入真隨機函數(shù)預(yù)言機時$D$輸出1的概率（1/2）的差異時可忽略的。

19. CPA安全例題

    • ${\mathsf{Enc}}_k(m)=PRG(k\Vert r)\oplus m$, $r$ 是新的隨機串。這是CPA安全的嗎？
    • 從PRF到CPA安全：變長消息
    • 對于任意長度消息 $m=m_1,\dots ,m_{?}$，$c:=?r_1,F_k(r_1)\oplus m_1,r_2,F_k(r_2)\oplus m_2,\dots ,r_{?},F_k(r_{?})\oplus m_{?}?$
    • 推論：如果$F$是一個 PRF，那么 $\Pi$ 對任意長度消息是 CPA 安全的。
    • 問題：這個方案有什么缺點？
    • 有效性: $|c|=2|m|$. 密文長度是明文長度的二倍，并且需要大量的真隨機串。

偽隨機排列PRP

20. 偽隨機排列（Pseudorandom Permutations）

    • 為了提高對任意長度消息加密的效率，以及更高級的加密基礎(chǔ)工具，學習偽隨機排列PRP的概念；

    • 雙射 Bijection: $F$ 是一到一的（一個輸入對應(yīng)一個唯一輸出）且滿射（覆蓋輸出集中每個元素）；

    • 排列 Permutation: 一個從一個集合到自身的雙射函數(shù)；

    • 帶密鑰的排列 Keyed permutation: $?k,F_k(?)$是排列；類似帶密鑰的函數(shù)；

    • $F$ 是一個雙射 $?F^{?1}$ 是一個雙射；函數(shù)和逆函數(shù)都是雙射；

    • 定義：一個有效的帶密鑰的排列 $F$ 是PRP，如果對于任意PPT的區(qū)分器$D$，

      $\left|\mathrm{Pr}[D^{F_k(?),F_k^{?1}(?)}(1^n)=1]?\mathrm{Pr}[D^{f(?),f^{?1}(?)}(1^n)=1]\right|\le \mathsf{negl}(n)$

    • 問題：一個PRP也是一個PRF嗎？

21. PRP例題

    • 對1比特的PRP、PRF的分析；
    • 交換引理：如果 $F$ 是一個 PRP 并且 ${?}_{in}(n)\ge n$，那么 $F$ 也是一個 PRF。
      • 一個隨機排列和一個查表是不可取分的，PRP和隨機排列不可取分，因此，PRP和查表是不可取分的。

22. 操作模式概念（Modes of Operation）

    • 操作模式是使用PRP或PRF來加密任意長度消息的方法；
    • 操作模式是從PRP或PRF來構(gòu)造一個PRG的方法；
    • 將一個消息分成若干等長的塊（分組，block），每個塊以相似方式處理；

23. Electronic Code Book (ECB) 模式

    • 在竊聽者出現(xiàn)時，是否是不可區(qū)分的？
    • $F$ 可以是任意PRF嗎？

24. 對ECB的攻擊

    • 為什么仍然可以識別企鵝？

25. Cipher Block Chaining (CBC) 模式

    • $IV$初始向量，一個新的隨機串；
    • 是CPA的嗎？可并行化嗎？F可以是任意PRF嗎？

26. Output Feedback (OFB) Mode模式

    • 是CPA安全嗎？可并行化嗎？F可以是任意PRF嗎？

27. Counter (CTR) Mode模式

    • $ctr$是一個初始向量，并且逐一增加；
    • 是CPA安全嗎？可并行化嗎？F可以是任意PRF嗎？

28. CTR模式是CPA安全
    

    • 定理：如果$F$是一個PRF，那么隨機CTR模式是CPA安全的。

    • 證明：其安全性與之前基于PRF的CPA安全證明類似，從PRF的偽隨機假設(shè)規(guī)約到CPA安全加密方案。其中，對$ctr$的安全性直覺在于，$ctr$也是在加密前不可預(yù)測的，且每個塊所用$ctr$都是不同的；

    • 當加密預(yù)言機是由真隨機查表構(gòu)成時，敵手多次訪問加密預(yù)言機得到的$ctr$序列與挑戰(zhàn)密文的$ctr$序列之間有重疊的概率$\frac{2q(n{)}^2}{2^n}$是可以忽略的；若沒有重疊，則相當于一次一密；

    • 規(guī)約與之前證明基于PRF的CPA安全加密方案一樣，證明過程也類似。

29. 初始向量不應(yīng)該可預(yù)測

    • 如果$IV$是可預(yù)測的，那么CBC/OFB/CTR模式不是CPA安全的。
    • 為什么？（作業(yè)）
    • 在SSL/TLS 1.0中的漏洞：記錄$\#i$的$IV$是上一個記錄$\#(i?1)$的密文塊。
    • OpenSSL中API：需要用戶輸入$IV$，但$IV$應(yīng)在函數(shù)內(nèi)實現(xiàn)。當$IV$不充分隨機時不安全。

30. 非確定性加密

    • 有三種通用的實現(xiàn)CPA安全的非確定性加密方法：
    • 隨機化的：$r$隨機生成，如構(gòu)造5；需要更多熵，長密文
    • 有狀態(tài)的：$r$為計數(shù)器，如CTR模式；需要通信雙方同步計數(shù)器
    • 基于Nonce的：$r$只用一次；需要保證只用一次，長密文

CCA安全加密方案

32. 選擇密文攻擊 Chosen-Ciphertext Attacks (CCA)

    • CCA不可區(qū)分實驗 ${\mathsf{PrivK}}_{\mathcal{A},\Pi }^{\mathsf{cca}}(n)$:

      1. 挑戰(zhàn)者生成密鑰 $k\leftarrow \mathsf{Gen}(1^n)$；（為了下一步的預(yù)言機）
      2. $\mathcal{A}$ 被給予輸入 $1^n$ 和對加密函數(shù) ${\mathsf{Enc}}_k(?)$和解密函數(shù)${\mathsf{Dec}}_k(?)$的預(yù)言機訪問（oracle access） ${\mathcal{A}}^{{\mathsf{Enc}}_k(?)}$ 和 ${\mathcal{A}}^{{\mathsf{Dec}}_k(?)}$，輸出相同長度 $m_0,m_1$ ；
      3. 挑戰(zhàn)者生成隨機比特 b ← { 0 , 1 } b \gets \{0,1\} b←{0,1}，將挑戰(zhàn)密文 $c\leftarrow {\mathsf{Enc}}_k(m_b)$ 發(fā)送給 $\mathcal{A}$；
      4. $\mathcal{A}$ 繼續(xù)對除了挑戰(zhàn)密文$c$之外的預(yù)言機的訪問，輸出$b^{\prime }$；如果$b^{\prime }=b$，則$\mathcal{A}$成功${\mathsf{PrivK}}_{\mathcal{A},\Pi }^{\mathsf{cca}}=1$，否則 0。

      定義：一個加密方案是CCA安全的，如果實驗成功的概率與1/2的差異是可忽略的。

33. 理解CCA安全

    • 在現(xiàn)實世界中，敵手可以通過影響被解密的內(nèi)容來實施CCA。如果通信沒有認證，那么敵手可以以通信參與方的身份來發(fā)送特定密文。下一頁有具體真實案例。

    • CCA安全性意味著“non-malleability”（不可鍛造性，即改變但不毀壞），不能修改密文來獲得新的有效密文。

    • 之前的方案中沒有CCA安全，因為都不是不可鍛造。

    • 對基于PRF的CPA安全加密方案的CCA攻擊：

      • $\mathcal{A}$ 獲得挑戰(zhàn)密文 $c=?r,F_k(r)\oplus m_b?$，并且查詢與$c$只相差了一個翻轉(zhuǎn)的比特的密文$c^{\prime }$，那么

        $m^{\prime }=c^{\prime }\oplus F_k(r)$ 應(yīng)該與 $m_b$ 除了什么之外都相同？（見下方的補充）

    • 問題：上述操作模式也不是CCA安全的（作業(yè)）

    • 由此，可以總結(jié)出CCA下敵手的常用策略：

      • 修改挑戰(zhàn)密文$c$為$c^{\prime }$，并查詢解密預(yù)言機得到$m^{\prime }$
      • 根據(jù)關(guān)系，由$m^{\prime }$來猜測被加密明文$m_b$

補充

在這個情況下，$\mathcal{A}$ 獲得了挑戰(zhàn)密文 $c=?r,F_k(r)\oplus m_b?$ 并查詢了一個只在一個比特上與 $c$ 不同的密文 $c^{\prime }$。我們來分析一下 $m^{\prime }=c^{\prime }\oplus F_k(r)$ 與 $m_b$ 的關(guān)系。

首先，我們明確 $c$ 的構(gòu)成：

• $c$ 包含兩個部分：一個隨機數(shù) $r$ 和使用密鑰 $k$ 的函數(shù) $F_k(r)$ 與明文 $m_b$ 的異或結(jié)果。
• 因此，$c=?r,F_k(r)\oplus m_b?$。

現(xiàn)在，如果 $\mathcal{A}$ 查詢了一個與 $c$ 只在一個比特上不同的密文 $c^{\prime }$，那么 $c^{\prime }$ 也可以寫成兩部分，但其中一部分與 $c$ 有一個比特的差異。這個差異可以在 $r$ 部分，也可以在 $F_k(r)\oplus m_b$ 部分。

當 $\mathcal{A}$ 計算 $m^{\prime }=c^{\prime }\oplus F_k(r)$ 時，他們實際上是在解開 $F_k(r)\oplus m_b$ 的異或操作。這是因為異或操作是可逆的，且當兩次使用相同的值時會取消彼此的效果（即 $A\oplus B\oplus B=A$）。

因此，如果 $c^{\prime }$ 的變化發(fā)生在 $F_k(r)$ 部分，則 $m^{\prime }$ 將與 $m_b$ 完全相同，因為 $F_k(r)$ 部分的變化被異或操作取消了。但如果變化發(fā)生在 $r$ 部分，則這個變化不會影響到 $F_k(r)\oplus m_b$ 部分，因此 $m^{\prime }$ 將與 $m_b$ 在一個比特上不同。

綜上所述，$m^{\prime }$ 與 $m_b$ 將在以下方面相同：

• 如果變化發(fā)生在 $F_k(r)$ 部分，那么 $m^{\prime }$ 與 $m_b$ 完全相同。
• 如果變化發(fā)生在 $r$ 部分，那么 $m^{\prime }$ 與 $m_b$ 除了那個翻轉(zhuǎn)的比特之外都相同。

填充預(yù)言機Padding-Oracle攻擊真實案例

34. Padding-Oracle（填充預(yù)言機）攻擊真實案例

    • CAPTCHA服務(wù)商為Web網(wǎng)站提供驗證用戶是否為人類的服務(wù)。為此，一個CAPTCHA服務(wù)器與Web服務(wù)器間事先共享一個密鑰$k$，服務(wù)工作原理如下：
      1. 當Web服務(wù)器驗證用戶是否為人類時，生成一個消息$w$并以$k$加密，向用戶發(fā)送一個密文$En{c}_k(w)$；
      2. 用戶將密文$En{c}_k(w)$轉(zhuǎn)發(fā)給CAPTCHA服務(wù)器；（可實施填充預(yù)言機攻擊）
      3. CAPTCHA服務(wù)器用密鑰$k$將密文解密，根據(jù)解密結(jié)果返回給用戶信息：一個由$w$生成的圖像，或者壞填充錯誤；
      4. 用戶根據(jù)圖像獲得 $w$ 并將 $w$ 發(fā)送給Web服務(wù)器。
    • 在第2步，當惡意用戶可以利用CAPTCHA服務(wù)器會返回給用戶壞填充錯誤這一漏洞，來實施填充錯誤攻擊。

35. Padding-Oracle（填充預(yù)言機）攻擊

    • 在PKCS #5 padding（填充）標準中，為了將一個消息的長度“填充”到塊長度的整數(shù)倍，在最后一個塊中填充$b$個字節(jié)的$b$；必要時，添加一個啞塊（dummy block，不包含消息的一個填充塊）。存在一種攻擊手段：當填充錯誤時，解密服務(wù)器返回一個“壞填充錯誤”，這相當于提供了一個解密預(yù)言機，最終可以獲得整個明文；
    • 具體攻擊原理：
      • 更改密文（包含$IV$部分）并發(fā)送給解密服務(wù)器；
      • 一旦觸發(fā)了“壞填充錯誤”，則說明對密文的更改導(dǎo)致了填充部分內(nèi)容的更改；否則，對密文的更改導(dǎo)致了原明文部分的更改；
      • 通過仔細修改密文來控制填充部分，從而獲得消息長度和內(nèi)容。

36. 填充預(yù)言機攻擊：獲得消息長度

    • 攻擊的第一步判斷消息是否為空：在單個塊的CBC中，通過更改$IV$的首個字節(jié)，攻擊者能夠獲知是否$m$是否為空。因為如果$m$是空的話，更改$IV$首個字節(jié)將更改解密出的填充內(nèi)容，解密服務(wù)器就會返回壞填充錯誤（1比特信息），具體分析如下：
      • 如果$m$是空的，那么明文會添加一個啞塊 { b } b \{b\}^b {b}b；
      • PRP的輸入為 I V ⊕ { b } b IV\oplus \{b\}^b IV⊕{b}b；設(shè)$IV$的首個字節(jié)為$x$，則PRP的輸入為 ( x ⊕ b ) ∥ ( { ? } b ? 1 ⊕ { b } b ? 1 ) (x \oplus b) \| (\{\cdot\}^{b-1} \oplus \{b\}^{b-1}) (x⊕b)∥({?}b?1⊕{b}b?1)；
      • 將$IV$的首個字節(jié)從$x$改成$y$變?yōu)? y ∥ ( { ? } b ? 1 ) y \| (\{\cdot\}^{b-1}) y∥({?}b?1)，不改變$c_1$解密得到的PRP的輸入不會變，而解密出的明文會改變?yōu)? ( x ⊕ y ⊕ b ) ∥ { b } b ? 1 (x \oplus y \oplus b) \| \{b\}^{b-1} (x⊕y⊕b)∥{b}b?1；
      • 上述明文首個字節(jié)一定不是$b$，這是填充格式錯誤，會觸發(fā)服務(wù)器返回錯誤；
      • 如果上面的嘗試沒有觸發(fā)錯誤，那么說明消息非空；下一步，發(fā)現(xiàn)消息長度是否為1字節(jié)，方法與上一步一樣，區(qū)別在于只改變$IV$的第2個字節(jié)；如此繼續(xù)，獲得消息的長度；（作業(yè)）

37. 填充預(yù)言機攻擊：獲得消息內(nèi)容

    • 一旦獲得消息的長度，也就知道了填充的長度$b$，采用下面的方法來獲得消息的最后一個字節(jié)內(nèi)容，進而獲得整個消息；
    • 更改密文中倒數(shù)第二塊，來獲得消息的最后一個字節(jié)$s$；
    • 明文的最后一個塊 m l a s t = ? s ∥ { b } b m_{last} = \cdots s \| \{b\}^ mlast?=?s∥{b}b，密文的倒數(shù)第二個塊 c l a s t ? 1 = ? t ∥ { ? } b c_{last-1} = \cdots t \| \{\cdot \}^ clast?1?=?t∥{?}b；
    • 最后一塊的PRP輸入為 c l a s t ? 1 ⊕ m l a s t = ? ( s ⊕ t ) ∥ ( { b } b ⊕ { ? } b ) c_{last-1} \oplus m_{last} = \cdots (s \oplus t) \| (\{b\}^b \oplus \{\cdot \}^) clast?1?⊕mlast?=?(s⊕t)∥({b}b⊕{?}b)；
    • 敵手更改 $c_{last?1}$ 為 c l a s t ? 1 ′ = ? u ∥ ( { ? } b ⊕ { b } b ⊕ { b + 1 } b ) c_{last-1}' = \cdots u \| (\{\cdot \}^ \oplus \{b\}^ \oplus \{b+1\}^) clast?1′?=?u∥({?}b⊕{b}b⊕{b+1}b)；其中，$u$是敵手猜測的某個字節(jié)；
    • 解密獲得最后一塊明文 m l a s t ′ = c l a s t ? 1 ⊕ m l a s t ⊕ c l a s t ? 1 ′ = ? ( s ⊕ t ⊕ u ) ∥ { b + 1 } b m'_{last} = c_{last-1} \oplus m_{last} \oplus c_{last-1}' = \cdots (s \oplus t \oplus u)\| \{ b+1 \}^b mlast′?=clast?1?⊕mlast?⊕clast?1′?=?(s⊕t⊕u)∥{b+1}b；
    • 如果沒有返回壞填充錯誤，那么意味著填充了$b+1$個字節(jié)的$b+1$，所以 $s\oplus t\oplus u=(b+1)$ ，而 $s=t\oplus u\oplus (b+1)$ 。

38. 總結(jié)

    • 略