流密码——使用块密码实现的流密码

作者: yuan1028 | 来源:发表于2021-02-10 11:05 被阅读0次

7.1 概述

流密码（Stream Cipher）是指一种可以处理一串字符的对称加密算法。理想中，字符长度可以是任意的，真实中的流密码有一定的长度限制，但通常对于正常需求来说已经足够大了。

7.2 使用块密码简单尝试

我们可以尝试用已有的工具来构建流密码。我们已经有了块密码，我们可以简单的将一个流划分成不同的块，然后加密每一个块。

image-20210208104027651.png

这种加密方式被称为ECB mode（Electronic Code Book Mode），这种方式下很多块密码算法都可以被用于流密码。不幸的是，随着电子系统的增长，安全法则也越来越严格。在ECB模式下，相同的块会被映射为相同的输出。

image-20210208104257467.png

在一开始，可能看起来并不是一个很严重的问题。如果块密码是安全的，攻击者并不能解密任何东西。通过将密文组织成块，攻击者只能看到一个密文块是在重复的，于此推断明文块也是在重复的。

现在已知的针对ECB模式的攻击有两种。

由于相同的明文块会得到相同的密文块，一个加密的图片就变的可视了。
攻击者可以通过与加密者交互来解密用ECB模式加密的信息。

加密流的视觉检查

我们模拟了块密码的不同块大小，并将它运用到一副图片中。然后我们就可以看到不同的加密后的图片。

因为一个相同的明文块会被映射为一个相同的密文块，这图片的大部分结构就被保留了下来。

可以看到使用更大的块大小，可以使加密的效果更好，但是从根本上来将，问题依然存在，在大部分块大小下，图片的微结构依然可视。更长远地看其中最小的块大小已经是很大了。对于没有压缩的图每个像素需要3原色的8位，一共24位来存储。由于AES的块大小仅有128位，（128/24）约每个块5个像素（图b）。AES是目前最主流的块密码。

看最后一副理想的加密图片，可以看出它像是一副有一些随机噪声的图片。要记住看起来像是随机噪声并不意味着被加密的信息也是这样，它只是表示我们无法通过加密后的图片获取任何有效信息。

image-20210208104956300.png

加密提示攻击（Encryption oracle attack）

前一节我们重点关注了攻击者如何调查使用了ECB加密的密文，这是一种只有密文（ciphertext-only）的被动的攻击。它是被动的是因为攻击者并没有任何的交互，而只是在实验密文。在这一节我们要介绍一种不同的主动的攻击，在这种场景里攻击者可以与他们的目标交互。本节接下来介绍攻击者如何利用主动攻击来解密使用ECB模式得到的密文。

在我们的例子中，oracle将会为攻击者执行一个特定的加密。给定数据A，oracle将会加密在其后加上后缀S后，将其用ECB模式加密。
$C=ECB(E_k,A||S)$

这个私密后缀S因系统而定。攻击者的目标是破解它。如果攻击者可以解密后缀，我们会惊奇地发现他也就可以解密其他信息。oracle看起来像是理论性的东西，实际上在实际中的应用也很多。一个简单的例子是用ECB模式加密的cookie，它的前缀是一个名字或者是e-mail，而这个是由攻击者可控的。

oracle的概念非常重要：攻击者无法自行计算C，因为他们不知道密钥k和私密后缀S。oracle的目标是保持私密性，但是我们将会看到攻击者如何通过复原后缀S。攻击者通过小心地挑选A来检查密文C。

在很多理论场景中假设攻击者可以访问这样的一个oracle。实际证明，很多软件也可以进行类似的操作。尽管攻击者不能够像精确地使用oracle一样控制真实的软件，攻击者也丝毫不会失落，时间是在他们那边的，攻击者只需被攻击的软件能给出他们想要的答案一次。这样系统就会有一部分消息是私密的，而另一部分消息会被攻击者影响，非常不幸的是，这就是ECB模式。

使用oracle解密一个块

攻击者以发送一个比块大小少一个字节的明文A来作为开始，这意味着被加密的块包含这些字节，以及S的第一个字节，我们称之为S0.攻击者记录密文块，这个时候还是不知道S0，但是他们现在指导了第一个加密块Ek(A||s0).也就是图里的CR1。

