Introduction to Modern Cryptography Reading Notes

6 Hash Functions and Applications

哈希函数的定义

A hash function (with output length \(\ell(n)\)) is a pair of probabilistic polynomial-time algorithms \((\text{Gen}, H)\) satisfying the following:

• \(\text{Gen}\) is a probabilistic algorithm that takes as input a security parameter \(1^n\) and outputs a key \(s\). We assume that \(n\) is implicit in \(s\).
• \(H\) is a deterministic algorithm that takes as input a key \(s\) and a string \(x \in \{0, 1\}^∗\) and outputs a string \(H^s(x) \in \{0, 1\}^{\ell(n)}\) (where \(n\) is the value of the security parameter implicit in \(s\)).

If \(H^s\) is defined only for inputs \(x\) of length \(\ell'(n) > \ell(n)\), then we say that \((\text{Gen}, H)\) is a fixed-length hash function for inputs of length \(\ell'(n)\). In this case, we also call \(H\) a compression function.

在这里，攻击者往往会知道 \(s\) 的值，因此 \(s\) 放在 \(H\) 的上标。

The collision-finding experiment \(\text{Hash-coll}_{\mathcal{A},\mathcal{H}(n)}\) \((\mathcal{H}=(\text{Gen},H))\):

1. A key \(s\) is generated by running \(\text{Gen}(1^n)\).
2. The adversary \(\mathcal{A}\) is given \(s\), and outputs \(x, x'\) . (If \(H\) is a fixed-length hash function for inputs of length \(\ell'(n)\), then we require \(x, x' \in \{0, 1\}^{\ell'(n)}\).)
3. The output of the experiment is defined to be \(1\) if and only if \(x = x'\) and \(H^s(x) = H^s(x')\). In such a case we say that \(\mathcal{A}\) has found a collision.

如果 \(\text{Pr}[\text{Hash-coll}_{\mathcal{A},\mathcal{H}(n)}=1]\leq\text{negl}(n)\)，则称 \(\mathcal{H}\) 是collision resistant的。

下面给出两个其他关于哈希安全的概念。

• Second-preimage resistance 给出 \(s\) 和一个均匀分布的 \(x\)，一个PPT的 \(\mathcal{A}\) 几乎无法找到 \(x'\) 使得 \(x\neq x',H(x)=H(x')\)
• Preimage resistance 给出 \(s\) 和 \(y=H^s(x)\) 对于一个均匀分布的 \(x\)，一个PPT的 \(\mathcal{A}\) 几乎无法找到 \(x'\) 使得 \(H(x)=H(x')\) (\(x'\) 可以等于 \(x\))

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.

Introduction to Modern Cryptography Reading Notes

4 Message Authentication Codes

MAC的定义

我们需要保证消息可靠性(message integrity)，以应对攻击者可能会注入或修改信息的情况，为此需要引入新的机制 message authentication code (MAC)。

A message authentication code (or MAC) consists of three probabilistic polynomial-time algorithms \((\text{Gen},\text{Mac},\text{Vrfy})\) such that:

1. The key-generation algorithm \(\text{Gen}\) takes as input the security parameter \(1^n\) and outputs a key \(k\) with \(|k| \geq n\).
2. The tag-generation algorithm \(\text{Mac}\) takes as input a key \(k\) and a message \(m \in \{0, 1\}^*\), and outputs a tag \(t\). Since this algorithm may be randomized, we write this as \(t \leftarrow \text{Mac}_k(m)\).
3. The deterministic verification algorithm \(\text{Vrfy}\) takes as input a key \(k\), a message \(m\), and a tag \(t\). It outputs a bit \(b\), with \(b = 1\) meaning valid and \(b = 0\) meaning invalid. We write this as \(b := \text{Vrfy}_k(m, t)\).

It is required that for every \(n\), every key \(k\) output by \(\text{Gen}(1^n)\), and every \(m \in \{0, 1\}^∗\), it holds that \(\text{Vrfy}_k(m, \text{Mac}_k(m)) = 1\).

If there is a function \(\ell\) such that for every \(k\) output by \(\text{Gen}(1^n)\), algorithm \(\text{Mac}_k\) is only defined for messages \(m \in \{0, 1\}^{\ell(n)}\), then we call the scheme a fixed-length MAC for messages of length \(\ell(n)\).

接下来就是关于 MAC 的安全测试和安全定义。

The message authentication experiment \(\text{Mac-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 oracle access to \(\text{Mac}_k(\cdot)\).The adversary eventually outputs \((m, t)\). Let \(Q\) denote the set of all queries that \(\mathcal{A}\) submitted to its oracle.
3. \(\mathcal{A}\) succeeds if and only if (1) \(\text{Vrfy}_k(m, t) = 1\) and (2) \(m \notin Q\).In that case the output of the experiment is defined to be \(1\).

也就是说，\(\mathcal{A}\) 能多次访问黑盒 \(\text{Mac}_k\)，如果构造出任意一组能通过 \(\text{Vrfy}\) 验证的，且自己没有把明文输入给 \(\text{Mac}_k\) 的 \((m,t)\)，就算 \(\mathcal{A}\) 成功。注意到，如果通过 \(t\) 构造出一个 \(m\)，使得 \((m,t)\) 通过验证，那么 \(\mathcal{A}\) 也是通过该测试的。

对于安全的定义和之前类似，即通过测试的概率可忽略，就不再抄一遍了。

上面的定义并没有预防 replay attacks，即攻击者可以重复发送一条信息（比如，转账请求）。这种问题一般在应用层面进行解决，比如在消息中添加编号或时间戳这类信息。

hexo 自带的 markdown 渲染器太拉了，老是和 mathjax 冲突，包括但不限于把公式里的 / 和 _ 认成 markdown 语法

所以改用 pandoc 了

1. Hello
2. World

1

This is code

\(\binom{n}{m}=\frac{n!}{m!(n-m)!}\)

\[ c\leftarrow \text{Enc}_k(m) \]

Introduction to Modern Cryptography Reading Notes

3 Private-Key Encryption

具体安全和渐进安全

安全有两种定义，具体的(concrete)和渐进的(asymasymptotic)。简单地说，具体安全依靠具体的数值，而渐进安全依靠关于 \(n\) 的函数。

对于具体安全的定义

A scheme is \((t, \varepsilon)\)-secure if any adversary running for time at most \(t\) succeeds in breaking the scheme with probability at most \(\varepsilon\).

在实际运用密码系统时往往需要一个具体的安全保障。

我们将 efficient adversaries 视为多项式时间随机算法(randomized algorithms running in time polynomial in \(n\))；将 small probabilities of success 视为不大于某一多项式的倒数(success probabilities smaller than any inverse polynomial in \(n\))，这样的概率成为可忽略的(negligible)。

PPT 表示 probabilistic polynomial-time。

对渐进安全进行定义：