現(xiàn)代密碼學(xué)3.7--CCA安全

• CCA安全
• • 含oracle的實(shí)驗(yàn)過(guò)程$Priv{K}_{\mathcal{A},\Pi }^{cca}(n)$
  • CCA安全定義
• 對(duì)不滿(mǎn)足CCA安全的密碼方案的攻擊
• • 簡(jiǎn)單例子：對(duì)基于PRF構(gòu)造的密碼方案的攻擊
  • 復(fù)雜例子：對(duì)CBC的攻擊，padding-oracle
  • • 求出$b$
    • 求出$m$的每一位

博主正在學(xué)習(xí)INTRODUCTION TO MODERN CRYPTOGRAPHY (Second Edition) --Jonathan Katz, Yehuda Lindell，做一些筆記供自己回憶，如有錯(cuò)誤請(qǐng)指正。整理成一個(gè)系列現(xiàn)代密碼學(xué)，方便檢索。

• 第二章定義了完美安全及其對(duì)應(yīng)的密碼方案“一次一密”，
• 第三章3.1、3.2定義了計(jì)算安全，3.3介紹了PRG和基于PRG構(gòu)造的滿(mǎn)足計(jì)算安全的密碼方案；
• 3.4節(jié)定義了CPA安全，3.5節(jié)介紹了PRF和基于PRF構(gòu)造的滿(mǎn)足CPA安全的密碼方案，3.6節(jié)介紹了PRG和PRF構(gòu)造的流密碼和分組密碼；
• 3.7節(jié)
  • 將介紹一種新的安全性：CCA安全，這種安全性是之前我們構(gòu)造的密碼方案都不滿(mǎn)足的，non-malleability/不可延展性是滿(mǎn)足CCA安全的必要條件；
  • 并以CBC分組密碼為例，表示對(duì)于這種不滿(mǎn)足CCA安全的密碼方案，可以進(jìn)行怎樣的攻擊。

CCA安全

跟CPA安全很類(lèi)似，除了encryption oracle外，多了decryption oracle，只有一個(gè)要求：不能問(wèn)oracle跟挑戰(zhàn)密文一樣的密文。

含oracle的實(shí)驗(yàn)過(guò)程$Priv{K}_{\mathcal{A},\Pi }^{cca}(n)$

• 敵手$\mathcal{A}$已知安全參數(shù)$1^n$，有一個(gè)連接$En{c}_k(?)$的oracle和連接$De{c}_k(?)$的oracle，輸出等長(zhǎng)明文$m_0,m_1$給加密者；
• 加密者任選$b\in \{0,1\}$，輸出密文$c\leftarrow En{c}_k(m_b)$給敵手$\mathcal{A}$，$c$是挑戰(zhàn)密文；
• 敵手$\mathcal{A}$在獲得$c$后，仍有一個(gè)連接$En{c}_k(?)$的oracle和連接$De{c}_k(?)$的oracle（可以根據(jù)$c$調(diào)整，繼續(xù)查詢(xún)），輸出猜測(cè)的$b^{\prime }$；
• 如果$b^{\prime }=b$輸出1，否則輸出0。

CCA安全定義

私鑰加密方案$\Pi =(Gen,Enc,Dec)$如果對(duì)于任意PPT敵手$\mathcal{A}$，都有一個(gè)可忽略函數(shù)negl滿(mǎn)足$Pr[Priv{K}_{\mathcal{A},\Pi }^{cca}(n)=1]\le \frac{1}{2}+$negl$(n)$，則稱(chēng)該方案$\Pi$在選擇明文攻擊下有不可區(qū)分的加密，是滿(mǎn)足CCA安全的。

安全性：多次加密的CCA安全=單次加密的CCA安全。

對(duì)不滿(mǎn)足CCA安全的密碼方案的攻擊

簡(jiǎn)單例子：對(duì)基于PRF構(gòu)造的密碼方案的攻擊