image-20210209092807712.png

接下来攻击者尝试一个完整大小的块，枚举最后一个字节的所有可能，最终他们将找到S0，因为他们之前记录CR1，只有枚举出相同的密文CR1，那么这一次枚举的值就是S0.

image-20210209093011686.png

然后攻击者会重复这个过程，这次明文使用比块大小少两个字节的明文A作为开始。oracle将会将A和后缀S的前两个字节s0s1，作为一个块来加密。攻击者记录该密文块CR2.由于攻击者已经得到了S0，只需要枚举最后一个字节s1的所有可能性，最终他们将得到匹配上相同的密文块CR2，得到S1的值。

攻击者只需要一直重复这个过程，直到解密整个S。这个最多需要p*b次尝试，其中p是一个字节的所有可能性（对于8位一个字节的情况，即2^8=256），b是块大小。这个远远优于直接进行暴力破解，直接暴力破解需要尝试所有的块，
$p*p...*p=p^b$

对于常用的16个字节的块大小（128位），暴力破解的复杂读位256^16,这是一个相当巨大的数字，通常认为不可直接暴力破解。但是ECB模式的加密提示攻击下，攻击者只需最多256*16=4096次尝试，一个非常可控的数字。

结论

真实世界中，块加密算法被用于各种系统中来加密大的数据。我们看到当使用ECB模式的时候，一个攻击者可以分析密文的重复情况，甚至当攻击者可以与加密系统（encryption oracle）交互时，还可以破解这个消息。

即使当我们使用一个理想中的拥有一些不切实际特性的块密码算法，比方说块大小是上千位，攻击者依然可以解密密文。真实世界中的块密码算法比我们理想的例子的限制还要更多，比方说只有一个很小的块大小。

在此我们不想讨论块密码的潜在缺陷，这个不是AES这一类块密码算法的问题，而是我们的ECB模式造成的，我们需要更好的模式。

7.3 块密码操作模式

一种更通用的做法是：使用特殊的构造方式来使用块密码。这个系统类似于流密码。这个构造方式通常被称为操作模式（mode of operations）。他们并不代表特定的块密码算法。

ECB模式，如7.2节所示，是最简单的模式。如上所属，ECB模式是不太有效的，还有很多其他的选择。

7.4 CBC模式

CBC模式是一种非常通用的将块密码链式使用的模式，它通常是将明文与前一个块的密文块进行异或后，再进行加密。这种情况下第一个明文块没有前一个密文块可以用来进行异或。这种情况下，我们选择IV，一个随机数在操作中来替代第一个密文块。IV（initialization vector）也出现在很多其他的算法里，一个IV需要不可预测，理论上需要完全的随机。他们不必要是私密的，通常情况下IV直接以明文的形式加在密文的前面。它必须是完全随机的，但是却不必是私密的，这听起来有点矛盾，这个重点是要求攻击者无法提前预知IV，之后我们将介绍一些针对可预知IV的攻击。

CBC模式的加密过程如下图（感觉这个图有些问题，在加密之前进行异或就可以了，E之后的异或是在干什么）

image-20210209095453067.png

（我自己画的加密过程图）

cbc encryption.png

解密过程如下图

image-20210209095535098.png

CBC模式不像ECB模式那样本身就是不安全的，但是tls1.0中的使用是有问题的，它最终导致了BEAST攻击，该攻击我们将在SSL/TLS部分详细介绍。CBC模式的一些缩减版本没有使用不可预见的IV，如使用前一个密码块的密文作为下一个消息的IV，不幸的是，攻击者已经可以对这些缩减版本进行攻击。

7.5 针对可预见IV的CBC模式的攻击

假设有一个数据库存储了用户的私密数据，例如身体检查数据、薪水、甚至是犯罪记录。为了保护这些数据，服务器使用固定的密钥的强块密码算法的CBC模式。我们假设服务器自身是安全的不会，不会通过任何途径造成密钥的泄露。

假设Mallory通过SQL注入攻击或者其他社交活动攻击，拿到了数据库的所有数据。目前一切依然是安全的，Mallory仅仅拥有密文数据，但是他没有密钥。

