设计方案表网站名称,哪些网站是做设计的,网站风格分类,企业管理方法【现代密码学】笔记3.4-3.7--构造安全加密方案、CPA安全、CCA安全 《introduction to modern cryphtography》 写在最前面私钥加密与伪随机性 第二部分流加密与CPA多重加密 CPA安全加密方案CPA安全实验、预言机访问#xff08;oracle access#xff09; 操作模式伪随机函数PR… 【现代密码学】笔记3.4-3.7--构造安全加密方案、CPA安全、CCA安全 《introduction to modern cryphtography》 写在最前面私钥加密与伪随机性 第二部分流加密与CPA多重加密 CPA安全加密方案CPA安全实验、预言机访问oracle access 操作模式伪随机函数PRF伪随机排列PRP CCA安全加密方案补充填充预言机Padding-Oracle攻击真实案例 写在最前面
主要在 哈工大密码学课程 张宇老师课件 的基础上学习记录笔记。
内容补充骆婷老师的PPT 《introduction to modern cryphtography》–Jonathan Katz, Yehuda Lindell现代密码学——原理与协议中相关章节 密码学复习笔记 这个博主好有意思
初步笔记如有错误请指正
快速补充一些密码相关的背景知识 私钥加密与伪随机性 第二部分 本节课学习另外两种私钥加密安全理论选择明文攻击CPA下不可区分性、选择密文攻击CCA下不可区分性以及相关的密码学原语、假设、构造和证明。这些攻击更好的刻画了现实世界中敌手的能力相应的密码学方案也是目前真正在实际使用的。 目录流加密与CPACPA安全加密方案操作模式CCA安全加密方案
流加密与CPA 流加密方案Stream Cipher 首先介绍当有多个消息需要被传递时如何利用之前学习的基于PRG的加密方案来保护消息。思路受一次一密方案的启发通过将变长消息与密钥的异或来加密流加密方案通过将多个消息“拼成”一个消息与伪随机的比特流密钥流异或来加密密钥流由一个变长的伪随机生成器产生优点逻辑简单比分组密码更快缺点难以做到安全 采用流加密方案的安全多重加密 同步模式用一个流中不同部分分别加密各个消息异步模式以密钥和初始向量一起作为输入来产生流每个明文的加密采用相同的密钥和不同的初始向量 初始向量Initial Vector I V IV IV是随机选取的并且是公开的其生成是随机的并不受控制但生成后并不保密密钥的生成是随机的并不受控制但生成后也要保密。 两种模式差异 同步模式适合持续通信场景例如语音异步模式适合间断通信场景例如即时消息。 流密码的安全性 现状没有标准化和流行的方案安全性仍有疑问例如在802.11中WEP协议的RC4线性反馈移位寄存器Linear Feedback Shift Registers警告不要使用任何流加密方案如果一定需要的话采用由分组加密方案构造的。eStream项目致力于设计安全的流密码 相关密钥真实世界例子 用于多重加密的密钥初始向量和密钥对必须是独立的。否则前面的攻击就会生效对于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会产生重复在一些WiFi网卡上在电源重启后 I V IV IV重置为0 I V i I V i − 1 1 IV_i IV_{i-1} 1 IViIVi−11. 对于RC4在40,000帧后可以恢复 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)当一次加密多个明文时窃听者敌手能够区分出两组明文吗一个敌手 A \mathcal{A} A与一个挑战者 C \mathcal{C} C进行3轮交互 A \mathcal{A} A选择两个长度相同、内容不同明文向量 M ⃗ 0 ( m 0 1 , … , m 0 t ) \vec{M}_0(m_0^1,\dots,m_0^t) M 0(m01,…,m0t), M ⃗ 1 ( m 1 1 , … , m 1 t ) \vec{M}_1(m_1^1,\dots,m_1^t) M 1(m11,…,m1t)其中两个向量中同一位置的明文长度相同 ∀ i , ∣ m 0 i ∣ ∣ m 1 i ∣ \forall i, |m_0^i| |m_1^i| ∀i,∣m0i∣∣m1i∣发送给 C \mathcal{C} C C \mathcal{C} C根据密钥生成算法生成一个新密钥 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 M b中每个明文加密 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) 并发送给 A \mathcal{A} A A \mathcal{A} A输出对所加密明文向量的猜测 b ′ b b′若 b b ′ bb bb′则 A \mathcal{A} A成功否则失败 这与之前的单个消息不可区分实验类似的区别在于用同一个密钥加密的多个消息。敌手可以获得多个明文的密文比单个明文不可区分实验中的敌手有更强的能力。 多重加密安全定义 Π \Pi Π 是窃听者出现时不可区分的多重加密方案如果任意PPT的敌手 A \mathcal{A} A, 存在可忽略的函数 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]≤21negl(n). 根据这个定义来分析迄今学习的密码学方案是否是多重加密不可区分的 攻击确定性加密方案 问题如果一个加密方案中加密算法是确定性的即同一个明文会被同一个密钥加密成同一个密文那么该加密方案是多重加密安全的吗攻击对于确定性加密方案敌手可以构造 m 0 1 m 0 2 m_0^1 m_0^2 m01m02 并且 m 1 1 ≠ m 1 2 m_1^1 \neq m_1^2 m11m12然后当 c 1 c 2 c^1 c^2 c1c2输出 b ′ 0 b0 b′0否则 b ′ 1 b1 b′1。因此确定性加密方案不是多重加密安全的我们需要新的密码学原语来防御多重加密攻击。接下来我们介绍一种更强的攻击其涵盖了多重加密攻击。只要防御了这个新定义的攻击也就同时防御了多重加密攻击。
CPA安全加密方案 选择明文攻击Chosen-Plaintext Attacks (CPA)思考 敌手具有获得其所选择明文对应的密文的能力。 第二次世界大战中的例子美国海军密码分析学家相信密文“AF”表示日语中的“中途岛”但美国将军不认为中途岛会遭到攻击这里没看懂美国海军密码分析学家发送了一个明文中途岛淡水供给不足日本军队截获的明文并发送了一段密文“AF”淡水不足美国军队派出三艘航空母舰并且取胜。 这里例子里美国海军密码分析学家选择了明文并得到了密文。
CPA安全实验、预言机访问oracle access CPA安全实验 CPA不可区分实验 P r i v K A , Π c p a ( n ) \mathsf{PrivK}^{\mathsf{cpa}}_{\mathcal{A},\Pi}(n) PrivKA,Πcpa(n): 挑战者生成密钥 k ← G e n ( 1 n ) k \gets \mathsf{Gen}(1^n) k←Gen(1n)这里与窃听者不可区分实验相比密钥的生成提前了这是为了下一步提供加密预言机 A \mathcal{A} A 被给予输入 1 n 1^n 1n 和对加密函数 E n c k ( ⋅ ) \mathsf{Enc}_k(\cdot) Enck(⋅)的预言机访问oracle access A E n c k ( ⋅ ) \mathcal{A}^{\mathsf{Enc}_k(\cdot)} AEnck(⋅) 输出相同长度 m 0 , m 1 m_0, m_1 m0,m1 挑战者生成随机比特 b ← { 0 , 1 } b \gets \{0,1\} b←{0,1}将挑战密文 c ← E n c k ( m b ) c \gets \mathsf{Enc}_k(m_b) c←Enck(mb) 发送给 A \mathcal{A} A A \mathcal{A} A 继续对 E n c k ( ⋅ ) \mathsf{Enc}_k(\cdot) Enck(⋅)的预言机的访问输出 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,Πcpa1否则 0。 敌手对加密函数预言机访问是指敌手以任意明文作为输入可以从预言机得到对应密文。此处密钥是已经提前生成的因此才能通过加密函数预研机得到密文但仍对敌手保密。预言机是一个形象的比喻它是一个黑盒只接收输入并返回输出访问者不需要了解其内部构造。该实验与窃听者不可区分实验的区别在于敌手可访问加密预言机在实验过程中始终可以包括在产生两个明文阶段以及在收到挑战密文后猜测被加密明文阶段获得任意明文被同一密钥加密的密文而且密文是逐个获得可以根据之前的明文和密文对来“适应性地”构造新的查询。CPA敌手比多重加密的敌手更“强大”因为多重加密敌手是可以一次性地获得一组密文而CPA敌手可以根据已经获得的明文和密文“多次适应性地”再次获得密文。 CPA安全 Π \Pi Π 是CPA不可区分加密方案 (CPA安全的)如果任意概率多项式时间算法 A \mathcal{A} A存在可忽略的函数 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]≤21negl(n) 定理CPA安全也是多重加密安全的。证明略。直觉上CPA敌手比多重加密敌手更强大。 之前的方案也难以实现CPA安全 多重加密安全意味着CPA安全作业显然是否定的。那么思考两种安全定义的区别成为解题的关键。
操作模式
伪随机函数PRF 伪随机函数Pseudorandom Function概念 为了实现CPA安全之前的PRG提供的随机性不够用了需要新的数学工具为加密提供额外的随机性。为此引入伪随机函数PRF是对伪PRG的泛化PRG从一个种子生成一个随机串PRF从一个key生成一个函数带密钥的函数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)两个输入到一个输出看上去像但不是加密函数输入key得到一个一输入到一输出的函数 查表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 需要多少比特信息存储 查表是一个直接描述输入与输出间映射的表格一个条目对应一个输入与一个输出当该映射是随机产生的是一个真随机函数 函数族Function family F u n c n \mathsf{Func}_n Funcn: 包含所有函数 { 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是函数族中一个子集key确定下的PRF是函数族中一个元素一个查表是函数族中一个元素 长度保留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密钥长度与函数输入、输出长度相同为 n n n没有特殊说明时只讨论长度保留的函数 伪随机函数定义 直觉上一个PRF生成的带密钥的函数与从函数族中随机选择的真随机函数查表之间是不可区分的然而一个真随机函数具有指数长度无法“预先生成”只能“on-the-fly”边运行、边生成的使用引入一个对函数 O \mathcal{O} O的确定性的预言机访问oracle access D O D^\mathcal{O} DO。这里的预言机是一个抽象的函数。访问预言机就是给出任意输入得到该函数的输出。访问预言机的能力不包括了解正在访问的预言机具体内部构造。一个带密钥的函数是一个伪随机函数PRF对任意PPT区分器 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中随机函数。 这里区分器 D D D是一个算法可以访问预言机但并不知道预言机背后是什么。这里不可区分性关键是对真随机查表和伪随机函数区分器输出相同结果概率的差异。区分器输出1或0本身没有也无需有特定语义。 PRF和PRG的关系在后面会学习可以由PRG来构造PRF。 PRF例题 问题一个固定长度的一次一密方案是一个PRF吗对于一个PRF在密钥保密和没有预言机访问时给指定输入能以不可忽略的概率猜测输出相关信息吗如果是PRF则给出该函数与查表的相似性否则给出一个区分器可以区分出该函数不是随机的。 以PRF实现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 : \leftr, 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的区分器算法 D \mathcal{D} D规约到加密方案敌手算法 A \mathcal{A} A区分器 D \mathcal{D} D作为敌手 A \mathcal{A} A的挑战者敌手 A \mathcal{A} A实验成功时区分器 D \mathcal{D} D输出1。分两种情况当输入真随机函数 f f f时相当于一次一密当输入伪随机函数 F k F_k Fk时为加密方案。规约 D \mathcal{D} D输入预言机输出一个比特 A \mathcal{A} A的加密预言机访问通过 D \mathcal{D} D的预言机 O \mathcal{O} O来提供 c : r , O ( r ) ⊕ m c : \leftr, \mathcal{O}(r) \oplus m \right c:⟨r,O(r)⊕m⟩ D \mathcal{D} D输出1当 A \mathcal{A} A在实验中成功。 这里有两个预言机 D \mathcal{D} D访问的预言机 O \mathcal{O} O A \mathcal{A} A访问的加密预言机 E n c k \mathsf{Enc}_k Enck后者不能直接访问前者的预言机。 从PRF到CPA安全的证明续 考虑真随机函数 f f f的情况分析不可区分实验成功概率 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访问加密预言机可以获得多项式 q ( n ) q(n) q(n)个明文与密文对的查询结果并得到随机串和pad { r i , f ( r i ) } \{ \left r_i, f(r_i) \right \} {⟨ri,f(ri)⟩}当收到挑战密文 c r c , s : f ( r c ) ⊕ m b c\leftr_c, s:f(r_c)\oplus m_b\right c⟨rc,s:f(rc)⊕mb⟩时根据之前查询结果中随机串是否与挑战密文中随机串相同分为两种情况 当有相同随机串时根据 r r r可以得到 f ( r c ) f(r_c) f(rc) m b f ( r c ) ⊕ s m_bf(r_c)\oplus s mbf(rc)⊕s但这种情况发生的概率 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]≤212nq(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). 根据伪随机函数定义 ε ( n ) \varepsilon(n) ε(n) 是可忽略的. 小结通过规约将 A \mathcal{A} A的不可区分实验成功的概率与 D D D的区分器实验输出1的概率建立等式分析输入真随机函数预言机时 D D D输出1的概率即不可区分实验成功概率是1/2一个可忽略函数根据PRF的定义输入伪随机函数预言机时 D D D输出1的概率1/2 ε ( n ) \varepsilon(n) ε(n)与输入真随机函数预言机时 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} mm1,…,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 为了提高对任意长度消息加密的效率以及更高级的加密基础工具学习伪随机排列PRP的概念 双射 Bijection: F F F 是一到一的一个输入对应一个唯一输出且满射覆盖输出集中每个元素 排列 Permutation: 一个从一个集合到自身的双射函数 带密钥的排列 Keyed permutation: ∀ k , F k ( ⋅ ) \forall k, F_k(\cdot) ∀k,Fk(⋅)是排列类似带密钥的函数 F F F 是一个双射 ⟺ F − 1 \iff F^{-1} ⟺F−1 是一个双射函数和逆函数都是双射 定义一个有效的带密钥的排列 F F F 是PRP如果对于任意PPT的区分器 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来构造一个PRG的方法将一个消息分成若干等长的块分组block每个块以相似方式处理 Electronic Code Book (ECB) 模式 在窃听者出现时是否是不可区分的 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的伪随机假设规约到CPA安全加密方案。其中对 c t r ctr ctr的安全性直觉在于 c t r ctr ctr也是在加密前不可预测的且每个块所用 c t r ctr ctr都是不同的 当加密预言机是由真随机查表构成时敌手多次访问加密预言机得到的 c t r ctr ctr序列与挑战密文的 c t r ctr ctr序列之间有重叠的概率 2 q ( n ) 2 2 n \frac{2q(n)^2}{2^n} 2n2q(n)2是可以忽略的若没有重叠则相当于一次一密 规约与之前证明基于PRF的CPA安全加密方案一样证明过程也类似。 初始向量不应该可预测 如果 I V IV IV是可预测的那么CBC/OFB/CTR模式不是CPA安全的。为什么作业在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应在函数内实现。当 I V IV IV不充分随机时不安全。 非确定性加密 有三种通用的实现CPA安全的非确定性加密方法随机化的 r r r随机生成如构造5需要更多熵长密文有状态的 r r r为计数器如CTR模式需要通信双方同步计数器基于Nonce的 r r r只用一次需要保证只用一次长密文
CCA安全加密方案 选择密文攻击 Chosen-Ciphertext Attacks (CCA) CCA不可区分实验 P r i v K A , Π c c a ( n ) \mathsf{PrivK}^{\mathsf{cca}}_{\mathcal{A},\Pi}(n) PrivKA,Πcca(n): 挑战者生成密钥 k ← G e n ( 1 n ) k \gets \mathsf{Gen}(1^n) k←Gen(1n)为了下一步的预言机 A \mathcal{A} A 被给予输入 1 n 1^n 1n 和对加密函数 E n c k ( ⋅ ) \mathsf{Enc}_k(\cdot) Enck(⋅)和解密函数 D e c k ( ⋅ ) \mathsf{Dec}_k(\cdot) Deck(⋅)的预言机访问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 挑战者生成随机比特 b ← { 0 , 1 } b \gets \{0,1\} b←{0,1}将挑战密文 c ← E n c k ( m b ) c \gets \mathsf{Enc}_k(m_b) c←Enck(mb) 发送给 A \mathcal{A} A A \mathcal{A} A 继续对除了挑战密文 c c c之外的预言机的访问输出 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,Πcca1否则 0。 定义一个加密方案是CCA安全的如果实验成功的概率与1/2的差异是可忽略的。 理解CCA安全 在现实世界中敌手可以通过影响被解密的内容来实施CCA。如果通信没有认证那么敌手可以以通信参与方的身份来发送特定密文。下一页有具体真实案例。 CCA安全性意味着“non-malleability”不可锻造性即改变但不毁坏不能修改密文来获得新的有效密文。 之前的方案中没有CCA安全因为都不是不可锻造。 对基于PRF的CPA安全加密方案的CCA攻击 A \mathcal{A} A 获得挑战密文 c r , F k ( r ) ⊕ m b c \leftr, F_k(r)\oplus m_{b}\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_{b} mb 除了什么之外都相同见下方的补充 问题上述操作模式也不是CCA安全的作业 由此可以总结出CCA下敌手的常用策略 修改挑战密文 c c c为 c ′ c c′并查询解密预言机得到 m ′ m m′根据关系由 m ′ m m′来猜测被加密明文 m b m_b mb
补充
在这个情况下 A \mathcal{A} A 获得了挑战密文 c r , F k ( r ) ⊕ m b c \leftr, F_k(r)\oplus m_{b}\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_{b} mb 的关系。
首先我们明确 c c c 的构成 c c c 包含两个部分一个随机数 r r r 和使用密钥 k k k 的函数 F k ( r ) F_k(r) Fk(r) 与明文 m b m_{b} mb 的异或结果。因此 c r , F k ( r ) ⊕ m b c \leftr, F_k(r)\oplus m_{b}\right c⟨r,Fk(r)⊕mb⟩。
现在如果 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_{b} 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_{b} Fk(r)⊕mb 的异或操作。这是因为异或操作是可逆的且当两次使用相同的值时会取消彼此的效果即 A ⊕ B ⊕ B A A \oplus B \oplus B A A⊕B⊕BA。
因此如果 c ′ c c′ 的变化发生在 F k ( r ) F_k(r) Fk(r) 部分则 m ′ m m′ 将与 m b m_{b} mb 完全相同因为 F k ( r ) F_k(r) Fk(r) 部分的变化被异或操作取消了。但如果变化发生在 r r r 部分则这个变化不会影响到 F k ( r ) ⊕ m b F_k(r)\oplus m_{b} Fk(r)⊕mb 部分因此 m ′ m m′ 将与 m b m_{b} mb 在一个比特上不同。
综上所述 m ′ m m′ 与 m b m_{b} mb 将在以下方面相同
如果变化发生在 F k ( r ) F_k(r) Fk(r) 部分那么 m ′ m m′ 与 m b m_{b} mb 完全相同。如果变化发生在 r r r 部分那么 m ′ m m′ 与 m b m_{b} mb 除了那个翻转的比特之外都相同。
填充预言机Padding-Oracle攻击真实案例 Padding-Oracle填充预言机攻击真实案例 CAPTCHA服务商为Web网站提供验证用户是否为人类的服务。为此一个CAPTCHA服务器与Web服务器间事先共享一个密钥 k k k服务工作原理如下 当Web服务器验证用户是否为人类时生成一个消息 w w w并以 k k k加密向用户发送一个密文 E n c k ( w ) Enc_k(w) Enck(w)用户将密文 E n c k ( w ) Enc_k(w) Enck(w)转发给CAPTCHA服务器可实施填充预言机攻击CAPTCHA服务器用密钥 k k k将密文解密根据解密结果返回给用户信息一个由 w w w生成的图像或者坏填充错误用户根据图像获得 w w w 并将 w w w 发送给Web服务器。 在第2步当恶意用户可以利用CAPTCHA服务器会返回给用户坏填充错误这一漏洞来实施填充错误攻击。 Padding-Oracle填充预言机攻击 在PKCS #5 padding填充标准中为了将一个消息的长度“填充”到块长度的整数倍在最后一个块中填充 b b b个字节的 b b b必要时添加一个哑块dummy block不包含消息的一个填充块。存在一种攻击手段当填充错误时解密服务器返回一个“坏填充错误”这相当于提供了一个解密预言机最终可以获得整个明文具体攻击原理 更改密文包含 I V IV IV部分并发送给解密服务器一旦触发了“坏填充错误”则说明对密文的更改导致了填充部分内容的更改否则对密文的更改导致了原明文部分的更改通过仔细修改密文来控制填充部分从而获得消息长度和内容。 填充预言机攻击获得消息长度 攻击的第一步判断消息是否为空在单个块的CBC中通过更改 I V IV IV的首个字节攻击者能够获知是否 m m m是否为空。因为如果 m m m是空的话更改 I V IV IV首个字节将更改解密出的填充内容解密服务器就会返回坏填充错误1比特信息具体分析如下 如果 m m m是空的那么明文会添加一个哑块 { b } b \{b\}^b {b}bPRP的输入为 I V ⊕ { b } b IV\oplus \{b\}^b IV⊕{b}b设 I V IV IV的首个字节为 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的首个字节从 x x x改成 y y y变为 y ∥ ( { ⋅ } b − 1 ) y \| (\{\cdot\}^{b-1}) y∥({⋅}b−1)不改变 c 1 c_1 c1解密得到的PRP的输入不会变而解密出的明文会改变为 ( x ⊕ y ⊕ b ) ∥ { b } b − 1 (x \oplus y \oplus b) \| \{b\}^{b-1} (x⊕y⊕b)∥{b}b−1上述明文首个字节一定不是 b b b这是填充格式错误会触发服务器返回错误如果上面的尝试没有触发错误那么说明消息非空下一步发现消息长度是否为1字节方法与上一步一样区别在于只改变 I V IV IV的第2个字节如此继续获得消息的长度作业 填充预言机攻击获得消息内容 一旦获得消息的长度也就知道了填充的长度 b b b采用下面的方法来获得消息的最后一个字节内容进而获得整个消息更改密文中倒数第二块来获得消息的最后一个字节 s s s明文的最后一个块 m l a s t ⋯ s ∥ { b } b m_{last} \cdots s \| \{b\}^{b} mlast⋯s∥{b}b密文的倒数第二个块 c l a s t − 1 ⋯ t ∥ { ⋅ } b c_{last-1} \cdots t \| \{\cdot \}^{b} 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 \}^{b}) 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 \}^{b} \oplus \{b\}^{b} \oplus \{b1\}^{b}) clast−1′⋯u∥({⋅}b⊕{b}b⊕{b1}b)其中 u u u是敌手猜测的某个字节解密获得最后一块明文 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)\| \{ b1 \}^b mlast′clast−1⊕mlast⊕clast−1′⋯(s⊕t⊕u)∥{b1}b如果没有返回坏填充错误那么意味着填充了 b 1 b1 b1个字节的 b 1 b1 b1所以 s ⊕ t ⊕ u ( b 1 ) s \oplus t \oplus u (b1) s⊕t⊕u(b1) 而 s t ⊕ u ⊕ ( b 1 ) s t \oplus u \oplus (b1) st⊕u⊕(b1) 。 总结 略
