为什么在上一轮AES中省略了MixColumns？

#1 楼

昨天刚刚从图书馆取了《 Rijndael设计》，我也对这个问题进行了了解。 Fixee在评论中写道：


但是，我的问题不是关于安全性的问题，而是
“ MixColumns的省略如何使逆密码类似于密码“
”和“这对实现密码有何帮助？”


加密在每一轮中都有这些步骤（清单3.2，第34页），并带有附加的AddRoundKey在开始时一小段结束时：

Round(State, ExpandedKey[i]) {
    SubBytes(State);
    ShiftRows(State);
    MixColumns(State);
    AddRoundKey(State, ExpandedKey[i]);
}

以一种简单的方式进行解密时，解密看起来是这样的（清单3.5，第47页）（带有一个较短的初始回合）：

InvRound(State, ExpandedKey[i]) {
    AddRoundKey(State, ExpandedKey[i]);
    InvMixColumns(State);
    InvShiftRows(State);
    InvSubBytes(State);
}

如评论中所述，如果不省略一个MixColumns步骤，则所有10回合将是相同的（就像那些上面的代码），我们可以将总的加密和解密处理为

AddRoundKey(ExpandedKey[0])
for i = 1 .. 10:
    Round(State, ExpandedKey[i])

for i = 10 .. 1:
    InvRound(State, ExpandedKey[i])
AddRoundKey(ExpandedKey[0])

如果将AddRoundKey移至逆函数的末尾，则它看起来像这样： br />

InvRound'(State, ExpandedKey[i]) {
    InvMixColumns(State);
    InvShiftRows(State);
    InvSubBytes(State);
    AddRoundKey(State, ExpandedKey[i]);
}

AddRoundKey(ExpandedKey[10])
for i = 9 .. 0:
    InvRound'(State, ExpandedKey[i])

以这种形式，我们会有一个模拟ilar的全局加密结构和功能，但是用于加密和解密的圆形函数在结构上仍然不同。我们（作为Rijndael的假想发明者）可以做得更好。


回到我们的（朴素的）逆循环函数：

InvRound(State, ExpandedKey[i]) {
    AddRoundKey(State, ExpandedKey[i]);
    InvMixColumns(State);
    InvShiftRows(State);
    InvSubBytes(State);
}

通过用修改后的ExpandedKey交换InvMixColumns和AddRoundKey），以及交换InvShiftRows和InvSubBytes（因为其中一个单独处理每个字节，另一个仅转置整个字节），我们看到这等效于此： br />

InvRound(State, ExpandedKey[i]) {
    InvMixColumns(State);
    AddRoundKey(State, InvMixColumns(ExpandedKey[i]));
    InvSubBytes(State);
    InvShiftRows(State);
}

（开始时我们还有一个较短的组，而结尾处是一个最终的AddRoundKey。）

现在，通过在回合结束时使用同时使用InvMixColums和AddRoundKey的分组，我们将InvSubBytes的位置与InvShiftRows交换，并将InvMixColumns的位置与AddRoundKey交换以获取此等效描述（表3.8，第49页），其中再短一点的是最后一个回合，还有一个初始AddRoundKey：

EqRound (State, EqExpandedKey[i]) {
    InvSubBytes(State);
    InvShiftRows(State);
    InvMixColumns(State);
    AddRoundKey(State, EqExpandedKey[i]);
}

但是，这种回合结构与初始AddRoundKey相结合，并不是加密的逆过程。加密的最后一个MixColumns没有对应的InvMixColumns，解密的最后一个InvMixColumns没有对应的MixColumns。我们将通过省略上一轮加密的MixColumns步骤和上一轮解密的​​InvMixColums步骤来解决此问题。有了这一更改，由于最后一轮MixColumns / InvMixColumns步骤的加密和解密均被忽略，因此它们的轮结构保持不变，解密是加密的逆过程。

这种替换的组合是，移位和列混合（按此顺序）看起来与加密操作序列非常相似，并且现在假定比直接反转中使用的逆序列更有效地实现。

此外，我们可以共享一些代码（用于软件实现）或芯片区域（用于硬件实现）以进行加密和解密。

当然，我们现在需要对解密的关键时间表进行调整：将InvMixColumns应用于每个回合键，除了第一个和最后一个键。由于密钥调度只对多个块执行一次，因此这不是一个大开销。

在具有某些快速缓存（或ROM）的32位（或更大）处理器上，可以通过查找来为每个32位列实现这种替换，行移位和列混合（与任何键无关）的序列。四个1kB查找表中的四个32位值（取决于旧状态下的不同字节），并将它们异或。通过在查找后使用不同的旋转，我们可以仅使用这些表之一（1 kB）。 （详细信息在本书第58/59页的4.2节中。）该表的一部分也可以用于最后一轮（没有列混合）。

这里我们可以对不同（一组）表使用相同的代码进行解密和加密。 （这些表不会使用不同的密钥进行更改，因此我们将它们放入ROM中，或在首次需要它们时进行计算。）

（这些查找表为不适合它们的攻击定时提供了一种方式完全在处理器缓存中，和/或被同时运行的其他程序从缓存中删除。）

#2 楼

根据Rijndael设计文档（第7页顶部）：


为了使密码及其逆结构更相似，最后一轮的线性混合层不同于其他回合中的混合层。可以证明，这不会以任何方式提高或降低密码的安全性。这类似于在DES的最后一轮中没有交换操作。


在常规AES轮中，MixColumns在AddRoundKey操作之前。但是，可以交换这些操作的顺序。通过先对AddRoundKey操作进行一点修改，然后再对MixColumns进行一些修改，您可以获得相同的结果。因此，人们认为最终的MixColumns不会增加任何安全性，因为它是无关键的可逆操作，可以作为最后一轮的最后一步。

但是从理论上讲，您可以这样做接下来的攻击，有安全后果。考虑一下在最后一轮加密中执行MixColumns的AES变体。为了攻击解密功能，对手可以交换MixColumns和AddRoundKey的顺序，以便她可以免费撤消MixColumns。现在，假设她能够（以某种方式）恢复有关AddRoundKey中使用的回合密钥的一些信息。因为她调换了操作，所以恢复的实际上不是密钥调度表吐出的有关圆形密钥的信息，而是有关对其应用了反转MixColumns的圆形密钥的信息。

在简而言之，如果信息实际上是关于最后一轮密钥的转换版本，则很难使用她所知道的有关最后一轮密钥的信息来确定有关倒数第二个密钥的信息。 （此攻击由@Samuel Neves链接到了已删除的评论中，因此归功于他。）