Mallory想要知道关于Alice的那条数据的内容，为了简单起见，假设该数据是一个密码块，这意味着Alice的密文数据包括一个IV和一个密文块。Mallory依然可以作为一个正常用户使用这个应用，也就是应用会加密Mallory的数据并将它写入到数据库中。假设Mallory可以预测服务器用来加密她信息的IV，比方说服务器可能所有的人都使用相同的IV，甚至就干脆使用的全零的IV。

Mallory可以利用Alice的IV_A,以及她自己预测的自己的IV_M来构造她的明文，她可以对Alice的数据进行猜测，假设数据是G，她可以让服务器加密
$P_M=IV_M⊕IV_A⊕G$
服务器会将该数据进行加密
$\begin{aligned} C_M&=E(k,IVM⊕PM)\\ &=E(k,IV_M⊕(IV_M⊕IV_A⊕G))\\ &=E(k,IV_A⊕G) \end{aligned}$

如果我们猜测的数据G是正确的，那么CM就会和Alice的密文块一样，那么Mallory也就知道Alice数据的明文，也就是Alice是否有犯罪记录或者是否有隐秘的疾病或者Alice其他的隐私数据。

由此可见，一定要让IV不可预测。在安全的系统里Alice和Mallory的数据不会使用相同的key进行加密。

7.6 针对CBC模式下，使用key作为IV的攻击

许多CBC系统将key的值设置成IV，这看起来是一个好主意：因为很多时候需要共享密钥，在这种情况下，性能会看起来比较好，因为发送者和接收者不需要再直接交流IV，他们已经提交知道了密钥（以及IV）；另外私钥也是不可预测的因为它是秘密的，如果它可以预测，攻击者就可以直接预测私钥了。通常情况下块加密的块大小通常是等于或者小于密钥长度的，所以密钥的大小已经足够了。

但是这种CBC的启动是不安全的。如果Alice发送了一条消息给Bob，Mallory可以在中间拦截到消息并且修改消息，然后她就可以通过挑选密文来尝试破解密钥。

Alice将她的明文P分解为三个块，P1P2P3然后用私钥k，使用CBC模式进行加密，假设她的IV和k相同。她得到了密文块C=C1C2C3，并将其发送给Bob。
在消息到达Bob之前，Mallory拦截了它。她将消息修改为C'=C1ZC1,其中Z是一个全0的区块。
Bob接收到消息C‘后，解密得到明文区块P'=P1'P2'P3':
$\begin{aligned} P_1'&=D(k,C1)⊕IV\\ &=D(k,C1)⊕k\\ &=P_1 \\ P_2'&=D(k,Z)C1\\ &=R\\ P_3'&=D(k,C1)⊕Z\\ &=D(k,C1)\\ &=P_1⊕IV \end{aligned}$

R是一个随机的块，它并不重要

