03 认证加密

我们已经独立地讨论了“安全”的两个方面：保密性与真实性。现在我们要考虑如何构造一个能够兼顾两个方面的安全性的方案。

选择密文攻击(Chosen-Ciphertext Attacks, CCA)

我们回到普通的私钥加密的场景，这里只有消息$m$和私钥$k$，没有标签$t$。在只考虑被动的没有能力修改密文的窃听者时，我们基于选择明文攻击定义了CPA安全性。现在考虑一个具有篡改密文能力的敌手，它能够通过给接收方发送其自己构造的密文，通过观察接收方的在此之后的“举动”来实现破译。换言之，接收方在接受到一个经过篡改的密文之后做出的行为本身有可能暴露明文的信息。例如，在一个CPA安全的block cipher加密方案中，我们通常要对长度不恰好为$n$的倍数的消息做padding（增加符合某种模式的冗余字符），而这一padding方案是敌手事先已知的。此时敌手对于一个截获的密文，可以修改其中的某些位重新发给接收方，接收方会有一个程序检查padding是否合法并在不合法的时候返回“错误”。我们发现，在实践中敌手可以通过不断尝试并结合接收方返回的错误与否这一信息还原出整个明文，哪怕加密方案是CPA安全的。可见，在具有篡改密文能力的敌手面前，CPA安全已经不够用了。

在以上例子中，我们看到敌手具有“让接收方收到某个密文并做出反应”的能力。通常情况下，接收方在收到一个长得稀奇古怪的密文时不免会有一些反应被敌手观察到，这样敌手就会对它构造的密文做出调整。既然这样，那么我们几乎可以说敌手有能力验证他构造的密文是否合情合理。我们不妨进一步加强，直接假定他有能力询问每一条密文对应的明文！（但不能是他想要破译的那条密文，否则就没有意义定义安全了），这样的攻击称为“选择密文攻击(CCA)”。

下面我们具体的定义CCA安全性：敌手选择两条明文$m_0,m_1$，我们随机把其中一条加密为$c$还给敌手。在这个过程中，敌手有选择明文并获取密文的oracle、选择密文并获取明文的oracle，它可以访问这两个oracle任意多项式次。但是，敌手不能获取$c$的明文。如果敌手猜对的概率不超过$1/2+\text{negl}$，就称这一方案是CCA不可辨别的。一个CCA不可辨别的方案被称为CCA-secure的。

直观上，要想抵抗选择密文攻击，我们的加密方案需要具备这样的性质：一条密文一旦经过了任何修改，它在解密后就完全和原来的密文没有任何关联了——经过修改的密文在解密后不包含原明文的任何信息。

从定义上来看，CCA-secure只对安全性给出了定义，并没有直接保证真实性（尽管我们是从真实性角度出发才定义了选择密文攻击）。事实上，我们可以构造出一个方案，它满足CCA-secure的条件，但是却是forgeable的。可见，为了同时保证保密性和真实性，CCA-secure是不够的，我们还需要进一步加强安全的定义（也就是接下来要讨论的认证加密）。

在这里我们暂时先不给出如何构造一个具体的CCA-secure的例子。原因是，大多数构造自然的CCA-secure方案其实都是unforgeable的。如果有什么场合需要我们用一个CCA-secure但是forgeable的方案，一定是因为这个方案比保证unforgeable的方案效率更高。但目前人们还没发现一个效率更高的方案。所以一般的，我们只需要用认证加密安全的方案就好了。

认证加密(Authenticated Encryption, AE)

下面我们加强CCA-secure的定义，给出AE-secure的定义。AE-secure依然是定义在一个私钥加密方案$(\text{Gen},\text{Enc},\text{Dec})$上的。我们给出两种定义方式，这两种定义方式是等价的。

第一种定义方式是分别定义什么是AE意义下的保密性和真实性。在这里，我们把保密性就定义为CCA-secure的。而因为方案中并没有$\text{Mac}$和$\text{Vrfy}$，所以我们需要重新用实验定义真实性：多项式算力的敌手能够访问一个加密oracle（输入明文$m$吐出密文$\text{Enc}_k(m)$），我们要求它最终交出一个密文$c$（当然是未被oracle输出过的）。假如运行$\text{Dec}_k(c)$不会输出错误，就称敌手成功。如果敌手成功的概率$\leq \text{negl}$，就称这一方案是AE-unforgeable的。如果一个加密方案又是CCA-secure的，又是AE-unforgeable的，就称这个方案是一个AE-secure的方案(authenticated encrption scheme)。

