当你听到“密码学”这个词时，有些人会记住他们的 WiFi 密码、他们最喜欢的网站地址旁边的绿色挂锁，以及进入别人的电子邮件有多么困难。 其他人回忆起近年来的一系列漏洞，其中包括明显的缩写（DROWN、FREAK、POODLE...）、时尚的徽标和紧急更新浏览器的警告。
密码学涵盖了这一切，但是 本质 在另一个。 关键是简单和复杂之间只有一线之隔。 有些事情很容易做，但很难重新组合起来，比如打碎鸡蛋。 有些事情很容易做，但当一个小的、重要的、关键的部分丢失时，就很难恢复了：例如，当“关键部分”是钥匙时，打开一扇锁着的门。 密码学研究这些情况以及如何在实践中使用它们。
近年来，密码攻击的集合已经变成了一个充满华丽标志的动物园，充满了科学论文中的公式，并引起了一种普遍的阴暗感觉，即一切都被破坏了。 但事实上，许多攻击都是基于一些通用原则，无休无止的公式往往被归结为易于理解的想法。
在本系列文章中，我们将研究不同类型的加密攻击，重点介绍基本原理。 一般来说，并不完全按照这个顺序，但我们将介绍以下内容：
- 基本策略： 暴力破解、频率分析、插值、降级和跨协议。
- 品牌漏洞： 怪胎、犯罪、贵宾犬、溺水、堵塞。
- 高级策略： 预言机攻击（Vodenet 攻击、Kelsey 攻击）； 中间相遇方法、生日攻击、统计偏差（差分密码分析、积分密码分析等）。
- 侧信道攻击 及其近亲，故障分析方法。
- 对公钥密码学的攻击： 立方根、广播、相关消息、Coppersmith 攻击、Pohlig-Hellman 算法、数筛、Wiener 攻击、Bleichenbacher 攻击。
这篇特别的文章涵盖了凯尔西攻击之前的上述材料。
基本策略
以下攻击很简单，因为无需太多技术细节就可以几乎完全解释它们。 让我们用最简单的术语解释每种类型的攻击，而不涉及复杂的示例或高级用例。
其中一些攻击基本上已经过时，并且已经很多年没有被使用了。 其他人则是老前辈，在 21 世纪仍然经常偷偷摸摸毫无戒心的密码系统开发人员。 现代密码学时代可以被认为是随着 IBM DES 的出现而开始的，IBM DES 是第一个能够抵御此列表中所有攻击的密码。
简单的暴力破解
加密方案由两部分组成：1）加密函数，将消息（明文）与密钥组合，然后创建加密消息-密文； 2) 解密函数，采用密文和密钥并生成明文。 加密和解密都必须易于使用密钥进行计算，而没有密钥则难以计算。
假设我们看到密文并尝试在没有任何附加信息的情况下解密它（这称为仅密文攻击）。 如果我们以某种方式神奇地找到了正确的密钥，如果结果是合理的消息，我们可以轻松验证它确实是正确的。
请注意，这里有两个隐含的假设。 首先，我们知道如何进行解密，即密码系统是如何工作的。 这是讨论密码学时的标准假设。 对攻击者隐藏密码的实现细节似乎是一种额外的安全措施，但一旦攻击者发现这些细节，这种额外的安全性就会悄然且不可逆转地丧失。 这就是如何 ：系统落入敌人手中不应造成不便。
其次，我们假设正确的密钥是唯一能够实现合理解密的密钥。 这也是一个合理的假设； 如果密文比密钥长得多并且可读，则满足。 这通常是现实世界中发生的情况，除了 или （如果你不喜欢我们跳过了解释，请参阅定理 3.8 ).
鉴于上述情况，出现了一个策略：检查每个可能的键。 这被称为暴力破解，这种攻击最终肯定能对抗所有实用的密码。 例如，暴力破解就足够了 ，一种古老的密码，其中密钥是字母表中的一个字母，意味着超过 20 个可能的密钥。
不幸的是，对于密码分析人员来说，增加密钥大小可以很好地防御暴力破解。 随着密钥大小的增加，可能的密钥数量呈指数增长。 对于现代密钥大小，简单的暴力破解是完全不切实际的。 为了理解我们的意思，让我们以 2019 年中期已知最快的超级计算机为例： 来自IBM，峰值性能约为每秒1017次操作。 如今，典型的密钥长度为 128 位，这意味着 2128 种可能的组合。 为了搜索所有密钥，Summit 超级计算机将需要大约宇宙年龄 7800 倍的时间。
暴力是否应该被视为一种历史奇观？ 完全不是：它是密码分析手册中的必要成分。 密码很少会如此脆弱，以至于只能通过巧妙的攻击来破解，而无需使用某种程度的武力。 许多成功的黑客攻击首先使用算法方法削弱目标密码，然后进行暴力攻击。
频率分析
大多数文本都不是乱码。 例如，在英语文本中，有很多字母“e”和冠词“the”； 在二进制文件中，有许多零字节作为信息之间的填充。 频率分析是利用这一事实的任何攻击。
易受此攻击的密码的典型示例是简单替换密码。 在这个密码中，密钥是一个所有字母都被替换的表。 例如，“g”被“h”替代，“o”被j替代，因此单词“go”变成“hj”。 这个密码很难被暴力破解，因为有很多可能的查找表。 如果您对数学感兴趣，有效密钥长度约为 88 位：即
。 但频率分析通常可以很快完成工作。
考虑使用简单替换密码处理的以下密文：
XDYLY ALY 丑陋 XDWNKE WN DYAJYN ANF YALXD DGLAXWG XDAN ALY FLYAUX GR WN OGQL ZDWBGEGZDO
自 Y 经常出现，包括出现在很多单词的末尾，我们可以初步假设这是这个字母 e:
XDeLe Ale UGle XDWNKE WN DEAJEN ANF eALXD DGLAXWG XDAN Ale FLeAUX GR WN OGQL ZDWBGEGZDO
情侣 XD 在几个单词的开头重复。 特别是，组合 XDeLe 清楚地暗示了这个词 these или there，所以我们继续：
LE ALE UGLE THWNKE WN HEAJEN ANF EALTH DGLAtWG 比 ALE FLEAUt GR WN OGQL ZDWBGEGZDO
让我们进一步假设 L 对应于 r, A - a 等等。 这可能需要几次尝试，但与完整的暴力攻击相比，这种攻击可以立即恢复原始文本：
天地间的事物比你的哲学所梦想的还要多
对于某些人来说，解决此类“密码”是一项令人兴奋的爱好。
频率分析的思想比乍一看更基础。 它适用于更复杂的密码。 纵观历史，各种密码设计都试图使用“多字母替换”来对抗这种攻击。 这里，在加密过程中，字母替换表会以复杂但可预测的方式进行修改，具体取决于密钥。 所有这些密码都被认为很难一次性破解。 然而适度的频率分析最终击败了所有这些。
历史上最雄心勃勃、也可能是最著名的多字母密码是二战时期的恩尼格玛密码。 与之前的版本相比，它相对复杂，但经过艰苦的努力，英国密码分析学家利用频率分析破解了它。 当然，他们不可能发展出像上图这样优雅的攻击； 他们必须比较已知的明文和密文对（所谓的“明文攻击”），甚至促使 Enigma 用户加密某些消息并分析结果（“选择明文攻击”）。 但这并没有让战败的敌军和击沉的潜艇的命运变得好过一些。
在这次胜利之后，频率分析从密码分析的历史中消失了。 现代数字时代的密码设计用于处理位，而不是字母。 更重要的是，这些密码的设计是基于对后来被称为“黑暗”的理解。 ：任何人都可以创建自己无法破解的加密算法。 加密系统还不够 好像 困难：为了证明它的价值，它必须接受许多密码分析师无情的安全审查，他们将尽最大努力破解密码。
初步计算
以假设的普雷科姆高地市为例，人口为 200 万。 该市的每户家庭平均拥有价值 000 美元的贵重物品，但价值不超过 30 美元。Precom 的安全市场被 ACME Industries 垄断，该公司生产传奇的 Coyote™ 级门锁。 据专家分析，Coyote级锁只能通过非常复杂的假设机器来破解，制造该机器需要大约五年时间和000万美元的投资。 城市安全吗？
很可能不会。 最终，一个相当野心勃勃的罪犯将会出现。 他会这样推理：“是的，我会承担大量的前期费用。 五年的耐心等待，还有 50 美元。但当我完成后，我将能够获得 这座城市的所有财富。 如果我的策略正确，这项投资将获得数倍的回报。”
密码学也是如此。 针对特定密码的攻击需要经过严格的成本效益分析。 如果该比率有利，则攻击不会发生。 但是，同时针对许多潜在受害者的攻击几乎总是会得到回报，在这种情况下，最佳设计实践是假设它们从第一天就开始了。 我们本质上有墨菲定律的加密版本：“任何能够真正破坏系统的东西都会破坏系统。”
易受预计算攻击的密码系统的最简单示例是常量无密钥密码。 情况就是如此 ，它只是将字母表中的每个字母向前移动三个字母（该表是循环的，因此字母表中的最后一个字母被第三次加密）。 克希霍夫原则再次发挥作用：系统一旦被黑客入侵，它就永远被黑客入侵。
这个概念很简单。 即使是新手密码系统开发人员也可能会认识到威胁并做出相应的准备。 纵观密码学的发展，这种攻击对于大多数密码来说都是不合适的，从凯撒密码的第一个改进版本到多表密码的衰落。 随着现代密码学时代的到来，此类攻击才卷土重来。
这种回报归因于两个因素。 首先，足够复杂的密码系统终于出现，被黑客攻击后被利用的可能性并不明显。 其次，密码学变得如此广泛，以至于数以百万计的外行人每天都在决定在哪里以及重用密码学的哪些部分。 经过一段时间，专家们才意识到其中的风险并发出警报。
请记住预计算攻击：在文章的末尾，我们将查看两个现实生活中的密码示例，其中它发挥了重要作用。
插值
这是著名侦探夏洛克·福尔摩斯对倒霉的华生医生进行的插值攻击：
我立刻就猜到你是从阿富汗来的……我的思路是这样的：“这个人是医生类型，但他有军人气质。 所以，军医。 他刚从热带来到这里——他的脸是黑的，但这不是他皮肤的自然色调，因为他的手腕要白得多。 面容憔悴——显然，他受过很多苦，饱受病痛之苦。 他的左手受伤了——他握着它一动不动，而且有点不自然。 英国军医在热带哪里可以吃苦受伤呢？ 当然，是在阿富汗。” 整个思路没有花一秒钟的时间。 所以我说你来自阿富汗，你很惊讶。
福尔摩斯只能从每件证据中单独提取很少的信息。 他只有综合考虑之后才能得出结论。 插值攻击的工作原理类似，通过检查由同一密钥产生的已知明文和密文对。 从每一对中提取单独的观察结果，从而可以得出有关密钥的一般结论。 所有这些推论都是模糊的，似乎毫无用处，直到它们突然达到临界点并得出唯一可能的结论：无论多么令人难以置信，它一定是真的。 此后，要么密钥被泄露，要么解密过程变得如此精细以至于可以复制。
让我们用一个简单的例子来说明插值是如何工作的。 假设我们想阅读我们的敌人鲍勃的个人日记。 他使用从《密码学模拟》杂志的广告中了解到的简单密码系统对日记中的每个数字进行加密。 系统的工作原理如下：鲍勃选择两个他喜欢的数字： и 。 从现在开始，加密任意数字 ，它计算 。 例如，如果鲍勃选择 и ，然后是数字 将被加密为 .
假设 28 月 XNUMX 日，我们注意到鲍勃正在他的日记中乱涂乱画。 当他完成后，我们会悄悄地拿起它并观看最后一个条目：
日期：
235/520亲爱的日记，
今天是个好日子。 通过
64今天我和艾丽莎有个约会，她住在公寓里843。 我真的认为她可能是26!
由于我们非常认真地关注 Bob 的约会（在这种情况下我们都是 15 岁），因此了解日期以及 Alice 的地址至关重要。 幸运的是，我们注意到鲍勃的密码系统容易受到插值攻击。 我们可能不知道 и ，但我们知道今天的日期，所以我们有两个明文-密文对。 也就是说，我们知道 加密在 和 - 在 。 这就是我们要写下的内容：
由于我们已经 15 岁了，我们已经知道有两个未知数的两个方程组，在这种情况下足以找到 и 没有任何问题。 每个明文-密文对都对 Bob 的密钥施加约束，这两个约束一起足以完全恢复密钥。 在我们的例子中，答案是 и （在 以便 26 日记中的 对应于单词“the one”，即“同一个” - 大约。 车道）。
当然，插值攻击并不限于这些简单的例子。 每个简化为易于理解的数学对象和参数列表的密码系统都面临着插值攻击的风险——对象越容易理解，风险就越高。
新来者经常抱怨密码学是“将事物设计得尽可能丑陋的艺术”。 插值攻击可能是罪魁祸首。 鲍勃可以使用优雅的数学设计，也可以将他与爱丽丝的约会保密 - 但可惜的是，通常不能两者兼得。 当我们最终讨论公钥密码学的主题时，这一点将变得非常清楚。
跨协议/降级
在《惊天魔盗团》（2013）中，一群魔术师试图骗取腐败的保险巨头阿瑟·特雷斯勒的全部财产。 为了进入亚瑟的银行账户，魔术师必须提供他的用户名和密码，或者强迫他亲自出现在银行并参与该计划。
这两种选择都非常困难； 这些家伙习惯了在舞台上表演，而不是参与情报行动。 所以他们选择了第三种可能的选择：他们的同伙打电话给银行并假装是亚瑟。 银行会询问几个问题来验证身份，例如叔叔的名字和第一个宠物的名字； 我们的英雄提前 。 从此时起，出色的密码安全性不再重要。
（根据我们亲自核实核实的都市传说，密码学家伊莱·比汉姆曾经遇到一位坚持设置安全问题的银行柜员。当柜员询问他外祖母的名字时，比汉姆开始口述：“资本X，小y，三……”）。
在密码学中也是如此，如果并行使用两种密码协议来保护同一个资产，并且其中一种比另一种要弱得多。 由此产生的系统很容易受到跨协议攻击，即攻击较弱的协议，以便在不接触较强协议的情况下获得奖励。
在一些复杂的情况下，仅仅使用较弱的协议来联系服务器是不够的，还需要合法客户端的非自愿参与。 这可以使用所谓的降级攻击来组织。 为了理解这种攻击，我们假设我们的魔术师面临着比电影中更困难的任务。 假设一位银行员工（出纳员）和 Arthur 遇到了一些不可预见的情况，产生了以下对话：
防盗： 你好？ 这是阿瑟·特雷斯勒。 我想重置我的密码。
收银员： 伟大的。 请查看您的个人密码书，第 28 页，第 3 个单词。以下所有消息都将使用该特定单词作为密钥进行加密。 PQJGH。 LOTJNAM PGGY MXVRL ZZLQ SRIU HHNMLPPPV…
防盗： 嘿嘿嘿，等等，等等。 这真的有必要吗？ 就不能像正常人一样说话吗？
收银员： 我不建议这样做。
防盗： 我只是...听着，我今天过得很糟糕，好吗？ 我是 VIP 客户，我没有心情去挖掘这些愚蠢的密码书。
收银员： 美好的。 如果你坚持的话，特雷斯勒先生。 你想要什么？
防盗： 拜托，我想将我所有的钱捐给亚瑟·特雷斯勒国家受害者基金会。
（暂停）。
收银员： 现在清楚了吗。 对于大额交易，请提供您的 PIN。
防盗： 我的什么？
收银员： 根据您的个人要求，这种规模的交易需要 PIN 码才能进行大额交易。 该代码是在您开设帐户时提供给您的。
防盗：... 我失去了它。 这真的有必要吗？ 你就不能批准这笔交易吗？
收银员： 不。 对不起，特雷斯勒先生。 再次强调，这是您所要求的安全措施。 如果您愿意，我们可以将新的 PIN 码发送到您的邮箱。
我们的英雄推迟了手术。 他们窃听特雷斯勒的几笔大额交易，希望听到密码； 但每次在说出任何有趣的事情之前，谈话都会变成编码的胡言乱语。 终于，在一个晴朗的日子里，计划付诸实施。 他们耐心地等待特雷斯勒必须通过电话进行一笔大额交易的那一刻，他接通电话，然后……
特雷斯勒： 你好。 我想完成一项远程交易。
收银员： 伟大的。 请看一下您的个人密码书、页面...
（窃贼按下按钮；收银员的声音变成难以理解的噪音）。
收银员： - #@$#@$#*@$$@#* 将使用该单词作为密钥进行加密。 AAAYRR PLRQRZ MMNJK LOJBAN…
特雷斯勒： 抱歉，我不太明白。 再次？ 在哪一页？ 什么词？
收银员： 这是页面@#$@#*$)#*#@()#@$(#@*$(#@*)。
特雷斯勒： 什么？
收银员： 字数二十@$#@$#%#$。
特雷斯勒： 严重地！ 已经足够！ 你和你的安全协议就像是某种马戏团。 我知道你可以正常地跟我说话。
收银员： 我不推荐…
特雷斯勒： 我不建议你浪费我的时间。 在你解决电话线问题之前我不想再听到任何关于此事的消息。 我们能否完成这笔交易？
收银员：… 是的。 美好的。 你想要什么？
特雷斯勒： 我想向 Lord Business Investments 转账 20 美元，帐号...
收银员： 请等一分钟。 这是一件大事。 对于大额交易，请提供您的 PIN。
特雷斯勒： 什么？ 哦，正是如此。 1234.
这里是向下攻击。 较弱的协议“直接说话”被设想为 选项 在紧急情况下。 然而我们就在这里。
您可能想知道谁心智正常，会设计一个真正的“安全，除非另有要求”的系统，就像上面描述的那样。 但正如虚构的银行冒着风险留住不喜欢加密技术的客户一样，系统通常会倾向于对安全性漠不关心甚至完全敌视的要求。
这正是 2 年 SSLv1995 协议所发生的情况。 美国政府很早就开始将密码学视为一种最好远离国内外敌人的武器。 代码片段被单独批准从美国出口，通常的条件是算法被故意削弱。 Netscape 是最受欢迎的浏览器 Netscape Navigator 的开发商，仅通过本质上易受攻击的 2 位 RSA 密钥（以及 RC512 的 40 位）获得了 SSLv4 的许可。
到本世纪末，规则已经放宽，现代加密技术变得广泛可用。 然而，由于维持对任何遗留系统的支持的相同惯性，客户端和服务器多年来一直支持弱化的“导出”加密。 客户认为他们可能会遇到不支持其他任何功能的服务器。 服务器也做了同样的事情。 当然，SSL 协议规定，当有更好的协议可用时，客户端和服务器决不应该使用较弱的协议。 但同样的前提也适用于特雷斯勒和他的银行。
这一理论在 2015 年两次引人注目的攻击中得到了运用，这两次攻击动摇了 SSL 协议的安全性，这两次攻击均由 Microsoft 研究人员和 。 首先，FREAK 攻击的细节在 XNUMX 月份被披露，三个月后又发生了另一次名为 Logjam 的类似攻击，我们将在继续讨论公钥加密攻击时更详细地讨论该攻击。
漏洞 当研究人员分析 TLS 客户端/服务器实现并发现一个奇怪的错误时，（也称为“Smack TLS”）被曝光。 在这些实现中，如果客户端甚至不要求使用弱导出加密，但服务器仍然使用此类密钥进行响应，则客户端会说“哦，好吧”并切换到弱密码套件。
当时，出口加密技术被广泛认为已经过时且不受限制，因此这次攻击完全令人震惊，并影响了许多重要领域，包括白宫、国税局和国家安全局网站。 更糟糕的是，事实证明，许多易受攻击的服务器通过重复使用相同的密钥而不是为每个会话生成新密钥来优化性能。 这使得在降级协议后进行预计算攻击成为可能：破解一个密钥仍然相对昂贵（发布时为 100 美元和 12 小时），但攻击连接的实际成本却显着降低。 选择一次服务器密钥并破解从那一刻起所有后续连接的加密就足够了。
在我们继续之前，需要提及一种高级攻击……
神谕攻击
最著名的身份是跨平台加密消息应用程序 Signal 之父； 但我们个人喜欢他的一项鲜为人知的创新 - （密码学末日原理）。 稍微解释一下，我们可以这样说：“如果协议执行 任何 对来自潜在恶意源的消息执行加密操作，并根据结果采取不同的行为，这是注定的。” 或者用更尖锐的形式：“不要从敌人那里获取信息进行处理，如果必须这样做，那么至少不要显示结果。”
让我们先不考虑缓冲区溢出、命令注入等问题； 它们超出了本次讨论的范围。 由于协议的行为完全符合预期，违反“末日原则”会导致严重的密码学黑客攻击。
作为示例，我们采用具有易受攻击的替换密码的虚构设计，然后演示可能的攻击。 虽然我们已经看到了使用频率分析对替换密码进行的攻击，但这不仅仅是“破解同一密码的另一种方法”。 相反，预言机攻击是一项更现代的发明，适用于频率分析失败的许多情况，我们将在下一节中看到对此的演示。 这里选择简单密码只是为了使示例更清晰。
因此，爱丽丝和鲍勃使用简单的替换密码进行通信，使用的密钥只有他们自己知道。 他们对消息的长度非常严格：消息长度正好是 20 个字符。 因此，他们一致认为，如果有人想要发送较短的消息，他们应该在消息末尾添加一些虚拟文本，使其恰好为 20 个字符。 经过一番讨论，他们决定只接受以下虚拟文本： a, bb, ccc, dddd 因此，任何所需长度的虚拟文本都是已知的。
当Alice或Bob收到消息时，他们首先检查消息的长度是否正确（20个字符），并且后缀是否是正确的虚拟文本。 如果情况并非如此，那么它们会以适当的错误消息进行响应。 如果文本长度和虚拟文本正常，收件人将读取消息本身并发送加密的响应。
在攻击过程中，攻击者冒充鲍勃并向爱丽丝发送虚假消息。 这些消息完全是无稽之谈——攻击者没有密钥，因此无法伪造有意义的消息。 但由于该协议违反了厄运原则，攻击者仍然可以诱骗 Alice 泄露关键信息，如下所示。
防盗：
PREWF ZHJKL MMMN. LA爱丽丝： 无效的虚拟文本。
防盗：
PREWF ZHJKL MMMN. LB爱丽丝： 无效的虚拟文本。
防盗：
PREWF ZHJKL MMMN. LC爱丽丝：
ILCT? TLCT RUWO PUT KCAW CPS OWPOW!
窃贼不知道爱丽丝刚才说了什么，但注意到这个符号 C 必须匹配 a，因为爱丽丝接受了虚拟文本。
防盗：
REWF ZHJKL MMMN. LAA爱丽丝： 无效的虚拟文本。
防盗：
REWF ZHJKL MMMN. LBB爱丽丝： 无效的虚拟文本。
经过多次尝试...
防盗：
REWF ZHJKL MMMN. LGG爱丽丝： 无效的虚拟文本。
防盗：
REWF ZHJKL MMMN. LHH爱丽丝：
TLQO JWCRO FQAW SUY LCR C OWQXYJW. IW PWWR TU TCFA CHUYT TLQO JWFCTQUPOLQZ.
同样，攻击者不知道 Alice 刚才说什么，但注意到 H 必须匹配 b，因为 Alice 接受了虚拟文本。
依此类推，直到攻击者知道每个字符的含义。
乍一看，该方法类似于选择的明文攻击。 最后，攻击者选择了密文，服务器就乖乖地处理了。 使这些攻击在现实世界中可行的主要区别在于，攻击者不需要访问实际的记录——服务器响应，即使是像“无效的虚拟文本”这样无害的响应就足够了。
虽然这种特殊的攻击很有启发性，但不要太关注“虚拟文本”方案的细节、使用的特定密码系统或攻击者发送的消息的确切序列。 基本思想是爱丽丝如何根据明文的属性做出不同的反应，并且在不验证相应的密文实际上来自受信任方的情况下这样做。 因此，爱丽丝允许攻击者从她的答案中榨取秘密信息。
在这种情况下，有很多可以改变的地方。 爱丽丝对符号的反应，或者她行为的差异，甚至是使用的密码系统。 但原则将保持不变，整个攻击将以一种或另一种形式仍然可行。 这种攻击的基本实现帮助发现了几个安全漏洞，我们很快就会看到这些漏洞； 但首先需要学习一些理论教训。 如何在可以对真正的现代密码起作用的攻击中使用这个虚构的“爱丽丝脚本”？ 即使在理论上，这是否可能？
1998年，瑞士密码学家丹尼尔·布莱辛巴赫（Daniel Bleichenbacher）对这个问题给出了肯定的回答。 他演示了使用特定消息方案对广泛使用的公钥密码系统 RSA 进行的预言机攻击。 在某些 RSA 实现中，服务器根据明文是否与方案匹配来响应不同的错误消息； 这足以进行攻击。
四年后，即 2002 年，法国密码学家 Serge Vaudenay 演示了一种与上面的 Alice 场景中描述的几乎相同的神谕攻击 - 只不过他破解的是人们实际使用的一整类受人尊敬的现代密码，而不是虚构的密码。 特别是，Vaudenay 的攻击针对固定输入大小的密码（“块密码”），当它们用于所谓的“CBC 加密模式”并采用某种流行的填充方案时，基本上相当于 Alice 场景中的方案。
同样是在 2002 年，美国密码学家 John Kelsey（合著者） - 提出了对压缩消息然后加密消息的系统的各种预言机攻击。 其中最引人注目的是利用通常可以从密文的长度推断明文的原始长度这一事实的攻击。 理论上，这允许预言机攻击恢复部分原始明文。
下面我们提供了对 Vaudenay 和 Kelsey 攻击的更详细描述（当我们继续讨论公钥密码学的攻击时，我们将更详细地描述 Bleichenbacher 攻击）。 尽管我们尽了最大努力，文本还是变得有些技术性； 因此，如果以上内容对您来说足够了，请跳过接下来的两部分。
沃登的攻击
为了理解沃德奈攻击，我们首先需要更多地讨论分组密码和加密模式。 如前所述，“分组密码”是一种采用密钥和特定固定长度（“分组长度”）的输入并产生相同长度的加密分组的密码。 分组密码被广泛使用并且被认为相对安全。 现已退役的 DES 被认为是第一个现代密码，是一种分组密码。 如上所述，如今广泛使用的 AES 也是如此。
不幸的是，分组密码有一个明显的弱点。 典型的块大小为 128 位，即 16 个字符。 显然，现代密码学需要处理更大的输入数据，这就是加密模式发挥作用的地方。 加密模式本质上是一种破解：它是一种以某种方式应用仅接受特定大小的输入的分组密码到任意长度的输入的方法。
Vodene 的攻击主要针对流行的 CBC（密码块链）操作模式。 该攻击将底层分组密码视为一个神奇的、坚不可摧的黑匣子，并完全绕过了其安全性。
下图显示了 CBC 模式的工作原理：
带圆圈的加号表示 XOR（异或）运算。 例如，收到第二块密文：
- 通过对第二个明文块与第一个密文块执行异或运算。
- 使用密钥通过块密码对结果块进行加密。
由于 CBC 大量使用了二进制 XOR 运算，让我们花点时间回顾一下它的一些属性：
- 幂等性：
- 交换性：
- 关联性：
- 自可逆性：
- 字节大小：第n个字节 =（字节n ) （字节 n )
通常，这些属性意味着如果我们有一个涉及 XOR 运算和一个未知数的方程，则可以求解该方程。 例如，如果我们知道 与未知的 和著名的 и ，那么我们可以依靠上面提到的属性来求解方程 。 通过在方程两边应用 XOR ，我们得到 。 这一切很快就会变得非常重要。
我们的 Alice 场景和 Vaudenay 的攻击之间有两个细微差别和一个主要差别。 两个小问题：
- 在脚本中，爱丽丝期望明文以字符结尾
a,bb,ccc等等。 在 Wodene 攻击中，受害者反而期望明文以 N 字节结束 N 次（即，十六进制 01 或 02 02，或 03 03 03，等等）。 这纯粹是外观上的差异。 - 在 Alice 场景中，很容易通过响应“错误的虚拟文本”来判断 Alice 是否接受了消息。 在Vodene的攻击中，需要更多的分析，受害者这边的精确实施很重要； 但为了简洁起见，我们假设这种分析仍然是可能的。
主要区别：
- 由于我们没有使用相同的密码系统，攻击者控制的密文字节和秘密（密钥和明文）之间的关系显然会有所不同。 因此，攻击者在创建密文和解释服务器响应时必须使用不同的策略。
这个主要区别是理解 Vaudenay 攻击的最后一块拼图，所以让我们花点时间思考一下为什么以及如何对 CBC 进行预言机攻击。
假设我们得到了 247 个块的 CBC 密文，并且我们想要解密它。 我们可以向服务器发送虚假消息，就像我们之前可以向 Alice 发送虚假消息一样。 服务器将为我们解密消息，但不会显示解密结果 - 相反，与 Alice 一样，服务器将仅报告一位信息：明文是否具有有效的填充。
考虑在爱丽丝的场景中，我们有以下关系：
$$显示$$文本{SIMPLE_SUBSTITUTION}(文本{密文},文本{密钥}) = 文本{明文}$$显示$$
我们称之为“爱丽丝方程”。 我们控制了密文； 服务器（Alice）泄露了有关收到的明文的模糊信息； 这使我们能够推断出有关最后一个因素的信息——关键。 以此类推，如果我们能找到CBC脚本的这样一个连接，我们也许也能从那里提取一些秘密信息。
幸运的是，确实存在我们可以利用的关系。 考虑解密分组密码的最终调用的输出，并将该输出表示为 。 我们还表示明文块 和密文块 。 再看一下 CBC 图并注意会发生什么：
我们称之为“CBC 方程”。
在爱丽丝的场景中，通过监视密文并观察相应的明文泄漏，我们能够发起攻击，恢复等式中的第三项——密钥。 在CBC场景中，我们还监控密文并观察相应明文的信息泄露情况。 如果类比成立，我们可以获得以下信息： .
假设我们真的恢复了 ， 然后怎样呢？ 好吧，那么我们可以一次打印整个最后一个明文块（），只需输入 （我们有）和
获得 代入 CBC 方程。
既然我们对总体进攻计划持乐观态度，那么现在是时候制定细节了。 请注意明文信息在服务器上是如何泄露的。 在 Alice 的脚本中，发生泄漏是因为如果 $inline$text{SIMPLE_SUBSTITUTION}(text{ciphertext},text{key})$inline$ 以该行结尾，Alice 只会响应正确的消息 a （ bb等等，但这些条件被偶然触发的机会很小）。 与 CBC 类似，服务器接受填充当且仅当 以十六进制结尾 01。 所以让我们尝试同样的技巧：用我们自己的假值发送假密文 直到服务器接受填充。
当服务器接受我们的假消息之一的填充时，这意味着：
现在我们使用字节字节异或属性：
我们知道第一项和第三项。 我们已经看到，这使我们能够恢复剩余的项——最后一个字节 :
这还通过 CBC 方程和逐字节属性为我们提供了最终明文块的最后一个字节。
我们可以就此打住，并对我们已经对理论上强大的密码进行了攻击感到满意。 但事实上我们可以做更多的事情：我们实际上可以恢复所有文本。 这需要一个 Alice 原始脚本中没有的技巧，也不是预言机攻击所必需的，但它仍然值得学习。
要理解它，首先注意输出最后一个字节的正确值的结果是 我们有一个新的能力。 现在，在伪造密文时，我们可以操纵相应明文的最后一个字节。 同样，这与 CBC 方程和逐字节属性有关：
既然我们现在知道了第二项，我们就可以利用对第一项的控制来控制第三项。 我们简单计算一下：
我们以前不能这样做，因为我们还没有最后一个字节 .
这对我们有什么帮助？ 假设我们现在创建所有密文，使得在相应的明文中最后一个字节等于 02。 如果明文以以下内容结尾，服务器现在仅接受填充 02 02。 由于我们更正了最后一个字节，因此只有当明文的倒数第二个字节也是 02 时才会发生这种情况。我们不断发送伪造的密文块，更改倒数第二个字节，直到服务器接受其中一个字节的填充。 此时我们得到：
我们恢复倒数第二个字节 就像上次恢复一样。 我们本着同样的精神继续：我们将明文的最后两个字节更正为 03 03，我们对倒数第三个字节重复此攻击，依此类推，最终完全恢复 .
那么文本的其余部分呢？ 请注意该值 实际上是$inline$text{BLOCK_DECRYPT}(text{key},C_{247})$inline$。 我们可以放置任何其他块来代替 ，攻击仍然会成功。 事实上，我们可以要求服务器对任何数据执行$inline$text{BLOCK_DECRYPT}$inline$。 此时，游戏结束了 - 我们可以解密任何密文（再看一下 CBC 解密图即可看到这一点；并注意 IV 是公开的）。
这种特殊的方法在我们后面会遇到的预言机攻击中起到了至关重要的作用。
凯尔西的进攻
我们的志趣相投的约翰·凯尔西（John Kelsey）阐述了许多可能的攻击背后的原理，而不仅仅是针对特定密码的特定攻击的细节。 他的 是对加密压缩数据可能的攻击的研究。 您是否认为加密前压缩数据的信息不足以进行攻击？ 事实证明这就足够了。
这一令人惊讶的结果归因于两个原则。 首先，明文的长度和密文的长度有很强的相关性； 对于许多密码来说完全相等。 其次，在进行压缩时，压缩消息的长度与明文的“嘈杂”程度，即非重复字符的比例（专业术语是“高熵”）之间也存在很强的相关性。 ）。
要了解该原理的实际应用，请考虑两个明文：
明文1：
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA明文2：
ATVXCAGTRSVPTVVULSJQHGEYCMQPCRQBGCYIXCFJGJ
我们假设两个明文都经过压缩然后加密。 您会得到两个密文，并且必须猜测哪个密文与哪个明文匹配：
密文1：
PVOVEYBPJDPVANEAWVGCIUWAABCIYIKOOURMYDTA密文2：
DWKJZXYU
答案很明确。 明文中，只有明文1可以被压缩成长度微薄的第二个密文。 我们在不了解压缩算法、加密密钥甚至密码本身的情况下就解决了这个问题。 与可能的加密攻击的层次结构相比，这有点疯狂。
凯尔西进一步指出，在某些异常情况下，这一原理也可以用来进行预言机攻击。 特别是，它描述了如果攻击者可以强制服务器加密表单数据（明文后跟），他将如何恢复秘密明文 当他掌控一切的时候 并可以以某种方式检查加密结果的长度。
同样，与其他预言机攻击一样，我们有以下关系：
再次，我们控制一项（），我们看到有关另一个成员（密文）的少量信息泄漏，并尝试恢复最后一个成员（明文）。 尽管有这样的类比，但与我们见过的其他预言机攻击相比，这种情况有些不寻常。
为了说明这种攻击如何发挥作用，让我们使用我们刚刚提出的虚构压缩方案：TOYZIP。 它查找文本中先前出现过的文本行，并用三个占位符字节替换它们，这三个占位符字节指示在哪里可以找到该行的较早实例以及它在那里出现的次数。 例如，该行 helloworldhello 可以压缩成 helloworld[00][00][05] 与原来的 13 个字节相比，增加了 15 个字节。
假设攻击者试图恢复表单的明文 password=...，其中密码本身未知。 根据凯尔西的攻击模型，攻击者可以要求服务器压缩然后加密表单消息（明文后跟 ）哪里 - 自由文本。 当服务器完成工作后，它会报告结果的长度。 攻击过程是这样的：
防盗： 请压缩并加密明文，不要进行任何填充。
服务器： 结果长度14。
防盗： 请对附加的明文进行压缩和加密
password=a.服务器： 结果长度18。
破解者注意到：[原来的14]+[替换的三个字节 password=] + a
防盗： 请对添加的明文进行压缩和加密
password=b.服务器： 结果长度18。
防盗： 请对添加的明文进行压缩和加密
password=с.服务器： 结果长度17。
破解者注意到：[原来的14]+[替换的三个字节 password=c]。 这假设原始明文包含字符串 password=c。 即密码以字母开头 c
防盗： 请对添加的明文进行压缩和加密
password=сa.服务器： 结果长度18。
破解者注意到：[原来的14]+[替换的三个字节 password=с] + a
防盗： 请对添加的明文进行压缩和加密
password=сb.服务器： 结果长度18。
（… 一段时间之后…）
防盗： 请对添加的明文进行压缩和加密
password=со.服务器： 结果长度17。
破解者注意到：[原来的14]+[替换的三个字节 password=co]。 使用相同的逻辑，攻击者得出结论，密码以字母开头 co
依此类推，直到整个密码恢复。
读者可能会认为这纯粹是学术练习，并且这种攻击场景在现实世界中永远不会出现。 唉，我们很快就会看到，最好不要放弃密码学。
品牌漏洞：CRIME、POODLE、DROWN
最后，在详细研究理论后，我们可以看到这些技术如何应用于现实生活中的密码攻击。
犯罪
如果攻击针对受害者的浏览器和网络，有些会更容易，有些会更困难。 例如，很容易看到受害者的流量：只需和他坐在同一家有 WiFi 的咖啡馆里即可。 因此，通常建议潜在受害者（即每个人）使用加密连接。 代表受害者向某些第三方网站（例如 Google）发出 HTTP 请求会更加困难，但仍然是可能的。 攻击者必须使用发出请求的脚本引诱受害者访问恶意网页。 Web 浏览器将自动提供相应的会话 cookie。
这看起来很神奇。 如果鲍勃去 evil.com，该网站上的脚本是否可以要求 Google 将 Bob 的密码通过电子邮件发送至 [email protected]？ 嗯，理论上是的，但实际上不是。 这种场景称为跨站请求伪造攻击（、CSRF），并在 90 年代中期流行。 今天如果 evil.com 尝试这个技巧时，Google（或任何有自尊的网站）通常会回复：“很好，但是您用于此交易的 CSRF 令牌将是......嗯...... три триллиона и семь。 请重复这个号码。” 现代浏览器有一种称为“同源策略”的东西，即站点 A 上的脚本无法访问网站 B 发送的信息。因此， evil.com 可以发送请求到 google.com，但无法读取响应或实际完成交易。
我们必须强调，除非 Bob 使用加密连接，否则所有这些保护都是毫无意义的。 攻击者可以简单地读取 Bob 的流量并恢复 Google 的会话 cookie。 有了这个 cookie，他只需打开一个新的 Google 标签而无需离开自己的浏览器，并可以模拟 Bob，而不会遇到讨厌的同源策略。 但不幸的是，对于窃贼来说，这种情况越来越少见。 整个互联网长期以来一直在向未加密的连接宣战，而鲍勃的传出流量可能是加密的，无论他是否喜欢。 此外，从协议实施之初，流量也受到影响。 缩小了 加密前； 这是减少延迟的常见做法。
这就是它发挥作用的地方 （压缩比Infoleak Made Easy，通过压缩比简单泄漏）。 该漏洞由安全研究人员 Juliano Rizzo 和 Thai Duong 于 2012 年 XNUMX 月披露。 我们已经研究了整个理论基础，这使我们能够了解他们做了什么以及如何做。 攻击者可以强制 Bob 的浏览器向 Google 发送请求，然后以压缩、加密的形式监听本地网络上的响应。 因此我们有：
在这里，攻击者控制请求并有权访问流量嗅探器，包括数据包大小。 凯尔西的虚构场景变成了现实。
了解这一理论后，CRIME 的作者创建了一个漏洞，可以窃取 Gmail、Twitter、Dropbox 和 Github 等多种网站的会话 cookie。 该漏洞影响了大多数现代 Web 浏览器，导致发布的补丁悄悄地将压缩功能隐藏在 SSL 中，使其根本无法使用。 唯一免受此漏洞影响的是古老的 Internet Explorer，它根本不使用 SSL 压缩。
狮子狗
2014年XNUMX月，谷歌安全团队在安全界掀起波澜。 他们能够利用 SSL 协议中的一个漏洞，该漏洞在十多年前就已修复。
事实证明，虽然服务器正在运行闪亮的新 TLSv1.2，但许多服务器已经放弃了对旧版 SSLv3 的支持，以向后兼容 Internet Explorer 6。我们已经讨论过降级攻击，因此您可以想象会发生什么。 对握手协议进行精心策划的破坏，服务器已准备好返回到旧的 SSLv3，从根本上破坏了过去 15 年的安全研究。
就历史背景而言， :
传输层安全 (TLS) 是 Internet 上最重要的安全协议。 [..] 几乎您在互联网上进行的每笔交易都依赖于 TLS。 [..] 但 TLS 并不总是 TLS。 该协议开始于 称为“安全套接字层”或 SSL。 有传言称 SSL 的第一个版本非常糟糕，以至于开发人员收集了所有代码的打印输出并将它们埋在新墨西哥州的一个秘密垃圾填埋场中。 因此，第一个公开可用的 SSL 版本实际上是 。 这非常可怕，而且 [..] 它是 90 年代中期的产物，现代密码学家将其视为“” 我们今天所知道的许多最令人发指的加密攻击尚未被发现。 结果，SSLv2 协议的开发人员基本上只能在黑暗中摸索，他们面临着 - 让他们懊恼，但对我们有利，因为对 SSLv2 的攻击为下一代协议留下了宝贵的教训。
这些事件发生后，1996 年，沮丧的 Netscape 从头开始重新设计了 SSL 协议。 结果是 SSL 版本 3，它 .
幸运的是，对于窃贼来说，“一些”并不意味着“全部”。 总体而言，SSLv3 提供了发起 Vodene 攻击所需的所有构建块。 该协议使用 CBC 模式分组密码和不安全的填充方案（这已在 TLS 中得到纠正；因此需要降级攻击）。 如果您还记得我们对 Vaudenay 攻击的原始描述中的填充方案，那么 SSLv3 方案非常相似。
但不幸的是，对于窃贼来说，“相似”并不意味着“相同”。 SSLv3 填充方案是“N 个随机字节后跟数字 N”。 在这些条件下，尝试选择一个假想的密文块，并执行 Vaudene 原始方案的所有步骤：您会发现攻击成功地从相应的明文块中提取了最后一个字节，但没有进一步进行。 解密密文的每 16 个字节是一个很棒的技巧，但这并不是一个胜利。
面对失败，谷歌团队采取了最后的手段：他们转向了一种更强大的威胁模型——CRIME中使用的模型。 假设攻击者是在受害者浏览器选项卡中运行的脚本，并且可以提取会话 cookie，那么攻击仍然令人印象深刻。 虽然更广泛的威胁模型不太现实，但我们在上一节中看到这个特定模型是可行的。
鉴于攻击者拥有更强大的能力，攻击现在可以继续进行。 请注意，攻击者知道加密的会话 cookie 出现在标头中的位置，并控制其前面的 HTTP 请求的长度。 因此，它能够操纵 HTTP 请求，使 cookie 的最后一个字节与块的末尾对齐。 现在这个字节适合解密。 您只需在请求中添加一个字符，Cookie 的倒数第二个字节将保留在同一位置，适合使用相同的方法进行选择。 攻击以这种方式继续，直到cookie文件完全恢复。 它被称为 POODLE：在降级的旧加密上填充 Oracle。
淹
正如我们提到的，SSLv3 有其缺陷，但它与其前身有本质上的不同，因为泄漏的 SSLv2 是不同时代的产物。 在那里你可以在中间打断消息： соглашусь на это только через мой труп 转换成 соглашусь на это; 客户端和服务器可以在线见面，建立信任并在攻击者面前交换秘密，然后攻击者可以轻松地冒充两者。 还有导出密码学的问题，我们在考虑 FREAK 时提到过。 这些是加密的所多玛和蛾摩拉。
2016 年 2 月，一群来自不同技术领域的研究人员聚集在一起，得出了一个惊人的发现：SSLv2 仍在安全系统中使用。 是的，攻击者无法再将现代 TLS 会话降级为 SSLv2，因为该漏洞在 FREAK 和 POODLE 之后已被关闭，但他们仍然可以连接到服务器并自行启动 SSLvXNUMX 会话。
您可能会问，为什么我们关心他们在那里做什么？ 他们有一个易受攻击的会话，但它不应该影响其他会话或服务器的安全 - 对吗？ 嗯，不完全是。 是的，理论上应该是这样。 但不行 - 因为生成 SSL 证书会带来一定的负担，导致许多服务器使用相同的证书，从而为 TLS 和 SSLv2 连接使用相同的 RSA 密钥。 更糟糕的是，由于 OpenSSL 错误，这个流行的 SSL 实现中的“禁用 SSLv2”选项实际上不起作用。
这使得对 TLS 的跨协议攻击成为可能，称为 （使用过时和弱化的加密解密 RSA，使用过时和弱化的加密解密 RSA）。 回想一下，这与短攻击不同。 攻击者不需要充当“中间人”，也不需要让客户端参与不安全的会话。 攻击者只需发起与服务器本身不安全的 SSLv2 会话，攻击弱协议，并恢复服务器的 RSA 私钥。 此密钥对于 TLS 连接也有效，从此时起，再多的 TLS 安全也无法阻止它受到损害。
但要破解它，您需要对 SSLv2 进行有效攻击，这样您不仅可以恢复特定流量，还可以恢复秘密 RSA 服务器密钥。 尽管这是一个复杂的设置，但研究人员可以选择 SSLv2 之后完全关闭的任何漏洞。 他们最终找到了一个合适的选择：Bleichenbacher 攻击，我们之前提到过，我们将在下一篇文章中详细解释。 SSL 和 TLS 受到保护，免受这种攻击，但 SSL 的一些随机功能与出口级加密中的短密钥相结合，使得这种攻击成为可能 .
截至本文发布时，25% 的互联网顶级网站受到 DROWN 漏洞的影响，即使是顽皮的孤独黑客也可以利用有限的资源来实施攻击。 检索服务器的 RSA 密钥需要 440 个小时的计算和 2 美元，SSLvXNUMX 从过时变成了放射性。
等等，《心血》呢？
这不是上述意义上的密码攻击； 这是缓冲区溢出。
休息一下吧
我们从一些基本技术开始：暴力破解、插值、降级、跨协议和预计算。 然后我们研究了一种先进技术，它可能是现代密码攻击的主要组成部分：预言机攻击。 我们花了相当多的时间来弄清楚——不仅了解了底层原理，还了解了两个具体实现的技术细节：针对 CBC 加密模式的 Vaudenay 攻击和针对预压缩加密协议的 Kelsey 攻击。
在回顾降级和预计算攻击时，我们简要概述了 FREAK 攻击，该攻击通过将目标站点降级为弱密钥然后重复使用相同的密钥来使用这两种方法。 在下一篇文章中，我们将保留（非常相似的）Logjam 攻击，该攻击针对公钥算法。
然后我们看了另外三个应用这些原则的例子。 首先，CRIME 和 POODLE：这两种攻击依赖于攻击者在目标明文旁边注入任意明文的能力，然后检查服务器的响应并 然后使用预言机攻击方法，利用这些稀疏信息来部分恢复明文。 CRIME 采用了 Kelsey 对 SSL 压缩的攻击路线，而 POODLE 使用了 Vaudenay 对 CBC 攻击的变体，具有相同的效果。
然后我们将注意力转向跨协议 DROWN 攻击，该攻击使用旧版 SSLv2 协议建立与服务器的连接，然后使用 Bleichenbacher 攻击恢复服务器的密钥。 我们暂时跳过了这次攻击的技术细节； 就像 Logjam 一样，它必须等到我们对公钥密码系统及其漏洞有充分的了解之后才能实现。
在下一篇文章中，我们将讨论高级攻击，例如中间相遇、差分密码分析和生日攻击。 让我们快速探讨一下侧信道攻击，然后继续有趣的部分：公钥密码系统。
来源： habr.com