此处假设，Mallory可以通过某种途径获取到Bob解密的内容。对于Mallory来说，她仅仅对第一个块(P1'=P1)和第三个块（P3'=P1⊕IV）感兴趣。将两者进行异或，她就可以得到(P1⊕IV)⊕P1=IV。然后由于IV就是密钥，所以Mallory仅仅只修改了一条消息就可以破解出key。

由此可见，不要使用密钥key作为IV。有一部分对CBC模式的误解就是认为私密的数据可以作为IV，因为它不可被预测。然而，私密对应的是不私密。通常对于非必要的情况不必使用私密的信息，精确来说因为它不必要时私密的，在算法过程中也会按照非私密的对待它，就像上例一样。

7.7 针对CBC模式的位翻转攻击

对于CBC模式一个有趣的攻击时位翻转攻击。在CBC位翻转攻击下，攻击者可以修改用CBC模式加密的密文，使得对于明文有一个特定的效果。这个看起来是一个奇怪的攻击，他们并不想解密任何信息，只是想要翻转明文中的部分位。后文中会看到当攻击者可以翻转明文中的一些位之后他实际上就能够使得明文和他想要的一致，这在现实系统中会引起非常严重的问题。

假设我们有一个CBC加密的密文。比方说cookie。拿到一个特定的块，可以翻转其中的一些位，这对明文来说会发生什么呢？

类似于疑惑操作，对于一串字符，假设为X，当X中的位为1的时候翻转相应的位，当这位为0时保持不变。

image-20210209145031676.png

当尝试解密翻转了一些位的密文时，可能会得到无意义的信息。CBC的解密方式：将块密码解密的信息异或上前一个密文块来产生最终的明文。假设现在输入的Ci被修改了，块密码解密的将会是一个随机的不相关的块，一般来讲是无意义的。通过和前一个密文块异或，它可能依然是无意义的。结果上来看得到的明文也是无意义的，如上图所示的Pi‘。

然而对于紧接着之后的块，对密文位的翻转，直接会导致明文跟着翻转了，这是因为在CBC模式下，密文块通过块密码解密后要异或上前一个密文块。而由于我们将密文块与X进行了异或，明文块Pi+1也和X异或了。结果是攻击者完全可以控制明文块Pi+1，因为他们可以任意翻转他们想要翻转的位。

乍看这可能没有什么大的问题，如果不知道下一个块的明文确实不会清楚翻转哪些位才能得到你想要明文。

为了强调下攻击者是如何在现实中进行攻击的，我们考虑一个使用cookie的网站，当我们注册了之后，用户名就会被放到cookie里。网站加密这个cookie然后将它发送到浏览器。下一次访问网站的时候，它将会使用加密的cookie，网站对其进行解密，然后就知道用户是谁了。

一个攻击者往往可以控制部分要被加密的明文。在这个例子里，用户名会是cookie明文的一部分。假设网站可以让你注册任意你想要的名字，那么你可以注册一个用户名，然后后面跟上一长串的Z。服务器对该cookie进行加密，然后将这一大堆的Z的字符加密之后返回给用户。明文的部分变换有可能就是这一串Z的一部分。

一个攻击者可能想要在解密后的明文中看到，例如“;admin=1;”为了展示出哪些位需要翻转，只需要将这些填充的字符（ZZZ）与目标位进行异或。因为相同的值进行异或可以相互抵消，填充串会被抵消掉，最后目标串会保留下来。攻击者会使得最后的明文为;admin=1;
$\begin{aligned} P_{i+1}'&=P_{i+1}⊕X\\ &=P_{i+1}⊕ZZZZZZZZ⊕;admin=1;\\ &=ZZZZZZZZ⊕ZZZZZZZZ⊕;admin=1;\\ &=;admin=1; \end{aligned}$
该攻击也揭示了一个很重要的密码学问题：加密是没有身份认证的。目前加密一条消息仅仅是让攻击者无法读到它，但是并不能阻止攻击者去修改他们想要修改的内容。这个问题将会在安全认证消息部分被解决。这部分会在后面介绍。目前只需要记住一个安全的密码系统需要有身份认证。

7.8 填充

目前为止，我们都是假设要加密的消息正好和我们的块大小匹配，不管是CBC模式还是ECB模式。这意味着消息大小都正好是块大小的倍数，对于典型的AES块密码，也就是16字节大小。当然真实世界中消息可能是任意长度的，所以我们需要对此进行适配，这个过程称之为填充（padding）。

以0为填充（或者其他填充字节）

一个办法是直接在明文后面填充特定的字节使其达到合适的长度。解密的时候解密出的明文再删掉后面的填充字节。该机制有一个明显的问题：没有办法发送以填充字节结尾的消息，会无法区分是用来做填充的，还是真实的消息内容。

PKCS#5/PKCS#7 填充

一个更好的也更通用的机制是使用PKCS#5/PKCS#7填充。PKCS#5，PKCS#7以及之后的其他填充方法基本都是同一思路。将需要填充的长度作为填充的内容，填充该次数。例如块大小为8字节，然后最后的块有3个字节12 34 45，填充之后的块为12 34 45 05 05 05 05 05

如果明文恰好是块大小的倍数，则需要填充整个块。否则接收者可能会将明文的最后一部分作为填充长度。例如上面的例子，当明文为12 34 45 05 05 05 05 05的时候，要在后面填充整个块，也就是 08 08 08 08 08 08 08 08，这样接收者就可以把最后一个块全部按照填充块考虑（完全填充，或者部分填充）。

7.9 CBC填充攻击

在7.7中可以看到位翻转是想要通过获得指定的解密后的内容来欺骗接收者。

如7.8中提到的CBC模式需要对消息进行填充已到达块大小的倍数。如果填充是不正确的，接收者会拒绝消息，并返回填充无效的错误。可以利用这一个关于填充的小小的信息来迭代地解密整条消息。

攻击者通过尝试所有拥有有效填充的明文块，一次处理一个密文块。这样也就知道了在块密码下密文块的明文内容。仅凭这一点填充是否有效信息，就可以迭代和有效地地进行解密。

CBC填充攻击不是要真的攻击给定消息的填充，而是要构造填充内容来解密消息。

只需要满足两个条件，即可达到攻击者的目的

需要解密的目标密文
一个填充提示：一个函数获取到密文后会告诉攻击者填充是否正确

和ECB的加密提示类似，填充提示看起来不像真实情况的假设。事实上很长一段时间，大多数系统都不尝试隐藏填充有效与否。

本章假设填充使用的是PKCS#5/PKCS#7填充，因为这是目前最通用的填充方式。该种攻击方式对于其他形式的填充，只需要简单修改即可。

解密第一个字节

攻击者将会使用任意字节填充一个块R=r1r2...rb.，从密文中挑选想要解密的目标块Ci。攻击者可以通过询问填充提示来确定R||Ci是否是有效的填充。统计显示，这样一个随机的明文通常不会是有效填充。如果单词尝试恰好是有效填充，则攻击者可以跳过下一步。

image-20210209170320566.png

接下来，攻击者尝试修改信息使其能够有有效的填充。他们并不能够直接修改明文的末尾字节：如果字节是01，那就已经是有效的填充了。为了修改明文块的最后一个字节，攻击者修改前一个加密块的最后一个字节。这一点类似于CBC的位翻转攻击。对于上述提到的R也就是修改R的最后一个字节Rb。

攻击者尝试最后一个字节的所有情况。最后填充提示会报告某些密文块R，解密后的R||Ci是有效的填充。

发现填充长度

假设提示已经告诉攻击者，对于我们挑选的R，明文R||Ci拥有有效的填充。由于我们是基于PKCS#5填充的，这也就意味着明文块Pi填充会以下面的串结尾：

01
02 02
03 03 03
...

第一个选项（01）和其他的一些类似，因为它仅仅有一个字节有特殊的值。攻击者修改这个字节所有的值，所以会撞到有01的时候，其他的有效填充不止需要一个字节为特定值，而是需要更多的字节。对于攻击者来说要保证一条消息是01的有效填充，只需要尝试字节的所有可能性即可。对于以02 02结尾的有效填充，必须要尝试两个字节的组合来使得明文最后两个位置为02.

为了成功的解密消息，尝试找出一个有效的填充。可以通过修改左侧起始的Pi使得有效填充变成无效填充来确定填充的长度。和其他攻击一样，通过修改选定的块R来修改字节Pi。只要填充被打破了，就可以确定填充了多少个字节。因为使用的是PKCS#5填充，这个时候我们也就知道了填充字节是什么。

为了强调这一点，来举一个例子。假设成功地找到了一个块R使得R||Ci对应的明文是有效填充。假设填充是03 03 03，通常情况下，攻击者不知道这一点，关键是找到这个填充的方法。假设块大小是8字节，我们知道（攻击者不知道）Pi是
$p_0p_1p_2p_3p_4030303$
在这个公式里p0是某个明文字节。他们的真实值并不重要，唯一有关的事情是它们不是填充的一部分。当我们修改了R的第一个字节后，Pi会发生变化，这个时候p0变成了p0':
$p_0'p_1p_2p_3p_4030303$
可以看出这个改变并不会影响填充的有效性。然后依次改变p1，p2，p3和p4，继续修改这些字节，最终会遇到填充的部分，这个例子中，假设我们修改后03变成了02，Pi现在变成了：
$p_0'p_1'p_2'p_3'p_4'020303$
而02 03 03不是有效的PKCS#5填充，服务器将会拒绝这条消息。这个时候我们知道修改的是第六个字节，打破了填充。这也就意味着第六个字节是填充开始的位置。由于块大小是8个字节，填充包含了第六个字节，第七个字节和第八个字节。所以填充长度为3个字节，也就是填充为 03 03 03.

一个聪明的攻击者会最小化提示提问的次数，通常较长的有效的填充是很稀少的。所以不从块的开始进行变更而是从倒数第二个开始。这个的优点是对于较短的填充，可以很快地发现。例如如果填充是01，攻击者修改倒数第二给字节，只需要一次提问就可以发现填充是什么。如果倒数第二个填充没有影响填充的有效性，那么这个填充一定是01.如果填充无效了，说明填充至少是02 02。这种情况需要继续修改倒数第三个，如果填充有效，则填充为02 02，如果无效，则填充至少是03 03 03.这个过程不断重复，直到找到正确的长度。一个实现上的一点小技巧，你可以修改同个块的不止一个字节，然后等待提示填充失效。这个可能看起来有些迷惑，但是会更快捷。

下面的部分，我们假设填充是01，因为这个是最常见的例子。攻击者并不是要根据填充长度改变数据。如果猜到了更多的填充，这个只是意味着剩下需要手动猜测的字节更少而已。

解密一个字节

假如攻击者已经成功解密了密文的最后一个字节。事实上在有效的填充上我们可以解锁很多字节。在此仅假设最差的情形，只有一个字节。那么攻击者是如何解密密文块Ci的最后一个字节的呢（D（Ci）[b]）,我们知道它与rb异或的结果是01
$D(C_i)[b]⊕r_b=01$
所以
$D(C_i)[b]=01⊕r_b$
攻击者现在成功破解了密文块的最后一个字节。

解密其他字节

接下来攻击者会继续解密下一个字节，因为已经知道最后一个字节目前的明文是01
$D(C_i)[b]⊕r_b=01$
现在我们需要让它变成02，用来产生另一种有效的填充，02 02。为了做到这一点，只需要在现在的rb上异或01，这样可以将现在的01抵消，然后再异或上02，我们就可以得到02了。
$\begin{aligned} D(C_i)[b]⊕r_b⊕01⊕02&=01⊕01⊕02\\ &=02 \end{aligned}$
所以为了在最后一个位置产生02，攻击者需要将rb替换为
$r_b'=r_b⊕01⊕02$
接下来只需要尝试倒数第二位的所有字节，直到产生有效的填充。由于我们已经知道最后一位的明文一定是02，那么有效填充一定是倒数第二位也是02.使用同样的计算，攻击者可以知道倒数第二位的明文。
$D(C_i)[b-1]⊕r_{b-1}=02$
即
$D(C_i)[b-1]=02⊕r_{b-1}$

然后只需要重复这一过程，将倒数两个字节都修改为03 03，然后枚举倒数第三个字节的所有可能性直到生成有效的填充。只要重复这个过程，攻击者就可以破解整个密文块，然后针对不同的密文块操作，意味着攻击者可以读取到整条消息。

这个攻击是非常不易察觉和很难以修复的。所以首先消息除了加密应该是有身份认证的。这样修改了的消息就会被拒绝。然而很多系统会在身份认证之前先解密消息，有关于填充是否有效的信息已经被泄漏了。该部分将会在身份认证部分讨论。

你可能觉得只需要去除掉非法填充的提示消息，判断该消息是非法的但是不告诉用户为什么是非法的就可以。这个通常出现在部分在身份认证之前进行解密的系统，这些系统通常拒绝非法填充的消息会比拒绝有效填充的消息要快一点点。之后他们不需要进行身份认证，如果填充是无效的消息不可能是有效的。攻击者通过时间上的不同获取泄漏的信息，该点被称之为“时间攻击”，这是一种特别的侧面的攻击，会在之后章节介绍。

通过获取到接收者拒绝消息的时间差异，可以判断出接收者是否进行了身份认证这一步。这也就提示了攻击者填充是否是有效的，攻击者就可以利用本节的方法来完成攻击。

这也告诉我们，绝对不要设计自己的密码系统。为了避免上述时间攻击的一个通用做法是先进行身份认证然后再进行解密。我们会在之后的消息认证章节进行详细介绍。