一些AES CBC加密的误解破解 – Kudelski安全研究
误解破解 /ˈmɪθˌbʌs.tɪŋ/：指说出或展示某些普遍认为是真实的事情实际上并非如此，或与通常描述不同的行为。 ——剑桥词典
对称分组密码如高级加密标准（AES，FIPS 197）是一种广泛使用的密码学原语，在无数平台和系统中用于提供数据机密性和认证。然而，分组密码不能“原样”使用来保护数据，它必须运行在所谓的操作模式下，以安全处理任意长度的消息。存在许多提议和标准化的操作模式，例如NIST目前在SP 800-38文档套件中批准了多种机密性、认证和认证加密模式。
SP 800-38A（当前正在修订中）讨论了五种机密性模式：ECB、CBC、CFB、OFB和CTR。ECB特别糟糕，因为它不是随机的；通常不鼓励使用。CBC、CFB、OFB和CTR都是可塑的。避免可塑性的最佳实践当然是向消息添加认证层，例如使用消息认证码（MAC）；选择要么采用认证加密模式（如GCM或CCM），要么将机密性模式与基于哈希的MAC结合（AES-CBC与HMAC-SHA-256是常见选择）。
我们可以说CBC和CTR可能是最普遍使用的机密性操作模式；它们也构成了认证加密模式如GCM和CCM的核心。普遍偏好可能是CTR，因为CBC相对于它没有真正优势。然而，IV重用对CTR的结果比CBC更具灾难性。CBC操作模式的安全证明可以在这里找到。注意，对于CBC，IV必须为每次加密随机选择（小心，计数器不是安全选择）。
那么，关于CBC操作模式我们能说什么？它的属性是什么？查看这个维基百科页面以了解（不）著名的企鹅图像。确实，密码学智慧（或民间传说？）和维基百科告诉我们关于CBC与其他操作模式的两件事：
- CBC（如ECB）要求底层分组密码（例如AES）在加密（用于CBC加密）和解密（用于CBC解密）两个方向实现。CTR没有这种需求，因为加密和解密基本上是相同的函数，其中底层分组密码用于加密方向。
- CBC加密本质上是串行的，不可并行化，而CBC解密可以。CTR没有这个问题，因为加密和解密可以在块级别完全并行化。
没有上述声明的证明。事实上，两者都（至少部分）错误。
为什么？对于我们这里的讨论，让我们坚持要加密的消息完全提前已知的情况（无在线加密）。在CBC加密中，用户应该选择一个随机IV，然后运行下图所示的过程（消息的4个完整块）：
IV的随机性通过XOR反馈影响所有密文块，该过程看起来本质上是串行的。相应的解密操作如下：
可以看到IV仅用于正确恢复第一个明文。即使IV错误，解密也“几乎”正常。每个明文块仅依赖于两个密文块，因此解密过程可以并行化。
现在，到目前为止还好，但……让我们尝试“反转”CBC加密的方向。如果用户随机选择最后一个密文块而不是IV会怎样？该过程将反向运行如下：
最终，用户将得到一个合法的CBC加密，CBC解密将正常工作并给出正确的明文。只有生成密文和IV的过程不同。注意，IV仍然是“随机选择”的，因为它依赖于最后一个密文块，该块是随机选择的。
但等等！底层分组密码现在用于CBC加密的解密方向。因此，可以使用底层分组密码（例如AES）在解密方向执行CBC加密和解密。第一个误解被破解！
小插曲：事实上，由于AES在加密或解密中都是一个好的伪随机置换（PRP），可以同时使用加密以节省周期和代码大小（这对受限设备有好处，尽管这可能不再被认为是“标准”）：
关于第二个常见信念，注意可以以下列方式运行加密：不是随机生成最后一个密文块，可以将消息分成两部分并随机生成中间密文块（下图中C2）。然后，他可以如上所述对第一部分消息向后进行，并对第二部分消息进行经典CBC加密向前进行：
这有缺点，即CBC加密需要底层分组密码的加密和解密两个方向，但两个过程显然可以并行运行。因此，如果我们有两个AES实例，我们可以为CBC加密实现并行化因子2。第二个误解也被破解！
这种修改后的CBC加密流程是安全的。事实上，CBC模式安全证明的核心是攻击者区分CBC加密与垃圾发射器（即吐出随机数据而不是真实加密结果的预言机）的优势界限。CBC的现有证明将此优势与导致底层分组密码（视为PRP）输入碰撞的概率联系起来。如果攻击者成功产生碰撞，他就赢了，可以区分CBC加密预言机和垃圾预言机。
该论文通过关键观察来限制此概率：与明文块XOR以形成PRP输入的值总是独立于它们并均匀随机选择，因为它们要么是IV，要么是应用PRP于新输入的结果。但修改后的流程也是如此，其中最后一个密文块是随机选择的。因此，我们可以为修改后流程（选择随机最后一个密文块而不是随机IV）的CBC加密提供完全相同的安全证明。
注意，对于给定消息和给定分组密码密钥，并考虑直接CBC加密，每个密文块完全由IV选择决定，显然该关系是双射。事实上，可以将IV视为来自先前（不存在）迭代的“零”密文，并且如果沿着链“移动”并选择中间密文块，考虑仍然有效：所有后续密文块完全确定，它们的值是所选值在块空间上的双射。
考虑到修改流程CBC加密在反向运行切换分组密码方向时，这也是正确的。每当选择中间密文块并在两个方向生成其他块时，对所有密文块也保持正确。
因此，在我们的修改流程中，如果均匀随机选择一个密文块，所有其他块（包括IV）也均匀随机分布（尽管显然不独立）；但均匀随机选择的IV正是直接CBC加密的起点。
结论
我们因此得出结论，对手区分原始或修改流程CBC加密过程的优势应该可以忽略。所以，不要太在意密码学民间传说，享受并行CBC加密吧！