BS Chap 5:Chosen Plaintext Attack

type

status

date

slug

summary

Introduction

多密钥和单密钥

在 Chap 3:Stream Ciphers 里，我们介绍过流密码的错误打开方式——Two Time Pad，也就是使用同一个 seed 去加密两个不一样的消息，这样的做法会带来很大的安全问题。而如果我们不使用同一个 seed，那就要一文件一密，当文件数量很多时，这会带来很大的空间开销问题。

因此，为了节省密钥存储带来的开销，我们需要考虑如何安全地使用同一密钥，加密不同信息。

选择明文攻击

选择明文攻击，是用来刻画攻击者获得任意明文对应的密文的能力。比如攻击者给 Alice 发送一封邮件，在 Alice 方加密这封邮件后，攻击者获取邮件的对应密文，而且这个行为是可重复的，攻击者可以得到多个已知的明文-密文对。

如果 Alice 使用同一个密钥加密不同消息，且用的是确定性加密算法，当遭遇选择明文攻击的时候，因为加密算法是确定的，一个明文只对应一个密文，一个密文也只可能对应一个明文。因此，如果攻击者手上有两个密文，那就马上能判定它们对应的明文是否相同，这显然违背 semantic secure 定义的初衷。

因此，当使用一个密钥加密不同消息时，确定性加密肯定是不够安全的，我们需要转向概率性加密。此外，为了描述一个 cipher 在面对选择明文攻击下的语义安全，引入 semantic secure against chosen plaintext attack。

Security against multi-key attacks

我们首先考虑，当 Alice 使用不同的、满足语义安全的 cipher 去加密不同消息时，是否能达到 “multi-key” 下的语义安全？以下给出对应的 attack game 定义。

Attack game（multi-key semantic secure）

对定义在上的 cipher ，定义 Experiment ，其中。

Experiment ：

对，攻击者构造等长消息对并发给挑战者，挑战者计算，并将发送给攻击者。

攻击者输出

设事件是攻击者在实验中输出1的概率，则攻击者攻击的优势为：

如果将实验改为 bit-guessing 版本，则对于，有：

Thm 5.1

如果满足语义安全，那么它也满足 multi-key semantic secure。

Proof：

假设有攻击 MSS 的攻击者，向 MSS attack game 的 challenger 问询了次，那么就可以构造一个攻击 SS 的攻击者来充当的 MSS challenger，并把自己的 challenge 藏在次问询中。

因此从直观上，我们可以大概感觉到（？）：

以下定义 hybrid game

hybird :

if then else

设是在 hybird game 中输出 1 的概率，显然有，因此：

接下来我们看如何将自己的 challenge 嵌进去：

首先挑一个

当进行第次问询时：

如果 :
如果 :
如果 : 将发给 Challenger，并将 Challenger 的返回发送给。

有：

注意——上式的是在玩两个 SS attack game 时对应的事件。

则有：

Semantic security against chosen plaintext attack

Definition of CPA security

对应定义在上的 cipher ，对于攻击者，定义以下两个实验：

Experiment ：

Challenger 选择

对，攻击者构造等长消息对并发给挑战者，挑战者计算，并将发送给攻击者。

攻击者输出

设事件是攻击者在实验中输出1的概率，则攻击者攻击的优势为：

用语义安全 cipher + PRF 构造 CPA secure cipher

构造方式

设是定义在上的 cipher，，我们的目标是用和一个 PRF 来构造一个满足 CPA secure 的 cipher 。

显然，一个确定性加密的 cipher 必定不是 CPA 安全的，因此我们需要引入一个随机变量，然后把扔到里面，这样的话如果的性质足够好，我们就可以利用来获得一个近似随机均匀分布的对称 key 。

则对于定义在上的 PRF ，定义在上的 cipher ：

对： output

对： output

Theorem 5.2

如果是一个 secure PRF，满足语言安全，的阶是 super-poly 的，那么上面构造的 cipher 满足 CPA 安全。

设是的 CPA 攻击者，和 Challenger 玩 CPA attack game 的 bit-guessing 版本，并且向 Challenger 发出了次问询；是的 SS 攻击者，和 Challenger 玩 SS attack game 的 bit-guessing 版本；是的攻击者。后面两个 attack game 定义可参见第三章。

则有：

转成 bit-guessing 形式则为：

证明直观

我们来看攻击者在每次问询中能直接获取到的。

从直观上来说，如果 PRF 的性质足够好，那么可以近似认为和是独立的，也就是攻击者得到并不会帮助他获得关于的信息。也就是说，如果 CPA 被攻破了，意味着攻击者掌握了关于的部分信息，也就能分清 PRF 输出和真随机数。

再来看，由于满足语义安全，所以攻击者也难以判断对应的是还是。又因为有次问询，因此需要乘上系数。

最后，如果第次问询和第次问询中，挑战者恰好选中，则有，key 的重用可能就会导致问题。比如说是满足语义安全的流密码，那么，，攻击者就可以得到，这时候只需要计算、，一对比就能知道的值。这种情况出现的概率为。

具体证明

设在中攻击者输出

Game 0 就是 CPA 的 bit-guessing 定义，因此有：

Game 0 到 Game 1 的转换满足 secure PRF 的定义，因此有：

Game 1 到 Game 2 的转换，由于在第9行的位置打了”补丁“，因此实际上是等价的，有：

如果不存在，那么 Game 2 和 Game 3 也是等价的，identical until something happens，因此有：

Game 3 就是 MSS 的 bit-guessing 定义，因此有：

结合上式，则有：

总结

这一章的主要内容有：

Security against multi-key attacks 是什么。

为什么需要刻画选择明文攻击（CPA）。

如何用语义安全 cipher + PRF 构造 CPA secure cipher，如何证明其安全性。