随机真的是好事情吗？密文分组链接模式的碰撞攻击——理论与实践
前言
好久没给朋友们带来黑客大会视频的分析了。我自己在空余时间仍然在做黑客大会的翻译工作，不过这一段时间听译的内容大多数都是工具的介绍，写起来感觉有些空（不过，如果我遇到有意思的工具，我还是会和大家分享的）。然而，前天发生的一件事情让我下定决心一定要为将要上线的一个DEF CON 23视频撰写一篇专栏。
事情的起因是这样的，在前天中午我与实验室新来的一位老师闲聊的时候，他提到业内有个学者的博客很不错，可以时常关注一下。一听这个人叫Matthew Green，我就来了兴趣。安全圈子里面的人可能不太知道这个人，但这个人在理论圈子里面可是非常知名的。理论圈子里面有3个最顶级的安全会议，分别叫做Usenix Security Symposium（Usenix Security）、ACM Conference on Computer and Communications Security（ACM CCS）、IEEE Symposium on Security and Privacy（S & P）。基本上国内研究机构每年也没几个人能在这3个会议上发表论文。这3个会议只要中了一篇，基本上就是各种基金项目信手拈来的程度。然而，从2010年开始，Matthew Green这个人每年都会在这3个会议上发表论文！更恐怖的是，这个人只是Johns Hopkins大学的一个普通的Assistant Professor而已。哎，只能说理论安全圈，国内外的研究水平还是有一定差距的…不过，Matthew Green本身是一个很喜欢Coding的人，尤其是喜欢做密码学工程相关的工作。他对理论分析倒并不是那么热衷，这没准也是他一直没沿着学术圈子继续往上升的原因吧。
言归正传，Matthew Green的博客叫做《[url=http://webcache.googleusercontent.com/search?q=cache:https://blog.cryptographyengineering.com/]A Few Thoughts on Cryptographic Engineering[/url]》（似乎需要翻墙，而且时常会出现链接挂掉的情况）。他的博客通俗易懂，有大家之范，有兴趣的朋友们可以关注一下。我们今天要谈到的就是他在2016年8月24日（没错，就是一周之前）发表的一篇博客《Attack of the week: 64-bit ciphers in TLS》。因为有的朋友可能打不开链接，我在这里贴出这篇博客的第一部分，大家可以感受一下：
A few months ago it was starting to seem like you couldn’t go a week without a new attack on TLS. In that context, this summer has been a blessed relief. Sadly, it looks like our vacation is over, and it’s time to go back to school.
Today brings the news that Karthikeyan Bhargavan and Gaëtan Leurent out of INRIA have a new paper that demonstrates a practical attack on legacy ciphersuites in TLS (it’s called “Sweet32”). What they show is that ciphersuites that use 64-bit blocklength ciphers — notably 3DES — are vulnerable to plaintext recovery attacks that work even if the attacker cannot recover the encryption key.
While the principles behind this attack are well known, there’s always a difference between attacks in principle and attacks in practice. What this paper shows is that we really need to start paying attention to the practice.
Karthikeyan Bhargavan和Gaëtan Leurent的这个工作已经被上面3个最顶级安全会议之一，ACM CCS 2016录用。今年，ACM CCS 2016将在奥地利的维也纳召开，时间是2016年10月24日至2016年10月28日（ACM CCS 2016）。两位作者专门构建了一个网站：Sweet32: Birthday attacks on 64-bit block ciphers in TLS and OpenVPN，提前将攻击原理、代码、分析等放在了网上。因此，我们有幸能提前2个月看到国际顶级学者们的最新研究成果，这也是一件值得庆贺的事情。
但是，当读完论文后我就傻眼了… 这个攻击的攻击原理是很简单的，之前也有人发现过。而公开这个问题的人，正是在DEF CON 23 – Crypto and Privacy Village上发表的讲座。而他们的讲座正是我的团队听译的… 他们是来自Fontbonne大学的Albert Carlson和Patrick Doherty。我不知道Karthikeyan Bhargavan和Gaëtan Leurent是否看过DEF CON 23的演讲，也不知道Albert Carlson和Patrick Doherty是否得知他们的攻击思想被来自另外机构的人完整实现。如果他们互相知道对方的成果，不知道会作何感想…
我想强调的是，这个攻击的原理很直观，但是如何正确利用这种攻击方式，两个大学的两组研究团队有着不一样的想法。而这不一样的想法导致他们分别在黑客大会和计算机理论大会上做相关的报告。这也引发了一个问题：安全理论有用吗？
讲座信息
何为密文分组链接模式的碰撞攻击
要讲起这个话题，我们得先来谈谈对称加密体制，或者说是单钥加密体制了。我在知乎上回答的绝大多数问题都是有关非对称加密体制，或者说是双钥加密体制的。不过，有关单钥加密体制的内容我在很早前已经在我的技术博客里面撰写了（因为后来我发现知乎平台分享知识的效果更好，所以就转战知乎专栏了）。相关分析和实现的内容链接为：Java密码学原型算法实现——第二部分：单钥加密算法。在这个攻击中，我们只需要关注单钥加密体制里面的分组加密算法。这里我需要引用这里面的一些描述。下述有关分组密码和加密模式讲解的插图来自于Silent Void的happyhippy博客：对称加密和分组加密中的四种模式(ECB、CBC、CFB、OFB)。觉得它博客里面的图还是非常清晰的，大家也可以直接看这位作者的描述。
分组密码将明文消息编码表示后的子串划分等长的组，各组分别在各子密钥的控制下变成等长的输出序列。最典型，现在仍然认为是安全的分组加密算法为AES。AES分组加密算法的流程如下图所示：
如果不特别说明，一般密码学初学者在使用分组加密算法时会使用所谓的电码本加密模式（ECB模式），也就是上图中的加密方法。这也是分组加密算法最简单、最直接的使用方法
为了保证加密结果一定可以被正确的密钥成功解密，对于对称加密算法我们有这样一个要求：如果加密时输入的明文和密钥是一样的，那么输出的密文也一定是一样的。ECB模式完美遵从了这个特性。
然而，这也带来了安全问题：如果在相同密钥下将一个消息加密两次，那么输出的密文也一定是相同的。在应用中，数据通常有部分可猜测的信息，例如薪水的数目就有一个可猜测的范围。如果明文消息是可猜测的，那么由确定性加密方案得到的密文就会使攻击者通过使用猜测的方法猜测出明文。因此，在大多数应用中不要使用ECB模式。在视频中，Carlson也讲到了ECB模式的这一个缺陷：
为了解决这个问题，人们提出了其他的加密方法。比较典型的加密方法是密文分组链接模式（CBC模式）、输出反馈模式（OFB模式）、密码反馈模式（CFB模式）、计数器模式（CTR模式）。我们今天要攻击的就是CBC模式。
CBC模式是用于一般数据加密的一个普通的分组密码加密模式。在这个模式中，第一个密文分组的计算需要一个特殊的明文，习惯上称之为初始向量（IV）。IV是一个随机的分组，每次会话加密时都要使用一个新的随机IV，IV无须保密，但一定是不可预知的。由于IV的随机性，IV将使得后续的密文分组都因为IV而随机化。由于IV需要公开，且第一个分组的加密结果是IV，因此CBC模式对于m个分组的明文将输出m+1个分组的密文。视频里面给出的CBC模式是这样的：
我也想吐槽，幻灯片上的图实在是太小了… 我们还是用Silent Void博客：对称加密和分组加密中的四种模式(ECB、CBC、CFB、OFB) 上的图吧，CBC模式实例如下图所示：
虽然CBC模式在理论界一直被别人诟病（最为经典的当属Padding Oracle Attack了，相关解释参见我的知乎答案：为什么说密文链接模式已经丧失安全性？ – 刘巍然-学酥的回答），但是在现实中可以使用的攻击方法也挺难找的。CBC模式真的不安全吗？实际上，密码学家们很早就发现一个问题：当在CBC模式中使用分组长度比较短（比如每个分组的长度是64bit）的对称加密算法时，方案在理论上是不安全的，因为可以存在一个所谓的碰撞攻击。
什么是碰撞攻击？我们首先粗略讲解一下什么是安全的加密算法。一个加密算法足够安全的要求是，加密结果看起来和随机数没什么区别。这个性质要求非常高了，如果加密结果跟随机数一模一样的话，相当于我们无法从密文中得到任何信息，这个加密也就是安全的了。然而，随机性在CBC模式下会带来一个很严重的问题：正因为随机，我们可以用很巧妙的概率学方法来分析，从而在随机中找到不随机。
我们考察下面的一个情况：一组密文是用相同的密钥key，在CBC模式加密输出的。如果输出的密文中有两个密文相等，会发生什么情况？举例来说，下图中两个红色部分的密文是相等的。
由于密文一样，密钥也一样，根据加密的一对一特性，我们可以直接得出：输入到加密算法的明文也一定是一样的，也就是说，上图“与或”运算的红色点是一样的。
然而，CBC模式输入的明文是什么呢？是真实的明文与上一个分组中密文的与或结果（上图黄色部分）。因此，假定两个密文分组c_i和c_j相等，这意味着： 
也就是说，我们能找到c_i和c_j前面一个分组中明文和密文的关系。
由于密文是通过不安全信道传输的，所有人都可能截获到密文。因此，如果我们知道其中一个明文是什么，我们就能够通过与或运算，得到另一个明文。
讲到这里，有的朋友不开心了… 输出都是随机的，密文中出现碰撞情况的概率太低了吧… 实际上概率一点都不低。朋友们还记得生日攻击吗？看看这个答案吧：你认为最反直觉的数学定理是什么？ – 知乎用户的回答。
多少个人中可以找到2个生日在同一天的人？
许多人以为要使至少有一个重复的概率大于0.5，那么大约应有100人，事实上只要23人。
在单钥加密中，我们也能发现相同的规律。
理论分析（有点数学，可忽略）
放在分组加密算法中，假设加密算法中每n比特分成一组，那么密文输出一共有N=2^n种可能。假设我们得到了2^d个密文分组，那么发生碰撞的概率为：
实际分析：如何实现碰撞攻击——CCS 2016篇
在实际网络中，这种攻击的实施具有哪些要求呢？Green列举了这些要求：
总结
总的来说，针对64 bit分组长度、CBC加密模式的碰撞攻击条件在真实网络环境下仍然比较苛刻。但这也说明，随着计算机计算能力的不断提升，不仅是暴力破解的难度会逐渐降低，通过其他概率算法，也会从侧面对一些经典加密算法实现攻击。
在文章的最后我想问大家一个问题：这种攻击的成功，标志着分组长度过短的加密算法在哪个安全模型下（选择密文攻击、选择明文攻击、静态攻击）是不安全的呢？或者说，在什么安全常数下是不安全的呢？（有关安全常数的解释，参见：密码体制中的安全参数k到底是个什么？ – 信息安全和密码学）
- 原始视频：DEF CON 23 – Crypto and Privacy Village – Carlson and Doherty – Breaking CBC。
- YouTube链接：https://www.youtube.com/watch?v=v0IsYNDMV7A
- 翻译：ScalersTalk成长会听力小组成员Myra
- 校对、压制：@刘巍然-学酥
- 时间轴：@吴诗湄
何为密文分组链接模式的碰撞攻击
要讲起这个话题，我们得先来谈谈对称加密体制，或者说是单钥加密体制了。我在知乎上回答的绝大多数问题都是有关非对称加密体制，或者说是双钥加密体制的。不过，有关单钥加密体制的内容我在很早前已经在我的技术博客里面撰写了（因为后来我发现知乎平台分享知识的效果更好，所以就转战知乎专栏了）。相关分析和实现的内容链接为：Java密码学原型算法实现——第二部分：单钥加密算法。在这个攻击中，我们只需要关注单钥加密体制里面的分组加密算法。这里我需要引用这里面的一些描述。下述有关分组密码和加密模式讲解的插图来自于Silent Void的happyhippy博客：对称加密和分组加密中的四种模式(ECB、CBC、CFB、OFB)。觉得它博客里面的图还是非常清晰的，大家也可以直接看这位作者的描述。
分组密码将明文消息编码表示后的子串划分等长的组，各组分别在各子密钥的控制下变成等长的输出序列。最典型，现在仍然认为是安全的分组加密算法为AES。AES分组加密算法的流程如下图所示：
如果不特别说明，一般密码学初学者在使用分组加密算法时会使用所谓的电码本加密模式（ECB模式），也就是上图中的加密方法。这也是分组加密算法最简单、最直接的使用方法
为了保证加密结果一定可以被正确的密钥成功解密，对于对称加密算法我们有这样一个要求：如果加密时输入的明文和密钥是一样的，那么输出的密文也一定是一样的。ECB模式完美遵从了这个特性。
然而，这也带来了安全问题：如果在相同密钥下将一个消息加密两次，那么输出的密文也一定是相同的。在应用中，数据通常有部分可猜测的信息，例如薪水的数目就有一个可猜测的范围。如果明文消息是可猜测的，那么由确定性加密方案得到的密文就会使攻击者通过使用猜测的方法猜测出明文。因此，在大多数应用中不要使用ECB模式。在视频中，Carlson也讲到了ECB模式的这一个缺陷：
为了解决这个问题，人们提出了其他的加密方法。比较典型的加密方法是密文分组链接模式（CBC模式）、输出反馈模式（OFB模式）、密码反馈模式（CFB模式）、计数器模式（CTR模式）。我们今天要攻击的就是CBC模式。
CBC模式是用于一般数据加密的一个普通的分组密码加密模式。在这个模式中，第一个密文分组的计算需要一个特殊的明文，习惯上称之为初始向量（IV）。IV是一个随机的分组，每次会话加密时都要使用一个新的随机IV，IV无须保密，但一定是不可预知的。由于IV的随机性，IV将使得后续的密文分组都因为IV而随机化。由于IV需要公开，且第一个分组的加密结果是IV，因此CBC模式对于m个分组的明文将输出m+1个分组的密文。视频里面给出的CBC模式是这样的：
我也想吐槽，幻灯片上的图实在是太小了… 我们还是用Silent Void博客：对称加密和分组加密中的四种模式(ECB、CBC、CFB、OFB) 上的图吧，CBC模式实例如下图所示：
虽然CBC模式在理论界一直被别人诟病（最为经典的当属Padding Oracle Attack了，相关解释参见我的知乎答案：为什么说密文链接模式已经丧失安全性？ – 刘巍然-学酥的回答），但是在现实中可以使用的攻击方法也挺难找的。CBC模式真的不安全吗？实际上，密码学家们很早就发现一个问题：当在CBC模式中使用分组长度比较短（比如每个分组的长度是64bit）的对称加密算法时，方案在理论上是不安全的，因为可以存在一个所谓的碰撞攻击。
什么是碰撞攻击？我们首先粗略讲解一下什么是安全的加密算法。一个加密算法足够安全的要求是，加密结果看起来和随机数没什么区别。这个性质要求非常高了，如果加密结果跟随机数一模一样的话，相当于我们无法从密文中得到任何信息，这个加密也就是安全的了。然而，随机性在CBC模式下会带来一个很严重的问题：正因为随机，我们可以用很巧妙的概率学方法来分析，从而在随机中找到不随机。
我们考察下面的一个情况：一组密文是用相同的密钥key，在CBC模式加密输出的。如果输出的密文中有两个密文相等，会发生什么情况？举例来说，下图中两个红色部分的密文是相等的。
由于密文一样，密钥也一样，根据加密的一对一特性，我们可以直接得出：输入到加密算法的明文也一定是一样的，也就是说，上图“与或”运算的红色点是一样的。
然而，CBC模式输入的明文是什么呢？是真实的明文与上一个分组中密文的与或结果（上图黄色部分）。因此，假定两个密文分组c_i和c_j相等，这意味着： 也就是说，我们能找到c_i和c_j前面一个分组中明文和密文的关系。
由于密文是通过不安全信道传输的，所有人都可能截获到密文。因此，如果我们知道其中一个明文是什么，我们就能够通过与或运算，得到另一个明文。
讲到这里，有的朋友不开心了… 输出都是随机的，密文中出现碰撞情况的概率太低了吧… 实际上概率一点都不低。朋友们还记得生日攻击吗？看看这个答案吧：你认为最反直觉的数学定理是什么？ – 知乎用户的回答。
多少个人中可以找到2个生日在同一天的人？
许多人以为要使至少有一个重复的概率大于0.5，那么大约应有100人，事实上只要23人。
在单钥加密中，我们也能发现相同的规律。
理论分析（有点数学，可忽略）
放在分组加密算法中，假设加密算法中每n比特分成一组，那么密文输出一共有N=2^n种可能。假设我们得到了2^d个密文分组，那么发生碰撞的概率为：
实际分析：如何实现碰撞攻击——CCS 2016篇
在实际网络中，这种攻击的实施具有哪些要求呢？Green列举了这些要求：
- The client and server must negotiate a 64-bit cipher. This is a relatively rare occurrence, but can happen in cases where one of the two sides is using an out-of-date client. For example, stock Windows XP does not support any of the AES-based ciphersuites. Similarly, SSL3 connections may negotiate 3DES ciphersuites.
- The server and client must support long-lived TLS sessions, i.e., encrypting a great deal of data with the same key. Unfortunately, most web browsers place no limit on the length of an HTTPS session if Keep-Alive is used, provided that the server allows the session. The Sweet32 authors scanned and discovered that many servers (including IIS) will allow sessions long enough to run their attack. Across the Internet, the percentage of vulnerable servers is small (less than 1%), but includes some important sites.
- The client must encipher a great deal of known data, including a secret session cookie. This is generally achieved by running adversarial Javascript code in the browser, although it could be done using standard HTML as well.
- 强制建立一个64 bit分组加密算法CBC模式的链接。Karthikeyan Bhargavan和Gaëtan Leurent做了详细的调研，认真分析了现有网络中64 bit分组加密算法CBC模式的使用率，结论是这种方式的使用率是非常高的。他们甚至指出，TLS的标准中也写明这种使用方法是正确而安全的，推荐使用（If you negotiate 3DES with a 1024-bit RSA key exchange with a host whose certificate you have verified, you can expect to be that secure），参见论文第3章。这里就可以看出，两位学者工作是多么的扎实。
- 要求通信双方建立长时间的TLS链接。这也是可以实现并在实际中会发生的，比如发送数据量很大、服务器的链接一直不断开。
- 重复发送一个秘密信息，并且其他信息攻击者还都知道。这个是最难实现的，然而两位学者想到了一个非常巧妙的方法：撰写一个Javascript恶意链接，让客户端重复请求下载并显示一个图片。作者利用了Session Cookie的特性来实现这个场景。Session Cookie的目的是让服务器知道对方是验证通过的用户，这个Cookie是秘密的，但是是在链接建立后，通过安全链接发送给服务器的。而HTTP的其他请求都是恶意程序生成的。这样就实现了知道秘密位置，不知道秘密本身，其他密文所对应的明文攻击者都能获知的这一极端条件。
总结
总的来说，针对64 bit分组长度、CBC加密模式的碰撞攻击条件在真实网络环境下仍然比较苛刻。但这也说明，随着计算机计算能力的不断提升，不仅是暴力破解的难度会逐渐降低，通过其他概率算法，也会从侧面对一些经典加密算法实现攻击。
在文章的最后我想问大家一个问题：这种攻击的成功，标志着分组长度过短的加密算法在哪个安全模型下（选择密文攻击、选择明文攻击、静态攻击）是不安全的呢？或者说，在什么安全常数下是不安全的呢？（有关安全常数的解释，参见：密码体制中的安全参数k到底是个什么？ – 信息安全和密码学）关注公众号：拾黑（shiheibook）了解更多
[广告]赞助链接：
四季很好，只要有你，文娱排行榜：https://www.yaopaiming.com/
让资讯触达的更精准有趣：https://www.0xu.cn/
![何丹彤彤：私服终于上完啦[跪了]](https://imgs.knowsafe.com:8087/img/aideep/2021/7/5/44c07c078026a2538372f1a9b4b27e38.jpg?w=250)
i春秋
关注网络尖刀微信公众号