另一种定义方式是设计一个实验同时描述保密性和真实性。假设我们有两套oracle，每套oracle里有一个加密oracle和解密oracle。第一套中的两个oracle就是方案本身的加密算法和解密算法；第二套中的加密oracle无论接受怎样的输入$m$，都只输出与$m$长度相同的全零串对应的密文$\text{Enc}_k(0^{|m|})$，解密oracle无论收到怎样的输入都返回密文不合法。我们规定敌手不能把加密oracle里输出的密文放进解密oracle里（不然这样解密oracle不可能输出不合法，这个实验就失去意义了）。实验开始时，我们随机选择一套oracle交给多项式算力的敌手，要求敌手分辨它得到的这套oracle是第一套还是第二套。如果敌手正确分辨的概率不超过$1/2+\text{negl}$，就称这一加密方案是AE方案。

这两种定义之所以等价的直观是，假如敌手不能分辨这两套oracle，说明敌手无法辨别它拿到的所有密文和全零串的密文的关系，也即密文没有泄露信息（保密性），并且在实验过程中敌手生成的密文始终都是不合法的（不可伪造性）。

具体的AE方案构造

我们构造一个AE方案的基本想法是，用某种方式合并一个已有的CPA-secure的方案（注意是CPA不是CCA！）与一个已有的MAC-strongly-secure的方案（要求strongly！）。也即，我们希望有一种AE-secure的构造方式，任何一个CPA-secure方案和任何一个MAC-strongly-secure方案在一起就可以组合出一个AE方案。

组合这二者的方式有很多。例如我们有以下三种组合方案（$k_E,k_M$分别代表加密密钥和认证密钥，它们是独立生成的）：

• $c=\text{Enc}_{k_E}(m),t=\text{Mac}_{k_M}(m)$；
• $t=\text{Mac}_{k_M}(m),c=\text{Enc}_{k_E}(m\| t)$；
• $c=\text{Enc}_{k_E}(m),t=\text{Mac}_{k_M}(c)$；

第一种显然是不安全的，因为$t$作为消息的认证码直接被传送，没有任何安全的保障。例如，考虑确定性的MAC，它一定是strongly-secure的。一个关于消息的确定性的函数总是无法保证CPA-secure的，因此更不可能满足AE-secure中要求的CCA-secure了。

第二种也是不安全的。因为它需要把tag接到消息末尾再做CPA加密，这和我们开头给出的用CCA对padding的攻击是完全类似的。

第三种方案是安全的。这个方案具体是这样做的：对于给定的$n$，用加密方案的$\text{Gen}^E$和认证方案的$\text{Gen}^M$独立生成密钥$k_E,k_M$；用这两个密钥结合$\text{Enc}^E$和$\text{Enc}^M$先后生成$c,t$，组合成$c\|t$后作为密文发送；接收方收到以后，用$\text{Vrfy}^M$验证$c,t$，如果验证通过就运行解密程序输出$\text{Dec}^M(c)$，否则输出一个错误字符$\bot$。这个方案称为先加密后认证(encrypt-then-authenticate)方案。

下面我们来证明encrypt-then-authenticate方案是安全的。设该方案为$\Pi$，对应的CPA-secure方案与MAC-strongly-secure方案为$\Pi^E,\Pi^M$。

我们用AE-secure的第一种定义方式。先证明$\Pi$是AE-unforgeable的，只需证，我们要证明任何多项式算力敌手$\mathcal{A}_0$在不断输入明文$m$询问oracle得到密文$\text{Enc}^\Pi(m)$以后，给出一个形如$c\|t$的密文通过验证$\text{Vrfy}^M$的概率不超过$\text{negl}$。要证明这一点，我们不妨假设一个CCA-secure定义的实验中攻击$\Pi$的敌手$\mathcal{A}$，它不仅可以访问加密oracle，而且可以访问解密oracle。所以，我们只需证明$\mathcal{A}$能够输出通过验证的$c\|t$的概率不超过$\text{negl}$即可。这等价于，$\mathcal{A}$能输入给解密oracle一个它从未输入过加密oracle的密文$c\|t$使得这条密文能通过验证。 我们把这个事件称为$\textsf{ValidQuery}$，只需证明$\Pr[\textsf{ValidQuery}]\leq \text{negl}$。我们利用$\Pi^M$的unforgeability来证明。对于任何challenge $\Pi^M$的敌手$\mathcal{A}_M$，有权访问oracle $\text{Mac}_{k_M}$。我们可以令$\mathcal{A}_M$随机生成一个$k_E$以及$1$到$q$中的一个整数$i$（$q$是$\mathcal{A}$询问解密oracle的总次数，这是$\mathcal{A}_M$可以提前知道的，因为$\mathcal{A}$是一个事先写好的程序）。于是$\mathcal{A}_M$可以这样充当$\mathcal{A}$的加密oracle：对于输入$m$，用$k_E$做加密得到$c=\text{Enc}_{k_E}(m)$，把$c$放入它自己的$\text{Mac}_{k_M}$ oracle得到$t$，把$c\|t$返回给$\mathcal{A}$。$\mathcal{A}_M$可以这样充当$\mathcal{A}$的解密oracle：如果输入$c\|t$曾是$\mathcal{A}$之前询问加密oracle的一个输出，那么返回对应的输入；否则返回错误，除非这恰好是$\mathcal{A}$的第$i$次询问解密oracle，此时$\mathcal{A}_M$给出$\mathcal{A}$的输入作为它的最终猜测$c\|t$并停机。我们看到，以上对$\mathcal{A}_M$的构造实际上是让$\mathcal{A}_M$去赌$\mathcal{A}$会在第$i$次询问解密oracle的时候给出一个valid query。我们来分析$\mathcal{A}_M$成功forge的概率。注意到如果$\textsf{ValidQuery}$发生且$\mathcal{A}_M$猜对了$i$，那么$\mathcal{A}_M$一定成功forge。并且，$A_M$猜对$i$的概率恰好是$1/q$（因为我们的猜测是均匀随机的，并且不会影响$\mathcal{A}$的决策）。注意到，在$\textsf{ValidQuery}$发生之前，$\mathcal{A}_M$完美的模拟了$\mathcal{A}$的oracle。因此有$\Pr[\textsf{ValidQuery}]\cdot \dfrac{1}{q}\leq \Pr[forge_{\mathcal{A}_M}]$。而$q$是多项式，因此$\Pr[\textsf{ValidQuery}]\leq q\Pr[forge_{\mathcal{A}_m}]\leq\text{negl}$。

