網(wǎng)站開發(fā)與服務(wù)合同范本建立網(wǎng)站平臺
【現(xiàn)代密碼學】筆記3.4-3.7--構(gòu)造安全加密方案、CPA安全、CCA安全 《introduction to modern cryphtography》
- 寫在最前面
- 私鑰加密與偽隨機性 第二部分
- 流加密與CPA
- 多重加密
- CPA安全加密方案
- CPA安全實驗、預(yù)言機訪問(oracle access)
- 操作模式
- 偽隨機函數(shù)PRF
- 偽隨機排列PRP
- CCA安全加密方案
- 補充
- 填充預(yù)言機Padding-Oracle攻擊真實案例
寫在最前面
主要在 哈工大密碼學課程 張宇老師課件 的基礎(chǔ)上學習記錄筆記。
內(nèi)容補充:駱婷老師的PPT
《introduction to modern cryphtography》–Jonathan Katz, Yehuda Lindell(現(xiàn)代密碼學——原理與協(xié)議)中相關(guān)章節(jié)
密碼學復(fù)習筆記 這個博主好有意思
初步筆記,如有錯誤請指正
快速補充一些密碼相關(guān)的背景知識
私鑰加密與偽隨機性 第二部分
-
本節(jié)課學習另外兩種私鑰加密安全理論:選擇明文攻擊(CPA)下不可區(qū)分性、選擇密文攻擊(CCA)下不可區(qū)分性以及相關(guān)的密碼學原語、假設(shè)、構(gòu)造和證明。這些攻擊更好的刻畫了現(xiàn)實世界中敵手的能力,相應(yīng)的密碼學方案也是目前真正在實際使用的。
-
目錄:流加密與CPA,CPA安全加密方案,操作模式,CCA安全加密方案
流加密與CPA
-
流加密方案(Stream Cipher)
- 首先介紹當有多個消息需要被傳遞時,如何利用之前學習的基于PRG的加密方案來保護消息。
- 思路:受一次一密方案的啟發(fā),通過將變長消息與密鑰的異或來加密
- 流加密方案:通過將多個消息“拼成”一個消息,與偽隨機的比特流(密鑰流)異或來加密
- 密鑰流:由一個變長的偽隨機生成器產(chǎn)生
- 優(yōu)點:邏輯簡單,比分組密碼更快
- 缺點:難以做到安全
-
采用流加密方案的安全多重加密
- 同步模式:用一個流中不同部分分別加密各個消息;
- 異步模式:以密鑰和初始向量一起作為輸入來產(chǎn)生流,每個明文的加密采用相同的密鑰和不同的初始向量
- 初始向量(Initial Vector), I V IV IV是隨機選取的并且是公開的;其生成是隨機的并不受控制,但生成后并不保密;密鑰的生成是隨機的并不受控制,但生成后也要保密。
- 兩種模式差異:
- 同步模式適合持續(xù)通信場景,例如語音;異步模式適合間斷通信場景,例如即時消息。
-
流密碼的安全性
- 現(xiàn)狀:沒有標準化和流行的方案,安全性仍有疑問,例如在802.11中WEP協(xié)議的RC4,線性反饋移位寄存器(Linear Feedback Shift Registers);
- 警告:不要使用任何流加密方案,如果一定需要的話,采用由分組加密方案構(gòu)造的。
- eStream項目致力于設(shè)計安全的流密碼
-
相關(guān)密鑰:真實世界例子
- 用于多重加密的密鑰(初始向量和密鑰對)必須是獨立的。否則,前面的攻擊就會生效;
- 對于802.11b WEP的若干攻擊:
- WEP為異步模式, E n c ( m i ) : = < I V i , G ( I V i ∥ k ) ⊕ m i > \mathsf{Enc}(m_i) := \left< IV_i, G(IV_i\|k) \oplus m_i\right> Enc(mi?):=?IVi?,G(IVi?∥k)⊕mi??
- I V IV IV長度為24比特,在 2 24 ≈ 2^{24} \approx 224≈ 16M 幀后 I V IV IV會產(chǎn)生重復(fù);
- 在一些WiFi網(wǎng)卡上,在電源重啟后 I V IV IV重置為0;
- I V i = I V i ? 1 + 1 IV_i = IV_{i-1} + 1 IVi?=IVi?1?+1. 對于RC4,在40,000幀后可以恢復(fù) k k k ;
多重加密
-
多重加密(Multiple Encryptions)
- 在一次一密中,一個密鑰不可以用于對多個消息的加密;否則,就是不安全的。如果敵手能夠獲得用同一個密鑰加密后的多個密文,則之前的方案都是不安全的;為此,我們需要新的加密方案來防御這樣的攻擊。
- 多個明文的加密實驗 P r i v K A , Π m u l t ( n ) \mathsf{PrivK}^{\mathsf{mult}}_{\mathcal{A},\Pi}(n) PrivKA,Πmult?(n),當一次加密多個明文時,竊聽者敵手能夠區(qū)分出兩組明文嗎?
- 一個敵手 A \mathcal{A} A與一個挑戰(zhàn)者 C \mathcal{C} C進行3輪交互:
- A \mathcal{A} A選擇兩個長度相同、內(nèi)容不同明文向量 M ? 0 = ( m 0 1 , … , m 0 t ) \vec{M}_0=(m_0^1,\dots,m_0^t) M0?=(m01?,…,m0t?), M ? 1 = ( m 1 1 , … , m 1 t ) \vec{M}_1=(m_1^1,\dots,m_1^t) M1?=(m11?,…,m1t?),其中兩個向量中同一位置的明文長度相同 ? i , ∣ m 0 i ∣ = ∣ m 1 i ∣ \forall i, |m_0^i| = |m_1^i| ?i,∣m0i?∣=∣m1i?∣,發(fā)送給 C \mathcal{C} C;
- C \mathcal{C} C根據(jù)密鑰生成算法生成一個新密鑰 k ← G e n ( 1 n ) k \gets \mathsf{Gen}(1^n) k←Gen(1n),一個隨機比特 b ← { 0 , 1 } b \gets \{0,1\} b←{0,1}。對向量 M ? b \vec{M}_b Mb?中每個明文加密 c i ← E n c k ( m b i ) c^i \gets \mathsf{Enc}_k(m_b^i) ci←Enck?(mbi?) 得到一個密文向量 C ? = ( c 1 , … , c t ) \vec{C}=(c^1,\dots,c^t) C=(c1,…,ct) ,并發(fā)送給 A \mathcal{A} A;
- A \mathcal{A} A輸出對所加密明文向量的猜測 b ′ b' b′,若 b = b ′ b=b' b=b′,則 A \mathcal{A} A成功;否則,失敗;
- 這與之前的單個消息不可區(qū)分實驗類似的,區(qū)別在于用同一個密鑰加密的多個消息。敵手可以獲得多個明文的密文,比單個明文不可區(qū)分實驗中的敵手有更強的能力。
-
多重加密安全定義
-
Π \Pi Π 是竊聽者出現(xiàn)時不可區(qū)分的多重加密方案,如果任意PPT的敵手 A \mathcal{A} A, 存在可忽略的函數(shù) n e g l \mathsf{negl} negl 使得
Pr ? [ P r i v K A , Π m u l t ( n ) = 1 ] ≤ 1 2 + n e g l ( n ) . \Pr\left[\mathsf{PrivK}^{\mathsf{mult}}_{\mathcal{A},\Pi}(n)=1\right] \le \frac{1}{2} + \mathsf{negl}(n). Pr[PrivKA,Πmult?(n)=1]≤21?+negl(n).
-
根據(jù)這個定義,來分析迄今學習的密碼學方案是否是多重加密不可區(qū)分的?
-
-
攻擊確定性加密方案
- 問題:如果一個加密方案中加密算法是確定性的,即同一個明文會被同一個密鑰加密成同一個密文,那么該加密方案是
多重加密安全
的嗎? - 攻擊:對于確定性加密方案,敵手可以構(gòu)造 m 0 1 = m 0 2 m_0^1 = m_0^2 m01?=m02? 并且 m 1 1 ≠ m 1 2 m_1^1 \neq m_1^2 m11?=m12?,然后當 c 1 = c 2 c^1 = c^2 c1=c2,輸出 b ′ = 0 b'=0 b′=0,否則 b ′ = 1 b'=1 b′=1。
- 因此,確定性加密方案不是多重加密安全的,我們需要新的密碼學原語來防御多重加密攻擊。接下來,我們介紹一種更強的攻擊,其涵蓋了多重加密攻擊。只要防御了這個新定義的攻擊,也就同時防御了多重加密攻擊。
- 問題:如果一個加密方案中加密算法是確定性的,即同一個明文會被同一個密鑰加密成同一個密文,那么該加密方案是
CPA安全加密方案
-
選擇明文攻擊(Chosen-Plaintext Attacks (CPA))(思考)
-
敵手具有獲得其所選擇明文對應(yīng)的密文的能力。
-
第二次世界大戰(zhàn)中的例子:美國海軍密碼分析學家相信密文“AF”表示日語中的“中途島”;但美國將軍不認為中途島會遭到攻擊(?這里沒看懂);美國海軍密碼分析學家發(fā)送了一個明文,中途島淡水供給不足;日本軍隊截獲的明文,并發(fā)送了一段密文,“AF”淡水不足;美國軍隊派出三艘航空母艦并且取勝。
-
這里例子里,美國海軍密碼分析學家選擇了明文并得到了密文。
-
CPA安全實驗、預(yù)言機訪問(oracle access)
-
CPA安全實驗
- CPA不可區(qū)分實驗 P r i v K A , Π c p a ( n ) \mathsf{PrivK}^{\mathsf{cpa}}_{\mathcal{A},\Pi}(n) PrivKA,Πcpa?(n):
- 挑戰(zhàn)者生成密鑰 k ← G e n ( 1 n ) k \gets \mathsf{Gen}(1^n) k←Gen(1n);(這里與竊聽者不可區(qū)分實驗相比,密鑰的生成提前了,這是為了下一步提供加密預(yù)言機)
- A \mathcal{A} A 被給予輸入 1 n 1^n 1n 和對加密函數(shù) E n c k ( ? ) \mathsf{Enc}_k(\cdot) Enck?(?)的預(yù)言機訪問(oracle access) A E n c k ( ? ) \mathcal{A}^{\mathsf{Enc}_k(\cdot)} AEnck?(?) ,輸出相同長度 m 0 , m 1 m_0, m_1 m0?,m1? ;
- 挑戰(zhàn)者生成隨機比特 b ← { 0 , 1 } b \gets \{0,1\} b←{0,1},將挑戰(zhàn)密文 c ← E n c k ( m b ) c \gets \mathsf{Enc}_k(m_b) c←Enck?(mb?) 發(fā)送給 A \mathcal{A} A;
- A \mathcal{A} A 繼續(xù)對 E n c k ( ? ) \mathsf{Enc}_k(\cdot) Enck?(?)的預(yù)言機的訪問,輸出 b ′ b' b′;如果 b ′ = b b' = b b′=b,則 A \mathcal{A} A成功 P r i v K A , Π c p a = 1 \mathsf{PrivK}^{\mathsf{cpa}}_{\mathcal{A},\Pi}=1 PrivKA,Π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)性地”再次獲得密文。
- CPA不可區(qū)分實驗 P r i v K A , Π c p a ( n ) \mathsf{PrivK}^{\mathsf{cpa}}_{\mathcal{A},\Pi}(n) PrivKA,Πcpa?(n):
-
CPA安全
-
Π \Pi Π 是CPA不可區(qū)分加密方案 (CPA安全的),如果任意概率多項式時間算法 A \mathcal{A} A,存在可忽略的函數(shù) n e g l \mathsf{negl} negl使得,
Pr ? [ P r i v K A , Π c p a ( n ) = 1 ] ≤ 1 2 + n e g l ( n ) \Pr\left[\mathsf{PrivK}^{\mathsf{cpa}}_{\mathcal{A},\Pi}(n)=1\right] \le \frac{1}{2} + \mathsf{negl}(n) Pr[PrivKA,Πcpa?(n)=1]≤21?+negl(n)
-
定理:CPA安全也是多重加密安全的。證明略。直覺上,CPA敵手比多重加密敵手更強大。
-
之前的方案也難以實現(xiàn)CPA安全;
-
多重加密安全意味著CPA安全?(作業(yè))顯然是否定的。那么,思考兩種安全定義的區(qū)別成為解題的關(guān)鍵。
-
操作模式
偽隨機函數(shù)PRF
-
偽隨機函數(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 ) = def F ( k , x ) F_k(x) \overset{\text{def}}{=} F(k,x) Fk?(x)=defF(k,x)
- 兩個輸入到一個輸出,看上去像,但不是加密函數(shù);輸入key,得到一個一輸入到一輸出的函數(shù);
- 查表Look-up table f f 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 F u n c n \mathsf{Func}_n Funcn?: 包含所有函數(shù) { 0 , 1 } n → { 0 , 1 } n \{0,1\}^n \to \{0,1\}^n {0,1}n→{0,1}n. ∣ F u n c n ∣ = 2 n ? 2 n |\mathsf{Func}_n| = 2^{n\cdot2^n} ∣Funcn?∣=2n?2n
- 一個PRF是函數(shù)族中一個子集,key確定下的PRF是函數(shù)族中一個元素,一個查表是函數(shù)族中一個元素;
- 長度保留Length Preserving: ? k e y ( n ) = ? i n ( n ) = ? o u t ( n ) = n \ell_{key}(n) = \ell_{in}(n) = \ell_{out}(n) = n ?key?(n)=?in?(n)=?out?(n)=n;密鑰長度與函數(shù)輸入、輸出長度相同為 n n n;沒有特殊說明時,只討論長度保留的函數(shù);
-
偽隨機函數(shù)定義
- 直覺上,一個PRF生成的帶密鑰的函數(shù)與從函數(shù)族中隨機選擇的真隨機函數(shù)(查表)之間是不可區(qū)分的;然而,一個真隨機函數(shù)具有指數(shù)長度,無法“預(yù)先生成”,只能“on-the-fly”(邊運行、邊生成)的使用,引入一個對函數(shù) O \mathcal{O} O的確定性的預(yù)言機訪問(oracle access) D O D^\mathcal{O} DO。
- 這里的預(yù)言機是一個抽象的函數(shù)。訪問預(yù)言機,就是給出任意輸入,得到該函數(shù)的輸出。訪問預(yù)言機的能力不包括了解正在訪問的預(yù)言機具體內(nèi)部構(gòu)造。
- 一個帶密鑰的函數(shù)是一個偽隨機函數(shù)(PRF),對任意PPT區(qū)分器 D D D, ∣ Pr ? [ D F k ( ? ) ( 1 n ) = 1 ] ? Pr ? [ D f ( ? ) ( 1 n ) = 1 ] ∣ ≤ n e g l ( n ) \left|\Pr[D^{F_k(\cdot)}(1^n)=1] - \Pr[D^{f(\cdot)}(1^n)=1]\right| \le \mathsf{negl}(n) ?Pr[DFk?(?)(1n)=1]?Pr[Df(?)(1n)=1] ?≤negl(n),其中 f f f是 F u n c n \mathsf{Func}_n Funcn?中隨機函數(shù)。
- 這里區(qū)分器 D D D是一個算法,可以訪問預(yù)言機,但并不知道預(yù)言機背后是什么。
- 這里不可區(qū)分性關(guān)鍵是,對真隨機查表和偽隨機函數(shù),區(qū)分器輸出相同結(jié)果概率的差異。區(qū)分器輸出1或0本身沒有,也無需,有特定語義。
- PRF和PRG的關(guān)系在后面會學習,可以由PRG來構(gòu)造PRF。
-
PRF例題
- 問題一個固定長度的一次一密方案是一個PRF嗎?
- 對于一個PRF,在密鑰保密和沒有預(yù)言機訪問時,給指定輸入,能以不可忽略的概率猜測輸出相關(guān)信息嗎?
- 如果是PRF,則給出該函數(shù)與查表的相似性;否則,給出一個區(qū)分器可以區(qū)分出該函數(shù)不是隨機的。
-
以PRF實現(xiàn)CPA安全
- 新隨機串 r r r,每次新生成一個隨機串;
- F k ( r ) F_k(r) Fk?(r): ∣ k ∣ = ∣ m ∣ = ∣ r ∣ = n |k| = |m| = |r| = n ∣k∣=∣m∣=∣r∣=n. 長度保留;
- G e n \mathsf{Gen} Gen: k ∈ { 0 , 1 } n k \in \{0,1\}^n k∈{0,1}n.
- E n c \mathsf{Enc} Enc: s : = F k ( r ) ⊕ m s := F_k(r)\oplus m s:=Fk?(r)⊕m, c : = < r , s > c := \left<r, s\right> c:=?r,s?. 密文包括兩部分新隨機串,以及異或輸出;
- D e c \mathsf{Dec} Dec: m : = F k ( r ) ⊕ s m := F_k(r)\oplus s m:=Fk?(r)⊕s.
- 定理:上述方案是CPA安全的。
-
從PRF到CPA安全的證明
- 思路:從PRF的區(qū)分器算法 D \mathcal{D} D規(guī)約到加密方案敵手算法 A \mathcal{A} A,區(qū)分器 D \mathcal{D} D作為敵手 A \mathcal{A} A的挑戰(zhàn)者,敵手 A \mathcal{A} A實驗成功時區(qū)分器 D \mathcal{D} D輸出1。分兩種情況,當輸入真隨機函數(shù) f f f時,相當于一次一密;當輸入偽隨機函數(shù) F k F_k Fk?時,為加密方案。
- 規(guī)約: D \mathcal{D} D輸入預(yù)言機,輸出一個比特; A \mathcal{A} A的加密預(yù)言機訪問通過 D \mathcal{D} D的預(yù)言機 O \mathcal{O} O來提供, c : = < r , O ( r ) ⊕ m > c := \left<r, \mathcal{O}(r) \oplus m \right> c:=?r,O(r)⊕m?; D \mathcal{D} D輸出1,當 A \mathcal{A} A在實驗中成功。
- 這里有兩個預(yù)言機: D \mathcal{D} D訪問的預(yù)言機 O \mathcal{O} O, A \mathcal{A} A訪問的加密預(yù)言機 E n c k \mathsf{Enc}_k Enck?,后者不能直接訪問前者的預(yù)言機。
-
從PRF到CPA安全的證明(續(xù))
-
考慮真隨機函數(shù) f f f的情況,分析不可區(qū)分實驗成功概率 Pr ? [ P r i v K A , Π ~ c p a ( n ) = 1 ] = Pr ? [ B r e a k ] \Pr[\mathsf{PrivK}_{\mathcal{A},\tilde{\Pi}}^{\mathsf{cpa}}(n) = 1] = \Pr[\mathsf{Break}] Pr[PrivKA,Π~cpa?(n)=1]=Pr[Break]。敵手 A \mathcal{A} A訪問加密預(yù)言機可以獲得多項式 q ( n ) q(n) 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 ) ⊕ m b > c=\left<r_c, s:=f(r_c)\oplus m_b\right> c=?rc?,s:=f(rc?)⊕mb??時,根據(jù)之前查詢結(jié)果中隨機串是否與挑戰(zhàn)密文中隨機串相同,分為兩種情況:
- 當有相同隨機串時,根據(jù) r r r可以得到 f ( r c ) f(r_c) f(rc?), m b = f ( r c ) ⊕ s m_b=f(r_c)\oplus s mb?=f(rc?)⊕s,但這種情況發(fā)生的概率 q ( n ) / 2 n q(n)/2^n q(n)/2n是可忽略的;
- 當沒有相同隨機串時,輸出是隨機串,相當于一次一密,成功概率=1/2;
-
Pr ? [ D F k ( ? ) ( 1 n ) = 1 ] = Pr ? [ P r i v K A , Π c p a ( n ) = 1 ] = 1 2 + ε ( n ) . \Pr[D^{F_k(\cdot)}(1^n)=1] = \Pr[\mathsf{PrivK}_{\mathcal{A},\Pi}^{\mathsf{cpa}}(n) = 1] = \frac{1}{2} + \varepsilon(n). Pr[DFk?(?)(1n)=1]=Pr[PrivKA,Πcpa?(n)=1]=21?+ε(n).
-
Pr ? [ D f ( ? ) ( 1 n ) = 1 ] = Pr ? [ P r i v K A , Π ~ c p a ( n ) = 1 ] = Pr ? [ B r e a k ] ≤ 1 2 + q ( n ) 2 n . \Pr[D^{f(\cdot)}(1^n)=1] = \Pr[\mathsf{PrivK}_{\mathcal{A},\tilde{\Pi}}^{\mathsf{cpa}}(n) = 1] = \Pr[\mathsf{Break}] \le \frac{1}{2} + \frac{q(n)}{2^n}. Pr[Df(?)(1n)=1]=Pr[PrivKA,Π~cpa?(n)=1]=Pr[Break]≤21?+2nq(n)?.
-
Pr ? [ D F k ( ? ) ( 1 n ) = 1 ] ? Pr ? [ D f ( ? ) ( 1 n ) = 1 ] ≥ ε ( n ) ? q ( n ) 2 n . \Pr[D^{F_k(\cdot)}(1^n)=1] - \Pr[D^{f(\cdot)}(1^n)=1] \ge \varepsilon(n) - \frac{q(n)}{2^n}. Pr[DFk?(?)(1n)=1]?Pr[Df(?)(1n)=1]≥ε(n)?2nq(n)?. 根據(jù)偽隨機函數(shù)定義, ε ( n ) \varepsilon(n) ε(n) 是可忽略的.
-
小結(jié):通過規(guī)約將 A \mathcal{A} A的不可區(qū)分實驗成功的概率與 D D D的區(qū)分器實驗輸出1的概率建立等式;分析輸入真隨機函數(shù)預(yù)言機時 D D D輸出1的概率(即不可區(qū)分實驗成功概率)是1/2+一個可忽略函數(shù);根據(jù)PRF的定義,輸入偽隨機函數(shù)預(yù)言機時 D D D輸出1的概率(1/2+ ε ( n ) \varepsilon(n) ε(n))與輸入真隨機函數(shù)預(yù)言機時 D D D輸出1的概率(1/2)的差異時可忽略的。
-
-
CPA安全例題
- E n c k ( m ) = P R G ( k ∥ r ) ⊕ m \mathsf{Enc}_k(m) = PRG(k\|r) \oplus m Enck?(m)=PRG(k∥r)⊕m, r r r 是新的隨機串。這是CPA安全的嗎?
- 從PRF到CPA安全:變長消息
- 對于任意長度消息 m = m 1 , … , m ? m = m_1, \dots , m_{\ell} m=m1?,…,m??, c : = < r 1 , F k ( r 1 ) ⊕ m 1 , r 2 , F k ( r 2 ) ⊕ m 2 , … , r ? , F k ( r ? ) ⊕ m ? > c := \left< r_1, F_k(r_1) \oplus m_1, r_2, F_k(r_2) \oplus m_2, \dots, r_\ell, F_k(r_\ell) \oplus m_\ell\right> c:=?r1?,Fk?(r1?)⊕m1?,r2?,Fk?(r2?)⊕m2?,…,r??,Fk?(r??)⊕m???
- 推論:如果 F F F是一個 PRF,那么 Π \Pi Π 對任意長度消息是 CPA 安全的。
- 問題:這個方案有什么缺點?
- 有效性: ∣ c ∣ = 2 ∣ m ∣ |c| = 2|m| ∣c∣=2∣m∣. 密文長度是明文長度的二倍,并且需要大量的真隨機串。
偽隨機排列PRP
-
偽隨機排列(Pseudorandom Permutations)
-
為了提高對任意長度消息加密的效率,以及更高級的加密基礎(chǔ)工具,學習偽隨機排列PRP的概念;
-
雙射 Bijection: F F F 是一到一的(一個輸入對應(yīng)一個唯一輸出)且滿射(覆蓋輸出集中每個元素);
-
排列 Permutation: 一個從一個集合到自身的雙射函數(shù);
-
帶密鑰的排列 Keyed permutation: ? k , F k ( ? ) \forall k, F_k(\cdot) ?k,Fk?(?)是排列;類似帶密鑰的函數(shù);
-
F F F 是一個雙射 ? F ? 1 \iff F^{-1} ?F?1 是一個雙射;函數(shù)和逆函數(shù)都是雙射;
-
定義:一個有效的帶密鑰的排列 F F F 是PRP,如果對于任意PPT的區(qū)分器 D D D,
∣ Pr ? [ D F k ( ? ) , F k ? 1 ( ? ) ( 1 n ) = 1 ] ? Pr ? [ D f ( ? ) , f ? 1 ( ? ) ( 1 n ) = 1 ] ∣ ≤ n e g l ( n ) \left|\Pr[D^{F_k(\cdot),F_k^{-1}(\cdot)}(1^n)=1] - \Pr[D^{f(\cdot),f^{-1}(\cdot)}(1^n)=1]\right| \le \mathsf{negl}(n) ?Pr[DFk?(?),Fk?1?(?)(1n)=1]?Pr[Df(?),f?1(?)(1n)=1] ?≤negl(n)
-
問題:一個PRP也是一個PRF嗎?
-
-
PRP例題
- 對1比特的PRP、PRF的分析;
- 交換引理:如果 F F F 是一個 PRP 并且 ? i n ( n ) ≥ n \ell_{in} (n) \ge n ?in?(n)≥n,那么 F F F 也是一個 PRF。
- 一個隨機排列和一個查表是不可取分的,PRP和隨機排列不可取分,因此,PRP和查表是不可取分的。
-
操作模式概念(Modes of Operation)
- 操作模式是使用PRP或PRF來加密任意長度消息的方法;
- 操作模式是從PRP或PRF來構(gòu)造一個PRG的方法;
- 將一個消息分成若干等長的塊(分組,block),每個塊以相似方式處理;
-
Electronic Code Book (ECB) 模式
- 在竊聽者出現(xiàn)時,是否是不可區(qū)分的?
- F F F 可以是任意PRF嗎?
-
對ECB的攻擊
- 為什么仍然可以識別企鵝?
-
Cipher Block Chaining (CBC) 模式
- I V IV IV初始向量,一個新的隨機串;
- 是CPA的嗎?可并行化嗎?F可以是任意PRF嗎?
-
Output Feedback (OFB) Mode模式
- 是CPA安全嗎?可并行化嗎?F可以是任意PRF嗎?
-
Counter (CTR) Mode模式
- c t r ctr ctr是一個初始向量,并且逐一增加;
- 是CPA安全嗎?可并行化嗎?F可以是任意PRF嗎?
-
CTR模式是CPA安全
-
定理:如果 F F F是一個PRF,那么隨機CTR模式是CPA安全的。
-
證明:其安全性與之前基于PRF的CPA安全證明類似,從PRF的偽隨機假設(shè)規(guī)約到CPA安全加密方案。其中,對 c t r ctr ctr的安全性直覺在于, c t r ctr ctr也是在加密前不可預(yù)測的,且每個塊所用 c t r ctr ctr都是不同的;
-
當加密預(yù)言機是由真隨機查表構(gòu)成時,敵手多次訪問加密預(yù)言機得到的 c t r ctr ctr序列與挑戰(zhàn)密文的 c t r ctr ctr序列之間有重疊的概率 2 q ( n ) 2 2 n \frac{2q(n)^2}{2^n} 2n2q(n)2?是可以忽略的;若沒有重疊,則相當于一次一密;
-
規(guī)約與之前證明基于PRF的CPA安全加密方案一樣,證明過程也類似。
-
-
初始向量不應(yīng)該可預(yù)測
- 如果 I V IV IV是可預(yù)測的,那么CBC/OFB/CTR模式不是CPA安全的。
- 為什么?(作業(yè))
- 在SSL/TLS 1.0中的漏洞:記錄 # i \#i #i的 I V IV IV是上一個記錄 # ( i ? 1 ) \#(i-1) #(i?1)的密文塊。
- OpenSSL中API:需要用戶輸入 I V IV IV,但 I V IV IV應(yīng)在函數(shù)內(nèi)實現(xiàn)。當 I V IV IV不充分隨機時不安全。
-
非確定性加密
- 有三種通用的實現(xiàn)CPA安全的非確定性加密方法:
- 隨機化的: r r r隨機生成,如構(gòu)造5;需要更多熵,長密文
- 有狀態(tài)的: r r r為計數(shù)器,如CTR模式;需要通信雙方同步計數(shù)器
- 基于Nonce的: r r r只用一次;需要保證只用一次,長密文
CCA安全加密方案
-
選擇密文攻擊 Chosen-Ciphertext Attacks (CCA)
-
CCA不可區(qū)分實驗 P r i v K A , Π c c a ( n ) \mathsf{PrivK}^{\mathsf{cca}}_{\mathcal{A},\Pi}(n) PrivKA,Πcca?(n):
- 挑戰(zhàn)者生成密鑰 k ← G e n ( 1 n ) k \gets \mathsf{Gen}(1^n) k←Gen(1n);(為了下一步的預(yù)言機)
- A \mathcal{A} A 被給予輸入 1 n 1^n 1n 和對加密函數(shù) E n c k ( ? ) \mathsf{Enc}_k(\cdot) Enck?(?)和解密函數(shù) D e c k ( ? ) \mathsf{Dec}_k(\cdot) Deck?(?)的預(yù)言機訪問(oracle access) A E n c k ( ? ) \mathcal{A}^{\mathsf{Enc}_k(\cdot)} AEnck?(?) 和 A D e c k ( ? ) \mathcal{A}^{\mathsf{Dec}_k(\cdot)} ADeck?(?),輸出相同長度 m 0 , m 1 m_0, m_1 m0?,m1? ;
- 挑戰(zhàn)者生成隨機比特 b ← { 0 , 1 } b \gets \{0,1\} b←{0,1},將挑戰(zhàn)密文 c ← E n c k ( m b ) c \gets \mathsf{Enc}_k(m_b) c←Enck?(mb?) 發(fā)送給 A \mathcal{A} A;
- A \mathcal{A} A 繼續(xù)對除了挑戰(zhàn)密文 c c c之外的預(yù)言機的訪問,輸出 b ′ b' b′;如果 b ′ = b b' = b b′=b,則 A \mathcal{A} A成功 P r i v K A , Π c c a = 1 \mathsf{PrivK}^{\mathsf{cca}}_{\mathcal{A},\Pi}=1 PrivKA,Πcca?=1,否則 0。
定義:一個加密方案是CCA安全的,如果實驗成功的概率與1/2的差異是可忽略的。
-
-
理解CCA安全
-
在現(xiàn)實世界中,敵手可以通過影響被解密的內(nèi)容來實施CCA。如果通信沒有認證,那么敵手可以以通信參與方的身份來發(fā)送特定密文。下一頁有具體真實案例。
-
CCA安全性意味著“non-malleability”(不可鍛造性,即改變但不毀壞),不能修改密文來獲得新的有效密文。
-
之前的方案中沒有CCA安全,因為都不是不可鍛造。
-
對基于PRF的CPA安全加密方案的CCA攻擊:
-
A \mathcal{A} A 獲得挑戰(zhàn)密文 c = < r , F k ( r ) ⊕ m b > c = \left<r, F_k(r)\oplus m_\right> c=?r,Fk?(r)⊕mb??,并且查詢與 c c c只相差了一個翻轉(zhuǎn)的比特的密文 c ′ c' c′,那么
m ′ = c ′ ⊕ F k ( r ) m' = c' \oplus F_k(r) m′=c′⊕Fk?(r) 應(yīng)該與 m b m_ mb? 除了什么之外都相同?(見下方的補充)
-
-
問題:上述操作模式也不是CCA安全的(作業(yè))
-
由此,可以總結(jié)出CCA下敵手的常用策略:
- 修改挑戰(zhàn)密文 c c c為 c ′ c' c′,并查詢解密預(yù)言機得到 m ′ m' m′
- 根據(jù)關(guān)系,由 m ′ m' m′來猜測被加密明文 m b m_b mb?
-
補充
在這個情況下, A \mathcal{A} A 獲得了挑戰(zhàn)密文 c = < r , F k ( r ) ⊕ m b > c = \left<r, F_k(r)\oplus m_\right> c=?r,Fk?(r)⊕mb?? 并查詢了一個只在一個比特上與 c c c 不同的密文 c ′ c' c′。我們來分析一下 m ′ = c ′ ⊕ F k ( r ) m' = c' \oplus F_k(r) m′=c′⊕Fk?(r) 與 m b m_ mb? 的關(guān)系。
首先,我們明確 c c c 的構(gòu)成:
- c c c 包含兩個部分:一個隨機數(shù) r r r 和使用密鑰 k k k 的函數(shù) F k ( r ) F_k(r) Fk?(r) 與明文 m b m_ mb? 的異或結(jié)果。
- 因此, c = < r , F k ( r ) ⊕ m b > c = \left<r, F_k(r)\oplus m_\right> c=?r,Fk?(r)⊕mb??。
現(xiàn)在,如果 A \mathcal{A} A 查詢了一個與 c c c 只在一個比特上不同的密文 c ′ c' c′,那么 c ′ c' c′ 也可以寫成兩部分,但其中一部分與 c c c 有一個比特的差異。這個差異可以在 r r r 部分,也可以在 F k ( r ) ⊕ m b F_k(r)\oplus m_ Fk?(r)⊕mb? 部分。
當 A \mathcal{A} A 計算 m ′ = c ′ ⊕ F k ( r ) m' = c' \oplus F_k(r) m′=c′⊕Fk?(r) 時,他們實際上是在解開 F k ( r ) ⊕ m b F_k(r)\oplus m_ Fk?(r)⊕mb? 的異或操作。這是因為異或操作是可逆的,且當兩次使用相同的值時會取消彼此的效果(即 A ⊕ B ⊕ B = A A \oplus B \oplus B = A A⊕B⊕B=A)。
因此,如果 c ′ c' c′ 的變化發(fā)生在 F k ( r ) F_k(r) Fk?(r) 部分,則 m ′ m' m′ 將與 m b m_ mb? 完全相同,因為 F k ( r ) F_k(r) Fk?(r) 部分的變化被異或操作取消了。但如果變化發(fā)生在 r r r 部分,則這個變化不會影響到 F k ( r ) ⊕ m b F_k(r)\oplus m_ Fk?(r)⊕mb? 部分,因此 m ′ m' m′ 將與 m b m_ mb? 在一個比特上不同。
綜上所述, m ′ m' m′ 與 m b m_ mb? 將在以下方面相同:
- 如果變化發(fā)生在 F k ( r ) F_k(r) Fk?(r) 部分,那么 m ′ m' m′ 與 m b m_ mb? 完全相同。
- 如果變化發(fā)生在 r r r 部分,那么 m ′ m' m′ 與 m b m_ mb? 除了那個翻轉(zhuǎn)的比特之外都相同。
填充預(yù)言機Padding-Oracle攻擊真實案例
-
Padding-Oracle(填充預(yù)言機)攻擊真實案例
- CAPTCHA服務(wù)商為Web網(wǎng)站提供驗證用戶是否為人類的服務(wù)。為此,一個CAPTCHA服務(wù)器與Web服務(wù)器間事先共享一個密鑰 k k k,服務(wù)工作原理如下:
- 當Web服務(wù)器驗證用戶是否為人類時,生成一個消息 w w w并以 k k k加密,向用戶發(fā)送一個密文 E n c k ( w ) Enc_k(w) Enck?(w);
- 用戶將密文 E n c k ( w ) Enc_k(w) Enck?(w)轉(zhuǎn)發(fā)給CAPTCHA服務(wù)器;(可實施填充預(yù)言機攻擊)
- CAPTCHA服務(wù)器用密鑰 k k k將密文解密,根據(jù)解密結(jié)果返回給用戶信息:一個由 w w w生成的圖像,或者壞填充錯誤;
- 用戶根據(jù)圖像獲得 w w w 并將 w w w 發(fā)送給Web服務(wù)器。
- 在第2步,當惡意用戶可以利用CAPTCHA服務(wù)器會返回給用戶壞填充錯誤這一漏洞,來實施填充錯誤攻擊。
- CAPTCHA服務(wù)商為Web網(wǎng)站提供驗證用戶是否為人類的服務(wù)。為此,一個CAPTCHA服務(wù)器與Web服務(wù)器間事先共享一個密鑰 k k k,服務(wù)工作原理如下:
-
Padding-Oracle(填充預(yù)言機)攻擊
- 在PKCS #5 padding(填充)標準中,為了將一個消息的長度“填充”到塊長度的整數(shù)倍,在最后一個塊中填充 b b b個字節(jié)的 b b b;必要時,添加一個啞塊(dummy block,不包含消息的一個填充塊)。存在一種攻擊手段:當填充錯誤時,解密服務(wù)器返回一個“壞填充錯誤”,這相當于提供了一個解密預(yù)言機,最終可以獲得整個明文;
- 具體攻擊原理:
- 更改密文(包含 I V IV IV部分)并發(fā)送給解密服務(wù)器;
- 一旦觸發(fā)了“壞填充錯誤”,則說明對密文的更改導(dǎo)致了填充部分內(nèi)容的更改;否則,對密文的更改導(dǎo)致了原明文部分的更改;
- 通過仔細修改密文來控制填充部分,從而獲得消息長度和內(nèi)容。
-
填充預(yù)言機攻擊:獲得消息長度
- 攻擊的第一步判斷消息是否為空:在單個塊的CBC中,通過更改 I V IV IV的首個字節(jié),攻擊者能夠獲知是否 m m m是否為空。因為如果 m m m是空的話,更改 I V IV IV首個字節(jié)將更改解密出的填充內(nèi)容,解密服務(wù)器就會返回壞填充錯誤(1比特信息),具體分析如下:
- 如果 m m m是空的,那么明文會添加一個啞塊 { b } b \{b\}^b {b}b;
- PRP的輸入為 I V ⊕ { b } b IV\oplus \{b\}^b IV⊕{b}b;設(shè) I V IV IV的首個字節(jié)為 x x 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);
- 將 I V IV IV的首個字節(jié)從 x x x改成 y y y變?yōu)? y ∥ ( { ? } b ? 1 ) y \| (\{\cdot\}^{b-1}) y∥({?}b?1),不改變 c 1 c_1 c1?解密得到的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 b b,這是填充格式錯誤,會觸發(fā)服務(wù)器返回錯誤;
- 如果上面的嘗試沒有觸發(fā)錯誤,那么說明消息非空;下一步,發(fā)現(xiàn)消息長度是否為1字節(jié),方法與上一步一樣,區(qū)別在于只改變 I V IV IV的第2個字節(jié);如此繼續(xù),獲得消息的長度;(作業(yè))
- 攻擊的第一步判斷消息是否為空:在單個塊的CBC中,通過更改 I V IV IV的首個字節(jié),攻擊者能夠獲知是否 m m m是否為空。因為如果 m m m是空的話,更改 I V IV IV首個字節(jié)將更改解密出的填充內(nèi)容,解密服務(wù)器就會返回壞填充錯誤(1比特信息),具體分析如下:
-
填充預(yù)言機攻擊:獲得消息內(nèi)容
- 一旦獲得消息的長度,也就知道了填充的長度 b b b,采用下面的方法來獲得消息的最后一個字節(jié)內(nèi)容,進而獲得整個消息;
- 更改密文中倒數(shù)第二塊,來獲得消息的最后一個字節(jié) s s 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 l a s t ? 1 c_{last-1} clast?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 u 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 b+1 b+1個字節(jié)的 b + 1 b+1 b+1,所以 s ⊕ t ⊕ u = ( b + 1 ) s \oplus t \oplus u = (b+1) s⊕t⊕u=(b+1) ,而 s = t ⊕ u ⊕ ( b + 1 ) s = t \oplus u \oplus (b+1) s=t⊕u⊕(b+1) 。
-
總結(jié)
- 略