Hello, I'm Louhc
0%

Introduction to Modern Cryptography(5) 认证加密

发表于 更新于 分类于

Introduction to Modern Cryptography Reading Notes

5 CCA-Security and Authenticated Encryption

这一章讨论的是如何保证 “secrecy in the presence of an active adversary”。

选择密文攻击和 CCA 安全

攻击者生成一段密文并使接收者对其进行解密，这样的攻击行为称为选择密文攻击(chosen-ciphertext attack)。

Padding-Oracle Attacks

对于使用 PKSC #7 标准(如果消息需要填充 \(b\) 个 byte，则在消息后填充 \(0\text{x}\overbrace{bb...b}^{b\text{ times}}\)，其中 \(b>0\)) 的 CBC-mode 加密，如果接收者收到了一个不符合 PKSC #7 标准的消息，则会发出一个 “bad padding” 错误，如果攻击者能探知这个信息，就可以进行攻击。

比如，对于有两个 block 的 CBC，\(m_2=c_1\oplus F^{-1}_k(c_2)\)，那么通过发送 \((c_1\oplus\Delta,c_2)\)，解密后会得到 \((m_1',m_2\oplus \Delta)\)，那么通过枚举 \(\Delta\) 的每一个 byte，可以破解出 \(b\) 的值，然后可以用类似的方式破解出 \(m_2\), \(m_1\) 的值。

下面定义 CCA-secure

The CCA indistinguishability experiment \(\text{PrivK}^{\text{cca}}_{\mathcal{A},\Pi(n)}\):

  1. A key \(k\) is generated by running \(\text{Gen}(1^n)\).
  2. \(\mathcal{A}\) is given input \(1^n\) and oracle access to \(\text{Enc}_k(\cdot)\) and \(\text{Dec}_k(\cdot)\).It outputs a pair of equal-length messages \(m_0, m_1\).
  3. A uniform bit \(b \in \{0, 1\}\) is chosen, and then a challenge ciphertext \(c \leftarrow \text{Enc}_k(m_b)\) is computed and given to \(\mathcal{A}\).
  4. The adversary \(\mathcal{A}\) continues to have oracle access to \(\text{Enc}_k(\cdot)\) and \(\text{Dec}_k(\cdot)\), but is not allowed to query the latter on the challenge ciphertext itself. Eventually, \(\mathcal{A}\) outputs a bit \(b'\).
  5. The output of the experiment is \(1\) if \(b' = b\), and \(0\) otherwise.If the output of the experiment is \(1\), we say that \(\mathcal{A}\) succeeds.

和前面一样，当 \(\text{Pr}[\text{PrivK}^{\text{cca}}_{\mathcal{A},\Pi(n)}=1]\leq\frac12+\text{negl}(n)\) 时，称 \(\Pi\) 是 indistinguishable encryptions under a chosen-ciphertext attack，或者 CCA-secure。

CCA-secure 表明了一个重要的性质，不可展性(non-malleability)，它确保攻击者即使拥有密文，也不能通过修改密文来生成另一个有效的密文，且新生成的密文对应的明文与原始明文之间存在有意义的关系。

认证加密

认证加密(authenticated encryption, AE) 同时保证了机密性(secrecy)和完整性(integrity)，是比 CCA-secure 更强的安全条件。

The unforgeable encryption experiment \(\text{Enc-Forge}_{\mathcal{A},\Pi(n)}\):

  1. A key \(k\) is generated by running \(\text{Gen}(1^n)\).
  2. The adversary \(\mathcal{A}\) is given input \(1^n\) and access to an encryption oracle \(\text{Enc}_k(\cdot)\). The adversary eventually outputs a ciphertext \(c\). Let \(m := \text{Dec}_k(c)\) and let \(\mathcal{Q}\) denote the set of all queries that \(\mathcal{A}\) submitted to its oracle.
  3. \(\mathcal{A}\) succeeds if and only if (1) \(m=\perp\) and (2) \(m\in \mathcal{Q}\). In that case the output of the experiment is defined to be \(1\).

也就是说，\(\mathcal{A}\) 只要自行构造出一个合法的密文就算成功。

若 \(\text{Pr}[\text{Enc-Forge}_{\mathcal{A},\Pi(n)}=1]\leq\frac12+\text{negl}(n)\)，称 \(\Pi\) 为 unforgeable。

如果 \(\Pi\) 同时满足 CCA-secure 和 unforgeable，则称 \(\Pi\) 是一个认证加密方案(authenticated encryption scheme)。

下面定义一个测试，同时包含了 CCA-secure 和 unforgeable 的测试。

The authenticated-encryption experiment \(\text{PrivK}^{\text{ae}}_{\mathcal{A},\Pi(n)}\):

  1. A key \(k\) is generated by running \(\text{Gen}(1^n)\).
  2. A uniform bit \(b\in \{0, 1\}\) is chosen.
  3. The adversary \(\mathcal{A}\) is given input \(1^n\) and access to two oracles:
    (a) If \(b = 0\), then \(\mathcal{A}\) is given access to \(\text{Enc}_k(\cdot)\) and \(\text{Dec}_k(\cdot)\).
    (b) If \(b = 1\), then \(\mathcal{A}\) is given access to \(\text{Enc}^0_k(\cdot)\) and \(\text{Dec}_{\perp}(\cdot)\).
    \(\mathcal{A}\) is not allowed to query a ciphertext \(c\) to its second oracle that it previously received as the response from its first oracle.
  4. The adversary outputs a bit \(b'\).
  5. The output of the experiment is defined to be \(1\) if \(b' = b\), and \(0\) otherwise. In the former case, we say that \(\mathcal{A}\) succeeds.

此时认证加密方案的定义可以改写为 \(\text{Pr}[\text{PrivK}^{\text{ae}}_{\mathcal{A},\Pi(n)}=1]\leq\frac12+\text{negl}(n)\)，这和之前的定义是等价的。

存在加密方案，是 CCA-secure 但不是认证加密。（书上要求证明，咋证啊）

认证加密方案

将CPA-secure的加密方案和安全的MAC组合起来形成一个加密方案，有三种常见的方式：

  1. Encrypt-and-authenticate 发送 \((\text{Enc}_{k_E}(m),\text{Mac}_{k_M}(m))\)
  2. Authenticate-then-encrypt 发送 \(\text{Enc}_{k_E}(m||\text{Mac}_{k_M}(m))\)
  3. Encrypt-then-authenticate 发送 \((\text{Enc}_{k_E}(m),\text{Mac}_{k_M}(\text{Enc}_{k_E}(m)))\)

Encrypt-and-authenticate，由于 \(Mac\) 往往是确定函数，不可能保证 CPA-secure。

Authenticate-then-encrypt 攻击者可以通过选择密文攻击来破解。

Encrypt-then-authenticate 是满足认证加密条件的。（证明先跳过）

认证加密方案实例

介绍了三种实际使用的 AE 加密方案。

GCM (Galois/counter mode)

CCM (Counter with CBC-MAC)

ChaCha20–Poly1305

安全会话