再证明$\Pi$是CCA-secure的。再次假设$\mathcal{A}$是CCA实验中的敌手，我们要证$\mathcal{A}$成功分辨的概率$\Pr[S_{\mathcal{A}}]\leq 1/2+\text{negl}$。由全概率公式有$\Pr[S_\mathcal{A}]=\Pr[S_\mathcal{A}\land \textsf{ValidQuery}]+$ $\Pr[S_\mathcal{A}\land \overline{\textsf{ValidQuery}}]\leq \Pr[\textsf{ValidQuery}]+\Pr[S_\mathcal{A}\land \overline{\textsf{ValidQuery}}]$。所以只需证$\Pr[S_\mathcal{A}\land \overline{\textsf{ValidQuery}}]\leq 1/2+\text{negl}$。我们利用$\Pi^E$的CPA-security来证明。对于任何challenge $\Pi^E$的敌手$\mathcal{A}_E$，有权访问oracle $\text{Enc}_{k_E}$（和oracle $\text{Dec}_{k_E}$，但在下面的方案中我们不需要用到这个oracle）。我们可以令$\mathcal{A}_E$随机生成一个$k_M$，于是$\mathcal{A}_E$可以这样充当$\mathcal{A}$的加密oracle：对于输入$m$，输入加密oracle得到$c=\text{Enc}_{k_E}(m)$，用$k_M$得到$t=\text{Mac}_{k_M}(c)$，把$c\|t$返回给$\mathcal{A}$。$\mathcal{A}_M$可以这样充当$\mathcal{A}$的解密oracle：如果输入$c\|t$曾是$\mathcal{A}$之前询问加密oracle的一个输出，那么返回对应的输入；否则返回错误。当$\mathcal{A}$选好两个challenge用的消息$m_0,m_1$后，$\mathcal{A}_E$也跟着选这两个消息交给$\mathcal{A}_E$的challenger得到其中一个的加密$c$，返还给$\mathcal{A}$。当$\mathcal{A}$做出了猜测，$\mathcal{A}_M$也做同样的猜测。注意到，如果$\textsf{ValidQuery}$不发生，那么$\mathcal{A}_E$不仅完美模拟了加密oracle，而且还完美模拟了解密oracle（因为$\mathcal{A}$从来没造出来一个合法的$c\|t$，所以一直输出错误就是真实发生的情况）。$\mathcal{A}$猜对当且仅当$\mathcal{A}_E$猜对。所以$\Pr[S_{\mathcal{A}}\land \overline{\textsf{ValidQuery}}]=\Pr[S_{\mathcal{A}_E}]\leq 1/2+\text{negl}$。这样就证完了。

Rmk. 从上述证明看出，在encrypt-then-authenticate中，我们只用到了MAC-secure（没有用到MAC-strongly-secure）。这说明即便加密方案不是CPA-secure的，只要认证方案是MAC-secure的就能证明encrypt-then-authenticate是AE-unforgeable的。另一方面，如果$\Pi_M$是MAC-secure却不是MAC-strongly-secure，那么以上构造将不是AE-secure的（只需在末尾加一个随机串，就会发现敌手只需改一下末尾的位就可以询问解密oracle，因此甚至不是CCA-secure的）