• 根據(jù)3.5節(jié)構(gòu)造基于PRF的密碼方案$\Pi$$：m_0=0^n$，$m_1=1^n$，$En{c}_k(m)=<F_k(r)\oplus m>$，$c=<r,s>$
• 如果修改$c$的第一個(gè)比特$s$，記作$c^{\prime }$；
• 因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$c=c^{\prime }$，所以可以問(wèn)decryption oracle；得到$10^{n?1}$或者$01^{n?1}$，那么就可以判斷是$m_0$還是$m_1$，這不滿(mǎn)足CCA安全。

所以，滿(mǎn)足CCA安全的密碼方案的必要條件是不可延展性：如果敵手修改一個(gè)給定密文，結(jié)果是一個(gè)無(wú)效密文或者解密得到一個(gè)與原始明文完全無(wú)關(guān)的明文。

復(fù)雜例子：對(duì)CBC的攻擊，padding-oracle

• $L$：塊長(zhǎng)度
• $b$：需要被填充的字節(jié)數(shù)，$b=0$，如果已經(jīng)是不需要填充，則填充$L$個(gè)字節(jié)，有$1\le b\le L$
• 填充規(guī)則：如果需要填充1個(gè)字節(jié)，則填$01$；如果需要填充4個(gè)字節(jié)，則填$04040404$；如果需要填充$b$個(gè)字節(jié)，則填$b$個(gè)$0b$
• 加密：對(duì)明文$m$填充至$L$的倍數(shù)，對(duì)填充后的信息進(jìn)行CBC加密
• 解密：按CBC解密，得到填充后的信息，找到最后一個(gè)字節(jié)$0b$，
  • 如果后$b$個(gè)都是$0b$，刪去這$b$個(gè)$0b$，得到原始明文；
  • 如果后$b$個(gè)不都是$0b$，則不符合填充規(guī)則，返回"bad padding" error。
  • 根據(jù)這兩種不同的返回，我們可以求出$b$，進(jìn)而求出明文信息的每一位。這種decryption oracle被稱(chēng)為padding-oracle，對(duì)于不滿(mǎn)足CCA安全的CBC分組加密模式可以進(jìn)行攻擊。

以3-block為例：$IV,c_1,c_2$，每個(gè)block長(zhǎng)度為$L$，解密$m_2=F_k^{?1}(c_2)\oplus c_1$，$c_1$改變則$m_2$會(huì)相應(yīng)改變

求出$b$

• 本來(lái)解密是正確的，改變$c_1$的第一個(gè)字節(jié)，如果解密$m_2$返回"bad padding"error，則說(shuō)明$c_1$($L$長(zhǎng))的第一個(gè)字節(jié)就屬于padding位（那么后面都屬于padding位），而padding位$1\le b\le L$最多只有$L$位，那么$b=L$；
• 同理，如果改變第一個(gè)字節(jié)解密還是正確的，改變第二個(gè)字節(jié)返回error，則$b=L?1$。

求出$m$的每一位

• 取${△}_i=(0\dots 0||0i||0(b+1)\dots 0(b+1)\oplus (0\dots 0||00||0b\dots 0b)$，$0\le i\le 2^8?1$
• $m_2$的最后一位是$B0b\dots 0b$
• 現(xiàn)在修改$c_1$為“$c_1\oplus {△}_i$”，則$m_2$最后一位相應(yīng)改變?yōu)?span id="ze8trgl8bvbq" class="katex--inline">$B\oplus i||(b\oplus (b+1)\dots b\oplus (b+1)$
• 除非$B\oplus {△}_i=b\oplus (b+1)$，解密$m_2$會(huì)返回"bad padding" error；
• 我們只需要遍歷$i$，找到某個(gè)$i$使得解密$m_2$不返回"bad padding " error，此時(shí)$B={△}_i\oplus b\oplus (b+1)$。
• 按照求最后一位$B$的方式去求其他位。

總結(jié)

以上是生活随笔為你收集整理的现代密码学3.7--CCA安全的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。